DynamicArray in Python

Using ctypes module, we can create a new DynamicArray type. See more ctypes documentation to understand.

import ctypes 

class DynamicArray:
    def __init__(self):
        """ Create an empty array """
        self._n = 0 # count actual elements in array
        self._capacity = 1
        self._A = self._make_array(self._capacity)
    
    def __len__(self):
        """ Return number of elements stored in array """
        return self._n
    
    def __getitem__(self, k):
        """ return element at index k """
        if not 0 <= k < len(self):
            raise IndexError('invalid index')
        return self._A[k] # retrieve from array
    
    def append(self, obj):
        """ Add object to the end of array """
        if len(self) == self._capacity: # not enough room
            self._resize(2 * self._capacity) # so double capacity
        self._A[self._n] = obj
        self._n += 1
    
    def _resize(self, c):
        """ Resize the old array to capacity c """
        print 'Call resize'
        B = self._make_array(c) # new bigger array
        for k in xrange(self._n): # copy the old array to bigger array
            B[k] = self._A[k]
        self._A = B
        self._capacity = c
    
    def _make_array(self, c):
        """ Return a new array with capacity c """
        return (c * ctypes.py_object)() # see ctypes documentation
    
    def insert(self, k, value):
        """ Insert value at index k in array by shifting rightmost elements to the right """
        if not 0 <= k < len(self):
            raise IndexError('invalid index')
        if self._n == len(self): # not enough room
            self.resize(2 * self._capacity) # double capacity
        for j in range(self._n, k, -1): # shift rightmost first
            self._A[j] = self._A[j-1]
        self._A[k] = value # get new element
        self._n += 1
    
    def remove(self, value):
        """ remove the first occurence of value """
        for k in xrange(len(self)):
            if self._A[k] == value: # found 
                for j in range(k, len(self)-1): # shift all elements on the right side to left
                    self._A[j] = self._A[j+1]
                self._A[len(self)-1] = None # garbage collection
                self._n -= 1 # reduce n 
                return # exit immediately
        raise ValueError('value not found') 

    def __str__(self):
        """ presentation of dynamic array (user friendly form) """
        pre = "["
        for i in xrange(len(self)):
            pre += str(self[i]) + (", " if i < len(self)-1 else "]")
        return pre

# test out the DynamicArray
if __name__ == '__main__':
    arr = DynamicArray()
    for i in range(100):
        arr.append(i)
    # print call resize 7 times
    print arr

An attribute (instance, method) with zero underscore is considered as public. One underscore is protected and two is private. Try it yourself, if you use two underscore, you cannot access the object’s attributes outside of class.

Advertisements