
+ class HashMap[K, T] {
    - _keys: Array[K] (.{})
    - zones: Array[?FlatMap[K, T]] (.{})

    + static fn new() SELF {
        return SELF{}
    }

    + macro "{" repeat(items, ws V:v1 ws "=>" ws V:v2 ws optional(",") ws, "}")
    <{
    	let m = SELF.new()
    	#loop macro_values items as item
    	m.set(item.v1, item.v2)
    	#end
    	return m
    }

    + get length : uint {
        return this._keys.length
    }
    + fn keys() Array[K] {
        return this._keys.copy()
    }
    + fn sort_keys() SELF {
        this._keys.sort()
        return this
    }
    + fn values() Array[T] {
        let values = Array[T].new(this.length)
        each this.zones as zone {
            if isset(zone) : values.append_many(zone._values)
        } 
        return values
    }

    static fn zone_index(key: K) uint {
        #if type_has_method(K, map_hash)
        return key.map_hash() % 128
        #else
        return key.@cast(uint) % 128
        #end
    }
    fn zone(key: K) FlatMap[K, T] {
        let i = SELF.zone_index(key)
        let zone = this.zones.get(i) !? null
        if !isset(zone) {
            let z = FlatMap[K, T].new()
            this.zones.set_expand(i, z, null)
            return z
        }
        return zone
    }

    + mut fn set(key: K, value: T) SELF $offset_assign {
        let zone = this.zone(key)

        let index = zone._keys.index_of(key) ! {
            this._keys.append(key)
            zone._keys.append(key)
            zone._values.append(value)
            return this
        }
        zone._values.set(index, value) _

        return this
    }

    + mut fn set_unique(key: K, value: T) SELF {
        let zone = this.zone(key)
        zone._keys.index_of(key) ! {
            this._keys.append(key)
            zone._keys.append(key)
            zone._values.append(value)
        }
        return this
    }

    + fn get(key: K) T !not_found $offset {
        let zone = this.zone(key)
        return zone.get(key) ! throw not_found
    }

    + fn has(key: K) bool {
        let zone = this.zone(key)
        return zone.has(key)
    }
    + fn has_value(value: T) bool {
        each this.zones as zone {
            if isset(zone) && zone.has_value(value) : return true
        }
        return false
    }

    + mut fn remove(key: K) SELF {
        let zone = this.zone(key)
        zone.remove(key)
        this._keys.remove_value(key)
        return this
    }

    + mut fn clear() SELF {
        this.zones.clear()
        this._keys.clear()
        return this
    }

    + fn merge(map: SELF) SELF $add {
        each map as v, k : this.set(k, v)
        return this
    }

    + fn copy() SELF {
        return SELF{
            _keys: this._keys.copy()
            zones: this.zones.copy()
        }
    }

    fn each_get(index: uint) (T, K) !end {
        let k = this._keys.get(index) ! throw end
        return (this.get(k) ! throw end), k
    }
}
