Chapter 4 - Linked Lists.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:24a398f5079d2b5ec4ad1b77b913b9629ff6aa4bdfa838b4364f2c52dc809f1a"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.1, PAGE 179"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Composite Classes\n",
      "\n",
      "#Python does not support friend funcitons hence 2 classes one for the node and one for the class are declared.\n",
      "\n",
      "class ThreeLetterNode:\n",
      "    data = None\n",
      "    link = None\n",
      "class ThreeLetterChain:\n",
      "    '''A linked list of 3 letter strings'''\n",
      "    first = None"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.2, PAGE 180"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Nested Classes\n",
      "class ThreeLetterChain:\n",
      "    class ThreeLetterNode:\n",
      "        data = None\n",
      "        link = None\n",
      "    first = None"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.3, PAGE 182"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Creating a two-node list\n",
      "class ChainNode:\n",
      "    def __init__(self, data, link = None):\n",
      "        self.data = data\n",
      "        self.link = link\n",
      "class Chain:\n",
      "    def __init__(self, first):\n",
      "        self.first = first\n",
      "def Create2(self):\n",
      "    #Create and set fields of second node\n",
      "    self.second = ChainNode(20,None)\n",
      "    \n",
      "    #Create and set fields of first node\n",
      "    self.first = ChainNode(10,second)\n",
      "Chain.Create2 = Create2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.4, PAGE 182"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Inserting a Node\n",
      "def Insert50(self,x):\n",
      "    if self.first is not None:\n",
      "        #Insert after x\n",
      "        x.link = ChainNode(50,x.link)\n",
      "    else:\n",
      "        #Insert into empty list\n",
      "        first = ChainNode(50)\n",
      "Chain.Insert50 = Insert50"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.5, PAGE 183"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Deleting a node\n",
      "def Delete(self,x,y):\n",
      "    if x == self.first:\n",
      "        self.first = self.first.link\n",
      "    else:\n",
      "        y.link = x.link\n",
      "Chain.Delete = Delete"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.6, PAGE 186"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Python uses [duck typing](http://en.wikipedia.org/wiki/Duck_typing), so it doesn't need special syntax to handle multiple types.\n",
      "Hence template class for Chains is not possible in Python."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.7, PAGE 187"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Pseudo code for computing maximum element\n",
      "\n",
      "def Max(C):\n",
      "    return max(C)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.8, PAGE 189"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Using an array iterator\n",
      "def main():\n",
      "    x = [0,1,2]\n",
      "    for y in x:\n",
      "        print y,\n",
      "if __name__ == \"__main__\":\n",
      "    main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0 1 2\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.9, PAGE 190"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Code to simulate C++:STL copy function\n",
      "\n",
      "def copy(src, target, start, end, to):\n",
      "    '''Copy form src[start:end] to target[to:(to+end-start)]'''\n",
      "    while start <= end:\n",
      "        target.__setitem__(to,src[start])\n",
      "        #Set item is used for inplace assignment\n",
      "        to += 1\n",
      "        start += 1\n",
      "        \n",
      "#Sample I/O - Not in textbook\n",
      "a = [1,2,3,4,5,6]\n",
      "b = [6,4,0,1,2,3]\n",
      "copy(a,b,2,5,2)\n",
      "#copies a[2:5] to b[2:5]\n",
      "print b"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[6, 4, 3, 4, 5, 6]\n"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.10, PAGE 191"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Forward chain iterator for Chain class\n",
      "class ChainIterator:\n",
      "    def __init__(self, startNode = None):\n",
      "        self.current = startNode\n",
      "    #Python does not support ++ operator hence add method is overloaded.\n",
      "    def __add__(self,value):\n",
      "        if value is int:\n",
      "            for i in range(value):\n",
      "                if self.current == None:\n",
      "                    break\n",
      "                self.current = self.current.link\n",
      "                return self\n",
      "        else:\n",
      "            raise TypeError\n",
      "    def __ne__(self, right):\n",
      "        return self.current != right.current\n",
      "    def __eq__(self, right):\n",
      "        return self.current == right.current\n",
      "    \n",
      "    # This is vaguely equivalent to overloading the . operator\n",
      "    # This basically allows accessing the members / attributes of the self.current from the interator instance itself.\n",
      "    __getattr__ = lambda self : self.current.__getattribute__(key)\n",
      "    \n",
      "    def __getattr__(self, key):\n",
      "        return self.current.__getattr__(key)\n",
      "\n",
      "# Defining ChainIterator as a member object of Chain class\n",
      "Chain.ChainIterator = ChainIterator\n",
      "\n",
      "# Refer Page No 190\n",
      "\n",
      "# Defining begin and end methods of Chain\n",
      "    \n",
      "Chain.begin = lambda self : self.ChainIterator(self.first)\n",
      "Chain.end   = lambda self : self.ChainIterator(None)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.11, PAGE 192"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Inserting at the back of a list\n",
      "\n",
      "def InsertBack(self, e):\n",
      "    if self.first == None :\n",
      "        #If chain is empty\n",
      "        self.first = ChainNode(e)\n",
      "        self.last = self.first\n",
      "    else:\n",
      "        #On non empty chains\n",
      "        self.last.link = ChainNode(e)\n",
      "        self.last = self.last.link\n",
      "        \n",
      "Chain.InsertBack = InsertBack"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 10
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.12, PAGE 192"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Concatenating two chains\n",
      "def Concatenate(b):\n",
      "    '''b is concatenated to the end of self'''\n",
      "    if first != None :\n",
      "        self.last.link = b.first\n",
      "        self.last = b.last\n",
      "    else:\n",
      "        self.first = b.first\n",
      "        self.last = b.last\n",
      "    b.first = None\n",
      "    b.last = None     \n",
      "Chain.Concatenate = Concatenate"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.13, PAGE 193"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Reversing a list\n",
      "def Reverse(self):\n",
      "    ''' A chain is reversed so that [ a[0] , ... , a[n] ] becomes [ a[n] , ... , a[0] ]'''\n",
      "    previous = None\n",
      "    current = self.first\n",
      "    while current is not None:\n",
      "        r = previous\n",
      "        #r is a temp variable which trails the previous\n",
      "        previous = current\n",
      "        current = current.link\n",
      "        previous.link = r\n",
      "    self.first = previous\n",
      "Chain.Reverse = Reverse"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.14, PAGE 196"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class CircularList:\n",
      "    def __init__(self):\n",
      "        self.first = None\n",
      "        self.last = None\n",
      "        self.av = None\n",
      "        #av is the list of deleted Nodes\n",
      "    def InsertFront(self,e):\n",
      "        '''Inserts the element e at the front of the circular list self, where last points to the last node in the list'''\n",
      "        newNode = ChainNode(e)\n",
      "        if last is not None:\n",
      "            newNode.link = self.last.link\n",
      "            self.last.link = newNode\n",
      "        else:\n",
      "            #empty list\n",
      "            self.last = newNode\n",
      "            self.last.link = self.last\n",
      "            #circular referencing"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.15, PAGE 198"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Getting a Node\n",
      "def GetNode(self):\n",
      "    '''Provide a node for use'''\n",
      "    if self.av is not None:\n",
      "        x = self.av\n",
      "        self.av = self.av.link\n",
      "    else:\n",
      "        #if there is no deleted node to x is assigned a new Node\n",
      "        x = ChainNode()\n",
      "    return x\n",
      "CircularList.GetNode = GetNode"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.16, PAGE 198"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Returning a node\n",
      "def RetNode(self,x):\n",
      "    '''Free the node pointed by x'''\n",
      "    x.link = self.av\n",
      "    self.av = x\n",
      "    x = None\n",
      "    #inserts (at the front) the x to the list av, which contains deleted list"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 15
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.17, PAGE 198"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Deleting a Circular list\n",
      "#Python manages out of scope variable by efficient garbage collection methods hence destructors need not be defined in python\n",
      "#Instead a method __del__() is created to simulate the same effect.\n",
      "def __del__(self):\n",
      "    '''Delete the circular list'''\n",
      "    if self.last is not None:\n",
      "        self.first = self.last.link\n",
      "        self.last.link = self.av\n",
      "        self.av = self.first\n",
      "        self.last = None\n",
      "CircularList.__del__ = __del__"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.19, PAGE 200"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Adding a linked stack\n",
      "class LinkedStack:\n",
      "    def __init__(self):\n",
      "        self.top = None\n",
      "    def Push(self,e):\n",
      "        self.top = ChainNode(e,top)\n",
      "    def IsEmpty(self):\n",
      "        return self.top is None       "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 17
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.20, PAGE 201"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Deleting from a Linked Stack\n",
      "def Pop(self):\n",
      "    '''Deleting top node from the stack'''\n",
      "    if (self.IsEmpty()):\n",
      "        raise Exception('Stack is empty. Cannot delete')\n",
      "    delNode = self.top\n",
      "    sel.top = self.top.link\n",
      "    #In python the del operator deletes the name from the name space only\n",
      "    #Automatic garbage collection in python frees the allocated space by itself hence the use of del is not required\n",
      "LinkedStack.Pop = Pop"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 18
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.21, PAGE 201"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Adding to a linked queue\n",
      "class LinkedQueue:\n",
      "    def __init__(self):\n",
      "        self.front = None\n",
      "        self.rear = None\n",
      "    def Push(self,e):\n",
      "        if(self.IsEmpty()):\n",
      "            self.rear = self.front = ChainNode(e,None)\n",
      "        else:\n",
      "            self.rear.link = ChainNode(e,None)\n",
      "    def IsEmpty(self):\n",
      "        if(self.front is None):\n",
      "            return True\n",
      "        else:\n",
      "            return False"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 19
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.22, PAGE 201"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Deleting from a linked queue\n",
      "def _pop(self):\n",
      "    if(self.IsEmpty()):\n",
      "        raise Exception(\"Queue is empty. Cannot delete\")\n",
      "    self.front = self.front.link\n",
      "LinkedQueue.pop = _pop"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 20
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.23, PAGE 203"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Polynomial class definition\n",
      "class Term:\n",
      "    def __init__(self, c = None, e = None):\n",
      "        self.coef = c\n",
      "        self.exp = e\n",
      "        lambda Set : self(c,e)\n",
      "        self.Set = Set\n",
      "\n",
      "class Polynomial:\n",
      "    def __init__(self):\n",
      "        poly = Chain()   # Instantiating a Chain object with an instance of Term as its attribute first."
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 21
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.24, PAGE 206"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Adding two polynomials\n",
      "def _add(self, b):\n",
      "    \"\"\"\n",
      "    Polynomials self (a) and b are added and the sum is returned\n",
      "    \"\"\"\n",
      "    temp = Term()\n",
      "    ai = poly.begin()\n",
      "    bi = b.poly.begin()\n",
      "    c = Polynomial\n",
      "    \n",
      "    while ai is not None and bi is not None:\n",
      "        if ai.exp == bi.exp:\n",
      "            sum_ = ai.coef + bi.coef\n",
      "            if sum_ != 0:\n",
      "                c.poly.InsertBack(temp.Set(sum_,ai.exp))\n",
      "                ai += 1\n",
      "                bi += 1\n",
      "        elif ai.exp < bi.exp:\n",
      "            c.poly.InsertBack(temp.Set(bi.coef, bi.exp))\n",
      "        else:\n",
      "            c.poly.InsertBack(temp.Set(ai.coef, ai.exp))\n",
      "            \n",
      "    while ai != 0:\n",
      "        # Copy rest of a\n",
      "        c.poly.InsertBack(temp.Set(ai.coef, ai.exp))\n",
      "        ai += 1\n",
      "        \n",
      "    while bi != 0:\n",
      "        # Copy rest of b\n",
      "        c.poly.InsertBack(temp.Set(bi.coef, bi.exp))\n",
      "        bi += 1\n",
      "            \n",
      "    return c\n",
      "\n",
      "# Overloading the Polynomial's __add__ method ( overloading the + operator for Polynomial class)\n",
      "Polynomial.__add__ = _add"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 22
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.26, PAGE 212 &nbsp; &amp; &nbsp; PROGRAM 4.27, PAGE 213 &nbsp; &amp; &nbsp; PROGRAM 4.28, PAGE 214"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Function to find equivalence classes\n",
      "class ENode:\n",
      "    def __init__(self, d = 0, link = None):\n",
      "        self.data = d\n",
      "        self.link = link\n",
      "\n",
      "def Equivalence():\n",
      "    \"\"\"\n",
      "    Input equivalence pairs and output the equivalence classes.\n",
      "    \"\"\"\n",
      "    inFileContent = None\n",
      "    try:\n",
      "        with open(\"equiv.in\", \"r\") as inFile:\n",
      "            inFileContent = [ int(i) for i in inFile.read().replace(',',' ').split() ]\n",
      "            # Stores the file contents as an array of type int.\n",
      "    except Exception, e:\n",
      "        print \"Cannot open input file\"\n",
      "        return\n",
      "    \n",
      "    n = inFileContent[0]\n",
      "    first = [ ENode(0) for i in range(n) ]\n",
      "    out = [False]*n\n",
      "\n",
      "    # p is a variable to iterate through the length of the inFileContent\n",
      "    p = 1\n",
      "    \n",
      "    # Phase 1 : Input equivalence pairs\n",
      "    while p < len(inFileContent):\n",
      "        i = inFileContent[p]; j = inFileContent[p+1]\n",
      "        first[i] = ENode(j, first[i])\n",
      "        first[j] = ENode(i, first[j])\n",
      "        p += 2\n",
      "    \n",
      "    #Phase 2 : Output Equivalence classes\n",
      "    for i in range(n):\n",
      "        if not out[i]:\n",
      "            print \"\\nA new class\", i,\n",
      "            out[i] = True\n",
      "            x = first[i]\n",
      "            top = None\n",
      "            while True:  # Find the rest of the class\n",
      "                while x is not None:  # Process the list\n",
      "                    j = x.data\n",
      "                    if not out[j]:\n",
      "                        print \",\", j, \n",
      "                        out[j] = True\n",
      "                        y = x.link\n",
      "                        x.link = top\n",
      "                        top = x\n",
      "                        x = y\n",
      "                    else:\n",
      "                        x = x.link\n",
      "                # End of while loop\n",
      "\n",
      "                if not top:\n",
      "                    break\n",
      "\n",
      "                x = first[top.data]\n",
      "                top = top.link # Unstack\n",
      "\n",
      "            # End of while True\n",
      "\n",
      "        # End of if not out[i]\n",
      "\n",
      "        # In python Garbage Collection is automatic\n",
      "        \n",
      "# Sample Example - Refer Page 211\n",
      "with open('equiv.in','w') as f:\n",
      "    f.write('12 0 4 3 1 6 10 8 9 7 4 6 8 3 5 2 11 11 0')\n",
      "    \n",
      "Equivalence()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "A new class 0 , 11 , 4 , 7 , 2 \n",
        "A new class 1 , 3 , 5 \n",
        "A new class 6 , 8 , 10 , 9\n"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.29, PAGE 219"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Class Definitions for sparse matrix\n",
      "class Triple:\n",
      "    def __init__(self):\n",
      "        self.row   = None\n",
      "        self.col   = None\n",
      "        self.value = None\n",
      "\n",
      "class MatrixNode:\n",
      "    def __init__(self, b, t):\n",
      "        if ( type(b) != bool ):\n",
      "            raise TypeError\n",
      "            return\n",
      "        \n",
      "        self.head = b\n",
      "        \n",
      "        if b:\n",
      "            self.right = self.down = self\n",
      "            self.next_ = None\n",
      "        else:\n",
      "            self.triple = t\n",
      "            \n",
      "       \n",
      "\n",
      "class Matrix:\n",
      "    def __init__(self):\n",
      "        self.headnode = None\n",
      "        self.av = None"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 24
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.30, PAGE 221"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Reading in the Sparse Matrix\n",
      "\n",
      "#Overloading Operator >> for Class Matrix\n",
      "import operator, sys, io, IPython\n",
      "\n",
      "class MyStdIn(object):\n",
      "    def __init__(self):\n",
      "        pass\n",
      "        \n",
      "    def __rshift__(self, matrix):\n",
      "        if isinstance(matrix, Matrix):    \n",
      "            s = Triple()\n",
      "            \n",
      "            # Accept inputs as triplets\n",
      "            # >>> 5 6 7\n",
      "            # >>> 1 2 3 etc ...\n",
      "            \n",
      "            triplet = raw_input().strip().split()\n",
      "                \n",
      "            s.row, s.col, s.value = [ int(i) for i in triplet ]\n",
      "                \n",
      "            p = max(s.row, s.col)\n",
      "            \n",
      "            # Set up header node for list of header Nodes\n",
      "            matrix.headnode = MatrixNode(False, s)\n",
      "            \n",
      "            # If there is no row or column to input\n",
      "            if p == 0:\n",
      "                matrix.headnode.right = matrix.headnode\n",
      "                return\n",
      "            \n",
      "            # If there is atleast one row or column\n",
      "            head = [ MatrixNode(True, None) for i in range(p)]\n",
      "            \n",
      "            currentRow = 0\n",
      "            last = head[0]   # Last node in current row\n",
      "            \n",
      "            for i in range(s.value):\n",
      "                t = Triple()\n",
      "                triplet = raw_input().strip().split()\n",
      "                \n",
      "                t.row, t.col, t.value = [ int(i) for i in triplet ]\n",
      "                if  t.row > currentRow:\n",
      "                    # Close current Row\n",
      "                    last.right = head[currentRow]\n",
      "                    currentRow = t.row\n",
      "                    last = head[currentRow]\n",
      "            \n",
      "                # End of if\n",
      "                last = last.right = MatrixNode(False, t)  # Link new node into row list\n",
      "                head[t.col].next_ = head[t.col].down = last # Link into column list\n",
      "            \n",
      "            # End of for\n",
      "            last.right = head[currentRow]  # Close last row\n",
      "            \n",
      "            for i in range(s.col):\n",
      "                head[i].next_.down = head[i] # Close all column lists\n",
      "                \n",
      "            # Link the header nodes together\n",
      "            for  i in range(p-1):\n",
      "                head[i].next_ = head[i+1]\n",
      "                \n",
      "            head[p-1].next = matrix.headnode\n",
      "            matrix.headnode.right = head[0]\n",
      "            \n",
      "            return\n",
      "        \n",
      "        else:\n",
      "            for k, v in list(globals().iteritems()):\n",
      "                if (id(v) == id(matrix)) and (k != \"matrix\"):\n",
      "                    globals()[k] = raw_input()\n",
      "                    return\n",
      "            \n",
      "#A new MyStdIn Class inheriting the elements of stdin <file class> [InStream Object Class] is created with the \n",
      "#overloaded operator function __rshift__. \n",
      "\n",
      "#Operator >> is specified as a function __rshift__() [Equivalent to c++ style 'operator>>']"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# So to emulate a C++ style cin we can have :\n",
      "\n",
      "print \"Standard input\"\n",
      "cin = MyStdIn()\n",
      "a = 'Text Before' # Otherwise NameError is raised; This is similar to declarations in C++\n",
      "cin>>a\n",
      "print type(a), a"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Standard input\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "New Text\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "<type 'str'> New Text\n"
       ]
      }
     ],
     "prompt_number": 26
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"\\nMatrix Input\"\n",
      "# For a Matrix we have:\n",
      "m = Matrix()\n",
      "# Matrix input is Given as :\n",
      "# NUM_ROW NUM_COL NUM_NON_ZERO_ELEMENTS\n",
      "# ROW COL VALUE\n",
      "# ROW COL VALUE\n",
      "#      .\n",
      "#      .\n",
      "#      .\n",
      "#      .\n",
      "\n",
      "cin>>m  # Refer Page 220 for Input format\n",
      "\n",
      "# Matrix Input\n",
      "# 2 2 2\n",
      "# 1 1 2\n",
      "# 1 0 4\n",
      "\n",
      "print \"\\nFirst Element of the Matrix: \",\n",
      "first_cell = m.headnode.right.down.triple\n",
      "print (first_cell.row, first_cell.col, first_cell.value)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Matrix Input\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2 2 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 1 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 0 4\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "First Element of the Matrix:  (1, 0, 4)\n"
       ]
      }
     ],
     "prompt_number": 27
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.31, PAGE 222"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def _del(self):\n",
      "    # Return all nodes to the av list. This list is a chain linked via the right field.\n",
      "    # av is a static variable that points to the first node of the av list.\n",
      "    if self.headnode is None:\n",
      "        return # No nodes to delete\n",
      "    \n",
      "    x = self.headnode.right\n",
      "    self.headnode.right = self.av\n",
      "    self.av = self.headnode # Return headnode\n",
      "    \n",
      "    while x!=self.headnode:\n",
      "        # Erase by rows\n",
      "        y = x.right\n",
      "        x.right = self.av\n",
      "        self.av = y\n",
      "        x = x.next_ # Next row\n",
      "    \n",
      "    self.headnode = None\n",
      "\n",
      "Matrix.__del__ = _del"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 28
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.32, PAGE 226"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Class definition of a doubly linked list\n",
      "\n",
      "class DblListNode:\n",
      "    def __init__(self):\n",
      "        self.data = None\n",
      "        self.left = self.right = None\n",
      "        \n",
      "class DblList:\n",
      "    def __init__(self):\n",
      "        self.first = DblListNode()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 29
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.33, PAGE 227"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Deleting from a doubly linked circular list\n",
      "def _delete(self, x):\n",
      "    if  x == self.first:\n",
      "        raise(Exception(\"Deletion of header node is not permitted\"))\n",
      "    else:\n",
      "        x.left.right = x.right\n",
      "        x.right.left = x.left\n",
      "        \n",
      "DblList.Delete = _delete"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 30
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.34, PAGE 227"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Insertion into a doubly linked circular list\n",
      "def _insert(self, p, x):\n",
      "    \"\"\" Insert into node p to the right of node x \"\"\"\n",
      "    p.left = x; p.right = x.right\n",
      "    x.right.left = p; x.right = p"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 31
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.35, PAGE 233"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Copying a list\n",
      "# Driver\n",
      "\n",
      "# Class Definition for GenList - Refer Page 231\n",
      "class GenList:\n",
      "    def __init__(self):\n",
      "        self.first = GenListNode()\n",
      "\n",
      "class GenListNode:\n",
      "    def __init__(self):\n",
      "        self.tag = False\n",
      "        self.data = None\n",
      "        self.down = None\n",
      "        \n",
      "        self.ref = 0 # Refer Page 238\n",
      "        self.next_ = None\n",
      "\n",
      "def _copy(self, l):\n",
      "    \"\"\"Make a copy of l\"\"\"\n",
      "    if isinstance(l, GenList):\n",
      "        self.first = self.Copy(l.first)\n",
      "        return None\n",
      "    else:\n",
      "        q = None\n",
      "        if l is not None:\n",
      "            q = GenListNode()\n",
      "            q.tag = p.tag\n",
      "            if p.tag:\n",
      "                q.down = Copy(p.down)\n",
      "            else:\n",
      "                q.data = p.data\n",
      "                \n",
      "            q.next_ = self.Copy(p.next_)\n",
      "        return q\n",
      "    \n",
      "GenList.Copy = _copy"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 32
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.36, PAGE 235"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Determining if two lists are identical\n",
      "\n",
      "def _eq(self, l):\n",
      "    return self.Equal(self, l)\n",
      "\n",
      "def _equal(self, s, l):\n",
      "    if ( s is None ) and ( t is None ):\n",
      "        return True\n",
      "    if ( s and t and ( s.tag == t.tag )):\n",
      "        if s.tag:\n",
      "            return self.Equal(s.down, t.down) and self.Equal(s.next_ and t.next_)\n",
      "        else:\n",
      "            return ( s.data == t.data ) and self.Equal(s.next_, t.next_)\n",
      "    return False\n",
      "\n",
      "GenList.__eq__ = _eq    # Overloading the equality operator.\n",
      "GenList.Equal = _equal"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 33
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.37, PAGE 236"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Driver\n",
      "def _depth(self, s = -1):\n",
      "    if s == -1:   # Pseudo - Function overloading\n",
      "        return Depth(first)\n",
      "    else:\n",
      "        # Workhorse\n",
      "        if s is None:\n",
      "            return None\n",
      "        \n",
      "        current = s\n",
      "        m = 0\n",
      "        \n",
      "        while current is not None:\n",
      "            if current.tag:\n",
      "                m = max(m, Depth(current.down))\n",
      "                current = current.next_\n",
      "                \n",
      "        return m+1\n",
      "GenList.Depth = _depth"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 35
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "PROGRAM 4.38, PAGE 239"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Deleting a list recursively\n",
      "# Driver\n",
      "\n",
      "def _del(self, *inputs):\n",
      "    \n",
      "    if len(inputs == 0):\n",
      "        if first is None:\n",
      "            self.Delete(first)\n",
      "            first = None\n",
      "            return\n",
      "    \n",
      "    x = inputs[0]  # Pseudo Function Overloading\n",
      "    \n",
      "    x.ref  -= x.ref\n",
      "    if x.ref != 0:\n",
      "        y = x\n",
      "        while y.next_ is not None:\n",
      "            y = y.next_\n",
      "            if y.tag == 1:\n",
      "                self.Delete(y.down)\n",
      "        y.next_ = self.av # Attach top level node to av list\n",
      "        self.av = x"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 36
    }
   ],
   "metadata": {}
  }
 ]
}