Abstract Data Types (ADTs)¶

In [1]:
import numpy as np
import matplotlib.pyplot as plt

API: Application programming interface Bare bones description of some functionality (e.g. A header file in C++)

  • The parameters to a method, as well as the return type/information
  • No implementation details about the functionality

ADT: API specalized to a data container of some type

Set ADT¶

A set is a collection of object, in no particular order, without repetition

Ex) myset = {2, 7, 1, 17, 7, 3}

Set ADT:

  • void add(obj): Add our object to the set if it doesn't exist, or do nothing if it's already there
  • bool contains(obj): Return True if obj is in the set, or False otherwise
  • void remove(obj): Remove obj from the set if it's there, or throw an exception if it's not there

A data structure is an underlying implementation that realizes and ADT.

We'll start with an unordered array as the underlying data

In [13]:
class ArraySet:
    def __init__(self):
        self.arr = np.array([]) # Numpy array is fixed in size
        # Behaves more like a Java/C++ array; if we want to add
        # or remove something from the array, we have to create
        # an entirely new array of a different size and fill that in
    
    def __contains__(self, obj):
        found = False
        i = 0
        while i < len(self.arr) and not found:
            if self.arr[i] == obj:
                found = True
            else:
                i += 1
        return found
    
    def add(self, obj):
        # if not self.__contains__(obj):
        if not obj in self:
            ## Step 1: Make an array that's one bigger
            N = len(self.arr)
            new_arr = np.zeros(N+1) # Make an array of all 0's that 
            # has one extra element
            
            ## Step 2: Copy everything over from the original array
            for i in range(N):
                new_arr[i] = self.arr[i]
                
            ## Step 3: Add this new object to the end
            new_arr[N] = obj
            
            self.arr = new_arr
        
    
    def remove(self, obj):
        # if not self.__contains__(obj):
        if not obj in self:
            raise KeyError("Cannot remove non-existant object {}".format(obj))
            
myset = ArraySet()
# {2, 7, 1, 17, 7, 3}
for x in [2, 7, 1, 17, 7, 3]:
    myset.add(x)

print(2 in myset)
print(7 in myset)
print(100 in myset)

True
True
False
In [ ]: