1 /*
   2  * reserved comment block
   3  * DO NOT REMOVE OR ALTER!
   4  */
   5 /*
   6  * Licensed to the Apache Software Foundation (ASF) under one or more
   7  * contributor license agreements.  See the NOTICE file distributed with
   8  * this work for additional information regarding copyright ownership.
   9  * The ASF licenses this file to You under the Apache License, Version 2.0
  10  * (the "License"); you may not use this file except in compliance with
  11  * the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  */
  21 
  22 package com.sun.org.apache.xalan.internal.xsltc.dom;
  23 
  24 import java.io.Externalizable;
  25 import java.io.IOException;
  26 import java.io.ObjectInput;
  27 import java.io.ObjectOutput;
  28 
  29 import com.sun.org.apache.xml.internal.dtm.DTMAxisIterator;
  30 
  31 
  32 /**
  33  * @author Morten Jorgensen
  34  */
  35 public class BitArray implements Externalizable {
  36     static final long serialVersionUID = -4876019880708377663L;
  37 
  38     private int[] _bits;
  39     private int   _bitSize;
  40     private int   _intSize;
  41     private int   _mask;
  42 
  43     // This table is used to prevent expensive shift operations
  44     // (These operations are inexpensive on CPUs but very expensive on JVMs.)
  45     private final static int[] _masks = {
  46         0x80000000, 0x40000000, 0x20000000, 0x10000000,
  47         0x08000000, 0x04000000, 0x02000000, 0x01000000,
  48         0x00800000, 0x00400000, 0x00200000, 0x00100000,
  49         0x00080000, 0x00040000, 0x00020000, 0x00010000,
  50         0x00008000, 0x00004000, 0x00002000, 0x00001000,
  51         0x00000800, 0x00000400, 0x00000200, 0x00000100,
  52         0x00000080, 0x00000040, 0x00000020, 0x00000010,
  53         0x00000008, 0x00000004, 0x00000002, 0x00000001 };
  54 
  55     private final static boolean DEBUG_ASSERTIONS = false;
  56 
  57     /**
  58      * Constructor. Defines the initial size of the bit array (in bits).
  59      */
  60     public BitArray() {
  61         this(32);
  62     }
  63 
  64     public BitArray(int size) {
  65         if (size < 32) size = 32;
  66         _bitSize = size;
  67         _intSize = (_bitSize >>> 5) + 1;
  68         _bits = new int[_intSize + 1];
  69     }
  70 
  71     public BitArray(int size, int[] bits) {
  72         if (size < 32) size = 32;
  73         _bitSize = size;
  74         _intSize = (_bitSize >>> 5) + 1;
  75         _bits = bits;
  76     }
  77 
  78     /**
  79      * Set the mask for this bit array. The upper 8 bits of this mask
  80      * indicate the DOM in which the nodes in this array belong.
  81      */
  82     public void setMask(int mask) {
  83         _mask = mask;
  84     }
  85 
  86     /**
  87      * See setMask()
  88      */
  89     public int getMask() {
  90         return(_mask);
  91     }
  92 
  93     /**
  94      * Returns the size of this bit array (in bits).
  95      */
  96     public final int size() {
  97         return(_bitSize);
  98     }
  99 
 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 }
--- EOF ---