#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013

# ensemble performance

# functionality of a symbol table:
# 1. make symbol table
# 2. length of symbol table 
# 3. list of keys
# 4. insert a new item by key (duplicates?)
# 5. retrieve value based on key if not there return default
# 6. remove a specific item by key
# 7. sort the symbol table by the keys
# 8. join one symbol table to another
# 9. print sorted list of keys and values
#
# Q. support duplicate keys with different information or only one copy?
#
# associative memory: LISP, Icon, Perl, Python
#

# implementation: a sorted list of (key, value) pairs

def makesymt() :
    return []

def length(st) :
    return len(st)

def keys(st) :
    ans = []
    for pair in st :
        ans.append(pair[0])
    return ans

# New improved findkey!
# assume order in increasing size
# returns first element >= key or end of list
def findkey(st, key) :
    loc = 0
    if len(st)>0 :
        while loc != None :
            oldloc = loc
            if key < st[loc][0]  : loc = st[loc][2][0]
            elif key > st[loc][0] : loc = st[loc][2][1]
            else  : return loc
        return oldloc
    else :
        return 0

# allow duplicate keys 
def insert(st, key, value) :
    ans = findkey(st, key)
#    print("new key:", ans, st, key, value)
    if ans<len(st) and st[ans][0]==key :
        st[ans][1] = value   # do not change key or links!
    else :
        if len(st)>0 :       # change links?
            if key < st[ans][0]  : 
                st[ans][2][0] = len(st)
            else : 
                st[ans][2][1] = len(st)
        # new node
        st.append([key, value, [None, None]])
        
def retrieve(st, key, default) :
    ans = findkey(st, key)
    if ans<len(st) and st[ans][0]==key :
        return st[ans][1]
    return default

def remove(st, key) :
    ans = findkey(st, key)
    if ans<len(st) and st[ans][0]==key :
        for i in range(ans, len(st)-1) :
            st[i] = st[i+1]
        del(st[len(st)-1])

def comparebykey(item) :
    return item[0]
def comparebyvalue(item) :
    return item[1]

def sortbykeys(st) :
    return st[:]

def sortbyvalues(st) :
    ans = st[:]
    ans.sort(key=comparebyvalue)
    return ans
    
def join(st1, st2) :
    pass # join by sorting together

def printsymbols(st) :
    printsymbolaux(st, 0, "")

# do an infix traversal
def printsymbolaux(st, loc, pre) :
    if st[loc][2][0]!=None : printsymbolaux(st, st[loc][2][0], pre + "  ")
    print(pre, st[loc][0], st[loc][1])
    if st[loc][2][1]!=None : printsymbolaux(st, st[loc][2][1], pre + "  ")

def main() :
    st = makesymt()    
    insert(st, "ant", 11)
    insert(st, "fox", 66)
    insert(st, "cow", 33)
    insert(st, "gnu", 77)
    insert(st, "bat", 22)
    insert(st, "eel", 55)
    insert(st, "dog", 44)
    insert(st, "hog", 88)
    printsymbols(st)

# main()