Java > Open Source Codes > com > mckoi > util > AbstractBlockIntegerList


1 /**
2  * com.mckoi.util.AbstractBlockIntegerList 20 Sep 2001
3  *
4  * Mckoi SQL Database ( http://www.mckoi.com/database )
5  * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * Version 2 as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License Version 2 for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * Version 2 along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19  *
20  * Change Log:
21  *
22  *
23  */
24
25 package com.mckoi.util;
26
27 import java.util.ArrayList ;
28
29 /**
30  * An implementation of a list of integer values that are stored across
31  * an array of blocks. This allows for quicker insertion and deletion of
32  * integer values, including other memory saving benefits.
33  * <p>
34  * The class works as follows;<p>
35  * <ol>
36  * <li>The list can contain any number of 'int' values.
37  * <li>Each value is stored within a block of int's. A block is of finite
38  * size.
39  * <li>When a block becomes full, int values are moved around until enough
40  * space is free. This may be by inserting a new block or by shifting
41  * information from one block to another.
42  * <li>When a block becomes empty, it is removed.
43  * </ol>
44  * The benefits of this system are that inserts and deletes are fast even
45  * for very large lists. There are no megabyte sized arraycopys. Also,
46  * the object could be extended to a version that pages un-used blocks to disk
47  * thus saving precious system memory.
48  * <p>
49  * NOTE: The following methods are <b>NOT</b> optimal:
50  * get(pos), add(val, pos), remove(pos)
51  * <p>
52  * Specifically, they slow as 'pos' nears the end of large lists.
53  * <p>
54  * This type of structure is very fast for large sorted lists where values can
55  * be inserted at any position within the list. Care needs to be taken for
56  * lists where values are inserted and removed constantly, because
57  * fragmentation of the list blocks can occur. For example, adding 60,000
58  * random entries followed by removing 50,000 random entries will result in
59  * many only partially filled blocks. Since each block takes a constant
60  * amount of memory, this may not be acceptable.
61  *
62  * @author Tobias Downer
63  */
64
65 public abstract class AbstractBlockIntegerList
66                                             implements IntegerListInterface {
67
68 // /**
69 // * The size of each integer block. (multiply by 4 to get rough size how
70 // * much each block takes up in memory).
71 // */
72 // private static final int BLOCK_SIZE = 512; // (2k memory per block)
73
74   /**
75    * The list of blocks (objects in this list are of type
76    * 'IntegerListBlockInterface'.
77    */
78   protected ArrayList block_list = new ArrayList (10);
79
80   /**
81    * The total number of ints in the list.
82    */
83   private int count;
84
85 // /**
86 // * The size of the blocks.
87 // */
88 // protected int block_size;
89
90   /**
91    * If this is set to true, then the list is immutable (we are not permitted
92    * to insert or remove integers from the list).
93    */
94   private boolean immutable;
95
96
97   /**
98    * Constructs the list.
99    */
100   public AbstractBlockIntegerList() {
101     immutable = false;
102     count = 0;
103 // block_size = BLOCK_SIZE;
104
105 // insertListBlock(0, newListBlock());
106
107   }
108
109   /**
110    * Constructs the list from the given set of initial blocks.
111    */
112   public AbstractBlockIntegerList(IntegerListBlockInterface[] blocks) {
113     this();
114     for (int i = 0; i < blocks.length; ++i) {
115       block_list.add(blocks[i]);
116       count += blocks[i].size();
117     }
118   }
119
120   /**
121    * Constructs the list by copying the contents from an IntegerVector.
122    */
123   public AbstractBlockIntegerList(IntegerVector ivec) {
124     this();
125
126     int sz = ivec.size();
127     for (int i = 0; i < sz; ++i) {
128       add(ivec.intAt(i));
129     }
130   }
131
132   /**
133    * Copies the information from the given BlockIntegerList into a new
134    * object and performs a deep clone of the information in this container.
135    */
136   public AbstractBlockIntegerList(IntegerListInterface i_list) {
137     this();
138
139     if (i_list instanceof AbstractBlockIntegerList) {
140       // Optimization for when the input list is a BlockIntegerList
141 AbstractBlockIntegerList in_list = (AbstractBlockIntegerList) i_list;
142
143 // block_size = in_list.block_size;
144
145       ArrayList in_blocks = in_list.block_list;
146       int in_blocks_count = in_blocks.size();
147       // For each block in 'in_list'
148 for (int i = 0; i < in_blocks_count; ++i) {
149         // get the block.
150 IntegerListBlockInterface block =
151                                 (IntegerListBlockInterface) in_blocks.get(i);
152         // Insert a new block in this object.
153 IntegerListBlockInterface dest_block =
154                                 insertListBlock(i, newListBlock());
155         // Copy the contents of the source block to the new destination block.
156 block.copyTo(dest_block);
157       }
158
159       // Set the size of the list
160 count = i_list.size(); //count;
161
162     }
163     else {
164       // The case when IntegerListInterface type is not known
165 IntegerIterator i = i_list.iterator();
166       while (i.hasNext()) {
167         add(i.next());
168       }
169     }
170
171     // If the given list is immutable then set this list to immutable
172 if (i_list.isImmutable()) {
173       setImmutable();
174     }
175
176   }
177
178
179
180   // ---------- Block operations ----------
181
182   /**
183    * Creates a new ListBlock for the given implementation.
184    */
185   protected abstract IntegerListBlockInterface newListBlock();
186
187   /**
188    * Called when the class decides this ListBlock is no longer needed.
189    * Provided as an event for derived classes to intercept.
190    */
191   protected void deleteListBlock(IntegerListBlockInterface list_block) {
192   }
193
194   /**
195    * Copies the data from each block into the given int[] array. The int[]
196    * array must be big enough to fit all the data in this list.
197    */
198   final void copyToArray(int[] array, int offset, int length) {
199     if (array.length >= length && (offset + length) <= size()) {
200       for (int i = 0; i < block_list.size() ; ++i) {
201         IntegerListBlockInterface block =
202                                 (IntegerListBlockInterface) block_list.get(i);
203         offset += block.copyTo(array, offset);
204       }
205       return;
206     }
207     throw new Error ("Size mismatch.");
208   }
209
210
211   /**
212    * Inserts a ListBlock at the given block in the list of ListBlock's.
213    */
214   private final IntegerListBlockInterface
215             insertListBlock(int index, IntegerListBlockInterface list_block) {
216     block_list.add(index, list_block);
217
218     // Point to next in the list.
219 if (index + 1 < block_list.size()) {
220       IntegerListBlockInterface next_b =
221                        (IntegerListBlockInterface) block_list.get(index + 1);
222       list_block.next = next_b;
223       next_b.previous = list_block;
224     }
225     else {
226       list_block.next = null;
227     }
228
229     // Point to previous in the list.
230 if (index > 0) {
231       IntegerListBlockInterface previous_b =
232                        (IntegerListBlockInterface) block_list.get(index - 1);
233       list_block.previous = previous_b;
234       previous_b.next = list_block;
235     }
236     else {
237       list_block.previous = null;
238     }
239
240     return list_block;
241   }
242
243   /**
244    * Removes a IntegerListBlockInterface from the given index in the list of
245    * IntegerListBlockInterface's.
246    */
247   private final void removeListBlock(int index) {
248     // Alter linked list pointers.
249 IntegerListBlockInterface new_prev = null;
250     IntegerListBlockInterface new_next = null;
251     if (index + 1 < block_list.size()) {
252       new_next = (IntegerListBlockInterface) block_list.get(index + 1);
253     }
254     if (index > 0) {
255       new_prev = (IntegerListBlockInterface) block_list.get(index - 1);
256     }
257
258     if (new_prev != null) {
259       new_prev.next = new_next;
260     }
261     if (new_next != null) {
262       new_next.previous = new_prev;
263     }
264
265     IntegerListBlockInterface been_removed =
266                         (IntegerListBlockInterface) block_list.remove(index);
267     deleteListBlock(been_removed);
268   }
269
270   /**
271    * Inserts a value in the given block position in the list.
272    */
273   private final void insertIntoBlock(int val, int block_index,
274                              IntegerListBlockInterface block, int position) {
275     block.insertIntAt(val, position);
276     ++count;
277     // Is the block full?
278 if (block.isFull()) {
279       // We need to move half of the data out of this block into either the
280 // next block or create a new block to store it.
281
282       // The size that we going to zap out of this block.
283 int move_size = (block.size() / 7) - 1;
284
285       // The block to move half the data from this block.
286 IntegerListBlockInterface move_to;
287       // Is there a next block?
288 if (block_index < block_list.size() - 1) {
289         IntegerListBlockInterface next_b =
290                  (IntegerListBlockInterface) block_list.get(block_index + 1);
291 // IntegerListBlockInterface next_b = block.next;
292 // if (next_b != null) {
293 // Yes, can this block contain half the values from this block?
294 if (next_b.canContain(move_size)) {
295           move_to = next_b;
296         }
297         else {
298           // Can't contain so insert a new block.
299 move_to = insertListBlock(block_index + 1, newListBlock());
300         }
301
302       }
303       else {
304         // No next block so create a new block
305 move_to = insertListBlock(block_index + 1, newListBlock());
306       }
307
308       // 'move_to' should be set to the block we are to use to move half the
309 // data from this block.
310 block.moveTo(move_to, 0, move_size);
311
312     }
313   }
314
315   /**
316    * Removes the value from the given position in the specified block. It
317    * returns the value that used to be at that position.
318    */
319   protected final int removeFromBlock(int block_index,
320                                       IntegerListBlockInterface block,
321                                       int position) {
322     int old_value = block.removeIntAt(position);
323     --count;
324     // If we have emptied out this block, then we should remove it from the
325 // list.
326 if (block.isEmpty() && block_list.size() > 1) {
327       removeListBlock(block_index);
328     }
329
330     return old_value;
331   }
332
333   /**
334    * Uses a binary search algorithm to quickly determine the index of the
335    * IntegerListBlockInterface within 'block_list' of the block that contains
336    * the given key value using the IndexComparator as a lookup comparator.
337    */
338   private final int findBlockContaining(Object key, IndexComparator c) {
339     if (count == 0) {
340       return -1;
341     }
342
343     int low = 0;
344     int high = block_list.size() - 1;
345
346     while (low <= high) {
347       int mid = (low + high) / 2;
348       IntegerListBlockInterface block =
349                              (IntegerListBlockInterface) block_list.get(mid);
350
351       // Is what we are searching for lower than the bottom value?
352 if (c.compare(block.bottomInt(), key) > 0) {
353         high = mid - 1;
354       }
355       // No, then is it greater than the highest value?
356 else if (c.compare(block.topInt(), key) < 0) {
357         low = mid + 1;
358       }
359       // Must be inside this block then!
360 else {
361         return mid;
362       }
363     }
364
365 // System.out.println("RETURNING: " + low);
366
367     return -(low + 1); // key not found.
368 }
369
370   /**
371    * Uses a binary search algorithm to quickly determine the index of the
372    * IntegerListBlockInterface within 'block_list' of the block that contains
373    * the given key value using the IndexComparator as a lookup comparator.
374    */
375   private final int findLastBlock(Object key, IndexComparator c) {
376     if (count == 0) {
377       return -1;
378     }
379
380     int low = 0;
381     int high = block_list.size() - 1;
382
383     while (low <= high) {
384
385       if (high - low <= 2) {
386         for (int i = high; i >= low; --i) {
387           IntegerListBlockInterface block =
388                               (IntegerListBlockInterface) block_list.get(i);
389           if (c.compare(block.bottomInt(), key) <= 0) {
390             if (c.compare(block.topInt(), key) >= 0) {
391               return i;
392             }
393             else {
394               return -(i + 1) - 1;
395             }
396           }
397         }
398         return -(low + 1);
399       }
400
401       int mid = (low + high) / 2;
402       IntegerListBlockInterface block =
403                             (IntegerListBlockInterface) block_list.get(mid);
404
405       // Is what we are searching for lower than the bottom value?
406 if (c.compare(block.bottomInt(), key) > 0) {
407         high = mid - 1;
408       }
409       // No, then is it greater than the highest value?
410 else if (c.compare(block.topInt(), key) < 0) {
411         low = mid + 1;
412       }
413       // Equal, so highest must be someplace between mid and high.
414 else {
415         low = mid;
416         if (low == high) {
417           return low;
418         }
419       }
420     }
421
422     return -(low + 1); // key not found.
423 }
424
425   /**
426    * Uses a binary search algorithm to quickly determine the index of the
427    * IntegerListBlockInterface within 'block_list' of the block that contains
428    * the given key value using the IndexComparator as a lookup comparator.
429    */
430   private final int findFirstBlock(Object key, IndexComparator c) {
431     if (count == 0) {
432       return -1;
433     }
434
435     int low = 0;
436     int high = block_list.size() - 1;
437
438     while (low <= high) {
439
440       if (high - low <= 2) {
441         for (int i = low; i <= high; ++i) {
442           IntegerListBlockInterface block =
443                                (IntegerListBlockInterface) block_list.get(i);
444           if (c.compare(block.topInt(), key) >= 0) {
445             if (c.compare(block.bottomInt(), key) <= 0) {
446               return i;
447             }
448             else {
449               return -(i + 1);
450             }
451           }
452         }
453         return -(high + 1) - 1;
454       }
455
456       int mid = (low + high) / 2;
457       IntegerListBlockInterface block =
458                             (IntegerListBlockInterface) block_list.get(mid);
459
460       // Is what we are searching for lower than the bottom value?
461 if (c.compare(block.bottomInt(), key) > 0) {
462         high = mid - 1;
463       }
464       // No, then is it greater than the highest value?
465 else if (c.compare(block.topInt(), key) < 0) {
466         low = mid + 1;
467       }
468       // Equal, so highest must be someplace between mid and high.
469 else {
470         high = mid;
471       }
472     }
473
474     return -(low + 1); // key not found.
475 }
476
477
478   /**
479    * Uses a binary search algorithm to quickly determine the index of the
480    * IntegerListBlockInterface within 'block_list' of the block that contains
481    * the given value.
482    */
483   private final int findFirstBlock(int val) {
484     if (count == 0) {
485       return -1;
486     }
487
488     int low = 0;
489     int high = block_list.size() - 1;
490
491     while (low <= high) {
492
493       if (high - low <= 2) {
494         for (int i = low; i <= high; ++i) {
495           IntegerListBlockInterface block =
496                                (IntegerListBlockInterface) block_list.get(i);
497           if (block.topInt() >= val) {
498             if (block.bottomInt() <= val) {
499               return i;
500             }
501             else {
502               return -(i + 1);
503             }
504           }
505         }
506         return -(high + 1) - 1;
507       }
508
509       int mid = (low + high) / 2;
510       IntegerListBlockInterface block =
511                             (IntegerListBlockInterface) block_list.get(mid);
512
513       // Is what we are searching for lower than the bottom value?
514 if (block.bottomInt() > val) {
515         high = mid - 1;
516       }
517       // No, then is it greater than the highest value?
518 else if (block.topInt() < val) {
519         low = mid + 1;
520       }
521       // Equal, so highest must be someplace between mid and high.
522 else {
523         high = mid;
524       }
525     }
526
527     return -(low + 1); // key not found.
528 }
529
530   /**
531    * Uses a binary search algorithm to quickly determine the index of the
532    * IntegerListBlockInterface within 'block_list' of the block that contains
533    * the given value.
534    */
535   private final int findLastBlock(int val) {
536     if (count == 0) {
537       return -1;
538     }
539
540     int low = 0;
541     int high = block_list.size() - 1;
542
543     while (low <= high) {
544
545       if (high - low <= 2) {
546         for (int i = high; i >= low; --i) {
547           IntegerListBlockInterface block =
548                               (IntegerListBlockInterface) block_list.get(i);
549           if (block.bottomInt() <= val) {
550             if (block.topInt() >= val) {
551               return i;
552             }
553             else {
554               return -(i + 1) - 1;
555             }
556           }
557         }
558         return -(low + 1);
559       }
560
561       int mid = (low + high) / 2;
562       IntegerListBlockInterface block =
563                             (IntegerListBlockInterface) block_list.get(mid);
564
565       // Is what we are searching for lower than the bottom value?
566 if (block.bottomInt() > val) {
567         high = mid - 1;
568       }
569       // No, then is it greater than the highest value?
570 else if (block.topInt() < val) {
571         low = mid + 1;
572       }
573       // Equal, so highest must be someplace between mid and high.
574 else {
575         low = mid;
576         if (low == high) {
577           return low;
578         }
579       }
580     }
581
582     return -(low + 1); // key not found.
583 }
584
585
586
587
588
589
590   /**
591    * Throws an error if the list is immutable. This is called before any
592    * mutable operations on the list. If the list is mutable and empty then
593    * an empty block is added to the list.
594    */
595   private void checkImmutable() {
596     if (immutable) {
597       throw new Error ("List is immutable.");
598     }
599     // HACK: We have a side effect of checking whether the list is immutable.
600 // If the block list doesn't contain any entries we add one here. This
601 // hack reduces the memory requirements.
602 else if (block_list.size() == 0) {
603       insertListBlock(0, newListBlock());
604     }
605   }
606
607   // ---------- Public methods ----------
608
609   /**
610    * Sets the list as immutable (we aren't allowed to change the contents).
611    */
612   public final void setImmutable() {
613     immutable = true;
614   }
615
616   /**
617    * Returns true if this interface is immutable.
618    */
619   public final boolean isImmutable() {
620     return immutable;
621   }
622
623
624   // ---------- Standard get/set/remove operations ----------
625 // NOTE: Some of these are not optimal.
626
627   /**
628    * The number of integers that are in the list.
629    */
630   public final int size() {
631     return count;
632   }
633
634   /**
635    * Returns the int at the given position in the list. NOTE: This is not
636    * a very fast routine. Certainly a lot slower than IntegerVector intAt.
637    */
638   public final int get(int pos) {
639     int size = block_list.size();
640     int start = 0;
641     for (int i = 0; i < size; ++i) {
642       IntegerListBlockInterface block =
643                               (IntegerListBlockInterface) block_list.get(i);
644       int bsize = block.size();
645       if (pos >= start && pos < start + bsize) {
646         return block.intAt(pos - start);
647       }
648       start += bsize;
649     }
650     throw new Error ("'pos' (" + pos + ") out of bounds.");
651   }
652
653   /**
654    * Adds an int at the given position in the list.
655    */
656   public final void add(int val, int pos) {
657     checkImmutable();
658
659     int size = block_list.size();
660     int start = 0;
661     for (int i = 0; i < size; ++i) {
662       Object ob = block_list.get(i);
663       IntegerListBlockInterface block = (IntegerListBlockInterface) ob;
664       int bsize = block.size();
665       if (pos >= start && pos <= start + bsize) {
666         insertIntoBlock(val, i, block, pos - start);
667         return;
668       }
669       start += bsize;
670     }
671     throw new Error ("'pos' (" + pos + ") out of bounds.");
672   }
673
674   /**
675    * Adds an int to the end of the list.
676    */
677   public final void add(int val) {
678     checkImmutable();
679
680     int size = block_list.size();
681     IntegerListBlockInterface block =
682                        (IntegerListBlockInterface) block_list.get(size - 1);
683     insertIntoBlock(val, size - 1, block, block.size());
684   }
685
686   /**
687    * Removes an int from the given position in the list. Returns the value
688    * that used to be at that position.
689    */
690   public final int remove(int pos) {
691     checkImmutable();
692
693     int size = block_list.size();
694     int start = 0;
695     for (int i = 0; i < size; ++i) {
696       IntegerListBlockInterface block =
697                               (IntegerListBlockInterface) block_list.get(i);
698       int bsize = block.size();
699       if (pos >= start && pos <= start + bsize) {
700         return removeFromBlock(i, block, pos - start);
701       }
702       start += bsize;
703     }
704     throw new Error ("'pos' (" + pos + ") out of bounds.");
705   }
706
707   // ---------- Fast methods ----------
708
709   /**
710    * Assuming the list is sorted, this performs a binary search and returns
711    * true if the value is found, otherwise returns false.
712    * <p>
713    * We must supply a 'IndexComparator' for how the list is sorted.
714    */
715   public final boolean contains(int val) {
716     int block_num = findLastBlock(val);
717
718     if (block_num < 0) {
719       // We didn't find in the list, so return false.
720 return false;
721     }
722
723     // We got a block, so find out if it's in the block or not.
724 IntegerListBlockInterface block =
725                       (IntegerListBlockInterface) block_list.get(block_num);
726
727     // Find, if not there then return false.
728 int sr = block.searchLast(val);
729     return sr >= 0;
730
731   }
732
733   /**
734    * Inserts plain 'int' values into the list in sorted order.
735    */
736   public final void insertSort(int val) {
737     checkImmutable();
738
739     int block_num = findLastBlock(val);
740
741     if (block_num < 0) {
742       // Not found a block,
743 // The block to insert the value,
744 block_num = (-(block_num + 1)) - 1;
745       if (block_num < 0) {
746         block_num = 0;
747       }
748     }
749
750     // We got a block, so find out if it's in the block or not.
751 IntegerListBlockInterface block =
752                       (IntegerListBlockInterface) block_list.get(block_num);
753
754     // The point to insert in the block,
755 int i = block.searchLast(val);
756     if (i < 0) {
757       i = -(i + 1);
758     }
759     else {
760       i = i + 1;
761       // NOTE: A block can never become totally full so it's always okay to
762 // skip one ahead.
763 }
764
765     // Insert value into the block,
766 insertIntoBlock(val, block_num, block, i);
767
768   }
769
770   /**
771    * Inserts plain 'int' value into the sorted position in the list only if
772    * it isn't already in the list. If the value is inserted it returns true,
773    * otherwise if the value wasn't inserted because it's already in the list,
774    * it returns false.
775    */
776   public final boolean uniqueInsertSort(int val) {
777     checkImmutable();
778
779     int block_num = findLastBlock(val);
780
781     if (block_num < 0) {
782       // Not found a block,
783 // The block to insert the value,
784 block_num = (-(block_num + 1)) - 1;
785       if (block_num < 0) {
786         block_num = 0;
787       }
788     }
789
790     // We got a block, so find out if it's in the block or not.
791 IntegerListBlockInterface block =
792                       (IntegerListBlockInterface) block_list.get(block_num);
793
794     // The point to insert in the block,
795 int i = block.searchLast(val);
796     if (i < 0) {
797       i = -(i + 1);
798     }
799     else {
800       // This means we found the value in the given block, so return false.
801 return false;
802     }
803
804     // Insert value into the block,
805 insertIntoBlock(val, block_num, block, i);
806
807     // Value inserted so return true.
808 return true;
809
810   }
811
812   /**
813    * Removes a plain 'int' value from the sorted position in the list only if
814    * it's already in the list. If the value is removed it returns true,
815    * otherwise if the value wasn't removed because it couldn't be found in the
816    * list, it returns false.
817    */
818   public final boolean removeSort(int val) {
819     checkImmutable();
820
821     int block_num = findLastBlock(val);
822
823     if (block_num < 0) {
824       // Not found a block,
825 // The block to remove the value,
826 block_num = (-(block_num + 1)) - 1;
827       if (block_num < 0) {
828         block_num = 0;
829       }
830     }
831
832     // We got a block, so find out if it's in the block or not.
833 IntegerListBlockInterface block =
834                       (IntegerListBlockInterface) block_list.get(block_num);
835
836     // The point to remove the block,
837 int i = block.searchLast(val);
838     if (i < 0) {
839       // This means we can't found the value in the given block, so return
840 // false.
841 return false;
842     }
843
844     // Remove value into the block,
845 int val_removed = removeFromBlock(block_num, block, i);
846     if (val != val_removed) {
847       throw new Error ("Incorrect value removed.");
848     }
849
850     // Value removed so return true.
851 return true;
852
853   }
854
855
856
857
858
859
860
861
862
863
864   /**
865    * Assuming the list is sorted, this performs a binary search and returns
866    * true if the value is found, otherwise returns false.
867    * <p>
868    * We must supply a 'IndexComparator' for how the list is sorted.
869    */
870   public final boolean contains(Object key, IndexComparator c) {
871     int block_num = findBlockContaining(key, c);
872
873     if (block_num < 0) {
874       // We didn't find in the list, so return false.
875 return false;
876     }
877
878     // We got a block, so find out if it's in the block or not.
879 IntegerListBlockInterface block =
880                       (IntegerListBlockInterface) block_list.get(block_num);
881
882     // Find, if not there then return false.
883 int sr = block.binarySearch(key, c);
884     return sr >= 0;
885
886   }
887
888   /**
889    * Inserts the key/index pair into the list at the correct sorted position
890    * (determine by the IndexComparator). If the list already contains
891    * identical key then the value is put on the end of the set. This way,
892    * the sort is stable (the order of identical elements does not change).
893    */
894   public final void insertSort(Object key, int val, IndexComparator c) {
895     checkImmutable();
896
897     int block_num = findLastBlock(key, c);
898
899     if (block_num < 0) {
900       // Not found a block,
901 // The block to insert the value,
902 block_num = (-(block_num + 1)) - 1;
903       if (block_num < 0) {
904         block_num = 0;
905       }
906     }
907
908     // We got a block, so find out if it's in the block or not.
909 IntegerListBlockInterface block =
910                       (IntegerListBlockInterface) block_list.get(block_num);
911
912     // The point to insert in the block,
913 int i = block.searchLast(key, c);
914     if (i < 0) {
915       i = -(i + 1);
916     }
917     else {
918       i = i + 1;
919       // NOTE: A block can never become totally full so it's always okay to
920 // skip one ahead.
921 }
922
923     // Insert value into the block,
924 insertIntoBlock(val, block_num, block, i);
925
926   }
927
928   /**
929    * Removes the key/val pair from the list by first searching for it, and then
930    * removing it from the list.
931    * <p>
932    * NOTE: There will be a list scan (bad performance) for the erronious case
933    * when the key/val pair is not present in the list.
934    */
935   public final int removeSort(Object key, int val, IndexComparator c) {
936     checkImmutable();
937
938     // Find the range of blocks that the value is in.
939 final int orig_block_num = findFirstBlock(key, c);
940     int block_num = orig_block_num;
941     int l_block_num = block_list.size() - 1;
942 // int l_block_num = findLastBlock(key, c);
943
944     if (block_num < 0) {
945       // Not found in a block,
946 throw new Error ("Value (" + key + ") was not found in the list.");
947     }
948
949 // int i = -1;
950 IntegerListBlockInterface block =
951                       (IntegerListBlockInterface) block_list.get(block_num);
952 // int search_from = block.searchFirst(key, c);
953 int i = block.iterativeSearch(val);
954     while (i == -1) {
955       // If not found, go to next block
956 ++block_num;
957       if (block_num > l_block_num) {
958         throw new Error ("Value (" + key + ") was not found in the list.");
959       }
960       block = (IntegerListBlockInterface) block_list.get(block_num);
961       // Try and find the value within this block
962 i = block.iterativeSearch(val);
963     }
964
965 // int last_block_num = findLastBlock(key, c);
966 // if (last_block_num > orig_block_num) {
967 // double percent = (double) (block_num - orig_block_num) /
968 // (double) (last_block_num - orig_block_num);
969 // System.out.println("Block range: " + orig_block_num + " to " +
970 // last_block_num + " p: " + percent);
971 // }
972
973     // Remove value from the block,
974 return removeFromBlock(block_num, block, i);
975
976   }
977
978
979
980
981
982
983
984
985
986
987
988
989   /**
990    * Returns the index of the last value in this set that equals the given
991    * value.
992    */
993   public final int searchLast(Object key, IndexComparator c) {
994     int block_num = findLastBlock(key, c);
995     int sr;
996
997     if (block_num < 0) {
998       // Guarenteed not found in any blocks so return start of insert block
999 block_num = (-(block_num + 1)); // - 1;
1000 sr = -1;
1001    }
1002
1003    else {
1004      // We got a block, so find out if it's in the block or not.
1005 IntegerListBlockInterface block =
1006                      (IntegerListBlockInterface) block_list.get(block_num);
1007
1008      // Try and find it in the block,
1009 sr = block.searchLast(key, c);
1010    }
1011
1012    int offset = 0;
1013    for (int i = 0; i < block_num; ++i) {
1014      IntegerListBlockInterface block =
1015                              (IntegerListBlockInterface) block_list.get(i);
1016      offset += block.size();
1017    }
1018
1019    if (sr >= 0) {
1020      return offset + sr;
1021    }
1022    else {
1023      return -offset + sr;
1024    }
1025
1026  }
1027
1028  /**
1029   * Returns the index of the first value in this set that equals the given
1030   * value.
1031   */
1032  public final int searchFirst(Object key, IndexComparator c) {
1033    int block_num = findFirstBlock(key, c);
1034    int sr;
1035
1036    if (block_num < 0) {
1037      // Guarenteed not found in any blocks so return start of insert block
1038 block_num = (-(block_num + 1)); // - 1;
1039// System.out.println("BN (" + key + "): " + block_num);
1040 sr = -1;
1041    }
1042
1043    else {
1044      // We got a block, so find out if it's in the block or not.
1045 IntegerListBlockInterface block =
1046                      (IntegerListBlockInterface) block_list.get(block_num);
1047
1048      // Try and find it in the block,
1049 sr = block.searchFirst(key, c);
1050    }
1051
1052    int offset = 0;
1053    for (int i = 0; i < block_num; ++i) {
1054      IntegerListBlockInterface block =
1055                              (IntegerListBlockInterface) block_list.get(i);
1056      offset += block.size();
1057    }
1058
1059    if (sr >= 0) {
1060      return offset + sr;
1061    }
1062    else {
1063      return -offset + sr;
1064    }
1065
1066  }
1067
1068  // ---------- Iterator operations ----------
1069
1070
1071  /**
1072   * Our iterator that walks through the list.
1073   */
1074  private final class BILIterator implements IntegerIterator {
1075
1076
1077    private int start_offset;
1078    private int end_offset;
1079    private IntegerListBlockInterface current_block;
1080    private int current_block_size;
1081    private int block_index;
1082    private int block_offset;
1083    private int cur_offset;
1084
1085    public BILIterator(int start_offset, int end_offset) {
1086      this.start_offset = start_offset;
1087      this.end_offset = end_offset;
1088      cur_offset = start_offset - 1;
1089
1090      if (end_offset >= start_offset) {
1091        // Setup variables to 1 before the start
1092 setupVars(start_offset - 1);
1093      }
1094
1095    }
1096
1097    /**
1098     * Sets up the internal variables given an offset.
1099     */
1100    private void setupVars(int pos) {
1101      int size = block_list.size();
1102      int start = 0;
1103      for (block_index = 0; block_index < size; ++block_index) {
1104        IntegerListBlockInterface block =
1105                    (IntegerListBlockInterface) block_list.get(block_index);
1106        int bsize = block.size();
1107        if (pos < start + bsize) {
1108          block_offset = pos - start;
1109          if (block_offset < 0) {
1110            block_offset = -1;
1111          }
1112          current_block = block;
1113          current_block_size = bsize;
1114          return;
1115        }
1116        start += bsize;
1117      }
1118      throw new Error ("'pos' (" + pos + ") out of bounds.");
1119    }
1120
1121
1122    // ---------- Implemented from IntegerIterator ----------
1123
1124    public boolean hasNext() {
1125      return cur_offset < end_offset;
1126    }
1127
1128    public int next() {
1129      ++block_offset;
1130      ++cur_offset;
1131      if (block_offset >= current_block_size) {
1132        ++block_index;
1133        current_block =
1134                    (IntegerListBlockInterface) block_list.get(block_index);
1135// current_block = current_block.next;
1136 current_block_size = current_block.size();
1137        block_offset = 0;
1138      }
1139      return current_block.intAt(block_offset);
1140    }
1141
1142    public boolean hasPrevious() {
1143      return cur_offset > start_offset;
1144    }
1145
1146    private void walkBack() {
1147      --block_offset;
1148      --cur_offset;
1149      if (block_offset < 0) {
1150        if (block_index > 0) {
1151// if (current_block.previous != null) {
1152 --block_index;
1153          current_block =
1154                    (IntegerListBlockInterface) block_list.get(block_index);
1155// current_block = current_block.previous;
1156 current_block_size = current_block.size();
1157          block_offset = current_block.size() - 1;
1158        }
1159      }
1160    }
1161
1162    public int previous() {
1163      walkBack();
1164      return current_block.intAt(block_offset);
1165    }
1166
1167    public void remove() {
1168      checkImmutable();
1169
1170      // NOT ELEGANT: We check 'block_list' size to determine if the value
1171 // deletion caused blocks to be removed. If it did, we set up the
1172 // internal variables afresh with a call to 'setupVars'.
1173 int orig_block_count = block_list.size();
1174      removeFromBlock(block_index, current_block, block_offset);
1175
1176      // Did the number of blocks in the list change?
1177 if (orig_block_count == block_list.size()) {
1178        // HACK: Reduce the current cached block size
1179 --current_block_size;
1180        walkBack();
1181      }
1182      else {
1183        --cur_offset;
1184        setupVars(cur_offset);
1185      }
1186      --end_offset;
1187    }
1188
1189  }
1190
1191
1192  /**
1193   * Returns an IntegerIterator that will walk from the start offset
1194   * (inclusive) to the end offset (inclusive) of this list.
1195   * <p>
1196   * This iterator supports the 'remove' method.
1197   */
1198  public IntegerIterator iterator(int start_offset, int end_offset) {
1199    return new BILIterator(start_offset, end_offset);
1200  }
1201
1202  /**
1203   * Returns an IntegerIterator that will walk from the start to the end
1204   * this list.
1205   * <p>
1206   * This iterator supports the 'remove' method.
1207   */
1208  public IntegerIterator iterator() {
1209    return iterator(0, size() - 1);
1210  }
1211
1212
1213
1214
1215
1216
1217
1218  // ---------- Debugging ----------
1219
1220  public String toString() {
1221    StringBuffer buf = new StringBuffer ();
1222    buf.append("Blocks: " + block_list.size() + "\n");
1223    for (int i = 0; i < block_list.size(); ++i) {
1224      buf.append("Block (" + i + "): " + block_list.get(i).toString() + "\n");
1225    }
1226    return new String (buf);
1227  }
1228
1229  public void checkSorted(IndexComparator c) {
1230    IntegerIterator iterator = iterator(0, size() - 1);
1231    checkSorted(iterator, c);
1232  }
1233
1234  public static void checkSorted(IntegerIterator iterator, IndexComparator c) {
1235    if (iterator.hasNext()) {
1236      int last_index = iterator.next();
1237      while (iterator.hasNext()) {
1238        int cur = iterator.next();
1239        if (c.compare(cur, last_index) < 0) {
1240          throw new Error ("List not sorted!");
1241        }
1242        last_index = cur;
1243      }
1244    }
1245  }
1246
1247
1248}
1249

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags