/*******************************************************************************

    ηMatrix - a browser extension to black/white list requests.
    Copyright (C) 2014-2019 Raymond Hill
    Copyright (C) 2019-2020 Alessio Vanni

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see {http://www.gnu.org/licenses/}.

    Home: https://libregit.spks.xyz/heckyel/ematrix
    uMatrix Home: https://github.com/gorhill/uMatrix
*/

'use strict';

var EXPORTED_SYMBOLS = ['LiquidDict'];

var LiquidDict = function () {
    this.dict = {};
    this.count = 0;
    this.duplicateCount = 0;
    this.bucketCount = 0;
    this.frozenCount = 0;
    this.cutoff = 500;
};

function meltBucket(dict, len, bucket) {
    let map = {};

    --dict.frozenCount;

    if (bucket.charAt(0) === ' ') {
        bucket.trim().split(' ').map(function (e) {
            map[e] = true;
        });
    } else {
        for (let i=0; i<bucket.length; i+=len) {
            map[bucket.substring(i, len)] = true;
        }
    }

    return map;
}

function melt(dict) {
    let buckets = dict.dict;
    for (let key in buckets) {
        let bucket = buckets[key];
        if (typeof bucket === 'string') {
            buckets[key] = meltBucket(dict, key.charCodeAt(0) & 0xFF, bucket);
        }
    }
}

function freezeBucket(dict, bucket) {
    let words = Object.keys(bucket);
    let wlen = words[0].length;

    ++dict.frozenCount;

    if (wlen * words.length < dict.cutoff) {
        return ' ' + words.join(' ') + ' ';
    }

    return words.sort().join('');
}

LiquidDict.prototype.makeKey = function (word) {
    let len = word.length;
    if (len > 255) {
        len = 255;
    }

    let i = len >> 2;
    return String.fromCharCode((word.charCodeAt(0) & 0x03) << 14
                               | (word.charCodeAt(i) & 0x03) << 12
                               | (word.charCodeAt(i+i) & 0x03) << 10
                               | (word.charCodeAt(i+i+i) & 0x03) << 8
                               | len);
};

LiquidDict.prototype.test = function (word) {
    let key = this.makeKey(word);
    let bucket = this.dict[key];

    if (bucket === undefined) {
        return false;
    }

    if (typeof bucket === 'object') {
        return bucket[word] !== undefined;
    }

    if (bucket.charAt(0) === ' ') {
        return bucket.indexOf(' ' + word + ' ') >= 0;
    }

    let len = word.length;
    let left = 0;
    let right = ~~(bucket.length / len + 0.5);

    while (left < right) {
        let i = left + right >> 1;
        let needle = bucket.substr(len * i, len);

        if (word < needle) {
            right = i;
        } else if (word > needle) {
            left = i + 1;
        } else {
            return true;
        }
    }

    return false;
};

LiquidDict.prototype.add = function (word) {
    let key = this.makeKey(word);
    if (key === undefined) {
        return false;
    }

    let bucket = this.dict[key];
    if (bucket === undefined) {
        this.dict[key] = bucket = {};
        ++this.bucketCount;
        bucket[word] = true;
        ++this.count;

        return true;
    } else if (typeof bucket === 'string') {
        this.dict[key] = bucket = meltBucket(this, word.len, bucket);
    }

    if (bucket[word] === undefined) {
        bucket[word] = true;
        ++this.count;

        return true;
    }

    ++this.duplicateCount;

    return false;
};

LiquidDict.prototype.freeze = function () {
    let buckets = this.dict;

    for (let key in buckets) {
        let bucket = buckets[key];
        if (typeof bucket === 'object') {
            buckets[key] = freezeBucket(this, bucket);
        }
    }
};

LiquidDict.prototype.reset = function () {
    this.dict = {};
    this.count = 0;
    this.duplicateCount = 0;
    this.bucketCount = 0;
    this.frozenBucketCount = 0;
}