001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020package org.apache.directory.mavibot.btree; 021 022 023import java.io.IOException; 024import java.util.NoSuchElementException; 025 026import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException; 027 028 029/** 030 * A Cursor is used to fetch elements in a BTree and is returned by the 031 * @see BTree#browse method. The cursor <strng>must</strong> be closed 032 * when the user is done with it. 033 * <p> 034 * 035 * @param <K> The type for the Key 036 * @param <V> The type for the stored value 037 * 038 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 039 */ 040public class TupleCursor<K, V> 041{ 042 /** A marker to tell that we are before the first element */ 043 private static final int BEFORE_FIRST = -1; 044 045 /** A marker to tell that we are after the last element */ 046 private static final int AFTER_LAST = -2; 047 048 /** The stack of pages from the root down to the leaf */ 049 protected ParentPos<K, V>[] stack; 050 051 /** The stack's depth */ 052 protected int depth = 0; 053 054 /** The transaction used for this cursor */ 055 protected ReadTransaction<K, V> transaction; 056 057 058 /** 059 * Creates a new instance of Cursor. 060 */ 061 protected TupleCursor() 062 { 063 } 064 065 066 /** 067 * Creates a new instance of Cursor, starting on a page at a given position. 068 * 069 * @param transaction The transaction this operation is protected by 070 * @param stack The stack of parent's from root to this page 071 */ 072 public TupleCursor( ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth ) 073 { 074 this.transaction = transaction; 075 this.stack = stack; 076 this.depth = depth; 077 } 078 079 080 /** 081 * Change the position in the current cursor to set it after the last key 082 */ 083 public void afterLast() throws IOException 084 { 085 // First check that we have elements in the BTree 086 if ( ( stack == null ) || ( stack.length == 0 ) ) 087 { 088 return; 089 } 090 091 Page<K, V> child = null; 092 093 for ( int i = 0; i < depth; i++ ) 094 { 095 ParentPos<K, V> parentPos = stack[i]; 096 097 if ( child != null ) 098 { 099 parentPos.page = child; 100 parentPos.pos = child.getNbElems(); 101 } 102 else 103 { 104 // We have N+1 children if the page is a Node, so we don't decrement the nbElems field 105 parentPos.pos = parentPos.page.getNbElems(); 106 } 107 108 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos ); 109 } 110 111 // and leaf 112 ParentPos<K, V> parentPos = stack[depth]; 113 114 if ( child == null ) 115 { 116 parentPos.pos = parentPos.page.getNbElems() - 1; 117 } 118 else 119 { 120 parentPos.page = child; 121 parentPos.pos = child.getNbElems() - 1; 122 } 123 124 parentPos.valueCursor = ( ( AbstractPage<K, V> ) parentPos.page ).getValue( parentPos.pos ).getCursor(); 125 parentPos.valueCursor.afterLast(); 126 parentPos.pos = AFTER_LAST; 127 } 128 129 130 /** 131 * Change the position in the current cursor before the first key 132 */ 133 public void beforeFirst() throws IOException 134 { 135 // First check that we have elements in the BTree 136 if ( ( stack == null ) || ( stack.length == 0 ) ) 137 { 138 return; 139 } 140 141 Page<K, V> child = null; 142 143 for ( int i = 0; i < depth; i++ ) 144 { 145 ParentPos<K, V> parentPos = stack[i]; 146 parentPos.pos = 0; 147 148 if ( child != null ) 149 { 150 parentPos.page = child; 151 } 152 153 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( 0 ); 154 } 155 156 // and leaf 157 ParentPos<K, V> parentPos = stack[depth]; 158 parentPos.pos = BEFORE_FIRST; 159 160 if ( child != null ) 161 { 162 parentPos.page = child; 163 } 164 165 if ( parentPos.valueCursor != null ) 166 { 167 parentPos.valueCursor = ( ( AbstractPage<K, V> ) parentPos.page ).getValue( 0 ).getCursor(); 168 parentPos.valueCursor.beforeFirst(); 169 } 170 } 171 172 173 /** 174 * Tells if the cursor can return a next element 175 * 176 * @return true if there are some more elements 177 * @throws IOException 178 * @throws EndOfFileExceededException 179 */ 180 public boolean hasNext() throws EndOfFileExceededException, IOException 181 { 182 // First check that we have elements in the BTree 183 if ( ( stack == null ) || ( stack.length == 0 ) ) 184 { 185 return false; 186 } 187 188 // Take the leaf and check if we have no mare values 189 ParentPos<K, V> parentPos = stack[depth]; 190 191 if ( parentPos.page == null ) 192 { 193 // Empty BTree, get out 194 return false; 195 } 196 197 if ( parentPos.pos == AFTER_LAST ) 198 { 199 // Ok, here, we have reached the last value in the leaf. We have to go up and 200 // see if we have some remaining values 201 int currentDepth = depth - 1; 202 203 while ( currentDepth >= 0 ) 204 { 205 parentPos = stack[currentDepth]; 206 207 if ( parentPos.pos < parentPos.page.getNbElems() ) 208 { 209 // The parent has some remaining values on the right, get out 210 return true; 211 } 212 else 213 { 214 currentDepth--; 215 } 216 } 217 218 return false; 219 } 220 221 if ( parentPos.pos < parentPos.page.getNbElems() - 1 ) 222 { 223 // Not the last position, we have a next value 224 return true; 225 } 226 else 227 { 228 // Check if we have some more value 229 if ( ( parentPos.valueCursor != null ) && parentPos.valueCursor.hasNext() ) 230 { 231 // No problem, we still have some values to read 232 return true; 233 } 234 235 // Ok, here, we have reached the last value in the leaf. We have to go up and 236 // see if we have some remaining values 237 int currentDepth = depth - 1; 238 239 while ( currentDepth >= 0 ) 240 { 241 parentPos = stack[currentDepth]; 242 243 if ( parentPos.pos < parentPos.page.getNbElems() ) 244 { 245 // The parent has some remaining values on the right, get out 246 return true; 247 } 248 else 249 { 250 currentDepth--; 251 } 252 } 253 254 // We are done, there are no more value left 255 return false; 256 } 257 } 258 259 260 /** 261 * Find the next key/value 262 * 263 * @return A Tuple containing the found key and value 264 * @throws IOException 265 * @throws EndOfFileExceededException 266 */ 267 public Tuple<K, V> next() throws EndOfFileExceededException, IOException 268 { 269 // First check that we have elements in the BTree 270 if ( ( stack == null ) || ( stack.length == 0 ) ) 271 { 272 throw new NoSuchElementException( "No tuple present" ); 273 } 274 275 ParentPos<K, V> parentPos = stack[depth]; 276 277 if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) ) 278 { 279 // This is the end : no more value 280 throw new NoSuchElementException( "No more tuples present" ); 281 } 282 283 if ( parentPos.pos == parentPos.page.getNbElems() ) 284 { 285 // End of the leaf. We have to go back into the stack up to the 286 // parent, and down to the leaf 287 parentPos = findNextParentPos(); 288 289 // we also need to check for the type of page cause 290 // findNextParentPos will never return a null ParentPos 291 if ( ( parentPos == null ) || ( parentPos.page == null ) ) 292 { 293 // This is the end : no more value 294 throw new NoSuchElementException( "No more tuples present" ); 295 } 296 } 297 298 V value = null; 299 300 if ( parentPos.valueCursor.hasNext() ) 301 { 302 // Deal with the BeforeFirst case 303 if ( parentPos.pos == BEFORE_FIRST ) 304 { 305 parentPos.pos++; 306 } 307 308 value = parentPos.valueCursor.next(); 309 } 310 else 311 { 312 if ( parentPos.pos == parentPos.page.getNbElems() - 1 ) 313 { 314 parentPos = findNextParentPos(); 315 316 if ( ( parentPos == null ) || ( parentPos.page == null ) ) 317 { 318 // This is the end : no more value 319 throw new NoSuchElementException( "No more tuples present" ); 320 } 321 } 322 else 323 { 324 parentPos.pos++; 325 } 326 327 try 328 { 329 ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) parentPos.page ).getValue( parentPos.pos ); 330 331 parentPos.valueCursor = valueHolder.getCursor(); 332 333 value = parentPos.valueCursor.next(); 334 } 335 catch ( IllegalArgumentException e ) 336 { 337 e.printStackTrace(); 338 } 339 } 340 341 AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page ); 342 Tuple<K, V> tuple = new Tuple<K, V>( leaf.getKey( parentPos.pos ), value ); 343 344 return tuple; 345 } 346 347 348 /** 349 * Get the next non-duplicate key. 350 * If the BTree contains : 351 * 352 * <ul> 353 * <li><1,0></li> 354 * <li><1,1></li> 355 * <li><1,2></li> 356 * <li><2,0></li> 357 * <li><2,1></li> 358 * </ul> 359 * 360 * and cursor is present at <1,1> then the returned tuple will be <2,0> (not <1,2>) 361 * 362 * @return A Tuple containing the found key and value 363 * @throws EndOfFileExceededException 364 * @throws IOException 365 */ 366 public Tuple<K, V> nextKey() throws EndOfFileExceededException, IOException 367 { 368 // First check that we have elements in the BTree 369 if ( ( stack == null ) || ( stack.length == 0 ) ) 370 { 371 // This is the end : no more value 372 throw new NoSuchElementException( "No more tuples present" ); 373 } 374 375 ParentPos<K, V> parentPos = stack[depth]; 376 377 if ( parentPos.page == null ) 378 { 379 // This is the end : no more value 380 throw new NoSuchElementException( "No more tuples present" ); 381 } 382 383 if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) ) 384 { 385 // End of the leaf. We have to go back into the stack up to the 386 // parent, and down to the next leaf 387 ParentPos<K, V> newParentPos = findNextParentPos(); 388 389 // we also need to check the result of the call to 390 // findNextParentPos as it will return a null ParentPos 391 if ( ( newParentPos == null ) || ( newParentPos.page == null ) ) 392 { 393 // This is the end : no more value 394 AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page ); 395 ValueHolder<V> valueHolder = leaf.getValue( parentPos.pos ); 396 parentPos.pos = AFTER_LAST; 397 parentPos.valueCursor = valueHolder.getCursor(); 398 parentPos.valueCursor.afterLast(); 399 400 return null; 401 } 402 else 403 { 404 parentPos = newParentPos; 405 } 406 } 407 else 408 { 409 // Get the next key 410 parentPos.pos++; 411 } 412 413 // The key 414 AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page ); 415 Tuple<K, V> tuple = new Tuple<K, V>(); 416 tuple.setKey( leaf.getKey( parentPos.pos ) ); 417 418 // The value 419 ValueHolder<V> valueHolder = leaf.getValue( parentPos.pos ); 420 parentPos.valueCursor = valueHolder.getCursor(); 421 V value = parentPos.valueCursor.next(); 422 tuple.setValue( value ); 423 424 return tuple; 425 } 426 427 428 /** 429 * Tells if the cursor can return a next key 430 * 431 * @return true if there are some more keys 432 * @throws IOException 433 * @throws EndOfFileExceededException 434 */ 435 public boolean hasNextKey() throws EndOfFileExceededException, IOException 436 { 437 // First check that we have elements in the BTree 438 if ( ( stack == null ) || ( stack.length == 0 ) ) 439 { 440 // This is the end : no more key 441 return false; 442 } 443 444 ParentPos<K, V> parentPos = stack[depth]; 445 446 if ( parentPos.page == null ) 447 { 448 // This is the end : no more key 449 return false; 450 } 451 452 if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) ) 453 { 454 // End of the leaf. We have to go back into the stack up to the 455 // parent, and down to the next leaf 456 return hasNextParentPos(); 457 } 458 else 459 { 460 return true; 461 } 462 } 463 464 465 /** 466 * Tells if the cursor can return a previous element 467 * 468 * @return true if there are some more elements 469 * @throws IOException 470 * @throws EndOfFileExceededException 471 */ 472 public boolean hasPrev() throws EndOfFileExceededException, IOException 473 { 474 // First check that we have elements in the BTree 475 if ( ( stack == null ) || ( stack.length == 0 ) ) 476 { 477 return false; 478 } 479 480 // Take the leaf and check if we have no mare values 481 ParentPos<K, V> parentPos = stack[depth]; 482 483 if ( parentPos.page == null ) 484 { 485 // Empty BTree, get out 486 return false; 487 } 488 489 if ( parentPos.pos > 0 ) 490 { 491 // get out, we have values on the left 492 return true; 493 } 494 else 495 { 496 // Check that we are not before the first value 497 if ( parentPos.pos == BEFORE_FIRST ) 498 { 499 return false; 500 } 501 502 // Check if we have some more value 503 if ( parentPos.valueCursor.hasPrev() ) 504 { 505 return true; 506 } 507 508 // Ok, here, we have reached the first value in the leaf. We have to go up and 509 // see if we have some remaining values 510 int currentDepth = depth - 1; 511 512 while ( currentDepth >= 0 ) 513 { 514 parentPos = stack[currentDepth]; 515 516 if ( parentPos.pos > 0 ) 517 { 518 // The parent has some remaining values on the right, get out 519 return true; 520 } 521 else 522 { 523 currentDepth--; 524 } 525 } 526 527 return false; 528 } 529 } 530 531 532 /** 533 * Find the previous key/value 534 * 535 * @return A Tuple containing the found key and value 536 * @throws IOException 537 * @throws EndOfFileExceededException 538 */ 539 public Tuple<K, V> prev() throws EndOfFileExceededException, IOException 540 { 541 // First check that we have elements in the BTree 542 if ( ( stack == null ) || ( stack.length == 0 ) ) 543 { 544 throw new NoSuchElementException( "No more tuple present" ); 545 } 546 547 ParentPos<K, V> parentPos = stack[depth]; 548 549 if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) ) 550 { 551 // This is the end : no more value 552 throw new NoSuchElementException( "No more tuples present" ); 553 } 554 555 if ( ( parentPos.pos == 0 ) && ( !parentPos.valueCursor.hasPrev() ) ) 556 { 557 // End of the leaf. We have to go back into the stack up to the 558 // parent, and down to the leaf 559 parentPos = findPrevParentPos(); 560 561 // we also need to check for the type of page cause 562 // findPrevParentPos will never return a null ParentPos 563 if ( ( parentPos == null ) || ( parentPos.page == null ) ) 564 { 565 // This is the end : no more value 566 throw new NoSuchElementException( "No more tuples present" ); 567 } 568 } 569 570 V value = null; 571 572 if ( parentPos.valueCursor.hasPrev() ) 573 { 574 // Deal with the AfterLast case 575 if ( parentPos.pos == AFTER_LAST ) 576 { 577 parentPos.pos = parentPos.page.getNbElems() - 1; 578 } 579 580 value = parentPos.valueCursor.prev(); 581 } 582 else 583 { 584 if ( parentPos.pos == 0 ) 585 { 586 parentPos = findPrevParentPos(); 587 588 if ( ( parentPos == null ) || ( parentPos.page == null ) ) 589 { 590 // This is the end : no more value 591 throw new NoSuchElementException( "No more tuples present" ); 592 } 593 } 594 else 595 { 596 parentPos.pos--; 597 598 try 599 { 600 ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) parentPos.page ).getValue( parentPos.pos ); 601 602 parentPos.valueCursor = valueHolder.getCursor(); 603 parentPos.valueCursor.afterLast(); 604 605 value = parentPos.valueCursor.prev(); 606 } 607 catch ( IllegalArgumentException e ) 608 { 609 e.printStackTrace(); 610 } 611 } 612 } 613 614 AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page ); 615 Tuple<K, V> tuple = new Tuple<K, V>( leaf.getKey( parentPos.pos ), value ); 616 617 return tuple; 618 } 619 620 621 /** 622 * Get the previous non-duplicate key. 623 * If the BTree contains : 624 * 625 * <ul> 626 * <li><1,0></li> 627 * <li><1,1></li> 628 * <li><1,2></li> 629 * <li><2,0></li> 630 * <li><2,1></li> 631 * </ul> 632 * 633 * and cursor is present at <2,1> then the returned tuple will be <1,0> (not <2,0>) 634 * 635 * @return A Tuple containing the found key and value 636 * @throws EndOfFileExceededException 637 * @throws IOException 638 */ 639 public Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException 640 { 641 // First check that we have elements in the BTree 642 if ( ( stack == null ) || ( stack.length == 0 ) ) 643 { 644 // This is the end : no more value 645 throw new NoSuchElementException( "No more tuples present" ); 646 } 647 648 ParentPos<K, V> parentPos = stack[depth]; 649 650 if ( parentPos.page == null ) 651 { 652 // This is the end : no more value 653 throw new NoSuchElementException( "No more tuples present" ); 654 } 655 656 if ( parentPos.pos == 0 ) 657 { 658 // Beginning of the leaf. We have to go back into the stack up to the 659 // parent, and down to the leaf 660 parentPos = findPrevParentPos(); 661 662 if ( ( parentPos == null ) || ( parentPos.page == null ) ) 663 { 664 // This is the end : no more value 665 throw new NoSuchElementException( "No more tuples present" ); 666 } 667 } 668 else 669 { 670 if ( parentPos.pos == AFTER_LAST ) 671 { 672 parentPos.pos = parentPos.page.getNbElems() - 1; 673 } 674 else 675 { 676 parentPos.pos--; 677 } 678 } 679 680 // Update the Tuple 681 AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page ); 682 683 // The key 684 Tuple<K, V> tuple = new Tuple<K, V>(); 685 tuple.setKey( leaf.getKey( parentPos.pos ) ); 686 687 // The value 688 ValueHolder<V> valueHolder = leaf.getValue( parentPos.pos ); 689 parentPos.valueCursor = valueHolder.getCursor(); 690 V value = parentPos.valueCursor.next(); 691 tuple.setValue( value ); 692 693 return tuple; 694 } 695 696 697 /** 698 * Tells if the cursor can return a previous key 699 * 700 * @return true if there are some more keys 701 * @throws IOException 702 * @throws EndOfFileExceededException 703 */ 704 public boolean hasPrevKey() throws EndOfFileExceededException, IOException 705 { 706 // First check that we have elements in the BTree 707 if ( ( stack == null ) || ( stack.length == 0 ) ) 708 { 709 // This is the end : no more key 710 return false; 711 } 712 713 ParentPos<K, V> parentPos = stack[depth]; 714 715 if ( parentPos.page == null ) 716 { 717 // This is the end : no more key 718 return false; 719 } 720 721 switch ( parentPos.pos ) 722 { 723 case 0: 724 // Beginning of the leaf. We have to go back into the stack up to the 725 // parent, and down to the leaf 726 return hasPrevParentPos(); 727 728 case -1: 729 // no previous key 730 return false; 731 732 default: 733 // we have a previous key 734 return true; 735 } 736 } 737 738 739 /** 740 * Tells if there is a next ParentPos 741 * 742 * @return the new ParentPos instance, or null if we have no following leaf 743 * @throws IOException 744 * @throws EndOfFileExceededException 745 */ 746 private boolean hasNextParentPos() throws EndOfFileExceededException, IOException 747 { 748 if ( depth == 0 ) 749 { 750 // No need to go any further, there is only one leaf in the btree 751 return false; 752 } 753 754 int currentDepth = depth - 1; 755 Page<K, V> child = null; 756 757 // First, go up the tree until we find a Node which has some element on the right 758 while ( currentDepth >= 0 ) 759 { 760 // We first go up the tree, until we reach a page whose current position 761 // is not the last one 762 ParentPos<K, V> parentPos = stack[currentDepth]; 763 764 if ( parentPos.pos + 1 > parentPos.page.getNbElems() ) 765 { 766 // No more element on the right : go up 767 currentDepth--; 768 } 769 else 770 { 771 // We can pick the next element at this level 772 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos + 1 ); 773 774 // and go down the tree through the nodes 775 while ( currentDepth < depth - 1 ) 776 { 777 currentDepth++; 778 child = ( ( AbstractPage<K, V> ) child ).getPage( 0 ); 779 } 780 781 return true; 782 } 783 } 784 785 return false; 786 } 787 788 789 /** 790 * Find the leaf containing the following elements. 791 * 792 * @return the new ParentPos instance, or null if we have no following leaf 793 * @throws IOException 794 * @throws EndOfFileExceededException 795 */ 796 private ParentPos<K, V> findNextParentPos() throws EndOfFileExceededException, IOException 797 { 798 if ( depth == 0 ) 799 { 800 // No need to go any further, there is only one leaf in the btree 801 return null; 802 } 803 804 int currentDepth = depth - 1; 805 Page<K, V> child = null; 806 807 // First, go up the tree until we find a Node which has some element on the right 808 while ( currentDepth >= 0 ) 809 { 810 // We first go up the tree, until we reach a page whose current position 811 // is not the last one 812 ParentPos<K, V> parentPos = stack[currentDepth]; 813 814 if ( parentPos.pos + 1 > parentPos.page.getNbElems() ) 815 { 816 // No more element on the right : go up 817 currentDepth--; 818 } 819 else 820 { 821 // We can pick the next element at this level 822 parentPos.pos++; 823 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos ); 824 825 // and go down the tree through the nodes 826 while ( currentDepth < depth - 1 ) 827 { 828 currentDepth++; 829 parentPos = stack[currentDepth]; 830 parentPos.pos = 0; 831 parentPos.page = child; 832 child = ( ( AbstractPage<K, V> ) child ).getPage( 0 ); 833 } 834 835 // and the leaf 836 parentPos = stack[depth]; 837 parentPos.page = child; 838 parentPos.pos = 0; 839 parentPos.valueCursor = ( ( AbstractPage<K, V> ) child ).getValue( 0 ).getCursor(); 840 841 return parentPos; 842 } 843 } 844 845 return null; 846 } 847 848 849 /** 850 * Find the leaf containing the previous elements. 851 * 852 * @return the new ParentPos instance, or null if we have no previous leaf 853 * @throws IOException 854 * @throws EndOfFileExceededException 855 */ 856 private ParentPos<K, V> findPrevParentPos() throws EndOfFileExceededException, IOException 857 { 858 if ( depth == 0 ) 859 { 860 // No need to go any further, there is only one leaf in the btree 861 return null; 862 } 863 864 int currentDepth = depth - 1; 865 Page<K, V> child = null; 866 867 // First, go up the tree until we find a Node which has some element on the left 868 while ( currentDepth >= 0 ) 869 { 870 // We first go up the tree, until we reach a page whose current position 871 // is not the last one 872 ParentPos<K, V> parentPos = stack[currentDepth]; 873 874 if ( parentPos.pos == 0 ) 875 { 876 // No more element on the right : go up 877 currentDepth--; 878 } 879 else 880 { 881 // We can pick the next element at this level 882 parentPos.pos--; 883 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos ); 884 885 // and go down the tree through the nodes 886 while ( currentDepth < depth - 1 ) 887 { 888 currentDepth++; 889 parentPos = stack[currentDepth]; 890 parentPos.pos = child.getNbElems(); 891 parentPos.page = child; 892 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.page.getNbElems() ); 893 } 894 895 // and the leaf 896 parentPos = stack[depth]; 897 parentPos.pos = child.getNbElems() - 1; 898 parentPos.page = child; 899 ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) parentPos.page ).getValue( parentPos.pos ); 900 parentPos.valueCursor = valueHolder.getCursor(); 901 parentPos.valueCursor.afterLast(); 902 903 return parentPos; 904 } 905 } 906 907 return null; 908 } 909 910 911 /** 912 * Tells if there is a prev ParentPos 913 * 914 * @return the new ParentPos instance, or null if we have no previous leaf 915 * @throws IOException 916 * @throws EndOfFileExceededException 917 */ 918 private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException 919 { 920 if ( depth == 0 ) 921 { 922 // No need to go any further, there is only one leaf in the btree 923 return false; 924 } 925 926 int currentDepth = depth - 1; 927 Page<K, V> child = null; 928 929 // First, go up the tree until we find a Node which has some element on the right 930 while ( currentDepth >= 0 ) 931 { 932 // We first go up the tree, until we reach a page whose current position 933 // is not the last one 934 ParentPos<K, V> parentPos = stack[currentDepth]; 935 936 if ( parentPos.pos == 0 ) 937 { 938 // No more element on the left : go up 939 currentDepth--; 940 } 941 else 942 { 943 // We can pick the previous element at this level 944 child = ( ( AbstractPage<K, V> ) parentPos.page ).getPage( parentPos.pos - 1 ); 945 946 // and go down the tree through the nodes 947 while ( currentDepth < depth - 1 ) 948 { 949 currentDepth++; 950 child = ( ( AbstractPage<K, V> ) child ).getPage( child.getNbElems() ); 951 } 952 953 return true; 954 } 955 } 956 957 return false; 958 } 959 960 961 /** 962 * {@inheritDoc} 963 */ 964 public void close() 965 { 966 transaction.close(); 967 } 968 969 970 /** 971 * Get the creation date 972 * @return The creation date for this cursor 973 */ 974 public long getCreationDate() 975 { 976 return transaction.getCreationDate(); 977 } 978 979 980 /** 981 * Get the current revision 982 * 983 * @return The revision this cursor is based on 984 */ 985 public long getRevision() 986 { 987 return transaction.getRevision(); 988 } 989 990 991 public String toString() 992 { 993 StringBuilder sb = new StringBuilder(); 994 995 sb.append( "TupleCursor, depth = " ).append( depth ).append( "\n" ); 996 997 for ( int i = 0; i <= depth; i++ ) 998 { 999 sb.append( " " ).append( stack[i] ).append( "\n" ); 1000 } 1001 1002 return sb.toString(); 1003 } 1004}