Last active
December 15, 2015 11:49
-
-
Save ympbyc/5256052 to your computer and use it in GitHub Desktop.
Persistent Hashtable for JavaScript (naive)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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 | |
} | |
}; | |
}()); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment