{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><center>cs1001.py , Tel Aviv University, Spring 2020</center></h1>\n",
    "<img src=\"http://www.pngall.com/wp-content/uploads/2016/05/Python-Logo-PNG-Image-180x180.png\" width=50/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recitation 9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We discussed OOP and special methods that allow us to define operators in Python.\n",
    "Then, we saw an implementation of a Linked list data structure.\n",
    "\n",
    "#### Takeaways:\n",
    "- OOP allows us to create classes at will and to define complex objects. Remember that the most important thing is to find a good inner representation of the object so that you will have an easy time working with it.\n",
    "\n",
    "- Important properties of Linked lists: \n",
    "    - Not stored continuously in memory.\n",
    "    - Allows for deletion and insertion after a __given__ element in $O(1)$ time.\n",
    "    - Accessing the $i$'th element takes $O(i)$ time.\n",
    "    - Search takes $O(n)$ time (no random access $\\implies$ no $O(\\log{n})$ search).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Code for printing several outputs in one cell (not part of the recitation):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## OOP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A link to special method names in python: <a href=\"https://diveintopython3.net/special-method-names.html\">https://diveintopython3.net/special-method-names.html</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic polynomial class\n",
    "\n",
    "We represent a polynomial as a list of coefficients, where the $i$'th element in the list is the coefficient of $x^i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1*x^0) + (1*x^1)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "(2*x^0) + (3*x^1) + (4*x^2)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Polynomial():\n",
    "    def __init__(self, coeffs):\n",
    "        self.coeffs = coeffs\n",
    "\n",
    "        \n",
    "        \n",
    "    def __repr__(self):\n",
    "        terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n",
    "                 str(k) + \")\" \\\n",
    "                 for k in range(len(self.coeffs)) \\\n",
    "                 if self.coeffs[k] != 0]\n",
    "        terms = \"\".join(terms)\n",
    "        if terms == \"\":\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return terms[3:] #discard leftmost '+'\n",
    "\n",
    "f = Polynomial([1, 1])\n",
    "g = Polynomial([2, 3, 4])\n",
    "\n",
    "f\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Add degree and evaluate functions (these are special to class polynomial and are not part of Python's recognized functions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Polynomial():\n",
    "    def __init__(self, coeffs):\n",
    "        self.coeffs = coeffs\n",
    "\n",
    "    def __repr__(self):\n",
    "        terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n",
    "                 str(k) + \")\" \\\n",
    "                 for k in range(len(self.coeffs)) \\\n",
    "                 if self.coeffs[k] != 0]\n",
    "        terms = \"\".join(terms)\n",
    "        if terms == \"\":\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return terms[3:] #discard leftmost '+'\n",
    "\n",
    "    def degree(self):\n",
    "        return len(self.coeffs) - 1\n",
    "\n",
    "    def evaluate(self, x):\n",
    "        result = 0\n",
    "        for i, c in enumerate(self.coeffs):\n",
    "            result += c * pow(x, i)\n",
    "        return result\n",
    "\n",
    "f = Polynomial([1, 1])\n",
    "f.degree()\n",
    "f.evaluate(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = Polynomial([1,0,1])\n",
    "q = Polynomial([1,0,1])\n",
    "p == q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Add \\__eq\\__ function for the '==' operator\n",
    "Without it, Python compares memory adderesses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Polynomial():\n",
    "    def __init__(self, coeffs):\n",
    "        self.coeffs = coeffs\n",
    "\n",
    "    def __repr__(self):\n",
    "        terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n",
    "                 str(k) + \")\" \\\n",
    "                 for k in range(len(self.coeffs)) \\\n",
    "                 if self.coeffs[k] != 0]\n",
    "        terms = \"\".join(terms)\n",
    "        if terms == \"\":\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return terms[3:] #discard leftmost '+'\n",
    "\n",
    "    def degree(self):\n",
    "        return len(self.coeffs) - 1\n",
    "\n",
    "    def evaluate(self, x):\n",
    "        result = 0\n",
    "        for i, c in enumerate(self.coeffs):\n",
    "            result += c * pow(x, i)\n",
    "        return result\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        assert isinstance(other, Polynomial)  \n",
    "        return self.coeffs == other.coeffs\n",
    "\n",
    "f = Polynomial([1, 1])\n",
    "f2 = Polynomial([1, 1])\n",
    "g = Polynomial([2, 3, 4])\n",
    "\n",
    "f == g\n",
    "f == f2\n",
    "f.__eq__(f2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Add the \\__add\\__ function for the '+' operator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3*x^0) + (4*x^1) + (4*x^2)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "(101*x^0) + (1*x^1)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "ename": "TypeError",
     "evalue": "unsupported operand type(s) for +: 'int' and 'Polynomial'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-6-b1cbfd0c49d6>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m     49\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     50\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m100\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 51\u001b[1;33m \u001b[1;36m100\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: unsupported operand type(s) for +: 'int' and 'Polynomial'"
     ]
    }
   ],
   "source": [
    "class Polynomial():\n",
    "    def __init__(self, coeffs):\n",
    "        self.coeffs = coeffs\n",
    "\n",
    "    def __repr__(self):\n",
    "        terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n",
    "                 str(k) + \")\" \\\n",
    "                 for k in range(len(self.coeffs)) \\\n",
    "                 if self.coeffs[k] != 0]\n",
    "        terms = \"\".join(terms)\n",
    "        if terms == \"\":\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return terms[3:] #discard leftmost '+'\n",
    "\n",
    "    def degree(self):\n",
    "        return len(self.coeffs) - 1\n",
    "\n",
    "    def evaluate(self, x):\n",
    "        result = 0\n",
    "        for i, c in enumerate(self.coeffs):\n",
    "            result += c * pow(x, i)\n",
    "        return result\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        assert isinstance(other, Polynomial)  \n",
    "        return self.coeffs == other.coeffs\n",
    "\n",
    "    def __add__(self, other):\n",
    "        assert isinstance(other, (Polynomial, int))  \n",
    "        if isinstance(other, int):\n",
    "            terms = [c for c in self.coeffs]\n",
    "            terms[0] += other\n",
    "            return Polynomial(terms)\n",
    "        #else, other is a polynomial\n",
    "        size = min(self.degree(), other.degree()) + 1\n",
    "        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n",
    "        terms += self.coeffs[size : self.degree() + 1]\n",
    "        terms += other.coeffs[size : other.degree() + 1]\n",
    "        #remove leading zeros\n",
    "        last = len(terms) - 1\n",
    "        while last > 0 and terms[last] == 0:\n",
    "            last -= 1\n",
    "        return Polynomial(terms[:last+1])\n",
    "\n",
    "f = Polynomial([1, 1])\n",
    "g = Polynomial([2, 3, 4])\n",
    "\n",
    "f+g\n",
    "f+100\n",
    "100+f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Add \\__radd\\__ function for right addition with int\n",
    "Since there is no support for addition with a Polynomial in the class int, python needs a definition of right addition for int in class Polynomial\n",
    "\n",
    "When executing the command $f + 3$, python will first search for an \\__add\\__ method in class int that can support a second operand of type polynomial (self = int, other = polynomial).\n",
    "If such method does not exist, python will then search for an \\__radd\\__ method in class polynomial that can support a second operand of type int (self= polynomial, other = int).\n",
    "If such method does not exist, an exception is thrown.\n",
    "\n",
    "Since + is commutative, then we set \\__radd\\__ to be identical to \\__add\\__\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2*x^0) + (1*x^1)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Polynomial():\n",
    "    def __init__(self, coeffs):\n",
    "        self.coeffs = coeffs\n",
    "\n",
    "    def __repr__(self):\n",
    "        terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n",
    "                 str(k) + \")\" \\\n",
    "                 for k in range(len(self.coeffs)) \\\n",
    "                 if self.coeffs[k] != 0]\n",
    "        terms = \"\".join(terms)\n",
    "        if terms == \"\":\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return terms[3:] #discard leftmost '+'\n",
    "\n",
    "    def degree(self):\n",
    "        return len(self.coeffs) - 1\n",
    "\n",
    "    def evaluate(self, x):\n",
    "        result = 0\n",
    "        for i, c in enumerate(self.coeffs):\n",
    "            result += c * pow(x, i)\n",
    "        return result\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        assert isinstance(other, Polynomial)  \n",
    "        return self.coeffs == other.coeffs\n",
    "\n",
    "    def __add__(self, other):\n",
    "        assert isinstance(other, (Polynomial, int))  \n",
    "        if isinstance(other, int):\n",
    "            terms = [c for c in self.coeffs]\n",
    "            terms[0] += other\n",
    "            return Polynomial(terms)\n",
    "        #else, other is a polynomial\n",
    "        size = min(self.degree(), other.degree()) + 1\n",
    "        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n",
    "        terms += self.coeffs[size : self.degree() + 1]\n",
    "        terms += other.coeffs[size : other.degree() + 1]\n",
    "        #remove leading zeros\n",
    "        last = len(terms) - 1\n",
    "        while last > 0 and terms[last] == 0:\n",
    "            last -= 1\n",
    "        return Polynomial(terms[:last+1])\n",
    "\n",
    "    __radd__ = __add__ #to allow int+Polynomial\n",
    "\n",
    "f = Polynomial([1, 1])\n",
    "1 + f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Add \\__neg\\__ function for unary minus (placing a '-' before a polynomial object)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-1*x^0) + (-1*x^1)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Polynomial():\n",
    "    def __init__(self, coeffs):\n",
    "        self.coeffs = coeffs\n",
    "\n",
    "    def __repr__(self):\n",
    "        terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n",
    "                 str(k) + \")\" \\\n",
    "                 for k in range(len(self.coeffs)) \\\n",
    "                 if self.coeffs[k] != 0]\n",
    "        terms = \"\".join(terms)\n",
    "        if terms == \"\":\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return terms[3:] #discard leftmost '+'\n",
    "\n",
    "    def degree(self):\n",
    "        return len(self.coeffs) - 1\n",
    "\n",
    "    def evaluate(self, x):\n",
    "        result = 0\n",
    "        for i, c in enumerate(self.coeffs):\n",
    "            result += c * pow(x, i)\n",
    "        return result\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        assert isinstance(other, Polynomial)  \n",
    "        return self.coeffs == other.coeffs\n",
    "\n",
    "    def __add__(self, other):\n",
    "        assert isinstance(other, (Polynomial, int))  \n",
    "        if isinstance(other, int):\n",
    "            terms = [c for c in self.coeffs]\n",
    "            terms[0] += other\n",
    "            return Polynomial(terms)\n",
    "        #else, other is a polynomial\n",
    "        size = min(self.degree(), other.degree()) + 1\n",
    "        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n",
    "        terms += self.coeffs[size : self.degree() + 1]\n",
    "        terms += other.coeffs[size : other.degree() + 1]\n",
    "        #remove leading zeros\n",
    "        last = len(terms) - 1\n",
    "        while last > 0 and terms[last] == 0:\n",
    "            last -= 1\n",
    "        return Polynomial(terms[:last+1])\n",
    "\n",
    "    __radd__ = __add__ #to allow int+Polynomial\n",
    "    \n",
    "    def __neg__(self):\n",
    "        return Polynomial([-co for co in self.coeffs])\n",
    "\n",
    "f = Polynomial([1, 1])\n",
    "-f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Add \\__sub\\__  function to subtract one poly form another or an int from a poly\n",
    "Using the fact we already have \\__neg\\__ and \\__add\\__ we define $f-g = f + (-g)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1*x^0) + (2*x^1) + (4*x^2)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "(1*x^0) + (3*x^1) + (4*x^2)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Polynomial():\n",
    "    def __init__(self, coeffs):\n",
    "        self.coeffs = coeffs\n",
    "\n",
    "    def __repr__(self):\n",
    "        terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n",
    "                 str(k) + \")\" \\\n",
    "                 for k in range(len(self.coeffs)) \\\n",
    "                 if self.coeffs[k] != 0]\n",
    "        terms = \"\".join(terms)\n",
    "        if terms == \"\":\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return terms[3:] #discard leftmost '+'\n",
    "\n",
    "    def degree(self):\n",
    "        return len(self.coeffs) - 1\n",
    "\n",
    "    def evaluate(self, x):\n",
    "        result = 0\n",
    "        for i, c in enumerate(self.coeffs):\n",
    "            result += c * pow(x, i)\n",
    "        return result\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        assert isinstance(other, Polynomial)  \n",
    "        return self.coeffs == other.coeffs\n",
    "\n",
    "    def __add__(self, other):\n",
    "        assert isinstance(other, (Polynomial, int))  \n",
    "        if isinstance(other, int):\n",
    "            terms = [c for c in self.coeffs]\n",
    "            terms[0] += other\n",
    "            return Polynomial(terms)\n",
    "        #else, other is a polynomial\n",
    "        size = min(self.degree(), other.degree()) + 1\n",
    "        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n",
    "        terms += self.coeffs[size : self.degree() + 1]\n",
    "        terms += other.coeffs[size : other.degree() + 1]\n",
    "        #remove leading zeros\n",
    "        last = len(terms) - 1\n",
    "        while last > 0 and terms[last] == 0:\n",
    "            last -= 1\n",
    "        return Polynomial(terms[:last+1])\n",
    "\n",
    "    __radd__ = __add__ #to allow int+Polynomial\n",
    "    \n",
    "    def __neg__(self):\n",
    "        return Polynomial([-co for co in self.coeffs])\n",
    "    \n",
    "    def __sub__(self, other):\n",
    "        assert isinstance(other, (int, Polynomial))  \n",
    "        return (self + (-other))\n",
    "    \n",
    "f = Polynomial([1, 1])\n",
    "g = Polynomial([2, 3, 4])\n",
    "\n",
    "g - f\n",
    "g - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Add \\__rsub\\__ function for right subtraction\n",
    "Using the fact we already have \\__neg\\__ and \\__sub\\__ we define $f-g = -(g-f)$\n",
    "\n",
    "since oprator \\- is not commutative, then we cannot set \\__rsub\\__ to be identical to \\__sub\\__\n",
    "\n",
    "Note that the following implementation of \\__rsub\\__ is promlematic, because it will keep calling itself (infinitely)\n",
    "\n",
    "    def __rsub__(self, other):\n",
    "        return other-self #PROBLEMATIC!\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-1*x^1)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "(-1*x^0) + (-3*x^1) + (-4*x^2)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Polynomial():\n",
    "    def __init__(self, coeffs):\n",
    "        self.coeffs = coeffs\n",
    "\n",
    "    def __repr__(self):\n",
    "        terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n",
    "                 str(k) + \")\" \\\n",
    "                 for k in range(len(self.coeffs)) \\\n",
    "                 if self.coeffs[k] != 0]\n",
    "        terms = \"\".join(terms)\n",
    "        if terms == \"\":\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return terms[3:] #discard leftmost '+'\n",
    "\n",
    "    def degree(self):\n",
    "        return len(self.coeffs) - 1\n",
    "\n",
    "    def evaluate(self, x):\n",
    "        result = 0\n",
    "        for i, c in enumerate(self.coeffs):\n",
    "            result += c * pow(x, i)\n",
    "        return result\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        assert isinstance(other, Polynomial)  \n",
    "        return self.coeffs == other.coeffs\n",
    "\n",
    "    def __add__(self, other):\n",
    "        assert isinstance(other, (Polynomial, int))  \n",
    "        if isinstance(other, int):\n",
    "            terms = [c for c in self.coeffs]\n",
    "            terms[0] += other\n",
    "            return Polynomial(terms)\n",
    "        #else, other is a polynomial\n",
    "        size = min(self.degree(), other.degree()) + 1\n",
    "        terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n",
    "        terms += self.coeffs[size : self.degree() + 1]\n",
    "        terms += other.coeffs[size : other.degree() + 1]\n",
    "        #remove leading zeros\n",
    "        last = len(terms) - 1\n",
    "        while last > 0 and terms[last] == 0:\n",
    "            last -= 1\n",
    "        return Polynomial(terms[:last+1])\n",
    "\n",
    "    __radd__ = __add__ #to allow int+Polynomial\n",
    "\n",
    "    def __neg__(self):\n",
    "        return Polynomial([-co for co in self.coeffs])\n",
    "\n",
    "    def __sub__(self, other):\n",
    "        assert isinstance(other, (int, Polynomial))  \n",
    "        return (self + (-other))\n",
    "\n",
    "    #__rsub__ = __sub__ #not what we want...\n",
    "\n",
    "    def __rsub__(self, other):\n",
    "        # other - self\n",
    "        return -(self - other) #why not just other-self ?\n",
    "\n",
    "f = Polynomial([1, 1])\n",
    "g = Polynomial([2, 3, 4])\n",
    "\n",
    "1 - f\n",
    "1 - g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A linked list is a linear data structure (i.e. - nodes can be accessed one after the other). The list is composed of nodes, where each node contains a value and a \"pointer\" to the next node in the list.\n",
    "\n",
    "Linked lists support operations such as insertion, deletion, search and many more."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node():\n",
    "    def __init__(self, val):\n",
    "        self.value = val\n",
    "        self.next = None\n",
    "        \n",
    "    def __repr__(self):\n",
    "        #return \"[\" + str(self.value) + \",\" + str(id(self.next))+ \"]\"\n",
    "        \n",
    "        #for today's recitation, we print the id of self instead of self.next\n",
    "        return \"[\" + str(self.value) + \",\" + str(id(self))+ \"]\"\n",
    "\n",
    "\n",
    "\n",
    "class Linked_list():\n",
    "\n",
    "    def __init__(self, seq=None):\n",
    "        self.next = None\n",
    "        self.len = 0\n",
    "        if seq != None:\n",
    "            for x in seq[::-1]:\n",
    "                self.add_at_start(x)\n",
    "            \n",
    "\n",
    "    def __repr__(self):\n",
    "       out = \"\"\n",
    "       p = self.next\n",
    "       while p != None:\n",
    "           out += str(p) + \" \" #str envokes __repr__ of class Node\n",
    "           p = p.next\n",
    "       return out\n",
    "\n",
    "            \n",
    "    def __len__(self):\n",
    "        ''' called when using Python's len() '''\n",
    "        return self.len\n",
    "            \n",
    "            \n",
    "    def add_at_start(self, val):\n",
    "        ''' add node with value val at the list head '''\n",
    "        p = self\n",
    "        tmp = p.next\n",
    "        p.next = Node(val)\n",
    "        p.next.next = tmp\n",
    "        self.len += 1\n",
    "    \n",
    "    def add_at_end(self, val):\n",
    "        ''' add node with value val at the list tail '''\n",
    "        p = self\n",
    "        while (p.next != None):\n",
    "            p = p.next\n",
    "        p.next = Node(val)\n",
    "        self.len += 1\n",
    "            \n",
    "        \n",
    "    def insert(self, loc, val):\n",
    "        ''' add node with value val after location 0<=loc<len of the list '''\n",
    "        assert 0 <= loc < len(self)\n",
    "        p = self\n",
    "        for i in range(0, loc):\n",
    "            p = p.next\n",
    "        tmp = p.next\n",
    "        p.next = Node(val)\n",
    "        p.next.next = tmp\n",
    "        self.len += 1\n",
    "        \n",
    "          \n",
    "    def __getitem__(self, loc):\n",
    "        ''' called when using L[i] for reading\n",
    "            return node at location 0<=loc<len '''\n",
    "        assert 0 <= loc < len(self)\n",
    "        p = self.next\n",
    "        for i in range(0, loc):\n",
    "            p = p.next\n",
    "        return p\n",
    "\n",
    "    def __setitem__(self, loc, val):\n",
    "        ''' called when using L[loc]=val for writing\n",
    "            assigns val to node at location 0<=loc<len '''\n",
    "        assert 0 <= loc < len(self)\n",
    "        p = self.next\n",
    "        for i in range(0, loc):\n",
    "            p = p.next\n",
    "        p.value = val\n",
    "        return None\n",
    "\n",
    "    \n",
    "    def find(self, val):\n",
    "        ''' find (first) node with value val in list '''\n",
    "        p = self.next\n",
    "        # loc = 0     # in case we want to return the location\n",
    "        while p != None:\n",
    "            if p.value == val:\n",
    "                return p\n",
    "            else:\n",
    "                p = p.next\n",
    "                #loc=loc+1   # in case we want to return the location\n",
    "        return None\n",
    "\n",
    "    def delete(self, loc):\n",
    "        ''' delete element at location 0<=loc<len '''\n",
    "        assert 0 <= loc < len(self)\n",
    "        p = self\n",
    "        for i in range(0, loc):\n",
    "            p = p.next\n",
    "        # p is the element BEFORE loc\n",
    "        p.next = p.next.next\n",
    "        self.len -= 1\n",
    " \n",
    "    \n",
    "    def insert_ordered(self, val):\n",
    "        ''' assume self is an ordered list,\n",
    "            insert Node with val in order '''\n",
    "        p = self\n",
    "        q = self.next\n",
    "        while q != None and q.value < val:\n",
    "            p = q\n",
    "            q = q.next\n",
    "        newNode = Node(val)\n",
    "        p.next = newNode\n",
    "        newNode.next = q\n",
    "        self.len += 1\n",
    "\n",
    "    def find_ordered(self, val):\n",
    "        ''' assume self is an ordered list,\n",
    "            find Node with value val '''\n",
    "        p = self.next\n",
    "        while p != None and p.value < val:\n",
    "            p = p.next\n",
    "        if p != None and p.value == val: \n",
    "            return p\n",
    "        else:\n",
    "            return None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Converting a string to a list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[a,91843024] [b,91843088] [c,91842992] "
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L= Linked_list(\"abc\")\n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "memory view"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"linked_lst_mem.PNG\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Adding elements one by one. Try using Python tutor. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[b,91843568] [a,91843664] "
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = Linked_list()\n",
    "l.add_at_start(\"a\")\n",
    "l.add_at_start(\"b\")\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### A short summary of methods complexity of Linked lists vs. lists:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table width=550 align=\"left\">\n",
    "        <tr>\n",
    "            <td> <b>Method</b></td>\n",
    "            <td> <b>List</b></td>\n",
    "            <td> <b>Linked list</b></td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "            <td> init</td>\n",
    "            <td> $O(1)$</td>\n",
    "            <td> $O(1)$</td>\n",
    "    </tr>\n",
    "    <tr> \n",
    "        <td> init with $k$ items</td>\n",
    "        <td> $O(k)$</td>\n",
    "        <td> $O(k)$</td>\n",
    "    </tr>\n",
    "    <tr> \n",
    "        <td colspan=\"3\"><b>for the rest of the methods we assume that the structure contains $n$ items</b></td>\n",
    "    </tr>\n",
    "    <tr> \n",
    "        <td> add at start</td>\n",
    "        <td> $O(n)$</td>\n",
    "        <td> $O(1)$</td>\n",
    "    </tr>\n",
    "    <tr> \n",
    "        <td> add at end</td>\n",
    "        <td> $O(1)$</td>\n",
    "        <td> $O(n)$</td>\n",
    "    </tr>\n",
    "    <tr> \n",
    "        <td> $lst[k]$ (get the $k$th item)</td>\n",
    "        <td> $O(1)$</td>\n",
    "        <td> $O(k)$</td>\n",
    "    </tr>\n",
    "    <tr> \n",
    "        <td> delete $lst[k]$</td>\n",
    "        <td> $O(n-k)$</td>\n",
    "        <td> $O(k)$</td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reversing a linked list in $O(1)$ additional memory. \n",
    "See the code and demo <a href=\"http://tau-cs1001-py.wdfiles.com/local--files/recitation-logs-2017b/m_09_reverse_list.pdf\">here</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[a,91941296] [b,91941232] [c,91941200] "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "[c,91941200] [b,91941232] [a,91941296] "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Node():\n",
    "    def __init__(self, val):\n",
    "        self.value = val\n",
    "        self.next = None\n",
    "        \n",
    "    def __repr__(self):\n",
    "        #return \"[\" + str(self.value) + \",\" + str(id(self.next))+ \"]\"\n",
    "        \n",
    "        #for today's recitation, we print the id of self instead of self.next\n",
    "        return \"[\" + str(self.value) + \",\" + str(id(self))+ \"]\"\n",
    "\n",
    "\n",
    "class Linked_list():\n",
    "\n",
    "    def __init__(self, seq=None):\n",
    "        self.next = None\n",
    "        self.len = 0\n",
    "        if seq != None:\n",
    "            for x in seq[::-1]:\n",
    "                self.add_at_start(x)\n",
    "            \n",
    "\n",
    "    def __repr__(self):\n",
    "       out = \"\"\n",
    "       p = self.next\n",
    "       while p != None:\n",
    "           out += str(p) + \" \" #str envokes __repr__ of class Node\n",
    "           p = p.next\n",
    "       return out\n",
    "\n",
    "            \n",
    "    def __len__(self):\n",
    "        ''' called when using Python's len() '''\n",
    "        return self.len\n",
    "            \n",
    "            \n",
    "    def add_at_start(self, val):\n",
    "        ''' add node with value val at the list head '''\n",
    "        p = self\n",
    "        tmp = p.next\n",
    "        p.next = Node(val)\n",
    "        p.next.next = tmp\n",
    "        self.len += 1\n",
    "    \n",
    "    def add_at_end(self, val):\n",
    "        ''' add node with value val at the list tail '''\n",
    "        p = self\n",
    "        while (p.next != None):\n",
    "            p = p.next\n",
    "        p.next = Node(val)\n",
    "        self.len += 1\n",
    "            \n",
    "        \n",
    "    def insert(self, loc, val):\n",
    "        ''' add node with value val after location 0<=loc<len of the list '''\n",
    "        assert 0 <= loc < len(self)\n",
    "        p = self\n",
    "        for i in range(0, loc):\n",
    "            p = p.next\n",
    "        tmp = p.next\n",
    "        p.next = Node(val)\n",
    "        p.next.next = tmp\n",
    "        self.len += 1\n",
    "        \n",
    "          \n",
    "    def __getitem__(self, loc):\n",
    "        ''' called when using L[i] for reading\n",
    "            return node at location 0<=loc<len '''\n",
    "        assert 0 <= loc < len(self)\n",
    "        p = self.next\n",
    "        for i in range(0, loc):\n",
    "            p = p.next\n",
    "        return p\n",
    "\n",
    "    def __setitem__(self, loc, val):\n",
    "        ''' called when using L[loc]=val for writing\n",
    "            assigns val to node at location 0<=loc<len '''\n",
    "        assert 0 <= loc < len(self)\n",
    "        p = self.next\n",
    "        for i in range(0, loc):\n",
    "            p = p.next\n",
    "        p.value = val\n",
    "        return None\n",
    "\n",
    "    \n",
    "    def find(self, val):\n",
    "        ''' find (first) node with value val in list '''\n",
    "        p = self.next\n",
    "        # loc = 0     # in case we want to return the location\n",
    "        while p != None:\n",
    "            if p.value == val:\n",
    "                return p\n",
    "            else:\n",
    "                p = p.next\n",
    "                #loc=loc+1   # in case we want to return the location\n",
    "        return None\n",
    "\n",
    "    def delete(self, loc):\n",
    "        ''' delete element at location 0<=loc<len '''\n",
    "        assert 0 <= loc < len(self)\n",
    "        p = self\n",
    "        for i in range(0, loc):\n",
    "            p = p.next\n",
    "        # p is the element BEFORE loc\n",
    "        p.next = p.next.next\n",
    "        self.len -= 1\n",
    " \n",
    "    \n",
    "    def insert_ordered(self, val):\n",
    "        ''' assume self is an ordered list,\n",
    "            insert Node with val in order '''\n",
    "        p = self\n",
    "        q = self.next\n",
    "        while q != None and q.value < val:\n",
    "            p = q\n",
    "            q = q.next\n",
    "        newNode = Node(val)\n",
    "        p.next = newNode\n",
    "        newNode.next = q\n",
    "        self.len += 1\n",
    "\n",
    "    def find_ordered(self, val):\n",
    "        ''' assume self is an ordered list,\n",
    "            find Node with value val '''\n",
    "        p = self.next\n",
    "        while p != None and p.value < val:\n",
    "            p = p.next\n",
    "        if p != None and p.value == val: \n",
    "            return p\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def reverse(self):\n",
    "        prev = None\n",
    "        curr = self.next\n",
    "        while curr != None:\n",
    "            tmp = curr.next\n",
    "            curr.next = prev\n",
    "            prev = curr\n",
    "            curr = tmp\n",
    "        self.next = prev\n",
    "        \n",
    "ll = Linked_list(\"abc\")\n",
    "ll\n",
    "ll.reverse()\n",
    "ll\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exam question (2018, Spring Semester)\n",
    "\n",
    "Let $L,K$ be two linked lists of length $n,m$ respectively. We say that the **lists merge** if there exists a node that is on both lists.\n",
    "\n",
    "I.e. - there exists a node $q$ in $L$ and $p$ in $K$ such that $q ~is~ p == True$. In such a case we call $p$ a **joint node**.\n",
    "\n",
    "Write a function $are\\_merged$ that gets two linked lists as an input and returns True iff the lists merge.\n",
    "\n",
    "The main idea - two linked lists merge if and only if their last node (their tail) is the same node.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[a,2582652271360] [b,2582652268728] [c,2582652271808] [d,2582652268840] "
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "[e,2582652270800] [c,2582652271808] [d,2582652268840] "
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "[d,2582652629344] "
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def are_merged(L, K):\n",
    "    node_l = L.next\n",
    "    node_k = K.next\n",
    "    while node_l.next != None:\n",
    "        node_l = node_l.next\n",
    "    while node_k.next != None:\n",
    "        node_k = node_k.next\n",
    "    return node_k is node_l\n",
    "    \n",
    "    #Here is an equivalent solution with a shorter code:\n",
    "    #last_node_l = L[len(L)-1]\n",
    "    #last_node_k = K[len(K)-1]\n",
    "    #return last_node_l is last_node_k\n",
    "\n",
    "L = Linked_list(\"abcd\")\n",
    "L\n",
    "\n",
    "K = Linked_list()\n",
    "K.next = L.next.next.next\n",
    "# Manually define the length of K\n",
    "K.len = 2\n",
    "K.add_at_start(\"e\")\n",
    "K\n",
    "\n",
    "M = Linked_list()\n",
    "M.add_at_start(\"d\")\n",
    "M\n",
    "\n",
    "print(are_merged(L,K))\n",
    "print(are_merged(L,M))\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time and space analysis\n",
    "\n",
    "Space: Saving a pointer to two nodes can be done in $O(1)$ memory\n",
    "Time: Each node in the lists is read exactly once and all operations run in time $O(1)$ so runtime is $O(n+m)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, write a function $find\\_shared$ that gets two merged linked lists as an input and returns the first joint node of the lists.\n",
    "\n",
    "Analyze its running time and space complexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[a,91940784] [b,91940624] [c,91940592] [d,91940272] "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "[e,91940432] [c,91940592] [d,91940272] "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "[d,1901584] "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "advp\n",
      "advp\n",
      "[c,91940592] True\n",
      "[c,91940592] True\n",
      "[c,91940592] True\n"
     ]
    }
   ],
   "source": [
    "def find_shared_1(L, K):\n",
    "    id_set = set()\n",
    "    p = L.next\n",
    "    while p != None:\n",
    "        id_set.add(id(p))\n",
    "        p = p.next\n",
    "    q = K.next\n",
    "    while q != None:\n",
    "        if id(q) in id_set:\n",
    "            return q\n",
    "        q = q.next\n",
    "    return None # should not reach here since L, K have joint items\n",
    "\n",
    "\n",
    "def find_shared_2(L, K):\n",
    "    n = len(L)\n",
    "    m = len(K)\n",
    "    p = L.next\n",
    "    q = K.next\n",
    "    for i in range(max(0, n-m)):\n",
    "        print('advp')\n",
    "        p = p.next\n",
    "    for i in range(max(0, m-n)):\n",
    "        print('advq')\n",
    "        q = q.next\n",
    "    while p != None:\n",
    "        if p is q:\n",
    "            return p\n",
    "        p = p.next\n",
    "        q = q.next\n",
    "    return None # Should never get here\n",
    "\n",
    "def find_shared_3(L, K):\n",
    "    p = L.next\n",
    "    q = K.next\n",
    "    while p != None and q != None:\n",
    "        if p is q:\n",
    "            return p\n",
    "        p = p.next\n",
    "        q = q.next\n",
    "        if p == None:\n",
    "            p = K.next\n",
    "        if q == None:\n",
    "            q = L.next\n",
    "    return None # must end before, since L, K have joint items    \n",
    "\n",
    "L = Linked_list(\"abcd\")\n",
    "L\n",
    "\n",
    "K = Linked_list()\n",
    "K.next = L.next.next.next\n",
    "# Save the first joint node\n",
    "x = K.next\n",
    "K.len = 2\n",
    "K.add_at_start(\"e\")\n",
    "K\n",
    "\n",
    "M = Linked_list()\n",
    "M.add_at_start(\"d\")\n",
    "M\n",
    "\n",
    "print(are_merged(L,K))\n",
    "print(are_merged(L,M))\n",
    "\n",
    "\n",
    "\n",
    "print(find_shared_1(L,K), find_shared_1(L,K) == x)\n",
    "print(find_shared_2(L,K), find_shared_2(L,K) == x)\n",
    "print(find_shared_3(L,K), find_shared_3(L,K) == x)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the analysis assume wlog that $n \\geq m$:\n",
    "* For find_shared_1:\n",
    "    * Space: Saving all of the node ids from $L$ in a set: $O(n)$, saving one or two node pointers at a time is $O(1)$\n",
    "    * Time: All lookups in the set run in $O(1)$ on average, apart from that each node in $K,L$ is read exactly once - $O(n)$ on average\n",
    "* For find_shared_2:\n",
    "    * Space: Saving $n,m$ and an index for the for loop: $O(\\log n)$, saving one or two node pointers at a time is $O(1)$\n",
    "    * Time: First two for loops and the while loop traverse each node in $K,L$ exactly once - $O(n)$\n",
    "* For find_shared_3:\n",
    "    * Space: Saving one or two node pointers throughout the while loop is $O(1)$\n",
    "    * Time: Pointer p will first traverse the $n$ nodes of L and then the $m$ nodes of K. Pointer $q$ will first traverse the $m$ nodes of K and then the $n$ nodes of L. Suppose that the joint part is of length $w$, then both pointers will reach it after $n+m-w$ steps. Since all operations in the while loop run in $O(1)$ time, the overall running time is $O(n)$\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}