Created
March 22, 2020 15:21
-
-
Save rdpoor/89ea64cb00107be368b2b69d7a89bb6c to your computer and use it in GitHub Desktop.
Efficiently maintain source => target associations.
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
// Efficiently maintain source => target associations. | |
// R. Dunbar Poor - March 2020 | |
var Association = function() { | |
this._links_by_source = new Map(); | |
this._links_by_target = new Map(); | |
} | |
/** | |
* @brief Clear all associations | |
*/ | |
Association.prototype.clear = function() { | |
this._links_by_source.clear(); | |
this._links_by_target.clear(); | |
} | |
/** | |
* @brief Return true if there is a link from source to target | |
*/ | |
Association.prototype.hasLink = function(source, target) { | |
let targets = this._links_by_source.get(source); | |
return targets != undefined && targets.has(target); | |
} | |
/** | |
* @brief Create a link from source to target, unless one already exists. | |
*/ | |
Association.prototype.addLink = function(source, target) { | |
this._add(source, target, this._links_by_source); | |
this._add(target, source, this._links_by_target); | |
} | |
/** | |
* @brief Return an iterator over all the targets of source. | |
*/ | |
Association.prototype.targetsOf = function(source) { | |
return this._of(source, this._links_by_source); | |
} | |
/** | |
* @brief Return an iterator over all the sources of target. | |
*/ | |
Association.prototype.sourcesOf = function(target) { | |
return this._of(target, this._links_by_target); | |
} | |
/** | |
* @brief Return an iterator that generates {source: a, target:b} for all links | |
* in the association. | |
*/ | |
Association.prototype.entries = function*() { | |
for (let [ks, vs] of this._links_by_source.entries()) { | |
for (let [kt, vt] of vs.entries()) { | |
yield {source: ks, target: kt}; | |
} | |
} | |
} | |
// ============================================================================= | |
// internal | |
Association.prototype._add = function(a, b, store) { | |
let set = store.get(a); | |
if (set == undefined) { | |
set = new Set(); | |
store.set(a, set); | |
} | |
set.add(b); | |
} | |
Association.prototype._of = function(a, map) { | |
let b = map.get(a); | |
if (b == undefined) { | |
return []; | |
} else { | |
return b.keys(); | |
} | |
} | |
// ============================================================================= | |
// testing | |
// let assoc = new Association(); | |
// | |
// assoc.addLink('a', 'b'); | |
// assoc.addLink('a', 'c'); | |
// assoc.addLink('a', 'd'); | |
// assoc.addLink('b', 'c'); | |
// assoc.addLink('c', 'd'); | |
// | |
// console.log(assoc.hasLink('a', 'b')); // true | |
// console.log(assoc.hasLink('b', 'a')); // false | |
// console.log(assoc.hasLink('x', 'y')); // false | |
// console.log(Array.from(assoc.targetsOf('a'))); // [b, c, d] | |
// console.log(Array.from(assoc.sourcesOf('a'))); // [] | |
// console.log(Array.from(assoc.targetsOf('b'))); // [c] | |
// console.log(Array.from(assoc.sourcesOf('b'))); // [a] | |
// | |
// for (let v of assoc.entries()) { | |
// console.log(v); | |
// } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment