| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library index.btree; | |
| 6 | |
| 7 | |
| 8 /** | |
| 9 * A simple B+Tree implementation. | |
| 10 */ | |
| 11 class BTree<K, V> { | |
| 12 /** | |
| 13 * The [Comparator] to compare keys. | |
| 14 */ | |
| 15 final Comparator<K> _comparator; | |
| 16 | |
| 17 /** | |
| 18 * The maximum number of keys in an index node. | |
| 19 */ | |
| 20 final int _maxIndexKeys; | |
| 21 | |
| 22 /** | |
| 23 * The maximum number of keys in a leaf node. | |
| 24 */ | |
| 25 final int _maxLeafKeys; | |
| 26 | |
| 27 /** | |
| 28 * The root node. | |
| 29 */ | |
| 30 _Node<K, V> _root; | |
| 31 | |
| 32 BTree(this._maxIndexKeys, this._maxLeafKeys, this._comparator) { | |
| 33 _root = new _LeafNode(_maxLeafKeys, _comparator); | |
| 34 } | |
| 35 | |
| 36 /** | |
| 37 * Returns the value for [key] or `null` if [key] is not in the tree. | |
| 38 */ | |
| 39 V find(K key) { | |
| 40 return _root.find(key); | |
| 41 } | |
| 42 | |
| 43 /** | |
| 44 * Associates the [key] with the given [value]. | |
| 45 * | |
| 46 * If the key was already in the tree, its associated value is changed. | |
| 47 * Otherwise the key-value pair is added to the tree. | |
| 48 */ | |
| 49 void insert(K key, V value) { | |
| 50 _Split<K, V> result = _root.insert(key, value); | |
| 51 if (result != null) { | |
| 52 _IndexNode<K, V> newRoot = new _IndexNode<K, V>(_maxIndexKeys, | |
| 53 _comparator); | |
| 54 newRoot.keys.add(result.key); | |
| 55 newRoot.children.add(result.left); | |
| 56 newRoot.children.add(result.right); | |
| 57 _root = newRoot; | |
| 58 } | |
| 59 } | |
| 60 | |
| 61 /** | |
| 62 * Removes the association for the given [key]. | |
| 63 * | |
| 64 * Returns the value associated with [key] in the tree or `null` if [key] is | |
| 65 * not in the tree. | |
| 66 */ | |
| 67 V remove(K key) { | |
| 68 _Remove<K, V> result = _root.remove(key, null, null, null); | |
| 69 if (_root is _IndexNode<K, V>) { | |
| 70 List<_Node<K, V>> children = (_root as _IndexNode<K, V>).children; | |
| 71 if (children.length == 1) { | |
| 72 _root = children[0]; | |
| 73 } | |
| 74 } | |
| 75 return result.value; | |
| 76 } | |
| 77 | |
| 78 /** | |
| 79 * Writes a textual presentation of the tree into [buffer]. | |
| 80 */ | |
| 81 void writeOn(StringBuffer buffer) { | |
| 82 _root.writeOn(buffer, ''); | |
| 83 } | |
| 84 } | |
| 85 | |
| 86 | |
| 87 /** | |
| 88 * An index node with keys and children references. | |
| 89 */ | |
| 90 class _IndexNode<K, V> extends _Node<K, V> { | |
| 91 final List<_Node<K, V>> children = new List<_Node<K, V>>(); | |
| 92 final int maxKeys; | |
| 93 final int minKeys; | |
| 94 | |
| 95 _IndexNode(int maxKeys, Comparator<K> comparator) | |
| 96 : super(comparator), | |
| 97 maxKeys = maxKeys, | |
| 98 minKeys = maxKeys ~/ 2; | |
| 99 | |
| 100 @override | |
| 101 V find(K key) { | |
| 102 int index = findChildIndex(key); | |
| 103 return children[index].find(key); | |
| 104 } | |
| 105 | |
| 106 /** | |
| 107 * Returns the index of the child into which [key] should be inserted. | |
| 108 */ | |
| 109 int findChildIndex(K key) { | |
| 110 for (int i = 0; i < keys.length; i++) { | |
| 111 if (comparator(keys[i], key) > 0) { | |
| 112 return i; | |
| 113 } | |
| 114 } | |
| 115 return keys.length; | |
| 116 } | |
| 117 | |
| 118 _Split<K, V> insert(K key, V value) { | |
| 119 // Early split. | |
| 120 if (keys.length == maxKeys) { | |
| 121 int middle = (maxKeys + 1) ~/ 2; | |
| 122 K splitKey = keys[middle]; | |
| 123 _IndexNode<K, V> sibling = new _IndexNode<K, V>(maxKeys, comparator); | |
| 124 sibling.keys.addAll(keys.getRange(middle + 1, keys.length)); | |
| 125 sibling.children.addAll(children.getRange(middle + 1, children.length)); | |
| 126 keys.length = middle; | |
| 127 children.length = middle + 1; | |
| 128 // Prepare split. | |
| 129 _Split<K, V> result = new _Split<K, V>(splitKey, this, sibling); | |
| 130 if (comparator(key, result.key) < 0) { | |
| 131 insertNotFull(key, value); | |
| 132 } else { | |
| 133 sibling.insertNotFull(key, value); | |
| 134 } | |
| 135 return result; | |
| 136 } | |
| 137 // No split. | |
| 138 insertNotFull(key, value); | |
| 139 return null; | |
| 140 } | |
| 141 | |
| 142 void insertNotFull(K key, V value) { | |
| 143 int index = findChildIndex(key); | |
| 144 _Split<K, V> result = children[index].insert(key, value); | |
| 145 if (result != null) { | |
| 146 keys.insert(index, result.key); | |
| 147 children[index] = result.left; | |
| 148 children.insert(index + 1, result.right); | |
| 149 } | |
| 150 } | |
| 151 | |
| 152 @override | |
| 153 _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right) { | |
| 154 int index = findChildIndex(key); | |
| 155 K thisAnchor = index == 0 ? keys[0] : keys[index - 1]; | |
| 156 _Node<K, V> child = children[index]; | |
| 157 bool hasLeft = index != 0; | |
| 158 bool hasRight = index < children.length - 1; | |
| 159 _Node<K, V> leftChild = hasLeft ? children[index - 1] : null; | |
| 160 _Node<K, V> rightChild = hasRight ? children[index + 1] : null; | |
| 161 // Ask child to remove. | |
| 162 _Remove<K, V> result = child.remove(key, leftChild, thisAnchor, rightChild); | |
| 163 V value = result.value; | |
| 164 if (value == null) { | |
| 165 return new _Remove<K, V>(value); | |
| 166 } | |
| 167 // Update anchor if borrowed. | |
| 168 if (result.leftAnchor != null) { | |
| 169 keys[index - 1] = result.leftAnchor; | |
| 170 } | |
| 171 if (result.rightAnchor != null) { | |
| 172 keys[index] = result.rightAnchor; | |
| 173 } | |
| 174 // Update keys / children if merged. | |
| 175 if (result.mergedLeft) { | |
| 176 keys.removeAt(index - 1); | |
| 177 children.removeAt(index); | |
| 178 } | |
| 179 if (result.mergedRight) { | |
| 180 keys.removeAt(index); | |
| 181 children.removeAt(index); | |
| 182 } | |
| 183 // Perform balancing. | |
| 184 if (keys.length < minKeys) { | |
| 185 // Try left sibling. | |
| 186 if (left is _IndexNode<K, V>) { | |
| 187 // Try to redistribute. | |
| 188 int leftLength = left.keys.length; | |
| 189 if (leftLength > minKeys) { | |
| 190 int halfExcess = (leftLength - minKeys + 1) ~/ 2; | |
| 191 int newLeftLength = leftLength - halfExcess; | |
| 192 keys.insert(0, anchor); | |
| 193 keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength)); | |
| 194 children.insertAll(0, left.children.getRange(newLeftLength, leftLength | |
| 195 + 1)); | |
| 196 K newAnchor = left.keys[newLeftLength - 1]; | |
| 197 left.keys.length = newLeftLength - 1; | |
| 198 left.children.length = newLeftLength; | |
| 199 return new _Remove<K, V>.borrowLeft(value, newAnchor); | |
| 200 } | |
| 201 // Do merge. | |
| 202 left.keys.add(anchor); | |
| 203 left.keys.addAll(keys); | |
| 204 left.children.addAll(children); | |
| 205 return new _Remove<K, V>.mergeLeft(value); | |
| 206 } | |
| 207 // Try right sibling. | |
| 208 if (right is _IndexNode<K, V>) { | |
| 209 // Try to redistribute. | |
| 210 var rightLength = right.keys.length; | |
| 211 if (rightLength > minKeys) { | |
| 212 int halfExcess = (rightLength - minKeys + 1) ~/ 2; | |
| 213 keys.add(anchor); | |
| 214 keys.addAll(right.keys.getRange(0, halfExcess - 1)); | |
| 215 children.addAll(right.children.getRange(0, halfExcess)); | |
| 216 K newAnchor = right.keys[halfExcess - 1]; | |
| 217 right.keys.removeRange(0, halfExcess); | |
| 218 right.children.removeRange(0, halfExcess); | |
| 219 return new _Remove<K, V>.borrowRight(value, newAnchor); | |
| 220 } | |
| 221 // Do merge. | |
| 222 right.keys.insert(0, anchor); | |
| 223 right.keys.insertAll(0, keys); | |
| 224 right.children.insertAll(0, children); | |
| 225 return new _Remove<K, V>.mergeRight(value); | |
| 226 } | |
| 227 } | |
| 228 // No balancing required. | |
| 229 return new _Remove<K, V>(value); | |
| 230 } | |
| 231 | |
| 232 @override | |
| 233 void writeOn(StringBuffer buffer, String indent) { | |
| 234 buffer.write(indent); | |
| 235 buffer.write('INode {\n'); | |
| 236 for (int i = 0; i < keys.length; i++) { | |
| 237 children[i].writeOn(buffer, indent + ' '); | |
| 238 buffer.write(indent); | |
| 239 buffer.write(' '); | |
| 240 buffer.write(keys[i]); | |
| 241 buffer.write('\n'); | |
| 242 } | |
| 243 children[keys.length].writeOn(buffer, indent + ' '); | |
| 244 buffer.write(indent); | |
| 245 buffer.write('}\n'); | |
| 246 } | |
| 247 } | |
| 248 | |
| 249 | |
| 250 /** | |
| 251 * A leaf node with keys and values. | |
| 252 */ | |
| 253 class _LeafNode<K, V> extends _Node<K, V> { | |
| 254 final int maxKeys; | |
| 255 final int minKeys; | |
| 256 | |
| 257 /** | |
| 258 * The list of values. | |
| 259 */ | |
| 260 final List<V> values = new List<V>(); | |
| 261 | |
| 262 _LeafNode(int maxKeys, Comparator<K> comparator) | |
| 263 : super(comparator), | |
| 264 maxKeys = maxKeys, | |
| 265 minKeys = maxKeys ~/ 2; | |
| 266 | |
| 267 @override | |
| 268 V find(K key) { | |
| 269 int index = findKeyIndex(key); | |
| 270 if (index < 0) { | |
| 271 return null; | |
| 272 } | |
| 273 if (index >= keys.length) { | |
| 274 return null; | |
| 275 } | |
| 276 if (keys[index] != key) { | |
| 277 return null; | |
| 278 } | |
| 279 return values[index]; | |
| 280 } | |
| 281 | |
| 282 /** | |
| 283 * Returns the index where [key] should be inserted. | |
| 284 */ | |
| 285 int findKeyIndex(K key) { | |
| 286 for (int i = 0; i < keys.length; i++) { | |
| 287 if (comparator(keys[i], key) >= 0) { | |
| 288 return i; | |
| 289 } | |
| 290 } | |
| 291 return keys.length; | |
| 292 } | |
| 293 | |
| 294 _Split<K, V> insert(K key, V value) { | |
| 295 int index = findKeyIndex(key); | |
| 296 // The node is full. | |
| 297 if (keys.length == maxKeys) { | |
| 298 int middle = (maxKeys + 1) ~/ 2; | |
| 299 _LeafNode<K, V> sibling = new _LeafNode<K, V>(maxKeys, comparator); | |
| 300 sibling.keys.addAll(keys.getRange(middle, keys.length)); | |
| 301 sibling.values.addAll(values.getRange(middle, values.length)); | |
| 302 keys.length = middle; | |
| 303 values.length = middle; | |
| 304 // Insert into the left / right sibling. | |
| 305 if (index < middle) { | |
| 306 insertNotFull(key, value, index); | |
| 307 } else { | |
| 308 sibling.insertNotFull(key, value, index - middle); | |
| 309 } | |
| 310 // Notify the parent about the split. | |
| 311 return new _Split<K, V>(sibling.keys[0], this, sibling); | |
| 312 } | |
| 313 // The node was not full. | |
| 314 insertNotFull(key, value, index); | |
| 315 return null; | |
| 316 } | |
| 317 | |
| 318 void insertNotFull(K key, V value, int index) { | |
| 319 if (index < keys.length && keys[index] == key) { | |
| 320 values[index] = value; | |
| 321 } else { | |
| 322 keys.insert(index, key); | |
| 323 values.insert(index, value); | |
| 324 } | |
| 325 } | |
| 326 | |
| 327 @override | |
| 328 _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right) { | |
| 329 // Find the key. | |
| 330 int index = keys.indexOf(key); | |
| 331 if (index == -1) { | |
| 332 return new _Remove<K, V>(null); | |
| 333 } | |
| 334 // Key key / value. | |
| 335 keys.removeAt(index); | |
| 336 V value = values.removeAt(index); | |
| 337 // Perform balancing. | |
| 338 if (keys.length < minKeys) { | |
| 339 // Try left sibling. | |
| 340 if (left is _LeafNode<K, V>) { | |
| 341 // Try to redistribute. | |
| 342 int leftLength = left.keys.length; | |
| 343 if (leftLength > minKeys) { | |
| 344 int halfExcess = (leftLength - minKeys + 1) ~/ 2; | |
| 345 int newLeftLength = leftLength - halfExcess; | |
| 346 keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength)); | |
| 347 values.insertAll(0, left.values.getRange(newLeftLength, leftLength)); | |
| 348 left.keys.length = newLeftLength; | |
| 349 left.values.length = newLeftLength; | |
| 350 return new _Remove<K, V>.borrowLeft(value, keys.first); | |
| 351 } | |
| 352 // Do merge. | |
| 353 left.keys.addAll(keys); | |
| 354 left.values.addAll(values); | |
| 355 return new _Remove<K, V>.mergeLeft(value); | |
| 356 } | |
| 357 // Try right sibling. | |
| 358 if (right is _LeafNode<K, V>) { | |
| 359 // Try to redistribute. | |
| 360 var rightLength = right.keys.length; | |
| 361 if (rightLength > minKeys) { | |
| 362 int halfExcess = (rightLength - minKeys + 1) ~/ 2; | |
| 363 keys.addAll(right.keys.getRange(0, halfExcess)); | |
| 364 values.addAll(right.values.getRange(0, halfExcess)); | |
| 365 right.keys.removeRange(0, halfExcess); | |
| 366 right.values.removeRange(0, halfExcess); | |
| 367 return new _Remove<K, V>.borrowRight(value, right.keys.first); | |
| 368 } | |
| 369 // Do merge. | |
| 370 right.keys.insertAll(0, keys); | |
| 371 right.values.insertAll(0, values); | |
| 372 return new _Remove<K, V>.mergeRight(value); | |
| 373 } | |
| 374 } | |
| 375 // No balancing required. | |
| 376 return new _Remove<K, V>(value); | |
| 377 } | |
| 378 | |
| 379 @override | |
| 380 void writeOn(StringBuffer buffer, String indent) { | |
| 381 buffer.write(indent); | |
| 382 buffer.write('LNode {'); | |
| 383 for (int i = 0; i < keys.length; i++) { | |
| 384 if (i != 0) { | |
| 385 buffer.write(', '); | |
| 386 } | |
| 387 buffer.write(keys[i]); | |
| 388 buffer.write(': '); | |
| 389 buffer.write(values[i]); | |
| 390 } | |
| 391 buffer.write('}\n'); | |
| 392 } | |
| 393 } | |
| 394 | |
| 395 | |
| 396 /** | |
| 397 * An internal or leaf node. | |
| 398 */ | |
| 399 abstract class _Node<K, V> { | |
| 400 /** | |
| 401 * The [Comparator] to compare keys. | |
| 402 */ | |
| 403 Comparator<K> comparator; | |
| 404 | |
| 405 /** | |
| 406 * The list of keys. | |
| 407 */ | |
| 408 List<K> keys = new List<K>(); | |
| 409 | |
| 410 _Node(this.comparator); | |
| 411 | |
| 412 /** | |
| 413 * Looks for [key]. | |
| 414 * | |
| 415 * Returns the associated value if found. | |
| 416 * Returns `null` if not found. | |
| 417 */ | |
| 418 V find(K key); | |
| 419 | |
| 420 /** | |
| 421 * Inserts the [key] / [value] pair into this [_Node]. | |
| 422 * | |
| 423 * Returns a [_Split] object if split happens, or `null` otherwise. | |
| 424 */ | |
| 425 _Split<K, V> insert(K key, V value); | |
| 426 | |
| 427 /** | |
| 428 * Removes the association for the given [key]. | |
| 429 * | |
| 430 * Returns the [_Remove] information about an operation performed. | |
| 431 * It may be restructuring or merging, with [left] or [left] siblings. | |
| 432 */ | |
| 433 _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right); | |
| 434 | |
| 435 /** | |
| 436 * Writes a textual presentation of the tree into [buffer]. | |
| 437 */ | |
| 438 void writeOn(StringBuffer buffer, String indent); | |
| 439 } | |
| 440 | |
| 441 | |
| 442 /** | |
| 443 * A container with information about redistribute / merge. | |
| 444 */ | |
| 445 class _Remove<K, V> { | |
| 446 K leftAnchor; | |
| 447 bool mergedLeft = false; | |
| 448 bool mergedRight = false; | |
| 449 K rightAnchor; | |
| 450 final V value; | |
| 451 _Remove(this.value); | |
| 452 _Remove.borrowLeft(this.value, this.leftAnchor); | |
| 453 _Remove.borrowRight(this.value, this.rightAnchor); | |
| 454 _Remove.mergeLeft(this.value) : mergedLeft = true; | |
| 455 _Remove.mergeRight(this.value) : mergedRight = true; | |
| 456 } | |
| 457 | |
| 458 | |
| 459 /** | |
| 460 * A container with information about split during insert. | |
| 461 */ | |
| 462 class _Split<K, V> { | |
| 463 final K key; | |
| 464 final _Node<K, V> left; | |
| 465 final _Node<K, V> right; | |
| 466 _Split(this.key, this.left, this.right); | |
| 467 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 320723002:
Rename to BPlusTree. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart