DSAP_Lab.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DSAP-Lab.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lpw8EB0WPEdL",
        "colab_type": "text"
      },
      "source": [
        "**Disclaimer**: \n",
        "These codes have been taken from the following book:\n",
        "\n",
        "__Data Structures and Algorithms in Python__ by Michael T. Goodrich, Roberto T Tamassia and Michael H. Goldwasser Published by Wiley. \n",
        "\n",
        "The codes are being made available for education purposes and no originality is being claimed here. \n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QPYCA-hRUXoR",
        "colab_type": "text"
      },
      "source": [
        "# Chapter 1: Introduction to Python Program\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LElbUtpK8jOc",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "## Basic sequence types classes\n",
        "\n",
        "\n",
        "* list\n",
        "* tuple\n",
        "* set\n",
        "* str\n",
        "* dict\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0-gkVKZo8s9V",
        "colab_type": "text"
      },
      "source": [
        "### lists\n",
        "\n",
        "- mutable sequence of objects\n",
        "- elements can be added, removed or inserted.\n",
        "- [] is used for creating a list. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qxfaWlO_Ktty",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Lists are mutable - elements can be added or removed\n",
        "a = [2,3,4,5]\n",
        "a.append(6)\n",
        "print(a)\n",
        "a.remove(3)\n",
        "print(a)\n",
        "a.insert(1,10)\n",
        "print(a)\n",
        "\n",
        "b = []\n",
        "print(type(b))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kbVhYQHkiA2v",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "47c4a17a-5f21-4fc4-e76a-230b68b5271d"
      },
      "source": [
        "# Lists\n",
        "d = list('hello')\n",
        "print(d)\n",
        "a = ['red', 'green', 'blue']\n",
        "print(a)\n",
        "b = [10,12,15]\n",
        "c = [a,b]\n",
        "print(c)\n",
        "g = [\"Tom\", 32, 5, \"london\"]\n",
        "print(g)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "['h', 'e', 'l', 'l', 'o']\n",
            "['red', 'green', 'blue']\n",
            "[['red', 'green', 'blue'], [10, 12, 15]]\n",
            "['Tom', 32, 5, 'london']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F9qn4o4p87nj",
        "colab_type": "text"
      },
      "source": [
        "### Tuples\n",
        "- immutable sequence of objects\n",
        "- elements can be inserted or removed.\n",
        "- it need to be converted into a list before adding or removing elements. \n",
        "- () creates empty tuple"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Aco0qV9xSuyA",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 83
        },
        "outputId": "3ac42661-00ef-4bf0-fe35-c10cb2307581"
      },
      "source": [
        "# Tuple are immutable - they can not be changed.\n",
        "a = (2,3,4,5)\n",
        "#a.append(5) # Gives error\n",
        "print(a) \n",
        "\n",
        "b = list(a)\n",
        "b.append(5)\n",
        "c = tuple(b)\n",
        "print(c)\n",
        "\n",
        "d = ()\n",
        "print(type(d))\n",
        "\n",
        "g = {5,6}\n",
        "print(type(g))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(2, 3, 4, 5)\n",
            "(2, 3, 4, 5, 5)\n",
            "<class 'tuple'>\n",
            "<class 'set'>\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ca1Mk7MHczqA",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 33
        },
        "outputId": "e8257456-8717-445e-ee17-ba3d79d0554f"
      },
      "source": [
        "number = 5.0\n",
        "try:\n",
        "    r = 10/number\n",
        "    print(r)\n",
        "except:\n",
        "    print(\"Oops! Error occurred.\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cTFyIDpCk0u9",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 107
        },
        "outputId": "accbe728-fa27-4ee2-d256-113d0eeefc15"
      },
      "source": [
        "# Tuples\n",
        "tup1 = ('physics', 'chemistry', 1997, 2000)\n",
        "tup2 = (1, 2, 3, 4, 5, 6, 7 )\n",
        "tup3 = \"a\", \"b\", \"c\", \"d\"\n",
        "print (\"tup1[0]: \", tup1[0])\n",
        "print (\"tup2[1:5]: \", tup2[1:5])\n",
        "print(tup3)\n",
        "tup4 = (17)\n",
        "print(type(tup4))\n",
        "tup5 = (17,)\n",
        "print(type(tup5))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "tup1[0]:  physics\n",
            "tup2[1:5]:  (2, 3, 4, 5)\n",
            "('a', 'b', 'c', 'd')\n",
            "<class 'int'>\n",
            "<class 'tuple'>\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KTTj1nDE9Hq7",
        "colab_type": "text"
      },
      "source": [
        "### Strings\n",
        "- immutable sequence of characters\n",
        "- multiline strings using ''' or \"\"\"\n",
        "- Escape sequences\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ULcwjTyTUCeT",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 215
        },
        "outputId": "82f8fc19-230f-4a47-bea5-561095a8a0ef"
      },
      "source": [
        "# Strings\n",
        "\n",
        "firstName = 'john'\n",
        "lastName = \"smith\"\n",
        "message = \"\"\"This is a string that will span across\n",
        " multiple lines. Using newline characters\n",
        "and no spaces for the next lines. The end\n",
        " of lines within this string also count as a \n",
        " newline when printed\"\"\"\n",
        "\n",
        "print(firstName)\n",
        "print(lastName)\n",
        "print(message)\n",
        "\n",
        "\n",
        "var1 = 'Hello World!'\n",
        "var2 = 'RhinoPython'\n",
        "\n",
        "print(var1[0])\n",
        "print(var2[1:5])\n",
        "\n",
        "c = 'Don\\'t Worry'\n",
        "print(c)\n",
        "\n",
        "d = \"C:\\\\Python\\\\Directory\\\\\"\n",
        "print(d)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "john\n",
            "smith\n",
            "This is a string that will span across\n",
            " multiple lines. Using newline characters\n",
            "and no spaces for the next lines. The end\n",
            " of lines within this string also count as a \n",
            " newline when printed\n",
            "H\n",
            "hino\n",
            "Don't Worry\n",
            "C:\\Python\\Directory\\\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lGku9zpB9mXV",
        "colab_type": "text"
      },
      "source": [
        "### Sets & Frozensets\n",
        "- Set is an Unordered sequence of immutable objects\n",
        "- Frozenset is immutable.\n",
        "- set() creates an empty set or converts a list into a set. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QSwV78SWX1_V",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 350
        },
        "outputId": "04f034f8-aeb7-4e32-8c3a-85e9b17b386e"
      },
      "source": [
        "# Sets and Frozensets\n",
        "a = {1,2,3}\n",
        "b = {4,5}\n",
        "c = {1.0, \"Hello\", (1,2,3)} # tuple is immutable\n",
        "print(c)\n",
        "\n",
        "d = set([1,2,3,4])\n",
        "print(d)\n",
        "print(set('hello'))\n",
        "\n",
        "e = {}\n",
        "print(type(e))\n",
        "\n",
        "f = set() # create an empty set\n",
        "print(type(f))\n",
        "\n",
        "f.add(4)  # modify set\n",
        "f.update([5,6,7])\n",
        "print(f)\n",
        "\n",
        "g = frozenset([1,2,3,4])\n",
        "print(g)\n",
        "print(type(g))\n",
        "\n",
        "h = {1.0, \"hello\", g} # g is immutable\n",
        "print(h)\n",
        "\n",
        "\n",
        "my_set = {1,2, [3,4]}  # gives an error"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{1.0, (1, 2, 3), 'Hello'}\n",
            "{1, 2, 3, 4}\n",
            "{'l', 'h', 'e', 'o'}\n",
            "<class 'dict'>\n",
            "<class 'set'>\n",
            "{4, 5, 6, 7}\n",
            "frozenset({1, 2, 3, 4})\n",
            "<class 'frozenset'>\n",
            "{1.0, frozenset({1, 2, 3, 4}), 'hello'}\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "error",
          "ename": "TypeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-58-1da8b0d1f8d4>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     26\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     27\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 28\u001b[0;31m \u001b[0mmy_set\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m}\u001b[0m  \u001b[0;31m# gives an error\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'list'"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gcriCXxT-HwV",
        "colab_type": "text"
      },
      "source": [
        "### Dictionaries\n",
        "\n",
        "- A sequence of key-value pairs\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-cUEu-JseHfj",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 306
        },
        "outputId": "07d35778-b3a5-41e2-94d1-381990e49fc3"
      },
      "source": [
        "# Python Dictionaries\n",
        "\n",
        "numbers = dict(x=5, y=0)\n",
        "print('numbers =', numbers)\n",
        "print(type(numbers))\n",
        "\n",
        "empty = dict()\n",
        "print('empty =', empty)\n",
        "print(type(empty))\n",
        "\n",
        "# Another way to create dictionaries\n",
        "n2 = {'y': 0, 'x': 5}\n",
        "print(n2)\n",
        "print(type(n2))\n",
        "empty = {}  # empty dictionaries\n",
        "print(type(empty))\n",
        "\n",
        "# create dictionary using iterables\n",
        "numbers1 = dict([('x', 5), ('y', -5)])\n",
        "print('numbers1 =',numbers1)\n",
        "\n",
        "# keyword argument is also passed\n",
        "numbers2 = dict([('x', 5), ('y', -5)], z=8)\n",
        "print('numbers2 =',numbers2)\n",
        "\n",
        "# zip() creates an iterable in Python 3\n",
        "numbers3 = dict(dict(zip(['x', 'y', 'z'], [1, 2, 3])))\n",
        "print('numbers3 =',numbers3)\n",
        "\n",
        "# Create dictionaries using mappings\n",
        "numbers1 = dict({'x': 4, 'y': 5})\n",
        "print('numbers1 =',numbers1)\n",
        "\n",
        "# you don't need to use dict() in above code\n",
        "numbers2 = {'x': 4, 'y': 5}\n",
        "print('numbers2 =',numbers2)\n",
        "\n",
        "# keyword argument is also passed\n",
        "numbers3 = dict({'x': 4, 'y': 5}, z=8)\n",
        "print('numbers3 =',numbers3)\n",
        "\n",
        "\n",
        "#using dict()\n",
        "my_dict = dict({1:'apple', 2:'ball'})\n",
        "print(my_dict)\n",
        "\n",
        "# Accessing dictionary elements\n",
        "my_dict = {'name':'Jack', 'age': 26, 'gender': 'male', 'passport': 4567, \\\n",
        "           'address': 'Lancashire'}\n",
        "print(my_dict['name'])\n",
        "print(my_dict.get('age'))\n",
        "print(my_dict.get('passport'))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "numbers = {'x': 5, 'y': 0}\n",
            "<class 'dict'>\n",
            "empty = {}\n",
            "<class 'dict'>\n",
            "{'y': 0, 'x': 5}\n",
            "<class 'dict'>\n",
            "<class 'dict'>\n",
            "numbers1 = {'x': 5, 'y': -5}\n",
            "numbers2 = {'x': 5, 'y': -5, 'z': 8}\n",
            "numbers3 = {'x': 1, 'y': 2, 'z': 3}\n",
            "numbers1 = {'x': 4, 'y': 5}\n",
            "numbers2 = {'x': 4, 'y': 5}\n",
            "numbers3 = {'x': 4, 'y': 5, 'z': 8}\n",
            "{1: 'apple', 2: 'ball'}\n",
            "Jack\n",
            "26\n",
            "4567\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q7nGoSNW6_5H",
        "colab_type": "text"
      },
      "source": [
        "### GPA Calculator\n",
        "Your first Python Program. \n",
        "\n",
        "Notice the following things:\n",
        "- print strings\n",
        "- indented code blocks for various control structures\n",
        "- Take input from keyboard."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rb8rX3TXqKD5",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 221
        },
        "outputId": "b0dcf334-3be4-43b7-c9eb-4d436b935221"
      },
      "source": [
        "print( 'Welcome to the GPA calculator.' )\n",
        "print( 'Please enter all your letter grades, one per line.' )\n",
        "print( 'Enter a blank line to designate the end.' )\n",
        "# map from letter grade to point value\n",
        "points = { 'A+':4.0, 'A':4.0, 'A-':3.67, 'B+':3.33, 'B' :3.0, 'B-' :2.67,\n",
        "'C+':2.33, 'C':2.0, 'C':1.67, 'D+':1.33, 'D':1.0, 'F':0.0}\n",
        "num_courses = 0\n",
        "total_points = 0\n",
        "done = False\n",
        "while not done:\n",
        "  grade = input( )\n",
        "  # read line from user\n",
        "  # empty line was entered\n",
        "  if grade == '' :\n",
        "    done = True\n",
        "  elif grade not in points:\n",
        "    # unrecognized grade entered\n",
        "    print(\"Unknown grade {0} being ignored\".format(grade))\n",
        "  else:\n",
        "    num_courses += 1\n",
        "    total_points += points[grade]\n",
        "    # avoid division by zero\n",
        "if num_courses > 0:\n",
        "  print( 'Your GPA is {0:.3} for {1} courses'.format((total_points / \n",
        "                                                    num_courses), num_courses))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Welcome to the GPA calculator.\n",
            "Please enter all your letter grades, one per line.\n",
            "Enter a blank line to designate the end.\n",
            "AAB\n",
            "Unknown grade AAB being ignored\n",
            "A,A,B\n",
            "Unknown grade A,A,B being ignored\n",
            "A\n",
            "A\n",
            "B\n",
            "\n",
            "Your GPA is 3.67 for 3 courses\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HYXdLyZF772N",
        "colab_type": "text"
      },
      "source": [
        "## Classes & Objects\n",
        "\n",
        "- accessor and mutator methods\n",
        "- constructors\n",
        "- Convention for public, protected and private data members\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "liW83azEcH2g",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "01d3dc1b-a04c-4f13-b650-d323c5557318"
      },
      "source": [
        "class Student():\n",
        "  def __init__(self, name=None, age=None, no_sub=None):\n",
        "    self._name = name\n",
        "    self._age = age\n",
        "    self._no_subj = no_sub\n",
        "  \n",
        "  def get_attrib(self):    # Accessor\n",
        "    attrib = [self._name, self._age, self._no_subj]\n",
        "    return attrib\n",
        "  def set_attrib(self,name,age, no_sub):  # Mutator\n",
        "    self._name = name\n",
        "    self._age = age\n",
        "    self._no_subj = no_sub\n",
        "###############\n",
        "\n",
        "stud1 = Student(\"Tom\", 12, 4)\n",
        "stud2 = Student(\"Harry\", 10, 2)\n",
        "print(stud1.get_attrib())\n",
        "print(stud2.get_attrib())\n",
        "stud1.set_attrib(\"Tom.H\", \"13\", 5)\n",
        "stud2.set_attrib(\"Harry.Mitchel\", \"11\", 3)\n",
        "print(stud1.get_attrib())\n",
        "print(stud2.get_attrib())"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "['Tom', 12, 4]\n",
            "['Harry', 10, 2]\n",
            "['Tom.H', '13', 5]\n",
            "['Harry.Mitchel', '11', 3]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l3jbYBir-ejp",
        "colab_type": "text"
      },
      "source": [
        "## Input / Output  & File Handling\n",
        "- Formatting"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dccuRYvO1FI7",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "21b72f6a-aa10-4676-b60b-86fec7354cb8"
      },
      "source": [
        " a = 2 + 4 * 5 / 5 + (3*4+5) \n",
        " print(a)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "23.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Rg3IUWHDqTeO",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 125
        },
        "outputId": "266df6f6-704f-46be-fb87-c58b74718166"
      },
      "source": [
        "# Input / Output\n",
        "print(\"Hello World!\", \"first time here?\")\n",
        "x = input(\"something:\")\n",
        "print(x)\n",
        "print(type(x))\n",
        "\n",
        "year = 2016\n",
        "event = 'Referendum'\n",
        "print(f'Results of the {year} {event}')\n",
        "\n",
        "\n",
        "yes_votes = 42_572_654\n",
        "no_votes = 43_132_495\n",
        "percentage = yes_votes / (yes_votes + no_votes)\n",
        "print('{:-9} YES votes  {:2.2%}'.format(yes_votes, percentage))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Hello World! first time here?\n",
            "something:10\n",
            "10\n",
            "<class 'str'>\n",
            "Results of the 2016 Referendum\n",
            " 42572654 YES votes  49.67%\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5Ia7D_Tl_g_E",
        "colab_type": "text"
      },
      "source": [
        "### File Handling\n",
        "- opening a file\n",
        "- reading a file\n",
        "- writing into a file\n",
        "- closing a file\n",
        "- checking the status of file"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "36tYTi9osddH",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 89
        },
        "outputId": "015e1261-9269-4126-efc3-cd9ea29f0c24"
      },
      "source": [
        "# File I/O\n",
        "# Open a file\n",
        "fo = open(\"foo.txt\", \"w\")\n",
        "print (\"Name of the file: \", fo.name)\n",
        "print (\"Closed or not : \", fo.closed)\n",
        "print (\"Opening mode : \", fo.mode)\n",
        "fo.close()\n",
        "print(\"Closed or Not:\", fo.closed)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Name of the file:  foo.txt\n",
            "Closed or not :  False\n",
            "Opening mode :  w\n",
            "Closed or Not: True\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RpdUzKWqbPIx",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "0f083077-6264-47eb-812d-11bf87c0616f"
      },
      "source": [
        "# File input/output examples\n",
        "\n",
        "f = open(\"test.txt\", 'w')\n",
        "f.write(\"Hello Python!\\n\")\n",
        "f.write(\"Today is Monday\\n\")\n",
        "f.write(\"Hello World!\\n\")\n",
        "f.close()\n",
        "\n",
        "f = open(\"test.txt\", 'r')\n",
        "print(f.read())\n",
        "f.close()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Hello Python!\n",
            "Today is Monday\n",
            "Hello World!\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zngJjA7u-lCi",
        "colab_type": "text"
      },
      "source": [
        "## Exception Handling\n",
        "\n",
        "- Various kind of exceptions raised when following errors are encounted.\n",
        "  - division by zero\n",
        "  - type error\n",
        "  - name error\n",
        "  \n",
        "\n",
        "Exception handling is carried out by the following means:\n",
        "\n",
        "- Raise an exception\n",
        "- Try ... except block\n",
        "- assertions\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MRJME0id34cn",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 180
        },
        "outputId": "f2b780e1-e222-4831-8e1e-f75014374875"
      },
      "source": [
        "# Various types of exceptions\n",
        "\n",
        "10 * (1/0)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "ZeroDivisionError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mZeroDivisionError\u001b[0m                         Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-10-8bf2ad9c61ca>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;36m10\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m/\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;31mZeroDivisionError\u001b[0m: division by zero"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TmOiBlQo4P2X",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 163
        },
        "outputId": "bf9213e7-d000-49c4-e483-725474cbcef2"
      },
      "source": [
        "'2' + 2"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "TypeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-33-d2b23a1db757>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;34m'2'\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m: must be str, not int"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "As57mpgd4NB1",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 163
        },
        "outputId": "6fb46f4c-0438-43b9-f4a9-0710d2d486d1"
      },
      "source": [
        "4 + spam*3"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "NameError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-32-c98bb92cdcac>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;36m4\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mspam\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;31mNameError\u001b[0m: name 'spam' is not defined"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l9tUXsP4-3dL",
        "colab_type": "text"
      },
      "source": [
        "### Use of raise() function to raise exceptions."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "inv8BqAeyUQV",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 333
        },
        "outputId": "5e73c1f3-6bec-46a3-b32a-995bfc8e6d77"
      },
      "source": [
        "\n",
        "# Exception Handling\n",
        "\n",
        "import math\n",
        "\n",
        "def my_sqrt(x):\n",
        "  if not isinstance(x, (int, float)):\n",
        "    raise TypeError('x must be numeric')\n",
        "  elif x < 0:\n",
        "    raise ValueError('x can not be negative')\n",
        "  \n",
        "  return math.sqrt(x)\n",
        "\n",
        "##############\n",
        "\n",
        "\n",
        "x = 25\n",
        "print('sqrt of {} = {}'.format(x, my_sqrt(x)))\n",
        "\n",
        "# x = -25;\n",
        "# print('sqrt of {} = {}'.format(x, my_sqrt(x)))\n",
        "\n",
        "x = \"twenty\"\n",
        "print('sqrt of {} = {}'.format(x, my_sqrt(x)))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "sqrt of 25 = 5.0\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "error",
          "ename": "TypeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-14-679a5799d60d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     20\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     21\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m\"twenty\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 22\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'sqrt of {} = {}'\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmy_sqrt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m<ipython-input-14-679a5799d60d>\u001b[0m in \u001b[0;36mmy_sqrt\u001b[0;34m(x)\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mmy_sqrt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m   \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mfloat\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m     \u001b[0;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'x must be numeric'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m   \u001b[0;32melif\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[0;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'x can not be negative'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mTypeError\u001b[0m: x must be numeric"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5kwQAWSH_Jjy",
        "colab_type": "text"
      },
      "source": [
        "### Try ... except block\n",
        "![alt text](https://)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XkS2b7oi2XAi",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 187
        },
        "outputId": "4d857e9c-1359-4bdb-8d0b-2d6603837c90"
      },
      "source": [
        "try:\n",
        "  fp = open('sample.txt')\n",
        "except IOError as e:\n",
        "  print('Unable to open the file', e)\n",
        "  \n",
        "print(\"\\n\\n -------\\n\")  \n",
        "\n",
        "age = -1\n",
        "while age <= 0:\n",
        "  try:\n",
        "    age = int(input('Enter your agen in years: '))\n",
        "    if age <= 0:\n",
        "      print('Your age must be positive')\n",
        "  except(ValueError, EOFError):\n",
        "    print('invalid response')\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Unable to open the file [Errno 2] No such file or directory: 'sample.txt'\n",
            "\n",
            "\n",
            " -------\n",
            "\n",
            "Enter your agen in years: 25.2\n",
            "invalid response\n",
            "Enter your agen in years: Twenty\n",
            "invalid response\n",
            "Enter your agen in years: 20\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nMpEa4le_OF_",
        "colab_type": "text"
      },
      "source": [
        "### Assertions\n",
        "- Enforces a condition.\n",
        "- Assertion exception is raised if the condition is not satisfied."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qimoWmSI3hy_",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 370
        },
        "outputId": "325e5fd0-35c0-4659-c743-8b6dfcba2516"
      },
      "source": [
        "# Assertions\n",
        "\n",
        "def KelvinToFahrenheit(Temperature):\n",
        "   assert (Temperature >= 0),\"Colder than absolute zero!\"\n",
        "   return ((Temperature-273)*1.8)+32\n",
        "\n",
        "print (KelvinToFahrenheit(273))\n",
        "print (int(KelvinToFahrenheit(505.78)))\n",
        "print (KelvinToFahrenheit(-5))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "32.0\n",
            "451\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "error",
          "ename": "AssertionError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-30-e5becc09480c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0mprint\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mKelvinToFahrenheit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m273\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mprint\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mKelvinToFahrenheit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m505.78\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m \u001b[0mprint\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mKelvinToFahrenheit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m<ipython-input-30-e5becc09480c>\u001b[0m in \u001b[0;36mKelvinToFahrenheit\u001b[0;34m(Temperature)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mKelvinToFahrenheit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mTemperature\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m    \u001b[0;32massert\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mTemperature\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\"Colder than absolute zero!\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m    \u001b[0;32mreturn\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mTemperature\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m273\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0;36m1.8\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m32\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mAssertionError\u001b[0m: Colder than absolute zero!"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uzcwzF_HASNM",
        "colab_type": "text"
      },
      "source": [
        "## Iterators & Generators\n",
        "\n",
        "- Iterators are created using generator functions\n",
        "- Generator functions can have more than one yield command.\n",
        "- iter() command converts an input into an iterable\n",
        "\n",
        "\n",
        "Examples:\n",
        "- Factors\n",
        "- Fibonacci series"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WkYtXMzHXjZW",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "outputId": "3588533f-2629-4f76-e486-a7219e83d9b6"
      },
      "source": [
        "# Generators - Factors of a number\n",
        "\n",
        "def factors(n): \n",
        "  for k in range(1,n+1):\n",
        "    if n % k == 0: \n",
        "      yield k\n",
        "      \n",
        "# an efficient version\n",
        "def factors2(n): # generator that computes factors\n",
        "  k = 1\n",
        "  while k*k < n: # while k < sqrt(n)\n",
        "    if n % k == 0:\n",
        "      yield k\n",
        "      yield n // k\n",
        "    k += 1\n",
        "  if k*k == n: # special case if n is perfect square\n",
        "    yield k\n",
        "  \n",
        "\n",
        "num_factors = 0\n",
        "f = []\n",
        "#for factor in factors1(100):\n",
        "for factor in factors2(100):\n",
        "  if factor > 0:\n",
        "    f.append(factor)\n",
        "    num_factors += 1\n",
        "print(\"Total number of factors:{}\".format(num_factors))\n",
        "print(\"Factors are:{}\".format(f))\n",
        "  "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Total number of factors:9\n",
            "Factors are:[1, 100, 2, 50, 4, 25, 5, 20, 10]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "C45TzfC_h6t2",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 161
        },
        "outputId": "8f94799a-b33d-4895-c844-5993ca4536c6"
      },
      "source": [
        "# iterators\n",
        "data = [1,2,3,4]\n",
        "\n",
        "for i in iter(data):\n",
        "  print(data[i-1])\n",
        "  \n",
        "for element in data:\n",
        "  print(element)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "1\n",
            "2\n",
            "3\n",
            "4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cu_upMyHk9sg",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "a4a92b07-63d5-42bb-c3de-35e04ee08fff"
      },
      "source": [
        "# Fibpnacci series - You can produce infinite series\n",
        "\n",
        "def fibonacci():\n",
        "  a = 0\n",
        "  b = 1\n",
        "  while True: # keep going...\n",
        "    yield a # report value, a, during this pass\n",
        "    future = a + b\n",
        "    a = b # this will be next value reported\n",
        "    b = future\n",
        "    \n",
        "series =[]    \n",
        "for i in fibonacci():\n",
        "  if(i < 100):\n",
        "    series.append(i)\n",
        "  else:\n",
        "    break\n",
        "print(\"Fibonacci series:{}\".format(series))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Fibonacci series:[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I50Ms76TBDL2",
        "colab_type": "text"
      },
      "source": [
        "### Some examples of Python Conveniences\n",
        "- List comprehension\n",
        "- Automated Packing & Unpacking\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rNAOFpxcF_Sp",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "26413af4-6924-47e6-95d6-d201d7796d12"
      },
      "source": [
        "def factors(n):\n",
        "  return [k for k in range(1,n+1) if n%k ==0]\n",
        "\n",
        "print(\"Factors of 100: \", factors(100))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Factors of 100:  [1, 2, 4, 5, 10, 20, 25, 50, 100]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "anZn4GMsGoUA",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "e145b191-918b-4a30-ef07-ec7bb27724be"
      },
      "source": [
        "def factors(n):\n",
        "  f = []\n",
        "  for k in range(1,n+1):\n",
        "    if n % k == 0: \n",
        "      f.append(k)\n",
        "  return f\n",
        "  \n",
        "print(\"Factors of 100: \", factors(100))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Factors of 100:  [1, 2, 4, 5, 10, 20, 25, 50, 100]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3ILd2JOPBse",
        "colab_type": "text"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vZxKRBezqxZP",
        "colab_type": "text"
      },
      "source": [
        "# Chapter 2: Object oriented Programming Examples\n",
        "\n",
        "### Classes & Objects"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HpIbrwokqvIn",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 247
        },
        "outputId": "c971559d-8cb5-43c8-b25f-b1b80cce17f1"
      },
      "source": [
        "class Person:\n",
        "  def __init__(self, name=None, age=None, gender=None):\n",
        "    self._name = name    # protected or nonpublic\n",
        "    self._age = age    \n",
        "    self.__gender = gender  # private\n",
        "\n",
        "  def get_attrib(self):\n",
        "    print(\"Hello my name is \", self._name)\n",
        "    print(\"My age is\", self._age)\n",
        "    print(\"My Gender is\", self.__gender)\n",
        "\n",
        "  def set_attrib(self, name, age, gender):\n",
        "    self._name=name\n",
        "    self._age = age\n",
        "    self.__gender = gender\n",
        "\n",
        "p1 = Person(\"John\", 36, \"Male\")\n",
        "p1.get_attrib()\n",
        "p1.set_attrib(\"Harry\", 25, \"Male\")\n",
        "p1.get_attrib()\n",
        "\n",
        "p2 = Person()\n",
        "p2.get_attrib()\n",
        "\n",
        "p2.__gender = \"Female\"   # still accessible\n",
        "p2._name = \"Sally\"       # Still accessible\n",
        "p2._age = 23             # Still accessible\n",
        "\n",
        "p2.get_attrib()\n",
        "\n",
        "print(\"Gender of P2 is\", p2.__gender)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Hello my name is  John\n",
            "My age is 36\n",
            "My Gender is Male\n",
            "Hello my name is  Harry\n",
            "My age is 25\n",
            "My Gender is Male\n",
            "Hello my name is  None\n",
            "My age is None\n",
            "My Gender is None\n",
            "Hello my name is  Sally\n",
            "My age is 23\n",
            "My Gender is None\n",
            "Gender of P2 is Female\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "j87Se30jxmRJ",
        "colab_type": "text"
      },
      "source": [
        "## Operator Overloading"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "A-pYsjJWBGEr",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 87
        },
        "outputId": "115fa52d-57c9-49a6-a2da-700f10749e1c"
      },
      "source": [
        "# Operator overloading\n",
        "print(2+3)  # addition of numbers\n",
        "print([2,3] + [4,5])\n",
        "a = [[2,3],[4,5]]\n",
        "b = [[7,8],[10,11]]\n",
        "c = a + b    # extending an array\n",
        "print(c)\n",
        "print(\"Tom\"+\"Harry\")  # concatenation of strings"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "5\n",
            "[2, 3, 4, 5]\n",
            "[[2, 3], [4, 5], [7, 8], [10, 11]]\n",
            "TomHarry\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WNMYGkdDxwfj",
        "colab_type": "text"
      },
      "source": [
        "### Overloading through specially named methods"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KiDO-pmnS3RT",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        },
        "outputId": "dc8cec25-22f3-4e60-b779-efaccca6b36c"
      },
      "source": [
        "class Vector:\n",
        "  '''\n",
        "  Represent a vector in a multidimensional space.\n",
        "\n",
        "  '''\n",
        "  def __init__(self, d):\n",
        "    '''Create d-dimensional vector of zeros.'''\n",
        "    self._coords = [0] * d\n",
        "\n",
        "  def __len__(self):\n",
        "    '''Return the dimension of the vector.'''\n",
        "    return len(self._coords)\n",
        "\n",
        "  def __getitem__(self, j):\n",
        "    '''Return jth coordinate of vector.'''\n",
        "    return self._coords[j]\n",
        "\n",
        "  def __setitem__(self, j, val):\n",
        "    '''Set jth coordinate of vector to given value.'''\n",
        "    self._coords[j] = val\n",
        "\n",
        "  def __add__(self, other):\n",
        "    '''Return sum of two vectors.'''\n",
        "    if len(self) != len(other): # relies on __len__ method\n",
        "      raise ValueError( 'dimensions must agree' )\n",
        "    result = Vector(len(self)) # start with vector of zeros\n",
        "    for j in range(len(self)):\n",
        "      result[j] = self[j] + other[j]\n",
        "    return result\n",
        "\n",
        "  def __eq__(self, other):\n",
        "    '''Return True if vector has same coordinates as other.'''\n",
        "    return self._coords == other._coords\n",
        "\n",
        "  def __ne__(self, other):\n",
        "    '''Return True if vector differs from other.'''\n",
        "    return not self == other # rely on existing __eq__ definition\n",
        "\n",
        "  def __str__(self):\n",
        "    '''Produce string representation of vector.'''\n",
        "    return '<' + str(self._coords)[1:-1] + '>' # adapt list representation\n",
        "  \n",
        "  \n",
        "########\n",
        "\n",
        "a = Vector(5)\n",
        "b = Vector(5)\n",
        "c = Vector(5)\n",
        "d = Vector(0)\n",
        "\n",
        "print( 'a dimension:', len(a))\n",
        "print( 'b dimension:', len(b))\n",
        "\n",
        "a[2] = 3\n",
        "b[3] = 2\n",
        "\n",
        "c = a + b  # overload + operator\n",
        "\n",
        "print('c:', c)  # overloaded str operator\n",
        "\n",
        "total = 0;\n",
        "for entry in c:  # implicit iteration via __len__ and __getitem__\n",
        "  total += entry\n",
        "\n",
        "if bool(d):   # Uses implied meaning of bool function\n",
        "  print('The vector has non zero length')\n",
        "else:\n",
        "  print('The vector has zero length')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "a dimension: 5\n",
            "b dimension: 5\n",
            "c: <0, 0, 3, 2, 0>\n",
            "The vector has zero length\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "H5M4I0Mdx5RW",
        "colab_type": "text"
      },
      "source": [
        "### Another example of creating Iterators for a user-defined class"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hgKp8vYH9SZI",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 123
        },
        "outputId": "69f7efcc-e21a-44ae-b792-bf59231fc7a0"
      },
      "source": [
        "class SequenceIterator:\n",
        "  '''An iterator for any of Python s sequence types.'''\n",
        "\n",
        "  def __init__(self, sequence):\n",
        "    '''Create an iterator for the given sequence.'''\n",
        "    self._seq = sequence # keep a reference to the underlying data\n",
        "    self._k = -1 # will increment to 0 on first call to next\n",
        "\n",
        "  def __next__(self):\n",
        "    '''Return the next element, or else raise StopIteration error.'''\n",
        "    self._k += 1 # advance to next index\n",
        "    if self._k < len(self._seq):\n",
        "      return(self._seq[self._k]) # return the data element\n",
        "    else:\n",
        "      raise StopIteration() # there are no more elements\n",
        "\n",
        "  def __iter__(self):\n",
        "    '''By convention, an iterator must return itself as an iterator.'''\n",
        "    return self\n",
        "\n",
        "################\n",
        "\n",
        "data = [7, 8, 9, 2, 3, 5]\n",
        "\n",
        "for i in SequenceIterator(data):\n",
        "  print(i)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "7\n",
            "8\n",
            "9\n",
            "2\n",
            "3\n",
            "5\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mJZeztIEyHN9",
        "colab_type": "text"
      },
      "source": [
        "## Class Iterator Example\n",
        "\n",
        "- creating class iterator by using specially named functions:  `__len__()` and `__getitem__()` functions. \n",
        "- by using generator functions by using `__iter__()` and `__next__()` functions.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6-KCJuxpBhGR",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        },
        "outputId": "717a18fe-fd46-410e-abd3-355bbee64795"
      },
      "source": [
        "class Range:\n",
        "  '''A class that mimics the built-in range class.'''\n",
        "\n",
        "  def __init__(self, start, stop=None, step=1):\n",
        "    '''\n",
        "    Initialize a Range instance.\n",
        "    Semantics is similar to built-in range class.\n",
        "    '''\n",
        "    if step == 0:\n",
        "      raise ValueError( 'step cannot be 0' )\n",
        "    \n",
        "    if stop is None: # special case of range(n)\n",
        "      start, stop = 0, start # should be treated as if range(0,n)\n",
        "\n",
        "    # calculate the effective length once\n",
        "    self._length = max(0, (stop - start + step - 1) // step)\n",
        "\n",
        "    # need knowledge of start and step (but not stop) to support getitem\n",
        "    self._start = start\n",
        "    self._step = step\n",
        "\n",
        "  def __len__(self):\n",
        "    '''Return number of entries in the range.'''\n",
        "    return self._length\n",
        "\n",
        "  def __getitem__(self, k):\n",
        "    '''Return entry at index k (using standard interpretation if negative).'''\n",
        "    if k < 0:\n",
        "      k += len(self) # attempt to convert negative index\n",
        "\n",
        "    if not 0 <= k < self._length:\n",
        "      raise IndexError( 'index out of range' )\n",
        "\n",
        "    return self._start + k * self._step\n",
        "\n",
        "\n",
        "##############\n",
        "\n",
        "r = Range(8, 140, 5)\n",
        "print('Length of r = ',len(r))\n",
        "print('Sixteenth element of r =', r[15])\n",
        "\n",
        "for i in r:\n",
        "  print(i, end=' ')\n",
        "print()\n",
        "\n",
        "for i in range(0,27):\n",
        "  print(r[i], end=' ')\n",
        "print()\n",
        "\n",
        "for i in Range(8,140, 5):\n",
        "  print(i, end=' ')\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Length of r =  27\n",
            "Sixteenth element of r = 83\n",
            "8 13 18 23 28 33 38 43 48 53 58 63 68 73 78 83 88 93 98 103 108 113 118 123 128 133 138 \n",
            "8 13 18 23 28 33 38 43 48 53 58 63 68 73 78 83 88 93 98 103 108 113 118 123 128 133 138 \n",
            "8 13 18 23 28 33 38 43 48 53 58 63 68 73 78 83 88 93 98 103 108 113 118 123 128 133 138 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kUXXiCvWyAnA",
        "colab_type": "text"
      },
      "source": [
        "## Inheritance\n",
        "\n",
        "- Child class can inherit methods and data from parent class.\n",
        "- Child class can modify or redefine methods inherited from parents. \n",
        "\n",
        "Two Examples\n",
        "- Credit Card Example\n",
        "- Progression Example\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4j22NFCACn3b",
        "colab_type": "text"
      },
      "source": [
        "### Credit-card example \n",
        "\n",
        "- Base class: CreditCard\n",
        "- Child class: PredatoryCreditCard\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "497Uu5bDx2tB",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 461
        },
        "outputId": "9d67a635-9159-4fa0-e333-71ba03b335a3"
      },
      "source": [
        "# Credit Card Example\n",
        "\n",
        "class CreditCard:\n",
        "  \n",
        "  def __init__(self, customer, bank, acnt, limit):\n",
        "    \n",
        "    \n",
        "    self._customer = customer\n",
        "    self._bank = bank\n",
        "    self._account = acnt\n",
        "    self._limit = limit\n",
        "    self._balance = 0\n",
        "    \n",
        "    \n",
        "  def get_customer(self):\n",
        "    return self._customer\n",
        "  \n",
        "  def get_bank(self):\n",
        "    return self._bank\n",
        "  \n",
        "  def get_account(self):\n",
        "    return self._account\n",
        "  \n",
        "  def get_limit(self):\n",
        "    return self._limit\n",
        "  \n",
        "  def get_balance(self):\n",
        "    return self._balance\n",
        "  \n",
        "  \n",
        "  def charge(self, price):\n",
        "    '''\n",
        "    Charge given price to the card, assuming sufficient credit limit. \n",
        "    Return True if charge was process; fale if charge was denied\n",
        "    '''\n",
        "    \n",
        "    if price + self._balance > self._limit: \n",
        "      return False\n",
        "    else:\n",
        "      self._balance += price\n",
        "      return True\n",
        "    \n",
        "  def make_payment(self, amount):\n",
        "    '''\n",
        "    Process customer payment that reduces the balance\n",
        "    '''\n",
        "    self._balance -= amount\n",
        "    \n",
        "  def _set_balance(self, value): # protected method\n",
        "    self._balance = value\n",
        "    \n",
        "#########################\n",
        "\n",
        "# Test Module\n",
        "\n",
        "\n",
        "if __name__ == '__main__':\n",
        "  wallet = []\n",
        "  wallet.append(CreditCard('John Bowman' , 'California Savings' , \n",
        "                           '5391 0375 9387 5309' , 2500) )\n",
        "  wallet.append(CreditCard('John Bowman' , 'California Federal' , \n",
        "                            '3485 0399 3395 1954' , 3500) )\n",
        "  wallet.append(CreditCard('John Bowman' , 'California Finance' , \n",
        "                            '5391 0375 9387 5309' , 5000) )\n",
        "  \n",
        "  for val in range(1,17):\n",
        "    wallet[0].charge(val)\n",
        "    wallet[1].charge(2*val)\n",
        "    wallet[2].charge(3*val)\n",
        "    \n",
        "  for c in range(3):\n",
        "    print('Customer =', wallet[c].get_customer())\n",
        "    print('Bank = ', wallet[c].get_bank())\n",
        "    print('Account = ', wallet[c].get_account())\n",
        "    print('Limit = ', wallet[c].get_limit())\n",
        "    print('Balance =', wallet[c].get_balance())\n",
        "    while wallet[c].get_balance() > 100:\n",
        "      wallet[c].make_payment(100)\n",
        "      print('New Balance = ', wallet[c].get_balance())\n",
        "    print('----------------------')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Customer = John Bowman\n",
            "Bank =  California Savings\n",
            "Account =  5391 0375 9387 5309\n",
            "Limit =  2500\n",
            "Balance = 136\n",
            "New Balance =  36\n",
            "----------------------\n",
            "Customer = John Bowman\n",
            "Bank =  California Federal\n",
            "Account =  3485 0399 3395 1954\n",
            "Limit =  3500\n",
            "Balance = 272\n",
            "New Balance =  172\n",
            "New Balance =  72\n",
            "----------------------\n",
            "Customer = John Bowman\n",
            "Bank =  California Finance\n",
            "Account =  5391 0375 9387 5309\n",
            "Limit =  5000\n",
            "Balance = 408\n",
            "New Balance =  308\n",
            "New Balance =  208\n",
            "New Balance =  108\n",
            "New Balance =  8\n",
            "----------------------\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Dy_XEWyaYYp0",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "0c74b9dd-e767-4ffe-a896-a42f10eac8d7"
      },
      "source": [
        "# Inheritance example - Extension of credit card program\n",
        "# Run the Credit card example above.\n",
        "\n",
        "class PredatoryCreditCard(CreditCard):\n",
        "  ''' An extension to CreditCard that compounds interest and fees.'''\n",
        "\n",
        "  def __init__(self, customer, bank, acnt, limit, apr):\n",
        "    '''\n",
        "    Create a new predatory credit card instance.\n",
        "    The initial balance is zero.\n",
        "    customer: the name of the customer (e.g., John Bowman )\n",
        "    bank: the name of the bank (e.g., California Savings )\n",
        "    acnt: the acount identifier (e.g., 5391 0375 9387 5309 )\n",
        "    limit: credit limit (measured in dollars)\n",
        "    apr: annual percentage rate (e.g., 0.0825 for 8.25% APR)\n",
        "    '''\n",
        "    super().__init__(customer, bank, acnt, limit)  # call super constructor\n",
        "    self._apr = apr\n",
        "    \n",
        "    \n",
        "  def charge(self, price): # modified inherited behaviour\n",
        "    '''\n",
        "    Charge given price to the card, assuming sufficient credit limit.\n",
        "    Return True if charge was processed.\n",
        "    Return False and assess 5 fee if charge is denied.\n",
        "    '''\n",
        "    \n",
        "    success = super().charge(price) # call inherited method\n",
        "    if not success:\n",
        "      self._balance += 5  # assess penalty\n",
        "    return success\n",
        "  \n",
        "  \n",
        "  def process_month(self):  # New behaviour in the child class\n",
        "    '''\n",
        "    Assess monthly interest on outstanding balance\n",
        "    '''\n",
        "    current_balance = super().get_balance()\n",
        "    if current_balance > 0:\n",
        "      # if positive balanec, convert APR to monthly multiplicative factor\n",
        "      monthly_factor = pow(1 + self._apr, 1/12)\n",
        "      current_balance *= monthly_factor\n",
        "      super()._set_balance(current_balance)\n",
        "      \n",
        "      \n",
        "##################\n",
        "\n",
        "pcc = PredatoryCreditCard('John Doe', '1st Bank', '5391 0375 9387 5309', \n",
        "                          1000, 0.0825)\n",
        "\n",
        "pcc.charge(2000)\n",
        "print('Available Balance:', pcc.get_balance())\n",
        "\n",
        "pcc.process_month()\n",
        "print('Available Balance after processing:',pcc.get_balance())\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Available Balance: 5\n",
            "Available Balance after processing: 5.03313983402184\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RFi-GPsMCx2l",
        "colab_type": "text"
      },
      "source": [
        "### Progression\n",
        "\n",
        "- Base Class: Progression\n",
        "- Child Classes: \n",
        "  - ArithmeticProgression\n",
        "  - GeometricProgression\n",
        "  - FibonacciProgression\n",
        "\n",
        "\n",
        "- Also see how the generator functions are used for creating iterators. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZgKweFRETAhH",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "285fa64d-5deb-4864-af29-ee47072160a5"
      },
      "source": [
        "# Progression Class\n",
        "\n",
        "class Progression:\n",
        "  '''\n",
        "  Iterator producing a generic progression.\n",
        "  Default iterator produces the whole numbers 0, 1, 2, ...\n",
        "  '''\n",
        "\n",
        "  def __init__(self, start=0):\n",
        "    ''' Initialize current to the first value of the progression.'''\n",
        "  \n",
        "    self._current = start\n",
        "\n",
        "  def _advance(self):\n",
        "    '''\n",
        "    Update self._current to a new value.\n",
        "    This should be overridden by a subclass to customize progression. \n",
        "    By convention, if current is set to None, this designates the \n",
        "    end of a finite progression.\n",
        "    '''\n",
        "\n",
        "    self._current += 1\n",
        "\n",
        "  def __next__(self):\n",
        "    '''Return the next element, or else raise StopIteration error.'''\n",
        "  \n",
        "    if self._current is None: # our convention to end a progression\n",
        "      raise StopIteration()\n",
        "    else:\n",
        "      answer = self._current # record current value to return\n",
        "      self._advance( ) # advance to prepare for next time\n",
        "      return answer # return the answer\n",
        "\n",
        "  def __iter__(self):\n",
        "    '''By convention, an iterator must return itself as an iterator.'''\n",
        "    return self\n",
        "\n",
        "  def print_progression(self, n):\n",
        "    '''Print next n values of the progression.'''\n",
        "    print(' '.join(str(next(self)) for j in range(n)))  #next() is overloaded here.\n",
        "    \n",
        "######################\n",
        "\n",
        "seq = Progression()\n",
        "seq.print_progression(10)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0 1 2 3 4 5 6 7 8 9\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9Px5_q3Ob-kk",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "fa26dd79-8ca0-4d33-b777-5e6264cc2302"
      },
      "source": [
        "# Arithmetic Progression\n",
        "# Execute the code for \"Progression Class before executing this cell\"\n",
        "\n",
        "class ArithmeticProgression(Progression): # inherit from Progression\n",
        "  '''Iterator producing an arithmetic progression.'''\n",
        "\n",
        "  def __init__(self, increment=2, start=0):\n",
        "    '''\n",
        "    Create a new arithmetic progression.\n",
        "    increment: the fixed constant to add to each term (default 1)\n",
        "    start: the first term of the progression (default 0)\n",
        "    '''\n",
        "    super().__init__(start) # initialize base class\n",
        "    self._increment = increment\n",
        "\n",
        "  def _advance(self): # override inherited version\n",
        "    '''Update current value by adding the fixed increment.'''\n",
        "    self._current += self._increment\n",
        "      \n",
        "      \n",
        "#################\n",
        "\n",
        "a = ArithmeticProgression()\n",
        "a.print_progression(10)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0 2 4 6 8 10 12 14 16 18\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UDtQ71-na1N7",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "2d7a3a81-5e7f-43dd-c8d4-b2d9fe3a11bf"
      },
      "source": [
        "# Geometric Progression\n",
        "# Execute the code for \"Progression Class\" before executing this cell\n",
        "\n",
        "\n",
        "class GeometricProgression(Progression): # inherit from Progression\n",
        "  '''Iterator producing a geometric progression.'''\n",
        "\n",
        "  def __init__(self, base=2, start=1):\n",
        "    '''\n",
        "    Create a new geometric progression.\n",
        "    base: the fixed constant multiplied to each term (default 2)\n",
        "    start: the first term of the progression (default 1)\n",
        "    '''\n",
        "\n",
        "    super().__init__(start)\n",
        "    self._base = base\n",
        "\n",
        "  def _advance(self): # override inherited version\n",
        "    '''Update current value by multiplying it by the base value.'''\n",
        "    self._current *= self._base\n",
        "    \n",
        " ####################\n",
        "\n",
        "b = GeometricProgression()\n",
        "b.print_progression(10)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 2 4 8 16 32 64 128 256 512\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m9GGgCMpnqFk",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "outputId": "ead320a4-e5bd-40c5-ea3f-b9567fcf5cf4"
      },
      "source": [
        "# Fibonacci Progression\n",
        "# Run the Progression class above first\n",
        "\n",
        "class FibonacciProgression(Progression):\n",
        "  '''Iterator producing a generalized Fibonacci progression.'''\n",
        "\n",
        "  def __init__(self, first=0, second=1):\n",
        "    '''Create a new fibonacci progression.\n",
        "\n",
        "    first the first term of the progression (default 0)\n",
        "    second the second term of the progression (default 1)\n",
        "    '''\n",
        "    super().__init__(first) # start progression at first\n",
        "    self._prev = second - first # fictitious value preceding the first\n",
        "\n",
        "  def _advance(self):\n",
        "    '''Update current value by taking sum of previous two.'''\n",
        "    self._prev, self._current = self._current, self._prev + self._current\n",
        "    \n",
        "######################\n",
        "\n",
        "c = FibonacciProgression()\n",
        "c.print_progression(10)\n",
        "\n",
        "FibonacciProgression(4,6).print_progression(10)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0 1 1 2 3 5 8 13 21 34\n",
            "4 6 10 16 26 42 68 110 178 288\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kL95Jx5eyBK5",
        "colab_type": "text"
      },
      "source": [
        "### Few test examples for inheritance\n",
        "\n",
        "- Dog class being inherited by child classes representing different breeds \n",
        "- Example demonstrating that the data members are not inherited by default."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JysBO4Ujc49E",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        },
        "outputId": "fdd433fe-ca5e-4086-a4d5-3233b025c784"
      },
      "source": [
        "# A test example for Inheritance\n",
        "\n",
        "class Dog:\n",
        "    def __init__(self, name, age):\n",
        "        self.name = name\n",
        "        self.age = age\n",
        "\n",
        "class JackRussellTerrier(Dog):\n",
        "    pass\n",
        "\n",
        "class Dachshund(Dog):\n",
        "    pass\n",
        "\n",
        "class Bulldog(Dog):\n",
        "    pass\n",
        "\n",
        "miles = JackRussellTerrier(\"Miles\", 4)\n",
        "buddy = Dachshund(\"Buddy\", 9)\n",
        "jack = Bulldog(\"Jack\", 3)\n",
        "jim = Bulldog(\"Jim\", 5)\n",
        "\n",
        "print(isinstance(miles, Dog))\n",
        "print(isinstance(miles, Bulldog))\n",
        "print(isinstance(jack, Dog))\n",
        "print(isinstance(buddy, Bulldog))\n",
        "print(isinstance(jack, Dachshund))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "True\n",
            "False\n",
            "True\n",
            "False\n",
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "24hmKsBa3flg",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "4f339523-5db8-4e00-f8c1-f013ead5de36"
      },
      "source": [
        "# data member is not inherited by the child class by default.\n",
        "# It is inherited only when base constructor is called. \n",
        "class A:\n",
        "    def __init__(self, i = 0):\n",
        "        self.i = i\n",
        "\n",
        "class B(A):\n",
        "    def __init__(self, j = 0): \n",
        "      super().__init__(2)   # Commenting this will give error\n",
        "      self.j = j\n",
        "\n",
        "def main():\n",
        "    b = B()\n",
        "    print(b.i)  # gives error if base constructor is not called. \n",
        "    print(b.j)\n",
        "\n",
        "main()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2\n",
            "0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8b08Y-RTyN-z",
        "colab_type": "text"
      },
      "source": [
        "## Abstract Classes\n",
        "\n",
        "- defines template for other child classes.\n",
        "- abstract base classes (ABCs) can not be directly instantiated. \n",
        "- see the use of `@abstracmethod` and `@property` attribute"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aukaQUMEyQ_u",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 292
        },
        "outputId": "edc2842d-baa6-457d-cbf6-1b27121ea43b"
      },
      "source": [
        "# Python program showing \n",
        "# abstract base class work \n",
        "\n",
        "from abc import ABC, abstractmethod \n",
        "class Animal(ABC):  # base class\n",
        "\n",
        "  @abstractmethod \n",
        "  def move(self):\n",
        "    pass\n",
        "\n",
        "class Human(Animal): # Child class 1\n",
        "\n",
        "\tdef move(self): \n",
        "\t\tprint(\"I can walk and run\") \n",
        "\n",
        "class Snake(Animal): # Child Class 2\n",
        "\n",
        "\tdef move(self): \n",
        "\t\tprint(\"I can crawl\") \n",
        "\n",
        "class Dog(Animal): # Child class 3\n",
        "\n",
        "\tdef move(self): \n",
        "\t\tprint(\"I can bark\") \n",
        "\n",
        "class Lion(Animal):  # Child class 4\n",
        "\n",
        "\tdef move(self): \n",
        "\t\tprint(\"I can roar\") \n",
        "\t\t\n",
        "# Driver code \n",
        "R = Human() \n",
        "R.move() \n",
        "\n",
        "K = Snake() \n",
        "K.move() \n",
        "\n",
        "R = Dog() \n",
        "R.move() \n",
        "\n",
        "K = Lion() \n",
        "K.move() \n",
        "\n",
        "L = Animal()\n",
        "L.move()\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "I can walk and run\n",
            "I can crawl\n",
            "I can bark\n",
            "I can roar\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "error",
          "ename": "TypeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-48-4d1ff6cf0376>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     40\u001b[0m \u001b[0mK\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmove\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     41\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 42\u001b[0;31m \u001b[0mL\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mAnimal\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     43\u001b[0m \u001b[0mL\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mmove\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mTypeError\u001b[0m: Can't instantiate abstract class Animal with abstract methods move"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "J9qjRx2p2q4s",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "b407bfb7-2818-4eaa-e765-270a8b1916f5"
      },
      "source": [
        "# Python program showing \n",
        "# abstract properties \n",
        "\n",
        "import abc\n",
        "from abc import ABC, abstractmethod \n",
        "\n",
        "class parent(ABC): \n",
        "  \n",
        "\t@abc.abstractproperty \n",
        "\tdef geeks(self): \n",
        "\t\tpass\n",
        "\t\t#return \"parent class\"\n",
        "\n",
        "class child(parent): \n",
        "\t\n",
        "\t@property\n",
        "\tdef geeks(self): \n",
        "\t\treturn \"child class\"\n",
        "\n",
        "\n",
        "try: \n",
        "\tr = parent()  # causes error\n",
        "\tprint( r.geeks) \n",
        "except Exception as err: \n",
        "\tprint (err) \n",
        "\n",
        "r = child() \n",
        "print (r.geeks) \n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Can't instantiate abstract class parent with abstract methods geeks\n",
            "child class\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7w7nAXleAjE1",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "35bf87ae-9f03-43af-9190-a33af5bb52d0"
      },
      "source": [
        "import abc\n",
        "from abc import ABC, abstractmethod\n",
        "class AbstractClassExample(ABC):\n",
        "  def __init__(self, value):\n",
        "    self.value = value\n",
        "    super().__init__()\n",
        "  \n",
        "  @abstractmethod\n",
        "  def do_something(self):\n",
        "    pass\n",
        "\n",
        "class DoAdd42(AbstractClassExample):\n",
        "\n",
        "  def do_something(self):\n",
        "    return self.value + 42\n",
        "\n",
        "    \n",
        "\n",
        "X = DoAdd42(4)\n",
        "print(X.do_something())"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "46\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7RgXdXXlDBO-",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        },
        "outputId": "987ce32f-4d89-4357-fb28-dede400bdb27"
      },
      "source": [
        "# Python program invoking a \n",
        "# method using super() \n",
        "\n",
        "import abc \n",
        "from abc import ABC, abstractmethod \n",
        "\n",
        "class R(ABC): \n",
        "\tdef rk(self): \n",
        "\t\tprint(\"Abstract Base Class\") \n",
        "\n",
        "class K(R): \n",
        "\tdef rk(self): \n",
        "\t\tsuper().rk() \n",
        "\t\tprint(\"subclass \") \n",
        "\n",
        "# Driver code \n",
        "r = K() \n",
        "r.rk() \n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Abstract Base Class\n",
            "subclass \n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "V6JvJZ126lgD",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YoRsj6c96V-l",
        "colab_type": "text"
      },
      "source": [
        "# Chapter 3: Algorithm Analysis"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Nl_AycdN_44V",
        "colab_type": "text"
      },
      "source": [
        "## Average Prefix\n",
        "\n",
        "$ A[j] = \\frac{\\sum_{i = 0}^jS[i]}{j+1};\\ j = 0, 1, \\cdots, n-1$\n",
        "\n",
        "\n",
        "First two functions are of quadratic run-time  while the last function is of linear time. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UPWf9l3q3Ed5",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 70
        },
        "outputId": "91662f48-728e-42ff-f6d5-51120b6bf88a"
      },
      "source": [
        "# Average Prefixes\n",
        "# Quadratic-Time Algorithm\n",
        "\n",
        "def prefix_average1(S):\n",
        "  '''return list such that, for all j, A[j] equals average of S[0], ..., S[j].'''\n",
        "  n = len(S)\n",
        "  A = [0] * n # create new list of n zeros\n",
        "  for j in range(n):\n",
        "    total = 0 # begin computing S[0] + ... + S[j]\n",
        "    for i in range(j + 1):\n",
        "      total += S[i]\n",
        "    A[j] = total / (j+1) # record the average\n",
        "  return A\n",
        "\n",
        "\n",
        "def prefix_average2(S):\n",
        "  '''\n",
        "  Return list such that for all j, A[j] equals average of S[0],..., S[j]\n",
        "  '''\n",
        "  n = len(S)\n",
        "  A = [0] * n\n",
        "  for j in range(n):\n",
        "    A[j] = sum(S[0:j+1])/(j+1)\n",
        "  return A \n",
        "\n",
        "# Linear-time algorithm\n",
        "def prefix_average3(S):\n",
        "  '''\n",
        "  Return list such that for all j, A[j] equals average of S[0],..., S[j]\n",
        "  '''\n",
        "  n = len(S)\n",
        "  A = [0] * n\n",
        "  total = 0\n",
        "  for j in range(n):\n",
        "    total += S[j]\n",
        "    A[j] = total / (j+1)\n",
        "  return A\n",
        "\n",
        "## test\n",
        "\n",
        "S = [1, 5, 7, 8, 9, 15]\n",
        "print(prefix_average1(S))\n",
        "print(prefix_average2(S))\n",
        "print(prefix_average3(S))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1.0, 3.0, 4.333333333333333, 5.25, 6.0, 7.5]\n",
            "[1.0, 3.0, 4.333333333333333, 5.25, 6.0, 7.5]\n",
            "[1.0, 3.0, 4.333333333333333, 5.25, 6.0, 7.5]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "go7-Enwb6GYX",
        "colab_type": "text"
      },
      "source": [
        "## Three-way disjointness"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "b3i4KJ4o_2iZ",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 176
        },
        "outputId": "d5f1e969-c748-4479-b57c-10638f04d7a4"
      },
      "source": [
        "# Three-way set disjointness\n",
        "\n",
        "def disjoint1(A, B, C):\n",
        "  '''\n",
        "  Return True if there is no element common to all the three lists\n",
        "  '''\n",
        "  for a in A:\n",
        "    for b in B:\n",
        "      for c in C:\n",
        "        if a == b == c:\n",
        "          return False\n",
        "  return True\n",
        "\n",
        "def disjoint2(A, B, C):\n",
        "  '''\n",
        "  Return True if there is no element common to all the three lists\n",
        "  '''\n",
        "  for a in A:\n",
        "    for b in B:\n",
        "      if a == b:\n",
        "        for c in C:\n",
        "          if a == c:\n",
        "            return False\n",
        "  return True\n",
        "\n",
        "\n",
        "def disjoint22(A, B, C):\n",
        "  '''\n",
        "  Return True if there is no element common to all the three lists\n",
        "  '''\n",
        "  for a in A:\n",
        "    for b in B:\n",
        "      if a == b:\n",
        "        print(a,b)\n",
        "        for c in C:\n",
        "          if a == c:\n",
        "            print(a,c)\n",
        "            return False\n",
        "  return True\n",
        "\n",
        "# test\n",
        "A = [1, 3, 5, 7, 9]\n",
        "B = [2, 4, 5, 7, 9]\n",
        "C = [10, 9, 8, 6, 11]\n",
        "print(disjoint1(A, B, C))\n",
        "print(disjoint2(A, B, C))\n",
        "\n",
        "# worst-case scenario\n",
        "A = [1,2,3,4,5]\n",
        "B = [1,2,3,4,5]\n",
        "C = [7,8,9,10,5]\n",
        "print(disjoint22(A,B,C))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "False\n",
            "False\n",
            "1 1\n",
            "2 2\n",
            "3 3\n",
            "4 4\n",
            "5 5\n",
            "5 5\n",
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Xv9A8NXh6L6V",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "## Element Uniqueness"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "izqshplXJHf2",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "b5a2d43e-8620-41b8-ba3a-50e8978eb656"
      },
      "source": [
        "# Element uniqueness\n",
        "\n",
        "def unique1(S):\n",
        "  '''\n",
        "  Return True if there are no duplicate elements in Sequence S\n",
        "  '''\n",
        "  for j in range(len(S)):\n",
        "    for k in range(j+1, len(S)):\n",
        "      if S[j] == S[k]:\n",
        "        return False\n",
        "  return True\n",
        "\n",
        "S = [1,2,3,4]\n",
        "#print(unique1(S))\n",
        "\n",
        "###################\n",
        "\n",
        "def unique2(S):\n",
        "  '''\n",
        "  Return True if there are no duplicate elements in Sequence S\n",
        "  '''\n",
        "  temp = sorted(S)\n",
        "  for j in range(1, len(temp)):\n",
        "    if S[j-1] == S[j]:\n",
        "      return False\n",
        "  return True\n",
        "\n",
        "T = [4, 3, 2, 1, 1]\n",
        "print(unique2(T))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bPcP4xFh6Rcd",
        "colab_type": "text"
      },
      "source": [
        "## Functions with logarithmic growth rate"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QhXqfT1E0PDp",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 70
        },
        "outputId": "e1150a4f-c31e-4398-de8c-77fa12381cfe"
      },
      "source": [
        "# Functions with logarithmic growth rate\n",
        "\n",
        "def logarithm1(n):\n",
        "  i = 1\n",
        "  while i <= n:\n",
        "    i = i * 2\n",
        "    print(i, end = ' ')\n",
        "\n",
        "def logarithm2(n):\n",
        "  i = n\n",
        "  while i >= 1:\n",
        "    i = i// 2  # floor division\n",
        "    print(i, end =' ')\n",
        "\n",
        "logarithm1(100)\n",
        "print('\\n')\n",
        "logarithm2 (100) "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2 4 8 16 32 64 128 \n",
            "\n",
            "50 25 12 6 3 1 0 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pAxEq3rq6a40",
        "colab_type": "text"
      },
      "source": [
        "# Chapter 4: Recursion\n",
        "\n",
        "We will see four examples in this section:\n",
        "\n",
        "- Factorial\n",
        "- English Ruler\n",
        "- Binary Search Algorithm\n",
        "- Disk Usage Algorithm\n",
        "- Element uniqueness problem"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FVb-fH-De-oj",
        "colab_type": "text"
      },
      "source": [
        "### Factorial Function\n",
        "\n",
        "- It has a time complexity of $O(n)$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "biSAF9GFEn-3",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "056ce36f-a4c0-48cd-cab9-de7dfc426e78"
      },
      "source": [
        "# Factorial Function\n",
        "\n",
        "def factorial(n):\n",
        "  if n == 0:\n",
        "    return 1\n",
        "  else:\n",
        "    return n*factorial(n-1)\n",
        "\n",
        "print(factorial(5))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "120\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yjsl3IblbuDh",
        "colab_type": "text"
      },
      "source": [
        "### English Ruler"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cNHfgG7lbwRY",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 102
        },
        "outputId": "5c9ea58d-0357-4837-e738-589060af1ef1"
      },
      "source": [
        "def draw_line(tick_length, tick_label=''):\n",
        "  '''\n",
        "  Draw one line with given tick length (followed by optional label)\n",
        "  '''\n",
        "  line = '_'*tick_length\n",
        "  if tick_label:\n",
        "    line += ' ' + tick_label \n",
        "  print(line)\n",
        "\n",
        "def draw_interval(center_length):\n",
        "  '''\n",
        "  Draw tick interval based upon a central tick length\n",
        "  '''\n",
        "  if center_length > 0:  # stop when length drops to 0\n",
        "    draw_interval(center_length - 1) # recursively draw top tics\n",
        "    draw_line(center_length) # draw center tick\n",
        "    draw_interval(center_length - 1) # recursively draw bottom ticks\n",
        "\n",
        "def draw_ruler(num_inches, major_length):\n",
        "  '''\n",
        "  Draw English ruler with given number of inches, major tick length\n",
        "  '''\n",
        "  draw_line(major_length, '0')     # draw inch 0 line\n",
        "  for j in range(1, 1+num_inches):\n",
        "    draw_interval(major_length - 1)  # draw interior ticks for inch\n",
        "    draw_line(major_length, str(j))  # draw nch j line and label\n",
        "\n",
        "draw_ruler(2, 2)\n",
        "#draw_ruler(2,3)\n",
        "#draw_ruler(2,5)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "__ 0\n",
            "_\n",
            "__ 1\n",
            "_\n",
            "__ 2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-7MwmAbGoI2-",
        "colab_type": "text"
      },
      "source": [
        "### Binary Search Algorithm\n",
        "\n",
        "- An efficient way to search for an element in a __sorted__ array. \n",
        "- Time complexity is of order $O(\\log n)$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5MaFMOANoY-T",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "79b3d413-ad23-413a-8f67-b08b07d18ddf"
      },
      "source": [
        "# Binary Search algorithm through recursion\n",
        "\n",
        "def binary_search(data, target, low, high):\n",
        "  '''\n",
        "  Return True if target is found in the indicated interval [low, high]\n",
        "  '''\n",
        "  if low > high:\n",
        "    return False  # interval is empty, no match found\n",
        "  else:\n",
        "    mid = (low + high) // 2 \n",
        "    if target == data[mid]:\n",
        "      return mid, True # Match found\n",
        "    elif target < data[mid]:\n",
        "      # recur on the first half of the interval\n",
        "      return binary_search(data, target, low, mid-1) \n",
        "    else:\n",
        "      # recur on the second half of the interval\n",
        "      return binary_search(data, target, mid+1, high)\n",
        "      #return binary_search(data, target, mid, high) # leads to infinite recursion\n",
        "\n",
        "\n",
        "a = [2, 4, 5, 7, 8, 9, 12, 14, 17, 19, 22, 25, 27, 28, 33, 37]\n",
        "\n",
        "print(binary_search(a, 22, 0, 15))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(10, True)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QSU3X4Fnv9DT",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "9965a8b7-84a1-4ccb-bb94-e16464dfe101"
      },
      "source": [
        "# Same as above function.\n",
        "# This, however, does not require one to pass the low and high \n",
        "# indices for the array\n",
        "# But then the index location is lost. One can only tell if the item\n",
        "# is present in the array or not. \n",
        "#---------------------------------------------\n",
        "def binary_search2(data, target):\n",
        "  '''\n",
        "  Return True if target is found in the indicated interval [low, high]\n",
        "  '''\n",
        "  low = 0\n",
        "  high = len(data) - 1\n",
        "\n",
        "  if low > high:\n",
        "    return False  # interval is empty, no match found\n",
        "  else:\n",
        "    mid = (low + high) // 2 \n",
        "    if target == data[mid]:\n",
        "      return True # Match found\n",
        "    elif target < data[mid]:\n",
        "      # recur on the first half of the interval\n",
        "      return binary_search2(data[low:mid], target) \n",
        "    else:\n",
        "      # recur on the second half of the interval\n",
        "      return binary_search2(data[mid+1:high+1], target)\n",
        "\n",
        "\n",
        "a = [2, 4, 5, 7, 8, 9, 12, 14, 17, 19, 22, 25, 27, 28, 33, 37]\n",
        "\n",
        "print(binary_search2(a, 23))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Q0M3iY_w2iAc",
        "colab_type": "text"
      },
      "source": [
        "### File System - Disk Usage\n",
        "\n",
        "- Computes the total disk space utilized by all files and folders within a particular folder.\n",
        "- In the worst case, each recursive call can lead to n recursive calls giving rise to $O(n^2)$ order of time complexity. \n",
        "- However, taking an amortized view, its time complexity is of order $O(n)$ for n number of entries in the file-system."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vg3w7tHi2rpB",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 425
        },
        "outputId": "35ff8390-248c-4075-d4e6-bec4c1b94983"
      },
      "source": [
        "# Disk Usage Example\n",
        "import os\n",
        "def disk_usage(path):\n",
        "  '''\n",
        "  Returns the number of bytes used by a file/folder and any descendents\n",
        "  '''\n",
        "  total = os.path.getsize(path)  \n",
        "  if os.path.isdir(path):  # if this is a directory\n",
        "    for filename in os.listdir(path):\n",
        "      childpath = os.path.join(path,filename)\n",
        "      total += disk_usage(childpath)\n",
        "\n",
        "  print('{0:<7}'.format(total),path)\n",
        "  return total\n",
        "\n",
        "disk_usage('./')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "49      ./.config/configurations/config_default\n",
            "4145    ./.config/configurations\n",
            "134     ./.config/.last_update_check.json\n",
            "5       ./.config/gce\n",
            "630     ./.config/logs/2019.08.27/16.17.22.686467.log\n",
            "394     ./.config/logs/2019.08.27/16.17.07.367707.log\n",
            "8168    ./.config/logs/2019.08.27/16.17.17.407104.log\n",
            "394     ./.config/logs/2019.08.27/16.17.21.663235.log\n",
            "21809   ./.config/logs/2019.08.27/16.17.00.530950.log\n",
            "35491   ./.config/logs/2019.08.27\n",
            "39587   ./.config/logs\n",
            "0       ./.config/config_sentinel\n",
            "7       ./.config/active_config\n",
            "32      ./.config/.metricsUUID\n",
            "48006   ./.config\n",
            "1697    ./sample_data/anscombe.json\n",
            "930     ./sample_data/README.md\n",
            "301141  ./sample_data/california_housing_test.csv\n",
            "1706430 ./sample_data/california_housing_train.csv\n",
            "36523880 ./sample_data/mnist_train_small.csv\n",
            "18289443 ./sample_data/mnist_test.csv\n",
            "56827617 ./sample_data\n",
            "56879719 ./\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "56879719"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bcUJ_yc612T8",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 136
        },
        "outputId": "58a8394e-de0d-4719-b268-a8bc15eb57cf"
      },
      "source": [
        "!ls\n",
        "!ls -a\n",
        "!ls -al"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "sample_data\n",
            ".  ..  .config\tsample_data\n",
            "total 16\n",
            "drwxr-xr-x 1 root root 4096 Aug 27 16:17 .\n",
            "drwxr-xr-x 1 root root 4096 Oct 22 09:10 ..\n",
            "drwxr-xr-x 1 root root 4096 Oct 18 15:18 .config\n",
            "drwxr-xr-x 1 root root 4096 Aug 27 16:17 sample_data\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HqVI3phTfw2F",
        "colab_type": "text"
      },
      "source": [
        "### Element Uniqueness Problem.\n",
        "- We revisit this problem once again.  This was earlier discussed in the Lecture titled \"Algorithm Analysis\".  \n",
        "- The time complexity of the function `unique3()` is $O(2^n)$. This shows a poor use of recursion. \n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zVGNh9-mf-sH",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "outputId": "fa64006b-44bc-4071-91a8-7e997f6198b0"
      },
      "source": [
        "# Element uniqueness problem\n",
        "def unique3(S, start, stop):\n",
        "  '''\n",
        "  Return True if there is no duplicate elements in the array\n",
        "  '''\n",
        "  if stop - start <= 1: return True  # at most one item\n",
        "  elif not unique3(S, start, stop-1): return False # first part has duplicate\n",
        "  elif not unique3(S, start+1, stop): return False # second part has duplicate\n",
        "  else: return S[start] != S[stop-1] # do first and last differ\n",
        "\n",
        "\n",
        "a = [2,2]\n",
        "print(a[0:5])\n",
        "print(unique3(a, 0,2))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2, 2]\n",
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HGaNtSarlr8o",
        "colab_type": "text"
      },
      "source": [
        "### Revisiting Fibonacci algorithm\n",
        "\n",
        "#### Bad fibonacci\n",
        "- This demonstrates another bad use of recursion.\n",
        "- Its time complexity is of order $O(2^n)$\n",
        "- Each call to the function results in two recursive calls leading to exponential time complexity. \n",
        "\n",
        "#### Good fibonacci\n",
        "- here the time complexity is of order $O(n)$.\n",
        "- Each call leads to only one recursive call and reduces the problem size by 1. So for $n$ elements, only $n$ recursive calls will be made leading to linear time complexity. \n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xHQOZ7mPnO_o",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "5e8943a1-2cab-4990-817a-a60dcf3c574b"
      },
      "source": [
        "## Bad fibonacci\n",
        "def bad_fibonacci(n):\n",
        "  '''\n",
        "  Return the nth Fibonacci number\n",
        "  '''\n",
        "  if n <= 1:\n",
        "    return n\n",
        "  else:\n",
        "    return bad_fibonacci(n-2) + bad_fibonacci(n-1)\n",
        "\n",
        "# ----------------------\n",
        "bad_fibonacci(10)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "55"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RlmgBEgJs4yi",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 200
        },
        "outputId": "2003fd15-ee47-4e3c-d08a-e0660e9fcc53"
      },
      "source": [
        "# Good Fibonacci\n",
        "def good_fibonacci(n):\n",
        "  '''\n",
        "  return pair of fibonacci numbers F(n) and F(n-1)\n",
        "  F(-1) = 0\n",
        "  '''\n",
        "  if n <= 1:\n",
        "    print('({}, {})'.format(n,0))\n",
        "    return (n, 0)\n",
        "  else:\n",
        "    (a,b) = good_fibonacci(n-1)\n",
        "    print('({}, {})'.format(a+b,a))\n",
        "    return (a+b, a)\n",
        "\n",
        "#---------------------------\n",
        "good_fibonacci(10)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(1, 0)\n",
            "(1, 1)\n",
            "(2, 1)\n",
            "(3, 2)\n",
            "(5, 3)\n",
            "(8, 5)\n",
            "(13, 8)\n",
            "(21, 13)\n",
            "(34, 21)\n",
            "(55, 34)\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(55, 34)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NQnWpMje8zmu",
        "colab_type": "text"
      },
      "source": [
        "### Linear recursion Example  \n",
        "\n",
        "- Summing the elements of a sequence recursively\n",
        "- Reversing a sequence with recursion\n",
        "- Recursive algorithms for computing powers \n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "64SjPMe49GR0",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "b05415b6-e8f2-4f0d-f70a-62ee1206b941"
      },
      "source": [
        "# Summing the elements of a sequence recursively\n",
        "def linear_sum(S, n):\n",
        "  '''\n",
        "  Return the sum the first n numbers of a sequence S\n",
        "  '''\n",
        "  if n == 0:\n",
        "    return 0\n",
        "  else:\n",
        "    return linear_sum(S, n-1) + S[n-1]\n",
        "\n",
        "# Same as above but does not take the additional argument\n",
        "def linear_sum2(S):\n",
        "  n = len(S)\n",
        "\n",
        "  if n == 0:\n",
        "    return 0\n",
        "  else:\n",
        "    return linear_sum2(S[0:n-1]) + S[n-1]\n",
        "\n",
        "#----------------------------------------\n",
        "b = [5, 10, 15, 20]\n",
        "print(linear_sum(b, 4))\n",
        "print(linear_sum2(b))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "50\n",
            "50\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Rn5VMZYXHQnC",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "fa366ca8-d1dd-4c5f-fd72-3cebc6fddc8c"
      },
      "source": [
        "# Reversing a sequence with recursion\n",
        "\n",
        "def reverse(S, start, stop):\n",
        "  ''' \n",
        "  Reverse the elements in implicit slice S[start:stop]\n",
        "  '''\n",
        "  if start < stop - 1:     # if at least two elements\n",
        "    S[start], S[stop-1] = S[stop-1], S[start]  # swap first and last \n",
        "    reverse(S, start+1, stop-1)\n",
        "\n",
        "a = [4,3,6,2,8,9,5]\n",
        "reverse(a, 0, 7)\n",
        "print(a)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[5, 9, 8, 2, 6, 3, 4]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0Fq9hPJRK7QH",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "1f9ef00a-5a17-45dc-b5fe-01415b353172"
      },
      "source": [
        "# Recursive algorithms for computing powers\n",
        "\n",
        "def power(x,n):\n",
        "  '''\n",
        "  Compute the value x**n for integer n\n",
        "  '''\n",
        "  if n ==0:\n",
        "    return 1\n",
        "  else:\n",
        "    return x * power(x, n-1)\n",
        "\n",
        "#----------------------------\n",
        "print(power(2,13))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "8192\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i9ode-reNywQ",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "60ac8f53-498c-49e7-82ca-7c7fe7eb5173"
      },
      "source": [
        "# An efficient version of the power algorithm\n",
        "def power2(x, n):\n",
        "  '''\n",
        "  Compute the value x**n for integer n\n",
        "  '''\n",
        "  if n ==0:\n",
        "    return 1\n",
        "  else:\n",
        "    partial = power2(x, n//2)\n",
        "    result = partial * partial\n",
        "    if n%2 == 1: # if n is odd, include extra factor of x\n",
        "      result *= x\n",
        "    return result\n",
        "#---------------------------------\n",
        "print(power2(2,13))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "8192\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "w70qe2H9ZviC",
        "colab_type": "text"
      },
      "source": [
        "### Binary Recursion Examples\n",
        "\n",
        "- Binary Sum: summing n elements of a sequence\n",
        "- It has $O(n)$ run-time complexity\n",
        "- However, it has $O(\\log n)$ space complexity"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2n4vHcXRaCLN",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "0358dae8-63ce-404c-9a1b-201c576cf687"
      },
      "source": [
        "# Binary sum - Summing n elements of a sequence\n",
        "\n",
        "def binary_sum(S, start, stop):\n",
        "  '''\n",
        "  Return the sum of the numbers in implicit slice S[start:stop]\n",
        "  '''\n",
        "  if start >= stop:\n",
        "    return 0\n",
        "  elif start == stop-1:\n",
        "    return S[start]\n",
        "  else:\n",
        "    mid = (start+stop) // 2\n",
        "    return binary_sum(S, start, mid) + binary_sum(S, mid, stop)\n",
        "\n",
        "a = [5, 10, 3, 7, 9, 2, 4, 12]\n",
        "print(binary_sum(a, 0, 8))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "52\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4jXqMKGrfygS",
        "colab_type": "text"
      },
      "source": [
        "### Eliminating tail recursion\n",
        "\n",
        "- non-recursive implementation of binary_search algorithm\n",
        "- non-recursive implementation of reverse algorithm"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "R5ESVNC4f0oU",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "f998cd6d-5ba7-42a0-fada-ccc343c0c348"
      },
      "source": [
        "# Eliminating tail recursion\n",
        "# Non-recursive implementation of binary_search\n",
        "\n",
        "def binary_search_iterative(data, target):\n",
        "  '''\n",
        "  Return True if target is found in the given python list\n",
        "  '''\n",
        "  low = 0\n",
        "  high = len(data) - 1\n",
        "  while low <= high:\n",
        "    mid = (low + high) // 2\n",
        "    if target == data[mid]:\n",
        "      return True\n",
        "    elif target < data[mid]:\n",
        "      high = mid-1\n",
        "    else:\n",
        "      low = mid+1\n",
        "  return False\n",
        "\n",
        "a = [0, 2, 6, 12, 20, 30, 42, 56, 72, 90 ]\n",
        "print(binary_search_iterative(a, 30))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "True\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gZuN6m6WzaQ9",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "33f7b423-b62c-421b-867e-e81f7305c121"
      },
      "source": [
        "# Non recursive implementation of reverse algorithm\n",
        "def reverse_iterative(S):\n",
        "  '''\n",
        "  Reverse elements in sequence S\n",
        "  '''\n",
        "  start, stop = 0, len(S)\n",
        "  while start < stop - 1:\n",
        "    S[start], S[stop-1] = S[stop-1], S[start] #swap first and last\n",
        "    start, stop = start+1, stop-1 # narrow the range\n",
        "\n",
        "a = [5, 6, 9, 10, 3]\n",
        "print(a)\n",
        "reverse_iterative(a)\n",
        "print(a)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[5, 6, 9, 10, 3]\n",
            "[3, 10, 9, 6, 5]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "x-3BJqMZ2_4I",
        "colab_type": "text"
      },
      "source": [
        "### Some More Examples of Recursion\n",
        "- Tower of Hanoi\n",
        "- Check if a given array is sorted"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-qhsLhDv3E4K",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 283
        },
        "outputId": "15eced65-7d4b-41eb-ad26-c039b62ab33c"
      },
      "source": [
        "# Tower of Hanoi Problem with 4 disks\n",
        "\n",
        "def towers_of_hanoi(numberOfDisks, startPeg=1, endPeg=3):\n",
        "  if numberOfDisks:\n",
        "    towers_of_hanoi(numberOfDisks-1, startPeg, 6-startPeg-endPeg)\n",
        "    print(\"Move disk {:d} from peg {:d} to peg {:d}\".format(numberOfDisks, startPeg, endPeg))\n",
        "    towers_of_hanoi(numberOfDisks-1, 6-startPeg-endPeg, endPeg)\n",
        "\n",
        "#------------------------------\n",
        "towers_of_hanoi(4)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Move disk 1 from peg 1 to peg 2\n",
            "Move disk 2 from peg 1 to peg 3\n",
            "Move disk 1 from peg 2 to peg 3\n",
            "Move disk 3 from peg 1 to peg 2\n",
            "Move disk 1 from peg 3 to peg 1\n",
            "Move disk 2 from peg 3 to peg 2\n",
            "Move disk 1 from peg 1 to peg 2\n",
            "Move disk 4 from peg 1 to peg 3\n",
            "Move disk 1 from peg 2 to peg 3\n",
            "Move disk 2 from peg 2 to peg 1\n",
            "Move disk 1 from peg 3 to peg 1\n",
            "Move disk 3 from peg 2 to peg 3\n",
            "Move disk 1 from peg 1 to peg 2\n",
            "Move disk 2 from peg 1 to peg 3\n",
            "Move disk 1 from peg 2 to peg 3\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "G1mZyc_r4sgP",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "6c65eb41-13ef-4b1e-8349-58f0977e5245"
      },
      "source": [
        "# Check if an array is sorted\n",
        "\n",
        "def is_array_in_sorted_order(A):\n",
        "  # Base case\n",
        "  if len(A) < 1:\n",
        "    raise ValueError(\"array can not be empty\")\n",
        "  elif len(A) == 1:\n",
        "    return True\n",
        "  else:\n",
        "    return A[0] <= A[1] and is_array_in_sorted_order(A[1:])\n",
        "\n",
        "a = [127, 220, 246, 277, 321, 454, 534, 565, 933]\n",
        "b = [4, 3, 1, 5, 7, 8, 0]\n",
        "print(is_array_in_sorted_order(a))\n",
        "print(is_array_in_sorted_order(b))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "True\n",
            "False\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BXDg5x1JfEKK",
        "colab_type": "text"
      },
      "source": [
        "# Chapter 5: Array-Based Sequences\n",
        "\n",
        "- lists, tuples & strings\n",
        "- compact arrays: `array` module \n",
        "- immutable & mutable sequences\n",
        "- Performance Analysis of Dynamic Sequenecs\n",
        "- Efficiency of Python Sequence Types\n",
        "- Some applications"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QRobqIsgfeX5",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 123
        },
        "outputId": "eb3cb17e-f8e6-403b-bb02-4e8a41a9b0ff"
      },
      "source": [
        "print(sys.getsizeof(8))\n",
        "a = 8\n",
        "print(sys.getsizeof(a))\n",
        "\n",
        "# compact arrays\n",
        "primes = array.array( 'i' , [2, 3, 5, 7, 11])\n",
        "print(type(primes))\n",
        "print(primes)\n",
        "\n",
        "# immutable class type\n",
        "c = \"Dog\"\n",
        "#c[1] = 'A' # gives an error. it is an immutable array\n",
        "print(c)\n",
        "\n",
        "print(sys.getsizeof(None))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "28\n",
            "28\n",
            "<class 'array.array'>\n",
            "array('i', [2, 3, 5, 7, 11])\n",
            "Dog\n",
            "16\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XpLeLNpfDNWu",
        "colab_type": "text"
      },
      "source": [
        "## Dynamic arrays"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fibMGcoSwtll",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 496
        },
        "outputId": "00226eb8-5da5-4646-ce4c-4a8566f53ea1"
      },
      "source": [
        "# analyzing a dynamic array\n",
        "import sys\n",
        "data = []\n",
        "for k in range(27):\n",
        "  a = len(data)\n",
        "  b = sys.getsizeof(data)\n",
        "  print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a,b))\n",
        "  data.append(None)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Length:   0; Size in bytes:   64\n",
            "Length:   1; Size in bytes:   96\n",
            "Length:   2; Size in bytes:   96\n",
            "Length:   3; Size in bytes:   96\n",
            "Length:   4; Size in bytes:   96\n",
            "Length:   5; Size in bytes:  128\n",
            "Length:   6; Size in bytes:  128\n",
            "Length:   7; Size in bytes:  128\n",
            "Length:   8; Size in bytes:  128\n",
            "Length:   9; Size in bytes:  192\n",
            "Length:  10; Size in bytes:  192\n",
            "Length:  11; Size in bytes:  192\n",
            "Length:  12; Size in bytes:  192\n",
            "Length:  13; Size in bytes:  192\n",
            "Length:  14; Size in bytes:  192\n",
            "Length:  15; Size in bytes:  192\n",
            "Length:  16; Size in bytes:  192\n",
            "Length:  17; Size in bytes:  264\n",
            "Length:  18; Size in bytes:  264\n",
            "Length:  19; Size in bytes:  264\n",
            "Length:  20; Size in bytes:  264\n",
            "Length:  21; Size in bytes:  264\n",
            "Length:  22; Size in bytes:  264\n",
            "Length:  23; Size in bytes:  264\n",
            "Length:  24; Size in bytes:  264\n",
            "Length:  25; Size in bytes:  264\n",
            "Length:  26; Size in bytes:  344\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4xc-7n-3DI_M",
        "colab_type": "text"
      },
      "source": [
        "### Implementing a Dynamic array\n",
        "\n",
        "If an element is appended to a list at a time when the underlying array is full, we perform the following steps:\n",
        "1. Allocate a new array B with larger capacity.\n",
        "2. Set $B[i] = A[i]$, for $i = 0, . . . ,n−1$, where $n$ denotes current number of items.\n",
        "3. Set $A = B$, that is, we henceforth use B as the array supporting the list.\n",
        "4. Insert the new element in the new array."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LVju__oFDlml",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "782c59c2-ee1b-4f18-f308-b05a4e5a7201"
      },
      "source": [
        "# Implementing a dynamic array\n",
        "import ctypes\n",
        "class DynamicArray:\n",
        "  ''' A dynamic array class akin to a simplified Python list '''\n",
        "  def __init__(self):\n",
        "    ''' create an empty array '''\n",
        "    self._n = 0                                 # count actual elements\n",
        "    self._capacity = 1                          # default array capacity\n",
        "    self._A = self._make_array(self._capacity)  # low-level array\n",
        "\n",
        "  def __len__(self):\n",
        "    ''' return number of elements stored in the array'''\n",
        "    return self._n\n",
        "  \n",
        "  def __getitem__(self, k):\n",
        "    ''' return element at index k '''\n",
        "    if not 0 <= k < self._n:\n",
        "      raise IndexError('invalid index')\n",
        "    return self._A[k]\n",
        " \n",
        "  def append(self, obj):\n",
        "    ''' Add object to the end of the array'''\n",
        "    if self._n == self._capacity:  # no enough room\n",
        "      self._resize(2*self._capacity) # so double the capacity\n",
        "    self._A[self._n] = obj\n",
        "    self._n += 1\n",
        "\n",
        "  def _resize(self, c):\n",
        "    ''' Resize the internal array to capacity c'''\n",
        "    B = self._make_array(c)       # new (bigger) array\n",
        "    for k in range(self._n):\n",
        "      B[k] = self._A[k]           # copy data from old array into new array\n",
        "    self._A = B                   # use the bigger array\n",
        "    self._capacity = c \n",
        "\n",
        "\n",
        "  def _make_array(self, c):    # nonpublic utility\n",
        "    ''' Return new array with capacity c'''\n",
        "    return (c * ctypes.py_object)()  \n",
        "\n",
        "\n",
        "  def insert(self, k, value):\n",
        "    '''\n",
        "    Insert value at index k, shifting subsequent values rightward\n",
        "    For simplicity, we assume 0 <= k <= n\n",
        "    '''\n",
        "    if not 0 <= k <= self._n:\n",
        "      raise ValueError(\"k must lie between 0 and n.\")\n",
        "      \n",
        "    if self._n == self._capacity:\n",
        "      self._resize(2*self._capacity)\n",
        "    for j in range(self._n, k,-1):  # shift rightmost first\n",
        "      self._A[j] = self._A[j-1]\n",
        "    self._A[k] = value\n",
        "    self._n += 1\n",
        "\n",
        "  def remove(self, value): \n",
        "    '''\n",
        "    Remove first occurrence of value (or raise ValueError)\n",
        "    note: We do not consider shrinking of dynamic array in\n",
        "    this  version\n",
        "    '''\n",
        "    for k in range(self._n):\n",
        "      if self._A[k] == value: # found a match\n",
        "        for j in range(k, self._n-1): # shift others to fill gap\n",
        "          self._A[j] = self._A[j+1]\n",
        "        self._A[self._n-1] = None   # help garbage collection\n",
        "        self._n -= 1 # We have now one less item\n",
        "        return       # exit if match found\n",
        "    raise ValueError('value not found') #only reached if no match\n",
        "\n",
        "  def __str__(self):\n",
        "    '''\n",
        "    Getting a string representation of the array\n",
        "    '''\n",
        "    string = str()\n",
        "    for i in range(0, self._n):\n",
        "      string = string + str(self._A[i]) +', '\n",
        "    return '< ' + string + ' >'\n",
        "\n",
        "A = DynamicArray()\n",
        "A.append(1)\n",
        "A.append(2)\n",
        "A.append(7)\n",
        "print(A[0], A[1], A[2])\n",
        "print(A)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 2 7\n",
            "< 1, 2, 7,  >\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uX4Oahfpsd-X",
        "colab_type": "text"
      },
      "source": [
        "The following code demonstrates that the Python's implementation of the append method exhibits amortized constant-time behaviour. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Lw_OLpH3qt-H",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 123
        },
        "outputId": "fa5a06c4-12f1-4c1d-f31e-e88c87ad8724"
      },
      "source": [
        "from time import time\n",
        "def compute_average(n):\n",
        "  '''\n",
        "  Perform n appends to an empty list and return average time elapsed.\n",
        "  '''\n",
        "  data = []\n",
        "  start = time() # record the start time (in seconds)\n",
        "  for k in range(n):\n",
        "    data.append(None)\n",
        "  end = time()   # record the end time (in seconds)\n",
        "  return (end-start)/n  # compute average time per operation\n",
        "\n",
        "print(\"Average time per operation={}\".format(compute_average(100)))\n",
        "print(\"Average time per operation={}\".format(compute_average(1000)))\n",
        "print(\"Average time per operation={}\".format(compute_average(10000)))\n",
        "print(\"Average time per operation={}\".format(compute_average(100000)))\n",
        "print(\"Average time per operation={}\".format(compute_average(1000000)))\n",
        "print(\"Average time per operation={}\".format(compute_average(100000000)))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Average time per operation=2.789497375488281e-07\n",
            "Average time per operation=1.8143653869628906e-07\n",
            "Average time per operation=8.652210235595703e-08\n",
            "Average time per operation=9.852409362792969e-08\n",
            "Average time per operation=1.3332366943359376e-07\n",
            "Average time per operation=7.863965034484863e-08\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Knj4z8lh-Z0t",
        "colab_type": "text"
      },
      "source": [
        "### Analysing the insert operation in a list\n",
        "\n",
        "- Execute the cell for \"DynamicArrays\" defined above.\n",
        "- Please note the function insert() defined above\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XyR0J51Y-d8Y",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        },
        "outputId": "4714b421-7f64-4aef-ed0f-b1a854232387"
      },
      "source": [
        " # Run the the Dynamic array class above before executing this cell.\n",
        " B = DynamicArray()\n",
        " B.append(1)\n",
        " B.append(5)\n",
        " B.append(7)\n",
        " print(\"Array Length: {}\".format(len(B)))\n",
        " print(B)\n",
        " B.insert(2,10)\n",
        " print(B)\n",
        " print(\"Array Length: {}\".format(len(B)))\n",
        " B.insert(3,-10)\n",
        " print(B)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Array Length: 3\n",
            "< 1, 5, 7,  >\n",
            "< 1, 5, 10, 7,  >\n",
            "Array Length: 4\n",
            "< 1, 5, 10, -10, 7,  >\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PeTmnGVQy5cu",
        "colab_type": "text"
      },
      "source": [
        "Points to be noted:\n",
        "- Inserting element at the end requires minimum time.\n",
        "- Inserting element at the beginning requires maximum time.\n",
        "- Inserting element in the middle takes time which is in betweeen the above two extremes.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ua1Z_2o25nue",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        },
        "outputId": "b4211904-fcad-453e-d68b-699055f72d82"
      },
      "source": [
        "from time import time\n",
        "def compute_average_insert1(n):\n",
        "  '''\n",
        "  Perform n insert operation to an empty list and report average time elapsed.\n",
        "  '''\n",
        "  data = []\n",
        "  start = time()\n",
        "  for k in range(n):\n",
        "    data.insert(0,None)\n",
        "  end = time()\n",
        "  return (end-start)/k\n",
        "\n",
        "def compute_average_insert2(n):\n",
        "  '''\n",
        "  Perform n insert operation to an empty list and report average time elapsed.\n",
        "  '''\n",
        "  data = []\n",
        "  start = time()\n",
        "  for k in range(n):\n",
        "    data.insert(n//2,None)\n",
        "  end = time()\n",
        "  return (end-start)/k\n",
        "\n",
        "def compute_average_insert3(n):\n",
        "  '''\n",
        "  Perform n insert operation to an empty list and report average time elapsed.\n",
        "  '''\n",
        "  data = []\n",
        "  start = time()\n",
        "  for k in range(n):\n",
        "    data.insert(n,None)\n",
        "  end = time()\n",
        "  return (end-start)/k\n",
        "####\n",
        "\n",
        "\n",
        "\n",
        "print(\"Average time per operation={}\".format(compute_average_insert1(100)))\n",
        "print(\"Average time per operation={}\".format(compute_average_insert2(1000)))\n",
        "print(\"Average time per operation={}\".format(compute_average_insert3(10000)))\n",
        "print(\"Average time per operation={}\".format(compute_average_insert1(100000)))\n",
        "print(\"Average time per operation={}\".format(compute_average_insert2(1000000)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Average time per operation=1.8784494111032196e-07\n",
            "Average time per operation=2.2767900346635699e-07\n",
            "Average time per operation=1.5596518910924296e-07\n",
            "Average time per operation=2.853767560884227e-05\n",
            "Average time per operation=6.925985205098975e-05\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "juyQOYs6zNXj",
        "colab_type": "text"
      },
      "source": [
        "### Analysing remove() function\n",
        "\n",
        "- we insert another function called remove() to our DynamicArray class described above.\n",
        "- Its run-time complexity is $\\Omega(n)$\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "z1Xv6n56zQsS",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 87
        },
        "outputId": "5d0a17e5-43f9-4bc4-9e8d-9ef7a34d8c9f"
      },
      "source": [
        "# Run the cell containing DynamicArray class above before executing this cell\n",
        "\n",
        "C = DynamicArray()\n",
        "C.append(1)\n",
        "C.append(5)\n",
        "C.append(7)\n",
        "print(C)\n",
        "print(\"Array Length:{}\".format(len(C)))\n",
        "C.remove(5)\n",
        "print(C)\n",
        "print(\"New Array Length:{}\".format(len(C)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "< 1, 5, 7,  >\n",
            "Array Length:3\n",
            "< 1, 7,  >\n",
            "New Array Length:2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xPkmXMmZRibQ",
        "colab_type": "text"
      },
      "source": [
        "## Using Array-Bases Sequences\n",
        "\n",
        "We will see three examples \n",
        "\n",
        "- Storing High Scores for a game\n",
        "- Sorting a Sequence\n",
        "- Simple Cryptography\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7KSTKkwy-ICY",
        "colab_type": "text"
      },
      "source": [
        "### Storing High Scores for a game\n",
        "\n",
        "- The objective is to store high score entries for a video game.\n",
        "- Each game entry has a name and a score. Corresponding class is `GameEntry`. \n",
        "- To maintain a sequence of high scores, we create another class called `Scoreboard`.\n",
        "- `Scoreboard` can have limited number of entries. A new score only qualifies for the scoreboard if it is strictly higher than the lowest of the high scores in the board. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aRClJKJ-SJ_f",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 283
        },
        "outputId": "9fab5681-d820-471d-ce3f-73bf9073befd"
      },
      "source": [
        "class GameEntry:\n",
        "  '''\n",
        "  Represents one entry of a list of high scores\n",
        "  '''\n",
        "\n",
        "  def __init__(self, name, score):\n",
        "    self._name = name\n",
        "    self._score = score\n",
        "  \n",
        "  def get_name(self):\n",
        "    return self._name\n",
        "  \n",
        "  def get_score(self):\n",
        "    return self._score\n",
        "  \n",
        "  def __str__(self):\n",
        "    return '({0}, {1})'.format(self._name, self._score) \n",
        "\n",
        "\n",
        "class Scoreboard:\n",
        "  '''  Fixed-length sequence of high score in nondecreasing order '''\n",
        "  def __init__(self, capacity=10):\n",
        "    ''' \n",
        "    Initialize scoreboard with given maximum capacity\n",
        "    All entries are initially None\n",
        "    '''\n",
        "    self._board = [None]*capacity   # reserve space for future scores\n",
        "    self._n = 0                     # number of actual entries\n",
        "\n",
        "  def __getitem__(self, k):\n",
        "    ''' return entry at index k'''\n",
        "    return self._board[k]\n",
        "\n",
        "  def __str__(self):\n",
        "    ''' return string representation of the high score list'''\n",
        "    return '\\n'.join(str(self._board[j]) for j in range(self._n))\n",
        "\n",
        "  def add(self, entry):\n",
        "    ''' add new entries to high scores'''\n",
        "    score = entry.get_score()\n",
        "\n",
        "    # Does new entry qualify as a high score?\n",
        "    # answer is yes if board not full or score is higher than the last entry\n",
        "\n",
        "    good = self._n < len(self._board) or score > self._board[-1].get_score()\n",
        "\n",
        "    if good:\n",
        "      if self._n < len(self._board):    # no score drops from list\n",
        "        self._n += 1                    # overall count increases\n",
        "      \n",
        "      # shift lower scores rightward to make room for new entry\n",
        "      j = self._n - 1\n",
        "      while j > 0 and self._board[j-1].get_score() < score:\n",
        "        self._board[j] = self._board[j-1]   # shift entry from j-1 to J\n",
        "        j -= 1                              # and decrement j\n",
        "      self._board[j] = entry              # when done, add new entry\n",
        "\n",
        "\n",
        "S = Scoreboard()\n",
        "S.add(GameEntry('Mike',1105))\n",
        "S.add(GameEntry('Rob',750))\n",
        "S.add(GameEntry('Paul',720))\n",
        "S.add(GameEntry('Anna',660))\n",
        "S.add(GameEntry('Rose',590))\n",
        "S.add(GameEntry('Jack',510))\n",
        "\n",
        "print('Entries on the Scoreboard:\\n', S)\n",
        "\n",
        "S.add(GameEntry('Jill', 740))\n",
        "\n",
        "print('Entries on the Scoreboard:\\n', S)\n",
        "\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Entries on the Scoreboard:\n",
            " (Mike, 1105)\n",
            "(Rob, 750)\n",
            "(Paul, 720)\n",
            "(Anna, 660)\n",
            "(Rose, 590)\n",
            "(Jack, 510)\n",
            "Entries on the Scoreboard:\n",
            " (Mike, 1105)\n",
            "(Rob, 750)\n",
            "(Jill, 740)\n",
            "(Paul, 720)\n",
            "(Anna, 660)\n",
            "(Rose, 590)\n",
            "(Jack, 510)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Dgdh7O4ahB-V",
        "colab_type": "text"
      },
      "source": [
        "### Sorting a sequence\n",
        "- insertion-sort algorithm"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "22Q7E2gShH3E",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 87
        },
        "outputId": "e76f9173-10ba-4eac-ef66-a333654a3c9b"
      },
      "source": [
        "def insertion_sort(A):\n",
        "  ''' sort a list of comparable elements into nondecreasing order'''\n",
        "  for k in range(1, len(A)):        # from 1 to n-1\n",
        "    cur = A[k]                      # current element to be inserted\n",
        "    j = k                           # find correct index j for the current\n",
        "    while j > 0 and A[j-1] > cur:   # element A[j-1] must be after the current\n",
        "      A[j] = A[j-1]\n",
        "      j -= 1\n",
        "    A[j] = cur \n",
        "\n",
        "A = [5, 9, 2, 1, 0, 7, 8, 6]\n",
        "print('Original Sequence:', A)\n",
        "\n",
        "insertion_sort(A)\n",
        "\n",
        "print('Sorted Sequence:', A)\n",
        "\n",
        "B = list('BCDAEHGF')\n",
        "print('Unsorted Sequence: ', B)\n",
        "insertion_sort(B)\n",
        "print('Sorted Sequence: ', B)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Original Sequence: [5, 9, 2, 1, 0, 7, 8, 6]\n",
            "Sorted Sequence: [0, 1, 2, 5, 6, 7, 8, 9]\n",
            "Unsorted Sequence:  ['B', 'C', 'D', 'A', 'E', 'H', 'G', 'F']\n",
            "Sorted Sequence:  ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pcp_MQDIsiKw",
        "colab_type": "text"
      },
      "source": [
        "### Simple Cryptography - Caesar Cipher\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "J31j0a0Osmwi",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "b8a09aaa-4102-49bc-90e6-cf573335d593"
      },
      "source": [
        "class CaesarCipher:\n",
        "  ''' Class for doing encryption and decryption using a Caesar Cipher'''\n",
        "\n",
        "  def __init__(self, shift):\n",
        "    ''' Construct Caesar cipher using given integer shift for rotation'''\n",
        "\n",
        "    encoder = [None] * 26           # temp array for encryption\n",
        "    decoder = [None] * 26           # temp array for decryption\n",
        "    for k in range(26):\n",
        "      encoder[k] = chr((k+shift) % 26 + ord('A'))\n",
        "      decoder[k] = chr((k-shift) % 26 + ord('A'))\n",
        "    self._forward = ''.join(encoder)      # store as string\n",
        "    self._backward = ''.join(decoder)\n",
        "\n",
        "\n",
        "  def encrypt(self, message):\n",
        "    ''' return string representing encrypted message'''\n",
        "    return self._transform(message, self._forward)\n",
        "\n",
        "  def decrypt(self, secret):\n",
        "    return self._transform(secret, self._backward)\n",
        "\n",
        "  def _transform(self, original, code):\n",
        "    ''' Utility to perform transformation based on given code string'''\n",
        "\n",
        "    msg = list(original)\n",
        "    for k in range(len(msg)):\n",
        "      if msg[k].isupper():\n",
        "        j = ord(msg[k]) - ord('A')  # index from 0 to 25\n",
        "        msg[k] = code[j]            # replace this character\n",
        "    return ''.join(msg)\n",
        "\n",
        "if __name__ =='__main__':\n",
        "  cipher = CaesarCipher(3)\n",
        "  message = \"THE EAGLE IS IN PLAY; MEET AT JOE'S\"\n",
        "  coded = cipher.encrypt(message)\n",
        "  print('Secret:', coded)\n",
        "  answer = cipher.decrypt(coded)\n",
        "  print('Message:', answer)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Secret: WKH HDJOH LV LQ SODB; PHHW DW MRH'V\n",
            "Message: THE EAGLE IS IN PLAY; MEET AT JOE'S\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CcuTpXdS9NvF",
        "colab_type": "text"
      },
      "source": [
        "## Multi-dimensional array\n",
        "Follow code demonstrates the correct way of initializing a two-dimensional array"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EG_AkBSL7BA8",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 176
        },
        "outputId": "bb215119-a491-454c-e49b-89ca52211ca3"
      },
      "source": [
        "print('Initializing 2-D array thee wrong way\\n')\n",
        "data = [[0]*3]*3\n",
        "print(data)\n",
        "data[2][0] = 5\n",
        "print(data, end='\\n\\n')\n",
        "\n",
        "print('initializing an array the right way\\n')\n",
        "data2 = [[0]*4 for j in range(3)]\n",
        "print(data2)\n",
        "\n",
        "data2[2][0] = 5\n",
        "data2[0][1] = 2\n",
        "print(data2)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Initializing 2-D array thee wrong way\n",
            "\n",
            "[[0, 0, 0], [0, 0, 0], [0, 0, 0]]\n",
            "[[5, 0, 0], [5, 0, 0], [5, 0, 0]]\n",
            "\n",
            "initializing an array the right way\n",
            "\n",
            "[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]\n",
            "[[0, 2, 0, 0], [0, 0, 0, 0], [5, 0, 0, 0]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3HGlLhLy96Ah",
        "colab_type": "text"
      },
      "source": [
        "### Tic-Tac-Toe Game"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FEiVw5EZ9827",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 123
        },
        "outputId": "693e6a83-097d-4c2d-c6ac-b4e4b7c61399"
      },
      "source": [
        "# Tic-Tac-Toe Game\n",
        "class TicTacToe:\n",
        "  ''' \n",
        "  Management of a Tic-Tac-Toe Game\n",
        "  No strategy\n",
        "  '''\n",
        "  def __init__(self):\n",
        "    ''' start a new game'''\n",
        "    self._board = [ [' '] * 3 for j in range(3) ]\n",
        "    self._player = 'X'\n",
        "\n",
        "  def mark(self, i, j):\n",
        "    ''' Put X or O mark at position (i,j) for next player's turn '''\n",
        "\n",
        "    if not(0 <= i <= 2  and 0 <= j <= 2):\n",
        "      raise ValueError('Invalid board position')\n",
        "    if self._board[i][j] != ' ':\n",
        "      raise ValueError('Board position occupied')\n",
        "    if self.winner() is not None:\n",
        "      raise ValueError('Game is already complete')\n",
        "    self._board[i][j] = self._player\n",
        "\n",
        "    if self._player == 'X':\n",
        "      self._player = 'O'\n",
        "    else:\n",
        "      self._player = 'X'\n",
        "\n",
        "  def _is_win(self, mark):\n",
        "    ''' Check whether the board configuration is a win for a given player'''\n",
        "    board = self._board\n",
        "\n",
        "    return (mark == board[0][0] == board[0][1] == board[0][2] or # row 0 \n",
        "            mark == board[1][0] == board[1][1] == board[1][2] or # row 1 \n",
        "            mark == board[2][0] == board[2][1] == board[2][2] or # row 2 \n",
        "            mark == board[0][0] == board[1][0] == board[2][0] or # column 0 \n",
        "            mark == board[0][1] == board[1][1] == board[2][1] or # column 1 \n",
        "            mark == board[0][2] == board[1][2] == board[2][2] or # column 2 \n",
        "            mark == board[0][0] == board[1][1] == board[2][2] or # diagonal \n",
        "            mark == board[0][2] == board[1][1] == board[2][0])   # rev diag\n",
        "  \n",
        "  def winner(self):\n",
        "    ''' return mark of the winning player, or None to indicate a tie'''\n",
        "    for mark in 'XO':\n",
        "      if self._is_win(mark):\n",
        "        return mark\n",
        "    return None\n",
        "\n",
        "  def __str__(self):\n",
        "    ''' return th estring representation of the current game board'''\n",
        "    rows = ['|'.join(self._board[r]) for r in range(3)]\n",
        "    return '\\n------\\n'.join(rows)\n",
        "\n",
        "\n",
        "game = TicTacToe()\n",
        "\n",
        "# X moves             # O moves\n",
        "game.mark(1,1);     game.mark(0,2)\n",
        "game.mark(2,2);     game.mark(0,0)\n",
        "game.mark(0,1);     game.mark(2,1)\n",
        "game.mark(1,2);     game.mark(1,0)\n",
        "game.mark(2,0); \n",
        "\n",
        "print(game)\n",
        "winner = game.winner()\n",
        "if winner is None:\n",
        "  print('Tie')\n",
        "else:\n",
        "  print(winner, 'wins')\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "O|X|O\n",
            "------\n",
            "O|X|X\n",
            "------\n",
            "X|O|X\n",
            "Tie\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "M-eQ4EBDxW_w",
        "colab_type": "text"
      },
      "source": [
        "# Stacks, Queues and Deques\n",
        "\n",
        "- Stacks\n",
        "- Queues\n",
        "- Double Ended Queues"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MZ-HeMZexfu2",
        "colab_type": "text"
      },
      "source": [
        "## Stacks\n",
        "\n",
        "- Array-based Stack ADT\n",
        "- The following codes shows an implementation of stack using Python List\n",
        "  - We define a new exception type \"Empty\" more suitable in the context of Stack\n",
        "  - We define functions `pop()` and `push()` for adding and removing elements to and from the stack. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Tx6LxByGxkZC",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 176
        },
        "outputId": "457e9ade-c321-4b88-8cd6-8699d7a62969"
      },
      "source": [
        "# define a new type of exception for stack ADT\n",
        "class Empty(Exception):\n",
        "  ''' Error attempting to access an element from an empty container.'''\n",
        "  pass\n",
        "\n",
        "class ArrayStack:\n",
        "  ''' LIFO stack implementation using a Python List as underlying storage'''\n",
        "\n",
        "  def __init__(self):\n",
        "    ''' create an empty stack'''\n",
        "    self._data = []    # nonpublic list instance\n",
        "\n",
        "  def __len__(self):\n",
        "    ''' return the number of elements in a stack'''\n",
        "    return len(self._data)\n",
        "\n",
        "  def is_empty(self):\n",
        "    ''' Return True if the stack is empty'''\n",
        "    return len(self._data) == 0\n",
        "\n",
        "  def push(self, e):\n",
        "    ''' Add element e to the top of the stack'''\n",
        "    self._data.append(e)  # new item stored at end of a list\n",
        "  \n",
        "  def top(self):\n",
        "    ''' \n",
        "    Return the element at the top of the stack\n",
        "    Raise Empty Exception if the stack is empty\n",
        "    '''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Stack is Empty')\n",
        "    return self._data[-1]           # the last item in the list\n",
        "\n",
        "  def pop(self):\n",
        "    ''' \n",
        "    Remove and return the element from the top of the stack \n",
        "    Raise Empty excepion if the stack is empty\n",
        "    '''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Stack is Empty')\n",
        "    return self._data.pop()\n",
        "\n",
        "  def __str__(self):\n",
        "    ''' \n",
        "    A string representation of the stack\n",
        "    An arrow shows the top of the stack\n",
        "    '''\n",
        "    return ''.join(str(self._data)) +'>'\n",
        "\n",
        "################\n",
        "S = ArrayStack()\n",
        "S.push(5)\n",
        "S.push(3)\n",
        "print('Stack Length: ', len(S))\n",
        "print('S: ', S)\n",
        "print('Pop ', S.pop())\n",
        "print('Is stack Empty? ', S.is_empty())\n",
        "print('Pop ', S.pop())\n",
        "print('Is stack Empty? ', S.is_empty())\n",
        "print('S:', S)\n",
        "S.push(7)\n",
        "S.push(9)\n",
        "print('Top Element in Stack: ', S.top())\n",
        "S.push(4)\n",
        "S.push(6)\n",
        "print('S: ', S)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Stack Length:  2\n",
            "S:  [5, 3]>\n",
            "Pop  3\n",
            "Is stack Empty?  False\n",
            "Pop  5\n",
            "Is stack Empty?  True\n",
            "S: []>\n",
            "Top Element in Stack:  9\n",
            "S:  [7, 9, 4, 6]>\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PRICR747NLJI",
        "colab_type": "text"
      },
      "source": [
        "### reversing data using a stack\n",
        "\n",
        "As an example, we use a stack to print lines from a file in reverse order. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CgfzvVclJ-RE",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 123
        },
        "outputId": "b10a5a9d-b7d9-427b-9e8d-42ec33b6835b"
      },
      "source": [
        "# reversing data using a stack\n",
        "def reverse_file(filename):\n",
        "  ''' Overwrite given file with its conent line-by-line reversed'''\n",
        "\n",
        "  S = ArrayStack()\n",
        "  original = open(filename)\n",
        "  for line in original:\n",
        "    S.push(line.rstrip('\\n')) # we will re-insert newlines when writing\n",
        "  original.close()\n",
        "\n",
        "  # Now we overwrite with contents in LIFO order\n",
        "  output = open(filename, 'w') # reopening file overwrites original\n",
        "  while not S.is_empty():\n",
        "    output.write(S.pop() + '\\n') # re-insert newline characters\n",
        "  output.close()\n",
        "\n",
        "###########\n",
        "file = open(\"initial.txt\", 'w')\n",
        "file.write(\"I am going home.\\n\")\n",
        "file.write(\"Today is a holiday.\")\n",
        "file.close()\n",
        "\n",
        "!cat initial.txt\n",
        "print('\\n\\n')\n",
        "reverse_file(\"initial.txt\")\n",
        "!cat initial.txt"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "I am going home.\n",
            "Today is a holiday.\n",
            "\n",
            "\n",
            "Today is a holiday.\n",
            "I am going home.\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aE-aqhREPSSq",
        "colab_type": "text"
      },
      "source": [
        "### Matching parentheses and HTML tages\n",
        "- Algorithm for matching delimiters\n",
        "- Algorithm for matching HTML Tags"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jwsRP3SIMZDO",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 70
        },
        "outputId": "83e1151e-a780-43be-edf5-0df8fee64faf"
      },
      "source": [
        "def is_matched(expr):\n",
        "  ''' Return True if all delimiters are properly matched; False otherwise'''\n",
        "\n",
        "  lefty = '({['               # opening delimiters\n",
        "  righty = ')}]'              # respective closing delimiters\n",
        "  S = ArrayStack()\n",
        "  for c in expr:\n",
        "    if c in lefty:            # push left delimiter on stack\n",
        "      S.push(c)\n",
        "    elif c in righty:\n",
        "      if S.is_empty():\n",
        "        return False          # Nothing to match\n",
        "      if righty.index(c) != lefty.index(S.pop()):\n",
        "        print('Mismatch Parenthesis:', c)\n",
        "        return False          # mismatch\n",
        "  return S.is_empty()         # were all symbols matched\n",
        "\n",
        "\n",
        "##########\n",
        "\n",
        "\n",
        "expr1 = '[(5+x)-(y+z)}'\n",
        "print(is_matched(expr))\n",
        "expr2 = '[(5+x)-(y+z)]'\n",
        "print(is_matched(expr2))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Mismatch Parenthesis: }\n",
            "False\n",
            "True\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PLcwjIOcWRT_",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "87c1710b-35f7-4da2-b1dc-6c3e17cdbdad"
      },
      "source": [
        "def is_matched_html(raw):\n",
        "  ''' return True if all HTML tags are properly match; False otherwise'''\n",
        "  S = ArrayStack()\n",
        "  j = raw.find('<')                 # find first '<' character (if any)\n",
        "  while j != -1:\n",
        "    k = raw.find('>', j+1)          # find next '>' character\n",
        "    if k == -1:\n",
        "      print('Invalid Tag')\n",
        "      return False                  # invalid tag\n",
        "    tag = raw[j+1:k]                # strip away < >\n",
        "    if not tag.startswith('/'):     # this is opening tag\n",
        "      S.push(tag)\n",
        "    else:                           # this is closing tag\n",
        "      if S.is_empty():\n",
        "        print('Stack is empty. Nothing to match with')\n",
        "        return False                # nothing to match with\n",
        "      if tag[1:] != S.pop():\n",
        "        print('Tag Mismatch:', tag)\n",
        "        return False                # mismatched delimiter\n",
        "    j = raw.find('<', k+1)          # find next '<' character (if any)\n",
        "  return S.is_empty()\n",
        "\n",
        "################\n",
        "\n",
        "is_matched_html('''<body>\n",
        "<center>\n",
        "<h1> The Little Boat </h1>\n",
        "</center>\n",
        "<p> The storm tossed the little boat like a cheap sneaker in an\n",
        "old washing machine. The three drunken fishermen were used to\n",
        "such treatment, of course, but not the tree salesman, who even as\n",
        "a stowaway now felt that he had overpaid for the voyage. </p>\n",
        "<ol>\n",
        "<li> Will the salesman die? </li>\n",
        "<li> What color is the boat? </li>\n",
        "<li> And what about Naomi? </li>\n",
        "</ol>\n",
        "</body>''')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dVqfsLnA0tFn",
        "colab_type": "text"
      },
      "source": [
        "## Queues\n",
        "- FIFO principle\n",
        "- New entries are added at the end of the array.\n",
        "- Data is accessed or removed from the front of the array.\n",
        "- A queue implementation with a standard array requires providing two methods:\n",
        "  - enqueue: adding a data\n",
        "  - dequeue: removing a data"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "z2jgibKj1Hwq",
        "colab_type": "text"
      },
      "source": [
        "### A python Queue implementation\n",
        "- It uses an array with circular indexing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5_RcbxaV1SgY",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 283
        },
        "outputId": "dba03166-1279-4fc5-80ad-acbeba3c736e"
      },
      "source": [
        "class ArrayQueue:\n",
        "  ''' \n",
        "  FIFO Queue implementation using a Python List as underlying storage\n",
        "  '''\n",
        "  DEFAULT_CAPACITY = 5       # moderate capacity for all new queues\n",
        "\n",
        "  def __init__(self):\n",
        "    ''' Create an empty queue '''\n",
        "    self._data = [None] * ArrayQueue.DEFAULT_CAPACITY\n",
        "    self._size = 0\n",
        "    self._front = 0\n",
        "\n",
        "\n",
        "  def __len__(self):\n",
        "    ''' return the number of elements in the queue'''\n",
        "    return self._size\n",
        "\n",
        "  def is_empty(self):\n",
        "    ''' Return True if the queue is empty'''\n",
        "    return self._size == 0\n",
        "\n",
        "  def first(self):\n",
        "    ''' \n",
        "    Return (but do not remove) the element at the front of the queue\n",
        "    Raise Empty Exception if the queue is empty.\n",
        "    '''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Queue is Empty')\n",
        "    return self._data[self._front]\n",
        "\n",
        "  \n",
        "  def dequeue(self):\n",
        "    ''' \n",
        "    remove and return the first element of the queue.\n",
        "    raise Empty exception if the queue is empty.\n",
        "    '''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Queue is Empty')\n",
        "    answer = self._data[self._front]\n",
        "    self._data[self._front] = None  # help garbage collection\n",
        "    self._front = (self._front + 1) % len(self._data)  # circular indexing\n",
        "    self._size -= 1  # reduce the queue size\n",
        "\n",
        "    if 0 < self._size < len(self._data) // 4:  # shrink the array size by half \n",
        "      self._resize(len(self._data)//2)         # when queue size 1/4 of the\n",
        "    return answer                              # total array capacity\n",
        "\n",
        "\n",
        "  def enqueue(self, e):\n",
        "    '''Add an element to the back of queue'''\n",
        "    if self._size == len(self._data):\n",
        "      self._resize(2*len(self._data))     # double the array size\n",
        "    avail = (self._front + self._size) % len(self._data)\n",
        "    self._data[avail] = e\n",
        "    self._size += 1\n",
        "\n",
        "\n",
        "  def _resize(self, cap):\n",
        "    ''' resize to a new list of capacity >= len(self)'''\n",
        "    old = self._data\n",
        "    self._data = [None] * cap \n",
        "    walk = self._front\n",
        "    for k in range(self._size):     # only consider existing elements\n",
        "      self._data[k] = old[walk]     # intentionally shift indices\n",
        "      walk = (1+walk) % len(old)    # use old size as modulus\n",
        "    self._front = 0                 # front has been realigned. \n",
        "\n",
        "  def __str__(self):\n",
        "    ''' string representation of the queue'''\n",
        "    return '<'+''.join(str(self._data)) +'<'\n",
        "\n",
        "\n",
        "#################\n",
        "\n",
        "Q = ArrayQueue()\n",
        "Q.enqueue(5)\n",
        "Q.enqueue(7)\n",
        "Q.enqueue(9)\n",
        "Q.enqueue(2)\n",
        "Q.enqueue(6)\n",
        "Q.enqueue(4)\n",
        "Q.enqueue(1)\n",
        "Q.enqueue(0)\n",
        "\n",
        "print('Q: ', Q)\n",
        "print('Queue Length:', len(Q))\n",
        "print('Remove last item: ', Q.dequeue())\n",
        "print('Remove last item: ', Q.dequeue())\n",
        "print('Q: ', Q)\n",
        "print('Queue Length:', len(Q))\n",
        "print('Remove last item: ', Q.dequeue())\n",
        "print('Remove last item: ', Q.dequeue())\n",
        "print('Remove last item: ', Q.dequeue())\n",
        "print('Remove last item: ', Q.dequeue())\n",
        "print('Q: ', Q)\n",
        "print('Queue Length:', len(Q))\n",
        "print('Remove last item: ', Q.dequeue())\n",
        "print('Q: ', Q)\n",
        "print('Queue Length:', len(Q))\n",
        "\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Q:  <[5, 7, 9, 2, 6, 4, 1, 0, None, None]<\n",
            "Queue Length: 8\n",
            "Remove last item:  5\n",
            "Remove last item:  7\n",
            "Q:  <[None, None, 9, 2, 6, 4, 1, 0, None, None]<\n",
            "Queue Length: 6\n",
            "Remove last item:  9\n",
            "Remove last item:  2\n",
            "Remove last item:  6\n",
            "Remove last item:  4\n",
            "Q:  <[None, None, None, None, None, None, 1, 0, None, None]<\n",
            "Queue Length: 2\n",
            "Remove last item:  1\n",
            "Q:  <[0, None, None, None, None]<\n",
            "Queue Length: 1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hXCqrzwvVjkC",
        "colab_type": "text"
      },
      "source": [
        "## Deques\n",
        "- elements can be added both at the front and back of the array.\n",
        "- elements can be removed both from the front and back of the array.\n",
        "- We will make use of `collections.deque` implementation in Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gkKN4QeiVi_D",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        },
        "outputId": "4340d52b-f143-42b6-b232-66d51445f9d0"
      },
      "source": [
        "import collections\n",
        "\n",
        "d = collections.deque('abcdefg')\n",
        "print('Deque:', d)\n",
        "print('Length:', len(d))\n",
        "print('Left end:', d[0])\n",
        "print('Right end:', d[-1])\n",
        "\n",
        "d.remove('c')\n",
        "print('remove(c):', d)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])\n",
            "Length: 7\n",
            "Left end: a\n",
            "Right end: g\n",
            "remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Id1zZvQTWfOP",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        },
        "outputId": "d2254ac9-9dbf-4d7e-b46c-cfd4658d0069"
      },
      "source": [
        "import collections\n",
        "D = collections.deque()\n",
        "D.appendleft(5)\n",
        "D.appendleft(6)\n",
        "D.append(10)\n",
        "D.append(2)\n",
        "D.appendleft(3)\n",
        "D.appendleft(7)\n",
        "print('Deque D: ', D)\n",
        "print('Length: ', len(D))\n",
        "D.rotate(5) #circularly shift rightward k steps\n",
        "print('Deque D: ', D)\n",
        "D.popleft()\n",
        "D.pop()\n",
        "print('Deque D: ', D)\n",
        "print('Length: ', len(D))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Deque D:  deque([7, 3, 6, 5, 10, 2])\n",
            "Length:  6\n",
            "Deque D:  deque([3, 6, 5, 10, 2, 7])\n",
            "Deque D:  deque([6, 5, 10, 2])\n",
            "Length:  4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ThHyNksFNv2N",
        "colab_type": "text"
      },
      "source": [
        "# Linked-List\n",
        "\n",
        "- Singly linked list\n",
        "- Circularly linked list\n",
        "- Doubly Linked List\n",
        "- Positional List ADT\n",
        "- Sorting a Positional List\n",
        "- case Study"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BSG-A2crN88B",
        "colab_type": "text"
      },
      "source": [
        "## Singly Linked List\n",
        "\n",
        "- Elements can be added at the head or the tail end of the list.\n",
        "- Elements can be removed easily from the head.\n",
        "- Deleting tail is complicated and can not be done efficiently in Singly Linked Lists.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sE5pAQ56OAWh",
        "colab_type": "text"
      },
      "source": [
        "### Implementing a stack with a Singly Linked List\n",
        "- Head of the linked-list is used to represent the top of the stack."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xhTh0igJOc95",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 123
        },
        "outputId": "d9179757-dfec-4a75-99cd-bb8389994939"
      },
      "source": [
        "class Empty(Exception):\n",
        "  ''' Error attempting to access an element from an empty container.'''\n",
        "  pass\n",
        "\n",
        "class LinkedStack:\n",
        "  ''' LIFO Stack implementation using a singly linked list for storage'''\n",
        "\n",
        "  #--------------------------- nested _Node Class ------------------------\n",
        "  class _Node:\n",
        "    ''' Lightweight, nonpublic class for storing a singly linked node'''\n",
        "    __slots__ = ['_element', '_next']        # streamline memory usage\n",
        "\n",
        "    def __init__(self, element, next):       # Initialize node's field\n",
        "      self._element = element                # reference to user's element\n",
        "      self._next = next                      # reference to next node\n",
        "  \n",
        "  #-------------------Stack Methods ------------------------------------------\n",
        "\n",
        "  def __init__(self):\n",
        "    ''' Create an empty stack'''\n",
        "    self._head = None         # reference to the head node\n",
        "    self._size = 0\n",
        "\n",
        "  def __len__(self):\n",
        "    ''' return the number of elements in the stack'''\n",
        "    return self._size\n",
        "\n",
        "  def is_empty(self):\n",
        "    ''' Returns True if the stack is empty'''\n",
        "    return self._size == 0\n",
        "\n",
        "  def top(self):\n",
        "    ''' \n",
        "    Return (but do not remove) the element at the top of the stack\n",
        "    Raise Empty Exception if the stack is Empty\n",
        "    '''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Stack is empty')\n",
        "    return self._head._element  # top of the stack is at the head of the list\n",
        "\n",
        "\n",
        "  def push(self, e):\n",
        "    '''Add elements e to the top of the stack'''\n",
        "    self._head = self._Node(e, self._head)  # create and link a new node\n",
        "    self._size += 1\n",
        "\n",
        "  \n",
        "  def pop(self):\n",
        "    '''\n",
        "    Remove and return the element from the top of the stack\n",
        "    Raise Empty exception if the stack is empty\n",
        "    '''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Stack is Empty')\n",
        "    answer = self._head._element\n",
        "    self._head = self._head._next   # Bypass the current node\n",
        "    self._size -= 1\n",
        "    return answer\n",
        "\n",
        "  def __str__(self):\n",
        "    ''' String representation of the stack'''\n",
        "    arr = ''\n",
        "    start = self._head\n",
        "    for i in range(self._size):\n",
        "      arr += str(start._element) +', '\n",
        "      start = start._next\n",
        "\n",
        "    return '<' + arr + ']'\n",
        "\n",
        "\n",
        "\n",
        "###############\n",
        "if __name__ == '__main__':\n",
        "\n",
        "  S = LinkedStack()\n",
        "  S.push(10)\n",
        "  S.push(15)\n",
        "  S.push(3)\n",
        "  S.push(17)\n",
        "  S.push(0)\n",
        "  S.push(2)\n",
        "  print('Stack Length: ', len(S))\n",
        "  print('Stack S: ', S)\n",
        "\n",
        "  print('Pop :', S.pop())\n",
        "  print('Pop :', S.pop())\n",
        "\n",
        "  print('Stack Length: ', len(S))\n",
        "  print('Stack S: ', S)\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Stack Length:  6\n",
            "Stack S:  <2, 0, 17, 3, 15, 10, ]\n",
            "Pop : 2\n",
            "Pop : 0\n",
            "Stack Length:  4\n",
            "Stack S:  <17, 3, 15, 10, ]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jaRaHqxei1Ox",
        "colab_type": "text"
      },
      "source": [
        "### Implementing a Queue with Singly Linked List\n",
        "- Elements are added to the back of the queue\n",
        "- Elements are removed from the front of the queue"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cZWQerxDi51T",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 116
        },
        "outputId": "9bdf452e-f0f3-4bc1-cd48-f21adef513bf"
      },
      "source": [
        "class Empty(Exception):\n",
        "  ''' Error attempting to access an element from an empty container.'''\n",
        "  pass\n",
        "#------------------------------------------------\n",
        "class LinkedQueue:\n",
        "  ''' FIFO Queue implementation using a singly linked list for storage'''\n",
        "\n",
        "  #--------------------- nested _Node Class ------------------\n",
        "  class _Node:\n",
        "    ''' Lightweight, nonpublic class for storing a singly linked node'''\n",
        "    __slots__ = ['_element', '_next']        # streamline memory usage\n",
        "\n",
        "    def __init__(self, element, next):       # Initialize node's field\n",
        "      self._element = element                # reference to user's element\n",
        "      self._next = next                      # reference to next node\n",
        "  \n",
        "  # -------------------Queue Methods-----------------------------------\n",
        "\n",
        "  def __init__(self):\n",
        "    ''' Create an empty queue'''\n",
        "    self._head = None\n",
        "    self._tail = None\n",
        "    self._size = 0            # number of Queue elements\n",
        "\n",
        "  def __len__(self):\n",
        "    ''' Return the number of elements in the Queue'''\n",
        "    return self._size\n",
        "\n",
        "  \n",
        "  def is_empty(self):\n",
        "    ''' Return True if the queue is empty'''\n",
        "    return self._size == 0\n",
        "\n",
        "  def first(self):\n",
        "    '''Return (but do not remove) the element at the front of the queue'''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Queue is Empty')\n",
        "    return self._head._element    # front aligned with head of list\n",
        "\n",
        "  \n",
        "  def dequeue(self):\n",
        "    ''' \n",
        "    Remove and return the first element of the queue (FIFO)\n",
        "    Raise Empty exception if the queue is empty\n",
        "    '''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Queue is empty')\n",
        "    answer = self._head._element\n",
        "    self._head = self._head._next   # now head points to next node\n",
        "    self._size -= 1\n",
        "    if self.is_empty():             # special case as queue is empty\n",
        "      self._tail = None             # removed head had been the tail\n",
        "    return answer\n",
        "\n",
        "  def enqueue(self, e):\n",
        "    ''' Add an element to the back of the queue'''\n",
        "    newest = self._Node(e, None)    # new node will be the new tail node\n",
        "    if self.is_empty():\n",
        "      self._head = newest           # special case: previously empty\n",
        "    else:\n",
        "      self._tail._next = newest\n",
        "    self._tail = newest             #  update reference to tail node\n",
        "    self._size += 1\n",
        "\n",
        "  def __str__(self):\n",
        "    '''String representation of the queue'''\n",
        "    arr = ''\n",
        "    start = self._head\n",
        "    for i in range(self._size):\n",
        "      arr += str(start._element) + ', '\n",
        "      start = start._next\n",
        "    return '<' + arr + '<'\n",
        "\n",
        "\n",
        "####################\n",
        "\n",
        "if __name__ == '__main__':\n",
        "\n",
        "  Q = LinkedQueue()\n",
        "  Q.enqueue(5)\n",
        "  Q.enqueue(7)\n",
        "  Q.enqueue(1)\n",
        "  Q.enqueue(9)\n",
        "  Q.enqueue(3)\n",
        "  print('Queue Length: ', len(Q))\n",
        "  print('Queue: ', Q)\n",
        "\n",
        "  print('Removed: ', Q.dequeue())\n",
        "  print('Removed: ', Q.dequeue())\n",
        "\n",
        "  print('Queue Length: ', len(Q))\n",
        "  print('Queue: ', Q)"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Queue Length:  5\n",
            "Queue:  <5, 7, 1, 9, 3, <\n",
            "Removed:  5\n",
            "Removed:  7\n",
            "Queue Length:  3\n",
            "Queue:  <1, 9, 3, <\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "13HyODm2cZSu",
        "colab_type": "text"
      },
      "source": [
        "### Implementing a Queue with a Circularly Linked List\n",
        "- Only keep a reference to the tail\n",
        "- `_tail.next` points to the head.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "reQ-vJZkcnOA",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 176
        },
        "outputId": "f3e0a033-b237-4bc5-88e2-f544dcc1418a"
      },
      "source": [
        "class Empty(Exception):\n",
        "  ''' Error attempting to access an element from an empty container.'''\n",
        "  pass\n",
        "#---------------------------------------------\n",
        "class CircularQueue:\n",
        "  '''Queue Implementation using circularly linked list for storage'''\n",
        "\n",
        "  #--------------------- nested _Node Class ------------------\n",
        "  class _Node:\n",
        "    ''' Lightweight, nonpublic class for storing a singly linked node'''\n",
        "    __slots__ = ['_element', '_next']        # streamline memory usage\n",
        "\n",
        "    def __init__(self, element, next):       # Initialize node's field\n",
        "      self._element = element                # reference to user's element\n",
        "      self._next = next                      # reference to next node\n",
        "  # -------------------Queue Methods-----------------------------------\n",
        "\n",
        "  def __init__(self):\n",
        "    ''' Create an empty queue'''\n",
        "    self._tail = None         # represents tail of the queue\n",
        "    self._size = 0            # number of Queue elements\n",
        "\n",
        "  def __len__(self):\n",
        "    ''' Return the number of elements in the Queue'''\n",
        "    return self._size\n",
        "\n",
        "  def is_empty(self):\n",
        "    ''' Return True if the queue is empty'''\n",
        "    return self._size == 0\n",
        "\n",
        "  def first(self):\n",
        "    '''Return (but do not remove) the element at the front of the queue'''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Queue is Empty')\n",
        "    head = self._tail._next           # head is next to tail in a circular list\n",
        "    return head._element\n",
        "\n",
        "\n",
        "  def dequeue(self):\n",
        "    ''' \n",
        "    Remove and return the first element of the queue (FIFO)\n",
        "    Raise Empty exception if the queue is empty\n",
        "    '''\n",
        "    if self.is_empty():\n",
        "      raise Empty('Queue is empty')\n",
        "    oldhead = self._tail._next      # element is removed from the head\n",
        "    if self._size == 1:             # removing the only element\n",
        "      self._tail = None             # queue becomes empty\n",
        "    else:\n",
        "      self._tail._next = oldhead._next # bypass old head\n",
        "    self._size -= 1\n",
        "    return oldhead._element         \n",
        "\n",
        "  def enqueue(self, e):\n",
        "    ''' Add an element to the back of the queue'''\n",
        "    newest = self._Node(e, None)    # new node will be the new tail node\n",
        "    if self.is_empty():\n",
        "      newest._next = newest         # initialize circularly\n",
        "    else:\n",
        "      newest._next = self._tail._next # new node points to head\n",
        "      self._tail._next = newest       # old tail points to new node\n",
        "    self._tail = newest             #  new nodes becomes the tail\n",
        "    self._size += 1\n",
        "\n",
        "  def rotate(self):\n",
        "    ''' Rotate front element to the back of the queue'''\n",
        "    if self._size > 0:\n",
        "      self._tail = self._tail._next       # old head becomes the new tail.\n",
        "\n",
        "  def __str__(self):\n",
        "    '''String representation of the queue'''\n",
        "    arr = ''\n",
        "    start = self._tail._next\n",
        "    for i in range(self._size):\n",
        "      arr += str(start._element) + ', '\n",
        "      start = start._next\n",
        "    return '<' + arr + '<'\n",
        "\n",
        "######################\n",
        "\n",
        "if __name__ == '__main__':\n",
        "\n",
        "  Q = CircularQueue()\n",
        "  Q.enqueue(5)\n",
        "  Q.enqueue(7)\n",
        "  Q.enqueue(1)\n",
        "  Q.enqueue(9)\n",
        "  Q.enqueue(3)\n",
        "  print('Queue Length: ', len(Q))\n",
        "  print('Queue: ', Q)\n",
        "\n",
        "  print('Removed: ', Q.dequeue())\n",
        "  print('Removed: ', Q.dequeue())\n",
        "\n",
        "  print('Queue Length: ', len(Q))\n",
        "  print('Queue: ', Q)\n",
        "\n",
        "  print('Rotate : '); Q.rotate();\n",
        "\n",
        "  print('Queue Length: ', len(Q))\n",
        "  print('Queue: ', Q)\n",
        "\n",
        "  "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Queue Length:  5\n",
            "Queue:  <5, 7, 1, 9, 3, <\n",
            "Removed:  5\n",
            "Removed:  7\n",
            "Queue Length:  3\n",
            "Queue:  <1, 9, 3, <\n",
            "Rotate : \n",
            "Queue Length:  3\n",
            "Queue:  <9, 3, 1, <\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "J7YxRvZCTTSJ",
        "colab_type": "text"
      },
      "source": [
        "## Doubly Linked List\n",
        "- Each node maintains reference to the next node and the previous node.\n",
        "- Dummy header and trailer nodes are added for simplifying operations.\n",
        "- Insertion and Deletion at any orbitrary location is possible with $O(1)$ time. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oAmGgxsdTu3G",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Empty(Exception):\n",
        "  ''' Error attempting to access an element from an empty container.'''\n",
        "  pass\n",
        "\n",
        "class _DoublyLinkedBase:\n",
        "  '''A base class providing a doubly linked list representation.'''\n",
        "\n",
        "  #-----------------------------------------------------------------\n",
        "  class _Node:\n",
        "    '''Lightweight, nonpublic class for storing a doubly linked node.'''\n",
        "    __slots__ = '_element', '_prev', '_next'        # streamline memory\n",
        "\n",
        "    def __init__(self, element, prev, next): # initialize node's field\n",
        "      self._element = element       # element to be stored\n",
        "      self._prev = prev             # Previous node reference\n",
        "      self._next = next             # next node reference\n",
        "  #-------------------------------------------------------------------\n",
        "  def __init__(self): \n",
        "    '''Create an empty list.''' \n",
        "    self._header = self._Node(None, None, None) \n",
        "    self._trailer = self._Node(None, None, None)\n",
        "    self._header._next = self._trailer      # trailer is after header\n",
        "    self._trailer._prev = self._header      # header is before trailer\n",
        "    self._size = 0                          # Number of elements \n",
        "\n",
        "  def __len__(self): \n",
        "    '''Return the number of elements in the list.''' \n",
        "    return self._size\n",
        "\n",
        "  def is_empty(self): \n",
        "    '''Return True if list is empty.'''\n",
        "    return self._size == 0\n",
        "\n",
        "  def _insert_between(self, e, predecessor, successor):\n",
        "    '''Add element e between two existing nodes and return new node.'''\n",
        "    newest = self._Node(e, predecessor, successor) # linked to neighbors\n",
        "    predecessor._next = newest \n",
        "    successor._prev = newest\n",
        "    self._size += 1\n",
        "    return newest\n",
        "\n",
        "  def _delete_node(self, node): \n",
        "    '''Delete nonsentinel node from the list and return its element.'''\n",
        "    predecessor = node._prev\n",
        "    successor = node._next \n",
        "    predecessor._next = successor \n",
        "    successor._prev = predecessor\n",
        "    self._size -= 1                 # record deleted element\n",
        "    element = node._element\n",
        "    node._prev = node._next = node._element = None # deprecate node\n",
        "    return element      # return deleted element\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "83gc2HwShVeT",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 116
        },
        "outputId": "58cae551-21ae-4aff-8bef-8a695214e76d"
      },
      "source": [
        "class LinkedDeque(_DoublyLinkedBase):         # note the use of inheritance\n",
        "  '''Double-ended queue implementation based on a doubly linked list.'''\n",
        "\n",
        "  def first(self): \n",
        "    '''Return (but do not remove) the element at the front of the deque.'''\n",
        "    if self.is_empty():\n",
        "      raise Empty(\"Deque is empty\")\n",
        "    return self._header._next._element      # real item just after header\n",
        "\n",
        "  def last(self):\n",
        "    '''Return (but do not remove) the element at the back of the deque.'''\n",
        "    if self.is_empty(): \n",
        "      raise Empty(\"Deque is empty\")\n",
        "    return self._trailer._prev._element     # real item just before trailer\n",
        "\n",
        "  def insert_first(self, e): \n",
        "    '''Add an element to the front of the deque.'''\n",
        "    self._insert_between(e, self._header, self._header._next) # after header\n",
        "\n",
        "  def insert_last(self, e):\n",
        "    '''Add an element to the back of the deque.'''\n",
        "    self._insert_between(e, self._trailer._prev, self._trailer) # before trailer\n",
        "\n",
        "  def delete_first(self):\n",
        "    '''\n",
        "    Remove and return the element from the front of the deque. \n",
        "    Raise Empty exception if the deque is empty.\n",
        "    '''\n",
        "    if self.is_empty(): \n",
        "      raise Empty(\"Deque is empty\")\n",
        "    return self._delete_node(self._header._next) # use inherited method\n",
        "\n",
        "  def delete_last(self):\n",
        "    '''\n",
        "    Remove and return the element from the back of the deque. \n",
        "    Raise Empty exception if the deque is empty.\n",
        "    '''\n",
        "    if self.is_empty(): \n",
        "      raise Empty(\"Deque is empty\") \n",
        "    return self._delete_node(self._trailer._prev)  # use inherited method\n",
        "\n",
        "  def __str__(self):\n",
        "    ''' String representation of deque '''\n",
        "\n",
        "    arr = ''\n",
        "    start = self._header._next\n",
        "    for i in range(self._size):\n",
        "      arr += str(start._element) + ', '\n",
        "      start = start._next\n",
        "    return '<' + arr + '>'\n",
        "\n",
        "\n",
        "##############\n",
        "\n",
        "D = LinkedDeque()\n",
        "D.insert_first(10)\n",
        "D.insert_first(15)\n",
        "D.insert_last(5)\n",
        "D.insert_last(-1)\n",
        "D.insert_first(20)\n",
        "\n",
        "print('Length of Deque: ', len(D))\n",
        "print('D: ', D)\n",
        "\n",
        "print('Delete from head: ', D.delete_first())\n",
        "print('Delete from tail ', D.delete_last())\n",
        "\n",
        "\n",
        "print('Length of Deque: ', len(D))\n",
        "print('D: ', D)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Length of Deque:  5\n",
            "D:  <20, 15, 10, 5, -1, <\n",
            "Delete from head:  20\n",
            "Delete from tail  -1\n",
            "Length of Deque:  3\n",
            "D:  <15, 10, 5, <\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ApaqeLmTf4ek",
        "colab_type": "text"
      },
      "source": [
        "## The Positional List ADT\n",
        "- Provides a generic abstraction for position or location within a linked list\n",
        "- Provides __worst-time__ $O(1)$ time peformance for insertion or deletion at arbitrary locations in the list.\n",
        "- Provides a simpler user interface by encapsulating the underlying implementation details\n",
        "- Inherits `_DoublyLinkedBase` class \n",
        "- A nested `Position` class is defined to provide the above abstraction for position within a list. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Kenkel0Umjf-",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 230
        },
        "outputId": "b4efa96d-dfa7-4203-d905-2d2fb314ead0"
      },
      "source": [
        "#Execute the cell containing _DoublyLinkedBase Class before running this cell\n",
        "\n",
        "class PositionalList(_DoublyLinkedBase):\n",
        "  '''A sequential container of elements allowing positional access'''\n",
        "  \n",
        "  # -------------- nested Position Class ----------------------------\n",
        "  class Position:\n",
        "    '''An abstraction representing the location of a single element'''\n",
        "    \n",
        "    def __init__(self, container, node):\n",
        "      '''Constructor should not be invoked by user'''\n",
        "      self._container = container \n",
        "      self._node = node\n",
        "\n",
        "    def element(self):\n",
        "      '''Return the element stored at this Position'''\n",
        "      return self._node._element\n",
        "\n",
        "    def __eq__(self, other):\n",
        "      '''Return True if other is a Position representing the same location'''\n",
        "      return type(other) is type(self) and other._node is self._node\n",
        "\n",
        "    def __ne__(self, other):\n",
        "      '''Return True if other does not represent the same location'''\n",
        "      return not (self == other)\n",
        "\n",
        "    #-------------------- Utility Methods ---------------------------\n",
        "\n",
        "  def _validate(self, p):\n",
        "    '''Return position's node or raise appropriate error if invalid'''\n",
        "    if not isinstance(p, self.Position):\n",
        "      raise TypeError('p must be proper Position type')\n",
        "    if p._container is not self:\n",
        "      raise ValueError('p does not belong to this container')\n",
        "    if p._node._next is None:   # convention for depricated nodes\n",
        "      raise ValueError('p is no longer valid')\n",
        "    return p._node\n",
        "\n",
        "  def _make_position(self, node):\n",
        "    ''' Return Position instance for a given node(or None if sentinel)'''\n",
        "    if node is self._header or node is self._trailer:\n",
        "      return None             #boundary violation - sentinel node\n",
        "    else:\n",
        "      return self.Position(self, node)    # legitimate position\n",
        "    \n",
        "  # ------------------- Accessors ----------------------------\n",
        "  def first(self):\n",
        "    ''' Return the first Position in the list (or None if list is empty)'''\n",
        "    return self._make_position(self._header._next)\n",
        "\n",
        "  def last(self):\n",
        "    '''Return the last Position in the list (or None if list is empty)'''\n",
        "    return self._make_position(self._trailer._prev)\n",
        "\n",
        "  def before(self, p):\n",
        "    '''Return the Position just before Position p (or None if p is first)'''\n",
        "    node = self._validate(p)\n",
        "    return self._make_position(node._prev)\n",
        "\n",
        "  def after(self, p):\n",
        "    '''Return the Position just after Position p (or None if p is last)'''\n",
        "    node = self._validate(p)\n",
        "    return self._make_position(node._next)\n",
        "\n",
        "  def __iter__(self):\n",
        "    '''Generate a forward iteration of the elements of the list'''\n",
        "    cursor = self.first()\n",
        "    while cursor is not None:\n",
        "      yield cursor.element()\n",
        "      cursor = self.after(cursor)\n",
        "\n",
        "  def __str__(self):\n",
        "    ''' Generates a string representation of the list'''\n",
        "    arr = ''\n",
        "    cursor = self.first()\n",
        "    while cursor is not None:\n",
        "      arr += str(cursor.element()) + ', '\n",
        "      cursor = self.after(cursor)\n",
        "    return '<' + arr + '>'\n",
        "\n",
        "  #-------------- Mutators ------------------------------\n",
        "  # override inherited version to return Position, rather than Node\n",
        "  def _insert_between(self, e, predecessor, successor):\n",
        "    '''Add element between existing nodes and return new Position'''\n",
        "    node = super()._insert_between(e, predecessor, successor)\n",
        "    return self._make_position(node)\n",
        "\n",
        "  def add_first(self, e):\n",
        "    '''Insert element e at the front of the list and return new Position'''\n",
        "    return self._insert_between(e, self._header, self._header._next)\n",
        "\n",
        "  def add_last(self, e):\n",
        "    '''Insert element e at the back of the list and return new Position'''\n",
        "    return self._insert_between(e, self._trailer._prev, self._trailer)\n",
        "\n",
        "  def add_before(self, p, e):\n",
        "    '''Insert element e into list before Position p and return new Position'''\n",
        "    original = self._validate(p)\n",
        "    return self._insert_between(e, original._prev, original)\n",
        "\n",
        "  def add_after(self, p, e):\n",
        "    '''Insert element e into list after Position p and return new Position.'''\n",
        "    original = self._validate(p)\n",
        "    return self._insert_between(e, original, original._next)\n",
        "\n",
        "  def delete(self, p):\n",
        "    '''Remove and return the element at Position p'''\n",
        "    original = self._validate(p)\n",
        "    return self._delete_node(original) # inherited method returns element\n",
        "\n",
        "  def replace(self, p, e):\n",
        "    '''\n",
        "    Replace the element at Position p with e. \n",
        "    Return the element formerly at Position p.\n",
        "    '''\n",
        "    original = self._validate(p)\n",
        "    old_value = original._element\n",
        "    original._element = e\n",
        "    return old_value\n",
        "\n",
        "################################\n",
        "\n",
        "L = PositionalList()\n",
        "L.add_first(5)\n",
        "L.add_last(10)\n",
        "L.add_first(7)\n",
        "L.add_first(-2)\n",
        "L.add_last(3)\n",
        "\n",
        "print('Length of List: ', len(L))\n",
        "print('Positional List: ', L)\n",
        "\n",
        "print('Delete: ', L.delete(L.first()))\n",
        "print('Delete: ', L.delete(L.last()))\n",
        "      \n",
        "print('Length of List: ', len(L))\n",
        "print('Positional List: ', L)\n",
        "\n",
        "L.add_before(L.last(), 11)\n",
        "L.add_after(L.first(), 15)\n",
        "\n",
        "print('Length of List: ', len(L))\n",
        "print('Positional List: ', L)\n",
        "\n",
        "L.replace(L.last(), 1)\n",
        "L.replace(L.after(L.first()), 100) # Second position\n",
        "\n",
        "print('Length of List: ', len(L))\n",
        "print('Positional List: ', L)\n",
        "\n",
        "print(\"Using Iterator to print elements:\")    \n",
        "for e in L:\n",
        "  print(e, end=' ')\n",
        "\n",
        "\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Length of List:  5\n",
            "Positional List:  <-2, 7, 5, 10, 3, >\n",
            "Delete:  -2\n",
            "Delete:  3\n",
            "Length of List:  3\n",
            "Positional List:  <7, 5, 10, >\n",
            "Length of List:  5\n",
            "Positional List:  <7, 15, 5, 11, 10, >\n",
            "Length of List:  5\n",
            "Positional List:  <7, 100, 5, 11, 1, >\n",
            "Using Iterator to print elements:\n",
            "7 100 5 11 1 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5qVGG_xwDWzA",
        "colab_type": "text"
      },
      "source": [
        "### Sorting a Positional List\n",
        "\n",
        "- We apply insertion-sort to a positional list\n",
        "- We need three variables:\n",
        "  - Marker: the rightmost position of the currently sorted portion of a list\n",
        "  - Pivot: The position just after the marker\n",
        "  - Walk: A variable required to move leftward from the marker, as long as  here remains a preceding element with value larger than the pivot’s."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "B0XJmRMXDcJc",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "8b918b03-5b1a-446e-c489-0c37e0d64e62"
      },
      "source": [
        "def insertion_sort(L):\n",
        "  '''Sort PositionalList of comparable elements into nondecreasing order'''\n",
        "\n",
        "  if len(L) > 1:                # otherwise, no need to sort it\n",
        "    marker = L.first()\n",
        "    while marker != L.last():\n",
        "      pivot = L.after(marker)     # next item to the current position\n",
        "      value = pivot.element()\n",
        "      if value > marker.element():   # pivot is already sorted\n",
        "        marker = pivot               # pivot becomes the new marker\n",
        "      else:                          # must relocate the pivote\n",
        "        walk = marker                # find the leftmost item greater than value\n",
        "        while walk != L.first() and L.before(walk).element() > value:\n",
        "          walk = L.before(walk)      # keep moving left\n",
        "        L.delete(pivot)\n",
        "        L.add_before(walk, value)    # reinsert value before walk\n",
        "\n",
        "############\n",
        "print('Original List L: ', L)\n",
        "insertion_sort(L)\n",
        "print('Sorted List:', L)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Original List L:  <7, 100, 5, 11, 1, >\n",
            "Sorted List: <1, 5, 7, 11, 100, >\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZDHconkeg0JT",
        "colab_type": "text"
      },
      "source": [
        "## Case Study: Maintaining Access Frequency\n",
        "- list of favourites\n",
        "  - Sorted list\n",
        "  - Move-to-front heuristic"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0vtCFzXzhCXv",
        "colab_type": "text"
      },
      "source": [
        "### Favourite List ADT\n",
        "- It uses a `PositionalList` as the underlying datastructure\n",
        "- Each element of the `PositionalList` is an instance of class `_Item`, having a value and a count which is incremented everytime the value is accessed.\n",
        "- Provides methods to access and remove items from the list and print top favourites\n",
        "- there are non-public utilities to search for the item and update the list.\n",
        "- The `top(k)` returns a sorted list of favourites. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sR4WMCWog8tP",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 247
        },
        "outputId": "b9a8a61d-ce5e-4759-80c9-76c0a1bf1a21"
      },
      "source": [
        "# Execute the cells containing the PositionList / _DoublyLinkedBase above\n",
        "# Before running this cell\n",
        "\n",
        "class FavoritesList:\n",
        "  '''List of elements ordered from most frequently accessed to least.'''\n",
        "\n",
        "  #------------------- nested _Item Class ------------------------\n",
        "  class _Item:\n",
        "    __slots__ = '_value', '_count'       # streamline memory usage\n",
        "    \n",
        "    def __init__(self, e):\n",
        "      self._value = e                     # user's element\n",
        "      self._count = 0                     # access count initially 0\n",
        "\n",
        "  #----------------- non-public utilities ----------------------------\n",
        "  def _find_position(self, e):\n",
        "    '''Search for element e and return its Position (or None if not found)'''\n",
        "    walk = self._data.first()\n",
        "    while walk is not None and walk.element()._value != e:\n",
        "      walk = self._data.after(walk)  # move forward\n",
        "    return walk\n",
        "\n",
        "  def _move_up(self, p):\n",
        "    '''Move item at Position p earlier in the list based on access count'''\n",
        "    if p != self._data.first(): # otherwise, already at top, can't move up\n",
        "      cnt = p.element()._count\n",
        "      walk = self._data.before(p) # move up\n",
        "      if cnt > walk.element()._count: \n",
        "        while (walk != self._data.first() and \n",
        "               cnt > self._data.before(walk).element()._count):\n",
        "          walk = self._data.before(walk) # keep moving upward\n",
        "        self._data.add_before(walk, self._data.delete(p)) # delete / reinsert\n",
        "\n",
        "\n",
        "  # ----------------- Public Methods --------------------------------\n",
        "  def __init__(self):\n",
        "    ''' Create an empty list of favourites'''\n",
        "    self._data = PositionalList()       # will be a list of _Item instances\n",
        "\n",
        "  def __len__(self):\n",
        "    '''Return the number of entries on the favourite list'''\n",
        "    return len(self._data)\n",
        "\n",
        "  def is_empty(self):\n",
        "    '''Return True if list is empty.'''\n",
        "    return len(self._data == 0)\n",
        "\n",
        "  def access(self, e):\n",
        "    '''Access element e, thereby increasing its access count'''\n",
        "    p = self._find_position(e)  # try to locate the existing element\n",
        "    if p is None:\n",
        "      p = self._data.add_last(self._Item(e))  # if new, place at end\n",
        "    p.element()._count += 1       # increment its access count\n",
        "    self._move_up(p)              # consider moving forward\n",
        "\n",
        "  def remove(self, e):\n",
        "    ''' Remove element e from the list of favourites'''\n",
        "    p = self._find_position(e)    # locate existing element\n",
        "    if p is not None:\n",
        "      self._data.delete(p)        # delete if found\n",
        "\n",
        "  def top(self, k):\n",
        "    '''Generate a sequence of top k elements in terms of access count.'''\n",
        "    if not 1 <= k <= len(self):\n",
        "      raise ValueError('Illegal value for k')\n",
        "    walk = self._data.first()\n",
        "    for j in range(k):\n",
        "      item = walk.element()       # element of list is _Item\n",
        "      yield item._value           # report user's element\n",
        "      walk = self._data.after(walk) # move forward\n",
        "\n",
        "\n",
        "####################\n",
        "\n",
        "F = FavoritesList()\n",
        "F.access('BackStreetBoys')\n",
        "F.access('KatyPerry')\n",
        "F.access('Eminem')\n",
        "F.access('MichaelJackson')\n",
        "F.access('ImagineDragons')\n",
        "F.access('BritneySpears')\n",
        "F.access('BackStreetBoys')\n",
        "F.access('ImagineDragons')\n",
        "F.access('ImagineDragons')\n",
        "F.access('ImagineDragons')\n",
        "F.access('KatyPerry')\n",
        "F.access('Eminem')\n",
        "\n",
        "\n",
        "for k in F.top(5):\n",
        "  print(k)\n",
        "\n",
        "\n",
        "F.access('BritneySpears')\n",
        "F.access('BritneySpears')\n",
        "F.access('BritneySpears')\n",
        "F.access('BritneySpears')\n",
        "F.access('BritneySpears')\n",
        "\n",
        "print('\\nUpdated Favourites \\n')\n",
        "for k in F.top(5):\n",
        "  print(k)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "ImagineDragons\n",
            "BackStreetBoys\n",
            "KatyPerry\n",
            "Eminem\n",
            "MichaelJackson\n",
            "\n",
            "Updated Favourites \n",
            "\n",
            "BritneySpears\n",
            "ImagineDragons\n",
            "BackStreetBoys\n",
            "KatyPerry\n",
            "Eminem\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eS1_1jYei0Uk",
        "colab_type": "text"
      },
      "source": [
        "### Implementing Move-to-Front Heuristic in Python\n",
        "- It is comparatively faster to access elements in the list compared to the previous implementation.\n",
        "- The resulting array is not sorted due to move-to-front heuristic and hence requires additional method to sort it. \n",
        "- this version is implemented by overriding `_move_up()` and `top(k)` methods of the `FavoritesList` class."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tSF22FPPi7hB",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 283
        },
        "outputId": "a826d579-1070-42f4-ba3a-727340e7a6d3"
      },
      "source": [
        "# Run the above three cells first containing the following:\n",
        "# _DoublyLinkedBase\n",
        "# PositionalList\n",
        "# FavoriteList\n",
        "\n",
        "class FavoritesListMTF(FavoritesList):\n",
        "  '''List of elements ordered with move-to-front heuristic'''\n",
        "\n",
        "  \n",
        "  # we override move up to provide move-to-front semantics\n",
        "  def _move_up(self, p):\n",
        "    '''Move accessed item at Position p to front of list.'''\n",
        "    if p != self._data.first():\n",
        "      self._data.add_first(self._data.delete(p))   # delete / reinsert\n",
        "\n",
        "  \n",
        "  # we override top because list is no longer sorted\n",
        "  def top(self, k):\n",
        "    '''Generate sequence of top k elements in terms of access count'''\n",
        "    if not 1 <= k <= len(self):\n",
        "      raise ValueError('Illegal value for k')\n",
        "\n",
        "    # we begin by making a copy of the original list\n",
        "    temp = PositionalList()\n",
        "    for item in self._data:\n",
        "      temp.add_last(item)     # positional lists support iteration\n",
        "\n",
        "    # we repeatedly find, report, and remove element with largest count\n",
        "    for j in range(k):\n",
        "      # find and report next highest from temp\n",
        "      highPos = temp.first()\n",
        "      walk = temp.after(highPos)\n",
        "      while walk is not None:\n",
        "        if walk.element()._count > highPos.element()._count:\n",
        "          highPos = walk\n",
        "        walk = temp.after(walk)\n",
        "      # We have found the element with highest count\n",
        "      yield highPos.element()._value        # report element to user\n",
        "      temp.delete(highPos)                  # remove from temp list\n",
        "\n",
        "\n",
        "\n",
        "  # to support print operations\n",
        "  def __str__(self):\n",
        "    ''' provides a string represention of the list'''\n",
        "    arr = ''\n",
        "    cursor = self._data.first()\n",
        "    while cursor is not None:\n",
        "      arr += str((cursor.element()._value, cursor.element()._count)) + '\\n'\n",
        "      cursor = self._data.after(cursor)\n",
        "    return '<' + arr + '>'\n",
        "\n",
        "\n",
        "#############################\n",
        "\n",
        "M = FavoritesListMTF()\n",
        "M.access('BackStreetBoys')\n",
        "M.access('KatyPerry')\n",
        "M.access('Eminem')\n",
        "M.access('MichaelJackson')\n",
        "M.access('ImagineDragons')\n",
        "M.access('BritneySpears')\n",
        "M.access('BackStreetBoys')\n",
        "M.access('ImagineDragons')\n",
        "M.access('ImagineDragons')\n",
        "M.access('ImagineDragons')\n",
        "M.access('KatyPerry')\n",
        "M.access('Eminem')\n",
        "M.access('BritneySpears')\n",
        "M.access('BritneySpears')\n",
        "M.access('BritneySpears')\n",
        "M.access('BritneySpears')\n",
        "M.access('BritneySpears')\n",
        "M.access('Eminem')\n",
        "M.access('Eminem')\n",
        "M.access('Eminem')\n",
        "\n",
        "print('Length of list M:', len(M))\n",
        "print('List M: ', M)\n",
        "\n",
        "print('\\nTop Favourites:')\n",
        "for k in M.top(5):\n",
        "  print(k)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Length of list M: 6\n",
            "List M:  <('Eminem', 5)\n",
            "('BritneySpears', 6)\n",
            "('KatyPerry', 2)\n",
            "('ImagineDragons', 4)\n",
            "('BackStreetBoys', 2)\n",
            "('MichaelJackson', 1)\n",
            ">\n",
            "\n",
            "Top Favourites:\n",
            "BritneySpears\n",
            "Eminem\n",
            "ImagineDragons\n",
            "KatyPerry\n",
            "BackStreetBoys\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WqmaOwAtOFfV",
        "colab_type": "text"
      },
      "source": [
        "# Trees\n",
        "- A tree abstract base class - Duck typing\n",
        "- A Binary tree abstract base class \n",
        "- Binary tree implementation using Linked list: LinkedBinaryTree\n",
        "- Binary tree implementation using Array-based sequences\n",
        "- General tree implementation using Linked List\n",
        "- Tree traversal algorithms\n",
        "  - To implement traversal algorithms, we need to define `__iter__()` function\n",
        "  - postorder and preorder and breadthfirst traversals are applicable to general trees\n",
        "  - inorder traversal is applicable only to Binary trees"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PmSuPTx08R62",
        "colab_type": "text"
      },
      "source": [
        "## Tree Abstract Base Class\n",
        "- It has a nested `Position` Class\n",
        "- Provides template for several accessor and mutator methods.\n",
        "- provides implementation of several traversal algorithms. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FmoJ-TmpOOeN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Tree:\n",
        "  '''Abstract Base Class representing a tree structure'''\n",
        "\n",
        "  # --------- Nested Position Class -----------\n",
        "  class Position:\n",
        "    '''An abstraction representing the location of a single element'''\n",
        "\n",
        "    def element(self):\n",
        "      '''return the element stored at this position'''\n",
        "      raise NotImplementedError('must be implemented by subclass')\n",
        "    \n",
        "    def __eq__(self, other):\n",
        "      '''Return True if other Position represents the same location'''\n",
        "      raise NotImplementedError('must be implemented by subclass')\n",
        "\n",
        "    def __ne__(self, other):\n",
        "      '''Return True if the other does not represent the same location.'''\n",
        "      return not(self == other)\n",
        "\n",
        "    #------------ Abstract Methods that concrete subclass must support ----\n",
        "\n",
        "  def root(self):\n",
        "    ''' Returns Position representing the tree's root (or None if Empty)'''\n",
        "    raise NotImplementedError('must be implemented by subclass')\n",
        "\n",
        "  def parent(self, p):\n",
        "    ''' Returns Position representing p's parent (or None if Empty)'''\n",
        "    raise NotImplementedError('must be implemented by subclass')\n",
        "\n",
        "  def num_children(self, p):\n",
        "    '''Return the number of children that Position p has.'''\n",
        "    raise NotImplementedError( 'must be implemented by subclass' )\n",
        "\n",
        "  def children(self, p):\n",
        "    '''Return the number of children that Position p has.'''\n",
        "    raise NotImplementedError( 'must be implemented by subclass' )\n",
        "\n",
        "  def __len__(self):\n",
        "    '''Return the total number of elements in the tree.'''\n",
        "    raise NotImplementedError( 'must be implemented by subclass' )\n",
        "\n",
        "    # ---------- concrete methods implemented in this class ----------\n",
        "\n",
        "  def is_root(self, p):\n",
        "    '''Return True if Position p represents the root of the tree.'''\n",
        "    return self.root() == p\n",
        "\n",
        "  def is_leaf(self, p):\n",
        "    '''Return True if Position p does not have any children.'''\n",
        "    return self.num_children(p) == 0\n",
        "\n",
        "  def is_empty(self):\n",
        "    '''Return True if the tree is empty.'''\n",
        "    return len(self) == 0\n",
        "\n",
        "  def depth(self, p):\n",
        "    ''' \n",
        "    Return the number of levels \n",
        "    separating Position p from the root.\n",
        "    '''\n",
        "    if self.is_root(p):\n",
        "      return 0\n",
        "    else:\n",
        "      return 1 + self.depth(self.parent(p))\n",
        "\n",
        "  def _height1(self):\n",
        "    ''' \n",
        "    Return the height of the tree\n",
        "    works but O(n^2) worst-case time\n",
        "    '''\n",
        "    return(max(self.depth(p) \n",
        "      for p in self.positions() if self.is_leaf(p)))\n",
        "\n",
        "  def _height2(self, p):\n",
        "    '''\n",
        "    Return the height of the tree\n",
        "    time is linear in size of sub-tree\n",
        "    '''\n",
        "    if self.is_leaf(p):\n",
        "      return 0\n",
        "    else:\n",
        "      return 1 + max(self._height2(c) for c in self.children(p))\n",
        "\n",
        "  def height(self, p = None):\n",
        "    ''' \n",
        "    Return the height of subtree rooted at Position P\n",
        "    if p is None, return the height of the entire tree.\n",
        "    '''\n",
        "    if p is None:\n",
        "      p = self.root()\n",
        "    return self._height2(p)   # start _height2 recursion\n",
        "\n",
        "  def __iter__(self):\n",
        "    '''Generate an iteration of tree's elements'''\n",
        "    for p in self.positions():    # use same order as positions\n",
        "      yield p.element()           # but yield each element\n",
        "\n",
        "  def preorder(self):\n",
        "    '''Generate a preorder iteration of positions in the tree.'''\n",
        "    if not self.is_empty(): \n",
        "      for p in self._subtree_preorder(self.root()):    # start recursion\n",
        "        yield p\n",
        "\n",
        "  def _subtree_preorder(self, p):\n",
        "    '''Generate a preorder iteration of positions in subtree rooted at p.'''\n",
        "    yield p                 # visit p before its subtrees\n",
        "    for c in self.children(p):    # for each child c\n",
        "      for other in self._subtree_preorder(c): # do preorder of c's subtree\n",
        "        yield other         # yield each element\n",
        "\n",
        "  def positions(self):\n",
        "    '''Generate an iteration of the tree's positions.'''\n",
        "    return self.preorder()        # return entire preorder iteration\n",
        "\n",
        "  def postorder(self):\n",
        "    '''Generate post order iteration of positions in the tree.'''\n",
        "    if not self.is_empty():\n",
        "      for p in self._subtree_postorder(self.root()):  # start recursion\n",
        "        yield p\n",
        "\n",
        "  def _subtree_postorder(self, p):\n",
        "    '''Generate a postorder iteration of positions in subtree rooted at p.'''\n",
        "    for c in self.children(p):        # for each child c\n",
        "      for other in self._subtree_postorder(c):  # do postorder of c's subtree\n",
        "        yield other                             # yield each element\n",
        "    yield p           # then visit p after visiting sub-trees.\n",
        "\n",
        "  def breadthfirst(self):\n",
        "    '''Generate a breadth-first iteration of the positions of the tree.'''\n",
        "    if not self.is_empty():\n",
        "      fringe = LinkedQueue()        # known positions not yet yielded\n",
        "      fringe.enqueue(self.root())   # store in queue starting with root\n",
        "      while not fringe.is_empty():   \n",
        "        p = fringe.dequeue()        # remove from front of the queue\n",
        "        yield p                     # report this position\n",
        "        for c in self.children(p):\n",
        "          fringe.enqueue(c)         # add children to back of queue\n"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IrncmDDnwyId",
        "colab_type": "text"
      },
      "source": [
        "## Binary Tree Abstract Base Class \n",
        "- Each node has at most 2 childs called siblings\n",
        "- Number of nodes at any level $d$ is at most $2^d$.\n",
        "- We define an abstract base class (ABC) that inherits the General Tree class defined above. \n",
        "- It provides additional three methods:\n",
        "  - left child / right child of a given node p.\n",
        "  - siblings of a node p\n",
        "  - children of a node p\n",
        "- Inorder traversal algorithm is applicable only to binary trees\n",
        "- Other traversal algorithms available with `Tree` base class can also be used for traversing Binary trees."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yaW1il92ZsHE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class BinaryTree(Tree):\n",
        "  '''Abstract base class representing a binary tree structure.'''\n",
        "\n",
        "  # -------- additional abstract methods --------------\n",
        "  def left(self, p):\n",
        "    ''' \n",
        "    Return a Position representing p's left child.\n",
        "    Return None if p does not have a left child.\n",
        "    '''\n",
        "    raise NotImplementedError('Must be implemented by subclass')\n",
        "\n",
        "  def right(self, p):\n",
        "    '''\n",
        "    Return a Position representing p's right child. \n",
        "    Return None if p does not have a right child\n",
        "    '''\n",
        "    raise NotImplementedError('Must be implemented by subclass')\n",
        "\n",
        "  # ---------- concrete methods implemented in this class ----------\n",
        "\n",
        "  def sibling(self, p):\n",
        "    '''Return a Position representing p's sibling (or None if no sibling).'''\n",
        "    parent = self.parent(p)\n",
        "    if parent is None:            # p must be the root\n",
        "      return None                 # root has no sibling\n",
        "    else:\n",
        "      if p == self.left(parent):\n",
        "        return self.right(parent)   # possibly None\n",
        "      else:\n",
        "        return self.left(parent)    # possibly None\n",
        "\n",
        "  \n",
        "  def children(self, p):\n",
        "    ''' Generate an iteration of Positions representing p's children'''\n",
        "    if self.left(p) is not None:\n",
        "      yield self.left(p)\n",
        "    if self.right(p) is not None:\n",
        "      yield self.right(p)\n",
        "\n",
        "  def inorder(self):  # inorder traversal is applicable only to Binary trees\n",
        "    '''Generate an inorder iteration of positions in the tree.'''\n",
        "    for p in self._subtree_inorder(self.root()):\n",
        "      yield p \n",
        "\n",
        "  def _subtree_inorder(self, p):\n",
        "    '''Generate an inorder iteration of positions in subtree rooted at p.'''\n",
        "    if self.left(p) is not None:    # if left child exists, traverse its subtree\n",
        "      for other in self._subtree_inorder(self.left(p)):\n",
        "        yield other\n",
        "    yield p                 # visit p between its subtrees\n",
        "    if self.right(p) is not None:   # if right child exists, traverse its subtree\n",
        "      for other in self._subtree_inorder(self.right(p)):\n",
        "        yield other\n",
        "\n",
        "  # override inherited version to make inorder the default\n",
        "  def positions(self):\n",
        "    '''Generate iteration of the tree's positions.'''\n",
        "    return self.inorder()       # make inorder the default traversal algorithm\n",
        "\n"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VuPCSWGYUlQP",
        "colab_type": "text"
      },
      "source": [
        "## Python implementation of a Linked Binary Tree Structure\n",
        "\n",
        "- Nested `_Node` class definition having four items - 3 node references and 1 element.\n",
        "- Nested `Position` class is defined here\n",
        "- utility to wrap and unwrap node\n",
        "- Each node can have at most two children\n",
        "\n",
        " \n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "donyIcXbwZTl",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 683
        },
        "outputId": "32ac147e-364f-4d8f-8498-21b9c52ceba4"
      },
      "source": [
        "#from IPython.core.debugger import set_trace\n",
        "\n",
        "# Linked Binary tree\n",
        "class LinkedBinaryTree(BinaryTree):\n",
        "  '''Linked representation of a binary tree structure.'''\n",
        "\n",
        "  class _Node:\n",
        "    __slots__='_element', '_parent','_left', '_right'\n",
        "    def __init__(self, element, parent=None, left=None, right=None):\n",
        "      self._element = element\n",
        "      self._parent = parent\n",
        "      self._left = left\n",
        "      self._right = right\n",
        "\n",
        "  class Position(BinaryTree.Position):\n",
        "    '''An abstraction representing the location of a single element.'''\n",
        "\n",
        "    def __init__(self, container, node):\n",
        "      '''Constructor should not be invoked by user.'''\n",
        "      self._container = container\n",
        "      self._node = node\n",
        "\n",
        "    def element(self):\n",
        "      '''Return the element stored at this position.'''\n",
        "      return self._node._element\n",
        "\n",
        "    def __eq__(self, other):\n",
        "      '''Return True if other is a position representing the same location.'''\n",
        "      return type(other) is type(self) and other._node is self._node\n",
        "\n",
        "  # ---------- hidden utility functions for LinkedBinary Tree ----\n",
        "  def _validate(self, p):\n",
        "    '''Return associated node, if position is valid.'''\n",
        "    if not isinstance(p, self.Position):\n",
        "      raise TypeError('p must be proper Position type')\n",
        "    if p._container is not self:\n",
        "      raise ValueError('p does not belong to this container')\n",
        "    if p._node._parent is p._node:  # convention for deprecated nodes\n",
        "      raise ValueError('p is no longer valid')\n",
        "    return p._node\n",
        "\n",
        "  def _make_position(self, node):\n",
        "    '''Return Position instance for a given node (or None if no node)'''\n",
        "    return self.Position(self, node) if node is not None else None\n",
        "\n",
        "  #-------- binary tree constructor -------------------------------\n",
        "  def __init__(self):\n",
        "    '''Create an initially empty binary tree'''\n",
        "    self._root = None\n",
        "    self._size = 0\n",
        "\n",
        "  # ----------- Public Accessors ------------------------------\n",
        "  def __len__(self):\n",
        "    '''Return the total number of elements in the tree.'''\n",
        "    return self._size\n",
        "\n",
        "  def root(self):\n",
        "    '''Return the root Position of the tree (or None if tree is empty).'''\n",
        "    return self._make_position(self._root)\n",
        "\n",
        "  def parent(self, p):\n",
        "    '''return the position P's parent (or None if p is root)'''\n",
        "    node = self._validate(p)\n",
        "    return self._make_position(node._parent)\n",
        "\n",
        "  def left(self, p):\n",
        "    '''Return the Position P's left child (or None if no left child).'''\n",
        "    node = self._validate(p)\n",
        "    return self._make_position(node._left)\n",
        "\n",
        "  def right(self, p):\n",
        "    '''Return the Position P's right child (or None if no right child).'''\n",
        "    node = self._validate(p)\n",
        "    return self._make_position(node._right)\n",
        "\n",
        "  def num_children(self, p):\n",
        "    '''Return the number of children of Position P.'''\n",
        "    node = self._validate(p)\n",
        "    count = 0\n",
        "    if node._left is not None:      # left child exists\n",
        "      count += 1\n",
        "    if node._right is not None:     # right child exists\n",
        "      count += 1\n",
        "    return count\n",
        "\n",
        "  def _print_children(self, p, arr):\n",
        "    if p is not None:\n",
        "      arr += str(p.element())+': '\n",
        "      if self.num_children(p) > 0:\n",
        "        for c in self.children(p):\n",
        "          arr += str(c.element()) + '\\t'\n",
        "        arr += '\\n'\n",
        "        for c in self.children(p):\n",
        "          arr = self._print_children(c, arr)\n",
        "      arr += '\\n'\n",
        "    return arr\n",
        "      \n",
        "  def __str__(self):\n",
        "    ''' Provide a string representation of the tree'''\n",
        "    \n",
        "    start = self.root()  \n",
        "    arr = ''\n",
        "    arr = self._print_children(start, arr)\n",
        "    return arr\n",
        "\n",
        "  # ----------- NonPublic tree update Methods --------------------------------------- \n",
        "  def _add_root(self, e):\n",
        "    '''\n",
        "    Place element e at the root of an empty tree and return new Position.\n",
        "    Raise ValueError if tree nonempty.\n",
        "    '''\n",
        "    if self._root is not None:  raise ValueError('Root Exists.')\n",
        "    self._size = 1\n",
        "    self._root = self._Node(e)\n",
        "    return self._make_position(self._root)\n",
        "\n",
        "  def _add_left(self, p, e):\n",
        "    '''\n",
        "    Create a new left child for Position P, storing element e.\n",
        "    Return the position of a new node.\n",
        "    Raise ValueError if Position p is invalid or p already has a left child.\n",
        "    '''\n",
        "    node = self._validate(p)\n",
        "    if node._left is not None: raise ValueError('Left child exists')\n",
        "    self._size += 1\n",
        "    node._left = self._Node(e, node) # node is its parent \n",
        "    return self._make_position(node._left)\n",
        "\n",
        "  def _add_right(self, p, e):\n",
        "    '''\n",
        "    Create a new right child for Position p, storing element e.\n",
        "    Return the position of new node.\n",
        "    Raise ValueError if Position p is invalid or p already has a right child.\n",
        "    '''\n",
        "    node = self._validate(p)\n",
        "    if node._right is not None: raise ValueError('Right Child Exists')\n",
        "    self._size += 1\n",
        "    node._right = self._Node(e, node)  # node is its parent\n",
        "    return self._make_position(node._right)\n",
        "\n",
        "  def _replace(self, p, e):\n",
        "    ''' replace the element at position P with e and return the old element.'''\n",
        "    node = self._validate(p)\n",
        "    old = node._element\n",
        "    node._element = e\n",
        "    return old\n",
        "\n",
        "  def _delete(self, p):\n",
        "    '''\n",
        "    Delete the node at Position p, and replace it with its child, if any.\n",
        "    Return the element that had been stored at Position p.\n",
        "    Raise ValueError if Position p is invalid or p has two children.\n",
        "    '''\n",
        "    node = self._validate(p)\n",
        "    if self.num_children(p) == 2: raise ValueError('p has two children')\n",
        "    child = node._left if node._left else node._right\n",
        "    if child is not None:\n",
        "      child._parent = node._parent   # child's grandparent becomes parent\n",
        "    if node is self._root: \n",
        "      self._root = child        # child becomes root if its parent is deleted\n",
        "    else:\n",
        "      parent = node._parent\n",
        "      if node is parent._left:\n",
        "        parent._left = child\n",
        "      else:\n",
        "        parent._right = child\n",
        "    self._size -= 1\n",
        "    node._parent = node             # convention for deprecated node\n",
        "    return node._element\n",
        "\n",
        "  def _attach(self, p, t1, t2):\n",
        "    '''Attach trees t1 and t2 as left and right subtrees of external p.'''\n",
        "\n",
        "    node = self._validate(p)\n",
        "\n",
        "    if not self.is_leaf(p): raise ValueError('position must be leaf')\n",
        "    if not type(self) is type(t1) is type(t2): # all 3 tree must be same type\n",
        "      raise TypeError('Tree types must match')\n",
        "    self._size += len(t1) + len(t2)\n",
        "\n",
        "    if not t1.is_empty():  # attach t1 as left subtree of node\n",
        "      t1._root._parent = node\n",
        "      node._left = t1._root\n",
        "      t1._root = None       # set t1 instance to empty\n",
        "      t1.size = 0\n",
        "    if not t2.is_empty():   # attach t2 as right subtree of node\n",
        "      t2._root._parent = node\n",
        "      node._right = t2._root\n",
        "      t2._root = None       # set t2 instance to empty\n",
        "      t2._size = 0\n",
        "\n",
        "############\n",
        "\n",
        "P = LinkedBinaryTree()\n",
        "P._add_root('Providence')\n",
        "P._add_left(P.root(), 'Chicago')\n",
        "P._add_right(P.root(), 'Seattle')\n",
        "P._add_left(P.left(P.root()), 'Baltimore')\n",
        "P._add_right(P.left(P.root()), 'New York')\n",
        "print(P)\n",
        "print ('\\n------------------------------------\\n')\n",
        "\n",
        "Q = LinkedBinaryTree()\n",
        "Q._add_root('-')\n",
        "Q._add_left(Q.root(),'/')\n",
        "Q._add_right(Q.root(),'+')\n",
        "Q._add_left(Q.left(Q.root()), 'X')\n",
        "Q._add_right(Q.left(Q.root()), '+')\n",
        "\n",
        "Q._add_left(Q.right(Q.root()), 'X')\n",
        "Q._add_right(Q.right(Q.root()),6)\n",
        "\n",
        "Q._add_left(Q.left(Q.left(Q.root())), '+')\n",
        "Q._add_right(Q.left(Q.left(Q.root())), '3')\n",
        "Q._add_left(Q.left(Q.left(Q.left(Q.root()))), '3')\n",
        "Q._add_right(Q.left(Q.left(Q.left(Q.root()))), '1')\n",
        "\n",
        "Q._add_left(Q.right(Q.left(Q.root())), '-')\n",
        "Q._add_right(Q.right(Q.left(Q.root())), '2')\n",
        "Q._add_left(Q.left(Q.right(Q.left(Q.root()))), '9')\n",
        "Q._add_right(Q.left(Q.right(Q.left(Q.root()))), '5')\n",
        "\n",
        "Q._add_left(Q.left(Q.right(Q.root())), '3')\n",
        "Q._add_right(Q.left(Q.right(Q.root())), '-')\n",
        "\n",
        "Q._add_left(Q.right(Q.left(Q.right(Q.root()))), '7')\n",
        "Q._add_right(Q.right(Q.left(Q.right(Q.root()))), '4')\n",
        "\n",
        "print(Q)\n",
        "\n",
        "\n"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Providence: Chicago\tSeattle\t\n",
            "Chicago: Baltimore\tNew York\t\n",
            "Baltimore: \n",
            "New York: \n",
            "\n",
            "Seattle: \n",
            "\n",
            "\n",
            "\n",
            "------------------------------------\n",
            "\n",
            "-: /\t+\t\n",
            "/: X\t+\t\n",
            "X: +\t3\t\n",
            "+: 3\t1\t\n",
            "3: \n",
            "1: \n",
            "\n",
            "3: \n",
            "\n",
            "+: -\t2\t\n",
            "-: 9\t5\t\n",
            "9: \n",
            "5: \n",
            "\n",
            "2: \n",
            "\n",
            "\n",
            "+: X\t6\t\n",
            "X: 3\t-\t\n",
            "3: \n",
            "-: 7\t4\t\n",
            "7: \n",
            "4: \n",
            "\n",
            "\n",
            "6: \n",
            "\n",
            "\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kCekoFlV2WJu",
        "colab_type": "text"
      },
      "source": [
        "## Python Implementation of a general Linked Tree Implementation \n",
        "- Each node can have any number of child nodes.\n",
        "- Child nodes are stored in a python list\n",
        "- Each node stores the following items:\n",
        "  - element itself\n",
        "  - reference to its parent\n",
        "  - an array containing references to child nodes\n",
        "  - number of child nodes in an array\n",
        "- We demonstrate various traversal algorithms for this general tree.\n",
        "- The `delete()` function is not tested yet. \n",
        "- Application: \n",
        "  - Printing table of contents\n",
        "    - with indent\n",
        "    - with labels\n",
        "    - with parenthesis - parenthetic representation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BLylQKNdN1v9",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "539b3598-cf17-4d87-b7af-fab7c3b1be4f"
      },
      "source": [
        "# from IPython.core.debugger import set_trace\n",
        "# This is my own implementation. It may have errors. \n",
        "# Use it at your own risk.\n",
        "\n",
        "class LinkedTree(Tree):\n",
        "  '''Linked representation of General Tree Structure.'''\n",
        "\n",
        "  class _Node:\n",
        "    __slots__='_element', '_parent','_children', '_noc'\n",
        "    def __init__(self, element, parent=None):\n",
        "      self._element = element\n",
        "      self._parent = parent\n",
        "      self._children = []\n",
        "      self._noc = 0 # number of children\n",
        "\n",
        "  class Position(Tree.Position):\n",
        "    '''An abstraction representing the location of a single element.'''\n",
        "\n",
        "    def __init__(self, container, node):\n",
        "      '''Constructor should not be invoked by user.'''\n",
        "      self._container = container\n",
        "      self._node = node\n",
        "\n",
        "    def element(self):\n",
        "      '''Return the element stored at this position.'''\n",
        "      return self._node._element\n",
        "\n",
        "    def __eq__(self, other):\n",
        "      '''Return True if other is a position representing the same location.'''\n",
        "      return type(other) is type(self) and other._node is self._node\n",
        "\n",
        "  # ---------- hidden utility functions for LinkedTree ----\n",
        "  def _validate(self, p):\n",
        "    '''Return associated node, if position is valid.'''\n",
        "    if not isinstance(p, self.Position):\n",
        "      raise TypeError('p must be proper Position type')\n",
        "    if p._container is not self:\n",
        "      raise ValueError('p does not belong to this container')\n",
        "    if p._node._parent is p._node:  # convention for deprecated nodes\n",
        "      raise ValueError('p is no longer valid')\n",
        "    return p._node\n",
        "\n",
        "  def _make_position(self, node):\n",
        "    '''Return Position instance for a given node (or None if no node)'''\n",
        "    return self.Position(self, node) if node is not None else None\n",
        "\n",
        "  #-------- Linked tree constructor -------------------------------\n",
        "  def __init__(self):\n",
        "    '''Create an initially empty binary tree'''\n",
        "    self._root = None\n",
        "    self._size = 0\n",
        "\n",
        "  # ----------- Public Accessors ------------------------------\n",
        "  def __len__(self):\n",
        "    '''Return the total number of elements in the tree.'''\n",
        "    return self._size\n",
        "\n",
        "  def root(self):\n",
        "    '''Return the root Position of the tree (or None if tree is empty).'''\n",
        "    return self._make_position(self._root)\n",
        "\n",
        "  def parent(self, p):\n",
        "    '''return the position P's parent (or None if p is root)'''\n",
        "    node = self._validate(p)\n",
        "    return self._make_position(node._parent)\n",
        "\n",
        "  def children(self, p):\n",
        "    ''' Generate an iteration of Positions representing p's children'''\n",
        "    node = self._validate(p)\n",
        "    for i in range(node._noc):\n",
        "      if node._children[i] is not None:\n",
        "        yield self._make_position(node._children[i])\n",
        "\n",
        "  def num_children(self, p):\n",
        "    '''Return the number of children of Position P.'''\n",
        "    node = self._validate(p)\n",
        "    return node._noc\n",
        "\n",
        "  # ----- Nonpublic tree update methods --------------------\n",
        "  def _add_root(self, e):\n",
        "    '''\n",
        "    Place element e at the root of an empty tree and return new Position.\n",
        "    Raise ValueError if tree nonempty.\n",
        "    '''\n",
        "    if self._root is not None:  raise ValueError('Root Exists.')\n",
        "    self._size = 1\n",
        "    self._root = self._Node(e)\n",
        "    return self._make_position(self._root)\n",
        "\n",
        "  def _add_child(self, p, e):\n",
        "    '''\n",
        "    Create a new left child for Position P, storing element e.\n",
        "    Return the position of a new node.\n",
        "    Raise ValueError if Position p is invalid or p already has a left child.\n",
        "    '''\n",
        "    node = self._validate(p)\n",
        "    child = self._Node(e, node)   # create a new child with node as its parent\n",
        "    node._children.append(child) # add child to the list with \n",
        "    self._size += 1\n",
        "    node._noc += 1\n",
        "    return self._make_position(child) # return current child position\n",
        "                                              \n",
        "  def _replace(self, p, e):\n",
        "    ''' replace the element at position P with e and return the old element.'''\n",
        "    node = self._validate(p)\n",
        "    old = node._element\n",
        "    node._element = e\n",
        "    return old\n",
        "  \n",
        "  def _delete(self, p):\n",
        "    '''\n",
        "    Delete the node at Position p, and replace it with its child, if any.\n",
        "    Return the element that had been stored at Position p.\n",
        "    Raise ValueError if Position p is invalid or p has two children.\n",
        "    *** NOT TEST YET *****\n",
        "    '''\n",
        "    node = self._validate(p)\n",
        "\n",
        "    if node._noc > 1:\n",
        "      raise ValueError('p has more than 1 child. Node can not be deleted')\n",
        "\n",
        "    if node is self._root:  # if we are deleting root node\n",
        "      for i in range(node._noc):\n",
        "        child = node._children[i]\n",
        "        if child is not None:\n",
        "          self._root = child\n",
        "    else:             # if not a root node\n",
        "      for i in range(node._noc):\n",
        "        child = node._children[i]\n",
        "        if child is not None:\n",
        "          child._parent = node._parent # child's grandparent becomes parent\n",
        "    self._size -= 1\n",
        "    node._parent._noc -= 1  # decrease the number of childen for the parent\n",
        "    node._parent = node  # convention for deprecated node\n",
        "    return node._element\n",
        "\n",
        "  def preorder_indent(self, p, d):\n",
        "    '''Print preorder representation of subtree T rooted a p at depth d.'''\n",
        "    print(2*d*' '+str(p.element()))\n",
        "    if not self.is_leaf(p):\n",
        "        for c in self.children(p):\n",
        "          self.preorder_indent(c, d+1)\n",
        "\n",
        "  def print_tree_with_indent(self):\n",
        "    p = self.root()\n",
        "    d = 0\n",
        "    #set_trace()\n",
        "    self.preorder_indent(p, d)\n",
        "\n",
        "  def preorder_label(self, p, d, path):\n",
        "    '''Print a labeled representation of subtree T rooted at p at depth d.'''\n",
        "    label='.'.join(str(j+1) for j in path) # displayed labels are one-indexed\n",
        "    print(2*d*' '+label, p.element())\n",
        "    path.append(0)     # path entries are zero-indexed\n",
        "    for c in self.children(p):\n",
        "      self.preorder_label(c, d+1, path)  # child depth is d+1\n",
        "      path[-1] += 1\n",
        "    path.pop()\n",
        "\n",
        "  def print_tree_with_labels(self):\n",
        "    ''' Print tree with Labels.'''\n",
        "    p = self.root()\n",
        "    d = 0\n",
        "    path = []\n",
        "    self.preorder_label(p, d,path)\n",
        "\n",
        "  def parenthesize(self, p):\n",
        "    '''Print parenthesized representation of subtree of T rooted at p.'''\n",
        "    print(p.element(), end='')  # use of end avoids trailing newline\n",
        "    if not self.is_leaf(p):\n",
        "      first_time = True\n",
        "      for c in self.children(p):\n",
        "        sep = ' (' if first_time else ', '  # determine proper separator\n",
        "        print(sep, end='')\n",
        "        first_time = False    # any future passes will not be the first\n",
        "        self.parenthesize(c)       # recur on child\n",
        "      print(')', end='')      # include closing parenthesis\n",
        "\n",
        "  def print_tree_with_parenthesis(self):\n",
        "    '''Generate parenthetic representation of the tree.'''\n",
        "    self.parenthesize(self.root())\n",
        "\n",
        "\n",
        "#################\n",
        "\n",
        "A = LinkedTree()\n",
        "A._add_root('Paper')\n",
        "A._add_child(A.root(),'Title')\n",
        "A._add_child(A.root(),'Abstract')\n",
        "A._add_child(A.root(),'Section1')\n",
        "A._add_child(A.root(),'Section2')\n",
        "A._add_child(A.root(),'Conclusion')\n",
        "print('Root has {} children'.format(A.num_children(A.root())))\n",
        "L1 =[]\n",
        "for child in A.children(A.root()):\n",
        "  L1.append(child)\n",
        "\n",
        "A._add_child(L1[2], 'Sec1.1')\n",
        "A._add_child(L1[2], 'Sec1.2')\n",
        "A._add_child(L1[2], 'Sec1.3')\n",
        "\n",
        "print('L1[2] has {} children'.format(A.num_children(L1[2])))\n",
        "\n",
        "A._add_child(L1[3], 'Sec2.1')\n",
        "A._add_child(L1[3], 'Sec2.2')\n",
        "A._add_child(L1[3], 'Sec2.3')\n",
        "\n",
        "# Prints the labels with indent\n",
        "A.print_tree_with_indent()\n",
        "\n",
        "print(\"-------------------\")\n",
        "\n",
        "for p in A.preorder():   # preorder traversal\n",
        "  print(p.element())\n",
        "print(\"-------------------\")\n",
        "\n",
        "for p in A.postorder():   # postorder traversal\n",
        "  print(p.element())\n",
        "print(\"-------------------\")\n",
        "\n",
        "# Execute the cell containing LinkedQueue for this\n",
        "for p in A.breadthfirst():    # breadthfirst traversal\n",
        "  print(p.element())\n",
        "\n",
        "print(\"-------------------\")\n",
        "A.print_tree_with_labels()\n",
        "\n",
        "print(\"-------------------\")\n",
        "A.print_tree_with_parenthesis()\n",
        "\n"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Root has 5 children\n",
            "L1[2] has 3 children\n",
            "Paper\n",
            "  Title\n",
            "  Abstract\n",
            "  Section1\n",
            "    Sec1.1\n",
            "    Sec1.2\n",
            "    Sec1.3\n",
            "  Section2\n",
            "    Sec2.1\n",
            "    Sec2.2\n",
            "    Sec2.3\n",
            "  Conclusion\n",
            "-------------------\n",
            "Paper\n",
            "Title\n",
            "Abstract\n",
            "Section1\n",
            "Sec1.1\n",
            "Sec1.2\n",
            "Sec1.3\n",
            "Section2\n",
            "Sec2.1\n",
            "Sec2.2\n",
            "Sec2.3\n",
            "Conclusion\n",
            "-------------------\n",
            "Title\n",
            "Abstract\n",
            "Sec1.1\n",
            "Sec1.2\n",
            "Sec1.3\n",
            "Section1\n",
            "Sec2.1\n",
            "Sec2.2\n",
            "Sec2.3\n",
            "Section2\n",
            "Conclusion\n",
            "Paper\n",
            "-------------------\n",
            "Paper\n",
            "Title\n",
            "Abstract\n",
            "Section1\n",
            "Section2\n",
            "Conclusion\n",
            "Sec1.1\n",
            "Sec1.2\n",
            "Sec1.3\n",
            "Sec2.1\n",
            "Sec2.2\n",
            "Sec2.3\n",
            "-------------------\n",
            " Paper\n",
            "  1 Title\n",
            "  2 Abstract\n",
            "  3 Section1\n",
            "    3.1 Sec1.1\n",
            "    3.2 Sec1.2\n",
            "    3.3 Sec1.3\n",
            "  4 Section2\n",
            "    4.1 Sec2.1\n",
            "    4.2 Sec2.2\n",
            "    4.3 Sec2.3\n",
            "  5 Conclusion\n",
            "-------------------\n",
            "Paper (Title, Abstract, Section1 (Sec1.1, Sec1.2, Sec1.3), Section2 (Sec2.1, Sec2.2, Sec2.3), Conclusion)"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1Ag258CfKFph",
        "colab_type": "text"
      },
      "source": [
        "## Euler Tour\n",
        "- A generic tree traversal algorithm that combines preorder and postorder traversal.\n",
        "- Run-time complexity is $O(n)$\n",
        "- Makes use of template method pattern\n",
        "  - primary algorithm calls auxilliary functions known as _**hooks**_"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r3DzbqxiMIYz",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 496
        },
        "outputId": "dfcc05e6-ca72-40fa-96d0-f0a5d065400f"
      },
      "source": [
        "class EulerTour:\n",
        "  '''\n",
        "  Abstract Base Class for performing Euler Tour of a tree.\n",
        "  _hook_previsit and _hook_postvisit may be overriden by subclasses.\n",
        "\n",
        "  '''\n",
        "  def __init__(self, tree):\n",
        "    '''Prepare an Euler Tour template for given tree.'''\n",
        "    self._tree = tree\n",
        "\n",
        "  def tree(self):\n",
        "    '''Return reference to the tree being traversed.'''\n",
        "    return self._tree\n",
        "  \n",
        "  def execute(self):\n",
        "    '''Perform the tour and return any result from post visit of root.'''\n",
        "    if len(self._tree) > 0:\n",
        "      return self._tour(self._tree.root(),0,[])  # start recursion\n",
        "\n",
        "  def _tour(self, p, d, path):\n",
        "    '''Perform tour of subtree rooted at Position P.\n",
        "\n",
        "    p: Position of current node being visited\n",
        "    d: depth of p in the tree\n",
        "    path: list of indices of children on path from root to p.\n",
        "\n",
        "    '''\n",
        "    self._hook_previsit(p, d, path)           #\"pre visit\" p\n",
        "    results = []\n",
        "    path.append(0)          # add new index to end of path before recursion\n",
        "    for c in self._tree.children(p):\n",
        "      results.append(self._tour(c, d+1, path))  # recur on child's subtree\n",
        "      path[-1] += 1       # increment index\n",
        "    path.pop()\n",
        "    answer = self._hook_postvisit(p, d, path, results) # \"post visit\" p\n",
        "    return answer\n",
        "\n",
        "  def _hook_previsit(self, p, d, path):     # can be overridden\n",
        "    pass\n",
        "\n",
        "  def _hook_postvisit(self, p, d, path, results): # can be overridden\n",
        "    pass \n",
        "\n",
        "class PreorderPrintIndentedTour(EulerTour):\n",
        "  def _hook_previsit(self, p, d, path):\n",
        "    print(2*d*' '+str(p.element()))\n",
        "\n",
        "class PreorderPrintIndentedTour2(EulerTour):\n",
        "  def _hook_previsit(self, p, d, path):\n",
        "    label = '.'.join(str(j+1)for j in path)  # labels are one-indexed\n",
        "    print(2*d*' '+label, str(p.element()))\n",
        "\n",
        "class ParenthesizeTour(EulerTour):\n",
        "  def _hook_previsit(self, p, d, path):\n",
        "    if path and path[-1] > 0:         # p follows a sibling\n",
        "      print(', ', end='')             # so preface with comma\n",
        "    print(p.element(), end='')        # then print element\n",
        "    if not self.tree().is_leaf(p):    # if p has children\n",
        "      print(' (', end='')             # print open parenthesis\n",
        "\n",
        "  def _hook_postvisit(self, p, d, path, results):\n",
        "    if not self.tree().is_leaf(p):        # if p has children\n",
        "      print(')', end='')\n",
        "\n",
        "# Test\n",
        "tour = PreorderPrintIndentedTour(A)\n",
        "tour.execute() \n",
        "print(\"-------------\")\n",
        "tour2 = PreorderPrintIndentedTour2(A)\n",
        "tour2.execute() \n",
        "print(\"--------------\")\n",
        "tour3 = ParenthesizeTour(A)\n",
        "tour3.execute()\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Paper\n",
            "  Title\n",
            "  Abstract\n",
            "  Section1\n",
            "    Sec1.1\n",
            "    Sec1.2\n",
            "    Sec1.3\n",
            "  Section2\n",
            "    Sec2.1\n",
            "    Sec2.2\n",
            "    Sec2.3\n",
            "  Conclusion\n",
            "-------------\n",
            " Paper\n",
            "  1 Title\n",
            "  2 Abstract\n",
            "  3 Section1\n",
            "    3.1 Sec1.1\n",
            "    3.2 Sec1.2\n",
            "    3.3 Sec1.3\n",
            "  4 Section2\n",
            "    4.1 Sec2.1\n",
            "    4.2 Sec2.2\n",
            "    4.3 Sec2.3\n",
            "  5 Conclusion\n",
            "--------------\n",
            "Paper (Title, Abstract, Section1 (Sec1.1, Sec1.2, Sec1.3), Section2 (Sec2.1, Sec2.2, Sec2.3), Conclusion)"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "j_MuMXU9YATF",
        "colab_type": "text"
      },
      "source": [
        "### The Euler Tour Traversal of a Binary Tree\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8kOCG1XuX-LY",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class BinaryEulerTour(EulerTour):\n",
        "  '''\n",
        "  Abstract base class for performing Euler Tour of a binary Tree.\n",
        "  '''\n",
        "  def _tour(self, p, d, path):\n",
        "    results = [None, None]          # will update with results from recursion\n",
        "    self._hook_previsit(p, d, path)   # \"pre visit\" p\n",
        "    if self._tree.left(p) is not None:      # consider left child\n",
        "      path.append(0)\n",
        "      results[0] = self._tour(self._tree.left(p), d+1, path)\n",
        "      path.pop()\n",
        "    self._hook_invisit(p, d, path)      # \"in visit\" for p\n",
        "    if self._tree.right(p) is not None:     # consider right child\n",
        "      path.append(1)\n",
        "      results[1] = self._tour(self._tree.right(p), d+1, path)\n",
        "      path.pop()\n",
        "    answer = self._hook_postvisit(p, d, path, results)  # \"post visit\" p\n",
        "    return answer\n",
        "  \n",
        "  def _hook_invisit(self, p, d, path):  # can be overridden\n",
        "    pass\n",
        "\n",
        "class BinaryLayout(BinaryEulerTour):\n",
        "  ''' Class for computing (x,y) coordinate for each node of a binary tree.'''\n",
        "  def __init__(self, tree):\n",
        "    super().__init__(tree)      # must call the parent constructor\n",
        "    self._count = 0             # initialize the count of processed nodes\n",
        "  \n",
        "  def _hook_invisit(self, p, d, path):\n",
        "    p.element().setX(self._count)       # x-coordinate serialized by count\n",
        "    p.element().setY(d)                 # y-coordinate is depth\n",
        "    self._count += 1\n",
        "    \n",
        "# Test\n",
        "tour4 = ParenthesizeTour(A)\n",
        "tour4.execute()\n"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}