001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the "License");
007 * you may not use this file except in compliance with the License.
008 * You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018 /*
019 * $Id: BitArray.java 478667 2006-11-23 20:50:36Z minchau $
020 */
021
022 package org.apache.xalan.xsltc.dom;
023
024 import java.io.Externalizable;
025 import java.io.IOException;
026 import java.io.ObjectInput;
027 import java.io.ObjectOutput;
028
029 import org.apache.xml.dtm.DTMAxisIterator;
030
031
032 /**
033 * @author Morten Jorgensen
034 */
035 public class BitArray implements Externalizable {
036 static final long serialVersionUID = -4876019880708377663L;
037
038 private int[] _bits;
039 private int _bitSize;
040 private int _intSize;
041 private int _mask;
042
043 // This table is used to prevent expensive shift operations
044 // (These operations are inexpensive on CPUs but very expensive on JVMs.)
045 private final static int[] _masks = {
046 0x80000000, 0x40000000, 0x20000000, 0x10000000,
047 0x08000000, 0x04000000, 0x02000000, 0x01000000,
048 0x00800000, 0x00400000, 0x00200000, 0x00100000,
049 0x00080000, 0x00040000, 0x00020000, 0x00010000,
050 0x00008000, 0x00004000, 0x00002000, 0x00001000,
051 0x00000800, 0x00000400, 0x00000200, 0x00000100,
052 0x00000080, 0x00000040, 0x00000020, 0x00000010,
053 0x00000008, 0x00000004, 0x00000002, 0x00000001 };
054
055 private final static boolean DEBUG_ASSERTIONS = false;
056
057 /**
058 * Constructor. Defines the initial size of the bit array (in bits).
059 */
060 public BitArray() {
061 this(32);
062 }
063
064 public BitArray(int size) {
065 if (size < 32) size = 32;
066 _bitSize = size;
067 _intSize = (_bitSize >>> 5) + 1;
068 _bits = new int[_intSize + 1];
069 }
070
071 public BitArray(int size, int[] bits) {
072 if (size < 32) size = 32;
073 _bitSize = size;
074 _intSize = (_bitSize >>> 5) + 1;
075 _bits = bits;
076 }
077
078 /**
079 * Set the mask for this bit array. The upper 8 bits of this mask
080 * indicate the DOM in which the nodes in this array belong.
081 */
082 public void setMask(int mask) {
083 _mask = mask;
084 }
085
086 /**
087 * See setMask()
088 */
089 public int getMask() {
090 return(_mask);
091 }
092
093 /**
094 * Returns the size of this bit array (in bits).
095 */
096 public final int size() {
097 return(_bitSize);
098 }
099
100 /**
101 * Returns true if the given bit is set
102 */
103 public final boolean getBit(int bit) {
104 if (DEBUG_ASSERTIONS) {
105 if (bit >= _bitSize) {
106 throw new Error(
107 "Programmer's assertion in BitArray.getBit");
108 }
109 }
110
111 return((_bits[bit>>>5] & _masks[bit%32]) != 0);
112 }
113
114 /**
115 * Returns the next set bit from a given position
116 */
117 public final int getNextBit(int startBit) {
118 for (int i = (startBit >>> 5) ; i<=_intSize; i++) {
119 int bits = _bits[i];
120 if (bits != 0) {
121 for (int b = (startBit % 32); b<32; b++) {
122 if ((bits & _masks[b]) != 0) {
123 return((i << 5) + b);
124 }
125 }
126 }
127 startBit = 0;
128 }
129 return(DTMAxisIterator.END);
130 }
131
132 /**
133 * This method returns the Nth bit that is set in the bit array. The
134 * current position is cached in the following 4 variables and will
135 * help speed up a sequence of next() call in an index iterator. This
136 * method is a mess, but it is fast and it works, so don't change it.
137 */
138 private int _pos = Integer.MAX_VALUE;
139 private int _node = 0;
140 private int _int = 0;
141 private int _bit = 0;
142
143 public final int getBitNumber(int pos) {
144
145 // Return last node if position we're looking for is the same
146 if (pos == _pos) return(_node);
147
148 // Start from beginning of position we're looking for is before
149 // the point where we left off the last time.
150 if (pos < _pos) {
151 _int = _bit = _pos = 0;
152 }
153
154 // Scan through the bit array - skip integers that have no bits set
155 for ( ; _int <= _intSize; _int++) {
156 int bits = _bits[_int];
157 if (bits != 0) { // Any bits set?
158 for ( ; _bit < 32; _bit++) {
159 if ((bits & _masks[_bit]) != 0) {
160 if (++_pos == pos) {
161 _node = ((_int << 5) + _bit) - 1;
162 return (_node);
163 }
164 }
165 }
166 _bit = 0;
167 }
168 }
169 return(0);
170 }
171
172 /**
173 * Returns the integer array in which the bit array is contained
174 */
175 public final int[] data() {
176 return(_bits);
177 }
178
179 int _first = Integer.MAX_VALUE; // The index where first set bit is
180 int _last = Integer.MIN_VALUE; // The _INTEGER INDEX_ where last set bit is
181
182 /**
183 * Sets a given bit
184 */
185 public final void setBit(int bit) {
186 if (DEBUG_ASSERTIONS) {
187 if (bit >= _bitSize) {
188 throw new Error(
189 "Programmer's assertion in BitArray.getBit");
190 }
191 }
192
193 if (bit >= _bitSize) return;
194 final int i = (bit >>> 5);
195 if (i < _first) _first = i;
196 if (i > _last) _last = i;
197 _bits[i] |= _masks[bit % 32];
198 }
199
200 /**
201 * Merge two bit arrays. This currently only works for nodes from
202 * a single DOM (because there is only one _mask per array).
203 */
204 public final BitArray merge(BitArray other) {
205 // Take other array's bits if we have node set
206 if (_last == -1) {
207 _bits = other._bits;
208 }
209 // Only merge if other array has any bits set
210 else if (other._last != -1) {
211 int start = (_first < other._first) ? _first : other._first;
212 int stop = (_last > other._last) ? _last : other._last;
213
214 // Merge these bits into other array if other array is larger
215 if (other._intSize > _intSize) {
216 if (stop > _intSize) stop = _intSize;
217 for (int i=start; i<=stop; i++)
218 other._bits[i] |= _bits[i];
219 _bits = other._bits;
220 }
221 // Merge other bits into this array if this arrai is large/equal.
222 else {
223 if (stop > other._intSize) stop = other._intSize;
224 for (int i=start; i<=stop; i++)
225 _bits[i] |= other._bits[i];
226 }
227 }
228 return(this);
229 }
230
231 /**
232 * Resizes the bit array - try to avoid using this method!!!
233 */
234 public final void resize(int newSize) {
235 if (newSize > _bitSize) {
236 _intSize = (newSize >>> 5) + 1;
237 final int[] newBits = new int[_intSize + 1];
238 System.arraycopy(_bits, 0, newBits, 0, (_bitSize>>>5) + 1);
239 _bits = newBits;
240 _bitSize = newSize;
241 }
242 }
243
244 public BitArray cloneArray() {
245 return(new BitArray(_intSize, _bits));
246 }
247
248 public void writeExternal(ObjectOutput out) throws IOException {
249 out.writeInt(_bitSize);
250 out.writeInt(_mask);
251 out.writeObject(_bits);
252 out.flush();
253 }
254
255 /**
256 * Read the whole tree from a file (serialized)
257 */
258 public void readExternal(ObjectInput in)
259 throws IOException, ClassNotFoundException {
260 _bitSize = in.readInt();
261 _intSize = (_bitSize >>> 5) + 1;
262 _mask = in.readInt();
263 _bits = (int[])in.readObject();
264 }
265
266 }