import vector
import structures_lib
import association

type Iterator = {
    reset->Void
    hasNext->Boolean
    get->T
    next->T}

type Association = {
    ==(_:Association)->Boolean
    hashcode->Number
    getValue->V
    getKey->K
    setValue(_:V)->V
    asString->String}

type Collection = {
    size->Number
    isEmpty->Boolean
    clear->Void
    contains(_:T)->Boolean
    addFirst(_:T)->Void
    addLast(_:T)->Void
    firstElement->T
    lastElement->T
    removeFirst->T
    removeLast->T
    removeValue(_:T)->Dynamic
    indexOf(_:T)->Number
    at(_:Number)->T
    setValue(_:T)at(_:Number)->T
    add(_:T)at(_:Number)->Void
    removeFromIndex(_:Number)->T
    iterator->Iterator
    asString->String
    forEachDo(_:Block)->Void
    map(_:Block)->Collection}

type Vector = {
    size->Number
    isEmpty->Boolean
    clear->Void
    contains(_:T)->Boolean
    addFirst(_:T)->Void
    addLast(_:T)->Void
    firstElement->T
    lastElement->T
    removeFirst->T
    removeLast->T
    removeValue(_:T)->Dynamic
    indexOf(_:T)->Number
    at(_:Number)->T
    setValue(_:T)at(_:Number)->T
    add(_:T)at(_:Number)->Void
    removeFromIndex(_:Number)->T
    iterator->Iterator
    asString->String
    forEachDo(_:Block)->Void
    map(_:Block)->Collection
    ensureCapacity(_:Number)->Void
    capacity->Number
    copyInto(_)->Void
    indexOf(_:T)startingFrom(_:Number)->Number
    setSize(_:Number)->Void
    trimToSize->Void}

type Map = {
    size->Number
    isEmpty->Boolean
    containsKey(_:K)->Boolean
    containsValue(_:V)->Boolean
    valueAt(_:K)->V
    put(_:V)at(_:K)->V
    removeValueAt(_:K)->V
    putAll(_:Map)->Void
    clear->Void
    keySet->Set
    values->Collection
    entrySet->Set
    asString->String}

type Set = {
    clear->Void
    isEmpty->Void
    add(_:T)->Void
    removeValue(_:T)->T
    contains(_:T)->Boolean
    containsAll(_:Set)->Boolean
    clone->Set
    addAll(_:Set)->Void
    retainAll(_:Set)->Void
    removeAll(_:Set)->Void
    iterator->Iterator
    size->Number
    asString->String}

def missing is public, readable = object{
    method asString->String{"-"}
}

// Constructs hashtable with capacity cap before chaining
method withSize(cap:Number)->Map is public{ChainedHashtable.new(cap)}

// Constructs reasonably large hashtable
method new->Map is public{ChainedHashtable.new(997)}

class ChainedHashtable.new(cap:Number){

    // array of chains used to store values
    var data:Vector is readable := 
        vector.withSize(cap)increment(0)
            initialVal(structures_lib.newList)

    data.setSize(cap)

    // number of key-value pairs stored in table
    var count:Number is readable := 0

    // @post removes all elements from hashtable
    method clear->Void is public{
        data.map{list-> list.clear}
        count := 0}

    // @post @return number of elements stored in hashtable
    method size->Number is public{count}

    // @post @return true iff no elements stored in hashtable
    method isEmpty->Boolean is public{size == 0}

    // @post @return the list in the table associated with key
    method locate(key:Dynamic)->Collection is confidential{
       var hash:Number := (key.hashcode % data.size) + 1
        if(data.at(hash).isEmpty) then {
            data.setValue(structures_lib.newList)at(hash)}
        return data.at(hash)}

    // @pre value is not "missing"
    // @post @return true iff hashtable contains value
    // @param value the value sought  
    method containsValue(value:Dynamic)->Boolean is public{values.contains(value)}

    // @pre value is not "missing"
    // @post @return true iff key appears in hashtable
    // @param key is key sought 
    method containsKey(key:Dynamic)->Boolean is public{
        var l:Collection := locate(key)
        return l.contains(association.withKey(key))}

    // @post @return set of keys that appear in hashtable
    method keySet->Set is public{
        var result:Set := structures_lib.newSet
        var i:Iterator := association.keyIterator(ChainedHashtableIterator.new(data))
        while{i.hasNext} do {result.add(i.next)}
        return result}

    // @post @return set of associations in hashtable
    method entrySet->Set is public{
        var result:Set := structures_lib.newSet
        var i:Iterator := ChainedHashtableIterator.new(data)
        while{i.hasNext} do {result.add(i.next)}
        return result}

    // @post @return list of values contained in hashtable
    method values->Collection is public{
        var result:Collection := structures_lib.newList
        var i:Iterator := association.valueIterator(ChainedHashtableIterator.new(data))
        while{i.hasNext} do {result.addLast(i.next)}
        return result}

    // @pre key is not "missing"
    // @post @return value associated with key, or missing
    // no such key
    // @param key the key used to find desired value
    method valueAt(key:Dynamic)->Dynamic is public{
        var l:Collection := locate(key)
        var a:Dynamic := l.removeValue(association.withKey(key))
        match(a)
            case{rmd:Association-> 
                l.addFirst(rmd)
                return rmd.getValue}
            case{_-> return missing}
    }

    // @pre key is not "missing"
    // @post key-value pair added to hashtable
    // @param key the key to be added
    // @param value the value associated with key
    // @return the value formerly associated with key, if
    // previously present
    method put(value:Dynamic)at(key:Dynamic)->Dynamic is public{
        var l:Collection := locate(key)
        var newa:Association := association.withKey(key)value(value)
        var olda:Dynamic := l.removeValue(newa)
        l.addFirst(newa)
        match(olda)
            case{rmd:Association-> return olda.getValue}
            case{_-> 
                count := count + 1
                return missing}
    }

    // @pre key is not "missing"
    // @post removes key-value pair associated w/key
    // @param key the key of the key-value pair to be removed
    // @return the value associated with the removed key
    method removeValueAt(key:Dynamic)->Dynamic is public{
        var l:Collection := locate(key)
        var pair:Association := l.removeValue(association.withKey(key))
        match(pair)
            case{rmd:Association->
                count := count - 1
                return rmd.getValue}
            case{_-> return missing}
    }

    // @post all key-value pairs in other are placed in this map,
    // potentially overwriting existing values with same keys
    // @param other the map to copy into this map
    method putAll(other:Map)->Void is public{
        var i:Iterator := other.entrySet.iterator
        while{i.hasNext} do{
            var e:Association := i.next
            put(e.getValue)at(e.getKey)}
    }

    // @post @return string representation of hashtable
    method asString->String is public{
        var s:String := " := ChainedHashtableIterator.new(data)
        while{hi.hasNext} do{
            var a:Association := hi.next
            s := s ++ " {a.getKey}={a.getValue}"}
        s := s ++ ">"
        return s}
}


// Iterator to traverse entries of a hashtable
// @param table the vector containing the hashtable's data
class ChainedHashtableIterator.new(table:Vector){

    var data:Collection is readable := structures_lib.newList

    for(1..table.size) do {i->
        if(!table.at(i).isEmpty) then{
            var entry:Collection := table.at(i)
            entry.forEachDo{a-> data.addFirst(a)}
        }
    }

    var elements:Iterator := data.iterator

    method reset->Void is public{elements.reset}

    method hasNext->Boolean is public{elements.hasNext}

    method next->Association is public{elements.next}

    method get->Association is public{elements.get}
}