mcs/tools/monkeydoc/Lucene.Net/Lucene.Net/Util/SortedVIntList.cs

   1 /*
   2  * Licensed to the Apache Software Foundation (ASF) under one or more
   3  * contributor license agreements.  See the NOTICE file distributed with
   4  * this work for additional information regarding copyright ownership.
   5  * The ASF licenses this file to You under the Apache License, Version 2.0
   6  * (the "License"); you may not use this file except in compliance with
   7  * the License.  You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 using System;
  19
  20 using DocIdSet = Mono.Lucene.Net.Search.DocIdSet;
  21 using DocIdSetIterator = Mono.Lucene.Net.Search.DocIdSetIterator;
  22
  23 namespace Mono.Lucene.Net.Util
  24 {
  25
  26         /// <summary> Stores and iterate on sorted integers in compressed form in RAM. <br/>
  27         /// The code for compressing the differences between ascending integers was
  28         /// borrowed from {@link Mono.Lucene.Net.Store.IndexInput} and
  29         /// {@link Mono.Lucene.Net.Store.IndexOutput}.
  30         /// <p/>
  31         /// <b>NOTE:</b> this class assumes the stored integers are doc Ids (hence why it
  32         /// extends {@link DocIdSet}). Therefore its {@link #Iterator()} assumes {@link
  33         /// DocIdSetIterator#NO_MORE_DOCS} can be used as sentinel. If you intent to use
  34         /// this value, then make sure it's not used during search flow.
  35         /// </summary>
  36         public class SortedVIntList:DocIdSet
  37         {
  38                 private class AnonymousClassDocIdSetIterator:DocIdSetIterator
  39                 {
  40                         public AnonymousClassDocIdSetIterator(SortedVIntList enclosingInstance)
  41                         {
  42                                 InitBlock(enclosingInstance);
  43                         }
  44                         private void  InitBlock(SortedVIntList enclosingInstance)
  45                         {
  46                                 this.enclosingInstance = enclosingInstance;
  47                         }
  48                         private SortedVIntList enclosingInstance;
  49                         public SortedVIntList Enclosing_Instance
  50                         {
  51                                 get
  52                                 {
  53                                         return enclosingInstance;
  54                                 }
  55
  56                         }
  57                         internal int bytePos = 0;
  58                         internal int lastInt = 0;
  59                         internal int doc = - 1;
  60
  61                         private void  Advance()
  62                         {
  63                                 // See Mono.Lucene.Net.Store.IndexInput.readVInt()
  64                                 sbyte b = Enclosing_Instance.bytes[bytePos++];
  65                                 lastInt += (b & Mono.Lucene.Net.Util.SortedVIntList.VB1);
  66                                 for (int s = Mono.Lucene.Net.Util.SortedVIntList.BIT_SHIFT; (b & ~ Mono.Lucene.Net.Util.SortedVIntList.VB1) != 0; s += Mono.Lucene.Net.Util.SortedVIntList.BIT_SHIFT)
  67                                 {
  68                                         b = Enclosing_Instance.bytes[bytePos++];
  69                                         lastInt += ((b & Mono.Lucene.Net.Util.SortedVIntList.VB1) << s);
  70                                 }
  71                         }
  72
  73                         /// <deprecated> use {@link #DocID()} instead.
  74                         /// </deprecated>
  75             [Obsolete("use DocID() instead.")]
  76                         public override int Doc()
  77                         {
  78                                 return lastInt;
  79                         }
  80
  81                         public override int DocID()
  82                         {
  83                                 return doc;
  84                         }
  85
  86                         /// <deprecated> use {@link #NextDoc()} instead.
  87                         /// </deprecated>
  88             [Obsolete("use NextDoc() instead.")]
  89                         public override bool Next()
  90                         {
  91                                 return NextDoc() != NO_MORE_DOCS;
  92                         }
  93
  94                         public override int NextDoc()
  95                         {
  96                                 if (bytePos >= Enclosing_Instance.lastBytePos)
  97                                 {
  98                                         doc = NO_MORE_DOCS;
  99                                 }
 100                                 else
 101                                 {
 102                                         Advance();
 103                                         doc = lastInt;
 104                                 }
 105                                 return doc;
 106                         }
 107
 108                         /// <deprecated> use {@link #Advance(int)} instead.
 109                         /// </deprecated>
 110             [Obsolete("use Advance(int) instead.")]
 111                         public override bool SkipTo(int docNr)
 112                         {
 113                                 return Advance(docNr) != NO_MORE_DOCS;
 114                         }
 115
 116                         public override int Advance(int target)
 117                         {
 118                                 while (bytePos < Enclosing_Instance.lastBytePos)
 119                                 {
 120                                         Advance();
 121                                         if (lastInt >= target)
 122                                         {
 123                                                 return doc = lastInt;
 124                                         }
 125                                 }
 126                                 return doc = NO_MORE_DOCS;
 127                         }
 128                 }
 129                 /// <summary>When a BitSet has fewer than 1 in BITS2VINTLIST_SIZE bits set,
 130                 /// a SortedVIntList representing the index numbers of the set bits
 131                 /// will be smaller than that BitSet.
 132                 /// </summary>
 133                 internal const int BITS2VINTLIST_SIZE = 8;
 134
 135                 private int size;
 136                 private sbyte[] bytes;
 137                 private int lastBytePos;
 138
 139                 /// <summary>  Create a SortedVIntList from all elements of an array of integers.
 140                 ///
 141                 /// </summary>
 142                 /// <param name="sortedInts"> A sorted array of non negative integers.
 143                 /// </param>
 144                 public SortedVIntList(int[] sortedInts):this(sortedInts, sortedInts.Length)
 145                 {
 146                 }
 147
 148                 /// <summary> Create a SortedVIntList from an array of integers.</summary>
 149                 /// <param name="sortedInts"> An array of sorted non negative integers.
 150                 /// </param>
 151                 /// <param name="inputSize">  The number of integers to be used from the array.
 152                 /// </param>
 153                 public SortedVIntList(int[] sortedInts, int inputSize)
 154                 {
 155                         SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
 156                         for (int i = 0; i < inputSize; i++)
 157                         {
 158                                 builder.AddInt(sortedInts[i]);
 159                         }
 160                         builder.Done();
 161                 }
 162
 163                 /// <summary> Create a SortedVIntList from a BitSet.</summary>
 164                 /// <param name="bits"> A bit set representing a set of integers.
 165                 /// </param>
 166                 public SortedVIntList(System.Collections.BitArray bits)
 167                 {
 168                         SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
 169                         int nextInt = SupportClass.BitSetSupport.NextSetBit(bits, 0);
 170                         while (nextInt != - 1)
 171                         {
 172                                 builder.AddInt(nextInt);
 173                                 nextInt = SupportClass.BitSetSupport.NextSetBit(bits, nextInt + 1);
 174                         }
 175                         builder.Done();
 176                 }
 177
 178                 /// <summary> Create a SortedVIntList from an OpenBitSet.</summary>
 179                 /// <param name="bits"> A bit set representing a set of integers.
 180                 /// </param>
 181                 public SortedVIntList(OpenBitSet bits)
 182                 {
 183                         SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
 184                         int nextInt = bits.NextSetBit(0);
 185                         while (nextInt != - 1)
 186                         {
 187                                 builder.AddInt(nextInt);
 188                                 nextInt = bits.NextSetBit(nextInt + 1);
 189                         }
 190                         builder.Done();
 191                 }
 192
 193                 /// <summary> Create a SortedVIntList.</summary>
 194                 /// <param name="docIdSetIterator"> An iterator providing document numbers as a set of integers.
 195                 /// This DocIdSetIterator is iterated completely when this constructor
 196                 /// is called and it must provide the integers in non
 197                 /// decreasing order.
 198                 /// </param>
 199                 public SortedVIntList(DocIdSetIterator docIdSetIterator)
 200                 {
 201                         SortedVIntListBuilder builder = new SortedVIntListBuilder(this);
 202                         int doc;
 203                         while ((doc = docIdSetIterator.NextDoc()) != DocIdSetIterator.NO_MORE_DOCS)
 204                         {
 205                                 builder.AddInt(doc);
 206                         }
 207                         builder.Done();
 208                 }
 209
 210
 211                 private class SortedVIntListBuilder
 212                 {
 213                         private void  InitBlock(SortedVIntList enclosingInstance)
 214                         {
 215                                 this.enclosingInstance = enclosingInstance;
 216                         }
 217                         private SortedVIntList enclosingInstance;
 218                         public SortedVIntList Enclosing_Instance
 219                         {
 220                                 get
 221                                 {
 222                                         return enclosingInstance;
 223                                 }
 224
 225                         }
 226                         private int lastInt = 0;
 227
 228                         internal SortedVIntListBuilder(SortedVIntList enclosingInstance)
 229                         {
 230                                 InitBlock(enclosingInstance);
 231                                 Enclosing_Instance.InitBytes();
 232                                 lastInt = 0;
 233                         }
 234
 235                         internal virtual void  AddInt(int nextInt)
 236                         {
 237                                 int diff = nextInt - lastInt;
 238                                 if (diff < 0)
 239                                 {
 240                                         throw new System.ArgumentException("Input not sorted or first element negative.");
 241                                 }
 242
 243                                 if ((Enclosing_Instance.lastBytePos + Enclosing_Instance.MAX_BYTES_PER_INT) > Enclosing_Instance.bytes.Length)
 244                                 {
 245                                         // biggest possible int does not fit
 246                                         Enclosing_Instance.ResizeBytes((Enclosing_Instance.bytes.Length * 2) + Enclosing_Instance.MAX_BYTES_PER_INT);
 247                                 }
 248
 249                                 // See Mono.Lucene.Net.Store.IndexOutput.writeVInt()
 250                                 while ((diff & ~ Mono.Lucene.Net.Util.SortedVIntList.VB1) != 0)
 251                                 {
 252                                         // The high bit of the next byte needs to be set.
 253                                         Enclosing_Instance.bytes[Enclosing_Instance.lastBytePos++] = (sbyte) ((diff & Mono.Lucene.Net.Util.SortedVIntList.VB1) | ~ Mono.Lucene.Net.Util.SortedVIntList.VB1);
 254                                         diff = SupportClass.Number.URShift(diff, Mono.Lucene.Net.Util.SortedVIntList.BIT_SHIFT);
 255                                 }
 256                                 Enclosing_Instance.bytes[Enclosing_Instance.lastBytePos++] = (sbyte) diff; // Last byte, high bit not set.
 257                                 Enclosing_Instance.size++;
 258                                 lastInt = nextInt;
 259                         }
 260
 261                         internal virtual void  Done()
 262                         {
 263                                 Enclosing_Instance.ResizeBytes(Enclosing_Instance.lastBytePos);
 264                         }
 265                 }
 266
 267
 268                 private void  InitBytes()
 269                 {
 270                         size = 0;
 271                         bytes = new sbyte[128]; // initial byte size
 272                         lastBytePos = 0;
 273                 }
 274
 275                 private void  ResizeBytes(int newSize)
 276                 {
 277                         if (newSize != bytes.Length)
 278                         {
 279                                 sbyte[] newBytes = new sbyte[newSize];
 280                                 Array.Copy(bytes, 0, newBytes, 0, lastBytePos);
 281                                 bytes = newBytes;
 282                         }
 283                 }
 284
 285                 private const int VB1 = 0x7F;
 286                 private const int BIT_SHIFT = 7;
 287                 private int MAX_BYTES_PER_INT = (31 / BIT_SHIFT) + 1;
 288
 289                 /// <returns>    The total number of sorted integers.
 290                 /// </returns>
 291                 public virtual int Size()
 292                 {
 293                         return size;
 294                 }
 295
 296                 /// <returns> The size of the byte array storing the compressed sorted integers.
 297                 /// </returns>
 298                 public virtual int GetByteSize()
 299                 {
 300                         return bytes.Length;
 301                 }
 302
 303                 /// <summary>This DocIdSet implementation is cacheable. </summary>
 304                 public override bool IsCacheable()
 305                 {
 306                         return true;
 307                 }
 308
 309                 /// <returns>    An iterator over the sorted integers.
 310                 /// </returns>
 311                 public override DocIdSetIterator Iterator()
 312                 {
 313                         return new AnonymousClassDocIdSetIterator(this);
 314                 }
 315         }
 316 }