1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *  http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.directory.server.core.partition.impl.btree.jdbm;
20  
21  
22  import org.slf4j.Logger;
23  import org.slf4j.LoggerFactory;
24  import org.apache.directory.server.xdbm.Table;
25  import org.apache.directory.server.xdbm.Tuple;
26  import org.apache.directory.server.core.cursor.Cursor;
27  import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
28  import org.apache.directory.server.schema.SerializableComparator;
29  import org.junit.Before;
30  import org.junit.After;
31  import org.junit.Test;
32  
33  import static org.junit.Assert.*;
34  
35  import java.io.File;
36  
37  import jdbm.RecordManager;
38  import jdbm.helper.IntegerSerializer;
39  import jdbm.recman.BaseRecordManager;
40  
41  
42  /**
43   * Tests the Cursor functionality of a JdbmTable when duplicate keys are 
44   * supported.
45   *
46   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
47   * @version $Rev$, $Date$
48   */
49  public class DupsCursorTest
50  {
51      private static final Logger LOG = LoggerFactory.getLogger( DupsCursorTest.class.getSimpleName() );
52      private static final String TEST_OUTPUT_PATH = "test.output.path";
53      private static final int SIZE = 15;
54  
55      transient Table<Integer,Integer> table;
56      transient File dbFile;
57      transient RecordManager recman;
58  
59  
60      @Before
61      public void createTable() throws Exception
62      {
63          File tmpDir = null;
64          if ( System.getProperty( TEST_OUTPUT_PATH, null ) != null )
65          {
66              tmpDir = new File( System.getProperty( TEST_OUTPUT_PATH ) );
67          }
68  
69          dbFile = File.createTempFile( getClass().getSimpleName(), "db", tmpDir );
70          recman = new BaseRecordManager( dbFile.getAbsolutePath() );
71  
72          // gosh this is a terrible use of a global static variable
73          SerializableComparator.setRegistry( new MockComparatorRegistry() );
74  
75          table = new JdbmTable<Integer,Integer>( "test", SIZE, recman,
76                  new SerializableComparator<Integer>( "" ),
77                  new SerializableComparator<Integer>( "" ),
78                  null, new IntegerSerializer() );
79          LOG.debug( "Created new table and populated it with data" );
80      }
81  
82  
83      @After
84      public void destryTable() throws Exception
85      {
86          table.close();
87          table = null;
88          recman.close();
89          recman = null;
90          dbFile.deleteOnExit();
91          // Remove temporary files
92          String fileToDelete = dbFile.getAbsolutePath();
93          new File( fileToDelete ).delete();
94          new File( fileToDelete + ".db" ).delete();
95          new File( fileToDelete + ".lg" ).delete();
96          
97          dbFile = null;
98      }
99  
100 
101     @Test
102     public void testEmptyTableOperations() throws Exception
103     {
104         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
105         assertFalse( cursor.next() );
106         
107         cursor.afterLast();
108         assertFalse( cursor.previous() );
109 
110         cursor.beforeFirst();
111         assertFalse( cursor.next() );
112 
113         assertFalse( cursor.first() );
114         assertFalse( cursor.last() );
115     }
116 
117 
118     @Test
119     public void testNextNoDups() throws Exception
120     {
121         // first try without duplicates at all
122         for ( int ii = 0; ii < SIZE-1; ii++ )
123         {
124             table.put( ii, ii );
125         }
126         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
127 
128         int ii = 0;
129         while ( cursor.next() )
130         {
131             Tuple<Integer,Integer> tuple = cursor.get();
132             assertEquals( ii, ( int ) tuple.getKey() );
133             assertEquals( ii, ( int ) tuple.getValue() );
134             ii++;
135         }
136     }
137 
138 
139     @Test
140     public void testPreviousNoDups() throws Exception
141     {
142         for ( int ii = 0; ii < SIZE-1; ii++ )
143         {
144             table.put( ii, ii );
145         }
146         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
147 
148         int ii = SIZE-2;
149         while ( cursor.previous() )
150         {
151             Tuple<Integer,Integer> tuple = cursor.get();
152             assertEquals( ii, ( int ) tuple.getKey() );
153             assertEquals( ii, ( int ) tuple.getValue() );
154             ii--;
155         }
156     }
157 
158 
159     @Test
160     public void testNextDups() throws Exception
161     {
162         for ( int ii = 0; ii < SIZE*3; ii++ )
163         {
164             if ( ii > 12 && ii < 17 + SIZE )
165             {
166                 table.put( 13, ii );
167             }
168             else
169             {
170                 table.put( ii, ii );
171             }
172         }
173         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
174 
175         int ii = 0;
176         while ( cursor.next() )
177         {
178             Tuple<Integer,Integer> tuple = cursor.get();
179             if ( ii > 12 && ii < 17 + SIZE )
180             {
181                 assertEquals( 13, ( int ) tuple.getKey() );
182                 assertEquals( ii, ( int ) tuple.getValue() );
183             }
184             else
185             {
186                 assertEquals( ii, ( int ) tuple.getKey() );
187                 assertEquals( ii, ( int ) tuple.getValue() );
188             }
189             ii++;
190         }
191     }
192 
193 
194     @Test
195     public void testPreviousDups() throws Exception
196     {
197         for ( int ii = 0; ii < SIZE*3; ii++ )
198         {
199             if ( ii > 12 && ii < 17 + SIZE )
200             {
201                 table.put( 13, ii );
202             }
203             else
204             {
205                 table.put( ii, ii );
206             }
207         }
208         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
209         cursor.afterLast();
210 
211         int ii = SIZE*3 - 1;
212         while ( cursor.previous() )
213         {
214             Tuple<Integer,Integer> tuple = cursor.get();
215             if ( ii > 12 && ii < 17 + SIZE )
216             {
217                 assertEquals( 13, ( int ) tuple.getKey() );
218                 assertEquals( ii, ( int ) tuple.getValue() );
219             }
220             else
221             {
222                 assertEquals( ii, ( int ) tuple.getKey() );
223                 assertEquals( ii, ( int ) tuple.getValue() );
224             }
225             ii--;
226         }
227     }
228 
229 
230     @Test
231     public void testFirstLastUnderDupLimit() throws Exception
232     {
233         for ( int ii = 0; ii < SIZE*2 - 1; ii++ )
234         {
235             if ( ii > 12 && ii < 17 )
236             {
237                 table.put( 13, ii );
238             }
239             else
240             {
241                 table.put( ii, ii );
242             }
243         }
244         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
245 
246         int ii = 0;
247         while ( cursor.next() )
248         {
249             Tuple<Integer,Integer> tuple = cursor.get();
250             if ( ii > 12 && ii < 17 )
251             {
252                 assertEquals( 13, ( int ) tuple.getKey() );
253                 assertEquals( ii, ( int ) tuple.getValue() );
254             }
255             else
256             {
257                 assertEquals( ii, ( int ) tuple.getKey() );
258                 assertEquals( ii, ( int ) tuple.getValue() );
259             }
260             ii++;
261         }
262 
263         cursor.first();
264         ii = 0;
265         do
266         {
267             Tuple<Integer,Integer> tuple = cursor.get();
268             if ( ii > 12 && ii < 17 )
269             {
270                 assertEquals( 13, ( int ) tuple.getKey() );
271                 assertEquals( ii, ( int ) tuple.getValue() );
272             }
273             else
274             {
275                 assertEquals( ii, ( int ) tuple.getKey() );
276                 assertEquals( ii, ( int ) tuple.getValue() );
277             }
278             ii++;
279         }
280         while ( cursor.next() );
281 
282         // now go backwards
283         cursor.afterLast();
284         ii = SIZE*2-2;
285         while ( cursor.previous() )
286         {
287             Tuple<Integer,Integer> tuple = cursor.get();
288             if ( ii > 12 && ii < 17 )
289             {
290                 assertEquals( 13, ( int ) tuple.getKey() );
291                 assertEquals( ii, ( int ) tuple.getValue() );
292             }
293             else
294             {
295                 assertEquals( ii, ( int ) tuple.getKey() );
296                 assertEquals( ii, ( int ) tuple.getValue() );
297             }
298             ii--;
299         }
300 
301         // now advance to last and go backwards again
302         cursor.last();
303         ii = SIZE*2-2;
304         do
305         {
306             Tuple<Integer,Integer> tuple = cursor.get();
307             if ( ii > 12 && ii < 17 )
308             {
309                 assertEquals( 13, ( int ) tuple.getKey() );
310                 assertEquals( ii, ( int ) tuple.getValue() );
311             }
312             else
313             {
314                 assertEquals( ii, ( int ) tuple.getKey() );
315                 assertEquals( ii, ( int ) tuple.getValue() );
316             }
317             ii--;
318         }
319         while ( cursor.previous() );
320 
321         // advance to first then last and go backwards again
322         cursor.beforeFirst();
323         cursor.afterLast();
324         ii = SIZE*2-2;
325         while ( cursor.previous() )
326         {
327             Tuple<Integer,Integer> tuple = cursor.get();
328             if ( ii > 12 && ii < 17 )
329             {
330                 assertEquals( 13, ( int ) tuple.getKey() );
331                 assertEquals( ii, ( int ) tuple.getValue() );
332             }
333             else
334             {
335                 assertEquals( ii, ( int ) tuple.getKey() );
336                 assertEquals( ii, ( int ) tuple.getValue() );
337             }
338             ii--;
339         }
340     }
341 
342 
343     @Test
344     public void testFirstLastOverDupLimit() throws Exception
345     {
346         for ( int ii = 0; ii < SIZE*3-1; ii++ )
347         {
348             if ( ii < 2 + SIZE ) // keys with multiple values
349             {
350                 table.put( 0, ii );
351             }
352             else // keys with single values
353             {
354                 table.put( ii, ii );
355             }
356         }
357         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
358 
359         int ii = 0;
360         while ( cursor.next() )
361         {
362             Tuple<Integer,Integer> tuple = cursor.get();
363             if ( ii < 2 + SIZE )
364             {
365                 assertEquals( 0, ( int ) tuple.getKey() );
366                 assertEquals( ii, ( int ) tuple.getValue() );
367             }
368             else
369             {
370                 assertEquals( ii, ( int ) tuple.getKey() );
371                 assertEquals( ii, ( int ) tuple.getValue() );
372             }
373             ii++;
374         }
375 
376         // now go back to first and traverse all over again
377         cursor.first();
378         ii = 0;
379         do
380         {
381             Tuple<Integer,Integer> tuple = cursor.get();
382             if ( ii < 2 + SIZE )
383             {
384                 assertEquals( 0, ( int ) tuple.getKey() );
385                 assertEquals( ii, ( int ) tuple.getValue() );
386             }
387             else
388             {
389                 assertEquals( ii, ( int ) tuple.getKey() );
390                 assertEquals( ii, ( int ) tuple.getValue() );
391             }
392             ii++;
393         }
394         while ( cursor.next() );
395 
396         // now go backwards
397         cursor.afterLast();
398         ii = SIZE*3-2;
399         while ( cursor.previous() )
400         {
401             Tuple<Integer,Integer> tuple = cursor.get();
402 
403             if ( ii < 2 + SIZE )
404             {
405                 assertEquals( 0, ( int ) tuple.getKey() );
406                 assertEquals( ii, ( int ) tuple.getValue() );
407             }
408             else
409             {
410                 assertEquals( ii, ( int ) tuple.getKey() );
411                 assertEquals( ii, ( int ) tuple.getValue() );
412             }
413             ii--;
414         }
415 
416         // now advance to last and go backwards again
417         cursor.last();
418         ii = SIZE*3-2;
419         do
420         {
421             Tuple<Integer,Integer> tuple = cursor.get();
422             if ( ii < 2 + SIZE )
423             {
424                 assertEquals( 0, ( int ) tuple.getKey() );
425                 assertEquals( ii, ( int ) tuple.getValue() );
426             }
427             else
428             {
429                 assertEquals( ii, ( int ) tuple.getKey() );
430                 assertEquals( ii, ( int ) tuple.getValue() );
431             }
432             ii--;
433         }
434         while ( cursor.previous() );
435 
436         // advance to first then last and go backwards again
437         cursor.beforeFirst();
438         cursor.afterLast();
439         ii = SIZE*3-2;
440         while ( cursor.previous() )
441         {
442             Tuple<Integer,Integer> tuple = cursor.get();
443             if ( ii < 2 + SIZE )
444             {
445                 assertEquals( 0, ( int ) tuple.getKey() );
446                 assertEquals( ii, ( int ) tuple.getValue() );
447             }
448             else
449             {
450                 assertEquals( ii, ( int ) tuple.getKey() );
451                 assertEquals( ii, ( int ) tuple.getValue() );
452             }
453             ii--;
454         }
455     }
456 
457 
458     @Test
459     public void testFirstOverDupLimit() throws Exception
460     {
461         for ( int ii = 0; ii < SIZE*3-1; ii++ )
462         {
463             if ( ii < 2 + SIZE ) // keys with multiple values
464             {
465                 table.put( 0, ii );
466             }
467             else // keys with single values
468             {
469                 table.put( ii, ii );
470             }
471         }
472         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
473 
474         int ii = 0;
475         while ( cursor.next() )
476         {
477             Tuple<Integer,Integer> tuple = cursor.get();
478             if ( ii < 2 + SIZE )
479             {
480                 assertEquals( 0, ( int ) tuple.getKey() );
481                 assertEquals( ii, ( int ) tuple.getValue() );
482             }
483             else
484             {
485                 assertEquals( ii, ( int ) tuple.getKey() );
486                 assertEquals( ii, ( int ) tuple.getValue() );
487             }
488             ii++;
489         }
490 
491         // now go back to first and traverse all over again
492         cursor.first();
493         ii = 0;
494         do
495         {
496             Tuple<Integer,Integer> tuple = cursor.get();
497             if ( ii < 2 + SIZE )
498             {
499                 assertEquals( 0, ( int ) tuple.getKey() );
500                 assertEquals( ii, ( int ) tuple.getValue() );
501             }
502             else
503             {
504                 assertEquals( ii, ( int ) tuple.getKey() );
505                 assertEquals( ii, ( int ) tuple.getValue() );
506             }
507             ii++;
508         }
509         while ( cursor.next() );
510 
511         // now go backwards
512         cursor.afterLast();
513         ii = SIZE*3-2;
514         while ( cursor.previous() )
515         {
516             Tuple<Integer,Integer> tuple = cursor.get();
517 
518             if ( ii < 2 + SIZE )
519             {
520                 assertEquals( 0, ( int ) tuple.getKey() );
521                 assertEquals( ii, ( int ) tuple.getValue() );
522             }
523             else
524             {
525                 assertEquals( ii, ( int ) tuple.getKey() );
526                 assertEquals( ii, ( int ) tuple.getValue() );
527             }
528             ii--;
529         }
530 
531         // now advance to last and go backwards again
532         cursor.last();
533         ii = SIZE*3-2;
534         do
535         {
536             Tuple<Integer,Integer> tuple = cursor.get();
537             if ( ii < 2 + SIZE )
538             {
539                 assertEquals( 0, ( int ) tuple.getKey() );
540                 assertEquals( ii, ( int ) tuple.getValue() );
541             }
542             else
543             {
544                 assertEquals( ii, ( int ) tuple.getKey() );
545                 assertEquals( ii, ( int ) tuple.getValue() );
546             }
547             ii--;
548         }
549         while ( cursor.previous() );
550 
551         // advance to first then last and go backwards again
552         cursor.beforeFirst();
553         cursor.afterLast();
554         ii = SIZE*3-2;
555         while ( cursor.previous() )
556         {
557             Tuple<Integer,Integer> tuple = cursor.get();
558             if ( ii < 2 + SIZE )
559             {
560                 assertEquals( 0, ( int ) tuple.getKey() );
561                 assertEquals( ii, ( int ) tuple.getValue() );
562             }
563             else
564             {
565                 assertEquals( ii, ( int ) tuple.getKey() );
566                 assertEquals( ii, ( int ) tuple.getValue() );
567             }
568             ii--;
569         }
570     }
571 
572 
573 
574 
575     @Test
576     public void testLastOverDupLimit() throws Exception
577     {
578         for ( int ii = 0; ii < SIZE*3-1; ii++ )
579         {
580             if ( ii > 2 + SIZE ) // keys with multiple values
581             {
582                 table.put( 3 + SIZE, ii );
583             }
584             else // keys with single values
585             {
586                 table.put( ii, ii );
587             }
588         }
589         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
590 
591         int ii = 0;
592         while ( cursor.next() )
593         {
594             Tuple<Integer,Integer> tuple = cursor.get();
595             if ( ii > 2 + SIZE )
596             {
597                 assertEquals( 3 + SIZE, ( int ) tuple.getKey() );
598                 assertEquals( ii, ( int ) tuple.getValue() );
599             }
600             else
601             {
602                 assertEquals( ii, ( int ) tuple.getKey() );
603                 assertEquals( ii, ( int ) tuple.getValue() );
604             }
605             ii++;
606         }
607 
608         // now go back to first and traverse all over again
609         cursor.first();
610         ii = 0;
611         do
612         {
613             Tuple<Integer,Integer> tuple = cursor.get();
614             if ( ii > 2 + SIZE )
615             {
616                 assertEquals( 3 + SIZE, ( int ) tuple.getKey() );
617                 assertEquals( ii, ( int ) tuple.getValue() );
618             }
619             else
620             {
621                 assertEquals( ii, ( int ) tuple.getKey() );
622                 assertEquals( ii, ( int ) tuple.getValue() );
623             }
624             ii++;
625         }
626         while ( cursor.next() );
627 
628         // now go backwards
629         cursor.afterLast();
630         ii = SIZE*3-2;
631         while ( cursor.previous() )
632         {
633             Tuple<Integer,Integer> tuple = cursor.get();
634 
635             if ( ii > 2 + SIZE )
636             {
637                 assertEquals( 3 + SIZE, ( int ) tuple.getKey() );
638                 assertEquals( ii, ( int ) tuple.getValue() );
639             }
640             else
641             {
642                 assertEquals( ii, ( int ) tuple.getKey() );
643                 assertEquals( ii, ( int ) tuple.getValue() );
644             }
645             ii--;
646         }
647 
648         // now advance to last and go backwards again
649         cursor.last();
650         ii = SIZE*3-2;
651         do
652         {
653             Tuple<Integer,Integer> tuple = cursor.get();
654             if ( ii > 2 + SIZE )
655             {
656                 assertEquals( 3 + SIZE, ( int ) tuple.getKey() );
657                 assertEquals( ii, ( int ) tuple.getValue() );
658             }
659             else
660             {
661                 assertEquals( ii, ( int ) tuple.getKey() );
662                 assertEquals( ii, ( int ) tuple.getValue() );
663             }
664             ii--;
665         }
666         while ( cursor.previous() );
667 
668         // advance to first then last and go backwards again
669         cursor.beforeFirst();
670         cursor.afterLast();
671         ii = SIZE*3-2;
672         while ( cursor.previous() )
673         {
674             Tuple<Integer,Integer> tuple = cursor.get();
675             if ( ii > 2 + SIZE )
676             {
677                 assertEquals( 3 + SIZE, ( int ) tuple.getKey() );
678                 assertEquals( ii, ( int ) tuple.getValue() );
679             }
680             else
681             {
682                 assertEquals( ii, ( int ) tuple.getKey() );
683                 assertEquals( ii, ( int ) tuple.getValue() );
684             }
685             ii--;
686         }
687     }
688 
689 
690     @Test
691     public void testOnEmptyTable() throws Exception
692     {
693         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
694         assertNotNull( cursor );
695         assertFalse( cursor.isClosed() );
696         
697         cursor.before( new Tuple<Integer, Integer>( 1, 2 ) );
698         assertFalse( cursor.available() );
699     }
700 
701     
702     @Test
703     public void testOverDupLimit() throws Exception
704     {
705         table.put( 5, 5 );
706         table.put( 6, 6 );
707         for ( int ii = 0; ii < 20; ii++ )
708         {
709             table.put( 7, ii );
710         }
711         table.put( 8, 8 );
712         table.put( 9, 9 );
713         
714         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
715         assertNotNull( cursor );
716         assertFalse( cursor.isClosed() );
717         
718         cursor.before( new Tuple<Integer, Integer>( 7, 2 ) );
719         assertFalse( cursor.available() );
720     }
721 
722     
723     @Test
724     public void testUnderDupLimit() throws Exception
725     {
726         table.put( 5, 5 );
727         table.put( 6, 6 );
728         for ( int ii = 0; ii < 10; ii++ )
729         {
730             table.put( 7, ii );
731         }
732         table.put( 8, 8 );
733         table.put( 9, 9 );
734         
735         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
736         assertNotNull( cursor );
737         assertFalse( cursor.isClosed() );
738         
739         cursor.before( new Tuple<Integer, Integer>( 7, 2 ) );
740         assertFalse( cursor.available() );
741     }
742 
743 
744     @Test
745     public void testBeforeAfterBelowDupLimit() throws Exception
746     {
747         for ( int ii = 0; ii < SIZE*2 - 1; ii++ )
748         {
749             if ( ii > 12 && ii < 17 ) // keys with multiple values
750             {
751                 table.put( 13, ii );
752             }
753             else if ( ii > 17 && ii < 21 ) // adds hole with no keys for ii
754             {
755             }
756             else // keys with single values
757             {
758                 table.put( ii, ii );
759             }
760         }
761 
762         // test before to advance just before a key with a single value
763         int ii = 5;
764         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
765         cursor.before( new Tuple<Integer,Integer>( 5, 5 ) );
766         while ( cursor.next() )
767         {
768             if ( ii > 17 && ii < 21 )
769             {
770                 assertFalse( table.has( ii ) );
771                 continue;
772             }
773 
774             Tuple<Integer,Integer> tuple = cursor.get();
775             if ( ii > 12 && ii < 17 )
776             {
777                 assertEquals( 13, ( int ) tuple.getKey() );
778                 assertEquals( ii, ( int ) tuple.getValue() );
779             }
780             else
781             {
782                 assertEquals( ii, ( int ) tuple.getKey() );
783                 assertEquals( ii, ( int ) tuple.getValue() );
784             }
785             ii++;
786         }
787 
788         // test before to advance just before a key with a single value but
789         // with a null tuple value which should not advance the dupsCursor
790         ii = 5;
791         cursor = table.cursor();
792         cursor.before( new Tuple<Integer,Integer>( 5, null ) );
793         while ( cursor.next() )
794         {
795             if ( ii > 17 && ii < 21 )
796             {
797                 assertFalse( table.has( ii ) );
798                 continue;
799             }
800 
801             Tuple<Integer,Integer> tuple = cursor.get();
802             if ( ii > 12 && ii < 17 )
803             {
804                 assertEquals( 13, ( int ) tuple.getKey() );
805                 assertEquals( ii, ( int ) tuple.getValue() );
806             }
807             else
808             {
809                 assertEquals( ii, ( int ) tuple.getKey() );
810                 assertEquals( ii, ( int ) tuple.getValue() );
811             }
812             ii++;
813         }
814 
815         // test before to advance just before a key value pair where the key
816         // does not exist - using value so we hit check for key equality
817         ii = 21;
818         cursor = table.cursor();
819         cursor.before( new Tuple<Integer,Integer>( 18, 18 ) );
820         while ( cursor.next() )
821         {
822             if ( ii > 17 && ii < 21 )
823             {
824                 assertFalse( table.has( ii ) );
825                 continue;
826             }
827 
828             Tuple<Integer,Integer> tuple = cursor.get();
829             if ( ii > 12 && ii < 17 )
830             {
831                 assertEquals( 13, ( int ) tuple.getKey() );
832                 assertEquals( ii, ( int ) tuple.getValue() );
833             }
834             else
835             {
836                 assertEquals( ii, ( int ) tuple.getKey() );
837                 assertEquals( ii, ( int ) tuple.getValue() );
838             }
839             ii++;
840         }
841 
842         // test after to advance just after the end
843         cursor = table.cursor();
844         cursor.after( new Tuple<Integer,Integer>( 111, null ) );
845         assertFalse( cursor.next() );
846 
847         // test after to advance just before a key with a single value
848         ii = 6;
849         cursor = table.cursor();
850         cursor.after( new Tuple<Integer,Integer>( 5, null ) );
851         while ( cursor.next() )
852         {
853             if ( ii > 17 && ii < 21 )
854             {
855                 assertFalse( table.has( ii ) );
856                 continue;
857             }
858 
859             Tuple<Integer,Integer> tuple = cursor.get();
860             if ( ii > 12 && ii < 17 )
861             {
862                 assertEquals( 13, ( int ) tuple.getKey() );
863                 assertEquals( ii, ( int ) tuple.getValue() );
864             }
865             else
866             {
867                 assertEquals( ii, ( int ) tuple.getKey() );
868                 assertEquals( ii, ( int ) tuple.getValue() );
869             }
870             ii++;
871         }
872 
873         // test before to advance just before a key & value with multiple
874         // values for the key - we should advance just before the value
875         cursor = table.cursor();
876         cursor.before( new Tuple<Integer,Integer>( 13, 14 ) );
877 
878         cursor.next();
879         Tuple<Integer,Integer> tuple = cursor.get();
880         assertEquals( 13, ( int ) tuple.getKey() );
881         assertEquals( 14, ( int ) tuple.getValue() );
882         ii = 15;
883 
884         while ( cursor.next() )
885         {
886             if ( ii > 17 && ii < 21 )
887             {
888                 assertFalse( table.has( ii ) );
889                 continue;
890             }
891 
892             tuple = cursor.get();
893             if ( ii > 12 && ii < 17 )
894             {
895                 assertEquals( 13, ( int ) tuple.getKey() );
896                 assertEquals( ii, ( int ) tuple.getValue() );
897             }
898             else
899             {
900                 assertEquals( ii, ( int ) tuple.getKey() );
901                 assertEquals( ii, ( int ) tuple.getValue() );
902             }
903             ii++;
904         }
905 
906         // test after to advance just before a key & value with multiple
907         // values for the key - we should advance just before the value
908         cursor = table.cursor();
909         cursor.after( new Tuple<Integer,Integer>( 13, 14 ) );
910 
911         cursor.next();
912         tuple = cursor.get();
913         assertEquals( 13, ( int ) tuple.getKey() );
914         assertEquals( 15, ( int ) tuple.getValue() );
915         ii=16;
916 
917         while ( cursor.next() )
918         {
919             if ( ii > 17 && ii < 21 )
920             {
921                 assertFalse( table.has( ii ) );
922                 continue;
923             }
924 
925             tuple = cursor.get();
926             if ( ii > 12 && ii < 17 )
927             {
928                 assertEquals( 13, ( int ) tuple.getKey() );
929                 assertEquals( ii, ( int ) tuple.getValue() );
930             }
931             else
932             {
933                 assertEquals( ii, ( int ) tuple.getKey() );
934                 assertEquals( ii, ( int ) tuple.getValue() );
935             }
936             ii++;
937         }
938 
939         // test after to advance just before a key that does not exist
940         cursor = table.cursor();
941         cursor.after( new Tuple<Integer,Integer>( 18, null ) );
942 
943         cursor.next();
944         tuple = cursor.get();
945         assertEquals( 21, ( int ) tuple.getKey() );
946         assertEquals( 21, ( int ) tuple.getValue() );
947         ii=22;
948 
949         while ( cursor.next() )
950         {
951             if ( ii > 17 && ii < 21 )
952             {
953                 assertFalse( table.has( ii ) );
954                 continue;
955             }
956 
957             tuple = cursor.get();
958             if ( ii > 12 && ii < 17 )
959             {
960                 assertEquals( 13, ( int ) tuple.getKey() );
961                 assertEquals( ii, ( int ) tuple.getValue() );
962             }
963             else
964             {
965                 assertEquals( ii, ( int ) tuple.getKey() );
966                 assertEquals( ii, ( int ) tuple.getValue() );
967             }
968             ii++;
969         }
970 
971         // test after to advance just before a key and value where the key
972         // does not exist - used to force key comparison in after()
973         cursor = table.cursor();
974         cursor.after( new Tuple<Integer,Integer>( 18, 18 ) );
975 
976         cursor.next();
977         tuple = cursor.get();
978         assertEquals( 21, ( int ) tuple.getKey() );
979         assertEquals( 21, ( int ) tuple.getValue() );
980         ii=22;
981 
982         while ( cursor.next() )
983         {
984             if ( ii > 17 && ii < 21 )
985             {
986                 assertFalse( table.has( ii ) );
987                 continue;
988             }
989 
990             tuple = cursor.get();
991             if ( ii > 12 && ii < 17 )
992             {
993                 assertEquals( 13, ( int ) tuple.getKey() );
994                 assertEquals( ii, ( int ) tuple.getValue() );
995             }
996             else
997             {
998                 assertEquals( ii, ( int ) tuple.getKey() );
999                 assertEquals( ii, ( int ) tuple.getValue() );
1000             }
1001             ii++;
1002         }
1003     }
1004 
1005 
1006     @Test
1007     public void testBeforeAfterOverDupLimit() throws Exception
1008     {
1009         for ( int ii = 0; ii < SIZE*3 - 1; ii++ )
1010         {
1011             if ( ii > 12 && ii < 17 + SIZE ) // keys with multiple values
1012             {
1013                 table.put( 13, ii );
1014             }
1015             else if ( ii > 17 + SIZE  && ii < 21 + SIZE ) // adds hole with no keys for ii
1016             {
1017             }
1018             else // keys with single values
1019             {
1020                 table.put( ii, ii );
1021             }
1022         }
1023 
1024         // test before to advance just before a key with a single value
1025         int ii = 5;
1026         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
1027         cursor.before( new Tuple<Integer,Integer>( 5, 5 ) );
1028         while ( cursor.next() )
1029         {
1030             if ( ii > 17 + SIZE && ii < 21 + SIZE )
1031             {
1032                 assertFalse( table.has( ii ) );
1033                 continue;
1034             }
1035 
1036             Tuple<Integer,Integer> tuple = cursor.get();
1037             if ( ii > 12 && ii < 17 + SIZE )
1038             {
1039                 assertEquals( 13, ( int ) tuple.getKey() );
1040                 assertEquals( ii, ( int ) tuple.getValue() );
1041             }
1042             else
1043             {
1044                 assertEquals( ii, ( int ) tuple.getKey() );
1045                 assertEquals( ii, ( int ) tuple.getValue() );
1046             }
1047             ii++;
1048         }
1049 
1050         // test before to advance just before a key with a single value but
1051         // with a null tuple value which should not advance the dupsCursor
1052         ii = 5;
1053         cursor = table.cursor();
1054         cursor.before( new Tuple<Integer,Integer>( 5, null ) );
1055         while ( cursor.next() )
1056         {
1057             if ( ii > 17 + SIZE && ii < 21 + SIZE )
1058             {
1059                 assertFalse( table.has( ii ) );
1060                 continue;
1061             }
1062 
1063             Tuple<Integer,Integer> tuple = cursor.get();
1064             if ( ii > 12 && ii < 17 + SIZE )
1065             {
1066                 assertEquals( 13, ( int ) tuple.getKey() );
1067                 assertEquals( ii, ( int ) tuple.getValue() );
1068             }
1069             else
1070             {
1071                 assertEquals( ii, ( int ) tuple.getKey() );
1072                 assertEquals( ii, ( int ) tuple.getValue() );
1073             }
1074             ii++;
1075         }
1076 
1077         // test before to advance just before a key value pair where the key
1078         // does not exist - using value so we hit check for key equality
1079         ii = 21 + SIZE;
1080         cursor = table.cursor();
1081         cursor.before( new Tuple<Integer,Integer>( 18 + SIZE, 18 + SIZE ) );
1082         while ( cursor.next() )
1083         {
1084             if ( ii > 17 + SIZE && ii < 21 + SIZE )
1085             {
1086                 assertFalse( table.has( ii ) );
1087                 continue;
1088             }
1089 
1090             Tuple<Integer,Integer> tuple = cursor.get();
1091             if ( ii > 12 && ii < 17 + SIZE )
1092             {
1093                 assertEquals( 13, ( int ) tuple.getKey() );
1094                 assertEquals( ii, ( int ) tuple.getValue() );
1095             }
1096             else
1097             {
1098                 assertEquals( ii, ( int ) tuple.getKey() );
1099                 assertEquals( ii, ( int ) tuple.getValue() );
1100             }
1101             ii++;
1102         }
1103 
1104         // test after to advance just after the end
1105         cursor = table.cursor();
1106         cursor.after( new Tuple<Integer,Integer>( 111, null ) );
1107         assertFalse( cursor.next() );
1108 
1109         // test after to advance just before a key with a single value
1110         ii = 6;
1111         cursor = table.cursor();
1112         cursor.after( new Tuple<Integer,Integer>( 5, null ) );
1113         while ( cursor.next() )
1114         {
1115             if ( ii > 17 + SIZE && ii < 21 + SIZE )
1116             {
1117                 assertFalse( table.has( ii ) );
1118                 continue;
1119             }
1120 
1121             Tuple<Integer,Integer> tuple = cursor.get();
1122             if ( ii > 12 && ii < 17 + SIZE )
1123             {
1124                 assertEquals( 13, ( int ) tuple.getKey() );
1125                 assertEquals( ii, ( int ) tuple.getValue() );
1126             }
1127             else
1128             {
1129                 assertEquals( ii, ( int ) tuple.getKey() );
1130                 assertEquals( ii, ( int ) tuple.getValue() );
1131             }
1132             ii++;
1133         }
1134 
1135         // test before to advance just before a key & value with multiple
1136         // values for the key - we should advance just before the value
1137         cursor = table.cursor();
1138         cursor.before( new Tuple<Integer,Integer>( 13, 14 ) );
1139 
1140         cursor.next();
1141         Tuple<Integer,Integer> tuple = cursor.get();
1142         assertEquals( 13, ( int ) tuple.getKey() );
1143         assertEquals( 14, ( int ) tuple.getValue() );
1144         ii = 15;
1145 
1146         while ( cursor.next() )
1147         {
1148             if ( ii > 17 + SIZE && ii < 21 + SIZE )
1149             {
1150                 assertFalse( table.has( ii ) );
1151                 continue;
1152             }
1153 
1154             tuple = cursor.get();
1155             if ( ii > 12 && ii < 17 + SIZE )
1156             {
1157                 assertEquals( 13, ( int ) tuple.getKey() );
1158                 assertEquals( ii, ( int ) tuple.getValue() );
1159             }
1160             else
1161             {
1162                 assertEquals( ii, ( int ) tuple.getKey() );
1163                 assertEquals( ii, ( int ) tuple.getValue() );
1164             }
1165             ii++;
1166         }
1167 
1168         // test after to advance just before a key & value with multiple
1169         // values for the key - we should advance just before the value
1170         cursor = table.cursor();
1171         cursor.after( new Tuple<Integer,Integer>( 13, 14 ) );
1172 
1173         cursor.next();
1174         tuple = cursor.get();
1175         assertEquals( 13, ( int ) tuple.getKey() );
1176         assertEquals( 15, ( int ) tuple.getValue() );
1177         ii=16;
1178 
1179         while ( cursor.next() )
1180         {
1181             if ( ii > 17 + SIZE && ii < 21 + SIZE )
1182             {
1183                 assertFalse( table.has( ii ) );
1184                 continue;
1185             }
1186 
1187             tuple = cursor.get();
1188             if ( ii > 12 && ii < 17 + SIZE )
1189             {
1190                 assertEquals( 13, ( int ) tuple.getKey() );
1191                 assertEquals( ii, ( int ) tuple.getValue() );
1192             }
1193             else
1194             {
1195                 assertEquals( ii, ( int ) tuple.getKey() );
1196                 assertEquals( ii, ( int ) tuple.getValue() );
1197             }
1198             ii++;
1199         }
1200 
1201         // test after to advance just before a key that does not exist
1202         cursor = table.cursor();
1203         cursor.after( new Tuple<Integer,Integer>( 18 + SIZE, null ) );
1204 
1205         cursor.next();
1206         tuple = cursor.get();
1207         assertEquals( 21 + SIZE, ( int ) tuple.getKey() );
1208         assertEquals( 21 + SIZE, ( int ) tuple.getValue() );
1209         ii=22 + SIZE;
1210 
1211         while ( cursor.next() )
1212         {
1213             if ( ii > 17 + SIZE && ii < 21 + SIZE )
1214             {
1215                 assertFalse( table.has( ii ) );
1216                 continue;
1217             }
1218 
1219             tuple = cursor.get();
1220             if ( ii > 12 && ii < 17 + SIZE )
1221             {
1222                 assertEquals( 13, ( int ) tuple.getKey() );
1223                 assertEquals( ii, ( int ) tuple.getValue() );
1224             }
1225             else
1226             {
1227                 assertEquals( ii, ( int ) tuple.getKey() );
1228                 assertEquals( ii, ( int ) tuple.getValue() );
1229             }
1230             ii++;
1231         }
1232 
1233         // test after to advance just before a key and value where the key
1234         // does not exist - used to force key comparison in after()
1235         cursor = table.cursor();
1236         cursor.after( new Tuple<Integer,Integer>( 18 + SIZE , 18 + SIZE ) );
1237 
1238         cursor.next();
1239         tuple = cursor.get();
1240         assertEquals( 21 + SIZE, ( int ) tuple.getKey() );
1241         assertEquals( 21 + SIZE, ( int ) tuple.getValue() );
1242         ii=22+ SIZE;
1243 
1244         while ( cursor.next() )
1245         {
1246             if ( ii > 17 + SIZE && ii < 21 + SIZE )
1247             {
1248                 assertFalse( table.has( ii ) );
1249                 continue;
1250             }
1251 
1252             tuple = cursor.get();
1253             if ( ii > 12 && ii < 17 + SIZE )
1254             {
1255                 assertEquals( 13, ( int ) tuple.getKey() );
1256                 assertEquals( ii, ( int ) tuple.getValue() );
1257             }
1258             else
1259             {
1260                 assertEquals( ii, ( int ) tuple.getKey() );
1261                 assertEquals( ii, ( int ) tuple.getValue() );
1262             }
1263             ii++;
1264         }
1265     }
1266 
1267 
1268     @Test
1269     public void testMiscellaneous() throws Exception
1270     {
1271         Cursor<Tuple<Integer,Integer>> cursor = table.cursor();
1272         assertNotNull( cursor );
1273         assertTrue( cursor.isElementReused() );
1274 
1275         try
1276         {
1277             cursor.get();
1278             fail( "Should never get here due to invalid cursor position exception." );
1279         }
1280         catch( InvalidCursorPositionException e )
1281         {
1282         }
1283     }
1284 }