1/*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 2002,2008 Oracle.  All rights reserved.
5 *
6 * $Id: IndexTest.java,v 1.1 2008/02/07 17:12:32 mark Exp $
7 */
8
9package com.sleepycat.persist.test;
10
11import static com.sleepycat.persist.model.Relationship.MANY_TO_MANY;
12import static com.sleepycat.persist.model.Relationship.MANY_TO_ONE;
13import static com.sleepycat.persist.model.Relationship.ONE_TO_MANY;
14import static com.sleepycat.persist.model.Relationship.ONE_TO_ONE;
15
16import java.util.ArrayList;
17import java.util.Collection;
18import java.util.Collections;
19import java.util.Iterator;
20import java.util.List;
21import java.util.Set;
22import java.util.SortedMap;
23import java.util.SortedSet;
24import java.util.TreeMap;
25import java.util.TreeSet;
26
27import junit.framework.Test;
28
29import com.sleepycat.collections.MapEntryParameter;
30import com.sleepycat.db.DatabaseException;
31import com.sleepycat.db.Transaction;
32import com.sleepycat.persist.EntityCursor;
33import com.sleepycat.persist.EntityIndex;
34import com.sleepycat.persist.EntityStore;
35import com.sleepycat.persist.PrimaryIndex;
36import com.sleepycat.persist.SecondaryIndex;
37import com.sleepycat.persist.StoreConfig;
38import com.sleepycat.persist.model.Entity;
39import com.sleepycat.persist.model.PrimaryKey;
40import com.sleepycat.persist.model.SecondaryKey;
41import com.sleepycat.persist.raw.RawObject;
42import com.sleepycat.persist.raw.RawStore;
43import com.sleepycat.persist.raw.RawType;
44import com.sleepycat.util.test.TxnTestCase;
45
46/**
47 * Tests EntityIndex and EntityCursor in all their permutations.
48 *
49 * @author Mark Hayes
50 */
51public class IndexTest extends TxnTestCase {
52
53    private static final int N_RECORDS = 5;
54    private static final int THREE_TO_ONE = 3;
55
56    public static Test suite() {
57        return txnTestSuite(IndexTest.class, null,
58                            null);
59                            //new String[] { TxnTestCase.TXN_NULL});
60    }
61
62    private EntityStore store;
63    private PrimaryIndex<Integer,MyEntity> primary;
64    private SecondaryIndex<Integer,Integer,MyEntity> oneToOne;
65    private SecondaryIndex<Integer,Integer,MyEntity> manyToOne;
66    private SecondaryIndex<Integer,Integer,MyEntity> oneToMany;
67    private SecondaryIndex<Integer,Integer,MyEntity> manyToMany;
68    private RawStore rawStore;
69    private RawType entityType;
70    private PrimaryIndex<Object,RawObject> primaryRaw;
71    private SecondaryIndex<Object,Object,RawObject> oneToOneRaw;
72    private SecondaryIndex<Object,Object,RawObject> manyToOneRaw;
73    private SecondaryIndex<Object,Object,RawObject> oneToManyRaw;
74    private SecondaryIndex<Object,Object,RawObject> manyToManyRaw;
75
76    /**
77     * Opens the store.
78     */
79    private void open()
80        throws DatabaseException {
81
82        StoreConfig config = new StoreConfig();
83        config.setAllowCreate(envConfig.getAllowCreate());
84        config.setTransactional(envConfig.getTransactional());
85
86        store = new EntityStore(env, "test", config);
87
88        primary = store.getPrimaryIndex(Integer.class, MyEntity.class);
89        oneToOne =
90            store.getSecondaryIndex(primary, Integer.class, "oneToOne");
91        manyToOne =
92            store.getSecondaryIndex(primary, Integer.class, "manyToOne");
93        oneToMany =
94            store.getSecondaryIndex(primary, Integer.class, "oneToMany");
95        manyToMany =
96            store.getSecondaryIndex(primary, Integer.class, "manyToMany");
97
98        assertNotNull(primary);
99        assertNotNull(oneToOne);
100        assertNotNull(manyToOne);
101        assertNotNull(oneToMany);
102        assertNotNull(manyToMany);
103
104        rawStore = new RawStore(env, "test", config);
105        String clsName = MyEntity.class.getName();
106        entityType = rawStore.getModel().getRawType(clsName);
107        assertNotNull(entityType);
108
109        primaryRaw = rawStore.getPrimaryIndex(clsName);
110        oneToOneRaw = rawStore.getSecondaryIndex(clsName, "oneToOne");
111        manyToOneRaw = rawStore.getSecondaryIndex(clsName, "manyToOne");
112        oneToManyRaw = rawStore.getSecondaryIndex(clsName, "oneToMany");
113        manyToManyRaw = rawStore.getSecondaryIndex(clsName, "manyToMany");
114
115        assertNotNull(primaryRaw);
116        assertNotNull(oneToOneRaw);
117        assertNotNull(manyToOneRaw);
118        assertNotNull(oneToManyRaw);
119        assertNotNull(manyToManyRaw);
120    }
121
122    /**
123     * Closes the store.
124     */
125    private void close()
126        throws DatabaseException {
127
128        store.close();
129        store = null;
130        rawStore.close();
131        rawStore = null;
132    }
133
134    /**
135     * The store must be closed before closing the environment.
136     */
137    public void tearDown()
138        throws Exception {
139
140        try {
141            if (rawStore != null) {
142                rawStore.close();
143            }
144        } catch (Throwable e) {
145            System.out.println("During tearDown: " + e);
146        }
147        try {
148            if (store != null) {
149                store.close();
150            }
151        } catch (Throwable e) {
152            System.out.println("During tearDown: " + e);
153        }
154        store = null;
155        rawStore = null;
156        super.tearDown();
157    }
158
159    /**
160     * Primary keys: {0, 1, 2, 3, 4}
161     */
162    public void testPrimary()
163        throws DatabaseException {
164
165        SortedMap<Integer,SortedSet<Integer>> expected =
166            new TreeMap<Integer,SortedSet<Integer>>();
167
168        for (int priKey = 0; priKey < N_RECORDS; priKey += 1) {
169            SortedSet<Integer> values = new TreeSet<Integer>();
170            values.add(priKey);
171            expected.put(priKey, values);
172        }
173
174        open();
175        addEntities(primary);
176        checkIndex(primary, expected, keyGetter, entityGetter);
177        checkIndex(primaryRaw, expected, rawKeyGetter, rawEntityGetter);
178
179        /* Close and reopen, then recheck indices. */
180        close();
181        open();
182        checkIndex(primary, expected, keyGetter, entityGetter);
183        checkIndex(primaryRaw, expected, rawKeyGetter, rawEntityGetter);
184
185        /* Check primary delete, last key first for variety. */
186        for (int priKey = N_RECORDS - 1; priKey >= 0; priKey -= 1) {
187            boolean useRaw = ((priKey & 1) != 0);
188            Transaction txn = txnBegin();
189            if (useRaw) {
190                primaryRaw.delete(txn, priKey);
191            } else {
192                primary.delete(txn, priKey);
193            }
194            txnCommit(txn);
195            expected.remove(priKey);
196            checkIndex(primary, expected, keyGetter, entityGetter);
197        }
198        checkAllEmpty();
199
200        /* Check PrimaryIndex put operations. */
201        MyEntity e;
202        Transaction txn = txnBegin();
203        /* put() */
204        e = primary.put(txn, new MyEntity(1));
205        assertNull(e);
206        e = primary.get(txn, 1, null);
207        assertEquals(1, e.key);
208        /* putNoReturn() */
209        primary.putNoReturn(txn, new MyEntity(2));
210        e = primary.get(txn, 2, null);
211        assertEquals(2, e.key);
212        /* putNoOverwrite */
213        assertTrue(!primary.putNoOverwrite(txn, new MyEntity(1)));
214        assertTrue(!primary.putNoOverwrite(txn, new MyEntity(2)));
215        assertTrue(primary.putNoOverwrite(txn, new MyEntity(3)));
216        e = primary.get(txn, 3, null);
217        assertEquals(3, e.key);
218        txnCommit(txn);
219        close();
220    }
221
222    /**
223     * { 0:0, 1:-1, 2:-2, 3:-3, 4:-4 }
224     */
225    public void testOneToOne()
226        throws DatabaseException {
227
228        SortedMap<Integer,SortedSet<Integer>> expected =
229            new TreeMap<Integer,SortedSet<Integer>>();
230
231        for (int priKey = 0; priKey < N_RECORDS; priKey += 1) {
232            SortedSet<Integer> values = new TreeSet<Integer>();
233            values.add(priKey);
234            Integer secKey = (-priKey);
235            expected.put(secKey, values);
236        }
237
238        open();
239        addEntities(primary);
240        checkSecondary(oneToOne, oneToOneRaw, expected);
241        checkDelete(oneToOne, oneToOneRaw, expected);
242        close();
243    }
244
245    /**
246     * { 0:0, 1:1, 2:2, 3:0, 4:1 }
247     */
248    public void testManyToOne()
249        throws DatabaseException {
250
251        SortedMap<Integer,SortedSet<Integer>> expected =
252            new TreeMap<Integer,SortedSet<Integer>>();
253
254        for (int priKey = 0; priKey < N_RECORDS; priKey += 1) {
255            Integer secKey = priKey % THREE_TO_ONE;
256            SortedSet<Integer> values = expected.get(secKey);
257            if (values == null) {
258                values = new TreeSet<Integer>();
259                expected.put(secKey, values);
260            }
261            values.add(priKey);
262        }
263
264        open();
265        addEntities(primary);
266        checkSecondary(manyToOne, manyToOneRaw, expected);
267        checkDelete(manyToOne, manyToOneRaw, expected);
268        close();
269    }
270
271    /**
272     * { 0:{}, 1:{10}, 2:{20,21}, 3:{30,31,32}, 4:{40,41,42,43}
273     */
274    public void testOneToMany()
275        throws DatabaseException {
276
277        SortedMap<Integer,SortedSet<Integer>> expected =
278            new TreeMap<Integer,SortedSet<Integer>>();
279
280        for (int priKey = 0; priKey < N_RECORDS; priKey += 1) {
281            for (int i = 0; i < priKey; i += 1) {
282                Integer secKey = (N_RECORDS * priKey) + i;
283                SortedSet<Integer> values = expected.get(secKey);
284                if (values == null) {
285                    values = new TreeSet<Integer>();
286                    expected.put(secKey, values);
287                }
288                values.add(priKey);
289            }
290        }
291
292        open();
293        addEntities(primary);
294        checkSecondary(oneToMany, oneToManyRaw, expected);
295        checkDelete(oneToMany, oneToManyRaw, expected);
296        close();
297    }
298
299    /**
300     * { 0:{}, 1:{0}, 2:{0,1}, 3:{0,1,2}, 4:{0,1,2,3}
301     */
302    public void testManyToMany()
303        throws DatabaseException {
304
305        SortedMap<Integer,SortedSet<Integer>> expected =
306            new TreeMap<Integer,SortedSet<Integer>>();
307
308        for (int priKey = 0; priKey < N_RECORDS; priKey += 1) {
309            for (int i = 0; i < priKey; i += 1) {
310                Integer secKey = i;
311                SortedSet<Integer> values = expected.get(secKey);
312                if (values == null) {
313                    values = new TreeSet<Integer>();
314                    expected.put(secKey, values);
315                }
316                values.add(priKey);
317            }
318        }
319
320        open();
321        addEntities(primary);
322        checkSecondary(manyToMany, manyToManyRaw, expected);
323        checkDelete(manyToMany, manyToManyRaw, expected);
324        close();
325    }
326
327    private void addEntities(PrimaryIndex<Integer,MyEntity> primary)
328        throws DatabaseException {
329
330        Transaction txn = txnBegin();
331        for (int priKey = 0; priKey < N_RECORDS; priKey += 1) {
332            MyEntity prev = primary.put(txn, new MyEntity(priKey));
333            assertNull(prev);
334        }
335        txnCommit(txn);
336    }
337
338    private void checkDelete(SecondaryIndex<Integer,Integer,MyEntity> index,
339                             SecondaryIndex<Object,Object,RawObject> indexRaw,
340                             SortedMap<Integer,SortedSet<Integer>> expected)
341        throws DatabaseException {
342
343        SortedMap<Integer,SortedSet<Integer>> expectedSubIndex =
344            new TreeMap<Integer,SortedSet<Integer>>();
345
346        while (expected.size() > 0) {
347            Integer delSecKey = expected.firstKey();
348            SortedSet<Integer> deletedPriKeys = expected.remove(delSecKey);
349            for (SortedSet<Integer> priKeys : expected.values()) {
350                priKeys.removeAll(deletedPriKeys);
351            }
352            Transaction txn = txnBegin();
353            boolean deleted = index.delete(txn, delSecKey);
354            assertEquals(deleted, !deletedPriKeys.isEmpty());
355            deleted = index.delete(txn, delSecKey);
356            assertTrue(!deleted);
357            assertNull(index.get(txn, delSecKey, null));
358            txnCommit(txn);
359            checkSecondary(index, indexRaw, expected);
360        }
361
362        /*
363         * Delete remaining records so that the primary index is empty.  Use
364         * the RawStore for variety.
365         */
366        Transaction txn = txnBegin();
367        for (int priKey = 0; priKey < N_RECORDS; priKey += 1) {
368            primaryRaw.delete(txn, priKey);
369        }
370        txnCommit(txn);
371        checkAllEmpty();
372    }
373
374    private void checkSecondary(SecondaryIndex<Integer,Integer,MyEntity> index,
375                                SecondaryIndex<Object,Object,RawObject>
376                                indexRaw,
377                                SortedMap<Integer,SortedSet<Integer>> expected)
378        throws DatabaseException {
379
380        checkIndex(index, expected, keyGetter, entityGetter);
381        checkIndex(index.keysIndex(), expected, keyGetter, keyGetter);
382
383        checkIndex(indexRaw, expected, rawKeyGetter, rawEntityGetter);
384        checkIndex(indexRaw.keysIndex(), expected, rawKeyGetter, rawKeyGetter);
385
386        SortedMap<Integer,SortedSet<Integer>> expectedSubIndex =
387            new TreeMap<Integer,SortedSet<Integer>>();
388
389        for (Integer secKey : expected.keySet()) {
390            expectedSubIndex.clear();
391            for (Integer priKey : expected.get(secKey)) {
392                SortedSet<Integer> values = new TreeSet<Integer>();
393                values.add(priKey);
394                expectedSubIndex.put(priKey, values);
395            }
396            checkIndex(index.subIndex(secKey),
397                       expectedSubIndex,
398                       keyGetter,
399                       entityGetter);
400            checkIndex(indexRaw.subIndex(secKey),
401                       expectedSubIndex,
402                       rawKeyGetter,
403                       rawEntityGetter);
404        }
405    }
406
407    private <K,V> void checkIndex(EntityIndex<K,V> index,
408                                  SortedMap<Integer,SortedSet<Integer>>
409                                  expected,
410                                  Getter<K> kGetter,
411                                  Getter<V> vGetter)
412        throws DatabaseException {
413
414        SortedMap<K,V> map = index.sortedMap();
415
416        Transaction txn = txnBegin();
417        for (int i : expected.keySet()) {
418            K k = kGetter.fromInt(i);
419            SortedSet<Integer> dups = expected.get(i);
420            if (dups.isEmpty()) {
421
422                /* EntityIndex */
423                V v = index.get(txn, k, null);
424                assertNull(v);
425                assertTrue(!index.contains(txn, k, null));
426
427                /* Map/Collection */
428                v = map.get(i);
429                assertNull(v);
430                assertTrue(!map.containsKey(i));
431            } else {
432                int j = dups.first();
433
434                /* EntityIndex */
435                V v = index.get(txn, k, null);
436                assertNotNull(v);
437                assertEquals(j, vGetter.getKey(v));
438                assertTrue(index.contains(txn, k, null));
439
440                /* Map/Collection */
441                v = map.get(i);
442                assertNotNull(v);
443                assertEquals(j, vGetter.getKey(v));
444                assertTrue(map.containsKey(i));
445                assertTrue("" + i + ' ' + j + ' ' + v + ' ' + map,
446                           map.containsValue(v));
447                assertTrue(map.keySet().contains(i));
448                assertTrue(map.values().contains(v));
449                assertTrue
450                    (map.entrySet().contains(new MapEntryParameter(i, v)));
451            }
452        }
453        txnCommit(txn);
454
455        int keysSize = expandKeySize(expected);
456        int valuesSize = expandValueSize(expected);
457
458        /* EntityIndex.count */
459        assertEquals("keysSize=" + keysSize, (long) valuesSize, index.count());
460
461        /* Map/Collection size */
462        assertEquals(valuesSize, map.size());
463        assertEquals(valuesSize, map.values().size());
464        assertEquals(valuesSize, map.entrySet().size());
465        assertEquals(keysSize, map.keySet().size());
466
467        /* Map/Collection isEmpty */
468        assertEquals(valuesSize == 0, map.isEmpty());
469        assertEquals(valuesSize == 0, map.values().isEmpty());
470        assertEquals(valuesSize == 0, map.entrySet().isEmpty());
471        assertEquals(keysSize == 0, map.keySet().isEmpty());
472
473        txn = txnBeginCursor();
474
475        /* Unconstrained cursors. */
476        checkCursor
477            (index.keys(txn, null),
478             map.keySet(), true,
479             expandKeys(expected), kGetter);
480        checkCursor
481            (index.entities(txn, null),
482             map.values(), false,
483             expandValues(expected), vGetter);
484
485        /* Range cursors. */
486        if (expected.isEmpty()) {
487            checkOpenRanges(txn, 0, index, expected, kGetter, vGetter);
488            checkClosedRanges(txn, 0, 1, index, expected, kGetter, vGetter);
489        } else {
490            int firstKey = expected.firstKey();
491            int lastKey = expected.lastKey();
492            for (int i = firstKey - 1; i <= lastKey + 1; i += 1) {
493                checkOpenRanges(txn, i, index, expected, kGetter, vGetter);
494                int j = i + 1;
495                if (j < lastKey + 1) {
496                    checkClosedRanges
497                        (txn, i, j, index, expected, kGetter, vGetter);
498                }
499            }
500        }
501
502        txnCommit(txn);
503    }
504
505    private <K,V> void checkOpenRanges(Transaction txn, int i,
506                                       EntityIndex<K,V> index,
507                                       SortedMap<Integer,SortedSet<Integer>>
508                                       expected,
509                                       Getter<K> kGetter,
510                                       Getter<V> vGetter)
511        throws DatabaseException {
512
513        SortedMap<K,V> map = index.sortedMap();
514        SortedMap<Integer,SortedSet<Integer>> rangeExpected;
515        K k = kGetter.fromInt(i);
516        K kPlusOne = kGetter.fromInt(i + 1);
517
518        /* Head range exclusive. */
519        rangeExpected = expected.headMap(i);
520        checkCursor
521            (index.keys(txn, null, false, k, false, null),
522             map.headMap(k).keySet(), true,
523             expandKeys(rangeExpected), kGetter);
524        checkCursor
525            (index.entities(txn, null, false, k, false, null),
526             map.headMap(k).values(), false,
527             expandValues(rangeExpected), vGetter);
528
529        /* Head range inclusive. */
530        rangeExpected = expected.headMap(i + 1);
531        checkCursor
532            (index.keys(txn, null, false, k, true, null),
533             map.headMap(kPlusOne).keySet(), true,
534             expandKeys(rangeExpected), kGetter);
535        checkCursor
536            (index.entities(txn, null, false, k, true, null),
537             map.headMap(kPlusOne).values(), false,
538             expandValues(rangeExpected), vGetter);
539
540        /* Tail range exclusive. */
541        rangeExpected = expected.tailMap(i + 1);
542        checkCursor
543            (index.keys(txn, k, false, null, false, null),
544             map.tailMap(kPlusOne).keySet(), true,
545             expandKeys(rangeExpected), kGetter);
546        checkCursor
547            (index.entities(txn, k, false, null, false, null),
548             map.tailMap(kPlusOne).values(), false,
549             expandValues(rangeExpected), vGetter);
550
551        /* Tail range inclusive. */
552        rangeExpected = expected.tailMap(i);
553        checkCursor
554            (index.keys(txn, k, true, null, false, null),
555             map.tailMap(k).keySet(), true,
556             expandKeys(rangeExpected), kGetter);
557        checkCursor
558            (index.entities(txn, k, true, null, false, null),
559             map.tailMap(k).values(), false,
560             expandValues(rangeExpected), vGetter);
561    }
562
563    private <K,V> void checkClosedRanges(Transaction txn, int i, int j,
564                                         EntityIndex<K,V> index,
565                                         SortedMap<Integer,SortedSet<Integer>>
566                                         expected,
567                                         Getter<K> kGetter,
568                                         Getter<V> vGetter)
569        throws DatabaseException {
570
571        SortedMap<K,V> map = index.sortedMap();
572        SortedMap<Integer,SortedSet<Integer>> rangeExpected;
573        K k = kGetter.fromInt(i);
574        K kPlusOne = kGetter.fromInt(i + 1);
575        K l = kGetter.fromInt(j);
576        K lPlusOne = kGetter.fromInt(j + 1);
577
578        /* Sub range exclusive. */
579        rangeExpected = expected.subMap(i + 1, j);
580        checkCursor
581            (index.keys(txn, k, false, l, false, null),
582             map.subMap(kPlusOne, l).keySet(), true,
583             expandKeys(rangeExpected), kGetter);
584        checkCursor
585            (index.entities(txn, k, false, l, false, null),
586             map.subMap(kPlusOne, l).values(), false,
587             expandValues(rangeExpected), vGetter);
588
589        /* Sub range inclusive. */
590        rangeExpected = expected.subMap(i, j + 1);
591        checkCursor
592            (index.keys(txn, k, true, l, true, null),
593             map.subMap(k, lPlusOne).keySet(), true,
594             expandKeys(rangeExpected), kGetter);
595        checkCursor
596            (index.entities(txn, k, true, l, true, null),
597             map.subMap(k, lPlusOne).values(), false,
598             expandValues(rangeExpected), vGetter);
599    }
600
601    private List<List<Integer>>
602        expandKeys(SortedMap<Integer,SortedSet<Integer>> map) {
603
604        List<List<Integer>> list = new ArrayList<List<Integer>>();
605        for (Integer key : map.keySet()) {
606            SortedSet<Integer> values = map.get(key);
607            List<Integer> dups = new ArrayList<Integer>();
608            for (int i = 0; i < values.size(); i += 1) {
609                dups.add(key);
610            }
611            list.add(dups);
612        }
613        return list;
614    }
615
616    private List<List<Integer>>
617        expandValues(SortedMap<Integer,SortedSet<Integer>> map) {
618
619        List<List<Integer>> list = new ArrayList<List<Integer>>();
620        for (SortedSet<Integer> values : map.values()) {
621            list.add(new ArrayList<Integer>(values));
622        }
623        return list;
624    }
625
626    private int expandKeySize(SortedMap<Integer,SortedSet<Integer>> map) {
627
628        int size = 0;
629        for (SortedSet<Integer> values : map.values()) {
630            if (values.size() > 0) {
631                size += 1;
632            }
633        }
634        return size;
635    }
636
637    private int expandValueSize(SortedMap<Integer,SortedSet<Integer>> map) {
638
639        int size = 0;
640        for (SortedSet<Integer> values : map.values()) {
641            size += values.size();
642        }
643        return size;
644    }
645
646    private <T> void checkCursor(EntityCursor<T> cursor,
647                                 Collection<T> collection,
648                                 boolean collectionIsKeySet,
649                                 List<List<Integer>> expected,
650                                 Getter<T> getter)
651        throws DatabaseException {
652
653        boolean first;
654        boolean firstDup;
655        Iterator<T> iterator = collection.iterator();
656
657        for (List<Integer> dups : expected) {
658            for (int i : dups) {
659                T o = cursor.next();
660                assertNotNull(o);
661                assertEquals(i, getter.getKey(o));
662                /* Value iterator over duplicates. */
663                if (!collectionIsKeySet) {
664                    assertTrue(iterator.hasNext());
665                    o = iterator.next();
666                    assertNotNull(o);
667                    assertEquals(i, getter.getKey(o));
668                }
669            }
670        }
671
672        first = true;
673        for (List<Integer> dups : expected) {
674            firstDup = true;
675            for (int i : dups) {
676                T o = first ? cursor.first()
677                            : (firstDup ? cursor.next() : cursor.nextDup());
678                assertNotNull(o);
679                assertEquals(i, getter.getKey(o));
680                first = false;
681                firstDup = false;
682            }
683        }
684
685        first = true;
686        for (List<Integer> dups : expected) {
687            if (!dups.isEmpty()) {
688                int i = dups.get(0);
689                T o = first ? cursor.first() : cursor.nextNoDup();
690                assertNotNull(o);
691                assertEquals(i, getter.getKey(o));
692                /* Key iterator over non-duplicates. */
693                if (collectionIsKeySet) {
694                    assertTrue(iterator.hasNext());
695                    o = iterator.next();
696                    assertNotNull(o);
697                    assertEquals(i, getter.getKey(o));
698                }
699                first = false;
700            }
701        }
702
703        List<List<Integer>> reversed = new ArrayList<List<Integer>>();
704        for (List<Integer> dups : expected) {
705            ArrayList<Integer> reversedDups = new ArrayList<Integer>(dups);
706            Collections.reverse(reversedDups);
707            reversed.add(reversedDups);
708        }
709        Collections.reverse(reversed);
710
711        first = true;
712        for (List<Integer> dups : reversed) {
713            for (int i : dups) {
714                T o = first ? cursor.last() : cursor.prev();
715                assertNotNull(o);
716                assertEquals(i, getter.getKey(o));
717                first = false;
718            }
719        }
720
721        first = true;
722        for (List<Integer> dups : reversed) {
723            firstDup = true;
724            for (int i : dups) {
725                T o = first ? cursor.last()
726                            : (firstDup ? cursor.prev() : cursor.prevDup());
727                assertNotNull(o);
728                assertEquals(i, getter.getKey(o));
729                first = false;
730                firstDup = false;
731            }
732        }
733
734        first = true;
735        for (List<Integer> dups : reversed) {
736            if (!dups.isEmpty()) {
737                int i = dups.get(0);
738                T o = first ? cursor.last() : cursor.prevNoDup();
739                assertNotNull(o);
740                assertEquals(i, getter.getKey(o));
741                first = false;
742            }
743        }
744
745        cursor.close();
746    }
747
748    private void checkAllEmpty()
749        throws DatabaseException {
750
751        checkEmpty(primary);
752        checkEmpty(oneToOne);
753        checkEmpty(oneToMany);
754        checkEmpty(manyToOne);
755        checkEmpty(manyToMany);
756    }
757
758    private <K,V> void checkEmpty(EntityIndex<K,V> index)
759        throws DatabaseException {
760
761        EntityCursor<K> keys = index.keys();
762        assertNull(keys.next());
763        assertTrue(!keys.iterator().hasNext());
764        keys.close();
765        EntityCursor<V> entities = index.entities();
766        assertNull(entities.next());
767        assertTrue(!entities.iterator().hasNext());
768        entities.close();
769    }
770
771    private interface Getter<T> {
772        int getKey(T o);
773        T fromInt(int i);
774    }
775
776    private static Getter<MyEntity> entityGetter =
777               new Getter<MyEntity>() {
778        public int getKey(MyEntity o) {
779            return o.key;
780        }
781        public MyEntity fromInt(int i) {
782            throw new UnsupportedOperationException();
783        }
784    };
785
786    private static Getter<Integer> keyGetter =
787               new Getter<Integer>() {
788        public int getKey(Integer o) {
789            return o;
790        }
791        public Integer fromInt(int i) {
792            return Integer.valueOf(i);
793        }
794    };
795
796    private static Getter<RawObject> rawEntityGetter =
797               new Getter<RawObject>() {
798        public int getKey(RawObject o) {
799            Object val = o.getValues().get("key");
800            return ((Integer) val).intValue();
801        }
802        public RawObject fromInt(int i) {
803            throw new UnsupportedOperationException();
804        }
805    };
806
807    private static Getter<Object> rawKeyGetter =
808               new Getter<Object>() {
809        public int getKey(Object o) {
810            return ((Integer) o).intValue();
811        }
812        public Object fromInt(int i) {
813            return Integer.valueOf(i);
814        }
815    };
816
817    @Entity
818    private static class MyEntity {
819
820        @PrimaryKey
821        private int key;
822
823        @SecondaryKey(relate=ONE_TO_ONE)
824        private int oneToOne;
825
826        @SecondaryKey(relate=MANY_TO_ONE)
827        private int manyToOne;
828
829        @SecondaryKey(relate=ONE_TO_MANY)
830        private Set<Integer> oneToMany = new TreeSet<Integer>();
831
832        @SecondaryKey(relate=MANY_TO_MANY)
833        private Set<Integer> manyToMany = new TreeSet<Integer>();
834
835        private MyEntity() {}
836
837        private MyEntity(int key) {
838
839            /* example keys: {0, 1, 2, 3, 4} */
840            this.key = key;
841
842            /* { 0:0, 1:-1, 2:-2, 3:-3, 4:-4 } */
843            oneToOne = -key;
844
845            /* { 0:0, 1:1, 2:2, 3:0, 4:1 } */
846            manyToOne = key % THREE_TO_ONE;
847
848            /* { 0:{}, 1:{10}, 2:{20,21}, 3:{30,31,32}, 4:{40,41,42,43} */
849            for (int i = 0; i < key; i += 1) {
850                oneToMany.add((N_RECORDS * key) + i);
851            }
852
853            /* { 0:{}, 1:{0}, 2:{0,1}, 3:{0,1,2}, 4:{0,1,2,3} */
854            for (int i = 0; i < key; i += 1) {
855                manyToMany.add(i);
856            }
857        }
858
859        @Override
860        public String toString() {
861            return "MyEntity " + key;
862        }
863    }
864}
865