001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.util;
007:
008: import java.util.Collection;
009: import java.util.Comparator;
010: import java.util.Iterator;
011:
012: import org.h2.constant.SysProperties;
013:
014: /**
015: * The object array is basically the same as ArrayList.
016: * It is a bit faster than ArrayList in some java versions.
017: */
018: public class ObjectArray {
019: private static final int SIZE_INIT = 4, SIZE_SHRINK = 256;
020:
021: private Object[] data;
022: private int size;
023:
024: public ObjectArray() {
025: this (SIZE_INIT);
026: }
027:
028: public ObjectArray(int size) {
029: data = new Object[size > 1 ? size : 1];
030: }
031:
032: public ObjectArray(Collection collection) {
033: // TODO lib: Collection should not be required
034: size = collection.size();
035: data = new Object[size];
036: Iterator it = collection.iterator();
037: for (int i = 0; i < size; i++) {
038: data[i] = it.next();
039: }
040: }
041:
042: private void throwException(int index) {
043: throw new ArrayIndexOutOfBoundsException("i=" + index
044: + " size=" + size);
045: }
046:
047: public void add(Object value) {
048: if (size >= data.length) {
049: ensureCapacity(size);
050: }
051: data[size++] = value;
052: }
053:
054: public Object get(int i) {
055: if (SysProperties.CHECK && i >= size) {
056: throwException(i);
057: }
058: return data[i];
059: }
060:
061: public Object remove(int i) {
062: // TODO performance: the app should (where possible)
063: // remove from end to start, to avoid O(n^2)
064: if (SysProperties.CHECK && i >= size) {
065: throwException(i);
066: }
067: Object value = data[i];
068: System.arraycopy(data, i + 1, data, i, size - i - 1);
069: size--;
070: data[size] = null;
071: // TODO optimization / lib: could shrink ObjectArray on element remove
072: return value;
073: }
074:
075: public void removeRange(int from, int to) {
076: if (SysProperties.CHECK && (to > size || from > to)) {
077: throw new ArrayIndexOutOfBoundsException("to=" + to
078: + " from=" + from + " size=" + size);
079: }
080: System.arraycopy(data, to, data, from, size - to);
081: size -= to - from;
082: for (int i = size + (to - from) - 1; i >= size; i--) {
083: data[i] = null;
084: }
085: }
086:
087: public void setSize(int i) {
088: ensureCapacity(i);
089: this .size = i;
090: }
091:
092: private void ensureCapacity(int i) {
093: while (i >= data.length) {
094: Object[] d = new Object[Math
095: .max(SIZE_INIT, data.length * 2)];
096: System.arraycopy(data, 0, d, 0, data.length);
097: data = d;
098: }
099: }
100:
101: public void add(int i, Object value) {
102: if (SysProperties.CHECK && i > size) {
103: throwException(i);
104: }
105: ensureCapacity(size);
106: if (i == size) {
107: add(value);
108: } else {
109: System.arraycopy(data, i, data, i + 1, size - i);
110: data[i] = value;
111: size++;
112: }
113: }
114:
115: public void set(int i, Object value) {
116: if (SysProperties.CHECK && i >= size) {
117: throwException(i);
118: }
119: data[i] = value;
120: }
121:
122: public int size() {
123: return size;
124: }
125:
126: public void toArray(Object[] array) {
127: for (int i = 0; i < size; i++) {
128: array[i] = data[i];
129: }
130: }
131:
132: public void clear() {
133: if (data.length > SIZE_SHRINK) {
134: data = new Object[SIZE_INIT];
135: } else {
136: for (int i = 0; i < size; i++) {
137: data[i] = null;
138: }
139: }
140: size = 0;
141: }
142:
143: public int indexOf(Object o) {
144: for (int i = 0; i < size; i++) {
145: if (data[i] == o) {
146: return i;
147: }
148: }
149: return -1;
150: }
151:
152: public void addAll(ObjectArray list) {
153: for (int i = 0; i < list.size; i++) {
154: add(list.data[i]);
155: }
156: }
157:
158: private void swap(int l, int r) {
159: Object t = data[r];
160: data[r] = data[l];
161: data[l] = t;
162: }
163:
164: public void sort(Comparator comp) {
165: sort(comp, 0, size - 1);
166: }
167:
168: private void sort(Comparator comp, int l, int r) {
169: // quicksort
170: int i, j;
171: while (r - l > 10) {
172: // randomized pivot to avoid worst case
173: i = RandomUtils.nextInt(r - l - 4) + l + 2;
174: if (comp.compare(get(l), get(r)) > 0) {
175: swap(l, r);
176: }
177: if (comp.compare(get(i), get(l)) < 0) {
178: swap(l, i);
179: } else if (comp.compare(get(i), get(r)) > 0) {
180: swap(i, r);
181: }
182: j = r - 1;
183: swap(i, j);
184: Object p = get(j);
185: i = l;
186: while (true) {
187: do {
188: ++i;
189: } while (comp.compare(get(i), p) < 0);
190: do {
191: --j;
192: } while (comp.compare(get(j), p) > 0);
193: if (i >= j) {
194: break;
195: }
196: swap(i, j);
197: }
198: swap(i, r - 1);
199: sort(comp, l, i - 1);
200: l = i + 1;
201: }
202: for (i = l + 1; i <= r; i++) {
203: Object t = get(i);
204: for (j = i - 1; j >= l && (comp.compare(get(j), t) > 0); j--) {
205: set(j + 1, get(j));
206: }
207: set(j + 1, t);
208: }
209: }
210:
211: // public void sortInsertion(Comparator comp) {
212: // for (int i = 1, j; i < size(); i++) {
213: // Object t = get(i);
214: // for (j = i - 1; j >= 0 && (comp.compare(get(j), t) < 0); j--) {
215: // set(j + 1, get(j));
216: // }
217: // set(j + 1, t);
218: // }
219: // }
220:
221: }
|