001: /**
002: * com.mckoi.util.IntegerVector 10 Mar 1998
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: /**
026: * Similar to the Vector class, except this can only store integer values.
027: * <p>
028: * @author Tobias Downer
029: */
030:
031: public final class IntegerVector implements java.io.Serializable {
032:
033: /**
034: * The int array.
035: */
036: protected int[] list;
037:
038: /**
039: * The index of the last value of the array.
040: */
041: protected int index;
042:
043: /**
044: * The Constructors.
045: */
046: public IntegerVector() {
047: this (32);
048: }
049:
050: public IntegerVector(int initial_list_size) {
051: index = 0;
052: list = new int[initial_list_size];
053: }
054:
055: public IntegerVector(IntegerVector vec) {
056: if (vec != null && vec.list != null) {
057: list = new int[vec.list.length];
058: index = vec.index;
059: System.arraycopy(vec.list, 0, list, 0, index);
060: } else {
061: index = 0;
062: list = new int[0];
063: }
064: }
065:
066: public IntegerVector(IntegerListInterface i_list) {
067: this (i_list.size());
068: if (i_list instanceof AbstractBlockIntegerList) {
069: AbstractBlockIntegerList bilist = (AbstractBlockIntegerList) i_list;
070: int bill_size = bilist.size();
071: bilist.copyToArray(list, 0, bill_size);
072: index = bill_size;
073: } else {
074: IntegerIterator i = i_list.iterator();
075: // NOTE: We are guarenteed the size of the 'list' array matches the size
076: // of input list.
077: while (i.hasNext()) {
078: list[index] = i.next();
079: ++index;
080: }
081: }
082: }
083:
084: /**
085: * Ensures there's enough room to make a single addition to the list.
086: */
087: private void ensureCapacityForAddition() {
088: if (index >= list.length) {
089: int[] old_arr = list;
090:
091: int grow_size = old_arr.length + 1;
092: // Put a cap on the new size.
093: if (grow_size > 35000) {
094: grow_size = 35000;
095: }
096:
097: int new_size = old_arr.length + grow_size;
098: list = new int[new_size];
099: System.arraycopy(old_arr, 0, list, 0, index);
100: }
101: }
102:
103: /**
104: * Ensures there's enough room to make 'n' additions to the list.
105: */
106: private void ensureCapacityForAdditions(int n) {
107: int intended_size = index + n;
108: if (intended_size > list.length) {
109: int[] old_arr = list;
110:
111: int grow_size = old_arr.length + 1;
112: // Put a cap on the new size.
113: if (grow_size > 35000) {
114: grow_size = 35000;
115: }
116:
117: int new_size = Math.max(old_arr.length + grow_size,
118: intended_size);
119: list = new int[new_size];
120: System.arraycopy(old_arr, 0, list, 0, index);
121: }
122: }
123:
124: /**
125: * Adds an int to the vector.
126: */
127: public void addInt(int val) {
128: // if (list == null) {
129: // list = new int[64];
130: // }
131:
132: ensureCapacityForAddition();
133:
134: list[index] = val;
135: ++index;
136: }
137:
138: /**
139: * Removes an Int from the specified position in the list.
140: */
141: public void removeIntAt(int pos) {
142: --index;
143: System.arraycopy(list, pos + 1, list, pos, (index - pos));
144: }
145:
146: /**
147: * Removes the first Int found that matched the specified value.
148: */
149: public void removeInt(int val) {
150: int pos = indexOf(val);
151: if (pos == -1) {
152: throw new RuntimeException(
153: "Tried to remove none existant int.");
154: }
155: removeIntAt(pos);
156: }
157:
158: /**
159: * Crops the IntegerVector so it only contains values between start
160: * (inclusive) and end (exclusive). So;
161: * crop({ 4, 5, 4, 3, 9, 7 }, 0, 3)
162: * would return {4, 5, 4)
163: * and,
164: * crop({ 4, 5, 4, 3, 9, 7 }, 3, 4)
165: * would return {3}
166: */
167: public void crop(int start, int end) {
168: if (start < 0) {
169: throw new Error("Crop start < 0.");
170: } else if (start == 0) {
171: if (end > index) {
172: throw new Error("Crop end was past end.");
173: }
174: index = end;
175: } else {
176: if (start >= index) {
177: throw new Error("start >= index");
178: }
179: int length = (end - start);
180: if (length < 0) {
181: throw new Error("end - start < 0");
182: }
183: System.arraycopy(list, start, list, 0, length);
184: index = length;
185: }
186: }
187:
188: /**
189: * Inserts an int at the given position.
190: */
191: public void insertIntAt(int val, int pos) {
192: if (pos >= index) {
193: throw new ArrayIndexOutOfBoundsException(pos + " >= "
194: + index);
195: }
196:
197: // if (list == null) {
198: // list = new int[64];
199: // }
200:
201: ensureCapacityForAddition();
202: System.arraycopy(list, pos, list, pos + 1, (index - pos));
203: ++index;
204: list[pos] = val;
205: }
206:
207: /**
208: * Sets an int at the given position, overwriting anything that was
209: * previously there. It returns the value that was previously at the element.
210: */
211: public int setIntAt(int val, int pos) {
212: if (pos >= index) {
213: throw new ArrayIndexOutOfBoundsException(pos + " >= "
214: + index);
215: }
216:
217: int old = list[pos];
218: list[pos] = val;
219: return old;
220: }
221:
222: /**
223: * Places an int at the given position, overwriting anything that was
224: * previously there. It returns the value that was previously at the
225: * element. If 'pos' points to a place outside the bounds of the list then
226: * the list is expanded to include this value.
227: */
228: public int placeIntAt(int val, int pos) {
229: int llength = list.length;
230: if (pos >= list.length) {
231: ensureCapacityForAdditions((llength - index)
232: + (pos - llength) + 5);
233: }
234:
235: if (pos >= index) {
236: index = pos + 1;
237: }
238:
239: int old = list[pos];
240: list[pos] = val;
241: return old;
242: }
243:
244: /**
245: * Appends an IntegerVector to the end of the array. Returns this object.
246: */
247: public IntegerVector append(IntegerVector vec) {
248: if (vec != null) {
249: int size = vec.size();
250: // Make sure there's enough room for the new array
251: ensureCapacityForAdditions(size);
252:
253: // Copy the list into this vector.
254: System.arraycopy(vec.list, 0, list, index, size);
255: index += size;
256:
257: // int size = vec.size();
258: // for (int i = 0; i < size; ++i) {
259: // addInt(vec.intAt(i));
260: // }
261: }
262: return this ;
263: }
264:
265: /**
266: * Returns the Int at the given position.
267: */
268: public int intAt(int pos) {
269: if (pos >= index) {
270: throw new ArrayIndexOutOfBoundsException(pos + " >= "
271: + index);
272: }
273:
274: return list[pos];
275: }
276:
277: /**
278: * Returns the first index of the given row in the array, or -1 if not
279: * found.
280: */
281: public int indexOf(int val) {
282: for (int i = 0; i < index; ++i) {
283: if (list[i] == val) {
284: return i;
285: }
286: }
287: return -1;
288: }
289:
290: /**
291: * Returns true if the vector contains the given value.
292: */
293: public boolean contains(int val) {
294: return (indexOf(val) != -1);
295: }
296:
297: /**
298: * Returns the size of the vector.
299: */
300: public int getSize() {
301: return index;
302: }
303:
304: /**
305: * Returns the size of the vector.
306: */
307: public int size() {
308: return index;
309: }
310:
311: /**
312: * Converts the vector into an int[] array.
313: */
314: public int[] toIntArray() {
315: if (getSize() != 0) {
316: int[] out_list = new int[getSize()];
317: System.arraycopy(list, 0, out_list, 0, getSize());
318: return out_list;
319: }
320: return null;
321: }
322:
323: /**
324: * Clears the object to be re-used.
325: */
326: public void clear() {
327: index = 0;
328: }
329:
330: /**
331: * Converts the vector into a String.
332: */
333: public String toString() {
334: StringBuffer buf = new StringBuffer();
335: for (int i = 0; i < index; ++i) {
336: buf.append(list[i]);
337: buf.append(", ");
338: }
339: return new String(buf);
340: }
341:
342: /**
343: * Returns true if this vector is equal to the given vector.
344: */
345: public boolean equals(IntegerVector ivec) {
346: int dest_index = ivec.index;
347: if (index != dest_index) {
348: return false;
349: }
350: for (int i = 0; i < index; ++i) {
351: if (list[i] != ivec.list[i]) {
352: return false;
353: }
354: }
355: return true;
356: }
357:
358: /**
359: * Reverses all the list of integers. So integer[0] is swapped with
360: * integer[n - 1], integer[1] is swapped with integer[n - 2], etc where
361: * n is the size of the vector.
362: */
363: public void reverse() {
364: final int upper = index - 1;
365: final int bounds = index / 2;
366: int end_index, temp;
367:
368: // Swap ends and interate the two end pointers inwards.
369: // i = lower end
370: // upper - i = upper end
371:
372: for (int i = 0; i < bounds; ++i) {
373: end_index = upper - i;
374:
375: temp = list[i];
376: list[i] = list[end_index];
377: list[end_index] = temp;
378: }
379: }
380:
381: /**
382: * These methods are algorithms that can be used on the array, such as
383: * sorting and searching.
384: */
385:
386: /**
387: * Performs a quick sort on the array between the min and max bounds.
388: */
389: public final void quickSort(int min, int max) {
390: int left = min;
391: int right = max;
392:
393: if (max > min) {
394: int mid = list[(min + max) / 2];
395: while (left < right) {
396: while (left < max && list[left] < mid) {
397: ++left;
398: }
399: while (right > min && list[right] > mid) {
400: --right;
401: }
402: if (left <= right) {
403: if (left != right) {
404: int t = list[left];
405: list[left] = list[right];
406: list[right] = t;
407: }
408:
409: ++left;
410: --right;
411: }
412:
413: }
414:
415: if (min < right) {
416: quickSort(min, right);
417: }
418: if (left < max) {
419: quickSort(left, max);
420: }
421:
422: }
423: }
424:
425: /**
426: * Performs a quick sort on the entire vector.
427: */
428: public final void quickSort() {
429: quickSort(0, index - 1);
430: }
431:
432: /**
433: * This is a very quick search for a value given a sorted array. The search
434: * is performed between the lower and higher bounds of the array. If the
435: * requested value is not found, it returns the index where the value should
436: * be 'inserted' to maintain a sorted list.
437: */
438: public final int sortedIndexOf(int val, int lower, int higher) {
439:
440: if (lower >= higher) {
441: if (lower < index && val > list[lower]) {
442: return lower + 1;
443: } else {
444: return lower;
445: }
446: }
447:
448: int mid = (lower + higher) / 2;
449: int mid_val = list[mid];
450:
451: if (val == mid_val) {
452: return mid;
453: } else if (val < mid_val) {
454: return sortedIndexOf(val, lower, mid - 1);
455: } else {
456: return sortedIndexOf(val, mid + 1, higher);
457: }
458:
459: }
460:
461: /**
462: * Searches the entire sorted list for the given value and returns the index
463: * of it. If the value is not found, it returns the place in the list where
464: * the value should be insorted to maintain a sorted list.
465: */
466: public final int sortedIndexOf(int val) {
467: return sortedIndexOf(val, 0, index - 1);
468: }
469:
470: /**
471: * Given a sorted list, this will return the count of this value in the
472: * list. This uses a quick search algorithm so should be quite fast.
473: */
474: public final int sortedIntCount(int val) {
475: if (index == 0) {
476: return 0;
477: }
478:
479: int count = 0;
480: int size = index - 1;
481:
482: int i = sortedIndexOf(val, 0, size);
483: if (i > size) {
484: return 0;
485: }
486: int temp_i = i;
487:
488: while (temp_i >= 0 && list[temp_i] == val) {
489: ++count;
490: --temp_i;
491: }
492: temp_i = i + 1;
493: while (temp_i <= size && list[temp_i] == val) {
494: ++count;
495: ++temp_i;
496: }
497:
498: return count;
499:
500: }
501:
502: /**
503: * Test routine to check vector is sorted.
504: */
505: public boolean isSorted() {
506: int cur = Integer.MIN_VALUE; //-1000000;
507: for (int i = 0; i < index; ++i) {
508: int a = list[i];
509: if (a >= cur) {
510: cur = a;
511: } else {
512: return false;
513: }
514: }
515: return true;
516: }
517:
518: }
|