set.js

gistfile1.js

function Point(x, y)
{
    this.x = x;
    this.y = y;
}

Point.prototype.__hash__ = function()
{
    return hash_int32array([this.x, this.y]);
};

Point.prototype.__eq__ = function(other)
{
    return other instanceof Point && this.x === other.x && this.y === other.y;
};

var FNV_PRIME = 16777619;
var FNV_BASE = 2166136261;

function hash_int32array(arr)
{
    var h = FNV_BASE;

    for(var i = 0; i < arr.length; i++)
    {
        var dword = arr[i];

        h = Math.imul(h, FNV_PRIME);
        h ^= dword & 0xff;
        h = Math.imul(h, FNV_PRIME);
        h ^= dword >> 8 & 0xff;
        h = Math.imul(h, FNV_PRIME);
        h ^= dword >> 16 & 0xff;
        h = Math.imul(h, FNV_PRIME);
        h ^= dword >>> 24;
    }

    return h;
}

var DUMMY_DELETED = {};

function Set()
{
    this.slot_count = 32;
    this.table = Array(this.slot_count);

    this.length = 0;
}

Set.prototype.add = function(element)
{
    if(this.length >= this.slot_count / 2)
    {
        this.resize();
    }

    var h = element.__hash__();
    var mask = this.slot_count - 1;
    var slot_index = h & (this.slot_count - 1);

    for(;;)
    {
        var other = this.table[slot_index];

        if(other === undefined || other === DUMMY_DELETED)
        {
            this.table[slot_index] = element;
            this.length++;
            return;
        }
        else if(other.__eq__(element))
        {
            return;
        }

        slot_index = slot_index + 1 & mask;
    }
};

Set.prototype.has = function(element)
{
    var h = element.__hash__();
    var mask = this.slot_count - 1;
    var slot_index = h & mask;

    for(;;)
    {
        var other = this.table[slot_index];

        if(other === undefined)
        {
            return false;
        }
        else if(element !== DUMMY_DELETED && other.__eq__(element))
        {
            return true;
        }

        slot_index = slot_index + 1 & mask;
    }
};