The Array-Backed List

Agenda

1. The List Abstract Data Type (ADT)
2. A List Data Structure
3. Our List API
4. NumPy Array
5. The ArrayList data structure

# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"

1. The List Abstract Data Type (ADT)

An abstract data type (ADT) defines a conceptual model for how data may be stored and accessed.

A list ADT is a data container where:

• values are ordered in a sequence
• each value has at most one preceding and one succeeding value
• a given value may appear more than once in a list

Other common ADTs (some of which we'll explore later) include:

• Stacks
• Queues
• Priority Queues
• Maps
• Graphs

2. A List Data Structure

A list data structure is a concrete implementation of the list ADT in some programming language, which, in addition to adhering to the basic premises of the ADT, will also typically support operations that:

• access values in the list by their position (index)
• append and insert new values into the list
• remove values from the list

The implementation of any data structure will generally rely on simpler, constituent data types (e.g., "primitive" types offered by the language), the choice of which may affect the runtime complexities of said operations.

3. The List API

The operations we'll be building into our list data structures will be based on the common and mutable sequence operations defined by the Python library.

class List:        
    ### subscript-based access ###
    
    
    def __getitem__(self, idx):
        """Implements `x = self[idx]`"""
        pass

    def __setitem__(self, idx, value):
        """Implements `self[idx] = x`"""
        pass

    def __delitem__(self, idx):
        """Implements `del self[idx]`"""
        pass
    
    ### stringification ###
            
    def __repr__(self):
        """Supports inspection"""
        return '[]'
    
    def __str__(self):
        """Implements `str(self)`"""
        return '[]'

    ### single-element manipulation ###
    
    def append(self, value):
        pass
    
    def insert(self, idx, value):
        pass
    
    def pop(self, idx=-1):
        pass
    
    def remove(self, value):
        pass
    
    ### predicates (T/F queries) ###
    
    def __eq__(self, other):
        """Implements `self == other`"""
        return True

    def __contains__(self, value):
        """Implements `val in self`"""
        return True
    
    ### queries ###
    
    def __len__(self):
        """Implements `len(self)`"""
        return self.size
    
    def min(self):
        pass
    
    def max(self):
        pass
    
    def index(self, value, i, j):
        pass
    
    def count(self, value):
        pass

    ### bulk operations ###

    def __add__(self, other):
        """Implements `self + other_array_list`"""
        return self
    
    def clear(self):
        pass
    
    def copy(self):
        pass

    def extend(self, other):
        pass

    ### iteration ###
    
    def __iter__(self):
        """Supports iteration (via `iter(self)`)"""
        pass

4. NumPy Array

For the ArrayList's underlying data storage mechanism you will use the NumPy array. You will be using a very limited subset of the available APIs for working with NumPy arrays, however. Specifically, you may use:

• empty for creating empty arrays. You will be calling it like this (assuming the numpy library has been imported as np, as we always do): np.empty(N, dtype=object). This will create an empty array of size N, each slot of which can be used to store a reference to an arbitrary Python object.

• Valid, positive indexes into arrays. It will be your job in the implementation of ArrayList to check for valid indexes and to translate negative indexes into positive ones.

• len(arr) to get the length (i.e., number of slots) of array arr. Note that this will not generally coincide with the number of actual elements in the list!

You should not use any other array-related functions provided by NumPy! Notably, delete, insert append, resize, and others, are off limits. Using them to carry out list operations is, generally speaking, less efficient than the manual approach outlined in class. Also, it's important that you learn how to implement them yourself. Breaking this rule will result in significant score reduction(s).

5. The ArrayList data structure

import numpy as np

class ArrayList:
    def __init__(self):
        self.data = np.empty(1, dtype=object)   # is a numpy array
        #  i can call self.data[index] both get and set
        #  len(self.data)   #of allocated slots 
        self.size = 0

    def append(self, value):
        # worst case append is O(n)  the size of the array
        #self.size is number of actual elements in array
        # self.size is also the next avaialble index
        if self.size<len(self.data):   # calling numpy len method
              #    self.size<self.__len()__     or  len(self) 
            self.data[self.size]=value
            self.size+=1
        else:
            newSize=2*len(self.data)
            newArray = np.empty(newSize, dtype=object)
            for i in range(len(self.data)):  # i goes from 0 to  len(self.data)-1
                newArray[i]=self.data[i]
            self.data=newArray
            self.data[self.size]=value
            self.size+=1       

    def __getitem__(self, idx):
        """Implements `x = self[idx]`"""
        #  O(1)
        assert(isinstance(idx, int))
        # add code later to fix negative idx
    #    return self.data[idx]    # calling numpy __get__ 
        idx = self._normalize_idx(idx)  #fixes the negative index
        if idx>=self.size:
            raise IndexError()
        return self.data[idx]
 
    def __setitem__(self, idx, value):
         #  O(1)
        """Implements `self[idx] = x`"""
        assert(isinstance(idx, int))
          # add code later to fix negative idx
        #self.data[idx] =value
        idx = self._normalize_idx(idx)  #fixes the negative index
        if idx>=self.size:
            raise IndexError()
        self.data[idx] =value

    def __delitem__(self, idx):
        """Implements `del self[idx]`"""
        assert(isinstance(idx, int))
        # assume idx is OK, remove element at idx position, move everything down 1
        #  decrement size
        # add code later to fix negative idx
        idx = self._normalize_idx(idx)  #fixes the negative index
        if idx>=self.size:
            raise IndexError()
        else:
            for i in range(idx+1,len(self.data)):   #self.size is the first none
                self.data[i-1]=self.data[i]
            self.data[len(self.data)-1]=None
            self.size-=1
    
    def __len__(self):
        """Implements `len(self)`"""
        return len(self.data)
    
    def __repr__(self):
        """Supports inspection"""
        value='['
        for i in range(self.size):
            value+=str(self.data[i])
            if i<self.size-1:
                value+=', '
        value+=']'
        return value

    def _normalize_idx(self, idx):    #helper method
        # returns the new index
        if idx>=0:
            return idx
        else:
            newIdx = idx+len(self.data)
            if newIdx<0:
                newIdx=0
            return newIdx
        
        
        

m = ArrayList()
m

[]

for x in range(5):
    m.append(x)
m

[0, 1, 2, 3, 4]

m['a']

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-31-4bd6ed298b02> in <module>
----> 1 m['a']

<ipython-input-28-2c871b54ad5f> in __getitem__(self, idx)
     28         """Implements `x = self[idx]`"""
     29         #  O(1)
---> 30         assert(isinstance(idx, int))
     31         # add code later to fix negative idx
     32     #    return self.data[idx]    # calling numpy __get__

AssertionError: 

m[3]=6
len(m)
m

8

[0, 1, 2, 6, 4]

m[10]

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-33-8907169b9e0e> in <module>
----> 1 m[10]

<ipython-input-28-2c871b54ad5f> in __getitem__(self, idx)
     33         idx = self._normalize_idx(idx)  #fixes the negative index
     34         if idx>=self.size:
---> 35             raise IndexError()
     36         return self.data[idx]
     37 

IndexError: 

m[5]

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-34-ce819d42d4fd> in <module>
----> 1 m[5]

<ipython-input-28-2c871b54ad5f> in __getitem__(self, idx)
     33         idx = self._normalize_idx(idx)  #fixes the negative index
     34         if idx>=self.size:
---> 35             raise IndexError()
     36         return self.data[idx]
     37 

IndexError: 

m

[0, 1, 2, 6, 4]

del m[1]
m

[0, 2, 6, 4]

del m[1]
m

[0, 6, 4]

del m[1]
m

[0, 4]

del m[1]
m

[0]

del m[0]
m

[]