lectures/Sequences.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "> Changing a data structure in a slow program can work the same way an organ transplant does in a sick patient. Important classes of abstract data types such as containers, dictionaries, and priority queues, have many different but functionally equivalent data structures that implement them. Changing the data structure does not change the correctness of the program, since we presumably replace a correct implementation with a different correct implementation. However, the new implementation of the data type realizes different tradeoffs in the time to execute various operations, so the total performance can improve dramatically. Like a patient in need of a transplant, only one part might need to be replaced in order to fix the problem.\n",
    "\n",
    "Steven S Skiena. The Algorithm Design Manual "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Sequences and their Abstractions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### What is a sequence?\n",
    "\n",
    "Consider the notion of **Abstract Data Types**. \n",
    "\n",
    "The idea there is that one data type might be implemented in terms of another, or some underlying code, not even in python. \n",
    "\n",
    "As long as the interface and contract presented to the user is solid, we can change the implementation below. \n",
    "\n",
    "More on this later.."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The **dunder methods** in python are used towards this purpose. \n",
    "\n",
    "In python a sequence is something that follows the sequence protocol. An example of this is a python list. \n",
    "\n",
    "This entails defining the `__len__` and `__getitem__` methods. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist=[1,2,3,4]\n",
    "len(alist)#calls alist.__len__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist[2]#calls alist.__getitem__(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Lists also support slicing. How does this work?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist[2:4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "To see this lets create a dummy sequence which shows us what happens. This sequence does not create any storage, it just implements the protocol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class DummySeq:\n",
    "    \n",
    "    def __len__(self):\n",
    "        return 42\n",
    "    \n",
    "    def __getitem__(self, index):\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = DummySeq()\n",
    "len(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d[5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "slice(67, 98, None)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d[67:98]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Slicing creates a `slice object` for us of the form `slice(start, stop, step)` and then python calls `seq.__getitem__(slice(start, stop, step))`.\n",
    "\n",
    "What about two dimensional indexing, if we wanted to create a two dimensional structure?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(slice(67, 98, 2), 1)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d[67:98:2,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(slice(67, 98, 2), slice(1, 10, None))"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d[67:98:2,1:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "As sequence writers, our job is to interpret these in `__getitem__`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "#taken from Fluent Python\n",
    "import numbers, reprlib\n",
    "\n",
    "class NotSoDummySeq:    \n",
    "    def __init__(self, iterator):\n",
    "        self._storage=list(iterator)\n",
    "        \n",
    "    def __repr__(self):\n",
    "        components = reprlib.repr(self._storage)\n",
    "        components = components[components.find('['):]\n",
    "        return 'NotSoDummySeq({})'.format(components)\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self._storage)\n",
    "    \n",
    "    def __getitem__(self, index):\n",
    "        cls = type(self)\n",
    "        if isinstance(index, slice):\n",
    "            return cls(self._storage[index])\n",
    "        elif isinstance(index, numbers.Integral): \n",
    "            return self._storage[index]\n",
    "        else:\n",
    "            msg = '{cls.__name__} indices must be integers' \n",
    "            raise TypeError(msg.format(cls=cls))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d2 = NotSoDummySeq(range(10))\n",
    "len(d2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "NotSoDummySeq([0, 1, 2, 3, 4, 5, ...])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d[4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "NotSoDummySeq([2, 3])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d2[2:4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "NotSoDummySeq indices must be integers",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-15-ae2b261447b5>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0md2\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-10-bae9aa90bd14>\u001b[0m in \u001b[0;36m__getitem__\u001b[0;34m(self, index)\u001b[0m\n\u001b[1;32m     22\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     23\u001b[0m             \u001b[0mmsg\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m'{cls.__name__} indices must be integers'\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 24\u001b[0;31m             \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmsg\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcls\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mcls\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: NotSoDummySeq indices must be integers"
     ]
    }
   ],
   "source": [
    "d2[1,4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Just BTW, It might seem that slices are only useful in writing dunder methods like `__getitem__`, but this is not the case. Imagine you are writing code to parse a file:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ralph 1 2\n",
      "Midge 3 4\n"
     ]
    }
   ],
   "source": [
    "mystring=\"\"\"\n",
    "Ralph 1 2\n",
    "Midge 3 4\n",
    "\"\"\"\n",
    "name = slice(0,5)\n",
    "weight =  slice(5,7)\n",
    "height =  slice(7,9)\n",
    "for line in mystring.split('\\n')[1:-1]:\n",
    "    print(line[name], line[weight].strip(), line[height].strip())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Linked Lists\n",
    "\n",
    "Lets next think of how a list with a pointer to its next element might be constructed in python. We'll use this notion of a \"linked list\" to illustrate sequences.\n",
    "\n",
    "#### Nested Pairs\n",
    "\n",
    "![](http://wla.berkeley.edu/~cs61a/fa11/lectures/img/pair.png)\n",
    "\n",
    "(from stanford cs61a, http://wla.berkeley.edu/~cs61a/fa11/lectures/objects.html#nested-pairs, this is the **box and pointer** notation.)\n",
    "\n",
    "The diagram above can be represented in python as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "pair = (1,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "But this representation lacks a certain power. What if we used this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "pair = (1, (2, None))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Which can generalize to something which looks like this:\n",
    "\n",
    "![](http://wla.berkeley.edu/~cs61a/fa11/lectures/img/sequence.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "linked_list = (1, (2, (3, (4, None))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe width=\"1000\" height=\"800\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=linked_list+%3D+(1,+(2,+(3,+(4,+None%29%29%29%29&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=2&rawInputLstJSON=%5B%5D&curInstr=1&codeDivWidth=300&codeDivHeight=200\"> </iframe>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "HTML('<iframe width=\"1000\" height=\"800\" frameborder=\"0\" src=\"http://pythontutor.com/iframe-embed.html#code=linked_list+%3D+(1,+(2,+(3,+(4,+None%29%29%29%29&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=2&rawInputLstJSON=%5B%5D&curInstr=1&codeDivWidth=300&codeDivHeight=200\"> </iframe>')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Quick Linked List implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, (2, (3, None)))"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "emptyll = None\n",
    "\n",
    "def make_ll(first, rest):\n",
    "        return (first, rest)\n",
    "def first(ll):\n",
    "        return ll[0]\n",
    "def rest(ll):\n",
    "        return ll[1]\n",
    "myll = make_ll(1,make_ll(2, make_ll(3,emptyll)))\n",
    "myll"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 | (2, (3, None)) | 2\n"
     ]
    }
   ],
   "source": [
    "print(first(myll), \"|\", rest(myll), \"|\", first(rest(myll)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Why might you want to use a linked list like the example above?\n",
    "\n",
    "- you allocate memory only when you want to use it\n",
    "- inserting a new element is cheaper than in a fixed size array\n",
    "- gateway drug to other \"pointer\"ish and hierarchical structures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Linked Lists: A python implementation with the sequence protocol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from doctest import run_docstring_examples as dtest\n",
    "import numbers\n",
    "import reprlib\n",
    "class LL:\n",
    "    \"\"\"\n",
    "    >>> A = LL()  \n",
    "    >>> A[0]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    IndexError: trying to index an empty LL\n",
    "    >>> A.insert_front(1)\n",
    "    >>> A[0]\n",
    "    1\n",
    "    >>> A.insert_back(2)\n",
    "    >>> A[1]\n",
    "    2\n",
    "    >>> A\n",
    "    LL([1,...])\n",
    "    >>> myll = LL.from_components([1,2])\n",
    "    >>> myll[1]\n",
    "    1\n",
    "    >>> len(myll)\n",
    "    2\n",
    "    >>> myll[2]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    IndexError: LL index out of range\n",
    "    >>> myll[0:1]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    TypeError: LL indices must be integers\n",
    "    \"\"\"\n",
    "    @classmethod\n",
    "    def from_components(cls, components):\n",
    "        inst = cls(components[0])\n",
    "        for c in components[1:]:\n",
    "            inst.insert_front(c)\n",
    "        return inst\n",
    "        \n",
    "    def __init__(self, head=None):\n",
    "        if head is None:\n",
    "            self._headNode = None\n",
    "        else:\n",
    "            self._headNode = [head, None]\n",
    "            \n",
    "    def insert_front(self, element):\n",
    "        new_node = [element, None]\n",
    "        new_node[1] = self._headNode\n",
    "        self._headNode = new_node\n",
    "        \n",
    "    def insert_back(self, element):\n",
    "        new_node = [element, None]\n",
    "        curr_ptr = self._headNode\n",
    "        while curr_ptr[1] is not None:\n",
    "            curr_ptr = curr_ptr[1]\n",
    "        curr_ptr[1]= new_node\n",
    "        \n",
    "    def __repr__(self):\n",
    "        class_name = type(self).__name__\n",
    "        if len(self)==0:\n",
    "            components=\"\"\n",
    "        else:\n",
    "            components = reprlib.repr(self[0])\n",
    "        return '{}([{},...])'.format(class_name,components)\n",
    "\n",
    "\n",
    "    def __len__(self):\n",
    "        curr_ptr = self._headNode\n",
    "        count = 0\n",
    "        if curr_ptr==None:\n",
    "            return 0\n",
    "        while 1:\n",
    "            count = count + 1\n",
    "            if curr_ptr[1] is None:\n",
    "                break\n",
    "            curr_ptr = curr_ptr[1]\n",
    "        return count    \n",
    "    \n",
    "    def __getitem__(self, index):\n",
    "        class_name = type(self).__name__\n",
    "        if isinstance(index, numbers.Integral): \n",
    "            curr_ptr = self._headNode\n",
    "            if curr_ptr==None:\n",
    "                msg = 'trying to index an empty {class_name}' \n",
    "                raise IndexError(msg.format(class_name=class_name))\n",
    "            next_ptr = self._headNode[1]\n",
    "            count = 0\n",
    "            while 1:\n",
    "                if index == count:\n",
    "                    return curr_ptr[0]\n",
    "                if curr_ptr[1] is None:\n",
    "                    msg = '{class_name} index out of range' \n",
    "                    raise IndexError(msg.format(class_name=class_name))       \n",
    "                count += 1\n",
    "                curr_ptr = curr_ptr[1]\n",
    "        else:\n",
    "            msg = '{class_name} indices must be integers' \n",
    "            raise TypeError(msg.format(class_name=class_name))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finding tests in NoName\n",
      "Trying:\n",
      "    A = LL()  \n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    A[0]\n",
      "Expecting:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    IndexError: trying to index an empty LL\n",
      "ok\n",
      "Trying:\n",
      "    A.insert_front(1)\n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    A[0]\n",
      "Expecting:\n",
      "    1\n",
      "ok\n",
      "Trying:\n",
      "    A.insert_back(2)\n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    A[1]\n",
      "Expecting:\n",
      "    2\n",
      "ok\n",
      "Trying:\n",
      "    A\n",
      "Expecting:\n",
      "    LL([1,...])\n",
      "ok\n",
      "Trying:\n",
      "    myll = LL.from_components([1,2])\n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    myll[1]\n",
      "Expecting:\n",
      "    1\n",
      "ok\n",
      "Trying:\n",
      "    len(myll)\n",
      "Expecting:\n",
      "    2\n",
      "ok\n",
      "Trying:\n",
      "    myll[2]\n",
      "Expecting:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    IndexError: LL index out of range\n",
      "ok\n",
      "Trying:\n",
      "    myll[0:1]\n",
      "Expecting:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    TypeError: LL indices must be integers\n",
      "ok\n"
     ]
    }
   ],
   "source": [
    "from doctest import run_docstring_examples as dtest\n",
    "dtest(LL, globals(), verbose = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "LL([5,...])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myll=LL.from_components([1,2,32,-4,5])\n",
    "myll"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-4, 32)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(myll), max(myll)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Linked List Complexity\n",
    "\n",
    "From this implementation we can see some things:\n",
    "\n",
    "- Insertion at the front of a linked list is O(1). Insertion at the back is O(n). \n",
    "- Searching a linked list is like linear search on an array: O(n)\n",
    "- What about deletion? What about slices? See the homework :-)\n",
    "- What about indexing? Its O(n) as you must follow the pointers.\n",
    "- Setting a value (not implemented here) follows the indexing complexity.\n",
    "\n",
    "The space complexity is O(n).\n",
    "\n",
    "How does this contrast with a regular array?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### From pointers to Iterators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "One can simply follow the `next` pointers to the next **POSITION** in a linked list. This suggests an abstraction of the **position** or pointer to an **iterator**, an abstraction which allows us to treat arrays and linked lists with an identical interface. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The salient points of this abstraction are:\n",
    "\n",
    "- the notion of a `next` abstracting away the actual gymnastics of where to go next in a storage system\n",
    "- the notion of a `first` to a `last` that `next` takes us on a journey from and to respectively\n",
    "\n",
    "- we already implemented the sequence protocol, but \n",
    "- now we suggest an additional abstraction that is more fundamental than the notion of a sequence: the **iterable**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterators and Iterables in python\n",
    "\n",
    "Just as a sequence is something implementing `__getitem__` and `__len__`, an **Iterable** is something implementing `__iter__`. \n",
    "\n",
    "`__len__` is not needed and indeed may not make sense. \n",
    "\n",
    "The following example is taken from Fluent Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import reprlib\n",
    "class Sentence:\n",
    "    def __init__(self, text): \n",
    "        self.text = text\n",
    "        self.words = text.split()\n",
    "        \n",
    "    def __getitem__(self, index):\n",
    "        return self.words[index] \n",
    "    \n",
    "    def __len__(self):\n",
    "        #completes sequence protocol, but not needed for iterable\n",
    "        return len(self.words) \n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'Sentence(%s)' % reprlib.repr(self.text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(11, 'little', Sentence('Mary had a l...hite as snow.'))"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#sequence'\n",
    "a= Sentence(\"Mary had a little lamb whose fleece was white as snow.\")\n",
    "len(a), a[3], a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Mary', 'whose')"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(a), max(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Mary',\n",
       " 'had',\n",
       " 'a',\n",
       " 'little',\n",
       " 'lamb',\n",
       " 'whose',\n",
       " 'fleece',\n",
       " 'was',\n",
       " 'white',\n",
       " 'as',\n",
       " 'snow.']"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "To iterate over an object x, python automatically calls `iter(x)`. An **iterable** is something which, when `iter` is called on it, returns an **iterator**.\n",
    "\n",
    "(1) if `__iter__` is defined, calls that to implement an iterator.\n",
    "\n",
    "(2) if not  `__getitem__` starting from index 0\n",
    "\n",
    "(3) otherwise raise TypeError\n",
    "\n",
    "Any Python sequence is iterable because they implement `__getitem__`. The standard sequences also implement `__iter__`; for future proofing you should too because  (2) might be deprecated in a future version of python.\n",
    "\n",
    "This:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mary\n",
      "had\n",
      "a\n",
      "little\n",
      "lamb\n",
      "whose\n",
      "fleece\n",
      "was\n",
      "white\n",
      "as\n",
      "snow.\n"
     ]
    }
   ],
   "source": [
    "for i in a:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "is implemented something like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mary\n",
      "had\n",
      "a\n",
      "little\n",
      "lamb\n",
      "whose\n",
      "fleece\n",
      "was\n",
      "white\n",
      "as\n",
      "snow.\n"
     ]
    }
   ],
   "source": [
    "it = iter(a)\n",
    "while True:\n",
    "    try:\n",
    "        nextval = next(it)\n",
    "        print(nextval)\n",
    "    except StopIteration:\n",
    "        del it\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "`it` is an iterator. \n",
    "\n",
    "An iterator defines both `__iter__` and a `__next__` (the first one is only required to make sure an *iterator* IS an *iterable*). \n",
    "\n",
    "Calling `next` on an iterator will trigger the calling of `__next__`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mary\n",
      "had\n",
      "a\n",
      "little\n",
      "lamb\n",
      "whose\n",
      "fleece\n",
      "was\n",
      "white\n",
      "as\n",
      "snow.\n"
     ]
    }
   ],
   "source": [
    "it=iter(a)#an iterator defines `__iter__` and can thus be used as an iterable\n",
    "for i in it:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Mary', 'had', 'a')"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = iter(a)\n",
    "next(it), next(it), next(it)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "So now we can completely abstract away a sequence in favor an iterable (ie we dont need to support indexing anymore). From Fluent:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class SentenceIterator:\n",
    "    def __init__(self, words): \n",
    "        self.words = words \n",
    "        self.index = 0\n",
    "        \n",
    "    def __next__(self): \n",
    "        try:\n",
    "            word = self.words[self.index] \n",
    "        except IndexError:\n",
    "            raise StopIteration() \n",
    "        self.index += 1\n",
    "        return word \n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "    \n",
    "class Sentence:#an iterable\n",
    "    def __init__(self, text): \n",
    "        self.text = text\n",
    "        self.words = text.split()\n",
    "        \n",
    "    def __iter__(self):\n",
    "        return SentenceIterator(self.words)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return 'Sentence(%s)' % reprlib.repr(self.text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "s2 = Sentence(\"While we could have implemented `__next__` in Sentence itself, making it an iterator, we will run into the problem of exhausting an iterator'.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "object of type 'Sentence' has no len()",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-42-4b382c72e9ab>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: object of type 'Sentence' has no len()"
     ]
    }
   ],
   "source": [
    "len(s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "While\n",
      "we\n",
      "could\n",
      "have\n",
      "implemented\n",
      "`__next__`\n",
      "in\n",
      "Sentence\n",
      "itself,\n",
      "making\n",
      "it\n",
      "an\n",
      "iterator,\n",
      "we\n",
      "will\n",
      "run\n",
      "into\n",
      "the\n",
      "problem\n",
      "of\n",
      "exhausting\n",
      "an\n",
      "iterator'.\n"
     ]
    }
   ],
   "source": [
    "for i in s2:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "While\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "('we', 'While')"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s2it=iter(s2)\n",
    "print(next(s2it))\n",
    "s2it2=iter(s2)\n",
    "next(s2it),next(s2it2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "While we could have implemented `__next__` in Sentence itself, making it an iterator, we will run into the problem of \"exhausting an iterator\". \n",
    "\n",
    "The iterator above keeps state in `self.index` and we must be able to start anew by creating a new instance if we want to re-iterate. Thus the `__iter__` in the iterable, simply returns the `SentenceIterator`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Sentence', 'will')"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(s2), max(s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that min and max will work even though we now DO NOT satisfy the sequence protocol, but rather the ITERABLE protocol, as its a pairwise comparison, which can be handled via iteration. The take home message is that in programming with these iterators, these generlization of pointers, we dont need either the length or indexing to work to implement many algorithms: we have abstracted these away."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A brief addendum on trees\n",
    "\n",
    "A tree is:\n",
    "\n",
    "- a hierarchical data structure that has a bunch of items,\n",
    "- each of which may have a value\n",
    "- some of which may point to other such items, and some that dont (leaf nodes)\n",
    "- each item is pointed to by exactly one other item, with the sole exception of the root."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Trees arise everywhere:\n",
    "\n",
    "- in parsing of code\n",
    "- evolutionary trees in biology\n",
    "- language origin trees\n",
    "- unix file system\n",
    "- html tags on this page\n",
    "\n",
    "Just like with lists, one can consider looking at a tree in two ways: a collection of nodes, or a tree with a root and multiple sub-tree's."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Once again, one can represent trees using the recursive data structures we used to represent linked lists (from cs61a):\n",
    "\n",
    "![](http://wla.berkeley.edu/~cs61a/fa11/lectures/img/tree.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "tree = ((1, 2), 3, 4)\n",
    "tree - (((1, None), (2, None)), (3, None), (4, None))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "You could also use a tree in which the nodes all themselves have data. This is often used to represent a binary tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Tree(1, Tree(2), Tree(3, Tree(4), None))"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Tree:#from cs61a\n",
    "    \n",
    "    def __init__(self, data, left=None, right=None):\n",
    "        self.entry = data\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "    def __repr__(self):\n",
    "        args = repr(self.entry)\n",
    "        if self.left or self.right:\n",
    "            args += ', {0}, {1}'.format(repr(self.left), repr(self.right))\n",
    "        return 'Tree({0})'.format(args)\n",
    "\n",
    "Tree(1,Tree(2), Tree(3, Tree(4)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Once we do iteration in more detail, we'll talk about traversal mechanisms!"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "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
}