hw10.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HW10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import uuid\n",
    "class BinaryTree:\n",
    "    def __init__(self, data, parent=None):\n",
    "        self.data = data\n",
    "        self.parent = parent\n",
    "        self.uuid= uuid.uuid4()\n",
    "        self.left = None\n",
    "        self.right = None    \n",
    "            \n",
    "    def addLeftChild(self, data): \n",
    "        n = self.__class__(data, self)\n",
    "        self.left = n\n",
    "        return n\n",
    "        \n",
    "    def addRightChild(self, data):\n",
    "        n = self.__class__(data, self)\n",
    "        self.right = n\n",
    "        return n\n",
    "        \n",
    "    def hasLeftChild(self):\n",
    "        return self.left is not None\n",
    "\n",
    "    def hasRightChild(self):\n",
    "        return self.right is not None\n",
    "\n",
    "    def hasAnyChild(self):\n",
    "        return self.hasRightChild() or self.hasLeftChild()\n",
    "\n",
    "    def hasBothChildren(self):\n",
    "        return self.hasRightChild() and self.hasLeftChild()\n",
    "    \n",
    "    def hasNoChildren(self):\n",
    "        return not self.hasRightChild() and not self.hasLeftChild()\n",
    "    \n",
    "    def isLeftChild(self):\n",
    "        return self.parent and self.parent.left == self\n",
    "\n",
    "    def isRightChild(self):\n",
    "        return self.parent and self.parent.right == self\n",
    "\n",
    "    def isRoot(self):\n",
    "        return not self.parent\n",
    "\n",
    "    def isLeaf(self):\n",
    "        return not (self.right or self.left)\n",
    "    \n",
    "            \n",
    "    def preorder(self):\n",
    "        if self.isLeftChild():\n",
    "            yield (self.parent, self, \"left\")\n",
    "        elif self.isRightChild():\n",
    "            yield (self.parent, self, \"right\")\n",
    "        if self.hasLeftChild():\n",
    "            for v in self.left.preorder():\n",
    "                yield v\n",
    "        if self.hasRightChild():\n",
    "            for v in self.right.preorder():\n",
    "                yield v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class BinarySearchTree(BinaryTree):\n",
    "        \n",
    "    def __init__(self, data, parent=None):\n",
    "        super().__init__(data, parent)\n",
    "        self.count = 1\n",
    "\n",
    "    def _insert_hook(self):\n",
    "        pass\n",
    "            \n",
    "    def insert(self, data):\n",
    "        if data < self.data:\n",
    "            if self.hasLeftChild():\n",
    "                self.left.insert(data)\n",
    "            else:\n",
    "                self.addLeftChild(data)\n",
    "                self._insert_hook()\n",
    "        elif data > self.data:\n",
    "            if self.hasRightChild():\n",
    "                self.right.insert(data)\n",
    "            else:\n",
    "                self.addRightChild(data)\n",
    "                self._insert_hook()\n",
    "        else: #duplicate value\n",
    "            self.count += 1\n",
    "            self._insert_hook()\n",
    "            \n",
    "    def search(self, data):\n",
    "        if self.data == data:\n",
    "            return self\n",
    "        elif data < self.data and self.left:\n",
    "            return self.left.search(data)\n",
    "        elif data > self.data and self.right:\n",
    "            return self.right.search(data)\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "    def delete(self, data):        \n",
    "        if self.isRoot() and self.hasNoChildren() and self.data==data:#deleting the whole tree\n",
    "            self.root=None#todo call a destructor that signals GC it can reap\n",
    "            #self._update_sizes(up=False) #really tree is gone\n",
    "            self._remove_hook()\n",
    "        elif self.hasAnyChild():\n",
    "            noder = self.search(data)\n",
    "            if noder:\n",
    "                self._remove(noder)\n",
    "            else:\n",
    "                raise ValueError(\"No such data {} in tree\".format(data))\n",
    "        else:\n",
    "            raise ValueError(\"No such data {} in tree\".format(data))\n",
    "\n",
    "    def _remove_hook(self, up=False, by=1):\n",
    "        pass\n",
    "    \n",
    "    def _remove(self, node):\n",
    "        if node.isLeaf():\n",
    "            if node.isLeftChild():\n",
    "                node.parent.left = None\n",
    "            else:\n",
    "                node.parent.right = None\n",
    "            #node._update_sizes(up=False, by=node.count)\n",
    "            node._remove_hook(by=node.count)\n",
    "            del node\n",
    "        elif node.hasBothChildren():\n",
    "            s = node.successor()\n",
    "            #successor is guaranteed to have right child only\n",
    "            s.spliceOut()\n",
    "            #s._update_sizes(up=False, by=s.count)\n",
    "            s._remove_hook(by=s.count)\n",
    "            #handled more generally above\n",
    "            #s.right.parent = s.parent\n",
    "            #s.parent.left = s.right\n",
    "            node.data = s.data\n",
    "            #diff = s.count - node.count            \n",
    "            #node._update_sizes(by=diff)\n",
    "            node._remove_hook(up=True, by = s.count - node.count)\n",
    "            node.count = s.count\n",
    "            del s #the node became the successor\n",
    "        else: # one child case\n",
    "            if node.hasLeftChild():\n",
    "                if node.isLeftChild():\n",
    "                    node.left.parent = node.parent\n",
    "                    node.parent.left = node.left\n",
    "                elif node.isRightChild():\n",
    "                    node.left.parent = node.parent\n",
    "                    node.parent.right = node.left\n",
    "                else: #root\n",
    "                    self.root = node.left\n",
    "                #node._update_sizes(up=False, by=node.count)\n",
    "                node._remove_hook(by=node.count)\n",
    "                del node\n",
    "            else:\n",
    "                if node.isLeftChild():\n",
    "                    node.right.parent = node.parent\n",
    "                    node.parent.left = node.right\n",
    "                elif node.isRightChild():\n",
    "                    node.right.parent = node.parent\n",
    "                    node.parent.right = node.right\n",
    "                else: #root\n",
    "                    self.root = node.right\n",
    "                #node._update_sizes(up=False, by=node.count)\n",
    "                node._remove_hook(by=node.count)\n",
    "                del node\n",
    "                    \n",
    "    def findMin(self):\n",
    "        minnode = self\n",
    "        while minnode.hasLeftChild():\n",
    "            minnode = minnode.left\n",
    "        return minnode\n",
    "    \n",
    "    def findMax(self):\n",
    "        maxnode = self\n",
    "        while maxnode.hasRightChild():\n",
    "            maxnode = maxnode.right\n",
    "        return maxnode\n",
    "    \n",
    "    def successor(self):\n",
    "        s = None\n",
    "        if self.hasRightChild():\n",
    "            s = self.right.findMin()\n",
    "        else:\n",
    "            if self.parent:\n",
    "                if self.isLeftChild():\n",
    "                    s = self.parent\n",
    "                else:\n",
    "                    self.parent.right=None\n",
    "                    s = self.parent.successor()\n",
    "                    self.parent.right=self\n",
    "        return s\n",
    "    \n",
    "    def predecessor(self):\n",
    "        p=None\n",
    "        if self.hasLeftChild():\n",
    "            p = self.left.findMax()\n",
    "        else:\n",
    "            if self.parent:\n",
    "                if self.isRightChild():\n",
    "                    p = self.parent\n",
    "                else:\n",
    "                    self.parent.left = None\n",
    "                    p = self.parent.predecessor()\n",
    "                    self.parent.left = self\n",
    "        return p\n",
    "            \n",
    "    def spliceOut(self):\n",
    "        if self.isLeaf():\n",
    "            if self.isLeftChild():\n",
    "                self.parent.left = None\n",
    "            else:\n",
    "                self.parent.right = None\n",
    "        elif self.hasAnyChild():\n",
    "            if self.hasLeftChild():\n",
    "                if self.isLeftChild():\n",
    "                    self.parent.left = self.left\n",
    "                else:\n",
    "                    self.parent.right = self.left\n",
    "                self.left.parent = self.parent\n",
    "            else:\n",
    "                if self.isLeftChild():\n",
    "                    self.parent.left = self.right\n",
    "                else:\n",
    "                    self.parent.right = self.right\n",
    "                self.right.parent = self.parent\n",
    "       \n",
    "\n",
    "    #now implement various pythonic things\n",
    "    \n",
    "    def __iter__(self):\n",
    "        if self is not None:\n",
    "            if self.hasLeftChild():\n",
    "                for node in self.left:\n",
    "                    yield node\n",
    "            for _ in range(self.count):\n",
    "                yield self\n",
    "            if self.hasRightChild():\n",
    "                for node in self.right:\n",
    "                    yield node\n",
    "                    \n",
    "    def __len__(self):#expensive O(n) version\n",
    "        start=0\n",
    "        for node in self:\n",
    "            start += 1\n",
    "        return start\n",
    "    \n",
    "    def __getitem__(self, i):\n",
    "        return self.ithorder(i+1)\n",
    "    \n",
    "    def __contains__(self, data):\n",
    "        return self.search(data) is not None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class AugmentedBinarySearchTree(BinarySearchTree):\n",
    "        \n",
    "    def __init__(self, data, parent=None):\n",
    "        super().__init__(data, parent)\n",
    "        self.size = 1\n",
    "        \n",
    "    def _update_sizes(self, up=True, by=1):\n",
    "        if up:\n",
    "            inc = by\n",
    "        else:\n",
    "            inc = -by\n",
    "        self.size += inc\n",
    "        curr = self\n",
    "        while curr.parent is not None:\n",
    "            curr.parent.size += inc\n",
    "            curr = curr.parent\n",
    "       \n",
    "    def _insert_hook(self):#insert up, by 1\n",
    "        self._update_sizes()\n",
    "            \n",
    "    def _remove_hook(self, up=False, by=1):\n",
    "        self._update_sizes(up, by)\n",
    "        \n",
    "    \n",
    "    def ithorder(self, i): #starts from 1\n",
    "        if self.hasLeftChild():\n",
    "            a = self.left.size\n",
    "        else:\n",
    "            a = 0\n",
    "        dupes = self.count - 1\n",
    "        if  a+1 <= i  < a+1 + dupes:\n",
    "            return self\n",
    "        if i < a + 1 : #wont go here for size 0 on left\n",
    "            return self.left.ithorder(i)\n",
    "        elif  a+1 <= i  <= a+1 + dupes:\n",
    "            return self\n",
    "        else:#ok to have self.right here and not check right child\n",
    "            return self.right.ithorder(i - a -1 -dupes)\n",
    "       \n",
    "    def _rankof(self, data):\n",
    "        if self.data == data:#found at top\n",
    "            if self.hasLeftChild():\n",
    "                return self.left.size + self.count, self.count\n",
    "            else:\n",
    "                return self.count, self.count\n",
    "        elif data < self.data and self.left:\n",
    "            return self.left._rankof(data)\n",
    "        elif data > self.data and self.right:\n",
    "            rtup = self.right._rankof(data)\n",
    "            if self.hasLeftChild():\n",
    "                return self.count + self.left.size+rtup[0], rtup[1]\n",
    "            else:\n",
    "                return self.count + rtup[0], rtup[1]\n",
    "        else:\n",
    "            raise ValueError(\"{} not found\".format(x))\n",
    "            \n",
    "    def rankof(self, data):\n",
    "        ranktup = self._rankof(data)\n",
    "        return [ranktup[0] - e for e in range(ranktup[1])]\n",
    "    \n",
    "    \n",
    "    #now implement various pythonic things\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    \n",
    "    def __getitem__(self, i):\n",
    "        return self.ithorder(i+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q1.\n",
    "\n",
    "Implement a Key-Value Search true, which allows no duplicates, but rather, updates the value associated with the key. This will change how `insert` works. Inherit from the augmented tree:\n",
    "\n",
    "`class KeyValueBinarySearchTree(AugmentedBinarySearchTree):`\n",
    "\n",
    "- The constructor should look like this: `def __init__(self, key_value_tuple, parent=None):`. Pick the key and value out separately in the constructor, and initialize the super with just the key, setting an instance variable `self.value` to the value.\n",
    "- insert wont duplicate any more, and `addLeftChild` and `addRightChild` will need to take the tuple in as they call the constructor for us.\n",
    "- implement a `__getitem__`, `__setitem__`, and `__delitem__` so that you can use code like:\n",
    "\n",
    "`btreekv['f']` for searching\n",
    "\n",
    "`btreekv['f']=10` for inserting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class KeyValueBinarySearchTree(AugmentedBinarySearchTree):\n",
    "    \"\"\"\n",
    "    Creates a KeyValueBinarySearchTree instance\n",
    "\n",
    "    EXAMPLES\n",
    "    -------\n",
    "    >>> bt = KeyValueBinarySearchTree(('c', 3))\n",
    "    >>> bt['a'] = 2\n",
    "    >>> bt['c']\n",
    "    3\n",
    "    >>> bt['a']\n",
    "    2\n",
    "    >>> bt['c'] = 10\n",
    "    >>> bt['c']\n",
    "    10\n",
    "    >>> del bt['c']\n",
    "    >>> bt['c'] == None\n",
    "    True\n",
    "    \"\"\"\n",
    "    def __init__(self,key_val,parent = None):\n",
    "        key, val = key_val\n",
    "        super().__init__(key,parent)\n",
    "        self.value = val\n",
    "        \n",
    "    def insert(self,key_val):\n",
    "        key,val = key_val\n",
    "        if key > self.data:\n",
    "            if self.hasRightChild():\n",
    "                self.right.insert(key_val)\n",
    "            else:\n",
    "                self.addRightChild(key_val)\n",
    "                self._insert_hook()\n",
    "            \n",
    "        elif key < self.data:\n",
    "            if self.hasLeftChild():\n",
    "                self.left.insert(key_val)\n",
    "            else:\n",
    "                self.addLeftChild(key_val)\n",
    "                self._insert_hook()\n",
    "            \n",
    "        else: \n",
    "            self.value = val\n",
    "            self._insert_hook()\n",
    "        \n",
    "    def __getitem__(self,key):\n",
    "        \"\"\"Return the value associated with given key\n",
    "        Returns None if the key,val pair doesn't exist\n",
    "        \"\"\"\n",
    "        return self.search(key).value\n",
    "    \n",
    "    def __setitem__(self,key,value):\n",
    "        \"\"\"\n",
    "        Sets the value for the given key\n",
    "        \"\"\"\n",
    "        self.insert((key,value))\n",
    "    \n",
    "    def __delitem__(self, data):\n",
    "        \"\"\"Delete the (key,val) pair where key = data\n",
    "        \"\"\"\n",
    "        if self.isRoot() and self.hasNoChildren() and self.data==data:\n",
    "            self.root = None\n",
    "            self._remove_hook()\n",
    "        elif self.hasAnyChild():\n",
    "            noder = self.search(data)\n",
    "            if noder:\n",
    "                self.__delitem__(noder)\n",
    "            else:\n",
    "                raise ValueError(\"No such data {} in tree\".format(data))\n",
    "        else:\n",
    "            raise ValueError(\"No such data {} in tree\".format(data))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It should all make sense...."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "btreekv = KeyValueBinarySearchTree(('f', 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "kvdata=zip(list('jeihrifhkdfks'), range(13))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for k,v in kvdata:\n",
    "    btreekv[k]=v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('d', 9),\n",
       " ('e', 1),\n",
       " ('f', 10),\n",
       " ('h', 7),\n",
       " ('i', 5),\n",
       " ('j', 0),\n",
       " ('k', 11),\n",
       " ('r', 4),\n",
       " ('s', 12)]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[(e.data, e.value) for e in list(btreekv)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "btreekv['f']"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [py35]",
   "language": "python",
   "name": "Python [py35]"
  },
  "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
}