// Simple and ugly hashtable implementation in javascript.

function is_prime(number)
{
    if (number == 2) {
	return true;
    }
    else {
	var sqrt_number = Math.sqrt(number);
	var divisor = 3;

	if ((number % 2) == 0) {
	    return false;
	}

	while (divisor <= sqrt_number) {
	    if ((number % divisor) == 0) {
		return false;
	    }
	    else {
		divisor += 2;
	    }
	}

	return true;
    }
}

function closest_prime_above(number)
{
    if ((number % 2) == 0) {
	++number;
    }

    while (!is_prime(number)) {
	number += 2;
    }

    return number;
}

function Hashtable(size, unique_id)
{
    this.capacity = closest_prime_above(size);
    this.table = new Array(this.size);
    this.hash_function = function(value) { return (unique_id(value) % this.capacity); };
    this.id = unique_id;

    this.elements_count = 0;

    this.insert = Hashtable_insert;
    this.has_value = Hashtable_has_value;
    this.to_ids_array = Hashtable_to_array;
}

function Hashtable_insert(value)
{
    var hash = this.hash_function(value);

    ++this.elements_count;

    if (this.table[hash] == null) {
	this.table[hash] = new Array(1);
	this.table[hash][0] = this.id(value);
    }
    else {
	this.table[hash].push(this.id(value));
    }
}

function Hashtable_has_value(value)
{
    var hash = this.hash_function(value);

    if (this.table[hash] == null) {
	return false;
    }
    else {
	var length = this.table[hash].length;

	for (var i = 0; i < length; i++) {
	    if (this.table[hash][i] == this.id(value)) {
		return true;
	    }
	}

	return false;
    }
}

function Hashtable_to_array()
{
    var result = new Array(this.elements_count);
    var capacity = this.capacity;
    var index = 0;

    for (var i = 0; i < capacity; i++) {
	if (this.table[i] != null) {
	    var length = this.table[i].length;

	    for (var j = 0; j < length; j++) {
		result[index] = this.table[i][j];
		++index;
	    }
	}
    }

    return result;
}