KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > xalan > xsltc > dom > BitArray


1 /*
2  * Copyright 2001-2004 The Apache Software Foundation.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 /*
17  * $Id: BitArray.java,v 1.7 2004/02/16 22:54:59 minchau Exp $
18  */
19
20 package org.apache.xalan.xsltc.dom;
21
22 import java.io.Externalizable JavaDoc;
23 import java.io.IOException JavaDoc;
24 import java.io.ObjectInput JavaDoc;
25 import java.io.ObjectOutput JavaDoc;
26
27 import org.apache.xml.dtm.DTMAxisIterator;
28
29
30 /**
31  * @author Morten Jorgensen
32  */
33 public class BitArray implements Externalizable JavaDoc {
34
35     private int[] _bits;
36     private int _bitSize;
37     private int _intSize;
38     private int _mask;
39
40     // This table is used to prevent expensive shift operations
41 // (These operations are inexpensive on CPUs but very expensive on JVMs.)
42 private final static int[] _masks = {
43     0x80000000, 0x40000000, 0x20000000, 0x10000000,
44     0x08000000, 0x04000000, 0x02000000, 0x01000000,
45     0x00800000, 0x00400000, 0x00200000, 0x00100000,
46     0x00080000, 0x00040000, 0x00020000, 0x00010000,
47     0x00008000, 0x00004000, 0x00002000, 0x00001000,
48     0x00000800, 0x00000400, 0x00000200, 0x00000100,
49     0x00000080, 0x00000040, 0x00000020, 0x00000010,
50     0x00000008, 0x00000004, 0x00000002, 0x00000001 };
51
52     private final static boolean DEBUG_ASSERTIONS = false;
53     
54     /**
55      * Constructor. Defines the initial size of the bit array (in bits).
56      */
57     public BitArray() {
58     this(32);
59     }
60
61     public BitArray(int size) {
62         if (size < 32) size = 32;
63         _bitSize = size;
64         _intSize = (_bitSize >>> 5) + 1;
65         _bits = new int[_intSize + 1];
66     }
67
68     public BitArray(int size, int[] bits) {
69     if (size < 32) size = 32;
70     _bitSize = size;
71     _intSize = (_bitSize >>> 5) + 1;
72     _bits = bits;
73     }
74
75     /**
76      * Set the mask for this bit array. The upper 8 bits of this mask
77      * indicate the DOM in which the nodes in this array belong.
78      */
79     public void setMask(int mask) {
80     _mask = mask;
81     }
82
83     /**
84      * See setMask()
85      */
86     public int getMask() {
87     return(_mask);
88     }
89
90     /**
91      * Returns the size of this bit array (in bits).
92      */
93     public final int size() {
94     return(_bitSize);
95     }
96
97     /**
98      * Returns true if the given bit is set
99      */
100     public final boolean getBit(int bit) {
101         if (DEBUG_ASSERTIONS) {
102             if (bit >= _bitSize) {
103                 throw new Error JavaDoc(
104                              "Programmer's assertion in BitArray.getBit");
105             }
106         }
107
108         return((_bits[bit>>>5] & _masks[bit%32]) != 0);
109     }
110
111     /**
112      * Returns the next set bit from a given position
113      */
114     public final int getNextBit(int startBit) {
115         for (int i = (startBit >>> 5) ; i<=_intSize; i++) {
116             int bits = _bits[i];
117             if (bits != 0) {
118                 for (int b = (startBit % 32); b<32; b++) {
119                     if ((bits & _masks[b]) != 0) {
120                         return((i << 5) + b);
121                     }
122                 }
123             }
124             startBit = 0;
125         }
126         return(DTMAxisIterator.END);
127     }
128
129     /**
130      * This method returns the Nth bit that is set in the bit array. The
131      * current position is cached in the following 4 variables and will
132      * help speed up a sequence of next() call in an index iterator. This
133      * method is a mess, but it is fast and it works, so don't fuck with it.
134      */
135     private int _pos = Integer.MAX_VALUE;
136     private int _node = 0;
137     private int _int = 0;
138     private int _bit = 0;
139
140     public final int getBitNumber(int pos) {
141
142     // Return last node if position we're looking for is the same
143 if (pos == _pos) return(_node);
144     
145     // Start from beginning of position we're looking for is before
146 // the point where we left off the last time.
147 if (pos < _pos) {
148         _int = _bit = _pos = 0;
149     }
150
151     // Scan through the bit array - skip integers that have no bits set
152 for ( ; _int <= _intSize; _int++) {
153         int bits = _bits[_int];
154         if (bits != 0) { // Any bits set?
155 for ( ; _bit < 32; _bit++) {
156             if ((bits & _masks[_bit]) != 0) {
157             if (++_pos == pos) {
158                 _node = ((_int << 5) + _bit) - 1;
159                 return (_node);
160             }
161             }
162         }
163         _bit = 0;
164         }
165     }
166     return(0);
167     }
168
169     /**
170      * Returns the integer array in which the bit array is contained
171      */
172     public final int[] data() {
173     return(_bits);
174     }
175
176     int _first = Integer.MAX_VALUE; // The index where first set bit is
177 int _last = Integer.MIN_VALUE; // The _INTEGER INDEX_ where last set bit is
178
179     /**
180      * Sets a given bit
181      */
182     public final void setBit(int bit) {
183         if (DEBUG_ASSERTIONS) {
184             if (bit >= _bitSize) {
185                 throw new Error JavaDoc(
186                              "Programmer's assertion in BitArray.getBit");
187             }
188         }
189
190         if (bit >= _bitSize) return;
191         final int i = (bit >>> 5);
192         if (i < _first) _first = i;
193         if (i > _last) _last = i;
194         _bits[i] |= _masks[bit % 32];
195     }
196
197     /**
198      * Merge two bit arrays. This currently only works for nodes from
199      * a single DOM (because there is only one _mask per array).
200      */
201     public final BitArray merge(BitArray other) {
202     // Take other array's bits if we have node set
203 if (_last == -1) {
204         _bits = other._bits;
205     }
206     // Only merge if other array has any bits set
207 else if (other._last != -1) {
208         int start = (_first < other._first) ? _first : other._first;
209         int stop = (_last > other._last) ? _last : other._last;
210
211         // Merge these bits into other array if other array is larger
212 if (other._intSize > _intSize) {
213         if (stop > _intSize) stop = _intSize;
214         for (int i=start; i<=stop; i++)
215             other._bits[i] |= _bits[i];
216         _bits = other._bits;
217         }
218         // Merge other bits into this array if this arrai is large/equal.
219 else {
220         if (stop > other._intSize) stop = other._intSize;
221         for (int i=start; i<=stop; i++)
222             _bits[i] |= other._bits[i];
223         }
224     }
225     return(this);
226     }
227
228     /**
229      * Resizes the bit array - try to avoid using this method!!!
230      */
231     public final void resize(int newSize) {
232     if (newSize > _bitSize) {
233         _intSize = (newSize >>> 5) + 1;
234         final int[] newBits = new int[_intSize + 1];
235         System.arraycopy(_bits, 0, newBits, 0, (_bitSize>>>5) + 1);
236         _bits = newBits;
237         _bitSize = newSize;
238     }
239     }
240
241     public BitArray cloneArray() {
242     return(new BitArray(_intSize, _bits));
243     }
244
245     public void writeExternal(ObjectOutput JavaDoc out) throws IOException JavaDoc {
246     out.writeInt(_bitSize);
247     out.writeInt(_mask);
248     out.writeObject(_bits);
249     out.flush();
250     }
251
252     /**
253      * Read the whole tree from a file (serialized)
254      */
255     public void readExternal(ObjectInput JavaDoc in)
256     throws IOException JavaDoc, ClassNotFoundException JavaDoc {
257     _bitSize = in.readInt();
258     _intSize = (_bitSize >>> 5) + 1;
259     _mask = in.readInt();
260     _bits = (int[])in.readObject();
261     }
262
263 }
264
Popular Tags