faster dictionary | Python Fiddle

"""
  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.put('Dave', 1202)  # when Dave is working in the lab
>>> d.lookup('Dave')
1202
>>> d.lookup('CS lab')
1202

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

>>> d2 = Dictionary()
>>> d2.put('Steven', 1203)
>>> d2.lookup('Steven')
1203

>>> p = Dictionary()
>>> p.put(2, "dog")
>>> q = Dictionary()
>>> q.put(1, "cat")
>>> q.put(3, "bird")
>>> p.merge(q)
[(2, 'dog'), (3, 'bird'), (1, 'cat')]

>>> q = Dictionary()
>>> q.put('cat', 123)
>>> q.__repr__()
"{'cat': 123}"

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

>>> 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('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

>>> p = Dictionary()
>>> p.put(2, "dog")
>>> p.put(1, "cat")
>>> p.put(3, "bird")
>>> p.__rep_inv__()
True

#>>> p.__repr__()
#"{1: 'cat', 2: 'dog', 3: 'bird'}"

"""
# 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 Dictionary1faster:
    """
        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(True)
        self.__listOfPairs = []

# "extending" constructor method: 'with'
    #  d.withEntry(k, v) has all the key/value pairs of d, together with a new entry
    # "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(???)
        result = self.__listOfPairs
        position = 0
        for k in result:
            if type(k[0]) != type(1):
                result = [ (key, value) ] + self.__listOfPairs
                return result
        for k in result:
            if key >= k[0]:
                position += 1
        result = self.__listOfPairs[:position] + [ (key, value) ] + self.__listOfPairs[position:]
        return result
    
    def __rep_inv__(self):
        result = self.__listOfPairs
        x = 1
        for k in result:
            key = result[x-1][0]
            for k in result[x:]:
                if key > k[0]:
                    return False
            x += 1
        return True

# 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):
        precondition(True)
        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(True)
        self.__listOfPairs = [ (key, value) ] + self.__listOfPairs

def __eq__(self,otherDictionary):
        precondition( isinstance(otherDictionary,Dictionary1faster) )  
        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):
        precondition( isinstance(otherDictionary,Dictionary1faster) )
        return self.__listOfPairs + otherDictionary.__listOfPairs
  
    def __repr__(self):
        #precondition(???)
        dict = {}
        for x in self.__listOfPairs:
            dict[x[0]] = x[1]
        return str(dict)

class Dictionary2:
    """
        A dictionary represented with a binary tree
    """
    def __init__(self):
        precondition(True)

# "extending" constructor method: 'withEntry'
    #  d.withEntry(k, v) has all the key/value pairs of d, together with a new entry
    def withEntry(self, key, value):
        precondition(True)

# 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):
        precondition(True)

# axioms:
    #  d.put(k, v) --> new d is d.withEntry(k, v)
    def put(self, key, value):
        precondition(True)

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

# axioms:
    #  fill these in
    def merge(self, otherDictionary):
        precondition( isinstance(otherDictionary,Dictionary1faster) )
  
    def __repr__(self):
        precondition(True)

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

# 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 = Dictionary1faster
    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 = Dictionary2
    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