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 using System;
  17 using Directory = Lucene.Net.Store.Directory;
  18 using InputStream = Lucene.Net.Store.InputStream;
  19 using OutputStream = Lucene.Net.Store.OutputStream;
  20 namespace Lucene.Net.Util
  21 {
  22
  23         /// <summary>Optimized implementation of a vector of bits.  This is more-or-less like
  24         /// java.util.BitSet, but also includes the following:
  25         /// <ul>
  26         /// <li>a count() method, which efficiently computes the number of one bits;</li>
  27         /// <li>optimized read from and write to disk;</li>
  28         /// <li>inlinable get() method;</li>
  29         /// </ul>
  30         /// </summary>
  31         /// <author>  Doug Cutting
  32         /// </author>
  33         /// <version>  $Id: BitVector.cs,v 1.2 2005/01/17 19:54:32 joeshaw Exp $
  34         /// </version>
  35         public sealed class BitVector
  36         {
  37
  38                 private byte[] bits;
  39                 private int size;
  40                 private int count = - 1;
  41
  42                 /// <summary>Constructs a vector capable of holding <code>n</code> bits. </summary>
  43                 public BitVector(int n)
  44                 {
  45                         size = n;
  46                         bits = new byte[(size >> 3) + 1];
  47                 }
  48
  49                 /// <summary>Sets the value of <code>bit</code> to one. </summary>
  50                 public void  Set(int bit)
  51                 {
  52                         bits[bit >> 3] |= (byte) (1 << (bit & 7));
  53                         count = - 1;
  54                 }
  55
  56                 /// <summary>Sets the value of <code>bit</code> to zero. </summary>
  57                 public void  Clear(int bit)
  58                 {
  59                         bits[bit >> 3] &= (byte) ~ (1 << (bit & 7));
  60                         count = - 1;
  61                 }
  62
  63                 /// <summary>Returns <code>true</code> if <code>bit</code> is one and
  64                 /// <code>false</code> if it is zero.
  65                 /// </summary>
  66                 public bool Get(int bit)
  67                 {
  68                         return (bits[bit >> 3] & (1 << (bit & 7))) != 0;
  69                 }
  70
  71                 /// <summary>Returns the number of bits in this vector.  This is also one greater than
  72                 /// the number of the largest valid bit number.
  73                 /// </summary>
  74                 public int Size()
  75                 {
  76                         return size;
  77                 }
  78
  79                 /// <summary>Returns the total number of one bits in this vector.  This is efficiently
  80                 /// computed and cached, so that, if the vector is not changed, no
  81                 /// recomputation is done for repeated calls.
  82                 /// </summary>
  83                 public int Count()
  84                 {
  85                         // if the vector has been modified
  86                         if (count == - 1)
  87                         {
  88                                 int c = 0;
  89                                 int end = bits.Length;
  90                                 for (int i = 0; i < end; i++)
  91                                         c += BYTE_COUNTS[bits[i] & 0xFF]; // sum bits per byte
  92                                 count = c;
  93                         }
  94                         return count;
  95                 }
  96
  97                 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};
  98
  99
 100                 /// <summary>Writes this vector to the file <code>name</code> in Directory
 101                 /// <code>d</code>, in a format that can be read by the constructor {@link
 102                 /// #BitVector(Directory, String)}.
 103                 /// </summary>
 104                 public void  Write(Directory d, System.String name)
 105                 {
 106                         OutputStream output = d.CreateFile(name);
 107                         try
 108                         {
 109                                 output.WriteInt(Size()); // write size
 110                                 output.WriteInt(Count()); // write count
 111                                 output.WriteBytes(bits, bits.Length); // write bits
 112                         }
 113                         finally
 114                         {
 115                                 output.Close();
 116                         }
 117                 }
 118
 119                 /// <summary>Constructs a bit vector from the file <code>name</code> in Directory
 120                 /// <code>d</code>, as written by the {@link #write} method.
 121                 /// </summary>
 122                 public BitVector(Directory d, System.String name)
 123                 {
 124                         InputStream input = d.OpenFile(name);
 125                         try
 126                         {
 127                                 size = input.ReadInt(); // read size
 128                                 count = input.ReadInt(); // read count
 129                                 bits = new byte[(size >> 3) + 1]; // allocate bits
 130                                 input.ReadBytes(bits, 0, bits.Length); // read bits
 131                         }
 132                         finally
 133                         {
 134                                 input.Close();
 135                         }
 136                 }
 137         }
 138 }