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

# 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

# fixed size hash table
# EMPTY locations are assigned None
# DELETED locations are assigned the value Deleted
# OTHERWISE (key, value)
# 

# IMPORTANT CONSTANTS:
Deleted = []
Empty = None

def makesymt(size) :
    return array(size, Empty)

def length(st) :
#zzz
    return len(st)

# assume for this exercise the type of the key is a string
mask=2**64-1
def hash(str) :
    if len(str)==0 : return 0        # pick a hash

    h = ord(str[0])<<7
    for i in range(0, len(str)) :
        h = 1000003*h ^ ord(str[i]);
        h = mask & h    # simulate limited size integers
    h ^= len(str);
    return h;


def keys(st) :
    ans = []
    for pair in st :
        if isinstance(pair, tuple) :
#        if pair!=Empty and pair!=Deleted :
            ans.append(pair[0])
    return ans

# allow duplicate keys 
def insert(st, key, value) :
    loc = hash(key)%len(st)
    lastempty = -1
    for k in range(0, len(st)) :
        pair = st[loc]

        if isinstance(pair, tuple) :
            if pair[0]==key :
                lastempty = loc
                break
        elif pair==Empty : 
            if lastempty==-1 : lastempty = loc    
            break
        else : # pair == Deleted   # does it need to be the last empty?  or first emtpy?
            lastempty = loc

        # rehash
        loc += 1   
        if loc>=len(st) : loc = 0

    st[lastempty] = (key, value)
        
def retrieve(st, key, default) :
    loc = hash(key)%len(st)
    while True :
        pair = st[loc]

        if isinstance(pair, tuple) :
            if pair[0]==key :
                return pair[1]
        elif pair==Empty : 
            return None
#        else : # pair == Deleted

        # rehash
        loc += 1   
        if loc>=len(st) : loc = 0

def remove(st, key) :
    loc = hash(key)%len(st)
    while True :
        pair = st[loc]

        if isinstance(pair, tuple) :
            if pair[0]==key :
                value = pair[1] 
                st[loc] = Deleted
                return value
        elif pair==Empty : 
            return None
#        else : # pair == Deleted

        # rehash
        loc += 1   
        if loc>len(st) : loc = 0

def printsymbols(st) :
    for s in st :
        if isinstance(s, tuple) :
            print(s[0], s[1])

def mainget(st) :
    print()
    print(retrieve(st, "ant", 111))
    print(retrieve(st, "bat", 222))
    print(retrieve(st, "cow", 333))
    print(retrieve(st, "dog", 444))
    print(retrieve(st, "eel", 555))
    print(retrieve(st, "fox", 666))
    print(retrieve(st, "gnu", 777))
    print(retrieve(st, "hog", 888))

def main() :
    st = makesymt(10)    
    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)
    mainget(st)
    remove(st, "dog")
    mainget(st)
    insert(st, "dog", 4444)
    mainget(st)
    insert(st, "dog", 44444)
    mainget(st)
    remove(st, "ant")
    remove(st, "fox")
    remove(st, "cow")
    remove(st, "bat")
    remove(st, "dog")
    print(st)
    printsymbols(st)
    print()
    insert(st, "ant", 110)
    insert(st, "fox", 660)
    insert(st, "cow", 330)
    insert(st, "gnu", 770)
    insert(st, "bat", 220)
    insert(st, "eel", 550)
    insert(st, "dog", 440)
    insert(st, "hog", 880)
    printsymbols(st)
    print(st)

main()