001: /**
002: * com.mckoi.util.BlockIntegerList 01 Jul 2000
003: *
004: * Mckoi SQL Database ( http://www.mckoi.com/database )
005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * Version 2 as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014: * GNU General Public License Version 2 for more details.
015: *
016: * You should have received a copy of the GNU General Public License
017: * Version 2 along with this program; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
019: *
020: * Change Log:
021: *
022: *
023: */package com.mckoi.util;
024:
025: import java.util.ArrayList;
026:
027: /**
028: * An implementation of AbstractBlockIntegerList that stores all int values in
029: * blocks that are entirely stored in main memory. This type of structure
030: * is useful for large in-memory lists in which add/remove performance must
031: * be fast.
032: *
033: * @author Tobias Downer
034: */
035:
036: public class BlockIntegerList extends AbstractBlockIntegerList {
037:
038: /**
039: * Constructs the list.
040: */
041: public BlockIntegerList() {
042: super ();
043: }
044:
045: public BlockIntegerList(IntegerVector ivec) {
046: super (ivec);
047: }
048:
049: /**
050: * Copies the information from the given BlockIntegerList into a new
051: * object and performs a deep clone of the information in this container.
052: */
053: public BlockIntegerList(IntegerListInterface i_list) {
054: super (i_list);
055: }
056:
057: // ---------- Block operations ----------
058:
059: /**
060: * Creates a new ListBlock to fill with ints.
061: */
062: protected IntegerListBlockInterface newListBlock() {
063: return new IntArrayListBlock(512); // (default block size is 512)
064: }
065:
066: /**
067: * Called when the class decides this ListBlock is no longer needed.
068: * Provided as an event for derived classes to intercept.
069: */
070: protected void deleteListBlock(IntegerListBlockInterface list_block) {
071: }
072:
073: // ---------- Inner classes ----------
074:
075: /**
076: * The block that contains the actual int values of the list. This is
077: * made public because it may be useful to derive from this class.
078: */
079: public static class IntArrayListBlock extends
080: IntegerListBlockInterface {
081:
082: /**
083: * The array of int's stored in this block.
084: */
085: protected int[] array;
086:
087: /**
088: * The number of block entries in this list.
089: */
090: protected int count;
091:
092: /**
093: * Blank protected constructor.
094: */
095: protected IntArrayListBlock() {
096: super ();
097: }
098:
099: /**
100: * Constructs the block to a specific size.
101: */
102: public IntArrayListBlock(int block_size) {
103: this ();
104: array = new int[block_size];
105: count = 0;
106: }
107:
108: /**
109: * Returns the int[] array for this block. If 'immutable' is true then
110: * the array object is guarenteed to not be mutated.
111: */
112: protected int[] getArray(boolean immutable) {
113: return array;
114: }
115:
116: /**
117: * Returns the count of int's in this block.
118: */
119: protected int getArrayLength() {
120: return array.length;
121: }
122:
123: // /**
124: // * Called just before the array is modified in a block mutation operation.
125: // * This is intended to be overwritten to perform advanced array reuse
126: // * schemes for cached objects.
127: // * <p>
128: // * If the block is immutable this method should make it mutable.
129: // */
130: // protected int[] prepareMutate() {
131: // return array;
132: // }
133:
134: /**
135: * Returns the number of entries in this block.
136: */
137: public final int size() {
138: return count;
139: }
140:
141: /**
142: * Returns true if the block is full.
143: */
144: public final boolean isFull() {
145: return count >= getArrayLength();
146: }
147:
148: /**
149: * Returns true if the block is empty.
150: */
151: public final boolean isEmpty() {
152: return count <= 0;
153: }
154:
155: /**
156: * Returns true if the block has enough room to fill with the given number
157: * of integers.
158: */
159: public final boolean canContain(int number) {
160: return count + number + 1 < getArrayLength();
161: }
162:
163: /**
164: * The top int in the list.
165: */
166: public int topInt() {
167: return getArray(true)[count - 1];
168: }
169:
170: /**
171: * The bottom int in the list.
172: */
173: public int bottomInt() {
174: if (count > 0) {
175: return getArray(true)[0];
176: }
177: throw new Error("no bottom integer.");
178: }
179:
180: /**
181: * Returns the int at the given position in the array.
182: */
183: public final int intAt(int pos) {
184: return getArray(true)[pos];
185: }
186:
187: /**
188: * Adds an int to the block.
189: */
190: public final void addInt(int val) {
191: has_changed = true;
192: int[] arr = getArray(false);
193: arr[count] = val;
194: ++count;
195: }
196:
197: /**
198: * Removes an Int from the specified position in the block.
199: */
200: public final int removeIntAt(int pos) {
201: has_changed = true;
202: int[] arr = getArray(false);
203: int val = arr[pos];
204: // System.out.println("[" + (pos + 1) + ", " + pos + ", " + (count - pos) + "]");
205: System.arraycopy(array, pos + 1, arr, pos, (count - pos));
206: --count;
207: return val;
208: }
209:
210: /**
211: * Inserts an int at the given position.
212: */
213: public final void insertIntAt(int val, int pos) {
214: has_changed = true;
215: int[] arr = getArray(false);
216: System.arraycopy(array, pos, arr, pos + 1, (count - pos));
217: ++count;
218: arr[pos] = val;
219: }
220:
221: /**
222: * Sets an int at the given position, overwriting anything that was
223: * previously there. It returns the value that was previously at the
224: * element.
225: */
226: public final int setIntAt(int val, int pos) {
227: has_changed = true;
228: int[] arr = getArray(false);
229: int old = arr[pos];
230: arr[pos] = val;
231: return old;
232: }
233:
234: /**
235: * Moves a set of values from the end of this block and inserts it into the
236: * given block at the destination index specified. Assumes the
237: * destination block has enough room to store the set.
238: */
239: public final void moveTo(IntegerListBlockInterface dest_block,
240: int dest_index, int length) {
241: IntArrayListBlock block = (IntArrayListBlock) dest_block;
242:
243: int[] arr = getArray(false);
244: int[] dest_arr = block.getArray(false);
245:
246: // Make room in the destination block
247: int destb_size = block.size();
248: if (destb_size > 0) {
249: System.arraycopy(dest_arr, 0, dest_arr, length,
250: destb_size);
251: }
252: // Copy from this block into the destination block.
253: System.arraycopy(arr, count - length, dest_arr, 0, length);
254: // Alter size of destination and source block.
255: block.count += length;
256: count -= length;
257: // Mark both blocks as changed
258: has_changed = true;
259: block.has_changed = true;
260: }
261:
262: /**
263: * Copies all the data from this block into the given destination block.
264: */
265: public final void copyTo(IntegerListBlockInterface dest_block) {
266: IntArrayListBlock block = (IntArrayListBlock) dest_block;
267: int[] dest_arr = block.getArray(false);
268: System.arraycopy(getArray(true), 0, dest_arr, 0, count);
269: block.count = count;
270: block.has_changed = true;
271: }
272:
273: /**
274: * Copies all the data from this block into the given int[] array. Returns
275: * the number of 'int' values copied.
276: */
277: public final int copyTo(int[] to, int offset) {
278: System.arraycopy(getArray(true), 0, to, offset, count);
279: return count;
280: }
281:
282: /**
283: * Clears the object to be re-used.
284: */
285: public final void clear() {
286: has_changed = true;
287: count = 0;
288: }
289:
290: /**
291: * Performs an iterative search through the int values in the list.
292: * If it's found the index of the value is returned, else it returns
293: * -1.
294: */
295: public int iterativeSearch(int val) {
296: int[] arr = getArray(true);
297: for (int i = count - 1; i >= 0; --i) {
298: if (arr[i] == val) {
299: return i;
300: }
301: }
302: return -1;
303: }
304:
305: /**
306: * Performs an iterative search from the given position to the end of
307: * the list in the block.
308: * If it's found the index of the value is returned, else it returns
309: * -1.
310: */
311: public int iterativeSearch(int val, int position) {
312: int[] arr = getArray(true);
313: for (int i = position; i < count; ++i) {
314: if (arr[i] == val) {
315: return i;
316: }
317: }
318: return -1;
319: }
320:
321: // ---------- Sort algorithms ----------
322:
323: /**
324: * Considers each int a reference to another structure, and the block
325: * sorted by these structures. The method performs a binary search.
326: */
327: public final int binarySearch(Object key, IndexComparator c) {
328: int[] arr = getArray(true);
329: int low = 0;
330: int high = count - 1;
331:
332: while (low <= high) {
333: int mid = (low + high) / 2;
334: int cmp = c.compare(arr[mid], key);
335:
336: if (cmp < 0)
337: low = mid + 1;
338: else if (cmp > 0)
339: high = mid - 1;
340: else
341: return mid; // key found
342: }
343: return -(low + 1); // key not found.
344: }
345:
346: /**
347: * Considers each int a reference to another structure, and the block
348: * sorted by these structures. Finds the first index in the block that
349: * equals the given key.
350: */
351: public final int searchFirst(Object key, IndexComparator c) {
352: int[] arr = getArray(true);
353: int low = 0;
354: int high = count - 1;
355:
356: while (low <= high) {
357:
358: if (high - low <= 2) {
359: for (int i = low; i <= high; ++i) {
360: int cmp = c.compare(arr[i], key);
361: if (cmp == 0) {
362: return i;
363: } else if (cmp > 0) {
364: return -(i + 1);
365: }
366: }
367: return -(high + 2);
368: }
369:
370: int mid = (low + high) / 2;
371: int cmp = c.compare(arr[mid], key);
372:
373: if (cmp < 0) {
374: low = mid + 1;
375: } else if (cmp > 0) {
376: high = mid - 1;
377: } else {
378: high = mid;
379: }
380: }
381: return -(low + 1); // key not found.
382: }
383:
384: /**
385: * Considers each int a reference to another structure, and the block
386: * sorted by these structures. Finds the first index in the block that
387: * equals the given key.
388: */
389: public final int searchLast(Object key, IndexComparator c) {
390: int[] arr = getArray(true);
391: int low = 0;
392: int high = count - 1;
393:
394: while (low <= high) {
395:
396: if (high - low <= 2) {
397: for (int i = high; i >= low; --i) {
398: int cmp = c.compare(arr[i], key);
399: if (cmp == 0) {
400: return i;
401: } else if (cmp < 0) {
402: return -(i + 2);
403: }
404: }
405: return -(low + 1);
406: }
407:
408: int mid = (low + high) / 2;
409: int cmp = c.compare(arr[mid], key);
410:
411: if (cmp < 0) {
412: low = mid + 1;
413: } else if (cmp > 0) {
414: high = mid - 1;
415: } else {
416: low = mid;
417: }
418: }
419: return -(low + 1); // key not found.
420: }
421:
422: /**
423: * Assuming a sorted block, finds the first index in the block that
424: * equals the given value.
425: */
426: public final int searchFirst(int val) {
427: int[] arr = getArray(true);
428: int low = 0;
429: int high = count - 1;
430:
431: while (low <= high) {
432:
433: if (high - low <= 2) {
434: for (int i = low; i <= high; ++i) {
435: if (arr[i] == val) {
436: return i;
437: } else if (arr[i] > val) {
438: return -(i + 1);
439: }
440: }
441: return -(high + 2);
442: }
443:
444: int mid = (low + high) / 2;
445:
446: if (arr[mid] < val) {
447: low = mid + 1;
448: } else if (arr[mid] > val) {
449: high = mid - 1;
450: } else {
451: high = mid;
452: }
453: }
454: return -(low + 1); // key not found.
455: }
456:
457: /**
458: * Assuming a sorted block, finds the first index in the block that
459: * equals the given value.
460: */
461: public final int searchLast(int val) {
462: int[] arr = getArray(true);
463: int low = 0;
464: int high = count - 1;
465:
466: while (low <= high) {
467:
468: if (high - low <= 2) {
469: for (int i = high; i >= low; --i) {
470: if (arr[i] == val) {
471: return i;
472: } else if (arr[i] < val) {
473: return -(i + 2);
474: }
475: }
476: return -(low + 1);
477: }
478:
479: int mid = (low + high) / 2;
480:
481: if (arr[mid] < val) {
482: low = mid + 1;
483: } else if (arr[mid] > val) {
484: high = mid - 1;
485: } else {
486: low = mid;
487: }
488: }
489: return -(low + 1); // key not found.
490: }
491:
492: /**
493: * Converts the block into a String.
494: */
495: public String toString() {
496: int[] arr = getArray(true);
497: StringBuffer buf = new StringBuffer();
498: buf.append("( VALUES: " + count + " ) ");
499: for (int i = 0; i < count; ++i) {
500: buf.append(arr[i]);
501: buf.append(", ");
502: }
503: return new String(buf);
504: }
505:
506: }
507:
508: }
|