hw4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q1.\n",
    "\n",
    "Use github to integrate our math library from the lab with Travis CI and Coveralls.\n",
    "In the cell below, put a link to your github `cs207test` repo so we can track your badges."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://github.com/volauvent/cs207test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q2.\n",
    "\n",
    "Take the implementation of binary search from a previous lecture/lab. Write unit tests for the algorithm (remember we have doctests in there), stripping the doctests down to those that illustrate the interface for a user. How do these doctests deal with the concerns we had?\n",
    "\n",
    "Make sure you have good test coverage. You will be integrationg with Travis and Coveralls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting binsearch.py\n"
     ]
    }
   ],
   "source": [
    "%%file binsearch.py\n",
    "def binary_search(da_array: list, needle, left:int=0, right:int=-1) -> int:\n",
    "    \"\"\"\n",
    "    An algorithm that operates in O(lg(n)) to search for an element\n",
    "    in an array sorted in ascending order.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    da_array : list\n",
    "        a list of \"comparable\"items sorted in non-descending order\n",
    "    needle: an item to find in the array; it may or may not\n",
    "        be in the array\n",
    "    left: int, optional\n",
    "        the left index in the array to search from. Default 0\n",
    "    right: int, optional\n",
    "        the right index in the array to search to. Default is -1\n",
    "        in which case we will use the end of the array `len(da_array) - 1`\n",
    "        \n",
    "    Returns\n",
    "    -------\n",
    "    index: int\n",
    "        an integer representing the index of `needle` if found, and -1\n",
    "        otherwise\n",
    "        \n",
    "    Notes\n",
    "    -----\n",
    "    PRE: `da_array` is sorted in non-decreasing order (thus items in\n",
    "        `da_array` must be comparable: implement < and ==)\n",
    "    POST: \n",
    "        - `da_array` is not changed by this function (immutable)\n",
    "        - returns `index`=-1 if `needle` is not in `da_array`\n",
    "        - returns an int `index ` in [0:len(da_array)] if\n",
    "          `index` is in `da_array`\n",
    "    INVARIANTS:\n",
    "        - If `needle` in `da_array`, needle in `da_array[rangemin:rangemax]`\n",
    "          is a loop invariant in the while loop below.\n",
    "          \n",
    "    Examples\n",
    "    --------\n",
    "    >>> input = list(range(10))\n",
    "    >>> binary_search(input, 5)\n",
    "    5\n",
    "    >>> binary_search(input, 4.5)\n",
    "    -1\n",
    "    >>> binary_search(input, 10)\n",
    "    -1\n",
    "    >>> binary_search([5], 5)\n",
    "    0\n",
    "    >>> binary_search([5], 4)\n",
    "    -1\n",
    "    >>> import numpy as np\n",
    "    >>> binary_search([1,2,np.inf], 2)\n",
    "    1\n",
    "    >>> binary_search([1,2,np.inf], np.inf)\n",
    "    2\n",
    "    >>> binary_search(input, 5, 1,3)\n",
    "    -1\n",
    "    >>> binary_search(input, 2, 1,3)\n",
    "    2\n",
    "    >>> binary_search(input, 2, 3, 1)\n",
    "    -1\n",
    "    >>> binary_search(input, 2, 2, 2)\n",
    "    2\n",
    "    >>> binary_search(input, 5, 2, 2)\n",
    "    -1\n",
    "    \"\"\"\n",
    "    if da_array is None:\n",
    "        return -1\n",
    "    if type(left) != int or type(right) != int:\n",
    "        raise TypeError('Left and right must be integers!')\n",
    "        \n",
    "    if left==0:\n",
    "        rangemin = 0\n",
    "    else:\n",
    "        rangemin = left\n",
    "    if right==-1:\n",
    "        rangemax=len(da_array) - 1\n",
    "    else:\n",
    "        rangemax=right\n",
    "    \n",
    "    if rangemax >= len(da_array):\n",
    "        raise ValueError('Right crosses the boundary!')\n",
    "    \n",
    "    if  rangemin == rangemax:\n",
    "        return rangemin if da_array[rangemin] == needle else -1\n",
    "    \n",
    "    for i in range(rangemin, rangemax):\n",
    "        try:\n",
    "            cmp = da_array[i] > da_array[i + 1]\n",
    "        except:\n",
    "            raise TypeError('Array contains uncompared items!')\n",
    "        if da_array[i] > da_array[i + 1]:\n",
    "            raise ValueError('Array must be in increasing order!')\n",
    "    \n",
    "    while True:\n",
    "        \"needle in da_array => needle in da_array[rangemin:rangemax]\"   \n",
    "        if rangemin > rangemax:\n",
    "            index = -1\n",
    "            return index\n",
    "        #If rangemin and rangemax are both very high we do not want overflow,\n",
    "        #so get the midpoint like this:\n",
    "        midpoint = rangemin + (rangemax - rangemin)//2\n",
    "        if da_array[midpoint] > needle:#lower part\n",
    "            rangemax = midpoint - 1\n",
    "        elif da_array[midpoint] < needle:\n",
    "            rangemin = midpoint + 1\n",
    "        else:\n",
    "            index = midpoint\n",
    "            return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting test_binsearch.py\n"
     ]
    }
   ],
   "source": [
    "%%file test_binsearch.py\n",
    "from binsearch import binary_search\n",
    "from pytest import raises\n",
    "import numpy as np\n",
    "\n",
    "def test_bad_input_results():\n",
    "    with raises(TypeError):\n",
    "        binary_search([1,2,3,4,5], 2,'a')\n",
    "    with raises(TypeError):\n",
    "        binary_search([(1,2),3,4,5], 2)\n",
    "    with raises(ValueError):\n",
    "        binary_search([5,4,3,2,1], 2)\n",
    "    with raises(TypeError):\n",
    "        binary_search([1,2,3,4,5], 2, 0.5, 1.4)\n",
    "    with raises(ValueError):\n",
    "        binary_search([1,2,3,4,5], 2, 1, 100)\n",
    "        \n",
    "def test_right_input_results():\n",
    "    assert binary_search([1,2,3,4,5], 2) == 1\n",
    "    assert binary_search([], 2) == -1\n",
    "    assert binary_search(None, 2) == -1\n",
    "    assert binary_search([1,2,3,4,5], 2) != -1\n",
    "    assert binary_search([1,2,3,4,5], 6) == -1\n",
    "    assert binary_search([1,2,3,4,5], 2, 1, 3) == 1\n",
    "    assert binary_search([1,2,3,4,5], 2, 3, 4) == -1\n",
    "    assert binary_search([1,2,3,4,5], 2, 3, 4) == -1\n",
    "    assert binary_search([1,2,3,4,5], 2, 4, 3) == -1\n",
    "    assert binary_search([1,2,3,np.inf], 2) == 1\n",
    "    assert binary_search([1,2,3,np.inf], np.inf) == 3\n",
    "    assert binary_search([1], 1) == 0\n",
    "    assert binary_search([1], 2) == -1\n",
    "\n",
    "def test_non_num_input_results():\n",
    "    assert binary_search(['a','b','c'],'b') == 1\n",
    "    assert binary_search(['a','b','c'],'d') == -1\n",
    "    assert binary_search(\"abcd\",'b') == 1\n",
    "    assert binary_search(\"abcd\",'e') == -1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition, we should be **systematic** about testing our code. You should at-least jave some tests like this:\n",
    "\n",
    "1. We should test with wierd data, ie a wierd array: does it have NANs, is it numeric? Does it have 0 elelemts? 1 element? 2?...ie test the boundaries\n",
    "\n",
    "2. Then think of how the needle relates to the above. Try needles less than or greter than the range in the sorted array, besides needles inbetween (in both cases the needle not being in the array). Try needles at the extremes of the array.\n",
    "\n",
    "3. test the integration of 1 and 2 to make sure something has not gone wrong there.\n",
    "\n",
    "Note: you can always compare your answers with linear search implemented in python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For reference, here are some of our concerns from that lab:\n",
    "\n",
    "#### What's happened to our issue from before?\n",
    "\n",
    "- What if the value is not there in the array? What if it is there multiple times? what are we returning (why the -1). Are we consistent in our returning?\n",
    "\n",
    "We return -1 if the element is not in the array. If it is there multiple times, we will return one of them: it is not defined which. We are consistent by always returning an int, choosing one which cannot be an index.\n",
    "\n",
    "- What if rangemax is so high as to create overflow: \n",
    "\n",
    "We fixed it by using the difference and have documented it in the algorithm\n",
    "\n",
    "\n",
    "- what types are we supporting? . \n",
    "\n",
    "It seems that as long as we have a notion of equals `==`, and a notion of `<` to support sorting we are set. We should document this.\n",
    "\n",
    "- what happens if we have a NaN in our array? Infty?\n",
    "\n",
    "If our preconditions are violated by the user, we can do anything. Doing it nicely might be costly. so we wont.\n",
    "\n",
    "\n",
    "- what if da_array was not an array?\n",
    "\n",
    "The user violated the pre-conditions. Anything could happen. We could check for a list\n",
    "but yhen that would hurt a special class which implemented the python sequence protocol\n",
    "\n",
    "- What happens if array is not sorted: \n",
    "\n",
    "The user violated the pre-conditions. We could return an error, violate post conditions. If we sort it we'd violate the o(lg(n)) notion. (fixing it seems dubious). Can we check if its sorted? This is naively O(n) and breaks our performance specifications. We can create a guard to terminate the array at more than n iterations for the infinite case or let the user have enough rope to hang themselves\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Submit** this to us by creating a repo `cs207binsearch` under your userid with a file `binarysearch.py` and accompanying test file(s). Intergrate with Travis CI and Coveralls. Set up badges on the README of your repo. Write the link to your repo below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://github.com/volauvent/cs207binsearch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}