beagled/Lucene.Net/Util/BitVector.cs

   1 /*
   2  * Copyright 2004 The Apache Software Foundation
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 using System;
  18 using Directory = Lucene.Net.Store.Directory;
  19 using IndexInput = Lucene.Net.Store.IndexInput;
  20 using IndexOutput = Lucene.Net.Store.IndexOutput;
  21
  22 namespace Lucene.Net.Util
  23 {
  24
  25         /// <summary>Optimized implementation of a vector of bits.  This is more-or-less like
  26         /// java.util.BitSet, but also includes the following:
  27         /// <ul>
  28         /// <li>a count() method, which efficiently computes the number of one bits;</li>
  29         /// <li>optimized read from and write to disk;</li>
  30         /// <li>inlinable get() method;</li>
  31         /// </ul>
  32         /// </summary>
  33         /// <author>  Doug Cutting
  34         /// </author>
  35         /// <version>  $Id: BitVector.cs,v 1.4 2006/10/02 17:09:10 joeshaw Exp $
  36         /// </version>
  37         public sealed class BitVector
  38         {
  39
  40                 private byte[] bits;
  41                 private int size;
  42                 private int count = - 1;
  43
  44                 /// <summary>Constructs a vector capable of holding <code>n</code> bits. </summary>
  45                 public BitVector(int n)
  46                 {
  47                         size = n;
  48                         bits = new byte[(size >> 3) + 1];
  49                 }
  50
  51                 /// <summary>Sets the value of <code>bit</code> to one. </summary>
  52                 public void  Set(int bit)
  53                 {
  54                         bits[bit >> 3] |= (byte) (1 << (bit & 7));
  55                         count = - 1;
  56                 }
  57
  58                 /// <summary>Sets the value of <code>bit</code> to zero. </summary>
  59                 public void  Clear(int bit)
  60                 {
  61                         bits[bit >> 3] &= (byte) (~ (1 << (bit & 7)));
  62                         count = - 1;
  63                 }
  64
  65                 /// <summary>Returns <code>true</code> if <code>bit</code> is one and
  66                 /// <code>false</code> if it is zero.
  67                 /// </summary>
  68                 public bool Get(int bit)
  69                 {
  70                         return (bits[bit >> 3] & (1 << (bit & 7))) != 0;
  71                 }
  72
  73                 /// <summary>Returns the number of bits in this vector.  This is also one greater than
  74                 /// the number of the largest valid bit number.
  75                 /// </summary>
  76                 public int Size()
  77                 {
  78                         return size;
  79                 }
  80
  81                 /// <summary>Returns the total number of one bits in this vector.  This is efficiently
  82                 /// computed and cached, so that, if the vector is not changed, no
  83                 /// recomputation is done for repeated calls.
  84                 /// </summary>
  85                 public int Count()
  86                 {
  87                         // if the vector has been modified
  88                         if (count == - 1)
  89                         {
  90                                 int c = 0;
  91                                 int end = bits.Length;
  92                                 for (int i = 0; i < end; i++)
  93                                         c += BYTE_COUNTS[bits[i] & 0xFF]; // sum bits per byte
  94                                 count = c;
  95                         }
  96                         return count;
  97                 }
  98
  99                 private static readonly byte[] BYTE_COUNTS = new byte[]{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
 100
 101
 102                 /// <summary>Writes this vector to the file <code>name</code> in Directory
 103                 /// <code>d</code>, in a format that can be read by the constructor {@link
 104                 /// #BitVector(Directory, String)}.
 105                 /// </summary>
 106                 public void  Write(Directory d, System.String name)
 107                 {
 108                         IndexOutput output = d.CreateOutput(name);
 109                         try
 110                         {
 111                                 output.WriteInt(Size()); // write size
 112                                 output.WriteInt(Count()); // write count
 113                                 output.WriteBytes(bits, bits.Length); // write bits
 114                         }
 115                         finally
 116                         {
 117                                 output.Close();
 118                         }
 119                 }
 120
 121                 /// <summary>Constructs a bit vector from the file <code>name</code> in Directory
 122                 /// <code>d</code>, as written by the {@link #write} method.
 123                 /// </summary>
 124                 public BitVector(Directory d, System.String name)
 125                 {
 126                         IndexInput input = d.OpenInput(name);
 127                         try
 128                         {
 129                                 size = input.ReadInt(); // read size
 130                                 count = input.ReadInt(); // read count
 131                                 bits = new byte[(size >> 3) + 1]; // allocate bits
 132                                 input.ReadBytes(bits, 0, bits.Length); // read bits
 133                         }
 134                         finally
 135                         {
 136                                 input.Close();
 137                         }
 138                 }
 139         }
 140 }