array_list.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Array Lists\n",
    "\n",
    "The array list implements the generic list interface:\n",
    "\n",
    "`insert(value, index)`<br>\n",
    "`delete(index)`<br>\n",
    "`access(index)`<br>\n",
    "`search(value)`<br>\n",
    "`append(value)`<br>\n",
    "\n",
    "with the use of an underlying array. Arrays are structures of fixed size. The closest to this that Python provides is the `numpy.empty(n, dtype=object)` which creates an array of length $n$ that can store objects and cannot be resized or appended to.\n",
    "\n",
    "All the above functions are **`O(n)`**. For insert and delete this is because they need to copy elements accordingly.\n",
    "In contrast access by index is fast **`O(1)`**.\n",
    "\n",
    "The helper functions:\n",
    "\n",
    "`ensure_capacity()`<br>\n",
    "`print_list()`<br>\n",
    "\n",
    "are also provided. `ensure_capacity()` checks if there is enough space. If needed it creates a larger array to copy the current one in order to allow additional capacity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyArrayList:\n",
    "    def __init__(self, capacity):\n",
    "        self.capacity = capacity\n",
    "        self.size = 0\n",
    "        self.a = np.empty(capacity, dtype=object) \n",
    "        \n",
    "    def insert(self,val,index):\n",
    "        assert (index>=0 and index<=self.size), \"index out of bounds, provide an index between 0 and \" + self.size\n",
    "        self.ensure_capacity()\n",
    "        for i in range (self.size-1, index-1, -1): #for i=size-1 to i<index-1, i--\n",
    "            self.a[i+1]=self.a[i]\n",
    "        self.a[index]=val\n",
    "        self.size = self.size+1\n",
    "    \n",
    "    def delete(self,index):\n",
    "        assert (index>=0 and index<=self.size), \"index out of bounds, provide an index between 0 and \" + str(self.size) \n",
    "        for i in range (index, self.size-1, +1): #for i=index to i<size-1, i++\n",
    "            self.a[i]=self.a[i+1]\n",
    "        self.a[self.size-1]=None\n",
    "        self.size = self.size-1\n",
    "    \n",
    "    def access(self, index):\n",
    "        assert (index>=0 and index<=self.size), \"index out of bounds, provide an index between 0 and \" + str(self.size)\n",
    "        return self.a[index]\n",
    "    \n",
    "    def search(self,value):\n",
    "        for i in range (0, self.size, +1):\n",
    "            if (self.a[i]==value): return i\n",
    "        return False\n",
    "    \n",
    "    def append(self, value):\n",
    "        self.ensure_capacity()\n",
    "        self.insert(value, self.size)\n",
    "    \n",
    "    def print_list(self):\n",
    "        for i in range(self.size):\n",
    "            print str (self.a[i]),\n",
    "        print \"size= \", self.size\n",
    "        \n",
    "    def ensure_capacity(self):\n",
    "        if (self.size==self.capacity): \n",
    "            c = self.capacity+self.capacity/2\n",
    "            b = np.empty(c, dtype=object)\n",
    "            for i in range (self.capacity):\n",
    "                b[i]=self.a[i]\n",
    "            self.a=b\n",
    "            self.capacity=c\n",
    "            print \"increased capacity: \" , self.capacity, \", size:\", self.size"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Notes:**\n",
    "\n",
    "`0 :1 :2 :3 :4 :5 :6_` <- array positions<br>\n",
    "`0 :10:20:30:40:##:##` <- array values<br> \n",
    "`0 :10:20:20:30:40:##` <- insert 50 in position 2: go to position `size-1` (4) and start copying right until position `index`<br>\n",
    "`0 :10:50:20:30:40:##`<br>\n",
    "\n",
    "Note that the implementation of \"in range\" stops one step before the end number, for example:\n",
    "-  in range (5) returns [0,1,2,3,4] (stops at 4, one step before 5)\n",
    "-  in range (5, 0, -1) returns [5,4,3,2,1] (stops at 1, one reverse step before 0)\n",
    "\n",
    "For this reason the stoping condition at `index` needs to become at `index-1`, when inserting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 size=  6\n"
     ]
    }
   ],
   "source": [
    "#Create a list\n",
    "alist = MyArrayList(10)\n",
    "for i in range(6):\n",
    "    alist.insert(i,i)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 10 1 2 3 4 5 size=  7\n"
     ]
    }
   ],
   "source": [
    "#insert in the middle\n",
    "alist.insert(10,1)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99 0 10 1 2 3 4 5 size=  8\n"
     ]
    }
   ],
   "source": [
    "#insert at the beggining\n",
    "alist.insert(99,0)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#search for values that exist\n",
    "alist.search(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99 0 1 2 3 4 5 size=  7\n"
     ]
    }
   ],
   "source": [
    "#delete in the middle\n",
    "alist.delete(2)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99 0 1 2 3 4 5 60 size=  8\n"
     ]
    }
   ],
   "source": [
    "#insert at the end\n",
    "alist.append(60)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#search for values that do not exist\n",
    "alist.search(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 60 size=  7\n"
     ]
    }
   ],
   "source": [
    "#delete the first node\n",
    "alist.delete(0)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 size=  6\n"
     ]
    }
   ],
   "source": [
    "#delete at the end\n",
    "#delete the first node\n",
    "alist.delete(alist.size-1)\n",
    "alist.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 60 70 80 90 size=  10\n",
      "increased capacity:  15 , size: 10\n",
      "0 1 2 3 4 5 60 70 80 90 100 size=  11\n"
     ]
    }
   ],
   "source": [
    "#increase the list capacity to more than 10 in order to accommodate more elements\n",
    "alist.append(60)\n",
    "alist.append(70)\n",
    "alist.append(80)\n",
    "alist.append(90)\n",
    "alist.print_list()\n",
    "\n",
    "alist.append(100)\n",
    "alist.print_list()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}