Persistent Hashtable for JavaScript (naive)

Hashtable.js

/*
 * 2013 Minori Yamashita <ympbyc@gmail.com>
 * Interim Persistent Hashtable for JavaScript
 * MIT License
 */

module.exports = (function () {
    //CONS CELLS
    function cons (a, d) {
        return [a, d];
    }
    function car (cell) {
        return cell[0];
    }
    function cdr (cell) {
        return cell[1];
    }
    function nil (cell) {
        return cell.length ? false : true;
    }

    //ALISTS
    function assoc (key, list, dflt) {
        if (nil(list)) return dflt || false;
        if (car(car(list)) === key) return car(list);
        return assoc(key, cdr(list), dflt);
    }

    function _alist_to_object (alist, obj) {
        if (nil(alist)) return obj;
        var cell = car(alist),
            key  = car(cell),
            item = cdr(cell);
        if (! obj[key]) obj[key] = item;
        return _alist_to_object(cdr(alist), obj);
    }
    function alist_to_object (alist) {
        return _alist_to_object(alist, {});
    }

    //OBJECTS

    //destructive merge
    function _merge (dst, src) {
        for (k in src)
            if (src.hasOwnProperty(k))
                dst[k] = src[k];
        return dst;
    }
    //pure merge
    function merge (dst, src) {
        var ret = {};
        _merge(ret, dst);
        _merge(ret, src);
        return ret;
    }

    //HASHTABLES
    function Hashtable (obj, size, diff, len) {
        this.data = obj;
        this.data_size = size || Object.keys(obj).length;
        this.diff = diff || [];  //cons cell
        this.diff_length= len || 0;
    }
    Hashtable.prototype = {
        hashtable: true
      , clone_cost_per_diff_length: 1
      , recursion_limit: 256

      //if you prefer...
      , get: function (k, dflt) { return hashtable_get(this, k, dflt);  }
      , add: function (k, val)  { return hashtable_add(this, k, val);   }
    };


    function hashtable (obj) {
        return new Hashtable(obj, Object.keys(obj).length, [], 0);
    }

    function hashtable_add (ht, key, val) {
        if (! ht.hashtable) throw "hashtable_add: not a valid hashtable";
        var ret = new Hashtable(ht.data,
                                ht.data_size,
                                cons(cons(key, val), ht.diff),
                                ht.diff_length + 1);

        if (ret.diff_length > Math.min(ret.data_size * ret.clone_cost_per_diff_length, ret.recursion_limit))
            //move data in the diff alist to data in background once per several turns
            setTimeout(function () {
                ret.data = merge(ret.data, alist_to_object(ret.diff));
                ret.data_size = Object.keys(ret.data).length;
                ret.diff = [];
                ret.diff_length = 0;
            }, 0);

        return ret;
    }

    function hashtable_get (ht, key, dflt) {
        if (! ht.hashtable) throw "hashtable_get: not a valid hashtable";
        var it = assoc(key, ht.diff, false);
        if (it) return cdr(it);
        return ht.data[key] || dflt || false;
    }

    return {
        hashtable: hashtable,
        hashtable_add: hashtable_add,
        hashtable_get: hashtable_get,
        Lists: {
            cons: cons
          , car: car
          , cdr: cdr
          , nil: nil
          , assoc: assoc
          , alist_to_object: alist_to_object
        }
    };
}());

repository.md

https://github.com/ympbyc/PersistentHashtable.js