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.lib;
032:
033: import java.util.NoSuchElementException;
034:
035: /**
036: * Maintains an ordered integer->integer lookup table, consisting of two
037: * columns, one for keys, the other for values.
038: *
039: * The table is sorted on either the key or value column, depending on the calls to
040: * setKeysSearchTarget() or setValuesSearchTarget(). By default, the table is
041: * sorted on values.<p>
042: *
043: * findXXX() methods return the array index into the list
044: * pair containing a matching key or value, or or -1 if not found.<p>
045: *
046: * Sorting methods originally contributed by Tony Lai.
047: *
048: * @author fredt@users
049: * @version 1.8.0
050: * @since 1.8.0
051: */
052: public class DoubleIntIndex implements IntLookup {
053:
054: private int count = 0;
055: private int capacity;
056: private boolean sorted = true;
057: private boolean sortOnValues = true;
058: private boolean hasChanged;
059: private final boolean fixedSize;
060: private int[] keys;
061: private int[] values;
062:
063: //
064: private int targetSearchValue;
065:
066: public DoubleIntIndex(int capacity, boolean fixedSize) {
067:
068: this .capacity = capacity;
069: keys = new int[capacity];
070: values = new int[capacity];
071: this .fixedSize = fixedSize;
072: hasChanged = true;
073: }
074:
075: public synchronized int getKey(int i) {
076:
077: if (i < 0 || i >= count) {
078: throw new IndexOutOfBoundsException();
079: }
080:
081: return keys[i];
082: }
083:
084: public synchronized int getValue(int i) {
085:
086: if (i < 0 || i >= count) {
087: throw new IndexOutOfBoundsException();
088: }
089:
090: return values[i];
091: }
092:
093: /**
094: * Modifies an existing pair.
095: * @param i the index
096: * @param key the key
097: */
098: public synchronized void setKey(int i, int key) {
099:
100: if (i < 0 || i >= count) {
101: throw new IndexOutOfBoundsException();
102: }
103:
104: if (!sortOnValues) {
105: sorted = false;
106: }
107:
108: keys[i] = key;
109: }
110:
111: /**
112: * Modifies an existing pair.
113: * @param i the index
114: * @param value the value
115: */
116: public synchronized void setValue(int i, int value) {
117:
118: if (i < 0 || i >= count) {
119: throw new IndexOutOfBoundsException();
120: }
121:
122: if (sortOnValues) {
123: sorted = false;
124: }
125:
126: values[i] = value;
127: }
128:
129: public synchronized int size() {
130: return count;
131: }
132:
133: public synchronized int capacity() {
134: return capacity;
135: }
136:
137: /**
138: * Adds a pair into the table.
139: *
140: * @param key the key
141: * @param value the value
142: * @return true or false depending on success
143: */
144: public synchronized boolean addUnsorted(int key, int value) {
145:
146: if (count == capacity) {
147: if (fixedSize) {
148: return false;
149: } else {
150: doubleCapacity();
151: }
152: }
153:
154: if (sorted && count != 0) {
155: if (sortOnValues) {
156: if (value < values[count - 1]) {
157: sorted = false;
158: }
159: } else {
160: if (value < keys[count - 1]) {
161: sorted = false;
162: }
163: }
164: }
165:
166: hasChanged = true;
167: keys[count] = key;
168: values[count] = value;
169:
170: count++;
171:
172: return true;
173: }
174:
175: /**
176: * Adds a key, value pair into the table with the guarantee that the key
177: * is equal or larger than the largest existing key. This prevents a sort
178: * from taking place on next call to find()
179: *
180: * @param key the key
181: * @param value the value
182: * @return true or false depending on success
183: */
184: public synchronized boolean addSorted(int key, int value) {
185:
186: if (count == capacity) {
187: if (fixedSize) {
188: return false;
189: } else {
190: doubleCapacity();
191: }
192: }
193:
194: if (count != 0 && value < values[count - 1]) {
195: return false;
196: }
197:
198: hasChanged = true;
199: keys[count] = key;
200: values[count] = value;
201:
202: count++;
203:
204: return true;
205: }
206:
207: /**
208: * Adds a pair, ensuring no duplicate key xor value already exists in the
209: * current search target column.
210: * @param key the key
211: * @param value the value
212: * @return true or false depending on success
213: */
214: public synchronized boolean addUnique(int key, int value) {
215:
216: if (count == capacity) {
217: if (fixedSize) {
218: return false;
219: } else {
220: doubleCapacity();
221: }
222: }
223:
224: if (!sorted) {
225: fastQuickSort();
226: }
227:
228: targetSearchValue = sortOnValues ? value : key;
229:
230: int i = binaryEmptySlotSearch();
231:
232: if (i == -1) {
233: return false;
234: }
235:
236: hasChanged = true;
237:
238: if (count != i) {
239: moveRows(i, i + 1, count - i);
240: }
241:
242: keys[i] = key;
243: values[i] = value;
244:
245: count++;
246:
247: return true;
248: }
249:
250: /**
251: * Adds a pair, maintaining sorted order
252: * current search target column.
253: * @param key the key
254: * @param value the value
255: * @return true or false depending on success
256: */
257: public synchronized boolean add(int key, int value) {
258:
259: if (count == capacity) {
260: if (fixedSize) {
261: return false;
262: } else {
263: doubleCapacity();
264: }
265: }
266:
267: if (!sorted) {
268: fastQuickSort();
269: }
270:
271: targetSearchValue = sortOnValues ? value : key;
272:
273: int i = binarySlotSearch();
274:
275: if (i == -1) {
276: return false;
277: }
278:
279: hasChanged = true;
280:
281: if (count != i) {
282: moveRows(i, i + 1, count - i);
283: }
284:
285: keys[i] = key;
286: values[i] = value;
287:
288: count++;
289:
290: return true;
291: }
292:
293: public int lookupFirstEqual(int key) throws NoSuchElementException {
294:
295: if (sortOnValues) {
296: sorted = false;
297: sortOnValues = false;
298: }
299:
300: int i = findFirstEqualKeyIndex(key);
301:
302: if (i == -1) {
303: throw new NoSuchElementException();
304: }
305:
306: return getValue(i);
307: }
308:
309: public int lookupFirstGreaterEqual(int key)
310: throws NoSuchElementException {
311:
312: if (sortOnValues) {
313: sorted = false;
314: sortOnValues = false;
315: }
316:
317: int i = findFirstGreaterEqualKeyIndex(key);
318:
319: if (i == -1) {
320: throw new NoSuchElementException();
321: }
322:
323: return getValue(i);
324: }
325:
326: public synchronized void setValuesSearchTarget() {
327:
328: if (!sortOnValues) {
329: sorted = false;
330: }
331:
332: sortOnValues = true;
333: }
334:
335: public synchronized void setKeysSearchTarget() {
336:
337: if (sortOnValues) {
338: sorted = false;
339: }
340:
341: sortOnValues = false;
342: }
343:
344: /**
345: * @param value the value
346: * @return the index
347: */
348: public synchronized int findFirstGreaterEqualKeyIndex(int value) {
349:
350: int index = findFirstGreaterEqualSlotIndex(value);
351:
352: return index == count ? -1 : index;
353: }
354:
355: /**
356: * @param value the value
357: * @return the index
358: */
359: public synchronized int findFirstEqualKeyIndex(int value) {
360:
361: if (!sorted) {
362: fastQuickSort();
363: }
364:
365: targetSearchValue = value;
366:
367: return binaryFirstSearch();
368: }
369:
370: /**
371: * This method is similar to findFirstGreaterEqualKeyIndex(int) but
372: * returns the index of the empty row past the end of the array if
373: * the search value is larger than all the values / keys in the searched
374: * column.
375: * @param value the value
376: * @return the index
377: */
378: public synchronized int findFirstGreaterEqualSlotIndex(int value) {
379:
380: if (!sorted) {
381: fastQuickSort();
382: }
383:
384: targetSearchValue = value;
385:
386: return binarySlotSearch();
387: }
388:
389: /**
390: * Returns the index of the lowest element == the given search target,
391: * or -1
392: * @return index or -1 if not found
393: */
394: private int binaryFirstSearch() {
395:
396: int low = 0;
397: int high = count;
398: int mid = 0;
399: int compare = 0;
400: int found = count;
401:
402: while (low < high) {
403: mid = (low + high) / 2;
404: compare = compare(mid);
405:
406: if (compare < 0) {
407: high = mid;
408: } else if (compare > 0) {
409: low = mid + 1;
410: } else {
411: high = mid;
412: found = mid;
413: }
414: }
415:
416: return found == count ? -1 : found;
417: }
418:
419: /**
420: * Returns the index of the lowest element > the given search target
421: * @return the index
422: */
423: private int binaryGreaterSearch() {
424:
425: int low = 0;
426: int high = count;
427: int mid = 0;
428: int compare = 0;
429:
430: while (low < high) {
431: mid = (low + high) / 2;
432: compare = compare(mid);
433:
434: if (compare < 0) {
435: high = mid;
436: } else {
437: low = mid + 1;
438: }
439: }
440:
441: return low == count ? -1 : low;
442: }
443:
444: /**
445: * Returns the index of the lowest element >= the given search target,
446: * or count
447: * @return the index
448: */
449: private int binarySlotSearch() {
450:
451: int low = 0;
452: int high = count;
453: int mid = 0;
454: int compare = 0;
455:
456: while (low < high) {
457: mid = (low + high) / 2;
458: compare = compare(mid);
459:
460: if (compare <= 0) {
461: high = mid;
462: } else {
463: low = mid + 1;
464: }
465: }
466:
467: return low;
468: }
469:
470: /**
471: * Returns the index of the lowest element > the given search target
472: * or count or -1 if target is found
473: * @return the index
474: */
475: private int binaryEmptySlotSearch() {
476:
477: int low = 0;
478: int high = count;
479: int mid = 0;
480: int compare = 0;
481:
482: while (low < high) {
483: mid = (low + high) / 2;
484: compare = compare(mid);
485:
486: if (compare < 0) {
487: high = mid;
488: } else if (compare > 0) {
489: low = mid + 1;
490: } else {
491: return -1;
492: }
493: }
494:
495: return low;
496: }
497:
498: private synchronized void fastQuickSort() {
499:
500: quickSort(0, count - 1);
501: insertionSort(0, count - 1);
502:
503: sorted = true;
504: }
505:
506: private void quickSort(int l, int r) {
507:
508: int M = 4;
509: int i;
510: int j;
511: int v;
512:
513: if ((r - l) > M) {
514: i = (r + l) / 2;
515:
516: if (lessThan(i, l)) {
517: swap(l, i); // Tri-Median Methode!
518: }
519:
520: if (lessThan(r, l)) {
521: swap(l, r);
522: }
523:
524: if (lessThan(r, i)) {
525: swap(i, r);
526: }
527:
528: j = r - 1;
529:
530: swap(i, j);
531:
532: i = l;
533: v = j;
534:
535: for (;;) {
536: while (lessThan(++i, v)) {
537: }
538:
539: while (lessThan(v, --j)) {
540: }
541:
542: if (j < i) {
543: break;
544: }
545:
546: swap(i, j);
547: }
548:
549: swap(i, r - 1);
550: quickSort(l, j);
551: quickSort(i + 1, r);
552: }
553: }
554:
555: private void insertionSort(int lo0, int hi0) {
556:
557: int i;
558: int j;
559:
560: for (i = lo0 + 1; i <= hi0; i++) {
561: j = i;
562:
563: while ((j > lo0) && lessThan(i, j - 1)) {
564: j--;
565: }
566:
567: if (i != j) {
568: moveAndInsertRow(i, j);
569: }
570: }
571: }
572:
573: private void moveAndInsertRow(int i, int j) {
574:
575: int col1 = keys[i];
576: int col2 = values[i];
577:
578: moveRows(j, j + 1, i - j);
579:
580: keys[j] = col1;
581: values[j] = col2;
582: }
583:
584: private void doubleCapacity() {
585:
586: keys = (int[]) ArrayUtil.resizeArray(keys, capacity * 2);
587: values = (int[]) ArrayUtil.resizeArray(values, capacity * 2);
588: capacity *= 2;
589: }
590:
591: private void swap(int i1, int i2) {
592:
593: int col1 = keys[i1];
594: int col2 = values[i1];
595:
596: keys[i1] = keys[i2];
597: values[i1] = values[i2];
598: keys[i2] = col1;
599: values[i2] = col2;
600: }
601:
602: private void moveRows(int fromIndex, int toIndex, int rows) {
603: System.arraycopy(keys, fromIndex, keys, toIndex, rows);
604: System.arraycopy(values, fromIndex, values, toIndex, rows);
605: }
606:
607: public void removeRange(int start, int limit) {
608:
609: moveRows(limit, start, count - limit);
610:
611: count -= (limit - start);
612: }
613:
614: public void removeAll() {
615:
616: hasChanged = true;
617:
618: ArrayUtil.clearArray(ArrayUtil.CLASS_CODE_INT, keys, 0, count);
619: ArrayUtil
620: .clearArray(ArrayUtil.CLASS_CODE_INT, values, 0, count);
621:
622: count = 0;
623: }
624:
625: /**
626: * Check if targeted column value in the row indexed i is less than the
627: * search target object.
628: * @param i the index
629: * @return -1, 0 or +1
630: */
631: private int compare(int i) {
632:
633: if (sortOnValues) {
634: if (targetSearchValue > values[i]) {
635: return 1;
636: } else if (targetSearchValue < values[i]) {
637: return -1;
638: }
639: } else {
640: if (targetSearchValue > keys[i]) {
641: return 1;
642: } else if (targetSearchValue < keys[i]) {
643: return -1;
644: }
645: }
646:
647: return 0;
648: }
649:
650: public final synchronized void remove(int position) {
651:
652: hasChanged = true;
653:
654: moveRows(position + 1, position, count - position - 1);
655:
656: count--;
657:
658: keys[count] = 0;
659: values[count] = 0;
660: }
661:
662: /**
663: * Check if row indexed i is less than row indexed j
664: * @param i the first index
665: * @param j the second index
666: * @return true or false
667: */
668: private boolean lessThan(int i, int j) {
669:
670: if (sortOnValues) {
671: if (values[i] < values[j]) {
672: return true;
673: }
674: } else {
675: if (keys[i] < keys[j]) {
676: return true;
677: }
678: }
679:
680: return false;
681: }
682: }
|