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
{
    
    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;
            }
        }
        internal const int BITS2VINTLIST_SIZE = 8;
        
        private int size;
        private sbyte[] bytes;
        private int lastBytePos;
        
        public SortedVIntList(params int[] sortedInts):this(sortedInts, sortedInts.Length)
        {
        }
        
        public SortedVIntList(int[] sortedInts, int inputSize)
        {
            SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
            for (int i = 0; i < inputSize; i++)
            {
                builder.AddInt(sortedInts[i]);
            }
            builder.Done();
        }
        
        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();
        }
        
        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();
        }
        
        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;

        public virtual int Size
        {
            get { return size; }
        }

        public virtual int ByteSize
        {
            get { return bytes.Length; }
        }

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

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