{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dynamic Array Exercise\n",
    "____\n",
    "\n",
    "In this exercise we will create our own Dynamic Array class!\n",
    "\n",
    "We'll be using a built in library called [ctypes](https://docs.python.org/2/library/ctypes.html). Check out the documentation for more info, but its basically going to be used here as a raw array from the ctypes module.\n",
    "If you find yourself very interested in it, check out: [Ctypes Tutorial](http://starship.python.net/crew/theller/ctypes/tutorial.html)\n",
    "\n",
    "Also..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**A quick note on public vs private methods, we can use an underscore _ before the method name to keep it non-public. For example:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class M(object):\n",
    "    \n",
    "    def public(self):\n",
    "        print 'Use Tab to see me!'\n",
    "        \n",
    "    def _private(self):\n",
    "        print \"You won't be able to Tab to see me!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "m = M()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Use Tab to see me!\n"
     ]
    }
   ],
   "source": [
    "m.public()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "You won't be able to see me!\n"
     ]
    }
   ],
   "source": [
    "m._private()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check out PEP 8 and the Python docs for more info on this!\n",
    "_____\n",
    "\n",
    "### Dynamic Array Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import ctypes\n",
    "\n",
    "class DynamicArray(object):\n",
    "    '''\n",
    "    DYNAMIC ARRAY CLASS (Similar to Python List)\n",
    "    '''\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.n = 0 # Count actual elements (Default is 0)\n",
    "        self.capacity = 1 # Default Capacity\n",
    "        self.A = self.make_array(self.capacity)\n",
    "        \n",
    "    def __len__(self):\n",
    "        \"\"\"\n",
    "        Return number of elements sorted in array\n",
    "        \"\"\"\n",
    "        return self.n\n",
    "    \n",
    "    def __getitem__(self,k):\n",
    "        \"\"\"\n",
    "        Return element at index k\n",
    "        \"\"\"\n",
    "        if not 0 <= k <self.n:\n",
    "            return IndexError('K is out of bounds!') # Check it k index is in bounds of array\n",
    "        \n",
    "        return self.A[k] #Retrieve from array at index k\n",
    "        \n",
    "    def append(self, ele):\n",
    "        \"\"\"\n",
    "        Add element to end of the array\n",
    "        \"\"\"\n",
    "        if self.n == self.capacity:\n",
    "            self._resize(2*self.capacity) #Double capacity if not enough room\n",
    "        \n",
    "        self.A[self.n] = ele #Set self.n index to element\n",
    "        self.n += 1\n",
    "        \n",
    "    def _resize(self,new_cap):\n",
    "        \"\"\"\n",
    "        Resize internal array to capacity new_cap\n",
    "        \"\"\"\n",
    "        \n",
    "        B = self.make_array(new_cap) # New bigger array\n",
    "        \n",
    "        for k in range(self.n): # Reference all existing values\n",
    "            B[k] = self.A[k]\n",
    "            \n",
    "        self.A = B # Call A the new bigger array\n",
    "        self.capacity = new_cap # Reset the capacity\n",
    "        \n",
    "    def make_array(self,new_cap):\n",
    "        \"\"\"\n",
    "        Returns a new array with new_cap capacity\n",
    "        \"\"\"\n",
    "        return (new_cap * ctypes.py_object)()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Instantiate\n",
    "arr = DynamicArray()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Append new element\n",
    "arr.append(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check length\n",
    "len(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Append new element\n",
    "arr.append(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check length\n",
    "len(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Index\n",
    "arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Awesome, we made our own dynamic array! Play around with it and see how it auto-resizes. Try using the same **sys.getsizeof()** function we worked with previously!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Great Job!"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}