X-Git-Url: https://git.mdrn.pl/pylucene.git/blobdiff_plain/a2e61f0c04805cfcb8706176758d1283c7e3a55c..aaeed5504b982cf3545252ab528713250aa33eed:/lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/FixedBitSet.java diff --git a/lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/FixedBitSet.java b/lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/FixedBitSet.java deleted file mode 100644 index 9da87bf..0000000 --- a/lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/FixedBitSet.java +++ /dev/null @@ -1,335 +0,0 @@ -/** - * 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. - */ - -package org.apache.lucene.util; - -import java.io.IOException; -import java.util.Arrays; - -import org.apache.lucene.search.DocIdSet; -import org.apache.lucene.search.DocIdSetIterator; - -// TODO: maybe merge with BitVector? Problem is BitVector -// caches its cardinality... - -/** BitSet of fixed length (numBits), backed by accessible - * ({@link #getBits}) long[], accessed with an int index, - * implementing Bits and DocIdSet. Unlike {@link - * OpenBitSet} this bit set does not auto-expand, cannot - * handle long index, and does not have fastXX/XX variants - * (just X). - * - * @lucene.internal - **/ - -public final class FixedBitSet extends DocIdSet { - private final long[] bits; - private int numBits; - - /** returns the number of 64 bit words it would take to hold numBits */ - public static int bits2words(int numBits) { - int numLong = numBits >>> 6; - if ((numBits & 63) != 0) { - numLong++; - } - return numLong; - } - - public FixedBitSet(int numBits) { - this.numBits = numBits; - bits = new long[bits2words(numBits)]; - } - - /** Makes full copy. */ - public FixedBitSet(FixedBitSet other) { - bits = new long[other.bits.length]; - System.arraycopy(other.bits, 0, bits, 0, bits.length); - numBits = other.numBits; - } - - @Override - public DocIdSetIterator iterator() { - return new OpenBitSetIterator(bits, bits.length); - } - - public int length() { - return numBits; - } - - /** This DocIdSet implementation is cacheable. */ - @Override - public boolean isCacheable() { - return true; - } - - /** Expert. */ - public long[] getBits() { - return bits; - } - - /** Returns number of set bits. NOTE: this visits every - * long in the backing bits array, and the result is not - * internally cached! */ - public int cardinality() { - return (int) BitUtil.pop_array(bits, 0, bits.length); - } - - public boolean get(int index) { - assert index >= 0 && index < numBits; - int i = index >> 6; // div 64 - // signed shift will keep a negative index and force an - // array-index-out-of-bounds-exception, removing the need for an explicit check. - int bit = index & 0x3f; // mod 64 - long bitmask = 1L << bit; - return (bits[i] & bitmask) != 0; - } - - public void set(int index) { - assert index >= 0 && index < numBits; - int wordNum = index >> 6; // div 64 - int bit = index & 0x3f; // mod 64 - long bitmask = 1L << bit; - bits[wordNum] |= bitmask; - } - - public boolean getAndSet(int index) { - assert index >= 0 && index < numBits; - int wordNum = index >> 6; // div 64 - int bit = index & 0x3f; // mod 64 - long bitmask = 1L << bit; - boolean val = (bits[wordNum] & bitmask) != 0; - bits[wordNum] |= bitmask; - return val; - } - - public void clear(int index) { - assert index >= 0 && index < numBits; - int wordNum = index >> 6; - int bit = index & 0x03f; - long bitmask = 1L << bit; - bits[wordNum] &= ~bitmask; - } - - public boolean getAndClear(int index) { - assert index >= 0 && index < numBits; - int wordNum = index >> 6; // div 64 - int bit = index & 0x3f; // mod 64 - long bitmask = 1L << bit; - boolean val = (bits[wordNum] & bitmask) != 0; - bits[wordNum] &= ~bitmask; - return val; - } - - /** Returns the index of the first set bit starting at the index specified. - * -1 is returned if there are no more set bits. - */ - public int nextSetBit(int index) { - assert index >= 0 && index < numBits; - int i = index >> 6; - int subIndex = index & 0x3f; // index within the word - long word = bits[i] >> subIndex; // skip all the bits to the right of index - - if (word!=0) { - return (i<<6) + subIndex + BitUtil.ntz(word); - } - - while(++i < bits.length) { - word = bits[i]; - if (word != 0) { - return (i<<6) + BitUtil.ntz(word); - } - } - - return -1; - } - - public int prevSetBit(int index) { - assert index >= 0 && index < numBits: "index=" + index + " numBits=" + numBits; - int i = index >> 6; - final int subIndex; - long word; - subIndex = index & 0x3f; // index within the word - word = (bits[i] << (63-subIndex)); // skip all the bits to the left of index - - if (word != 0) { - return (i << 6) + subIndex - Long.numberOfLeadingZeros(word); // See LUCENE-3197 - } - - while (--i >= 0) { - word = bits[i]; - if (word !=0 ) { - return (i << 6) + 63 - Long.numberOfLeadingZeros(word); - } - } - - return -1; - } - - /** Does in-place OR of the bits provided by the - * iterator. */ - public void or(DocIdSetIterator iter) throws IOException { - int doc; - while ((doc = iter.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) { - set(doc); - } - } - - public void or(FixedBitSet other) { - long[] thisArr = this.bits; - long[] otherArr = other.bits; - int pos = Math.min(thisArr.length, otherArr.length); - while (--pos >= 0) { - thisArr[pos] |= otherArr[pos]; - } - } - - // NOTE: no .isEmpty() here because that's trappy (ie, - // typically isEmpty is low cost, but this one wouldn't - // be) - - /** Flips a range of bits - * - * @param startIndex lower index - * @param endIndex one-past the last bit to flip - */ - public void flip(int startIndex, int endIndex) { - assert startIndex >= 0 && startIndex < numBits; - assert endIndex >= 0 && endIndex <= numBits; - if (endIndex <= startIndex) { - return; - } - - int startWord = startIndex >> 6; - int endWord = (endIndex-1) >> 6; - - /*** Grrr, java shifting wraps around so -1L>>>64 == -1 - * for that reason, make sure not to use endmask if the bits to flip will - * be zero in the last word (redefine endWord to be the last changed...) - long startmask = -1L << (startIndex & 0x3f); // example: 11111...111000 - long endmask = -1L >>> (64-(endIndex & 0x3f)); // example: 00111...111111 - ***/ - - long startmask = -1L << startIndex; - long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap - - if (startWord == endWord) { - bits[startWord] ^= (startmask & endmask); - return; - } - - bits[startWord] ^= startmask; - - for (int i=startWord+1; i= 0 && startIndex < numBits; - assert endIndex >= 0 && endIndex <= numBits; - if (endIndex <= startIndex) { - return; - } - - int startWord = startIndex >> 6; - int endWord = (endIndex-1) >> 6; - - long startmask = -1L << startIndex; - long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap - - if (startWord == endWord) { - bits[startWord] |= (startmask & endmask); - return; - } - - bits[startWord] |= startmask; - Arrays.fill(bits, startWord+1, endWord, -1L); - bits[endWord] |= endmask; - } - - /** Clears a range of bits. - * - * @param startIndex lower index - * @param endIndex one-past the last bit to clear - */ - public void clear(int startIndex, int endIndex) { - assert startIndex >= 0 && startIndex < numBits; - assert endIndex >= 0 && endIndex <= numBits; - if (endIndex <= startIndex) { - return; - } - - int startWord = startIndex >> 6; - int endWord = (endIndex-1) >> 6; - - long startmask = -1L << startIndex; - long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap - - // invert masks since we are clearing - startmask = ~startmask; - endmask = ~endmask; - - if (startWord == endWord) { - bits[startWord] &= (startmask | endmask); - return; - } - - bits[startWord] &= startmask; - Arrays.fill(bits, startWord+1, endWord, 0L); - bits[endWord] &= endmask; - } - - @Override - public Object clone() { - return new FixedBitSet(this); - } - - /** returns true if both sets have the same bits set */ - @Override - public boolean equals(Object o) { - if (this == o) { - return true; - } - if (!(o instanceof FixedBitSet)) { - return false; - } - FixedBitSet other = (FixedBitSet) o; - if (numBits != other.length()) { - return false; - } - return Arrays.equals(bits, other.bits); - } - - @Override - public int hashCode() { - long h = 0; - for (int i = bits.length; --i>=0;) { - h ^= bits[i]; - h = (h << 1) | (h >>> 63); // rotate left - } - // fold leftmost bits into right and add a constant to prevent - // empty sets from returning 0, which is too common. - return (int) ((h>>32) ^ h) + 0x98761234; - } -}