1 package com.daffodilwoods.database.general; 2 3 import java.util.*; 4 import com.daffodilwoods.database.resource.*; 5 import com.daffodilwoods.daffodildb.utils.comparator.SuperComparator; 6 public class OrderedKeyList { 8 14 private SuperComparator comparator = null; 15 16 private transient Entry root = null; 17 18 private Entry current = null; 19 20 23 private transient int size = 0; 24 25 28 private transient int modCount = 0; 29 30 private void incrementSize() throws DException { size++; } 31 private void decrementSize() throws DException { size--; } 32 private static final boolean RED = false; 33 private static final boolean BLACK = true; 34 35 public OrderedKeyList(SuperComparator comparator) { 36 this.comparator = comparator; 37 } 38 39 public int size() throws DException { 40 return size; 41 } 42 43 public boolean containsKey(Object key) throws DException { 44 return getEntry(key) != null; 45 } 46 47 public int getRowCount() throws DException { 48 return size; 49 } 50 51 public boolean containsValue(Object value) throws DException { 52 return (root==null ? false : 53 (value==null ? valueSearchNull(root) 54 : valueSearchNonNull(root, value))); 55 } 56 57 private boolean valueSearchNull(Entry n) throws DException { 58 if (n.value == null) 59 return true; 60 61 return (n.left != null && valueSearchNull(n.left)) || 62 (n.right != null && valueSearchNull(n.right)); 63 } 64 65 68 69 private boolean valueSearchNonNull(Entry n, Object value) throws DException { 70 if (value.equals(n.value)) 71 return true; 72 73 return (n.left != null && valueSearchNonNull(n.left, value)) || 74 (n.right != null && valueSearchNonNull(n.right, value)); 75 } 76 77 public Object getRootKey() throws DException { 78 return root.key; 79 } 80 81 public Entry getKeyEntry() throws DException { 82 return current; 83 } 84 89 public Object getObject(Object key) throws DException { 90 Entry p = getEntry(key); 91 return p==null ? null : p.value; 92 } 93 94 95 public Object getTopKey() throws DException { 96 Entry p = firstEntry(); 97 return p==null ? null : p.key; 98 } 99 100 public Object getPreviousKey(Object key) throws DException { 101 Entry k = getEntry(key); 102 Entry p = predeccesor(k); 103 return p==null ? null : p.key; 104 } 105 106 public Object getNextKey(Object key) throws DException { 107 Entry k = getEntry(key); 108 Entry p = successor(k); 109 return p==null ? null : p.key; 110 } 111 112 public Object getBottomKey() throws DException { 113 Entry p = lastEntry(); 114 return p==null ? null : p.key; 115 } 116 public boolean top() throws DException { 117 current = firstEntry(); 118 return current != null ; } 120 121 private Entry getEntry(Object key) throws DException { 122 Entry p = root; 123 while (p != null) { 124 int cmp = compare(key,p.key); 125 if (cmp == 0) 126 return p; 127 else if (cmp < 0) 128 p = p.left; 129 else 130 p = p.right; 131 } 132 return null; 133 } 134 135 public Object locateNearestRecord(Object value) throws DException { 136 Entry p = root; 137 while (p != null) { 138 int cmp = compare(value,p.key); 139 if (cmp == 0) 140 return p.key; 141 else if (cmp < 0){ 142 if(p.left == null) 143 return p.key; 144 p = p.left; 145 } 146 else{ 147 if(p.right == null) 148 return p.key; 149 p = p.right; 150 } 151 } 152 return null; 153 } 154 155 public boolean locateKey(Object value) throws DException { 156 return getEntry(value) != null; 157 } 158 159 private Object locateKey1(Object value) throws DException { 160 Entry p = root; 161 while (p != null) { 162 int cmp = compare(value,p.value); 163 if (cmp == 0) 164 return p; 165 else if (cmp < 0) 166 p = p.left; 167 else 168 p = p.right; 169 } 170 return null; 171 } 172 173 public void changeCurrentKey(Object object,Object oldKey) throws DException { 174 Object key = locateKey1(object); 175 if(key == null) 176 return; 177 moveToKey(key); 178 } 179 180 public synchronized void insert(Object key, Object value) throws DException { 181 186 187 Entry t = root; 188 189 if (t == null) { 190 incrementSize(); 191 root = new Entry(key, value, null); 192 current = root; 193 return ; 194 } 195 196 while (true) { 197 int cmp = compare(key, t.key); 198 if (cmp == 0) { 199 t.setValue(value); 200 return; 201 } else if (cmp < 0) { 202 if (t.left != null) { 203 t = t.left; 204 } else { 205 incrementSize(); 206 t.left = new Entry(key, value, t); 207 fixAfterInsertion(t.left); 208 return ; 209 } 210 } else { if (t.right != null) { 212 t = t.right; 213 } else { 214 incrementSize(); 215 t.right = new Entry(key, value, t); 216 fixAfterInsertion(t.right); 217 return ; 218 } 219 } 220 } 221 } 222 223 public void remove(Object key) throws DException { 224 try{ 225 delete(key); 226 }catch(Exception ex){} 227 } 228 229 public synchronized void delete(Object key) throws DException{ 230 if(current == null) 231 throw new DException("DSE986",null); 232 else if( key == null) 233 throw new DException("DSE982",null); 234 Entry p = getEntry(key); 235 236 if(p == null || p.value == null) 237 throw new DException("DSE978",null); 238 if(current == p){ 239 if( ! next()) if(! previous()) 241 current = null; 242 } 243 deleteEntry(p); 244 p.value = null; 245 return ; 246 } 247 248 257 public boolean previous() throws DException { 258 Entry p = predeccesor(current); 259 if(p == null) 260 return false; 261 current = p; 262 return true; 263 } 264 265 public boolean bottom() throws DException { 266 current = lastEntry(); 267 return current != null ; 268 } 269 270 public boolean next() throws DException { 271 Entry p = successor(current); 272 if(p != null) { 273 current = p; 274 return true; 275 } 276 else 277 return false; 278 } 279 280 286 287 public boolean isTop() throws DException { 288 if( current == null || current.left != null ) 289 return false; 290 else { 291 Entry p = firstEntry(); 292 return (p != null && current == p); 293 } 294 } 295 296 302 303 public boolean isBottom() throws DException { 304 if( current == null || current.right != null) 305 return false; 306 else { 307 Entry p = lastEntry(); 308 return (p != null && current == p) ; 309 } 310 } 311 316 317 public boolean isNext() throws DException { 318 return current == null ? false : 319 current.right != null ? true : 320 successor(current) != null ; 321 } 322 327 public boolean isPrevious() throws DException { 328 return current == null ? false : 329 current.left != null ? true 330 : predeccesor(current)!= null ; 331 } 332 333 public void moveToKey(Object key) { try { 335 if(current == null) 336 throw new DException("DSE562",null); 337 else if(key == null) 338 throw new DException("DSE554",null); 339 Entry p = getEntry(key); 340 current = p == null ? current : p; 341 } 342 catch(Exception e) { 343 e.printStackTrace(); 344 } 345 } 346 347 public Object getKey() throws DException { 348 return current == null ? null : current.key; 349 } 350 351 354 public Object getObject() throws DException { 355 return current == null ? null : current.value; 356 } 357 358 protected int compare(Object k1, Object k2) throws DException { 359 return (comparator==null ? ((Comparable )k1).compareTo(k2) 360 : comparator.compare(k1, k2)); 361 } 362 363 private Entry firstEntry() throws DException { 364 Entry p = root; 365 if (p != null) 366 while (p.left != null) 367 p = p.left; 368 return p; 369 } 370 371 375 private Entry lastEntry() throws DException { 376 Entry p = root; 377 if (p != null) 378 while (p.right != null) 379 p = p.right; 380 return p; 381 } 382 383 386 private Entry successor(Entry t) throws DException { 387 if (t == null) 388 return null; 389 else if (t.right != null) { 390 Entry p = t.right; 391 while (p.left != null) 392 p = p.left; 393 return p; 394 } else { 395 Entry p = t.parent; 396 Entry ch = t; 397 while (p != null && ch == p.right) { 398 ch = p; 399 p = p.parent; 400 } 401 return p; 402 } 403 } 404 405 414 415 private static boolean colorOf(Entry p) throws DException { 416 return (p == null ? BLACK : p.color); 417 } 418 419 private static Entry parentOf(Entry p) throws DException { 420 return (p == null ? null: p.parent); 421 } 422 423 private static void setColor(Entry p, boolean c) throws DException { 424 if (p != null) p.color = c; 425 } 426 427 private static Entry leftOf(Entry p) throws DException { 428 return (p == null)? null: p.left; 429 } 430 431 private static Entry rightOf(Entry p) throws DException { 432 return (p == null)? null: p.right; 433 } 434 435 436 private void rotateLeft(Entry p) throws DException { 437 Entry r = p.right; 438 p.right = r.left; 439 if (r.left != null) 440 r.left.parent = p; 441 r.parent = p.parent; 442 if (p.parent == null) 443 root = r; 444 else if (p.parent.left == p) 445 p.parent.left = r; 446 else 447 p.parent.right = r; 448 r.left = p; 449 p.parent = r; 450 } 451 452 453 private void rotateRight(Entry p) throws DException { 454 Entry l = p.left; 455 p.left = l.right; 456 if (l.right != null) l.right.parent = p; 457 l.parent = p.parent; 458 if (p.parent == null) 459 root = l; 460 else if (p.parent.right == p) 461 p.parent.right = l; 462 else p.parent.left = l; 463 l.right = p; 464 p.parent = l; 465 } 466 467 468 469 private void fixAfterInsertion(Entry x) throws DException { 470 x.color = RED; 471 472 while (x != null && x != root && x.parent.color == RED) { 473 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 474 Entry y = rightOf(parentOf(parentOf(x))); 475 if (colorOf(y) == RED) { 476 setColor(parentOf(x), BLACK); 477 setColor(y, BLACK); 478 setColor(parentOf(parentOf(x)), RED); 479 x = parentOf(parentOf(x)); 480 } else { 481 if (x == rightOf(parentOf(x))) { 482 x = parentOf(x); 483 rotateLeft(x); 484 } 485 setColor(parentOf(x), BLACK); 486 setColor(parentOf(parentOf(x)), RED); 487 if (parentOf(parentOf(x)) != null) 488 rotateRight(parentOf(parentOf(x))); 489 } 490 } else { 491 Entry y = leftOf(parentOf(parentOf(x))); 492 if (colorOf(y) == RED) { 493 setColor(parentOf(x), BLACK); 494 setColor(y, BLACK); 495 setColor(parentOf(parentOf(x)), RED); 496 x = parentOf(parentOf(x)); 497 } else { 498 if (x == leftOf(parentOf(x))) { 499 x = parentOf(x); 500 rotateRight(x); 501 } 502 setColor(parentOf(x), BLACK); 503 setColor(parentOf(parentOf(x)), RED); 504 if (parentOf(parentOf(x)) != null) 505 rotateLeft(parentOf(parentOf(x))); 506 } 507 } 508 } 509 root.color = BLACK; 510 } 511 512 515 private void deleteEntry(Entry p) throws DException { 516 decrementSize(); 517 518 if (p.left != null && p.right != null) { 519 Entry s = successor(p); 520 swapPosition(s, p); 521 } 522 523 Entry replacement = (p.left != null ? p.left : p.right); 524 525 if (replacement != null) { 526 replacement.parent = p.parent; 527 if (p.parent == null) 528 root = replacement; 529 else if (p == p.parent.left) 530 p.parent.left = replacement; 531 else 532 p.parent.right = replacement; 533 534 p.left = p.right = p.parent = null; 535 536 if (p.color == BLACK) 537 fixAfterDeletion(replacement); 538 } else if (p.parent == null) { root = null; 540 } else { if (p.color == BLACK) 542 fixAfterDeletion(p); 543 544 if (p.parent != null) { 545 if (p == p.parent.left) 546 p.parent.left = null; 547 else if (p == p.parent.right) 548 p.parent.right = null; 549 p.parent = null; 550 } 551 } 552 } 553 554 555 556 private Entry predeccesor(Entry t) throws DException { 557 if (t == null) 558 return null; 559 else if (t.left != null) { 560 Entry p = t.left; 561 while (p.right != null) 562 p = p.right; 563 return p; 564 } 565 else { 566 Entry p = t.parent; 567 Entry ch = t; 568 while (p != null && ch == p.left) { 569 ch = p; 570 p = p.parent; 571 } 572 return p; 573 } 574 } 575 576 public void show(){ 577 try{ 578 Object iter = getTopKey(); 579 if(iter != null){ 580 do{ 581 iter = getNextKey(iter); 582 }while(iter != null); 583 }else 584 ; }catch(DException E){E.printStackTrace();} 586 } 587 588 public OrderedKeyListIterator getIterator() throws DException { 589 return new OrderedKeyListIterator(); 590 } 591 592 593 private void fixAfterDeletion(Entry x) throws DException { 594 while (x != root && colorOf(x) == BLACK) { 595 if (x == leftOf(parentOf(x))) { 596 Entry sib = rightOf(parentOf(x)); 597 598 if (colorOf(sib) == RED) { 599 setColor(sib, BLACK); 600 setColor(parentOf(x), RED); 601 rotateLeft(parentOf(x)); 602 sib = rightOf(parentOf(x)); 603 } 604 605 if (colorOf(leftOf(sib)) == BLACK && 606 colorOf(rightOf(sib)) == BLACK) { 607 setColor(sib, RED); 608 x = parentOf(x); 609 } else { 610 if (colorOf(rightOf(sib)) == BLACK) { 611 setColor(leftOf(sib), BLACK); 612 setColor(sib, RED); 613 rotateRight(sib); 614 sib = rightOf(parentOf(x)); 615 } 616 setColor(sib, colorOf(parentOf(x))); 617 setColor(parentOf(x), BLACK); 618 setColor(rightOf(sib), BLACK); 619 rotateLeft(parentOf(x)); 620 x = root; 621 } 622 } else { Entry sib = leftOf(parentOf(x)); 624 625 if (colorOf(sib) == RED) { 626 setColor(sib, BLACK); 627 setColor(parentOf(x), RED); 628 rotateRight(parentOf(x)); 629 sib = leftOf(parentOf(x)); 630 } 631 632 if (colorOf(rightOf(sib)) == BLACK && 633 colorOf(leftOf(sib)) == BLACK) { 634 setColor(sib, RED); 635 x = parentOf(x); 636 } else { 637 if (colorOf(leftOf(sib)) == BLACK) { 638 setColor(rightOf(sib), BLACK); 639 setColor(sib, RED); 640 rotateLeft(sib); 641 sib = leftOf(parentOf(x)); 642 } 643 setColor(sib, colorOf(parentOf(x))); 644 setColor(parentOf(x), BLACK); 645 setColor(leftOf(sib), BLACK); 646 rotateRight(parentOf(x)); 647 x = root; 648 } 649 } 650 } 651 652 setColor(x, BLACK); 653 } 654 655 658 private void swapPosition(Entry x, Entry y) throws DException { 659 Entry px = x.parent, lx = x.left, rx = x.right; 660 Entry py = y.parent, ly = y.left, ry = y.right; 661 boolean xWasLeftChild = px != null && x == px.left; 662 boolean yWasLeftChild = py != null && y == py.left; 663 664 if (x == py) { x.parent = y; 666 if (yWasLeftChild) { 667 y.left = x; 668 y.right = rx; 669 } else { 670 y.right = x; 671 y.left = lx; 672 } 673 } else { 674 x.parent = py; 675 if (py != null) { 676 if (yWasLeftChild) 677 py.left = x; 678 else 679 py.right = x; 680 } 681 y.left = lx; 682 y.right = rx; 683 } 684 685 if (y == px) { y.parent = x; 687 if (xWasLeftChild) { 688 x.left = y; 689 x.right = ry; 690 } else { 691 x.right = y; 692 x.left = ly; 693 } 694 } else { 695 y.parent = px; 696 if (px != null) { 697 if (xWasLeftChild) 698 px.left = y; 699 else 700 px.right = y; 701 } 702 x.left = ly; 703 x.right = ry; 704 } 705 706 if (x.left != null) 707 x.left.parent = x; 708 if (x.right != null) 709 x.right.parent = x; 710 if (y.left != null) 711 y.left.parent = y; 712 if (y.right != null) 713 y.right.parent = y; 714 715 boolean c = x.color; 716 x.color = y.color; 717 y.color = c; 718 719 if (root == x) 720 root = y; 721 else if (root == y) 722 root = x; 723 } 724 725 public class Entry { public Object key; 727 Object value; 728 public Entry left = null; 729 public Entry right = null; 730 Entry parent; 731 boolean color = BLACK; 732 733 737 Entry(Object key, Object value, Entry parent) { 738 this.key = key; 739 this.value = value; 740 this.parent = parent; 741 } 742 743 748 public Object getKey() throws DException { 749 return key; 750 } 751 752 757 public Object getValue() throws DException { 758 return value; 759 } 760 761 768 public Object setValue(Object value) throws DException { 769 Object oldValue = this.value; 770 this.value = value; 771 return oldValue; 772 } 773 774 781 782 public int hashCode() { 783 int keyHash = (key==null ? 0 : key.hashCode()); 784 int valueHash = (value==null ? 0 : value.hashCode()); 785 return keyHash ^ valueHash; 786 } 787 788 public String toString() { return key + "=" + value; 789 } 790 } 791 792 public class OrderedKeyListIterator { 793 Object current; 794 795 public OrderedKeyListIterator() throws DException { 796 current = getTopKey(); 797 } 798 799 public Object locateNearestRecord(Object value) throws DException { 800 return OrderedKeyList.this.locateNearestRecord(value); 801 } 802 803 public int getRowCount() throws DException { 804 return size(); 805 } 806 807 public boolean top() throws DException { 808 current = getTopKey(); 809 return current != null; 810 } 811 812 public boolean bottom() throws DException { 813 current = getBottomKey(); 814 return current != null; 815 } 816 817 public void changeCurrentKey(Object object,Object oldKey) throws DException{ 818 Entry entry = getEntry(object); 819 if(entry == null) 820 return; 821 moveToKey(entry.key); 822 } 823 824 public boolean previous() throws DException { 825 Object p = getPreviousKey(current); 826 if(p == null) 827 return false; 828 current = p; 829 return true; 830 } 831 832 public boolean next() throws DException { 833 Object p = getNextKey(current); 834 if(p == null) 835 return false; 836 current = p; 837 return true; 838 } 839 840 public boolean isTop() throws DException { 841 if( current == null ) 842 return false; 843 else { 844 Object p = getTopKey(); 845 return (p != null && current == p); 846 } 847 } 848 849 public boolean isBottom() throws DException { 850 if( current == null ) 851 return false; 852 else { 853 Object p = getBottomKey(); 854 return (p != null && current == p) ; 855 } 856 } 857 858 public boolean isPrevious() throws DException { 859 return current == null ? false : 860 getPreviousKey(current) != null ; 861 } 862 863 public boolean isNext() throws DException { 864 return current == null ? false : 865 getNextKey(current) != null ; 866 } 867 868 public void moveToKey(Object key) throws DException 869 { 870 if(key == null) 871 throw new DException("DSE982",null); 872 873 current = key; 874 } 875 876 public Object getKey() throws DException { 877 Entry e = getEntry(current); 878 if(current!=null && e.getValue() == null){ 879 Object nextKey = getNextKey(current); 880 if(nextKey == null ) { 881 Object previousKey = getPreviousKey(current); 882 if(previousKey == null) 883 return null; 884 else 885 current = previousKey; 886 } 887 else 888 current = nextKey; 889 } 890 return current; 891 } 892 893 public Object getObject() throws DException { 894 return OrderedKeyList.this.getObject(current); 895 } 896 897 public Comparator getComparator() throws DException { 898 return getComparator(); 899 } 900 } 901 902 } 903 | Popular Tags |