Efficiently maintain source => target associations.

association.js

// 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);
// }