Spaces:
Sleeping
Sleeping
File size: 3,751 Bytes
fcf3b03 | 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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | // @flow
import murmur3 from 'murmurhash-js';
import {register} from '../util/web_worker_transfer';
import assert from 'assert';
type SerializedFeaturePositionMap = {
ids: Float64Array;
positions: Uint32Array;
};
type FeaturePosition = {
index: number;
start: number;
end: number;
};
// A transferable data structure that maps feature ids to their indices and buffer offsets
export default class FeaturePositionMap {
ids: Array<number>;
positions: Array<number>;
indexed: boolean;
constructor() {
this.ids = [];
this.positions = [];
this.indexed = false;
}
add(id: mixed, index: number, start: number, end: number) {
this.ids.push(getNumericId(id));
this.positions.push(index, start, end);
}
getPositions(id: mixed): Array<FeaturePosition> {
assert(this.indexed);
const intId = getNumericId(id);
// binary search for the first occurrence of id in this.ids;
// relies on ids/positions being sorted by id, which happens in serialization
let i = 0;
let j = this.ids.length - 1;
while (i < j) {
const m = (i + j) >> 1;
if (this.ids[m] >= intId) {
j = m;
} else {
i = m + 1;
}
}
const positions = [];
while (this.ids[i] === intId) {
const index = this.positions[3 * i];
const start = this.positions[3 * i + 1];
const end = this.positions[3 * i + 2];
positions.push({index, start, end});
i++;
}
return positions;
}
static serialize(map: FeaturePositionMap, transferables: Array<ArrayBuffer>): SerializedFeaturePositionMap {
const ids = new Float64Array(map.ids);
const positions = new Uint32Array(map.positions);
sort(ids, positions, 0, ids.length - 1);
if (transferables) {
transferables.push(ids.buffer, positions.buffer);
}
return {ids, positions};
}
static deserialize(obj: SerializedFeaturePositionMap): FeaturePositionMap {
const map = new FeaturePositionMap();
// after transferring, we only use these arrays statically (no pushes),
// so TypedArray vs Array distinction that flow points out doesn't matter
map.ids = (obj.ids: any);
map.positions = (obj.positions: any);
map.indexed = true;
return map;
}
}
const MAX_SAFE_INTEGER = Math.pow(2, 53) - 1;
function getNumericId(value: mixed) {
const numValue = +value;
if (!isNaN(numValue) && numValue <= MAX_SAFE_INTEGER) {
return numValue;
}
return murmur3(String(value));
}
// custom quicksort that sorts ids, indices and offsets together (by ids)
// uses Hoare partitioning & manual tail call optimization to avoid worst case scenarios
function sort(ids, positions, left, right) {
while (left < right) {
const pivot = ids[(left + right) >> 1];
let i = left - 1;
let j = right + 1;
while (true) {
do i++; while (ids[i] < pivot);
do j--; while (ids[j] > pivot);
if (i >= j) break;
swap(ids, i, j);
swap(positions, 3 * i, 3 * j);
swap(positions, 3 * i + 1, 3 * j + 1);
swap(positions, 3 * i + 2, 3 * j + 2);
}
if (j - left < right - j) {
sort(ids, positions, left, j);
left = j + 1;
} else {
sort(ids, positions, j + 1, right);
right = j;
}
}
}
function swap(arr, i, j) {
const tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
register('FeaturePositionMap', FeaturePositionMap);
|