FixedBitSet.cs

Go to the documentation of this file.

/*
 * 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.
 */

using System;
using System.Collections;
using Lucene.Net.Search;
using Lucene.Net.Util;

namespace Lucene.Net.Spatial.Util
{
    /* 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 class FixedBitSet : DocIdSet, IBits
    {
        private readonly BitArray bits;

        public static int bits2words(int numBits)
        {
            var numLong = (int)((uint)numBits >> 6);
            if ((numBits & 63) != 0)
            {
                numLong++;
            }
            return numLong;
        }

        public FixedBitSet(int numBits)
        {
            bits = new BitArray(numBits);
        }

        public FixedBitSet(FixedBitSet other)
        {
            bits = new BitArray(other.bits);
        }

        public IBits Bits()
        {
            return this;
        }

        public int Length()
        {
            return bits.Length;
        }

        public override bool IsCacheable
        {
            get { return true; }
        }

        public int Cardinality()
        {
            int ret = 0;
            for (var i = 0; i < bits.Length; i++)
            {
                if (bits[i]) ret++;
            }
            return ret;
        }

        public bool Get(int index)
        {
            return bits[index];
        }

        public void Set(int index)
        {
            bits.Set(index, true);
        }

        public bool GetAndSet(int index)
        {
            var ret = bits[index];
            bits.Set(index, true);
            return ret;
        }

        public void Clear(int index)
        {
            bits.Set(index, false);
        }

        public bool GetAndClear(int index)
        {
            var ret = bits[index];
            bits.Set(index, false);
            return ret;
        }

        public int NextSetBit(int index)
        {
            if (index >= bits.Length || index < 0)
                throw new ArgumentException("Invalid index", "index");

            for (var i = index; i < bits.Length; i++)
            {
                if (bits[i]) return i;
            }

            return -1;
        }

        /* Returns the index of the last set bit before or on the index specified.
         *  -1 is returned if there are no more set bits.
         */
        public int PrevSetBit(int index)
        {
            if (index >= bits.Length || index < 0)
                throw new ArgumentException("Invalid index", "index");

            for (var i = index; i >= 0; i--)
            {
                if (bits[i]) return i;
            }

            return -1;
        }

        /* Does in-place OR of the bits provided by the
         *  iterator. */
        //public void Or(DocIdSetIterator iter)
        //{
        //    if (iter is OpenBitSetIterator && iter.DocID() == -1)
        //    {
        //        var obs = (OpenBitSetIterator)iter;
        //        Or(obs.arr, obs.words);
        //        // advance after last doc that would be accepted if standard
        //        // iteration is used (to exhaust it):
        //        obs.Advance(bits.Length);
        //    }
        //    else
        //    {
        //        int doc;
        //        while ((doc = iter.NextDoc()) < bits.Length)
        //        {
        //            Set(doc);
        //        }
        //    }
        //}

        /* this = this OR other */
        public void Or(FixedBitSet other)
        {
            Or(other.bits, other.bits.Length);
        }

        private void Or(BitArray otherArr, int otherLen)
        {
            var thisArr = this.bits;
            int pos = Math.Min(thisArr.Length, otherLen);
            while (--pos >= 0)
            {
                thisArr[pos] |= otherArr[pos];
            }
        }

        /* Does in-place AND of the bits provided by the
         *  iterator. */
        //public void And(DocIdSetIterator iter)
        //{
        //    if (iter is OpenBitSetIterator && iter.DocID() == -1)
        //    {
        //        var obs = (OpenBitSetIterator)iter;
        //        And(obs.arr, obs.words);
        //        // advance after last doc that would be accepted if standard
        //        // iteration is used (to exhaust it):
        //        obs.Advance(bits.Length);
        //    }
        //    else
        //    {
        //        if (bits.Length == 0) return;
        //        int disiDoc, bitSetDoc = NextSetBit(0);
        //        while (bitSetDoc != -1 && (disiDoc = iter.Advance(bitSetDoc)) < bits.Length)
        //        {
        //            Clear(bitSetDoc, disiDoc);
        //            disiDoc++;
        //            bitSetDoc = (disiDoc < bits.Length) ? NextSetBit(disiDoc) : -1;
        //        }
        //        if (bitSetDoc != -1)
        //        {
        //            Clear(bitSetDoc, bits.Length);
        //        }
        //    }
        //}

        /* this = this AND other */
        public void And(FixedBitSet other)
        {
            And(other.bits, other.bits.Length);
        }

        private void And(BitArray otherArr, int otherLen)
        {
            var thisArr = this.bits;
            int pos = Math.Min(thisArr.Length, otherLen);
            while (--pos >= 0)
            {
                thisArr[pos] &= otherArr[pos];
            }
            if (thisArr.Length > otherLen)
            {
                for (var i = otherLen; i < thisArr.Length; i++)
                {
                    thisArr[i] = false;
                }
            }
        }

        /* Does in-place AND NOT of the bits provided by the
         *  iterator. */
        //public void AndNot(DocIdSetIterator iter)
        //{
        //    var obs = iter as OpenBitSetIterator;
        //    if (obs != null && iter.DocID() == -1)
        //    {
        //        AndNot(obs.arr, obs.words);
        //        // advance after last doc that would be accepted if standard
        //        // iteration is used (to exhaust it):
        //        obs.Advance(bits.Length);
        //    }
        //    else
        //    {
        //        int doc;
        //        while ((doc = iter.NextDoc()) < bits.Length)
        //        {
        //            Clear(doc);
        //        }
        //    }
        //}

        /* this = this AND NOT other */
        public void AndNot(FixedBitSet other)
        {
            AndNot(other.bits, other.bits.Length);
        }

        private void AndNot(BitArray otherArr, int otherLen)
        {
            var thisArr = this.bits;
            int pos = Math.Min(thisArr.Length, otherLen);
            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) {
        //  Debug.Assert(startIndex >= 0 && startIndex < numBits);
        //  Debug.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 (var i=startWord+1; i<endWord; i++) {
        //    bits[i] = ~bits[i];
        //  }

        //  bits[endWord] ^= endmask;
        //}

        /* Sets a range of bits
         *
         * @param startIndex lower index
         * @param endIndex one-past the last bit to set
         */
        public void Set(int startIndex, int endIndex)
        {
            // Naive implementation
            for (int i = startIndex; i < endIndex; i++)
            {
                Set(i);
            }
        }

        //      public void Set(int startIndex, int endIndex) {
        //  Debug.Assert(startIndex >= 0 && startIndex < numBits);
        //  Debug.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)
        {
            for (int i = startIndex; i < endIndex; i++)
            {
                Clear(i);
            }
        }

        //@Override
        public FixedBitSet Clone()
        {
            return new FixedBitSet(this);
        }

        /* returns true if both sets have the same bits set */
        public override bool Equals(Object o)
        {
            if (this == o)
            {
                return true;
            }

            var other = o as FixedBitSet;
            if (other == null)
            {
                return false;
            }

            return bits.Equals(other.bits);
        }

        public override int GetHashCode()
        {
            return bits.GetHashCode();
        }

        public override DocIdSetIterator Iterator()
        {
            return new FixedBitSetIterator(this);
        }

        public class FixedBitSetIterator : DocIdSetIterator
        {
            private int curDocId = -1;
            private readonly IEnumerator enumerator;

            public FixedBitSetIterator(FixedBitSet bitset)
            {
                enumerator = bitset.bits.GetEnumerator();
            }

            public override int DocID()
            {
                return curDocId;
            }

            public override int NextDoc()
            {
                while (enumerator.MoveNext())
                {
                    ++curDocId;
                    if ((bool)enumerator.Current) return curDocId;
                }
                return curDocId = NO_MORE_DOCS;
            }

            public override int Advance(int target)
            {
                int doc;
                while ((doc = NextDoc()) < target)
                {
                }
                return doc;
            }
        }
    }
}