001: /*
002: * ComplexBitVector.java
003: *
004: * Copyright (C) 2003-2004 Peter Graves
005: * $Id: ComplexBitVector.java,v 1.9 2004/05/27 17:11:14 piso Exp $
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: * as published by the Free Software Foundation; either version 2
010: * of the License, or (at your option) any later version.
011: *
012: * This program is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
015: * GNU General Public License for more details.
016: *
017: * You should have received a copy of the GNU General Public License
018: * along with this program; if not, write to the Free Software
019: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
020: */
021:
022: package org.armedbear.lisp;
023:
024: public final class ComplexBitVector extends AbstractBitVector {
025: private int fillPointer = -1; // -1 indicates no fill pointer.
026: private boolean isDisplaced;
027:
028: // For displaced bit-vectors.
029: private AbstractArray array;
030: private int displacement;
031:
032: public ComplexBitVector(int capacity) throws ConditionThrowable {
033: this .capacity = capacity;
034: int size = capacity >>> 6;
035: if ((capacity & LONG_MASK) != 0)
036: ++size;
037: bits = new long[size];
038: }
039:
040: public ComplexBitVector(int capacity, AbstractArray array,
041: int displacement) {
042: this .capacity = capacity;
043: this .array = array;
044: this .displacement = displacement;
045: isDisplaced = true;
046: }
047:
048: public LispObject typeOf() {
049: return list2(Symbol.BIT_VECTOR, new Fixnum(capacity));
050: }
051:
052: public boolean hasFillPointer() {
053: return fillPointer >= 0;
054: }
055:
056: public int getFillPointer() {
057: return fillPointer;
058: }
059:
060: public void setFillPointer(int n) {
061: fillPointer = n;
062: }
063:
064: public void setFillPointer(LispObject obj)
065: throws ConditionThrowable {
066: if (obj == T)
067: fillPointer = capacity();
068: else {
069: int n = Fixnum.getValue(obj);
070: if (n > capacity()) {
071: StringBuffer sb = new StringBuffer(
072: "The new fill pointer (");
073: sb.append(n);
074: sb.append(") exceeds the capacity of the vector (");
075: sb.append(capacity());
076: sb.append(").");
077: signal(new LispError(sb.toString()));
078: } else if (n < 0) {
079: StringBuffer sb = new StringBuffer(
080: "The new fill pointer (");
081: sb.append(n);
082: sb.append(") is negative.");
083: signal(new LispError(sb.toString()));
084: } else
085: fillPointer = n;
086: }
087: }
088:
089: public LispObject arrayDisplacement() throws ConditionThrowable {
090: LispObject value1, value2;
091: if (array != null) {
092: value1 = array;
093: value2 = new Fixnum(displacement);
094: } else {
095: value1 = NIL;
096: value2 = Fixnum.ZERO;
097: }
098: return LispThread.currentThread().setValues(value1, value2);
099: }
100:
101: public int length() {
102: return fillPointer >= 0 ? fillPointer : capacity;
103: }
104:
105: public LispObject elt(int index) throws ConditionThrowable {
106: // The index < 0 case is checked in get().
107: if (index >= length())
108: badIndex(index, length());
109: return getRowMajor(index);
110: }
111:
112: public LispObject getRowMajor(int index) throws ConditionThrowable {
113: if (bits != null) {
114: if (index < 0 || index >= capacity)
115: badIndex(index, capacity);
116: int offset = index >> 6;
117: return (bits[offset] & (1L << index)) != 0 ? Fixnum.ONE
118: : Fixnum.ZERO;
119: } else
120: return array.getRowMajor(index + displacement);
121: }
122:
123: protected int getBit(int index) throws ConditionThrowable {
124: if (bits != null) {
125: int offset = index >> 6;
126: return (bits[offset] & (1L << index)) != 0 ? 1 : 0;
127: } else
128: return Fixnum.getValue(array.getRowMajor(index
129: + displacement));
130: }
131:
132: public void setRowMajor(int index, LispObject newValue)
133: throws ConditionThrowable {
134: if (index < 0 || index >= capacity)
135: badIndex(index, capacity);
136: try {
137: switch (((Fixnum) newValue).value) {
138: case 0:
139: if (bits != null) {
140: final int offset = index >> 6;
141: bits[offset] &= ~(1L << index);
142: } else
143: clearBit(index);
144: return;
145: case 1:
146: if (bits != null) {
147: final int offset = index >> 6;
148: bits[offset] |= 1L << index;
149: } else
150: setBit(index);
151: return;
152: }
153: } catch (ClassCastException e) {
154: // Fall through...
155: }
156: signal(new TypeError(newValue, Symbol.BIT));
157: }
158:
159: protected void setBit(int index) throws ConditionThrowable {
160: if (bits != null) {
161: int offset = index >> 6;
162: bits[offset] |= 1L << index;
163: } else
164: array.setRowMajor(index + displacement, Fixnum.ONE);
165: }
166:
167: protected void clearBit(int index) throws ConditionThrowable {
168: if (bits != null) {
169: int offset = index >> 6;
170: bits[offset] &= ~(1L << index);
171: } else
172: array.setRowMajor(index + displacement, Fixnum.ZERO);
173: }
174:
175: public void shrink(int n) throws ConditionThrowable {
176: if (bits != null) {
177: if (n < capacity) {
178: int size = n >>> 6;
179: if ((n & LONG_MASK) != 0)
180: ++size;
181: if (size < bits.length) {
182: long[] newbits = new long[size];
183: System.arraycopy(bits, 0, newbits, 0, size);
184: bits = newbits;
185: }
186: capacity = n;
187: return;
188: }
189: if (n == capacity)
190: return;
191: }
192: signal(new LispError());
193: }
194:
195: public boolean isSimpleVector() {
196: return false;
197: }
198:
199: // FIXME
200: public LispObject vectorPushExtend(LispObject element)
201: throws ConditionThrowable {
202: final int fp = getFillPointer();
203: if (fp < 0)
204: noFillPointer();
205: if (fp >= capacity()) {
206: // Need to extend vector.
207: ensureCapacity(capacity() * 2 + 1);
208: }
209: setRowMajor(fp, element);
210: setFillPointer(fp + 1);
211: return new Fixnum(fp);
212: }
213:
214: // FIXME
215: public LispObject vectorPushExtend(LispObject element,
216: LispObject extension) throws ConditionThrowable {
217: int ext = Fixnum.getValue(extension);
218: final int fp = getFillPointer();
219: if (fp < 0)
220: noFillPointer();
221: if (fp >= capacity()) {
222: // Need to extend vector.
223: ext = Math.max(ext, capacity() + 1);
224: ensureCapacity(capacity() + ext);
225: }
226: setRowMajor(fp, element);
227: setFillPointer(fp + 1);
228: return new Fixnum(fp);
229: }
230:
231: private final void ensureCapacity(int minCapacity)
232: throws ConditionThrowable {
233: if (bits != null) {
234: if (capacity < minCapacity) {
235: int size = minCapacity >>> 6;
236: if ((minCapacity & LONG_MASK) != 0)
237: ++size;
238: long[] newBits = new long[size];
239: System.arraycopy(bits, 0, newBits, 0, bits.length);
240: bits = newBits;
241: capacity = minCapacity;
242: }
243: } else {
244: Debug.assertTrue(array != null);
245: if (array.getTotalSize() - displacement < minCapacity) {
246: // Copy array.
247: int size = minCapacity >>> 6;
248: if ((minCapacity & LONG_MASK) != 0)
249: ++size;
250: bits = new long[size];
251: for (int i = 0; i < capacity; i++) {
252: int n = Fixnum.getValue(array
253: .getRowMajor(displacement + i));
254: if (n == 1)
255: setBit(i);
256: else
257: clearBit(i);
258: }
259: capacity = minCapacity;
260: array = null;
261: displacement = 0;
262: isDisplaced = false;
263: }
264: }
265: }
266:
267: public AbstractVector adjustVector(int newCapacity,
268: LispObject initialElement, LispObject initialContents)
269: throws ConditionThrowable {
270: if (bits == null) {
271: // Copy array.
272: int size = capacity >>> 6;
273: if ((capacity & LONG_MASK) != 0)
274: ++size;
275: bits = new long[size];
276: for (int i = 0; i < capacity; i++) {
277: int n = Fixnum.getValue(array.getRowMajor(displacement
278: + i));
279: if (n == 1)
280: setBit(i);
281: else
282: clearBit(i);
283: }
284: array = null;
285: displacement = 0;
286: isDisplaced = false;
287: }
288: if (capacity != newCapacity) {
289: int size = newCapacity >>> 6;
290: if ((newCapacity & LONG_MASK) != 0)
291: ++size;
292: if (initialContents != NIL) {
293: bits = new long[size];
294: if (initialContents.listp()) {
295: LispObject list = initialContents;
296: for (int i = 0; i < newCapacity; i++) {
297: setRowMajor(i, list.car());
298: list = list.cdr();
299: }
300: } else if (initialContents.vectorp()) {
301: for (int i = 0; i < newCapacity; i++)
302: setRowMajor(i, initialContents.elt(i));
303: } else
304: signal(new TypeError(initialContents,
305: Symbol.SEQUENCE));
306: } else {
307: long[] newBits = new long[size];
308: System.arraycopy(bits, 0, newBits, 0, Math.min(
309: bits.length, newBits.length));
310: bits = newBits;
311: if (newCapacity > capacity) {
312: int n = Fixnum.getValue(initialElement);
313: if (n == 1)
314: for (int i = capacity; i < newCapacity; i++)
315: setBit(i);
316: else
317: for (int i = capacity; i < newCapacity; i++)
318: clearBit(i);
319: }
320: }
321: capacity = newCapacity;
322: }
323: return this ;
324: }
325:
326: public AbstractVector adjustVector(int size,
327: AbstractArray displacedTo, int displacement)
328: throws ConditionThrowable {
329: capacity = size;
330: array = displacedTo;
331: this .displacement = displacement;
332: bits = null;
333: isDisplaced = true;
334: return this;
335: }
336: }
|