From fa7b2028715ce321dc2c1b16d0f0e4d60bcdae3d Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Tue, 24 Dec 2019 16:44:18 -0500 Subject: moved search.js --- examples/jarvis.js | 2 +- examples/search.js | 82 ------------------------------------------------------ tools/search.js | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 83 insertions(+), 83 deletions(-) delete mode 100644 examples/search.js create mode 100644 tools/search.js diff --git a/examples/jarvis.js b/examples/jarvis.js index e0cb82f..d21a41c 100644 --- a/examples/jarvis.js +++ b/examples/jarvis.js @@ -4,7 +4,7 @@ const Space = require('../space'); const Socket = require('../socket'); const getdims = require('../utils/getdims'); const tilekeys = require('../utils/tilekeys'); -const Search = require('./search'); +const Search = require('../tools/search'); var main = new Socket(); diff --git a/examples/search.js b/examples/search.js deleted file mode 100644 index 0eebe3b..0000000 --- a/examples/search.js +++ /dev/null @@ -1,82 +0,0 @@ -// 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; 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; -- cgit