1'use strict'; 2 3const assert = require('assert'); 4const Node = require('./tree-node'); 5 6const HAS_DATA_FLAG = 1 << 0; 7const DATA_DUPLET_FLAG = 1 << 1; 8const HAS_BRANCHES_FLAG = 1 << 2; 9 10const MAX_UINT16 = (1 << 16) - 1; 11const MAX_BRANCH_MARKER_VALUE = HAS_DATA_FLAG | DATA_DUPLET_FLAG | HAS_BRANCHES_FLAG; 12 13class ArrayMappedRadixTree { 14 constructor(radixTree) { 15 this.arr = []; 16 17 this._convertNode(radixTree); 18 19 for (const n of this.arr) { 20 assert(n <= MAX_UINT16, `${n} overflows uint16`); 21 } 22 23 return this.arr; 24 } 25 26 _convertEdge(edge) { 27 for (const cp of edge.filter) { 28 assert(cp > MAX_BRANCH_MARKER_VALUE, 'filter code point shadows node marker'); 29 this.arr.push(cp); 30 } 31 32 this._convertNode(edge.node); 33 } 34 35 _writeNodeMarker(data, branches) { 36 let marker = 0; 37 38 if (data) { 39 marker |= HAS_DATA_FLAG; 40 41 if (data.length === 2) { 42 marker |= DATA_DUPLET_FLAG; 43 } 44 } 45 46 if (branches) { 47 marker |= HAS_BRANCHES_FLAG; 48 } 49 50 this.arr.push(marker); 51 } 52 53 _writeBranches(branches) { 54 const kvPairs = Object.keys(branches) 55 .map(Number) 56 .map(key => ({ key, branch: branches[key] })); 57 58 const count = kvPairs.length; 59 60 this.arr.push(count); 61 62 const transitionTableIdx = this.arr.length; 63 64 // NOTE: allocate space for transition table 65 this.arr.length += count * 2; 66 67 kvPairs 68 .sort((pair1, pair2) => pair1.key - pair2.key) 69 .forEach((pair, idx) => { 70 const keyIdx = transitionTableIdx + idx; 71 const branchIdx = keyIdx + count; 72 73 this.arr[keyIdx] = pair.key; 74 this.arr[branchIdx] = this.arr.length; 75 76 if (pair.branch instanceof Node) { 77 this._convertNode(pair.branch); 78 } else { 79 this._convertEdge(pair.branch); 80 } 81 }); 82 } 83 84 _convertNode(node) { 85 const data = node.data; 86 const branches = node.branches; 87 88 this._writeNodeMarker(data, branches); 89 90 if (data) { 91 data.forEach(cp => this.arr.push(cp)); 92 } 93 94 if (branches) { 95 this._writeBranches(branches); 96 } 97 } 98} 99 100module.exports = ArrayMappedRadixTree; 101