Arrays/Python/DynamicArray

The DynamicArray class in Python demonstrates the use of a low-level ctype array to keep track of objects.

The class

"""
Goodrich et al
Data Structures in Python
Chapter 5: Array-Based Sequences

Question R-4

Expand on the DynamicArray class to support negative indexing
with the __getitem__ method.
"""
import ctypes

class DynamicArray:
    """
    A dynamic array class that works like a list.
    """
    def __init__(self):
        self._n = 0 # number of elements
        self._capacity = 1 # default array capacity
        self._A = self._make_array(self._capacity) # low-level guts

    def __getitem__(self,k):
        if(0<=k<self._n):
            return self._A[k]
        elif(-self._n<=k<0):
            return self._A[self._n+k]
        else:
            raise IndexError("Invalid index: Requested index {0} exceeds number of elements {1}".format(k,self._n))

    def append(self,obj):
        """Add obj to end of array"""
        if(self._n==self._capacity):
            # We are out of space, so resize.
            # Resize will update capacity for us.
            self._resize(2*self._capacity)
        self._A[self._n] = obj
        self._n += 1

    def _resize(self,c):
        """ Resize to capacity c (private)"""
        print("Resizing array: {0:3d}".format(self._n))
        B = self._make_array(c) # bigger array
        for k in range(self._n):
            B[k] = self._A[k] # copy existing elements only
        self._A = B # forget the old array
        self._capacity = c # update capacity

    def _make_array(self,n):
        """Make the internal array (private)"""
        return (n*ctypes.py_object)()

This should also utilize the following test, which can be tacked onto the end of the file.

The test

if __name__=="__main__":
    import random, sys
    a = DynamicArray()
    for j in range(1000):
        a.append(random.randint(0,9))

    for ix in [0, 10, 35, -10, -999, 999, -1000]:
        print("Index {0:4d}\tDynamicArray value: {1:2d}".format(ix,a[ix]))

    try:
        ix = 1000
        print("Index {0:4d}\tDynamicArray value: {1:2d}".format(ix,a[ix]))
    except IndexError:
        print("Correctly throws IndexError for index {0}.".format(ix))