1 16 19 20 package com.sun.org.apache.xalan.internal.xsltc.dom; 21 22 import java.io.Externalizable ; 23 import java.io.IOException ; 24 import java.io.ObjectInput ; 25 import java.io.ObjectOutput ; 26 27 import com.sun.org.apache.xml.internal.dtm.DTMAxisIterator; 28 29 30 33 public class BitArray implements Externalizable { 34 35 private int[] _bits; 36 private int _bitSize; 37 private int _intSize; 38 private int _mask; 39 40 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 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 79 public void setMask(int mask) { 80 _mask = mask; 81 } 82 83 86 public int getMask() { 87 return(_mask); 88 } 89 90 93 public final int size() { 94 return(_bitSize); 95 } 96 97 100 public final boolean getBit(int bit) { 101 if (DEBUG_ASSERTIONS) { 102 if (bit >= _bitSize) { 103 throw new Error ( 104 "Programmer's assertion in BitArray.getBit"); 105 } 106 } 107 108 return((_bits[bit>>>5] & _masks[bit%32]) != 0); 109 } 110 111 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 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 if (pos == _pos) return(_node); 144 145 if (pos < _pos) { 148 _int = _bit = _pos = 0; 149 } 150 151 for ( ; _int <= _intSize; _int++) { 153 int bits = _bits[_int]; 154 if (bits != 0) { 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 172 public final int[] data() { 173 return(_bits); 174 } 175 176 int _first = Integer.MAX_VALUE; int _last = Integer.MIN_VALUE; 179 182 public final void setBit(int bit) { 183 if (DEBUG_ASSERTIONS) { 184 if (bit >= _bitSize) { 185 throw new Error ( 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 201 public final BitArray merge(BitArray other) { 202 if (_last == -1) { 204 _bits = other._bits; 205 } 206 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 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 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 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 out) throws IOException { 246 out.writeInt(_bitSize); 247 out.writeInt(_mask); 248 out.writeObject(_bits); 249 out.flush(); 250 } 251 252 255 public void readExternal(ObjectInput in) 256 throws IOException , ClassNotFoundException { 257 _bitSize = in.readInt(); 258 _intSize = (_bitSize >>> 5) + 1; 259 _mask = in.readInt(); 260 _bits = (int[])in.readObject(); 261 } 262 263 } 264 | Popular Tags |