{
 "metadata": {
  "name": "",
  "signature": "sha256:8fd742e3911255005d5cc80d3e792a10aed91d6e12fc125e66cc3c416b974be7"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Chapter 10 : 2-3-4 Trees and External Storage"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Example 10.1  Page No : 478"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " \n",
      "class DataItem:\n",
      "    def __init__(self,dd):\n",
      "        self.dData = dd\n",
      "\n",
      "    def displayItem(self):\n",
      "        print '/' ,self.dData\n",
      "\n",
      "class Node:\n",
      "    def __init__(self):\n",
      "        self.ORDER = 4\n",
      "        self.numItems = 0\n",
      "        self.parent = None\n",
      "        self.childArray = [None,None,None,None]\n",
      "        self.itemArray = [None,None,None]\n",
      "\n",
      "    def connectChild(self,childNum,child):\n",
      "        self.childArray[childNum] = child\n",
      "        if(child != None):\n",
      "            child.parent = self\n",
      "\n",
      "    def disconnectChild(self,childNum):\n",
      "        tempNode = self.childArray[childNum]\n",
      "        self.childArray[childNum] = None\n",
      "        return tempNode\n",
      "\n",
      "    def getChild(self,childNum):\n",
      "        return self.childArray[childNum]\n",
      "\n",
      "    def getParent(self):\n",
      "        return self.parent\n",
      "\n",
      "    def isLeaf(self):\n",
      "        if self.childArray[0]==None:\n",
      "            return True \n",
      "        return False    \n",
      "\n",
      "    def getNumItems(self):\n",
      "        return self.numItems\n",
      "\n",
      "    def getItem(self,index):         # get DataItem at index\n",
      "        return self.itemArray[index] \n",
      "\n",
      "    def isFull(self):\n",
      "        if self.numItems==self.ORDER-1:\n",
      "            return True\n",
      "        return False\n",
      "\n",
      "    def findItem(self,key): # return index of # item (within node)\n",
      "        for j in range(self.ORDER-1): \n",
      "            if(self.itemArray[j] == None):\n",
      "                break\n",
      "            elif(self.itemArray[j].dData == key):\n",
      "                return j\n",
      "        return -1\n",
      "\n",
      "    def insertItem(self,newItem):\n",
      "        #assumes node is not full\n",
      "        self.numItems += 1 # will add new item\n",
      "        newKey = newItem.dData # key of new item\n",
      "        j = self.ORDER - 2\n",
      "        while j>=0:\n",
      "            if(self.itemArray[j] == None):\n",
      "                continue\n",
      "            else:\n",
      "                itsKey = self.itemArray[j].dData\n",
      "                if(newKey < itsKey):\n",
      "                    self.itemArray[j+1] = self.itemArray[j]\n",
      "                else:\n",
      "                    self.itemArray[j+1] = newItem\n",
      "                    return j+1 # return index to\n",
      "            j -= 1\n",
      "\n",
      "        self.itemArray[0] = newItem # insert new item\n",
      "        return 0\n",
      "\n",
      "    def removeItem(self): # remove largest item\n",
      "        temp = self.itemArray[self.numItems-1] # save item\n",
      "        self.itemArray[self.numItems-1] = None # disconnect it\n",
      "        self.numItems -= 1 # one less item\n",
      "        return temp # return item\n",
      "\n",
      "    def displayNode(self):\n",
      "        for j in range(self.numItems):\n",
      "            self.itemArray[j].displayItem()\n",
      "        print ''\n",
      "\n",
      "class Tree234:\n",
      "    def __init__(self):\n",
      "        self.root = Node() # make root node\n",
      "\n",
      "    def find(self,key):\n",
      "        curNode = self.root\n",
      "        childNumber = 0\n",
      "        while(True):\n",
      "            childNumber=curNode.findItem(key) \n",
      "            if(childNumber != -1):\n",
      "                return childNumber # found it\n",
      "            elif( curNode.isLeaf() ):\n",
      "                return -1 # cant find it\n",
      "            else: # search deeper\n",
      "                curNode = getNextChild(curNode, key)\n",
      "\n",
      "    def insert(self,dValue):\n",
      "        curNode = self.root\n",
      "        tempItem = DataItem(dValue)\n",
      "        while(True):\n",
      "            if( curNode.isFull() ):\n",
      "                split(curNode)\n",
      "                curNode = curNode.getParent()\n",
      "                curNode = getNextChild(curNode, dValue)\n",
      "            elif( curNode.isLeaf() ): # if node is leaf,\n",
      "                break\n",
      "            else:\n",
      "                curNode = getNextChild(curNode, dValue)\n",
      "        curNode.insertItem(tempItem)\n",
      "\n",
      "    def split(self,thisNode): # split the node\n",
      "        # assumes node is full\n",
      "        itemC = thisNode.removeItem()         # remove items from\n",
      "        itemB = thisNode.removeItem()         # this node\n",
      "        child2 = thisNode.disconnectChild(2) # remove children\n",
      "        child3 = thisNode.disconnectChild(3) # from this nodeJava Code for a 2-3-4 Tree\n",
      "        newRight = Node() # make new node\n",
      "        if(thisNode==self.root):\n",
      "            self.root = Node()\n",
      "            parent = self.root\n",
      "            self.root.connectChild(0, thisNode)\n",
      "        else:\n",
      "            parent = thisNode.getParent()\n",
      "        itemIndex = parent.insertItem(itemB) # item B to parent\n",
      "        n = parent.getNumItems()\n",
      "        j = n-1\n",
      "        while j > itemIndex:\n",
      "            temp = parent.disconnectChild(j) # one child\n",
      "            parent.connectChild(j+1, temp)\n",
      "            j -= 1\n",
      "\n",
      "        parent.connectChild(itemIndex+1, newRight) # deal with newRight\n",
      "        newRight.insertItem(itemC) # item C to newRight\n",
      "        newRight.connectChild(0, child2) # connect to 0 and 1\n",
      "        newRight.connectChild(1, child3) # on newRight\n",
      "\n",
      "    def getNextChild(self,theNode,theValue):\n",
      "        # assumes node is not empty, not full, not a leaf\n",
      "        numItems = theNode.getNumItems()        \n",
      "        for j in range(numItems): # for each item in node\n",
      "            if( theValue < theNode.getItem(j).dData ):\n",
      "                return theNode.getChild(j) # return left child\n",
      "        return theNode.getChild(j)\n",
      "\n",
      "    def displayTree(self):\n",
      "        self.recDisplayTree(self.root, 0, 0)\n",
      "\n",
      "    def recDisplayTree(self,thisNode,level, childNumber):\n",
      "        print 'level=' ,level ,' child=',childNumber , ' '\n",
      "        thisNode.displayNode()\n",
      "        numItems = thisNode.getNumItems()\n",
      "        for j in range(numItems+1):\n",
      "            nextNode = thisNode.getChild(j)\n",
      "            if(nextNode != None):\n",
      "                self.recDisplayTree(nextNode, level+1, j)\n",
      "            else:\n",
      "                return\n",
      "theTree = Tree234()\n",
      "theTree.insert(50)\n",
      "theTree.insert(40)\n",
      "theTree.insert(60)\n",
      "theTree.insert(30)\n",
      "theTree.insert(70)\n",
      "while(True):\n",
      "    print 'Enter first letter of show, '\n",
      "    print 'insert, find, or display: ',\n",
      "    choice = raw_input()\n",
      "    if choice == 's':\n",
      "        theTree.displayTree()\n",
      "    elif choice == 'i':\n",
      "        print 'Enter value to insert: '\n",
      "        value = int(raw_input())\n",
      "        theTree.insert(value)\n",
      "    elif choice == 'f':\n",
      "        print 'Enter value to find: ',\n",
      "        value = int(raw_input())\n",
      "        found = theTree.find(value)\n",
      "        if(found != -1):\n",
      "            print 'Found: ', value\n",
      "        else:\n",
      "            print 'Could not find', value \n",
      "    else:\n",
      "        print 'Invalid entry'\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}