1'use strict'; 2 3const Node = require('./tree-node'); 4 5class RadixTree { 6 constructor(src) { 7 this.root = new Node(null); 8 9 for (const entity of Object.keys(src)) { 10 this._addEntity(entity, src[entity].codepoints); 11 } 12 13 return this.root; 14 } 15 16 static _entityToCodePointsArray(entity) { 17 return entity 18 .replace(/^&/, '') 19 .split('') 20 .map(ch => ch.charCodeAt(0)); 21 } 22 23 static _decoupleSurrogatePair(cp) { 24 cp -= 0x10000; 25 26 return [((cp >>> 10) & 0x3ff) | 0xd800, 0xdc00 | (cp & 0x3ff)]; 27 } 28 29 // Before: 30 // 31 // {...} 32 // 33 // 34 // After: 35 // 36 // filter 37 // *--------- {data} 38 // / 39 // {..., key} 40 // 41 // 42 static _appendNewDataBranch(node, key, filter, data) { 43 const newNode = new Node(data); 44 45 if (filter.length) { 46 node.addEdge(key, filter, newNode); 47 } else { 48 node.addNode(key, newNode); 49 } 50 } 51 52 // Before: 53 // 54 // filter 55 // *------------ node 56 // 57 // 58 // After: 59 // 60 // commonPrefix 61 // *[---------------] newNode 62 // 63 // 64 // 65 static _shortenEdgeAndAddNewNode(edge, newFilter, data) { 66 const newNode = new Node(data); 67 68 if (newFilter.length) { 69 edge.filter = newFilter; 70 edge.node = newNode; 71 } else { 72 edge.parent.addNode(edge.parentKey, newNode); 73 } 74 75 return newNode; 76 } 77 78 // Before: 79 // 80 // filter 81 // *------------ node 82 // 83 // 84 // After: 85 // 86 // oldNodeSuffix 87 // *------------------ node 88 // commonPrefix / 89 // *[---------------] {newDataKey, oldNodeKey} 90 // \ 91 // \ newDataSuffix 92 // *------------------- {data} 93 // 94 // 95 static _branchEdgeWithNewData(edge, commonPrefix, newDataKey, oldNodeKey, newDataSuffix, oldNodeSuffix, data) { 96 const node = edge.node; 97 const newDataNode = new Node(data); 98 const branchNode = RadixTree._shortenEdgeAndAddNewNode(edge, commonPrefix, null); 99 100 branchNode.addEdge(newDataKey, newDataSuffix, newDataNode); 101 branchNode.addEdge(oldNodeKey, oldNodeSuffix, node); 102 } 103 104 // Before: 105 // 106 // filter 107 // *------------ node 108 // 109 // 110 // After: 111 // 112 // commonPrefix oldNodeSuffix 113 // *[---------------] {data, oldNodeKey} ---------------- node 114 // 115 // 116 // 117 static _splitEdgeWithNewData(edge, commonPrefix, oldNodeKey, oldNodeSuffix, data) { 118 const node = edge.node; 119 const splitNode = RadixTree._shortenEdgeAndAddNewNode(edge, commonPrefix, data); 120 121 splitNode.addEdge(oldNodeKey, oldNodeSuffix, node); 122 } 123 124 static _tryAddDataIntoEdge(edge, cps, i, data) { 125 const commonPrefix = []; 126 const filter = edge.filter; 127 128 for (let j = 0; j < filter.length; j++, i++) { 129 const filterCp = filter[j]; 130 131 // Edge is longer than current sequence. We need to insert intermediate node 132 if (i === cps.length) { 133 RadixTree._splitEdgeWithNewData(edge, commonPrefix, filterCp, filter.slice(j + 1), data); 134 return null; 135 } 136 137 const cp = cps[i]; 138 139 if (cp === filterCp) { 140 commonPrefix.push(cp); 141 } else { 142 RadixTree._branchEdgeWithNewData( 143 edge, 144 commonPrefix, 145 cp, 146 filterCp, 147 cps.slice(i + 1), 148 filter.slice(j + 1), 149 data 150 ); 151 return null; 152 } 153 } 154 155 return i - 1; 156 } 157 158 _addEntity(entity, data) { 159 const cps = RadixTree._entityToCodePointsArray(entity); 160 161 if (data.length === 1 && data[0] > 0xffff) { 162 data = RadixTree._decoupleSurrogatePair(data[0]); 163 } 164 165 for (let i = 0, current = this.root; i < cps.length; i++) { 166 const cp = cps[i]; 167 168 if (current instanceof Node) { 169 const next = current.branches && current.branches[cp]; 170 171 // NOTE: Iterate to next node/edge 172 if (next) { 173 current = next; 174 } 175 // NOTE: We can't iterate to next node, so we just create a new branch. 176 else { 177 RadixTree._appendNewDataBranch(current, cp, cps.slice(i + 1), data); 178 break; 179 } 180 } else { 181 const nextIdx = RadixTree._tryAddDataIntoEdge(current, cps, i, data); 182 183 if (nextIdx !== null) { 184 // NOTE: We've passed through, nothing was added. Continue with next node. 185 i = nextIdx; 186 current = current.node; 187 } else { 188 break; 189 } 190 } 191 } 192 } 193} 194 195module.exports = RadixTree; 196