001: /*
002: * BitVector.java
003: *
004: * Copyright (C) 2003 Peter Graves
005: * $Id: BitVector.java,v 1.6 2003/11/15 11:03:30 beedlem 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 BitVector extends AbstractVector {
025: private static final int LONG_MASK = 0x3f;
026:
027: private int capacity;
028: private long[] bits;
029:
030: public BitVector(int length) throws ConditionThrowable {
031: if (length < 0)
032: throw new NegativeArraySizeException();
033: capacity = length;
034: int size = length >>> 6;
035: if ((length & LONG_MASK) != 0)
036: ++size;
037: bits = new long[size];
038: }
039:
040: public BitVector(String s) throws ConditionThrowable {
041: this (s.length());
042: for (int i = s.length(); i-- > 0;) {
043: char c = s.charAt(i);
044: if (c == '0')
045: ;
046: else if (c == '1')
047: set(i);
048: else
049: Debug.assertTrue(false);
050: }
051: }
052:
053: public LispObject typeOf() {
054: if (isSimpleVector())
055: return list2(Symbol.SIMPLE_BIT_VECTOR, new Fixnum(length()));
056: return list2(Symbol.BIT_VECTOR, new Fixnum(length()));
057: }
058:
059: public LispClass classOf() {
060: return BuiltInClass.BIT_VECTOR;
061: }
062:
063: public LispObject typep(LispObject type) throws ConditionThrowable {
064: if (type == Symbol.BIT_VECTOR)
065: return T;
066: if (type == Symbol.SIMPLE_BIT_VECTOR)
067: return isSimpleVector() ? T : NIL;
068: if (type == Symbol.SIMPLE_VECTOR)
069: return NIL; // Can't hold elements of any type, only bits.
070: if (type == BuiltInClass.BIT_VECTOR)
071: return T;
072: return super .typep(type);
073: }
074:
075: public LispObject BIT_VECTOR_P() {
076: return T;
077: }
078:
079: public LispObject getElementType() {
080: return Symbol.BIT;
081: }
082:
083: public int capacity() {
084: return capacity;
085: }
086:
087: public final void ensureCapacity(int minCapacity) {
088: if (capacity < minCapacity) {
089: int size = minCapacity >>> 6;
090: if ((minCapacity & LONG_MASK) != 0)
091: ++size;
092: long[] newBits = new long[size];
093: System.arraycopy(bits, 0, newBits, 0, bits.length);
094: bits = newBits;
095: capacity = minCapacity;
096: }
097: }
098:
099: public int length() {
100: return fillPointer >= 0 ? fillPointer : capacity;
101: }
102:
103: public LispObject elt(int index) throws ConditionThrowable {
104: if (index < 0 || index >= length())
105: badIndex(index, length());
106: int offset = index >> 6;
107: return (bits[offset] & (1L << index)) != 0 ? Fixnum.ONE
108: : Fixnum.ZERO;
109: }
110:
111: // Ignores fill pointer.
112: public LispObject AREF(LispObject index) throws ConditionThrowable {
113: return get(Fixnum.getValue(index));
114: }
115:
116: public LispObject reverse() throws ConditionThrowable {
117: int length = length();
118: BitVector result = new BitVector(length);
119: int i, j;
120: for (i = 0, j = length - 1; i < length; i++, j--) {
121: if (_get(j) == 1)
122: result.set(i);
123: else
124: result.clear(i);
125: }
126: return result;
127: }
128:
129: public LispObject getRowMajor(int index) throws ConditionThrowable {
130: return get(index);
131: }
132:
133: public void setRowMajor(int index, LispObject newValue)
134: throws ConditionThrowable {
135: set(index, newValue);
136: }
137:
138: public LispObject get(int index) throws ConditionThrowable {
139: if (index >= capacity)
140: badIndex(index, capacity);
141: int offset = index >> 6;
142: return (bits[offset] & (1L << index)) != 0 ? Fixnum.ONE
143: : Fixnum.ZERO;
144: }
145:
146: private int _get(int index) {
147: int offset = index >> 6;
148: return (bits[offset] & (1L << index)) != 0 ? 1 : 0;
149: }
150:
151: public void set(int index, LispObject newValue)
152: throws ConditionThrowable {
153: if (index >= capacity)
154: badIndex(index, capacity);
155: try {
156: int n = Fixnum.getValue(newValue);
157: if (n == 1) {
158: set(index);
159: return;
160: }
161: if (n == 0) {
162: clear(index);
163: return;
164: }
165: // None of the above...
166: } catch (ConditionThrowable t) {
167: }
168: throw new ConditionThrowable(new TypeError(newValue, "bit"));
169: }
170:
171: public void set(int index) {
172: int offset = index >> 6;
173: bits[offset] |= 1L << index;
174: }
175:
176: public void clear(int index) {
177: int offset = index >> 6;
178: bits[offset] &= ~(1L << index);
179: }
180:
181: public LispObject subseq(int start, int end)
182: throws ConditionThrowable {
183: BitVector v = new BitVector(end - start);
184: int i = start, j = 0;
185: while (i < end) {
186: if (_get(i++) == 0)
187: v.clear(j++);
188: else
189: v.set(j++);
190: }
191: return v;
192: }
193:
194: public void fill(LispObject obj) throws ConditionThrowable {
195: try {
196: int n = Fixnum.getValue(obj);
197: if (n == 1) {
198: for (int i = bits.length; i-- > 0;)
199: bits[i] = -1L;
200: return;
201: }
202: if (n == 0) {
203: for (int i = bits.length; i-- > 0;)
204: bits[i] = 0;
205: return;
206: }
207: // None of the above...
208: } catch (ConditionThrowable t) {
209: }
210: throw new ConditionThrowable(new TypeError(obj, "bit"));
211: }
212:
213: public void shrink(int n) throws ConditionThrowable {
214: if (n < capacity) {
215: int size = n >>> 6;
216: if ((n & LONG_MASK) != 0)
217: ++size;
218: if (size < bits.length) {
219: long[] newbits = new long[size];
220: System.arraycopy(bits, 0, newbits, 0, size);
221: bits = newbits;
222: }
223: capacity = n;
224: return;
225: }
226: if (n == capacity)
227: return;
228: throw new ConditionThrowable(new LispError());
229: }
230:
231: public boolean isSimpleVector() {
232: return fillPointer < 0;
233: }
234:
235: public boolean equal(LispObject obj) throws ConditionThrowable {
236: if (this == obj)
237: return true;
238: if (obj instanceof BitVector) {
239: BitVector v = (BitVector) obj;
240: if (length() != v.length())
241: return false;
242: for (int i = length(); i-- > 0;) {
243: if (_get(i) != v._get(i))
244: return false;
245: }
246: return true;
247: }
248: return false;
249: }
250:
251: public boolean equalp(LispObject obj) throws ConditionThrowable {
252: if (this == obj)
253: return true;
254: if (obj instanceof BitVector) {
255: BitVector v = (BitVector) obj;
256: if (length() != v.length())
257: return false;
258: for (int i = length(); i-- > 0;) {
259: if (_get(i) != v._get(i))
260: return false;
261: }
262: return true;
263: }
264: if (obj instanceof AbstractVector)
265: return ((AbstractVector) obj).equalp(this );
266: return false;
267: }
268:
269: public String toString() {
270: final int limit = length();
271: StringBuffer sb = new StringBuffer(limit + 2);
272: sb.append("#*");
273: for (int i = 0; i < limit; i++)
274: sb.append(_get(i) == 1 ? '1' : '0');
275: return sb.toString();
276: }
277: }
|