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