001: /*
002: This source file is part of Smyle, a database library.
003: For up-to-date information, see http://www.drjava.de/smyle
004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
005:
006: This library is free software; you can redistribute it and/or
007: modify it under the terms of the GNU Lesser General Public
008: License as published by the Free Software Foundation; either
009: version 2.1 of the License, or (at your option) any later version.
010:
011: This library 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 GNU
014: Lesser General Public License for more details.
015:
016: You should have received a copy of the GNU Lesser General Public
017: License along with this library; if not, write to the Free Software
018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: For full license text, see doc/license/lgpl.txt in this distribution
021: */
022:
023: package drjava.smyle.core;
024:
025: import java.util.*;
026: import org.artsProject.mcop.*;
027:
028: public class FastIntVector {
029: int blockSize = 32;
030: ArrayList<Block> blocks = new ArrayList<Block>();
031: int size;
032: int cacheIndex = -2, cacheI, cacheB;
033:
034: class Block {
035: int[] data = new int[blockSize];
036: int length = 0;
037:
038: void add(int i) {
039: data[length++] = i;
040: }
041:
042: void add(int index, int value) {
043: System.arraycopy(data, index, data, index + 1, length
044: - index);
045: data[index] = value;
046: ++length;
047: }
048:
049: int get(int index) {
050: return data[index];
051: }
052:
053: int[] data() {
054: int[] result = new int[length];
055: System.arraycopy(data, 0, result, 0, length);
056: return result;
057: }
058:
059: boolean full() {
060: return length >= blockSize;
061: }
062:
063: boolean overfull() {
064: return length > blockSize;
065: }
066:
067: boolean underfull() {
068: return length < blockSize / 2;
069: }
070:
071: void remove(int index) {
072: --length;
073: System.arraycopy(data, index + 1, data, index, length
074: - index);
075: }
076:
077: void set(int index, int value) {
078: data[index] = value;
079: }
080:
081: Block split() {
082: Block b = new Block();
083: int l = length / 2;
084: b.length = length - l;
085: System.arraycopy(data, l, b.data, 0, b.length);
086: length = l;
087:
088: // slim down overfat merged block
089: if (data.length > blockSize) {
090: int[] d = new int[blockSize];
091: System.arraycopy(data, 0, d, 0, length);
092: data = d;
093: }
094:
095: return b;
096: }
097:
098: void mergeWith(Block b) {
099: int l = length + b.length;
100: if (l > blockSize) {
101: int[] d = new int[l];
102: System.arraycopy(data, 0, d, 0, length);
103: data = d;
104: }
105: System.arraycopy(b.data, 0, data, length, b.length);
106: length = l;
107: }
108: }
109:
110: public FastIntVector(/*ChunkManager cm*/) {
111: blocks.add(new Block());
112: }
113:
114: public void read(Buffer b) {
115: int n = b.readLong();
116: for (int i = 0; i < n; i++)
117: add(b.readLong());
118: }
119:
120: public void marshal(Buffer buf) {
121: buf.writeLong(size);
122: for (int b = 0; b < blocks.size(); b++) {
123: Block block = blocks.get(b);
124: for (int i = 0; i < block.length; i++)
125: buf.writeLong(block.data[i]);
126: }
127: }
128:
129: public void setBlockSize(int entries) {
130: blockSize = entries;
131: }
132:
133: public void add(int index, int value) {
134: long n = findIndex(index);
135: int b = (int) n, ofs = (int) (n >> 32);
136: if (b == blocks.size()) {
137: --b;
138: ofs += blocks.get(blocks.size() - 1).length;
139: }
140: Block block = blocks.get(b);
141: if (block.full()) {
142: Block newBlock = block.split();
143: blocks.add(b + 1, newBlock);
144: if (ofs < block.length)
145: block.add(ofs, value);
146: else
147: newBlock.add(ofs - block.length, value);
148: } else
149: block.add(ofs, value);
150: ++size;
151: clearCache();
152: }
153:
154: public void set(int index, int value) {
155: long n = findIndex(index);
156: blocks.get((int) n).set((int) (n >> 32), value);
157: }
158:
159: public void add(int i) {
160: Block b = blocks.get(blocks.size() - 1);
161: if (b.full())
162: blocks.add(b = new Block());
163: b.add(i);
164: ++size;
165: clearCache();
166: }
167:
168: /** returns block number | (offset << 32) */
169: long findIndex(int index) {
170: // shortcut: end of vector
171: if (index == size)
172: return blocks.size();
173:
174: // hit on cached index
175: if (index == cacheIndex)
176: return cacheB | ((long) cacheI << 32);
177:
178: // hit on successor of cached index
179: if (index == cacheIndex + 1) {
180: ++cacheIndex;
181: if (++cacheI >= blocks.get(cacheB).length) {
182: ++cacheB;
183: cacheI = 0;
184: }
185: return cacheB | ((long) cacheI << 32);
186: }
187:
188: int b, n = 0;
189: for (b = 0; b < blocks.size(); b++) {
190: int nextN = n + blocks.get(b).length;
191: if (index < nextN) {
192: cacheIndex = index;
193: cacheB = b;
194: cacheI = index - n;
195: return cacheB | ((long) cacheI << 32);
196: }
197: n = nextN;
198: }
199:
200: return b;
201: }
202:
203: public int get(int index) {
204: // what a shitty way to return two ints...
205: long n = findIndex(index);
206: return blocks.get((int) n).get((int) (n >> 32));
207: }
208:
209: public int numBlocks() {
210: return blocks.size();
211: }
212:
213: public int[] getBlockData(int blockNr) {
214: return blocks.get(blockNr).data();
215: }
216:
217: public int indexOf(int value) {
218: int n = 0;
219: for (int b = 0; b < blocks.size(); b++) {
220: Block block = blocks.get(b);
221: int[] data = block.data;
222: for (int i = 0; i < block.length; i++)
223: if (data[i] == value)
224: return n + i;
225: n += block.length;
226: }
227: return -1;
228: }
229:
230: public boolean removeElement(int value) {
231: for (int b = 0; b < blocks.size(); b++) {
232: Block block = blocks.get(b);
233: int[] data = block.data;
234: for (int i = 0; i < block.length; i++) {
235: if (data[i] == value) {
236: remove(b, i);
237: return true;
238: }
239: }
240: }
241: return false;
242: }
243:
244: void remove(int b, int i) {
245: Block block = blocks.get(b);
246: block.remove(i);
247: --size;
248: clearCache();
249:
250: // handle underflow
251: if (block.underfull() && blocks.size() != 1) {
252: if (b != 0)
253: --b;
254: block = blocks.get(b);
255: block.mergeWith(blocks.get(b + 1));
256: blocks.remove(b + 1);
257: if (block.overfull())
258: blocks.add(b + 1, block.split());
259: }
260: }
261:
262: public void remove(int index) {
263: long n = findIndex(index);
264: remove((int) n, (int) (n >> 32));
265: }
266:
267: public int size() {
268: return size;
269: }
270:
271: class I implements IntIterator {
272: int b, i;
273: Block block = blocks.get(0);
274:
275: public boolean hasNext() {
276: return i < block.length;
277: }
278:
279: public int next() {
280: int result = block.get(i++);
281: if (i >= block.length && b < blocks.size() - 1) {
282: block = blocks.get(++b);
283: i = 0;
284: }
285: return result;
286: }
287: }
288:
289: public IntIterator iterator() {
290: return new I();
291: }
292:
293: public boolean isEmpty() {
294: return size == 0;
295: }
296:
297: public void clear() {
298: blocks.clear();
299: blocks.add(new Block());
300: size = 0;
301: clearCache();
302: }
303:
304: void clearCache() {
305: cacheIndex = -2;
306: }
307: }
|