#!/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 (no 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
#
# 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

# Any reason to keep it ordered if you don't use it here?
# assume order in increasing size
# returns first element >= key or end of list
def findkey(st, key) :
    for i in range(0, len(st)) :
        if st[i][0]>=key : return i
    return len(st)  # where to put it if we can't find it


# 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] = (key, value)
    else :
        st.append(None)       # could be done with fixed length array
        for i in range(len(st)-2, ans-1, -1) :  
            st[i+1] = st[i]
        st[ans] = (key, value)

        
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) :
    for s in st :
        print(s[0], s[1])