moved search.js

1 files changed, 82 insertions, 0 deletions

diff --git a/tools/search.js b/tools/search.js
new file mode 100644
index 0000000..0eebe3b
--- /dev/null
+++ b/tools/search.js
@@ -0,0 +1,82 @@
+// A search utility for arbitrary (new) tileUpdates.
+// Provides `add` functionality, which auto-checks adjacency with other blocks. Subsequently, it searches them
+// Provides `del` functionality, which should be used with auto-deletion
+
+const bs = require('binary-search');
+const Space = require('../space');
+const comb = require('../utils/comb')
+const getdims = require('../utils/getdims');
+const vec = require('../utils/vec');
+
+function getComp(index){
+  return (element,needle) => (element[index] - needle[index] || element[1-index] - needle[1-index])
+}
+
+function tileToChar(coord){
+  let cofactor = [8,16];
+  return [coord[0]*cofactor[0], coord[1]*cofactor[1]];
+}
+
+function Search(searchBlock){ // searchBlock should be a Space object.
+  this.tiles = {};     // Object which stores Spaces.
+  this.sort = [[],[]]; // Vertically/horizontally sorted list of tiles for fast addition, deletion, and searching
+
+  this.add = function(loc, space){ // loc should be [tileY,tileX] and space Space.
+    this.tiles[loc] = space;
+    this.tiles[loc].loc = vec.tileToChar(loc);
+    let inds = Array(2); // Records horizontal and vertical indices for insertion. Then actually inserts the item.
+    [0,1].forEach( ind => { // ind chooses y-or-x
+      inds[ind] = -bs(this.sort[ind], loc, getComp(ind))-1;
+      if (inds[ind] < 0) throw "loc should not be a part of the list";
+      this.sort[ind].splice(inds[ind], 0, loc);
+    });
+    let block = this.block(loc, inds);
+    let searchspace = new Space();
+    block.forEach( (tile) => {
+      searchspace.comb( this.tiles[tile], comb.add );
+    });
+    coords = searchspace.search(searchBlock); // According to space docs, [] on failure and a character location on success
+    return vec.add(coords, searchspace.loc);
+  }
+  
+  this.block = function(loc,inds,exclude){
+    if (! exclude) exclude = new Set(); // If not given, replace.
+    let adjacent = new Set([loc]);
+    exclude.add(loc);
+    [0,1].forEach( ind => {
+      // inds[ind] is address, so check neighbors on sort[ind] (up, then down)
+      // until sort[ind][inds[ind]][ind] != sort[ind][otherind][ind].
+      // on each, if sort[ind][otherind][1-ind] == sort[ind][inds[ind]][1-ind],
+      // add to adjacent and search it with exclude=adjacent. Add that to adjacent
+      let sort = this.sort[ind];
+      let chkind = inds[ind];
+      [-1, 1].forEach( sgn => {
+        let curind = chkind + sgn;
+        while (sort[curind] && sort[chkind][ind] == sort[curind][ind]){
+          if (! exclude.has(sort[curind])){
+            adjacent.add(...this.block(sort[curind], [curind, bs(sort, sort[curind], getComp(1-ind))], adjacent));
+          }
+          curind += sgn;
+        }
+      });
+    });
+    return adjacent;
+  }
+
+  this.del = function(loc){
+    delete this.tiles[loc];
+    [0, 1].forEach( ind => {
+      let theind = bs(this.sort[ind], loc, getComp(ind));
+      if (theind < 0) throw "loc must already be a part of the list";
+      this.sort[ind].splice(bs(this.sort[ind], loc, getComp(ind)), 1);
+    })
+  }
+
+  this.has = function(loc){
+    if (bs(this.sort[0], loc, getComp(0)) < 0) return false; // Could use ind = 1 just as well, but doesn't really matter
+    // bs returns negative if not found.
+    else return true;
+  }
+}
+
+module.exports = Search;