001: /* Copyright (c) 2001-2005, The HSQL Development Group
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the HSQL Development Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: */
030:
031: package org.hsqldb.test;
032:
033: import java.util.Random;
034:
035: import org.hsqldb.lib.DoubleIntIndex;
036: import org.hsqldb.lib.StopWatch;
037:
038: import junit.framework.TestCase;
039:
040: /**
041: * @author fredt@users
042: */
043: public class TestHashStructures extends TestCase {
044:
045: public TestHashStructures(String s) {
046: super (s);
047: }
048:
049: Random randomgen = new java.util.Random();
050:
051: public void testHashMap() throws Exception {
052:
053: boolean failed = false;
054: int testSize = 33;
055: org.hsqldb.lib.HashMap hMap = new org.hsqldb.lib.HashMap();
056: org.hsqldb.lib.IntKeyHashMap hIntMap = new org.hsqldb.lib.IntKeyHashMap();
057: java.util.HashMap uMap = new java.util.HashMap();
058:
059: try {
060: populateBySerialIntKeys(uMap, hMap, testSize);
061: compareByUIterator(uMap, hMap);
062: compareByHIterator(uMap, hMap);
063:
064: // -
065: populateByRandomIntKeys(uMap, hMap, testSize);
066: compareByUIterator(uMap, hMap);
067: compareByHIterator(uMap, hMap);
068:
069: //
070: depopulateRandomly(uMap, hMap, 20);
071: compareByUIterator(uMap, hMap);
072: compareByHIterator(uMap, hMap);
073:
074: // -
075: populateBySerialIntKeys(uMap, hMap, testSize);
076: compareByUIterator(uMap, hMap);
077: compareByHIterator(uMap, hMap);
078:
079: //
080: depopulateByIterator(uMap, hMap, 20);
081: compareByUIterator(uMap, hMap);
082: compareByHIterator(uMap, hMap);
083: } catch (Exception e) {
084: failed = true;
085: }
086:
087: assertTrue(!failed);
088: }
089:
090: public void testIntKeyHashMap() throws Exception {
091:
092: boolean failed = false;
093: int testSize = 33;
094: org.hsqldb.lib.IntKeyHashMap hIntMap = new org.hsqldb.lib.IntKeyHashMap();
095: java.util.HashMap uMap = new java.util.HashMap();
096:
097: try {
098: populateBySerialIntKeysInt(uMap, hIntMap, testSize);
099: compareByUIteratorInt(uMap, hIntMap);
100: populateByRandomIntKeysInt(uMap, hIntMap, testSize);
101: compareByUIteratorInt(uMap, hIntMap);
102: compareByHIteratorInt(uMap, hIntMap);
103:
104: //
105: depopulateByIntIterator(uMap, hIntMap, 20);
106: compareByUIteratorInt(uMap, hIntMap);
107: compareByHIteratorInt(uMap, hIntMap);
108:
109: //
110: clearByIntIterator(uMap, hIntMap);
111: compareByUIteratorInt(uMap, hIntMap);
112: compareByHIteratorInt(uMap, hIntMap);
113:
114: // -
115: populateBySerialIntKeysInt(uMap, hIntMap, testSize);
116: compareByUIteratorInt(uMap, hIntMap);
117: compareByHIteratorInt(uMap, hIntMap);
118:
119: //
120: clearByIntIterator(uMap, hIntMap);
121: compareByUIteratorInt(uMap, hIntMap);
122: compareByHIteratorInt(uMap, hIntMap);
123: } catch (Exception e) {
124: failed = true;
125: }
126:
127: assertTrue(!failed);
128: }
129:
130: public void testHashMappedList() throws Exception {
131:
132: boolean failed = false;
133: int testSize = 33;
134: org.hsqldb.lib.HashMappedList hMap = new org.hsqldb.lib.HashMappedList();
135: java.util.HashMap uMap = new java.util.HashMap();
136:
137: try {
138: populateBySerialIntKeys(uMap, hMap, testSize);
139: compareByUIterator(uMap, hMap);
140: compareByHIterator(uMap, hMap);
141: populateByRandomIntKeys(uMap, hMap, testSize);
142: compareByUIterator(uMap, hMap);
143: compareByHIterator(uMap, hMap);
144: depopulateRandomly(uMap, hMap, 20);
145: compareByUIterator(uMap, hMap);
146: compareByHIterator(uMap, hMap);
147: populateByRandomIntKeys(uMap, hMap, testSize);
148: compareByUIterator(uMap, hMap);
149: compareByHIterator(uMap, hMap);
150: depopulateRandomly(uMap, hMap, 20);
151: populateBySerialIntKeys(uMap, hMap, testSize);
152: compareByUIterator(uMap, hMap);
153: compareByHIterator(uMap, hMap);
154: } catch (Exception e) {
155: failed = true;
156: }
157:
158: assertTrue(!failed);
159: }
160:
161: public void testDoubleIntLookup() throws Exception {
162:
163: boolean failed = false;
164: int testSize = 512;
165: org.hsqldb.lib.IntKeyHashMap hIntMap = new org.hsqldb.lib.IntKeyHashMap();
166: DoubleIntIndex intLookup = new DoubleIntIndex(12, false);
167:
168: try {
169: intLookup.setKeysSearchTarget();
170: populateBySerialIntKeysInt(intLookup, hIntMap, testSize);
171: compareByHIteratorInt(intLookup, hIntMap);
172: populateByRandomIntKeysInt(intLookup, hIntMap, testSize);
173: compareByHIteratorInt(intLookup, hIntMap);
174: } catch (Exception e) {
175: failed = true;
176: }
177:
178: assertTrue(!failed);
179: }
180:
181: public void testDoubleIntSpeed() throws Exception {
182:
183: boolean failed = false;
184: int testSize = 500;
185: org.hsqldb.lib.IntKeyHashMap hIntMap = new org.hsqldb.lib.IntKeyHashMap();
186: DoubleIntIndex intLookup = new DoubleIntIndex(testSize, false);
187:
188: intLookup.setKeysSearchTarget();
189: populateByRandomIntKeysInt(intLookup, hIntMap, testSize);
190: compareByHIteratorInt(intLookup, hIntMap);
191:
192: int[] sample = getSampleIntArray(intLookup, 100);
193: int[] sampleVals = new int[sample.length];
194: int i = 0;
195: int j = 0;
196: StopWatch sw = new StopWatch();
197:
198: try {
199: for (j = 0; j < 10000; j++) {
200: for (i = 0; i < sample.length; i++) {
201: int pos = intLookup
202: .findFirstEqualKeyIndex(sample[i]);
203:
204: sampleVals[i] = intLookup.getValue(pos);
205:
206: intLookup.remove(pos);
207: }
208:
209: for (i = 0; i < sample.length; i++) {
210: intLookup.addUnique(sample[i], sampleVals[i]);
211: }
212: }
213:
214: System.out.println(sw
215: .elapsedTimeToMessage("Double int table times"));
216: intLookup.findFirstEqualKeyIndex(0); // sort
217: compareByHIteratorInt(intLookup, hIntMap);
218: } catch (Exception e) {
219: System.out.println(sw
220: .elapsedTimeToMessage("Double int table error: i ="
221: + i));
222:
223: failed = true;
224: }
225:
226: assertTrue(!failed);
227: }
228:
229: int[] getSampleIntArray(org.hsqldb.lib.DoubleIntIndex index,
230: int size) {
231:
232: int[] array = new int[size];
233: org.hsqldb.lib.IntKeyHashMap map = new org.hsqldb.lib.IntKeyHashMap();
234:
235: for (; map.size() < size;) {
236: int pos = nextIntRandom(randomgen, index.size());
237:
238: map.put(pos, null);
239: }
240:
241: org.hsqldb.lib.Iterator it = map.keySet().iterator();
242:
243: for (int i = 0; i < size; i++) {
244: int pos = it.nextInt();
245:
246: array[i] = index.getKey(pos);
247: }
248:
249: return array;
250: }
251:
252: void populateBySerialIntKeys(java.util.HashMap uMap,
253: org.hsqldb.lib.HashMap hMap, int testSize) throws Exception {
254:
255: for (int i = 0; i < testSize; i++) {
256: int intValue = randomgen.nextInt();
257:
258: uMap.put(new Integer(i), new Integer(intValue));
259: hMap.put(new Integer(i), new Integer(intValue));
260:
261: if (uMap.size() != hMap.size()) {
262: throw new Exception("HashMap size mismatch");
263: }
264: }
265: }
266:
267: void populateBySerialIntKeysInt(java.util.HashMap uMap,
268: org.hsqldb.lib.IntKeyHashMap hMap, int testSize)
269: throws Exception {
270:
271: for (int i = 0; i < testSize; i++) {
272: int intValue = randomgen.nextInt();
273:
274: uMap.put(new Integer(i), new Integer(intValue));
275: hMap.put(i, new Integer(intValue));
276:
277: if (uMap.size() != hMap.size()) {
278: throw new Exception("HashMap size mismatch");
279: }
280: }
281: }
282:
283: void populateBySerialIntKeysInt(DoubleIntIndex intLookup,
284: org.hsqldb.lib.IntKeyHashMap hMap, int testSize)
285: throws Exception {
286:
287: for (int i = 0; i < testSize; i++) {
288: int intValue = randomgen.nextInt();
289:
290: intLookup.addUnique(i, intValue);
291: hMap.put(i, new Integer(intValue));
292:
293: if (intLookup.size() != hMap.size()) {
294: throw new Exception("HashMap size mismatch");
295: }
296: }
297: }
298:
299: void populateByRandomIntKeysInt(DoubleIntIndex intLookup,
300: org.hsqldb.lib.IntKeyHashMap hMap, int testSize)
301: throws Exception {
302:
303: for (int i = 0; i < testSize; i++) {
304: int intValue = randomgen.nextInt();
305:
306: intLookup.addUnique(intValue, i);
307: hMap.put(intValue, new Integer(i));
308:
309: // actually this can happen as duplicates are allowed in DoubleIntTable
310: if (intLookup.size() != hMap.size()) {
311: throw new Exception("Duplicate random in int lookup");
312: }
313: }
314: }
315:
316: void populateByRandomIntKeys(java.util.HashMap uMap,
317: org.hsqldb.lib.HashMap hMap, int testSize) throws Exception {
318:
319: for (int i = 0; i < testSize; i++) {
320: int intValue = randomgen.nextInt();
321:
322: uMap.put(new Integer(intValue), new Integer(i));
323: hMap.put(new Integer(intValue), new Integer(i));
324:
325: if (uMap.size() != hMap.size()) {
326: throw new Exception("HashMap size mismatch");
327: }
328: }
329: }
330:
331: void populateByRandomIntKeysInt(java.util.HashMap uMap,
332: org.hsqldb.lib.IntKeyHashMap hMap, int testSize)
333: throws Exception {
334:
335: for (int i = 0; i < testSize; i++) {
336: int intValue = randomgen.nextInt();
337:
338: uMap.put(new Integer(intValue), new Integer(i));
339: hMap.put(intValue, new Integer(i));
340:
341: if (uMap.size() != hMap.size()) {
342: throw new Exception("HashMap size mismatch");
343: }
344: }
345: }
346:
347: void depopulateRandomly(java.util.HashMap uMap,
348: org.hsqldb.lib.HashMap hMap, int testCount)
349: throws Exception {
350:
351: int removeCount = 0;
352: int size = uMap.size();
353:
354: if (testCount > size / 2) {
355: testCount = size / 2;
356: }
357:
358: while (removeCount < testCount) {
359: java.util.Iterator uIt = uMap.keySet().iterator();
360:
361: for (int i = 0; uIt.hasNext(); i++) {
362: Object uKey = uIt.next();
363: int intValue = randomgen.nextInt(size);
364:
365: if (intValue == i) {
366: uIt.remove();
367: hMap.remove(uKey);
368:
369: removeCount++;
370: }
371:
372: if (uMap.size() != hMap.size()) {
373: throw new Exception("HashMap size mismatch");
374: }
375: }
376: }
377: }
378:
379: void depopulateByIterator(java.util.HashMap uMap,
380: org.hsqldb.lib.HashMap hMap, int testCount)
381: throws Exception {
382:
383: org.hsqldb.lib.Iterator hIt = hMap.keySet().iterator();
384:
385: System.out.println(uMap.size());
386:
387: for (int i = 0; hIt.hasNext(); i++) {
388: Object key = hIt.next();
389: int check = randomgen.nextInt(2);
390:
391: if (check == i % 2) {
392: hIt.remove();
393: uMap.remove(key);
394: }
395:
396: if (uMap.size() != hMap.size()) {
397: throw new Exception("HashMap size mismatch");
398: }
399: }
400:
401: System.out.println(uMap.size());
402: }
403:
404: void depopulateByIntIterator(java.util.HashMap uMap,
405: org.hsqldb.lib.IntKeyHashMap hIntMap, int testCount)
406: throws Exception {
407:
408: org.hsqldb.lib.Iterator hIt = hIntMap.keySet().iterator();
409:
410: System.out.println(uMap.size());
411:
412: for (int i = 0; hIt.hasNext(); i++) {
413: Object key = new Integer(hIt.nextInt());
414: int check = randomgen.nextInt(2);
415:
416: if (check == i % 2) {
417: hIt.remove();
418: uMap.remove(key);
419: }
420:
421: if (uMap.size() != hIntMap.size()) {
422: throw new Exception("HashMap size mismatch");
423: }
424: }
425:
426: System.out.println(uMap.size());
427: }
428:
429: void clearByIntIterator(java.util.HashMap uMap,
430: org.hsqldb.lib.IntKeyHashMap hIntMap) throws Exception {
431:
432: org.hsqldb.lib.Iterator hIt = hIntMap.keySet().iterator();
433:
434: System.out.println(uMap.size());
435:
436: for (int i = 0; hIt.hasNext(); i++) {
437: Object key = new Integer(hIt.nextInt());
438:
439: hIt.remove();
440: uMap.remove(key);
441:
442: if (uMap.size() != hIntMap.size()) {
443: throw new Exception("HashMap size mismatch");
444: }
445: }
446:
447: System.out.println(uMap.size());
448: }
449:
450: void compareByUIterator(java.util.HashMap uMap,
451: org.hsqldb.lib.HashMap hMap) throws Exception {
452:
453: java.util.Iterator uIt = uMap.keySet().iterator();
454:
455: for (int i = 0; uIt.hasNext(); i++) {
456: Object uKey = uIt.next();
457: Object oU = uMap.get(uKey);
458: Object hU = hMap.get(uKey);
459:
460: if (!oU.equals(hU)) {
461: throw new Exception("HashMap value mismatch");
462: }
463: }
464: }
465:
466: void compareByHIterator(java.util.HashMap uMap,
467: org.hsqldb.lib.HashMap hMap) throws Exception {
468:
469: org.hsqldb.lib.Iterator hIt = hMap.keySet().iterator();
470:
471: for (int i = 0; hIt.hasNext(); i++) {
472: Object hKey = hIt.next();
473: Object oU = uMap.get(hKey);
474: Object hU = hMap.get(hKey);
475:
476: if (!oU.equals(hU)) {
477: throw new Exception("HashMap value mismatch");
478: }
479: }
480: }
481:
482: void compareByUIteratorInt(java.util.HashMap uMap,
483: org.hsqldb.lib.IntKeyHashMap hMap) throws Exception {
484:
485: java.util.Iterator uIt = uMap.keySet().iterator();
486:
487: for (int i = 0; uIt.hasNext(); i++) {
488: Object uKey = uIt.next();
489: Object oU = uMap.get(uKey);
490: Object hU = hMap.get(((Integer) uKey).intValue());
491:
492: if (!oU.equals(hU)) {
493: throw new Exception("HashMap value mismatch");
494: }
495: }
496: }
497:
498: void compareByHIteratorInt(java.util.HashMap uMap,
499: org.hsqldb.lib.IntKeyHashMap hMap) throws Exception {
500:
501: org.hsqldb.lib.Iterator hIt = hMap.keySet().iterator();
502:
503: for (int i = 0; hIt.hasNext(); i++) {
504: Object hKey = new Integer(hIt.nextInt());
505: Object oU = uMap.get(hKey);
506: Object hU = hMap.get(((Integer) hKey).intValue());
507:
508: if (!oU.equals(hU)) {
509: throw new Exception("HashMap value mismatch");
510: }
511: }
512: }
513:
514: void compareByHIteratorInt(DoubleIntIndex intLookup,
515: org.hsqldb.lib.IntKeyHashMap hMap) throws Exception {
516:
517: org.hsqldb.lib.Iterator hIt = hMap.keySet().iterator();
518:
519: for (int i = 0; hIt.hasNext(); i++) {
520: int hK = hIt.nextInt();
521: int lookup = intLookup.findFirstEqualKeyIndex(hK);
522: int lV = intLookup.getValue(lookup);
523: Integer hV = (Integer) hMap.get(hK);
524:
525: if (hV.intValue() != lV) {
526: throw new Exception("HashMap value mismatch");
527: }
528: }
529: }
530:
531: int nextIntRandom(Random r, int range) {
532:
533: int b = Math.abs(r.nextInt());
534:
535: return b % range;
536: }
537:
538: public static void main(String[] argv) {
539:
540: try {
541: TestHashStructures test = new TestHashStructures(
542: "testHashMap");
543:
544: test.testHashMap();
545: test.testIntKeyHashMap();
546: test.testHashMappedList();
547: test.testDoubleIntLookup();
548: test.testDoubleIntSpeed();
549: } catch (Exception e) {
550: e.printStackTrace();
551: }
552: }
553: }
|