code: /*
   * Licensed to the Apache Software Foundation (ASF) under one
   * or more contributor license agreements. See the NOTICE file
   * distributed with this work for additional information
   * regarding copyright ownership. The ASF licenses this file
   * to you under the Apache License, Version 2.0 (the  "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  /*
   * $Id$
   */
  
  package org.apache.xalan.xsltc.dom;
  
  import java.io.Externalizable;
  import java.io.IOException;
  import java.io.ObjectInput;
  import java.io.ObjectOutput;
  
  import org.apache.xml.dtm.DTMAxisIterator;
  
  
  /**
   * @author Morten Jorgensen
   */
  public class BitArray implements Externalizable {
      static final long serialVersionUID = -4876019880708377663L;
  
      private int[] _bits;
      private int   _bitSize;
      private int   _intSize;
      private int   _mask;
  
      // This table is used to prevent expensive shift operations
      // (These operations are inexpensive on CPUs but very expensive on JVMs.)
      private final static int[] _masks = {
  	0x80000000, 0x40000000, 0x20000000, 0x10000000,
  	0x08000000, 0x04000000, 0x02000000, 0x01000000,
  	0x00800000, 0x00400000, 0x00200000, 0x00100000,
  	0x00080000, 0x00040000, 0x00020000, 0x00010000,
  	0x00008000, 0x00004000, 0x00002000, 0x00001000,
  	0x00000800, 0x00000400, 0x00000200, 0x00000100,
  	0x00000080, 0x00000040, 0x00000020, 0x00000010,
  	0x00000008, 0x00000004, 0x00000002, 0x00000001 };
  
      private final static boolean DEBUG_ASSERTIONS = false;
      
      /**
       * Constructor. Defines the initial size of the bit array (in bits).
       */
      public BitArray() {
  	this(32);
      }
  
      public BitArray(int size) {        
          if (size < 32) size = 32;
          _bitSize = size;
          _intSize = (_bitSize >>> 5) + 1;
          _bits = new int[_intSize + 1];
      }
  
      public BitArray(int size, int[] bits) {
  	if (size < 32) size = 32;
  	_bitSize = size;
  	_intSize = (_bitSize >>> 5) + 1;
  	_bits = bits;
      }
  
      /**
       * Set the mask for this bit array. The upper 8 bits of this mask
       * indicate the DOM in which the nodes in this array belong.
       */    
      public void setMask(int mask) {
  	_mask = mask;
      }
  
      /**
       * See setMask()
       */
      public int getMask() {
  	return(_mask);
      }
  
      /**
       * Returns the size of this bit array (in bits).
       */
      public final int size() {
  	return(_bitSize);
      }
  
      /**
       * Returns true if the given bit is set
       */
      public final boolean getBit(int bit) {
          if (DEBUG_ASSERTIONS) {
              if (bit >= _bitSize) {
                  throw new Error(
                               "Programmer's assertion in  BitArray.getBit");
              }
          }
  
          return((_bits[bit>>>5] & _masks[bit%32]) != 0);
      }
  
      /**
       * Returns the next set bit from a given position
       */
      public final int getNextBit(int startBit) {
          for (int i = (startBit >>> 5) ; i<=_intSize; i++) {
              int bits = _bits[i];
              if (bits != 0) {
                  for (int b = (startBit % 32); b<32; b++) {
                      if ((bits & _masks[b]) != 0) {
                          return((i << 5) + b);
                      }
                  }
              }
              startBit = 0;
          }
          return(DTMAxisIterator.END);
      }
  
      /**
       * This method returns the Nth bit that is set in the bit array. The
       * current position is cached in the following 4 variables and will
       * help speed up a sequence of next() call in an index iterator. This
       * method is a mess, but it is fast and it works, so don't change it.
       */
      private int _pos = Integer.MAX_VALUE;
      private int _node = 0;
      private int _int = 0;
      private int _bit = 0;
  
      public final int getBitNumber(int pos) {
  
  	// Return last node if position we're looking for is the same
  	if (pos == _pos) return(_node);
  	
  	// Start from beginning of position we're looking for is before
  	// the point where we left off the last time.
  	if (pos < _pos) {
  	    _int = _bit = _pos = 0;
  	}
  
  	// Scan through the bit array - skip integers that have no bits set
  	for ( ; _int <= _intSize; _int++) {
  	    int bits = _bits[_int];
  	    if (bits != 0) { // Any bits set?
  		for ( ; _bit < 32; _bit++) {
  		    if ((bits & _masks[_bit]) != 0) {
  			if (++_pos == pos) {
  			    _node = ((_int << 5) + _bit) - 1;
  			    return (_node);
  			}
  		    }
  		}
  		_bit = 0;
  	    }
  	}
  	return(0);
      }
  
      /**
       * Returns the integer array in which the bit array is contained
       */
      public final int[] data() {
  	return(_bits);
      }
  
      int _first = Integer.MAX_VALUE; // The index where first set bit is
      int _last  = Integer.MIN_VALUE; // The _INTEGER INDEX_ where last set bit is
  
      /**
       * Sets a given bit
       */
      public final void setBit(int bit) {
          if (DEBUG_ASSERTIONS) {
              if (bit >= _bitSize) {
                  throw new Error(
                               "Programmer's assertion in  BitArray.getBit");
              }
          }
  
          if (bit >= _bitSize) return;
          final int i = (bit >>> 5);
          if (i < _first) _first = i;
          if (i > _last) _last = i;
          _bits[i] |= _masks[bit % 32];
      }
  
      /**
       * Merge two bit arrays. This currently only works for nodes from
       * a single DOM (because there is only one _mask per array).
       */
      public final BitArray merge(BitArray other) {
  	// Take other array's bits if we have node set
  	if (_last == -1) {
  	    _bits = other._bits;
  	}
  	// Only merge if other array has any bits set
  	else if (other._last != -1) {
  	    int start = (_first < other._first) ? _first : other._first;
  	    int stop  = (_last > other._last) ? _last : other._last;
  
  	    // Merge these bits into other array if other array is larger
  	    if (other._intSize > _intSize) {
  		if (stop > _intSize) stop = _intSize;
  		for (int i=start; i<=stop; i++)
  		    other._bits[i] |= _bits[i];
  		_bits = other._bits;
  	    }
  	    // Merge other bits into this array if this arrai is large/equal.
  	    else {
  		if (stop > other._intSize) stop = other._intSize;
  		for (int i=start; i<=stop; i++)
  		    _bits[i] |= other._bits[i];
  	    }
  	}
  	return(this);
      }
  
      /**
       * Resizes the bit array - try to avoid using this method!!!
       */
      public final void resize(int newSize) {
  	if (newSize > _bitSize) {
  	    _intSize = (newSize >>> 5) + 1;
  	    final int[] newBits = new int[_intSize + 1];
  	    System.arraycopy(_bits, 0, newBits, 0, (_bitSize>>>5) + 1);
  	    _bits = newBits;
  	    _bitSize = newSize;
  	}
      }
  
      public BitArray cloneArray() {
  	return(new BitArray(_intSize, _bits));
      }
  
      public void writeExternal(ObjectOutput out) throws IOException {
  	out.writeInt(_bitSize);
  	out.writeInt(_mask);
  	out.writeObject(_bits);
  	out.flush();
      }
  
      /**
       * Read the whole tree from a file (serialized)
       */
      public void readExternal(ObjectInput in)
  	throws IOException, ClassNotFoundException {
  	_bitSize = in.readInt();
  	_intSize = (_bitSize >>> 5) + 1;
  	_mask    = in.readInt();
  	_bits    = (int[])in.readObject();
      }
  
  }
  