import { defaultToString } from '../util';
import { ValuePairLazy } from './models/value-pair-lazy';

/**
 * HashTable：Dictionary类的一种散列表实现，也叫HashMap。区别就是HashTable用hash值作为键，并且可以相同key不同value
 * 线性探查法将每个元素都存储在表中，而不是借助链表等外物来解决冲突。当想向表中某个位置添加一个新元素的时候，
 * 如果索引为index的位置已经被占据了，就尝试index+1的位置，如果这个位置也被占据就尝试下一个直至找到空闲的位置
 * 它有个问题：删除时会用一个字段记录删除状态而不是真正的删除它，在查询时可能会查询很多位置的这个字段导致效率变慢
 * 要解决这个问题可查看hash-table-linear-probing.ts这个类。
 */

export default class HashTableLinearProbingLazy<K, V> {
    private _toStrFn: (key: K) => string;
    private _table: { [key: string]: ValuePairLazy<K, V> };
    constructor(toStrFn: (key: K) => string = defaultToString) {
        this._table = {};
        this._toStrFn = toStrFn;
    }
    /**
     * 散列函数1
     */
    private loseloseHashCode(key: K): number {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this._toStrFn(key);
        let hash = 0;
        for (let i = 0, le = tableKey.length; i < le; i ++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }
    /**
     * 散列函数2
     * 一个表现良好的散列函数由几个方面构成：
     * 插入和检索元素的时间（即性能），以及较低的冲突可能性。
     */
    /* private djb2HashCode(key: K) {
        const tableKey = this._toStrFn(key);
        let hash = 5381;
        for (let i = 0; i < tableKey.length; i ++) {
            hash = (hash * 33) + tableKey.charCodeAt(i);
        }
        return hash % 1013;
    } */
    /**
     * 得到key对应的hash值，这个hash值会作为hashtable的键
     */
    public hashCode(key: K): number {
        // return this.djb2HashCode(key); // 使用更好的散列函数
        return this.loseloseHashCode(key);
    }
    /**
     * 向HashTable中添加新元素。如果某个位置可用（位置没有被用过或者已经被删除）就可以插入新元素，
     * 否则会在它下一个位置（位置没有被用过或者已经被删除）插入该项，如果下个位置也不可用就再找
     * 下一个位置直至找到新位置就插入新元素
     */
    public put(key: K, value: V): boolean {
        if (key != null && value != null) {
            const tableKey: number = this.hashCode(key);
            // 这个位置没有被用过或者已经被删除，就可以插入新元素
            if (this._table[tableKey] == null || this._table[tableKey].isDeleted) {
                this._table[tableKey] = new ValuePairLazy<K, V>(key, value);
            } else { // 需要向下一个位置进发
                let index: number = tableKey + 1;
                // 该位置被占了（isDeleted为false），那就找出下一个可用的位置
                while (this._table[index] != null && !this._table[index].isDeleted) {
                    index ++;
                }
                this._table[index] = new ValuePairLazy<K, V>(key, value);
            }
            return true;
        }
        return false;
    }
    /**
     * 通过以键值作为参数查找对应的值并返回
     * 情况复杂：
     * 1.哈希值所在的位置key相同并且没被删除就返回这个value，否则去下一个位置查找。 {1}
     * 2.下一个位置key相同并且也没被删除就返回这个value。否则只能去寻下下个位置了。{4}
     * 3.但是下一个位置key相同并且被删除就直接return undefined {2}
     * 4.一直找但key一直不相同（删不删除无所谓），就一直找，直到没有元素了（this._table[index]为空） {3}
     */
    public get(key: K): V {
        if (key == null) { // 参数不合法
            return undefined;
        }
        const tableKey: number = this.hashCode(key);
        if (this._table[tableKey] == null) { // 因为是线性，这个为空证明下面的也没有，直接返回undefined
            return undefined;
        }
        // key相同，并且没被删除 {1}
        if (this._table[tableKey].key === key && !this._table[tableKey].isDeleted) {
            return this._table[tableKey].value;
        } else {
            let index: number = tableKey + 1;
            while (this._table[index] != null && (this._table[index].key !== key
                || this._table[index].isDeleted)) {
                // 情况1：key相同并且被删除。是我们找的key，但被删除了那就直接return undefined {2}
                if (this._table[index].key === key && this._table[index].isDeleted) {
                    return undefined;
                }
                index ++; // 情况2：key不相同，删不删除无所谓。此时必须找下一个位置以保证拿到相同key {3}
            }
            // 情况3：key相同并且没被删除或者this._table[index]根本就为空 {4}
            return this._table[index] != null ? this._table[index].value : undefined;
        }
    }
    /**
     * 通过键来删除字典中对应的键值对
     * 情况复杂：
     * 1.哈希值所在的位置key相同并且没被删除就返回这个value，否则去下一个位置查找。 {1}
     * 2.下一个位置key相同并且也没被删除就返回这个value。否则只能去寻下下个位置了。{4}
     * 3.但是下一个位置key相同并且被删除就直接return undefined {2}
     * 4.一直找但key一直不相同（删不删除无所谓），就一直找，直到没有元素了（this._table[index]为空） {3}
     */
    public remove(key: K): boolean {
        if (key == null) { // 参数不合法
            return false;
        }
        const tableKey: number = this.hashCode(key);
        if (this._table[tableKey] == null) { // 因为是线性，这个为空证明下面的也没有，直接返回fasle
            return false;
        }
        // key相同，并且没被删除 {1}
        if (this._table[tableKey].key === key && !this._table[tableKey].isDeleted) {
            this._table[tableKey].isDeleted = true;
            return true;
        } else {
            let index: number = tableKey + 1;
            while (this._table[index] != null && (this._table[index].key !== key
                || this._table[index].isDeleted)) {
                // 情况1：key相同并且被删除。是我们找的key，但被删除了那就直接return false {2}
                if (this._table[index].key === key && this._table[index].isDeleted) {
                    return false;
                }
                index ++; // 情况2：key不相同，删不删除无所谓。此时必须找下一个位置以保证拿到相同key {3}
            }
            // 情况3：key相同并且没被删除 {4}
            if (this._table[index] != null) {
                this._table[index].isDeleted = true;
                return true;
            }
            return false; // this._table[index]为空, 没有删除的东西
        }
    }
    /**
     * hashtable大小，把hashtable中每一个key对应的链表中所有项相加
     */
    public size(): number {
        let count = 0;
        Object.values(this._table).forEach(
            (valuePairLazy: ValuePairLazy<K, V>) => {
                if (!valuePairLazy.isDeleted) { // 统计没被删除的
                    count ++;
                }
            });
        return count;
    }
    /**
     * hashtable是否为空
     */
    public isEmpty(): boolean {
        return this.size() === 0;
    }
    /**
     * 返回hashtable
     */
    public getTable(): { [key: string]: ValuePairLazy<K, V> } {
        return this._table;
    }
    /**
     * 清空hashtable
     */
    public clear() {
        this._table = {};
    }
    /**
     * 返回hashtable的字符串形式
     */
    public toString(): string {
        if (this.isEmpty()) {
            return '';
        }
        const keys = Object.keys(this._table);
        let objString = `{${keys[0].toString()} => ${this._table[keys[0]].toString()}}`;
        for (let i = 1; i < keys.length; i ++) {
            objString = `${objString},{${keys[i].toString()} => ${this._table[keys[i]].toString()}}`;
        }
        return objString;
    }
}