File Explorer

1/* eslint no-constant-condition: 0 */2/**3 * Mnemonist StaticDisjointSet4 * ============================5 *6 * JavaScript implementation of a static disjoint set (union-find).7 *8 * Note that to remain performant, this implementation needs to know a size9 * beforehand.10 */11var helpers = require('./utils/typed-arrays.js');12 13/**14 * StaticDisjointSet.15 *16 * @constructor17 */18function StaticDisjointSet(size) {19 20  // Optimizing the typed array types21  var ParentsTypedArray = helpers.getPointerArray(size),22      RanksTypedArray = helpers.getPointerArray(Math.log2(size));23 24  // Properties25  this.size = size;26  this.dimension = size;27  this.parents = new ParentsTypedArray(size);28  this.ranks = new RanksTypedArray(size);29 30  // Initializing parents31  for (var i = 0; i < size; i++)32    this.parents[i] = i;33}34 35/**36 * Method used to find the root of the given item.37 *38 * @param  {number} x - Target item.39 * @return {number}40 */41StaticDisjointSet.prototype.find = function(x) {42  var y = x;43 44  var c, p;45 46  while (true) {47    c = this.parents[y];48 49    if (y === c)50      break;51 52    y = c;53  }54 55  // Path compression56  while (true) {57    p = this.parents[x];58 59    if (p === y)60      break;61 62    this.parents[x] = y;63    x = p;64  }65 66  return y;67};68 69/**70 * Method used to perform the union of two items.71 *72 * @param  {number} x - First item.73 * @param  {number} y - Second item.74 * @return {StaticDisjointSet}75 */76StaticDisjointSet.prototype.union = function(x, y) {77  var xRoot = this.find(x),78      yRoot = this.find(y);79 80  // x and y are already in the same set81  if (xRoot === yRoot)82    return this;83 84  this.dimension--;85 86  // x and y are not in the same set, we merge them87  var xRank = this.ranks[x],88      yRank = this.ranks[y];89 90  if (xRank < yRank) {91    this.parents[xRoot] = yRoot;92  }93  else if (xRank > yRank) {94    this.parents[yRoot] = xRoot;95  }96  else {97    this.parents[yRoot] = xRoot;98    this.ranks[xRoot]++;99  }100 101  return this;102};103 104/**105 * Method returning whether two items are connected.106 *107 * @param  {number} x - First item.108 * @param  {number} y - Second item.109 * @return {boolean}110 */111StaticDisjointSet.prototype.connected = function(x, y) {112  var xRoot = this.find(x);113 114  return xRoot === this.find(y);115};116 117/**118 * Method returning the set mapping.119 *120 * @return {TypedArray}121 */122StaticDisjointSet.prototype.mapping = function() {123  var MappingClass = helpers.getPointerArray(this.dimension);124 125  var ids = {},126      mapping = new MappingClass(this.size),127      c = 0;128 129  var r;130 131  for (var i = 0, l = this.parents.length; i < l; i++) {132    r = this.find(i);133 134    if (typeof ids[r] === 'undefined') {135      mapping[i] = c;136      ids[r] = c++;137    }138    else {139      mapping[i] = ids[r];140    }141  }142 143  return mapping;144};145 146/**147 * Method used to compile the disjoint set into an array of arrays.148 *149 * @return {array}150 */151StaticDisjointSet.prototype.compile = function() {152  var ids = {},153      result = new Array(this.dimension),154      c = 0;155 156  var r;157 158  for (var i = 0, l = this.parents.length; i < l; i++) {159    r = this.find(i);160 161    if (typeof ids[r] === 'undefined') {162      result[c] = [i];163      ids[r] = c++;164    }165    else {166      result[ids[r]].push(i);167    }168  }169 170  return result;171};172 173/**174 * Convenience known methods.175 */176StaticDisjointSet.prototype.inspect = function() {177  var array = this.compile();178 179  // Trick so that node displays the name of the constructor180  Object.defineProperty(array, 'constructor', {181    value: StaticDisjointSet,182    enumerable: false183  });184 185  return array;186};187 188if (typeof Symbol !== 'undefined')189  StaticDisjointSet.prototype[Symbol.for('nodejs.util.inspect.custom')] = StaticDisjointSet.prototype.inspect;190 191 192/**193 * Exporting.194 */195module.exports = StaticDisjointSet;196