From 3da86ed4ae7bf63600b5875a0a7d99344f738b98 Mon Sep 17 00:00:00 2001
From: Holden Rohrer <holden.rohrer@gmail.com>
Date: Thu, 19 Dec 2019 22:59:00 -0500
Subject: totally untested search.js finished (needs refactor)

---
 examples/search.js | 44 ++++++++++++++++++++++++++++++++++++--------
 1 file changed, 36 insertions(+), 8 deletions(-)

diff --git a/examples/search.js b/examples/search.js
index d119fd3..204dc00 100644
--- a/examples/search.js
+++ b/examples/search.js
@@ -1,9 +1,10 @@
 // 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
-// As of now, it assumes that no search block is larger than 8x16, or the size of a block.
 
 const bs = require('binary-search');
+const Space = require('../space');
+const comb = require('../utils/comb.js')
 
 function getComp(index){
   return (element,needle) => element[index] - needle[index];
@@ -11,20 +12,47 @@ function getComp(index){
 
 
 function Search(searchBlock){ // searchBlock should be a Space object.
-  this.tiles = {};    // Object which stores Spaces.
-  this.vertsort = []; // Vertically sorted list of tiles for fast addition, deletion, and searching
-  this.horisort = []; // Horizantally sorted list
+  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;
-    vertsort.insert(loc, bs(vertsort, loc, getComp(0))); // TEST
-    horisort.insert(loc, bs(horisort, loc, getComp(1)));
+    let inds = Array(2); // Records horizontal and vertical indices for insertion. Then actually inserts the item.
+    [null,null].forEach( (item, ind) => {
+      inds[ind] = -bs(sort[ind], loc, getComp(ind))-1;
+      if (inds[ind] < 0) throw "loc should not be a part of the list";
+      sort[ind].splice(inds[ind], 0, loc);
+    });
+    let block = this.block(inds);
+    let searchspace = new Space();
+    block.forEach( (tile) => {searchspace.comb(tiles[tile],comb.add,[tile[0]*8,tile[1]*16])});
+    return searchspace.search(searchBlock); // According to space docs, [] on failure and a character location on success
+  }
+  
+  this.block = function(loc,inds,exclude=Set()){
+    let adjacent = Set([loc]);
+    exclude.add(loc);
+    [null,null].forEach( (item, 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 addr = inds[ind];
+      for (let i = -1; i <= 1; i++) for (let j = 1; sort[ind][inds[ind]][ind] == sort[ind][inds[ind]+i*j][ind]; j++)
+        if (! exclude.has(sort[ind][inds[ind]]) && sort[ind][inds[ind]][1-ind] == sort[inds[ind]+i*j][1-ind]){ // Make more readable
+          adjacent.add(...this.block(sort[ind][inds[ind]+i*j], inds[ind+i*j], exclude=adjacent)); // Already includes itself
+        }
+      return adjacent;
+    });
   }
 
   this.del = function(loc){
     delete tiles[loc];
-    vertsort.remove(bs(vertsort, loc, getComp(0))); // TEST
-    horisort.remove(bs(horisort, loc, getComp(1)));
+    [null,null].forEach( (item,ind) => {
+      let theind = bs(sort[ind], loc, getComp(ind));
+      if (theind < 0) throw "loc must already be a part of the list";
+      sort[ind].splice(bs(sort[ind], loc, getComp(ind)), 1);
+    })
   }
 }
 module.exports = Search;
-- 
cgit