KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > lucene > util > BitVector


1 package org.apache.lucene.util;
2
3 /**
4  * Copyright 2004 The Apache Software Foundation
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */
18
19 import java.io.IOException JavaDoc;
20
21 import org.apache.lucene.store.Directory;
22 import org.apache.lucene.store.IndexInput;
23 import org.apache.lucene.store.IndexOutput;
24
25 /** 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
33   @author Doug Cutting
34   @version $Id: BitVector.java 150536 2004-09-28 18:15:52Z cutting $
35   */
36 public final class BitVector {
37
38   private byte[] bits;
39   private int size;
40   private int count = -1;
41
42   /** Constructs a vector capable of holding <code>n</code> bits. */
43   public BitVector(int n) {
44     size = n;
45     bits = new byte[(size >> 3) + 1];
46   }
47
48   /** Sets the value of <code>bit</code> to one. */
49   public final void set(int bit) {
50     bits[bit >> 3] |= 1 << (bit & 7);
51     count = -1;
52   }
53
54   /** Sets the value of <code>bit</code> to zero. */
55   public final void clear(int bit) {
56     bits[bit >> 3] &= ~(1 << (bit & 7));
57     count = -1;
58   }
59
60   /** Returns <code>true</code> if <code>bit</code> is one and
61     <code>false</code> if it is zero. */
62   public final boolean get(int bit) {
63     return (bits[bit >> 3] & (1 << (bit & 7))) != 0;
64   }
65
66   /** Returns the number of bits in this vector. This is also one greater than
67     the number of the largest valid bit number. */
68   public final int size() {
69     return size;
70   }
71
72   /** Returns the total number of one bits in this vector. This is efficiently
73     computed and cached, so that, if the vector is not changed, no
74     recomputation is done for repeated calls. */
75   public final int count() {
76     // if the vector has been modified
77 if (count == -1) {
78       int c = 0;
79       int end = bits.length;
80       for (int i = 0; i < end; i++)
81         c += BYTE_COUNTS[bits[i] & 0xFF]; // sum bits per byte
82 count = c;
83     }
84     return count;
85   }
86
87   private static final byte[] BYTE_COUNTS = { // table of bits/byte
88 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
89     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
90     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
91     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
92     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
93     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
94     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
95     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
96     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
97     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
98     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
99     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
100     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
101     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
102     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
103     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
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 JavaDoc name) throws IOException JavaDoc {
111     IndexOutput output = d.createOutput(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 JavaDoc name) throws IOException JavaDoc {
125     IndexInput input = d.openInput(name);
126     try {
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 } finally {
132       input.close();
133     }
134   }
135
136 }
137
Popular Tags