DoubleIntIndex


1   /* Copyright (c) 2001-2005, The HSQL Development Group
2    * All rights reserved.
3    *
4    * Redistribution and use in source and binary forms, with or without
5    * modification, are permitted provided that the following conditions are met:
6    *
7    * Redistributions of source code must retain the above copyright notice, this
8    * list of conditions and the following disclaimer.
9    *
10   * Redistributions in binary form must reproduce the above copyright notice,
11   * this list of conditions and the following disclaimer in the documentation
12   * and/or other materials provided with the distribution.
13   *
14   * Neither the name of the HSQL Development Group nor the names of its
15   * contributors may be used to endorse or promote products derived from this
16   * software without specific prior written permission.
17   *
18   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21   * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
22   * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29   */
30  
31  
32  package org.hsqldb.lib;
33  
34  import java.util.NoSuchElementException  ;
35  
36  /**
37   * Maintains an ordered  integer->integer lookup table, consisting of two
38   * columns, one for keys, the other for values.
39   *
40   * The table is sorted on either the key or value column, depending on the calls to
41   * setKeysSearchTarget() or setValuesSearchTarget(). By default, the table is
42   * sorted on values.<p>
43   *
44   * findXXX() methods return the array index into the list
45   * pair containing a matching key or value, or  or -1 if not found.<p>
46   *
47   * Sorting methods originally contributed by Tony Lai.
48   *
49   * @author fredt@users
50   * @version 1.8.0
51   * @since 1.8.0
52   */
53  public class DoubleIntIndex implements IntLookup {
54  
55      private int           count = 0;
56      private int           capacity;
57      private boolean       sorted       = true;
58      private boolean       sortOnValues = true;
59      private boolean       hasChanged;
60      private final boolean fixedSize;
61      private int[]         keys;
62      private int[]         values;
63  
64  //
65      private int targetSearchValue;
66  
67      public DoubleIntIndex(int capacity, boolean fixedSize) {
68  
69          this.capacity  = capacity;
70          keys           = new int[capacity];
71          values         = new int[capacity];
72          this.fixedSize = fixedSize;
73          hasChanged     = true;
74      }
75  
76      public synchronized int getKey(int i) {
77  
78          if (i < 0 || i >= count) {
79              throw new IndexOutOfBoundsException  ();
80          }
81  
82          return keys[i];
83      }
84  
85      public synchronized int getValue(int i) {
86  
87          if (i < 0 || i >= count) {
88              throw new IndexOutOfBoundsException  ();
89          }
90  
91          return values[i];
92      }
93  
94      /**
95       * Modifies an existing pair.
96       * @param i the index
97       * @param key the key
98       */
99      public synchronized void setKey(int i, int key) {
100 
101         if (i < 0 || i >= count) {
102             throw new IndexOutOfBoundsException  ();
103         }
104 
105         if (!sortOnValues) {
106             sorted = false;
107         }
108 
109         keys[i] = key;
110     }
111 
112     /**
113      * Modifies an existing pair.
114      * @param i the index
115      * @param value the value
116      */
117     public synchronized void setValue(int i, int value) {
118 
119         if (i < 0 || i >= count) {
120             throw new IndexOutOfBoundsException  ();
121         }
122 
123         if (sortOnValues) {
124             sorted = false;
125         }
126 
127         values[i] = value;
128     }
129 
130     public synchronized int size() {
131         return count;
132     }
133 
134     public synchronized int capacity() {
135         return capacity;
136     }
137 
138     /**
139      * Adds a pair into the table.
140      *
141      * @param key the key
142      * @param value the value
143      * @return true or false depending on success
144      */
145     public synchronized boolean addUnsorted(int key, int value) {
146 
147         if (count == capacity) {
148             if (fixedSize) {
149                 return false;
150             } else {
151                 doubleCapacity();
152             }
153         }
154 
155         if (sorted && count != 0) {
156             if (sortOnValues) {
157                 if (value < values[count - 1]) {
158                     sorted = false;
159                 }
160             } else {
161                 if (value < keys[count - 1]) {
162                     sorted = false;
163                 }
164             }
165         }
166 
167         hasChanged    = true;
168         keys[count]   = key;
169         values[count] = value;
170 
171         count++;
172 
173         return true;
174     }
175 
176     /**
177      * Adds a key, value pair into the table with the guarantee that the key
178      * is equal or larger than the largest existing key. This prevents a sort
179      * from taking place on next call to find()
180      *
181      * @param key the key
182      * @param value the value
183      * @return true or false depending on success
184      */
185     public synchronized boolean addSorted(int key, int value) {
186 
187         if (count == capacity) {
188             if (fixedSize) {
189                 return false;
190             } else {
191                 doubleCapacity();
192             }
193         }
194 
195         if (count != 0 && value < values[count - 1]) {
196             return false;
197         }
198 
199         hasChanged    = true;
200         keys[count]   = key;
201         values[count] = value;
202 
203         count++;
204 
205         return true;
206     }
207 
208     /**
209      * Adds a pair, ensuring no duplicate key xor value already exists in the
210      * current search target column.
211      * @param key the key
212      * @param value the value
213      * @return true or false depending on success
214      */
215     public synchronized boolean addUnique(int key, int value) {
216 
217         if (count == capacity) {
218             if (fixedSize) {
219                 return false;
220             } else {
221                 doubleCapacity();
222             }
223         }
224 
225         if (!sorted) {
226             fastQuickSort();
227         }
228 
229         targetSearchValue = sortOnValues ? value
230                                          : key;
231 
232         int i = binaryEmptySlotSearch();
233 
234         if (i == -1) {
235             return false;
236         }
237 
238         hasChanged = true;
239 
240         if (count != i) {
241             moveRows(i, i + 1, count - i);
242         }
243 
244         keys[i]   = key;
245         values[i] = value;
246 
247         count++;
248 
249         return true;
250     }
251 
252     /**
253      * Adds a pair, maintaining sorted order
254      * current search target column.
255      * @param key the key
256      * @param value the value
257      * @return true or false depending on success
258      */
259     public synchronized boolean add(int key, int value) {
260 
261         if (count == capacity) {
262             if (fixedSize) {
263                 return false;
264             } else {
265                 doubleCapacity();
266             }
267         }
268 
269         if (!sorted) {
270             fastQuickSort();
271         }
272 
273         targetSearchValue = sortOnValues ? value
274                                          : key;
275 
276         int i = binarySlotSearch();
277 
278         if (i == -1) {
279             return false;
280         }
281 
282         hasChanged = true;
283 
284         if (count != i) {
285             moveRows(i, i + 1, count - i);
286         }
287 
288         keys[i]   = key;
289         values[i] = value;
290 
291         count++;
292 
293         return true;
294     }
295 
296     public int lookupFirstEqual(int key) throws NoSuchElementException   {
297 
298         if (sortOnValues) {
299             sorted       = false;
300             sortOnValues = false;
301         }
302 
303         int i = findFirstEqualKeyIndex(key);
304 
305         if (i == -1) {
306             throw new NoSuchElementException  ();
307         }
308 
309         return getValue(i);
310     }
311 
312     public int lookupFirstGreaterEqual(int key)
313     throws NoSuchElementException   {
314 
315         if (sortOnValues) {
316             sorted       = false;
317             sortOnValues = false;
318         }
319 
320         int i = findFirstGreaterEqualKeyIndex(key);
321 
322         if (i == -1) {
323             throw new NoSuchElementException  ();
324         }
325 
326         return getValue(i);
327     }
328 
329     public synchronized void setValuesSearchTarget() {
330 
331         if (!sortOnValues) {
332             sorted = false;
333         }
334 
335         sortOnValues = true;
336     }
337 
338     public synchronized void setKeysSearchTarget() {
339 
340         if (sortOnValues) {
341             sorted = false;
342         }
343 
344         sortOnValues = false;
345     }
346 
347     /**
348      * @param value the value
349      * @return the index
350      */
351     public synchronized int findFirstGreaterEqualKeyIndex(int value) {
352 
353         int index = findFirstGreaterEqualSlotIndex(value);
354 
355         return index == count ? -1
356                               : index;
357     }
358 
359     /**
360      * @param value the value
361      * @return the index
362      */
363     public synchronized int findFirstEqualKeyIndex(int value) {
364 
365         if (!sorted) {
366             fastQuickSort();
367         }
368 
369         targetSearchValue = value;
370 
371         return binaryFirstSearch();
372     }
373 
374     /**
375      * This method is similar to findFirstGreaterEqualKeyIndex(int) but
376      * returns the index of the empty row past the end of the array if
377      * the search value is larger than all the values / keys in the searched
378      * column.
379      * @param value the value
380      * @return the index
381      */
382     public synchronized int findFirstGreaterEqualSlotIndex(int value) {
383 
384         if (!sorted) {
385             fastQuickSort();
386         }
387 
388         targetSearchValue = value;
389 
390         return binarySlotSearch();
391     }
392 
393     /**
394      * Returns the index of the lowest element == the given search target,
395      * or -1
396      * @return index or -1 if not found
397      */
398     private int binaryFirstSearch() {
399 
400         int low     = 0;
401         int high    = count;
402         int mid     = 0;
403         int compare = 0;
404         int found   = count;
405 
406         while (low < high) {
407             mid     = (low + high) / 2;
408             compare = compare(mid);
409 
410             if (compare < 0) {
411                 high = mid;
412             } else if (compare > 0) {
413                 low = mid + 1;
414             } else {
415                 high  = mid;
416                 found = mid;
417             }
418         }
419 
420         return found == count ? -1
421                               : found;
422     }
423 
424     /**
425      * Returns the index of the lowest element > the given search target
426      *     @return the index
427      */
428     private int binaryGreaterSearch() {
429 
430         int low     = 0;
431         int high    = count;
432         int mid     = 0;
433         int compare = 0;
434 
435         while (low < high) {
436             mid     = (low + high) / 2;
437             compare = compare(mid);
438 
439             if (compare < 0) {
440                 high = mid;
441             } else {
442                 low = mid + 1;
443             }
444         }
445 
446         return low == count ? -1
447                             : low;
448     }
449 
450     /**
451      * Returns the index of the lowest element >= the given search target,
452      * or count
453      *     @return the index
454      */
455     private int binarySlotSearch() {
456 
457         int low     = 0;
458         int high    = count;
459         int mid     = 0;
460         int compare = 0;
461 
462         while (low < high) {
463             mid     = (low + high) / 2;
464             compare = compare(mid);
465 
466             if (compare <= 0) {
467                 high = mid;
468             } else {
469                 low = mid + 1;
470             }
471         }
472 
473         return low;
474     }
475 
476     /**
477      * Returns the index of the lowest element > the given search target
478      * or count or -1 if target is found
479      * @return the index
480      */
481     private int binaryEmptySlotSearch() {
482 
483         int low     = 0;
484         int high    = count;
485         int mid     = 0;
486         int compare = 0;
487 
488         while (low < high) {
489             mid     = (low + high) / 2;
490             compare = compare(mid);
491 
492             if (compare < 0) {
493                 high = mid;
494             } else if (compare > 0) {
495                 low = mid + 1;
496             } else {
497                 return -1;
498             }
499         }
500 
501         return low;
502     }
503 
504     private synchronized void fastQuickSort() {
505 
506         quickSort(0, count - 1);
507         insertionSort(0, count - 1);
508 
509         sorted = true;
510     }
511 
512     private void quickSort(int l, int r) {
513 
514         int M = 4;
515         int i;
516         int j;
517         int v;
518 
519         if ((r - l) > M) {
520             i = (r + l) / 2;
521 
522             if (lessThan(i, l)) {
523                 swap(l, i);    // Tri-Median Methode!
524             }
525 
526             if (lessThan(r, l)) {
527                 swap(l, r);
528             }
529 
530             if (lessThan(r, i)) {
531                 swap(i, r);
532             }
533 
534             j = r - 1;
535 
536             swap(i, j);
537 
538             i = l;
539             v = j;
540 
541             for (;;) {
542                 while (lessThan(++i, v)) {}
543 
544                 while (lessThan(v, --j)) {}
545 
546                 if (j < i) {
547                     break;
548                 }
549 
550                 swap(i, j);
551             }
552 
553             swap(i, r - 1);
554             quickSort(l, j);
555             quickSort(i + 1, r);
556         }
557     }
558 
559     private void insertionSort(int lo0, int hi0) {
560 
561         int i;
562         int j;
563 
564         for (i = lo0 + 1; i <= hi0; i++) {
565             j = i;
566 
567             while ((j > lo0) && lessThan(i, j - 1)) {
568                 j--;
569             }
570 
571             if (i != j) {
572                 moveAndInsertRow(i, j);
573             }
574         }
575     }
576 
577     private void moveAndInsertRow(int i, int j) {
578 
579         int col1 = keys[i];
580         int col2 = values[i];
581 
582         moveRows(j, j + 1, i - j);
583 
584         keys[j]   = col1;
585         values[j] = col2;
586     }
587 
588     private void doubleCapacity() {
589 
590         keys     = (int[]) ArrayUtil.resizeArray(keys, capacity * 2);
591         values   = (int[]) ArrayUtil.resizeArray(values, capacity * 2);
592         capacity *= 2;
593     }
594 
595     private void swap(int i1, int i2) {
596 
597         int col1 = keys[i1];
598         int col2 = values[i1];
599 
600         keys[i1]   = keys[i2];
601         values[i1] = values[i2];
602         keys[i2]   = col1;
603         values[i2] = col2;
604     }
605 
606     private void moveRows(int fromIndex, int toIndex, int rows) {
607         System.arraycopy(keys, fromIndex, keys, toIndex, rows);
608         System.arraycopy(values, fromIndex, values, toIndex, rows);
609     }
610 
611     public void removeRange(int start, int limit) {
612 
613         moveRows(limit, start, count - limit);
614 
615         count -= (limit - start);
616     }
617 
618     public void removeAll() {
619 
620         hasChanged = true;
621 
622         ArrayUtil.clearArray(ArrayUtil.CLASS_CODE_INT, keys, 0, count);
623         ArrayUtil.clearArray(ArrayUtil.CLASS_CODE_INT, values, 0, count);
624 
625         count = 0;
626     }
627 
628     /**
629      * Check if targeted column value in the row indexed i is less than the
630      * search target object.
631      * @param i the index
632      * @return -1, 0 or +1
633      */
634     private int compare(int i) {
635 
636         if (sortOnValues) {
637             if (targetSearchValue > values[i]) {
638                 return 1;
639             } else if (targetSearchValue < values[i]) {
640                 return -1;
641             }
642         } else {
643             if (targetSearchValue > keys[i]) {
644                 return 1;
645             } else if (targetSearchValue < keys[i]) {
646                 return -1;
647             }
648         }
649 
650         return 0;
651     }
652 
653     public final synchronized void remove(int position) {
654 
655         hasChanged = true;
656 
657         moveRows(position + 1, position, count - position - 1);
658 
659         count--;
660 
661         keys[count]   = 0;
662         values[count] = 0;
663     }
664 
665     /**
666      * Check if row indexed i is less than row indexed j
667      * @param i the first index
668      * @param j the second index
669      * @return true or false
670      */
671     private boolean lessThan(int i, int j) {
672 
673         if (sortOnValues) {
674             if (values[i] < values[j]) {
675                 return true;
676             }
677         } else {
678             if (keys[i] < keys[j]) {
679                 return true;
680             }
681         }
682 
683         return false;
684     }
685 }
686
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags