lab 5 | Python Fiddle

#Searching a binary tree style dictionary with orderable keys 
#is much faster than searching a sorted list style dictionary 
#or searching an unsorted list (which is even slower). 
#In the lists, the entire length n must be searched. In the binary tree, 
#searching usually only covers about half of the tree. However, altering 
#a binary tree style dictionary is more complicated because inserting or 
#deleting pairs can result in the loss of the parent of two siblings, 
#which must then be repaired.

"""
  Dictionary class, and two implementations

>>> d = Dictionary()
>>> d.put('Dave', 4973)
>>> d.put('J.D.', 4993)
>>> d.put('CS lab', 1202)
>>> d.lookup('Dave')
4973

>>> d = Dictionary()
>>> d.put('Dave', 4973)
>>> d.put('J.D.', 4993)
>>> d.put('CS lab', 1202)
>>> d.lookup('CS lab')
1202

>>> d = Dictionary()
>>> d.put('Dave', 1202)  # when Dave is working in the lab
>>> d.lookup('Dave')
1202

>>> d = Dictionary()
>>> d.lookup('Steven')
'No entry'

>>> d = Dictionary()
>>> d2 = d.withEntry('Steven', 1203)
>>> d.lookup('Steven')
'No entry'

>>> d = Dictionary()
>>> d2 = d.withEntry('Steven', 1203)
>>> d2.__repr__()
"[('Steven', 1203)]"

>>> q = Dictionary()
>>> q.put('cat', 123)
>>> q.__repr__()
[('cat', 123)]

>>> p = Dictionary()
>>> p.put('fish', 456)
>>> q = Dictionary()
>>> q.put('cat', 123)
>>> q.merge(p)
>>> q.__repr__()
[('cat', 123), ('fish', 456)]

>>> p = Dictionary()
>>> p.put('fish', 1)
>>> q = Dictionary()
>>> q.put('fish', 1)
>>> p.__eq__(q)
True

>>> p = Dictionary()
>>> q = Dictionary()
>>> p.__eq__(q)
True

>>> p = Dictionary()
>>> p.put('cat', 1)
>>> p.put('cat', 2)
'error, key already in use'

>>> p = Dictionary()
>>> p.put('fish', 1)
>>> q = Dictionary()
>>> q.put('fish', 2)
>>> p.__eq__(q)
False

>>> p = Dictionary()
>>> p.put('fish', 1)
>>> q = Dictionary()
>>> q.put('wish', 1)
>>> p.__eq__(q)
False
"""
# make Python look in the right place for logic.py, or complain if it doesn't
try:
    import sys
    sys.path.append('/home/courses/python')
    from logic import *
except:
    print "Can't find logic.py; if this happens in the CS teaching lab, tell your instructor"
    print "   If you are using a different computer, add logic.py to your project"
    print "   (You can download logic.py from http://www.cs.haverford.edu/resources/software/logic.py)"
    sys.exit(1)

class Dictionary1:

#A dictionary represented with a Python list.
        #Each list element is a tuple of two parts, the key and the value

def __init__(self):
        #precondition self is Dictionary object
        self.__listOfPairs = []

# "extending" constructor method: 'with'
    #  d.withEntry(k, v) has all the key/value pairs of d, together with a new entry
    def withEntry(self, key, value):
        #precondition self is Dictionary object
        result = Dictionary1()
        result.__listOfPairs = [ (key, value) ] + self.__listOfPairs
        return result

# axioms:
    #  Dictionary().lookup(x) === "No entry"
    #  d.withEntry(k, v).lookup(x) === v, if k==x
    #                          or d.lookup(x), otherwise
    def lookup(self, key):
        #complexity = linear (n)
        #precondition self is Dictionary object
        for pair in self.__listOfPairs:
            if pair[0] == key:
                return pair[1]
        return "No entry"

# axioms:
    #  d.put(k, v) --> new d is d.withEntry(k, v)
    def put(self, key, value):
        #precondition self is Dictionary object
        for k in self.__listOfPairs:
            if k[0] == key:
                return "error, key already in use"
        self.__listOfPairs = [ (key, value) ] + self.__listOfPairs

def __eq__(self,otherDictionary):
        #complexity = linear (n, due to list of pairs adding one thing on at a time)
        precondition( isinstance(otherDictionary,Dictionary1) )  
        if self.__listOfPairs != otherDictionary.__listOfPairs:
            return False
        return True

# axioms:
    #  Dictionary().put(x, a).merge((Dictionary().put(y, b))) === Dictionary().put(x, a).put(y, b)
    def merge(self, otherDictionary):
        #complexity = constant (since the __listOfPairs method is also constant)
        precondition( isinstance(otherDictionary,Dictionary1) )
        self.__listOfPairs = self.__listOfPairs + otherDictionary.__listOfPairs
  
    def __repr__(self):
        #complexity = linear (n = len(self.listOfPairs))
        dict = []
        for x in self.__listOfPairs:
            dict += [(x[0], x[1])]
        return dict

class node:
    def __init__(self, ltree, top, rtree):
        self.top = top
        self.ltree = ltree
        self.rtree = rtree

def __repr__(self):
        return str(self.top)
    
class BT(node):
 # constructor: a BT is either empty, or
 # a top node (root) connected to two (sub)BTs
 # primitive: BT()
 # extending: BT(l, t, r)
    def __init__(self, left=None, top=None, right=None):
        #inputs must be tuples to store key and value
        #NOTE: preconditions below are commented out in order to not conflict with the existing doctest (which does not use tuples as parameters)
        #precondition(type(left) == type(right) == type(top) == type([(1, "a")]) and len(left) == len(right) == len(top) == 1 and len(left)[0] == len(right)[0] == len(top)[0] == 2)
        #precondition: left[0][0] and right[0][0] and top[0][0] are keys, left[0][1] and right[0][1] and top[0][1] are values
        if top == None: # primitive
            self.rep = None
        else: # extending
            self.rep = node(left, top, right)
            
    def withEntry(self, key, value):
        #precondition self is Dictionary object
        return node([], [(key, value)], [])

# axioms:
 # empty(BT()) === True
 # empty(BT(l, t, r)) === False
    def empty(self):
        return self.rep == None
 # axioms:
 # root(BT()) === undefined
 # root(BT(l, t, r)) === t
    def root(self):
        precondition(not self.empty())
        return self.rep.top
 # axioms:
 # left(BT()) === undefined
 # left(BT(l, t, r)) === l
    def left(self):
        precondition(not self.empty())
        return self.rep.ltree

# axioms:
 # right(BT()) === undefined
 # right(BT(l, t, r)) === r
    def right(self):
        precondition(not self.empty())
        return self.rep.rtree
 # print with inorder traversal

# size function for binary trees;
 # should work on any representation
 # of a binary tree
    def size(self):
        if self.empty():
            return 0
        else:
            return self.left().size() + self.right().size() + 1
 # preorder traversal
    def preorder(self, f):
        if not self.empty():
            f(self.root())
            self.left().preorder(f)
            self.right().preorder(f)

# inorder traversal
    def inorder(self, f):
        if not self.empty():
            self.left().inorder(f)
            f(self.root())
            self.right().inorder(f)

# postorder traversal
    def postorder(self, f):
        if not self.empty():
            self.left().postorder(f)
            self.right().postorder(f)
            f(self.root())
    #complexity (not counting rep invariant) = log(n)        
    def __repr__(self): 
        #inorder traversal  
        a =[]
        if not self.empty():
            if not self.left().empty():
                a += self.left().__repr__()
            if not self.empty():
                a += [(self.root()[0][0], self.root()[0][1])]
            if not self.right().empty():
                a += self.right().__repr__()
        return a

# BSTD inherits from BT, you get for free:
# - constructors
# - accessors:
# - empty(), root(), left() & right()
# - display traversals:
# - pre, in, and postorder
class BSTD(BT):
    def rep_invariant(self):
        if self.empty():
            return True
        elif not self.left().empty():
            if self.left().root()[0][0] >= self.root()[0][0]:
                return False
        elif not self.right().empty():
            if self.right().root()[0][0] <= self.root()[0][0]:
                return False
        if self.left().rep_invariant() and self.left().rep_invariant():
            return True

# insert mutator without allowing duplicates
    def put(self, k, v):
        if self.empty():
            self.rep = node(BSTD(), [(k,v)], BSTD())
        elif k == self.root()[0][0]: # duplicate key protocol
            return 'error, key already in use'
        elif k < self.root()[0][0]: # insert to the left
            self.left().put(k, v)
        else:
            self.right().put(k, v)
        if not self.rep_invariant():
            return "error, not in order"
            
    #complexity (not counting rep invariant) = log(n)
    def __eq__(self, otherDictionary):
        if not self.rep_invariant():
            return "error, not in order"
        if self.empty and otherDictionary.empty():
            return True
        elif self.empty() or otherDictionary.empty():
            return False
        else:
            if not self.left().empty() and not otherDictionary.left().empty():
                self.left().__eq__(otherDictionary.left())
            if self.root()[0] != otherDictionary.root()[0]:
                return False
            if not self.right().empty() and not otherDictionary.right().empty():
                self.right().__eq__(otherDictionary.right())
        return True
        
        
    #complexity (not counting rep invariant) = log(n)
    def merge(self, otherDictionary):
        if otherDictionary.empty():
            return self.rep     
        self.put(otherDictionary.root()[0][0], otherDictionary.root()[0][1])
        self.merge(otherDictionary.left())
        self.merge(otherDictionary.right())
        if not self.rep_invariant():
            return "error, not in order"

def lookup(self, key):
        if not self.rep_invariant():
            return "error, not in order"
        if self.empty():
            return "No entry"
        elif self.root()[0][0] == key:
            return self.root()[0][1]
        elif self.root()[0][0] > key:
            return self.left().lookup(key)
        elif self.root()[0][0] < key:
            return self.right().lookup(key)

"""
class Dictionary2:

#A dictionary represented with a binary search tree

def __init__(self, root):
        precondition(True)
        self.root = [root]

def right(self, right_tree):
        self.right = [right_tree]
        return self.root + self.right
    
    def right(self, left_tree):
        self.left = [left_tree]
        return self.left + self.root

def withEntry(self, key, value):
        precondition(True)

def lookup(self, key):
        precondition(True)

def put(self, key, value):
        precondition(True)

def __eq__(self,otherDictionary):
        precondition( isinstance(otherDictionary,Dictionary1) )

# axioms:
    #  fill these in
    def merge(self, otherDictionary):
        precondition( isinstance(otherDictionary,Dictionary1) )
  
    def __repr__(self):
        precondition(True)
        dict = {}
        for x in self.__listOfPairs:
            dict[(x[0])] = x[1]
        return str(dict)

"""

# by default, use the first representation, but this is changed in DocTest below
Dictionary = Dictionary1

# mostly copied from  http://docs.python.org/lib/module-doctest.html
def _test():
    import doctest
    global Dictionary
    whatever_dictionary_was = Dictionary

print "=========================== Running doctest tests for Dictionary1 ===========================\n"
    Dictionary = Dictionary1
    result = doctest.testmod()
    if result[0] == 0:
        print "Wahoo! Passed all", result[1], __file__.split('/')[-1],  "tests!"
    else:
        print "Rats!"

print "\n\n\n\n"
    print "=========================== Running doctest tests for Dictionary2 ===========================\n"
    Dictionary = BSTD
    result = doctest.testmod()
    if result[0] == 0:
        print "Wahoo! Passed all", result[1], __file__.split('/')[-1],  "tests!"
    else:
        print "Rats!"
    Dictionary = whatever_dictionary_was

if __name__ == "__main__":
    _test()

Python Fiddle

Python Cloud IDE