SortedVIntList.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 Lucene.Net.Support;
using DocIdSet = Lucene.Net.Search.DocIdSet;
using DocIdSetIterator = Lucene.Net.Search.DocIdSetIterator;

namespace Lucene.Net.Util
{
    
    /// <summary> Stores and iterate on sorted integers in compressed form in RAM. <br/>
    /// The code for compressing the differences between ascending integers was
    /// borrowed from <see cref="Lucene.Net.Store.IndexInput" /> and
    /// <see cref="Lucene.Net.Store.IndexOutput" />.<p/>
    /// <b>NOTE:</b> this class assumes the stored integers are doc Ids (hence why it
    /// extends <see cref="DocIdSet" />). Therefore its <see cref="Iterator()" /> assumes <see cref="DocIdSetIterator.NO_MORE_DOCS" />
    /// can be used as sentinel. If you intent to use
    /// this value, then make sure it's not used during search flow.
    /// </summary>
    public class SortedVIntList:DocIdSet
    {
        private class AnonymousClassDocIdSetIterator:DocIdSetIterator
        {
            public AnonymousClassDocIdSetIterator(SortedVIntList enclosingInstance)
            {
                InitBlock(enclosingInstance);
            }
            private void  InitBlock(SortedVIntList enclosingInstance)
            {
                this.enclosingInstance = enclosingInstance;
            }
            private SortedVIntList enclosingInstance;
            public SortedVIntList Enclosing_Instance
            {
                get
                {
                    return enclosingInstance;
                }
                
            }
            internal int bytePos = 0;
            internal int lastInt = 0;
            internal int doc = - 1;
            
            private void  Advance()
            {
                // See Lucene.Net.Store.IndexInput.readVInt()
                sbyte b = Enclosing_Instance.bytes[bytePos++];
                lastInt += (b & Lucene.Net.Util.SortedVIntList.VB1);
                for (int s = Lucene.Net.Util.SortedVIntList.BIT_SHIFT; (b & ~ Lucene.Net.Util.SortedVIntList.VB1) != 0; s += Lucene.Net.Util.SortedVIntList.BIT_SHIFT)
                {
                    b = Enclosing_Instance.bytes[bytePos++];
                    lastInt += ((b & Lucene.Net.Util.SortedVIntList.VB1) << s);
                }
            }
            
            public override int DocID()
            {
                return doc;
            }
            
            public override int NextDoc()
            {
                if (bytePos >= Enclosing_Instance.lastBytePos)
                {
                    doc = NO_MORE_DOCS;
                }
                else
                {
                    Advance();
                    doc = lastInt;
                }
                return doc;
            }
            
            public override int Advance(int target)
            {
                while (bytePos < Enclosing_Instance.lastBytePos)
                {
                    Advance();
                    if (lastInt >= target)
                    {
                        return doc = lastInt;
                    }
                }
                return doc = NO_MORE_DOCS;
            }
        }
        /// <summary>When a BitSet has fewer than 1 in BITS2VINTLIST_SIZE bits set,
        /// a SortedVIntList representing the index numbers of the set bits
        /// will be smaller than that BitSet.
        /// </summary>
        internal const int BITS2VINTLIST_SIZE = 8;
        
        private int size;
        private sbyte[] bytes;
        private int lastBytePos;
        
        /// <summary>  Create a SortedVIntList from all elements of an array of integers.
        /// 
        /// </summary>
        /// <param name="sortedInts"> A sorted array of non negative integers.
        /// </param>
        public SortedVIntList(params int[] sortedInts):this(sortedInts, sortedInts.Length)
        {
        }
        
        /// <summary> Create a SortedVIntList from an array of integers.</summary>
        /// <param name="sortedInts"> An array of sorted non negative integers.
        /// </param>
        /// <param name="inputSize">  The number of integers to be used from the array.
        /// </param>
        public SortedVIntList(int[] sortedInts, int inputSize)
        {
            SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
            for (int i = 0; i < inputSize; i++)
            {
                builder.AddInt(sortedInts[i]);
            }
            builder.Done();
        }
        
        /// <summary> Create a SortedVIntList from a BitSet.</summary>
        /// <param name="bits"> A bit set representing a set of integers.
        /// </param>
        public SortedVIntList(System.Collections.BitArray bits)
        {
            SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
            int nextInt = BitSetSupport.NextSetBit(bits, 0);
            while (nextInt != - 1)
            {
                builder.AddInt(nextInt);
                nextInt = BitSetSupport.NextSetBit(bits, nextInt + 1);
            }
            builder.Done();
        }
        
        /// <summary> Create a SortedVIntList from an OpenBitSet.</summary>
        /// <param name="bits"> A bit set representing a set of integers.
        /// </param>
        public SortedVIntList(OpenBitSet bits)
        {
            SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
            int nextInt = bits.NextSetBit(0);
            while (nextInt != - 1)
            {
                builder.AddInt(nextInt);
                nextInt = bits.NextSetBit(nextInt + 1);
            }
            builder.Done();
        }
        
        /// <summary> Create a SortedVIntList.</summary>
        /// <param name="docIdSetIterator"> An iterator providing document numbers as a set of integers.
        /// This DocIdSetIterator is iterated completely when this constructor
        /// is called and it must provide the integers in non
        /// decreasing order.
        /// </param>
        public SortedVIntList(DocIdSetIterator docIdSetIterator)
        {
            SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
            int doc;
            while ((doc = docIdSetIterator.NextDoc()) != DocIdSetIterator.NO_MORE_DOCS)
            {
                builder.AddInt(doc);
            }
            builder.Done();
        }
        
        
        private class SortedVIntListBuilder
        {
            private void  InitBlock(SortedVIntList enclosingInstance)
            {
                this.enclosingInstance = enclosingInstance;
            }
            private SortedVIntList enclosingInstance;
            public SortedVIntList Enclosing_Instance
            {
                get
                {
                    return enclosingInstance;
                }
                
            }
            private int lastInt = 0;
            
            internal SortedVIntListBuilder(SortedVIntList enclosingInstance)
            {
                InitBlock(enclosingInstance);
                Enclosing_Instance.InitBytes();
                lastInt = 0;
            }
            
            internal virtual void  AddInt(int nextInt)
            {
                int diff = nextInt - lastInt;
                if (diff < 0)
                {
                    throw new System.ArgumentException("Input not sorted or first element negative.");
                }
                
                if ((Enclosing_Instance.lastBytePos + Enclosing_Instance.MAX_BYTES_PER_INT) > Enclosing_Instance.bytes.Length)
                {
                    // biggest possible int does not fit
                    Enclosing_Instance.ResizeBytes((Enclosing_Instance.bytes.Length * 2) + Enclosing_Instance.MAX_BYTES_PER_INT);
                }
                
                // See Lucene.Net.Store.IndexOutput.writeVInt()
                while ((diff & ~ Lucene.Net.Util.SortedVIntList.VB1) != 0)
                {
                    // The high bit of the next byte needs to be set.
                    Enclosing_Instance.bytes[Enclosing_Instance.lastBytePos++] = (sbyte) ((diff & Lucene.Net.Util.SortedVIntList.VB1) | ~ Lucene.Net.Util.SortedVIntList.VB1);
                    diff = Number.URShift(diff, Lucene.Net.Util.SortedVIntList.BIT_SHIFT);
                }
                Enclosing_Instance.bytes[Enclosing_Instance.lastBytePos++] = (sbyte) diff; // Last byte, high bit not set.
                Enclosing_Instance.size++;
                lastInt = nextInt;
            }
            
            internal virtual void  Done()
            {
                Enclosing_Instance.ResizeBytes(Enclosing_Instance.lastBytePos);
            }
        }
        
        
        private void  InitBytes()
        {
            size = 0;
            bytes = new sbyte[128]; // initial byte size
            lastBytePos = 0;
        }
        
        private void  ResizeBytes(int newSize)
        {
            if (newSize != bytes.Length)
            {
                sbyte[] newBytes = new sbyte[newSize];
                Array.Copy(bytes, 0, newBytes, 0, lastBytePos);
                bytes = newBytes;
            }
        }
        
        private const int VB1 = 0x7F;
        private const int BIT_SHIFT = 7;
        private int MAX_BYTES_PER_INT = (31 / BIT_SHIFT) + 1;

        /// <value> The total number of sorted integers. </value>
        public virtual int Size
        {
            get { return size; }
        }

        /// <value> The size of the byte array storing the compressed sorted integers. </value>
        public virtual int ByteSize
        {
            get { return bytes.Length; }
        }

        /// <summary>This DocIdSet implementation is cacheable. </summary>
        public override bool IsCacheable
        {
            get { return true; }
        }

        /// <returns>    An iterator over the sorted integers.
        /// </returns>
        public override DocIdSetIterator Iterator()
        {
            return new AnonymousClassDocIdSetIterator(this);
        }
    }
}