Arrays/Python/DynamicArray

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

Features:

• Implements an array-based structure that works like a Python list, has many of the same features and O() operational costs
• Handles negative indices like mylist[-1]
• "Dynamic shrinkage" that works like a Python list - as more elements are removed, the array is automatically resized to be smaller
• See pop() method implementation

The class

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

Question R-5.4

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

Question C-5.16

Implement a pop() method for DynamicArray.
It should remove the last item in the array.
It should shrink the capacity in half
if the number of elements drops below N/4.
"""
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 pop(self):
        """Pop obj from end of array"""
        self._A[self._n] = None
        self._n -= 1
        if(self._capacity//4 > self._n):
            self._resize(self._capacity//2)

    def _resize(self,c):
        """ Resize to capacity c (private)"""
        print("Resizing array: {0:4d} elements, {1:5d} capacity".format(self._n,c))
        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)()


if __name__=="__main__":

    import random, sys
    a = DynamicArray()


    print("Appending 1,000 elements to array...")
    for j in range(1000):
        a.append(random.randint(0,9))
    print("Done.\n")


    print("Accessing array at individual positive/negative indices...")
    for ix in [0, 10, 35, -10, -999, 999, -1000]:
        print("Index {0:4d}\tDynamicArray value: {1:2d}".format(ix,a[ix]))
    print("Done.\n")


    print("Accessing array at invalid index...")
    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))
    print("Done.\n")


    print("Popping 995 elements from array...")
    for j in range(995):
        a.pop()
    print("Done.\n")

Expected output

$ python DynamicArray.py
Appending 1,000 elements to array...
Resizing array:    1 elements,     2 capacity
Resizing array:    2 elements,     4 capacity
Resizing array:    4 elements,     8 capacity
Resizing array:    8 elements,    16 capacity
Resizing array:   16 elements,    32 capacity
Resizing array:   32 elements,    64 capacity
Resizing array:   64 elements,   128 capacity
Resizing array:  128 elements,   256 capacity
Resizing array:  256 elements,   512 capacity
Resizing array:  512 elements,  1024 capacity
Done.

Accessing array at individual positive/negative indices...
Index    0	DynamicArray value:  5
Index   10	DynamicArray value:  9
Index   35	DynamicArray value:  4
Index  -10	DynamicArray value:  2
Index -999	DynamicArray value:  1
Index  999	DynamicArray value:  7
Index -1000	DynamicArray value:  5
Done.

Accessing array at invalid index...
Correctly throws IndexError for index 1000.
Done.

Popping 995 elements from array...
Resizing array:  255 elements,   512 capacity
Resizing array:  127 elements,   256 capacity
Resizing array:   63 elements,   128 capacity
Resizing array:   31 elements,    64 capacity
Resizing array:   15 elements,    32 capacity
Resizing array:    7 elements,    16 capacity
Done.