aboutsummaryrefslogtreecommitdiff
path: root/examples
diff options
context:
space:
mode:
authorHolden Rohrer <holden.rohrer@gmail.com>2019-12-19 22:59:00 -0500
committerHolden Rohrer <holden.rohrer@gmail.com>2019-12-19 22:59:00 -0500
commit3da86ed4ae7bf63600b5875a0a7d99344f738b98 (patch)
treed4fbcf513a4caa4a7b706b7e074f4893a5a1d3d7 /examples
parented1603283db986d5838a7d3abefd7aac27ac70f9 (diff)
totally untested search.js finished (needs refactor)
Diffstat (limited to 'examples')
-rw-r--r--examples/search.js44
1 files 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;