BitVector.java
001 package gate.creole.annic.apache.lucene.util;
002 
003 /**
004  * Copyright 2004 The Apache Software Foundation
005  *
006  * Licensed under the Apache License, Version 2.0 (the "License");
007  * you may not use this file except in compliance with the License.
008  * You may obtain a copy of the License at
009  *
010  *     http://www.apache.org/licenses/LICENSE-2.0
011  *
012  * Unless required by applicable law or agreed to in writing, software
013  * distributed under the License is distributed on an "AS IS" BASIS,
014  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015  * See the License for the specific language governing permissions and
016  * limitations under the License.
017  */
018 
019 import java.io.IOException;
020 
021 import gate.creole.annic.apache.lucene.store.Directory;
022 import gate.creole.annic.apache.lucene.store.InputStream;
023 import gate.creole.annic.apache.lucene.store.OutputStream;
024 
025 /** Optimized implementation of a vector of bits.  This is more-or-less like
026   java.util.BitSet, but also includes the following:
027   <ul>
028   <li>a count() method, which efficiently computes the number of one bits;</li>
029   <li>optimized read from and write to disk;</li>
030   <li>inlinable get() method;</li>
031   </ul>
032 
033   @author Doug Cutting
034   @version $Id: BitVector.java 529 2004-10-05 11:55:26Z niraj $
035   */
036 public final class BitVector {
037 
038   private byte[] bits;
039   private int size;
040   private int count = -1;
041 
042   /** Constructs a vector capable of holding <code>n</code> bits. */
043   public BitVector(int n) {
044     size = n;
045     bits = new byte[(size >> 31];
046   }
047 
048   /** Sets the value of <code>bit</code> to one. */
049   public final void set(int bit) {
050     bits[bit >> 3|= << (bit & 7);
051     count = -1;
052   }
053 
054   /** Sets the value of <code>bit</code> to zero. */
055   public final void clear(int bit) {
056     bits[bit >> 3&= ~(<< (bit & 7));
057     count = -1;
058   }
059 
060   /** Returns <code>true</code> if <code>bit</code> is one and
061     <code>false</code> if it is zero. */
062   public final boolean get(int bit) {
063     return (bits[bit >> 3(<< (bit & 7))) != 0;
064   }
065 
066   /** Returns the number of bits in this vector.  This is also one greater than
067     the number of the largest valid bit number. */
068   public final int size() {
069     return size;
070   }
071 
072   /** Returns the total number of one bits in this vector.  This is efficiently
073     computed and cached, so that, if the vector is not changed, no
074     recomputation is done for repeated calls. */
075   public final int count() {
076     // if the vector has been modified
077     if (count == -1) {
078       int c = 0;
079       int end = bits.length;
080       for (int i = 0; i < end; i++)
081         c += BYTE_COUNTS[bits[i0xFF];    // sum bits per byte
082       count = c;
083     }
084     return count;
085   }
086 
087   private static final byte[] BYTE_COUNTS = {    // table of bits/byte
088     0112122312232334,
089     1223233423343445,
090     1223233423343445,
091     2334344534454556,
092     1223233423343445,
093     2334344534454556,
094     2334344534454556,
095     3445455645565667,
096     1223233423343445,
097     2334344534454556,
098     2334344534454556,
099     3445455645565667,
100     2334344534454556,
101     3445455645565667,
102     3445455645565667,
103     4556566756676778
104   };
105 
106 
107   /** Writes this vector to the file <code>name</code> in Directory
108     <code>d</code>, in a format that can be read by the constructor {@link
109     #BitVector(Directory, String)}.  */
110   public final void write(Directory d, String namethrows IOException {
111     OutputStream output = d.createFile(name);
112     try {
113       output.writeInt(size());        // write size
114       output.writeInt(count());        // write count
115       output.writeBytes(bits, bits.length);    // write bits
116     finally {
117       output.close();
118     }
119   }
120 
121   /** Constructs a bit vector from the file <code>name</code> in Directory
122     <code>d</code>, as written by the {@link #write} method.
123     */
124   public BitVector(Directory d, String namethrows IOException {
125     InputStream input = d.openFile(name);
126     try {
127       size = input.readInt();        // read size
128       count = input.readInt();        // read count
129       bits = new byte[(size >> 31];      // allocate bits
130       input.readBytes(bits, 0, bits.length);    // read bits
131     finally {
132       input.close();
133     }
134   }
135 
136 }