class HashMap[K: Hash + Equals, V] {
    // BitSet.size == capacity * 2
    // [bit 0: inserted; bit 1: deleted] * capacity
    var inserted_and_deleted: BitSet = nil;
    var keys: Array[K] = nil;
    var values: Array[V] = nil;
    var size: Int = 0;
    var capacity: Int = 0;

    fun insert(key: K, value: V) {
        self.ensureCapacity(1);
        assert(self.size < self.capacity);

        var hash = key.hash();
        var idx = hash & (self.capacity - 1);

        while true {
            if self.isLive(idx) {
                let current_key = self.keys.get(idx);

                if current_key.hash() == hash && current_key.equals(key) {
                    self.values.set(idx, value);
                    return;
                }

            } else {
                self.inserted_and_deleted.insert(2 * idx);
                self.inserted_and_deleted.remove(2 * idx + 1);

                self.keys.set(idx, key);
                self.values.set(idx, value);

                self.size = self.size + 1;
                return;
            }

            idx = (idx + 1) & (self.capacity - 1);
        }
    }

    fun contains(key: K) -> Bool {
        assert(self.size < self.capacity);

        var hash = key.hash();
        var idx = hash & (self.capacity - 1);

        while true {
            if self.isLive(idx) {
                let current_key = self.keys.get(idx);

                if current_key.hash() == hash && current_key.equals(key) {
                    return true;
                }
            } else {
                break;
            }

            idx = (idx + 1) & (self.capacity - 1);
        }

        return false;
    }

    fun get(key: K) -> V {
        assert(self.size < self.capacity);

        var hash = key.hash();
        var idx = hash & (self.capacity - 1);

        while true {
            if self.isLive(idx) {
                let current_key = self.keys.get(idx);

                if current_key.hash() == hash && current_key.equals(key) {
                    return self.values.get(idx);
                }
            } else {
                break;
            }

            idx = (idx + 1) & (self.capacity - 1);
        }

        return defaultValue[V]();
    }

    fun remove(key: K) -> V {
        self.shrink();

        var hash = key.hash();
        var idx = hash & (self.capacity - 1);

        while true {
            if self.isLive(idx) {
                let current_key = self.keys.get(idx);

                if current_key.hash() == hash && current_key.equals(key) {
                    let value = self.values.get(idx);
                    self.inserted_and_deleted.insert(2 * idx + 1);

                    self.keys.set(idx, defaultValue[K]());
                    self.values.set(idx, defaultValue[V]());

                    self.size = self.size - 1;
                    return value;
                }
            } else {
                break;
            }

            idx = (idx + 1) & (self.capacity - 1);
        }

        return defaultValue[V]();
    }

    fun ensureCapacity(elements_to_add: Int) {
        if self.size + elements_to_add < self.capacity {
            if self.size <= (self.capacity - (self.capacity / 4)) {
                return;
            }
        }

        var new_capacity = 4;
        let old_capacity = self.capacity;

        if old_capacity > 0 {
            new_capacity = old_capacity * 2;
        }

        assert(self.size + elements_to_add < new_capacity);

        self.rehash(new_capacity);
    }

    fun shrink() {
        if self.size > (self.capacity / 4) {
            return;
        }

        let new_capacity = self.capacity / 2;

        if new_capacity < 4 {
            return;
        }

        assert(self.size < new_capacity);

        self.rehash(new_capacity);
    }

    fun rehash(new_capacity: Int) {
        let old_capacity = self.capacity;

        let new_map = HashMap[K, V]();
        new_map.inserted_and_deleted = BitSet(2 * new_capacity);
        new_map.keys = Array[K](new_capacity);
        new_map.values = Array[V](new_capacity);
        new_map.size = 0;
        new_map.capacity = new_capacity;

        var idx = 0;

        while idx < old_capacity {
            if self.isLive(idx) {
                let key = self.keys.get(idx);
                let value = self.values.get(idx);

                new_map.insert(key, value);
            }

            idx = idx + 1;
        }

        self.inserted_and_deleted = new_map.inserted_and_deleted;
        self.keys = new_map.keys;
        self.values = new_map.values;
        self.size = new_map.size;
        self.capacity = new_capacity;
    }

    fun isLive(idx: Int) -> Bool {
        return self.inserted_and_deleted.contains(2 * idx) &&
               !self.inserted_and_deleted.contains(2 * idx + 1);
    }

    fun len() -> Int {
        return self.size;
    }

    fun capacity() -> Int {
        return self.capacity;
    }
}