1 2 17 18 19 20 package org.apache.poi.hdf.extractor.util; 21 22 import java.util.*; 23 24 25 39 40 public class BTreeSet extends AbstractSet implements Set { 41 42 45 public BTreeNode root; 46 private Comparator comparator = null; 47 private int order; 48 private int size = 0; 49 50 56 57 public BTreeSet() { 58 this(6); } 60 61 public BTreeSet(Collection c) { 62 this(6); addAll(c); 64 } 65 66 public BTreeSet(int order) { 67 this(order, null); 68 } 69 70 public BTreeSet(int order, Comparator comparator) { 71 this.order = order; 72 this.comparator = comparator; 73 root = new BTreeNode(null); 74 } 75 76 77 80 public boolean add(Object x) throws IllegalArgumentException { 81 if (x == null) throw new IllegalArgumentException (); 82 return root.insert(x, -1); 83 } 84 85 public boolean contains(Object x) { 86 return root.includes(x); 87 } 88 89 public boolean remove(Object x) { 90 if (x == null) return false; 91 return root.delete(x, -1); 92 } 93 94 public int size() { 95 return size; 96 } 97 98 public void clear() { 99 root = new BTreeNode(null); 100 size = 0; 101 } 102 103 public java.util.Iterator iterator() { 104 return new Iterator(); 105 } 106 107 108 111 private int compare(Object x, Object y) { 112 return (comparator == null ? ((Comparable )x).compareTo(y) : comparator.compare(x, y)); 113 } 114 115 116 117 120 121 129 130 private class Iterator implements java.util.Iterator { 131 private int index = 0; 132 private Stack parentIndex = new Stack(); private Object lastReturned = null; 134 private Object next; 135 private BTreeNode currentNode; 136 137 Iterator() { 138 currentNode = firstNode(); 139 next = nextElement(); 140 } 141 142 public boolean hasNext() { 143 return next != null; 144 } 145 146 public Object next() { 147 if (next == null) throw new NoSuchElementException(); 148 149 lastReturned = next; 150 next = nextElement(); 151 return lastReturned; 152 } 153 154 public void remove() { 155 if (lastReturned == null) throw new NoSuchElementException(); 156 157 BTreeSet.this.remove(lastReturned); 158 lastReturned = null; 159 } 160 161 private BTreeNode firstNode() { 162 BTreeNode temp = BTreeSet.this.root; 163 164 while (temp.entries[0].child != null) { 165 temp = temp.entries[0].child; 166 parentIndex.push(new Integer (0)); 167 } 168 169 return temp; 170 } 171 172 private Object nextElement() { 173 if (currentNode.isLeaf()) { 174 if (index < currentNode.nrElements) return currentNode.entries[index++].element; 175 176 else if (!parentIndex.empty()) { currentNode = currentNode.parent; 178 index = ((Integer )parentIndex.pop()).intValue(); 179 180 while (index == currentNode.nrElements) { 181 if (parentIndex.empty()) break; 182 currentNode = currentNode.parent; 183 index = ((Integer )parentIndex.pop()).intValue(); 184 } 185 186 if (index == currentNode.nrElements) return null; return currentNode.entries[index++].element; 188 } 189 190 else { if (index == currentNode.nrElements) return null; 192 return currentNode.entries[index++].element; 193 } 194 } 195 196 else { currentNode = currentNode.entries[index].child; 198 parentIndex.push(new Integer (index)); 199 200 while (currentNode.entries[0].child != null) { 201 currentNode = currentNode.entries[0].child; 202 parentIndex.push(new Integer (0)); 203 } 204 205 index = 1; 206 return currentNode.entries[0].element; 207 } 208 } 209 } 210 211 212 public static class Entry { 213 214 public Object element; 215 public BTreeNode child; 216 } 217 218 219 public class BTreeNode { 220 221 public Entry[] entries; 222 public BTreeNode parent; 223 private int nrElements = 0; 224 private final int MIN = (BTreeSet.this.order - 1) / 2; 225 226 BTreeNode(BTreeNode parent) { 227 this.parent = parent; 228 entries = new Entry[BTreeSet.this.order]; 229 entries[0] = new Entry(); 230 } 231 232 boolean insert(Object x, int parentIndex) { 233 if (isFull()) { Object splitNode = entries[nrElements / 2].element; 235 BTreeNode rightSibling = split(); 236 237 if (isRoot()) { splitRoot(splitNode, this, rightSibling); 239 if (BTreeSet.this.compare(x, BTreeSet.this.root.entries[0].element) < 0) insert(x, 0); 241 else rightSibling.insert(x, 1); 242 } 243 244 else { parent.insertSplitNode(splitNode, this, rightSibling, parentIndex); 246 if (BTreeSet.this.compare(x, parent.entries[parentIndex].element) < 0) return insert(x, parentIndex); 247 else return rightSibling.insert(x, parentIndex + 1); 248 } 249 } 250 251 else if (isLeaf()) { int insertAt = childToInsertAt(x, true); 253 if (insertAt == -1) return false; else { 255 insertNewElement(x, insertAt); 256 BTreeSet.this.size++; 257 return true; 258 } 259 } 260 261 else { int insertAt = childToInsertAt(x, true); 263 return (insertAt == -1 ? false : entries[insertAt].child.insert(x, insertAt)); 264 } 265 return false; 266 } 267 268 boolean includes(Object x) { 269 int index = childToInsertAt(x, true); 270 if (index == -1) return true; 271 if (entries[index] == null || entries[index].child == null) return false; 272 return entries[index].child.includes(x); 273 } 274 275 boolean delete(Object x, int parentIndex) { 276 int i = childToInsertAt(x, true); 277 int priorParentIndex = parentIndex; 278 BTreeNode temp = this; 279 if (i != -1) { 280 do { 281 if (temp.entries[i] == null || temp.entries[i].child == null) return false; 282 temp = temp.entries[i].child; 283 priorParentIndex = parentIndex; 284 parentIndex = i; 285 i = temp.childToInsertAt(x, true); 286 } while (i != -1); 287 } 289 if (temp.isLeaf()) { if (temp.nrElements > MIN) { 291 temp.deleteElement(x); 292 BTreeSet.this.size--; 293 return true; 294 } 295 296 else { temp.prepareForDeletion(parentIndex); 298 temp.deleteElement(x); 299 BTreeSet.this.size--; 300 temp.fixAfterDeletion(priorParentIndex); 301 return true; 302 } 303 } 304 305 else { temp.switchWithSuccessor(x); 307 parentIndex = temp.childToInsertAt(x, false) + 1; 308 return temp.entries[parentIndex].child.delete(x, parentIndex); 309 } 310 } 311 312 313 private boolean isFull() { return nrElements == (BTreeSet.this.order - 1); } 314 315 private boolean isLeaf() { return entries[0].child == null; } 316 317 private boolean isRoot() { return parent == null; } 318 319 323 private BTreeNode split() { 324 BTreeNode rightSibling = new BTreeNode(parent); 325 int index = nrElements / 2; 326 entries[index++].element = null; 327 328 for (int i = 0, nr = nrElements; index <= nr; i++, index++) { 329 rightSibling.entries[i] = entries[index]; 330 if (rightSibling.entries[i] != null && rightSibling.entries[i].child != null) 331 rightSibling.entries[i].child.parent = rightSibling; 332 entries[index] = null; 333 nrElements--; 334 rightSibling.nrElements++; 335 } 336 337 rightSibling.nrElements--; return rightSibling; 339 } 340 341 345 private void splitRoot(Object splitNode, BTreeNode left, BTreeNode right) { 346 BTreeNode newRoot = new BTreeNode(null); 347 newRoot.entries[0].element = splitNode; 348 newRoot.entries[0].child = left; 349 newRoot.entries[1] = new Entry(); 350 newRoot.entries[1].child = right; 351 newRoot.nrElements = 1; 352 left.parent = right.parent = newRoot; 353 BTreeSet.this.root = newRoot; 354 } 355 356 private void insertSplitNode(Object splitNode, BTreeNode left, BTreeNode right, int insertAt) { 357 for (int i = nrElements; i >= insertAt; i--) entries[i + 1] = entries[i]; 358 359 entries[insertAt] = new Entry(); 360 entries[insertAt].element = splitNode; 361 entries[insertAt].child = left; 362 entries[insertAt + 1].child = right; 363 364 nrElements++; 365 } 366 367 private void insertNewElement(Object x, int insertAt) { 368 369 for (int i = nrElements; i > insertAt; i--) entries[i] = entries[i - 1]; 370 371 entries[insertAt] = new Entry(); 372 entries[insertAt].element = x; 373 374 nrElements++; 375 } 376 377 386 private int childToInsertAt(Object x, boolean position) { 387 int index = nrElements / 2; 388 389 if (entries[index] == null || entries[index].element == null) return index; 390 391 int lo = 0, hi = nrElements - 1; 392 while (lo <= hi) { 393 if (BTreeSet.this.compare(x, entries[index].element) > 0) { 394 lo = index + 1; 395 index = (hi + lo) / 2; 396 } 397 else { 398 hi = index - 1; 399 index = (hi + lo) / 2; 400 } 401 } 402 403 hi++; 404 if (entries[hi] == null || entries[hi].element == null) return hi; 405 return (!position ? hi : BTreeSet.this.compare(x, entries[hi].element) == 0 ? -1 : hi); 406 } 407 408 409 private void deleteElement(Object x) { 410 int index = childToInsertAt(x, false); 411 for (; index < (nrElements - 1); index++) entries[index] = entries[index + 1]; 412 413 if (nrElements == 1) entries[index] = new Entry(); else entries[index] = null; 415 416 nrElements--; 417 } 418 419 private void prepareForDeletion(int parentIndex) { 420 if (isRoot()) return; 422 else if (parentIndex != 0 && parent.entries[parentIndex - 1].child.nrElements > MIN) { 424 stealLeft(parentIndex); 425 return; 426 } 427 428 else if (parentIndex < entries.length && parent.entries[parentIndex + 1] != null && parent.entries[parentIndex + 1].child != null && parent.entries[parentIndex + 1].child.nrElements > MIN) { 430 stealRight(parentIndex); 431 return; 432 } 433 434 else if (parentIndex != 0) { 436 mergeLeft(parentIndex); 437 return; 438 } 439 440 else mergeRight(parentIndex); 442 } 443 444 private void fixAfterDeletion(int parentIndex) { 445 if (isRoot() || parent.isRoot()) return; 447 if (parent.nrElements < MIN) { BTreeNode temp = parent; 449 temp.prepareForDeletion(parentIndex); 450 if (temp.parent == null) return; if (!temp.parent.isRoot() && temp.parent.nrElements < MIN) { BTreeNode x = temp.parent.parent; 453 int i = 0; 454 for (; i < entries.length; i++) if (x.entries[i].child == temp.parent) break; 456 temp.parent.fixAfterDeletion(i); 457 } 458 } 459 } 460 461 private void switchWithSuccessor(Object x) { 462 int index = childToInsertAt(x, false); 463 BTreeNode temp = entries[index + 1].child; 464 while (temp.entries[0] != null && temp.entries[0].child != null) temp = temp.entries[0].child; 465 Object successor = temp.entries[0].element; 466 temp.entries[0].element = entries[index].element; 467 entries[index].element = successor; 468 } 469 470 474 private void stealLeft(int parentIndex) { 475 BTreeNode p = parent; 476 BTreeNode ls = parent.entries[parentIndex - 1].child; 477 478 if (isLeaf()) { int add = childToInsertAt(p.entries[parentIndex - 1].element, true); 480 insertNewElement(p.entries[parentIndex - 1].element, add); 481 p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element; 482 ls.entries[ls.nrElements - 1] = null; 483 ls.nrElements--; 484 } 485 486 else { entries[0].element = p.entries[parentIndex - 1].element; 488 p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element; 489 entries[0].child = ls.entries[ls.nrElements].child; 490 entries[0].child.parent = this; 491 ls.entries[ls.nrElements] = null; 492 ls.entries[ls.nrElements - 1].element = null; 493 nrElements++; 494 ls.nrElements--; 495 } 496 } 497 498 503 private void stealRight(int parentIndex) { 504 BTreeNode p = parent; 505 BTreeNode rs = p.entries[parentIndex + 1].child; 506 507 if (isLeaf()) { entries[nrElements] = new Entry(); 509 entries[nrElements].element = p.entries[parentIndex].element; 510 p.entries[parentIndex].element = rs.entries[0].element; 511 for (int i = 0; i < rs.nrElements; i++) rs.entries[i] = rs.entries[i + 1]; 512 rs.entries[rs.nrElements - 1] = null; 513 nrElements++; 514 rs.nrElements--; 515 } 516 517 else { for (int i = 0; i <= nrElements; i++) entries[i] = entries[i + 1]; 519 entries[nrElements].element = p.entries[parentIndex].element; 520 p.entries[parentIndex].element = rs.entries[0].element; 521 entries[nrElements + 1] = new Entry(); 522 entries[nrElements + 1].child = rs.entries[0].child; 523 entries[nrElements + 1].child.parent = this; 524 for (int i = 0; i <= rs.nrElements; i++) rs.entries[i] = rs.entries[i + 1]; 525 rs.entries[rs.nrElements] = null; 526 nrElements++; 527 rs.nrElements--; 528 } 529 } 530 531 540 private void mergeLeft(int parentIndex) { 541 BTreeNode p = parent; 542 BTreeNode ls = p.entries[parentIndex - 1].child; 543 544 if (isLeaf()) { int add = childToInsertAt(p.entries[parentIndex - 1].element, true); 546 insertNewElement(p.entries[parentIndex - 1].element, add); p.entries[parentIndex - 1].element = null; 548 549 for (int i = nrElements - 1, nr = ls.nrElements; i >= 0; i--) 550 entries[i + nr] = entries[i]; 551 552 for (int i = ls.nrElements - 1; i >= 0; i--) { 553 entries[i] = ls.entries[i]; 554 nrElements++; 555 } 556 557 if (p.nrElements == MIN && p != BTreeSet.this.root) { 558 559 for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--) 560 p.entries[x] = p.entries[y]; 561 p.entries[0] = new Entry(); 562 p.entries[0].child = ls; } 564 565 else { 566 567 for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++) 568 p.entries[x] = p.entries[y]; 569 p.entries[p.nrElements] = null; 570 } 571 572 p.nrElements--; 573 574 if (p.isRoot() && p.nrElements == 0) { BTreeSet.this.root = this; 576 parent = null; 577 } 578 } 579 580 else { entries[0].element = p.entries[parentIndex - 1].element; 582 entries[0].child = ls.entries[ls.nrElements].child; 583 nrElements++; 584 585 for (int x = nrElements, nr = ls.nrElements; x >= 0; x--) 586 entries[x + nr] = entries[x]; 587 588 for (int x = ls.nrElements - 1; x >= 0; x--) { 589 entries[x] = ls.entries[x]; 590 entries[x].child.parent = this; 591 nrElements++; 592 } 593 594 if (p.nrElements == MIN && p != BTreeSet.this.root) { for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x++, y++){ 596 System.out.println(x + " " + y); 597 p.entries[x] = p.entries[y];} 598 p.entries[0] = new Entry(); 599 } 600 601 else { for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++) 603 p.entries[x] = p.entries[y]; 604 p.entries[p.nrElements] = null; 605 } 606 607 p.nrElements--; 608 609 if (p.isRoot() && p.nrElements == 0) { BTreeSet.this.root = this; 611 parent = null; 612 } 613 } 614 } 615 616 625 private void mergeRight(int parentIndex) { 626 BTreeNode p = parent; 627 BTreeNode rs = p.entries[parentIndex + 1].child; 628 629 if (isLeaf()) { entries[nrElements] = new Entry(); 631 entries[nrElements].element = p.entries[parentIndex].element; 632 nrElements++; 633 for (int i = 0, nr = nrElements; i < rs.nrElements; i++, nr++) { 634 entries[nr] = rs.entries[i]; 635 nrElements++; 636 } 637 p.entries[parentIndex].element = p.entries[parentIndex + 1].element; 638 if (p.nrElements == MIN && p != BTreeSet.this.root) { 639 for (int x = parentIndex + 1, y = parentIndex; y >= 0; x--, y--) 640 p.entries[x] = p.entries[y]; 641 p.entries[0] = new Entry(); 642 p.entries[0].child = rs; } 644 645 else { 646 for (int x = parentIndex + 1, y = parentIndex + 2; y <= p.nrElements; x++, y++) 647 p.entries[x] = p.entries[y]; 648 p.entries[p.nrElements] = null; 649 } 650 651 p.nrElements--; 652 if (p.isRoot() && p.nrElements == 0) { BTreeSet.this.root = this; 654 parent = null; 655 } 656 } 657 658 else { 660 entries[nrElements].element = p.entries[parentIndex].element; 661 nrElements++; 662 663 for (int x = nrElements + 1, y = 0; y <= rs.nrElements; x++, y++) { 664 entries[x] = rs.entries[y]; 665 rs.entries[y].child.parent = this; 666 nrElements++; 667 } 668 nrElements--; 669 670 p.entries[++parentIndex].child = this; 671 672 if (p.nrElements == MIN && p != BTreeSet.this.root) { 673 for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--) 674 p.entries[x] = p.entries[y]; 675 p.entries[0] = new Entry(); 676 } 677 678 else { 679 for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++) 680 p.entries[x] = p.entries[y]; 681 p.entries[p.nrElements] = null; 682 } 683 684 p.nrElements--; 685 686 if (p.isRoot() && p.nrElements == 0) { BTreeSet.this.root = this; 688 parent = null; 689 } 690 } 691 } 692 } 693 } 694 695 | Popular Tags |