| /* |
| * 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 fuck with 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(); |
| } |
| |
| } |