import interface Hashable from hash;
import fn hash from hash;
import fn { iterator, next, is_consumed, range } from range;

class HashMap<V, K> {
    buckets: Array<Array<('V [Hashable], 'K)>>;
}

fn<K, V> init(map: @HashMap<'K [Hashable], 'V>, size: Int) {
    let _buckets = map.buckets();
    _buckets.reserve(*size);

    for i in range(0, *size) {
        _buckets.push(arr<('K, 'V)>());
    }
}

fn<K, V> hashmap() -> HashMap<'K [Hashable], 'V> {
    let res = HashMap(arr<Array<('K, 'V)>>());
    res.init(10);

    return move(res);
}

fn<K, V> rehash(map: @HashMap<'K [Hashable], 'V>) {
    let b = map.buckets();
    let size = b.len();

    let aux = HashMap(arr<Array<('K, 'V)>>());
    aux.init(size * 2);

    for bucket in map.buckets() {
        for elem in bucket {
            aux.add(move(elem.get_0()), move(elem.get_1()));
        }
    }

    map.buckets() := move(aux.buckets());
}

fn<K, V> add(map: @HashMap<'K [Hashable], 'V>, key: 'K, value: 'V) {
    let b = map.buckets();
    let size = b.len();
    let pos = hash(*key) % size;

    b[*pos].push((move(key), move(value)));

    if b[*pos].len() > size {
        map.rehash();
    }
}

fn<K, V> get(map: @HashMap<'K [Hashable], 'V>, key: @'K) -> () | @'V {
    let b = map.buckets();
    let size = b.len();
    let pos = hash(*key) % size;

    for i in b[*pos] {
        if i.get_0() == key {
            return i.get_1();
        }
    }

    return ();
}

fn<K, V> contains(map: @HashMap<'K [Hashable], 'V>, key: @'K) -> Bool {
    let b = map.buckets();
    let size = b.len();
    let pos = hash(*key) % size;

    for i in b[*pos] {
        if i.get_0() == key {
            return true;
        }
    }

    return false;
}