array-list.ipynb

balanced-bsts-demo.ipynb

binary-search-trees.ipynb

bst-ds-demo.ipynb

hashtable-demo.ipynb

iterators-demo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementing Iteration\n",
    "\n",
    "## Agenda\n",
    "\n",
    "1. Review: Iteration\n",
    "2. Details: *iterables*, *iterators*, `iter`, and `next`\n",
    "3. Implementing iterators with classes\n",
    "4. Implementing iterators with *generators* and `yield`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Review: Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Iteration* simply refers to the process of accessing — one by one — the items stored in some container. The order of the items, and whether or not the iteration is comprehensive, depends on the container.\n",
    "\n",
    "In Python, we typically perform iteration using the `for` loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# e.g., iterating over a list\n",
    "l = [2**x for x in range(10)]\n",
    "for n in l:\n",
    "    print(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# e.g., iterating over the key-value pairs in a dictionary\n",
    "d = {x:2**x for x in range(10)}\n",
    "for k,v in d.items():\n",
    "    print(k, '=>', v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Details: *iterables*, *iterators*, `iter`, and `next`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can iterate over anything that is *iterable*. Intuitively, if something can be used as the source of items in a `for` loop, it is iterable.\n",
    "\n",
    "But how does a `for` loop really work? (Review time!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l = [2**x for x in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Implementing iterators with classes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class MyIterator:\n",
    "    def __init__(self, max):\n",
    "        self.max = max\n",
    "        self.curr = 0\n",
    "        \n",
    "    # the following methods are required for iterator objects\n",
    "    \n",
    "    def __next__(self):\n",
    "        pass\n",
    "    \n",
    "    def __iter__(self):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "it = MyIterator(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "next(it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "it = MyIterator(10)\n",
    "while True:\n",
    "    try:\n",
    "        print(next(it))\n",
    "    except StopIteration:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "it = MyIterator(10)\n",
    "for i in it:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a container type, we need to implement an `__iter__` method that returns an iterator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class ArrayList:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        \n",
    "    def append(self, val):\n",
    "        self.data.append(None)\n",
    "        self.data[len(self.data)-1] = val\n",
    "        \n",
    "    def __iter__(self):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l = ArrayList()\n",
    "for x in range(10):\n",
    "    l.append(2**x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "it = iter(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "type(it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "next(it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for x in l:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Implementing iterators with generators and `yield`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What's a \"generator\"?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}

lang-intro-part1.ipynb

lang-intro-part2.ipynb

lang-intro-part3.ipynb

linked-list-demo.ipynb

linked-structures-demo.ipynb

on-recursion-demo.ipynb

priority-queues-demo.ipynb

searching-sorting-timing.ipynb

stacks-and-queues-demo.ipynb