test/java/compat/src/com/sleepycat/persist/test/IndexTest.java

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