BlockIntegerList


1   /**
2    * com.mckoi.util.BlockIntegerList  01 Jul 2000
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 AbstractBlockIntegerList that stores all int values in
31   * blocks that are entirely stored in main memory.  This type of structure
32   * is useful for large in-memory lists in which add/remove performance must
33   * be fast.
34   *
35   * @author Tobias Downer
36   */
37  
38  public class BlockIntegerList extends AbstractBlockIntegerList {
39  
40    /**
41     * Constructs the list.
42     */
43    public BlockIntegerList() {
44      super();
45    }
46  
47    public BlockIntegerList(IntegerVector ivec) {
48      super(ivec);
49    }
50  
51    /**
52     * Copies the information from the given BlockIntegerList into a new
53     * object and performs a deep clone of the information in this container.
54     */
55    public BlockIntegerList(IntegerListInterface i_list) {
56      super(i_list);
57    }
58  
59    // ---------- Block operations ----------
60  
61    /**
62     * Creates a new ListBlock to fill with ints.
63     */
64    protected IntegerListBlockInterface newListBlock() {
65      return new IntArrayListBlock(512);     // (default block size is 512)
66    }
67  
68    /**
69     * Called when the class decides this ListBlock is no longer needed.
70     * Provided as an event for derived classes to intercept.
71     */
72    protected void deleteListBlock(IntegerListBlockInterface list_block) {
73    }
74  
75    // ---------- Inner classes ----------
76  
77    /**
78     * The block that contains the actual int values of the list.  This is
79     * made public because it may be useful to derive from this class.
80     */
81    public static class IntArrayListBlock extends IntegerListBlockInterface {
82  
83      /**
84       * The array of int's stored in this block.
85       */
86      protected int[] array;
87  
88      /**
89       * The number of block entries in this list.
90       */
91      protected int count;
92  
93      /**
94       * Blank protected constructor.
95       */
96      protected IntArrayListBlock() {
97        super();
98      }
99  
100     /**
101      * Constructs the block to a specific size.
102      */
103     public IntArrayListBlock(int block_size) {
104       this();
105       array = new int[block_size];
106       count = 0;
107     }
108 
109     /**
110      * Returns the int[] array for this block.  If 'immutable' is true then
111      * the array object is guarenteed to not be mutated.
112      */
113     protected int[] getArray(boolean immutable) {
114       return array;
115     }
116 
117     /**
118      * Returns the count of int's in this block.
119      */
120     protected int getArrayLength() {
121       return array.length;
122     }
123 
124 //    /**
125 //     * Called just before the array is modified in a block mutation operation.
126 //     * This is intended to be overwritten to perform advanced array reuse
127 //     * schemes for cached objects.
128 //     * <p>
129 //     * If the block is immutable this method should make it mutable.
130 //     */
131 //    protected int[] prepareMutate() {
132 //      return array;
133 //    }
134 
135     /**
136      * Returns the number of entries in this block.
137      */
138     public final int size() {
139       return count;
140     }
141 
142     /**
143      * Returns true if the block is full.
144      */
145     public final boolean isFull() {
146       return count >= getArrayLength();
147     }
148 
149     /**
150      * Returns true if the block is empty.
151      */
152     public final boolean isEmpty() {
153       return count <= 0;
154     }
155 
156     /**
157      * Returns true if the block has enough room to fill with the given number
158      * of integers.
159      */
160     public final boolean canContain(int number) {
161       return count + number + 1 < getArrayLength();
162     }
163 
164     /**
165      * The top int in the list.
166      */
167     public int topInt() {
168       return getArray(true)[count - 1];
169     }
170 
171     /**
172      * The bottom int in the list.
173      */
174     public int bottomInt() {
175       if (count > 0) {
176         return getArray(true)[0];
177       }
178       throw new Error  ("no bottom integer.");
179     }
180 
181     /**
182      * Returns the int at the given position in the array.
183      */
184     public final int intAt(int pos) {
185       return getArray(true)[pos];
186     }
187 
188     /**
189      * Adds an int to the block.
190      */
191     public final void addInt(int val) {
192       has_changed = true;
193       int[] arr = getArray(false);
194       arr[count] = val;
195       ++count;
196     }
197 
198     /**
199      * Removes an Int from the specified position in the block.
200      */
201     public final int removeIntAt(int pos) {
202       has_changed = true;
203       int[] arr = getArray(false);
204       int val = arr[pos];
205 //      System.out.println("[" + (pos + 1) + ", " + pos + ", " + (count - pos) + "]");
206       System.arraycopy(array, pos + 1, arr, pos, (count - pos));
207       --count;
208       return val;
209     }
210 
211     /**
212      * Inserts an int at the given position.
213      */
214     public final void insertIntAt(int val, int pos) {
215       has_changed = true;
216       int[] arr = getArray(false);
217       System.arraycopy(array, pos, arr, pos + 1, (count - pos));
218       ++count;
219       arr[pos] = val;
220     }
221 
222     /**
223      * Sets an int at the given position, overwriting anything that was
224      * previously there.  It returns the value that was previously at the
225      * element.
226      */
227     public final int setIntAt(int val, int pos) {
228       has_changed = true;
229       int[] arr = getArray(false);
230       int old = arr[pos];
231       arr[pos] = val;
232       return old;
233     }
234 
235     /**
236      * Moves a set of values from the end of this block and inserts it into the
237      * given block at the destination index specified.  Assumes the
238      * destination block has enough room to store the set.
239      */
240     public final void moveTo(IntegerListBlockInterface dest_block,
241                              int dest_index, int length) {
242       IntArrayListBlock block = (IntArrayListBlock) dest_block;
243 
244       int[] arr = getArray(false);
245       int[] dest_arr = block.getArray(false);
246 
247       // Make room in the destination block
248       int destb_size = block.size();
249       if (destb_size > 0) {
250         System.arraycopy(dest_arr, 0,
251                          dest_arr, length, destb_size);
252       }
253       // Copy from this block into the destination block.
254       System.arraycopy(arr, count - length, dest_arr, 0, length);
255       // Alter size of destination and source block.
256       block.count += length;
257       count -= length;
258       // Mark both blocks as changed
259       has_changed = true;
260       block.has_changed = true;
261     }
262 
263     /**
264      * Copies all the data from this block into the given destination block.
265      */
266     public final void copyTo(IntegerListBlockInterface dest_block) {
267       IntArrayListBlock block = (IntArrayListBlock) dest_block;
268       int[] dest_arr = block.getArray(false);
269       System.arraycopy(getArray(true), 0, dest_arr, 0, count);
270       block.count = count;
271       block.has_changed = true;
272     }
273 
274     /**
275      * Copies all the data from this block into the given int[] array.  Returns
276      * the number of 'int' values copied.
277      */
278     public final int copyTo(int[] to, int offset) {
279       System.arraycopy(getArray(true), 0, to, offset, count);
280       return count;
281     }
282 
283     /**
284      * Clears the object to be re-used.
285      */
286     public final void clear() {
287       has_changed = true;
288       count = 0;
289     }
290 
291     /**
292      * Performs an iterative search through the int values in the list.
293      * If it's found the index of the value is returned, else it returns
294      * -1.
295      */
296     public int iterativeSearch(int val) {
297       int[] arr = getArray(true);
298       for (int i = count - 1; i >= 0; --i) {
299         if (arr[i] == val) {
300           return i;
301         }
302       }
303       return -1;
304     }
305 
306     /**
307      * Performs an iterative search from the given position to the end of
308      * the list in the block.
309      * If it's found the index of the value is returned, else it returns
310      * -1.
311      */
312     public int iterativeSearch(int val, int position) {
313       int[] arr = getArray(true);
314       for (int i = position; i < count; ++i) {
315         if (arr[i] == val) {
316           return i;
317         }
318       }
319       return -1;
320     }
321 
322 
323 
324     // ---------- Sort algorithms ----------
325 
326     /**
327      * Considers each int a reference to another structure, and the block
328      * sorted by these structures.  The method performs a binary search.
329      */
330     public final int binarySearch(Object   key, IndexComparator c) {
331       int[] arr = getArray(true);
332       int low = 0;
333       int high = count - 1;
334 
335       while (low <= high) {
336         int mid = (low + high) / 2;
337         int cmp = c.compare(arr[mid], key);
338 
339         if (cmp < 0)
340           low = mid + 1;
341         else if (cmp > 0)
342           high = mid - 1;
343         else
344           return mid; // key found
345       }
346       return -(low + 1);  // key not found.
347     }
348 
349 
350     /**
351      * Considers each int a reference to another structure, and the block
352      * sorted by these structures.  Finds the first index in the block that
353      * equals the given key.
354      */
355     public final int searchFirst(Object   key, IndexComparator c) {
356       int[] arr = getArray(true);
357       int low = 0;
358       int high = count - 1;
359 
360       while (low <= high) {
361 
362         if (high - low <= 2) {
363           for (int i = low; i <= high; ++i) {
364             int cmp = c.compare(arr[i], key);
365             if (cmp == 0) {
366               return i;
367             }
368             else if (cmp > 0) {
369               return -(i + 1);
370             }
371           }
372           return -(high + 2);
373         }
374 
375         int mid = (low + high) / 2;
376         int cmp = c.compare(arr[mid], key);
377 
378         if (cmp < 0) {
379           low = mid + 1;
380         }
381         else if (cmp > 0) {
382           high = mid - 1;
383         }
384         else {
385           high = mid;
386         }
387       }
388       return -(low + 1);  // key not found.
389     }
390 
391     /**
392      * Considers each int a reference to another structure, and the block
393      * sorted by these structures.  Finds the first index in the block that
394      * equals the given key.
395      */
396     public final int searchLast(Object   key, IndexComparator c) {
397       int[] arr = getArray(true);
398       int low = 0;
399       int high = count - 1;
400 
401       while (low <= high) {
402 
403         if (high - low <= 2) {
404           for (int i = high; i >= low; --i) {
405             int cmp = c.compare(arr[i], key);
406             if (cmp == 0) {
407               return i;
408             }
409             else if (cmp < 0) {
410               return -(i + 2);
411             }
412           }
413           return -(low + 1);
414         }
415 
416         int mid = (low + high) / 2;
417         int cmp = c.compare(arr[mid], key);
418 
419         if (cmp < 0) {
420           low = mid + 1;
421         }
422         else if (cmp > 0) {
423           high = mid - 1;
424         }
425         else {
426           low = mid;
427         }
428       }
429       return -(low + 1);  // key not found.
430     }
431 
432     /**
433      * Assuming a sorted block, finds the first index in the block that
434      * equals the given value.
435      */
436     public final int searchFirst(int val) {
437       int[] arr = getArray(true);
438       int low = 0;
439       int high = count - 1;
440 
441       while (low <= high) {
442 
443         if (high - low <= 2) {
444           for (int i = low; i <= high; ++i) {
445             if (arr[i] == val) {
446               return i;
447             }
448             else if (arr[i] > val) {
449               return -(i + 1);
450             }
451           }
452           return -(high + 2);
453         }
454 
455         int mid = (low + high) / 2;
456 
457         if (arr[mid] < val) {
458           low = mid + 1;
459         }
460         else if (arr[mid] > val) {
461           high = mid - 1;
462         }
463         else {
464           high = mid;
465         }
466       }
467       return -(low + 1);  // key not found.
468     }
469 
470     /**
471      * Assuming a sorted block, finds the first index in the block that
472      * equals the given value.
473      */
474     public final int searchLast(int val) {
475       int[] arr = getArray(true);
476       int low = 0;
477       int high = count - 1;
478 
479       while (low <= high) {
480 
481         if (high - low <= 2) {
482           for (int i = high; i >= low; --i) {
483             if (arr[i] == val) {
484               return i;
485             }
486             else if (arr[i] < val) {
487               return -(i + 2);
488             }
489           }
490           return -(low + 1);
491         }
492 
493         int mid = (low + high) / 2;
494 
495         if (arr[mid] < val) {
496           low = mid + 1;
497         }
498         else if (arr[mid] > val) {
499           high = mid - 1;
500         }
501         else {
502           low = mid;
503         }
504       }
505       return -(low + 1);  // key not found.
506     }
507 
508 
509 
510 
511     /**
512      * Converts the block into a String.
513      */
514     public String   toString() {
515       int[] arr = getArray(true);
516       StringBuffer   buf = new StringBuffer  ();
517       buf.append("( VALUES: " + count + " ) ");
518       for (int i = 0; i < count; ++i) {
519         buf.append(arr[i]);
520         buf.append(", ");
521       }
522       return new String  (buf);
523     }
524 
525   }
526 
527 }
528
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags