{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Copyright 2014 Brett Slatkin, Pearson Education Inc.\n",
    "#\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "\n",
    "# Preamble to mimick book environment\n",
    "import logging\n",
    "from pprint import pprint\n",
    "from sys import stdout as STDOUT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 1\n",
    "class FrequencyList(list):\n",
    "    def __init__(self, members):\n",
    "        super().__init__(members)\n",
    "\n",
    "    def frequency(self):\n",
    "        counts = {}\n",
    "        for item in self:\n",
    "            counts.setdefault(item, 0)\n",
    "            counts[item] += 1\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length is 7\n",
      "After pop: ['a', 'b', 'a', 'c', 'b', 'a']\n",
      "Frequency: {'c': 1, 'a': 3, 'b': 2}\n"
     ]
    }
   ],
   "source": [
    "# Example 2\n",
    "foo = FrequencyList(['a', 'b', 'a', 'c', 'b', 'a', 'd'])\n",
    "print('Length is', len(foo))\n",
    "foo.pop()\n",
    "print('After pop:', repr(foo))\n",
    "print('Frequency:', foo.frequency())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 3\n",
    "class BinaryNode(object):\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example 4\n",
    "bar = [1, 2, 3]\n",
    "bar[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example 5\n",
    "bar.__getitem__(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 6\n",
    "class IndexableNode(BinaryNode):\n",
    "    def _search(self, count, index):\n",
    "        found = None\n",
    "        if self.left:\n",
    "            found, count = self.left._search(count, index)\n",
    "        if not found and count == index:\n",
    "            found = self\n",
    "        else:\n",
    "            count += 1\n",
    "        if not found and self.right:\n",
    "            found, count = self.right._search(count, index)\n",
    "        return found, count\n",
    "        # Returns (found, count)\n",
    "\n",
    "    def __getitem__(self, index):\n",
    "        found, _ = self._search(0, index)\n",
    "        if not found:\n",
    "            raise IndexError('Index out of range')\n",
    "        return found.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 7\n",
    "tree = IndexableNode(\n",
    "    10,\n",
    "    left=IndexableNode(\n",
    "        5,\n",
    "        left=IndexableNode(2),\n",
    "        right=IndexableNode(\n",
    "            6, right=IndexableNode(7))),\n",
    "    right=IndexableNode(\n",
    "        15, left=IndexableNode(11)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LRR = 7\n",
      "Index 0 = 2\n",
      "Index 1 = 5\n",
      "11 in the tree? True\n",
      "17 in the tree? False\n",
      "Tree is [2, 5, 6, 7, 10, 11, 15]\n"
     ]
    }
   ],
   "source": [
    "# Example 8\n",
    "print('LRR =', tree.left.right.right.value)\n",
    "print('Index 0 =', tree[0])\n",
    "print('Index 1 =', tree[1])\n",
    "print('11 in the tree?', 11 in tree)\n",
    "print('17 in the tree?', 17 in tree)\n",
    "print('Tree is', list(tree))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 9\n",
    "try:\n",
    "    len(tree)\n",
    "except:\n",
    "    logging.exception('Expected')\n",
    "else:\n",
    "    assert False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 10\n",
    "class SequenceNode(IndexableNode):\n",
    "    def __len__(self):\n",
    "        _, count = self._search(0, None)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree has 7 nodes\n"
     ]
    }
   ],
   "source": [
    "# Example 11\n",
    "tree = SequenceNode(\n",
    "    10,\n",
    "    left=SequenceNode(\n",
    "        5,\n",
    "        left=SequenceNode(2),\n",
    "        right=SequenceNode(\n",
    "            6, right=SequenceNode(7))),\n",
    "    right=SequenceNode(\n",
    "        15, left=SequenceNode(11))\n",
    ")\n",
    "\n",
    "print('Tree has %d nodes' % len(tree))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 12\n",
    "try:\n",
    "    from collections.abc import Sequence\n",
    "    \n",
    "    class BadType(Sequence):\n",
    "        pass\n",
    "    \n",
    "    foo = BadType()\n",
    "except:\n",
    "    logging.exception('Expected')\n",
    "else:\n",
    "    assert False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index of 7 is 3\n",
      "Count of 10 is 1\n"
     ]
    }
   ],
   "source": [
    "# Example 13\n",
    "class BetterNode(SequenceNode, Sequence):\n",
    "    pass\n",
    "\n",
    "tree = BetterNode(\n",
    "    10,\n",
    "    left=BetterNode(\n",
    "        5,\n",
    "        left=BetterNode(2),\n",
    "        right=BetterNode(\n",
    "            6, right=BetterNode(7))),\n",
    "    right=BetterNode(\n",
    "        15, left=BetterNode(11))\n",
    ")\n",
    "\n",
    "print('Index of 7 is', tree.index(7))\n",
    "print('Count of 10 is', tree.count(10))"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}