1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
// 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 vec = require('../utils/vec');
const raster = require('../utils/raster');
function getComp(index){
return (element,needle) => (element[index] - needle[index] || element[1-index] - needle[1-index])
}
class Search {
constructor(){
this.tiles = {}; // Object which stores Spaces.
this.sort = [[],[]]; // Vertically/horizontally sorted list of indexed tiles for fast addition, deletion, and searching
this.spaces = []; // if spaces[i] is detected,
this.calls = []; // calls[i](coords, send, searchspace)
}
add(loc, space, send){ // loc should be [tileY,tileX] and space Space.
this.tiles[loc] = space;
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 );
});
for (let i=0; i<this.spaces.length; i++){
let coords = searchspace.regex(this.spaces[i])[0];
if (coords) this.calls[i](vec.add(coords, searchspace.loc), send,
searchspace);
}
}
block(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(this.sort[1-ind], sort[curind], getComp(1-ind))], exclude));
}
curind += sgn;
}
});
});
return adjacent;
}
del(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);
})
}
has(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;
}
update(space){ // Must be a space w/ valid loc; allows overlay of some arbitrary text (in the space) mostly for recording updates from the server without directly cataloguing them
if (space.loc.length === 0) throw "Update space must have valid loc";
let tiles = raster(space); // Returns a this.tiles-style binding: {'2,-3':Space object}
for (let tile in tiles) {
tile = tile.split(',').map(s => parseInt(s));
if (this.tiles[tile]) this.tiles[tile].comb(tiles[tile], comb.flip(comb.add));
else this.add(tile, tiles[tile]);
}
}
match(space, call){
this.spaces.push(space);
this.calls.push(call);
}
unmatch(space){
let ind = this.spaces.indexOf(space);
this.spaces.splice(ind, 1);
this.calls.splice(ind, 1);
}
}
module.exports = Search;
|
