Lucene.Net  3.0.3
Lucene.Net is a .NET port of the Java Lucene Indexing Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties
FixedBitSet.cs
Go to the documentation of this file.
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 using System.Collections;
20 using Lucene.Net.Search;
21 using Lucene.Net.Util;
22 
23 namespace Lucene.Net.Spatial.Util
24 {
25  /* BitSet of fixed length (numBits), backed by accessible
26  * ({@link #getBits}) long[], accessed with an int index,
27  * implementing Bits and DocIdSet. Unlike {@link
28  * OpenBitSet} this bit set does not auto-expand, cannot
29  * handle long index, and does not have fastXX/XX variants
30  * (just X).
31  *
32  * @lucene.internal
33  **/
34  public class FixedBitSet : DocIdSet, IBits
35  {
36  private readonly BitArray bits;
37 
43  public static int bits2words(int numBits)
44  {
45  var numLong = (int)((uint)numBits >> 6);
46  if ((numBits & 63) != 0)
47  {
48  numLong++;
49  }
50  return numLong;
51  }
52 
53  public FixedBitSet(int numBits)
54  {
55  bits = new BitArray(numBits);
56  }
57 
62  public FixedBitSet(FixedBitSet other)
63  {
64  bits = new BitArray(other.bits);
65  }
66 
67  public IBits Bits()
68  {
69  return this;
70  }
71 
72  public int Length()
73  {
74  return bits.Length;
75  }
76 
77  public override bool IsCacheable
78  {
79  get { return true; }
80  }
81 
88  public int Cardinality()
89  {
90  int ret = 0;
91  for (var i = 0; i < bits.Length; i++)
92  {
93  if (bits[i]) ret++;
94  }
95  return ret;
96  }
97 
98  public bool Get(int index)
99  {
100  return bits[index];
101  }
102 
103  public void Set(int index)
104  {
105  bits.Set(index, true);
106  }
107 
108  public bool GetAndSet(int index)
109  {
110  var ret = bits[index];
111  bits.Set(index, true);
112  return ret;
113  }
114 
115  public void Clear(int index)
116  {
117  bits.Set(index, false);
118  }
119 
120  public bool GetAndClear(int index)
121  {
122  var ret = bits[index];
123  bits.Set(index, false);
124  return ret;
125  }
126 
133  public int NextSetBit(int index)
134  {
135  if (index >= bits.Length || index < 0)
136  throw new ArgumentException("Invalid index", "index");
137 
138  for (var i = index; i < bits.Length; i++)
139  {
140  if (bits[i]) return i;
141  }
142 
143  return -1;
144  }
145 
146  /* Returns the index of the last set bit before or on the index specified.
147  * -1 is returned if there are no more set bits.
148  */
149  public int PrevSetBit(int index)
150  {
151  if (index >= bits.Length || index < 0)
152  throw new ArgumentException("Invalid index", "index");
153 
154  for (var i = index; i >= 0; i--)
155  {
156  if (bits[i]) return i;
157  }
158 
159  return -1;
160  }
161 
162  /* Does in-place OR of the bits provided by the
163  * iterator. */
164  //public void Or(DocIdSetIterator iter)
165  //{
166  // if (iter is OpenBitSetIterator && iter.DocID() == -1)
167  // {
168  // var obs = (OpenBitSetIterator)iter;
169  // Or(obs.arr, obs.words);
170  // // advance after last doc that would be accepted if standard
171  // // iteration is used (to exhaust it):
172  // obs.Advance(bits.Length);
173  // }
174  // else
175  // {
176  // int doc;
177  // while ((doc = iter.NextDoc()) < bits.Length)
178  // {
179  // Set(doc);
180  // }
181  // }
182  //}
183 
184  /* this = this OR other */
185  public void Or(FixedBitSet other)
186  {
187  Or(other.bits, other.bits.Length);
188  }
189 
190  private void Or(BitArray otherArr, int otherLen)
191  {
192  var thisArr = this.bits;
193  int pos = Math.Min(thisArr.Length, otherLen);
194  while (--pos >= 0)
195  {
196  thisArr[pos] |= otherArr[pos];
197  }
198  }
199 
200  /* Does in-place AND of the bits provided by the
201  * iterator. */
202  //public void And(DocIdSetIterator iter)
203  //{
204  // if (iter is OpenBitSetIterator && iter.DocID() == -1)
205  // {
206  // var obs = (OpenBitSetIterator)iter;
207  // And(obs.arr, obs.words);
208  // // advance after last doc that would be accepted if standard
209  // // iteration is used (to exhaust it):
210  // obs.Advance(bits.Length);
211  // }
212  // else
213  // {
214  // if (bits.Length == 0) return;
215  // int disiDoc, bitSetDoc = NextSetBit(0);
216  // while (bitSetDoc != -1 && (disiDoc = iter.Advance(bitSetDoc)) < bits.Length)
217  // {
218  // Clear(bitSetDoc, disiDoc);
219  // disiDoc++;
220  // bitSetDoc = (disiDoc < bits.Length) ? NextSetBit(disiDoc) : -1;
221  // }
222  // if (bitSetDoc != -1)
223  // {
224  // Clear(bitSetDoc, bits.Length);
225  // }
226  // }
227  //}
228 
229  /* this = this AND other */
230  public void And(FixedBitSet other)
231  {
232  And(other.bits, other.bits.Length);
233  }
234 
235  private void And(BitArray otherArr, int otherLen)
236  {
237  var thisArr = this.bits;
238  int pos = Math.Min(thisArr.Length, otherLen);
239  while (--pos >= 0)
240  {
241  thisArr[pos] &= otherArr[pos];
242  }
243  if (thisArr.Length > otherLen)
244  {
245  for (var i = otherLen; i < thisArr.Length; i++)
246  {
247  thisArr[i] = false;
248  }
249  }
250  }
251 
252  /* Does in-place AND NOT of the bits provided by the
253  * iterator. */
254  //public void AndNot(DocIdSetIterator iter)
255  //{
256  // var obs = iter as OpenBitSetIterator;
257  // if (obs != null && iter.DocID() == -1)
258  // {
259  // AndNot(obs.arr, obs.words);
260  // // advance after last doc that would be accepted if standard
261  // // iteration is used (to exhaust it):
262  // obs.Advance(bits.Length);
263  // }
264  // else
265  // {
266  // int doc;
267  // while ((doc = iter.NextDoc()) < bits.Length)
268  // {
269  // Clear(doc);
270  // }
271  // }
272  //}
273 
274  /* this = this AND NOT other */
275  public void AndNot(FixedBitSet other)
276  {
277  AndNot(other.bits, other.bits.Length);
278  }
279 
280  private void AndNot(BitArray otherArr, int otherLen)
281  {
282  var thisArr = this.bits;
283  int pos = Math.Min(thisArr.Length, otherLen);
284  while (--pos >= 0)
285  {
286  thisArr[pos] &= !otherArr[pos];
287  }
288  }
289 
290  // NOTE: no .isEmpty() here because that's trappy (ie,
291  // typically isEmpty is low cost, but this one wouldn't
292  // be)
293 
294  /* Flips a range of bits
295  *
296  * @param startIndex lower index
297  * @param endIndex one-past the last bit to flip
298  */
299  // public void Flip(int startIndex, int endIndex) {
300  // Debug.Assert(startIndex >= 0 && startIndex < numBits);
301  // Debug.Assert(endIndex >= 0 && endIndex <= numBits);
302  // if (endIndex <= startIndex) {
303  // return;
304  // }
305 
306  // int startWord = startIndex >> 6;
307  // int endWord = (endIndex-1) >> 6;
308 
309  // /* Grrr, java shifting wraps around so -1L>>>64 == -1
310  // * for that reason, make sure not to use endmask if the bits to flip will
311  // * be zero in the last word (redefine endWord to be the last changed...)
312  // long startmask = -1L << (startIndex & 0x3f); // example: 11111...111000
313  // long endmask = -1L >>> (64-(endIndex & 0x3f)); // example: 00111...111111
314  // ***/
315 
316  // long startmask = -1L << startIndex;
317  // long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
318 
319  // if (startWord == endWord) {
320  // bits[startWord] ^= (startmask & endmask);
321  // return;
322  // }
323 
324  // bits[startWord] ^= startmask;
325 
326  // for (var i=startWord+1; i<endWord; i++) {
327  // bits[i] = ~bits[i];
328  // }
329 
330  // bits[endWord] ^= endmask;
331  //}
332 
333  /* Sets a range of bits
334  *
335  * @param startIndex lower index
336  * @param endIndex one-past the last bit to set
337  */
338  public void Set(int startIndex, int endIndex)
339  {
340  // Naive implementation
341  for (int i = startIndex; i < endIndex; i++)
342  {
343  Set(i);
344  }
345  }
346 
347  // public void Set(int startIndex, int endIndex) {
348  // Debug.Assert(startIndex >= 0 && startIndex < numBits);
349  // Debug.Assert(endIndex >= 0 && endIndex <= numBits);
350  // if (endIndex <= startIndex) {
351  // return;
352  // }
353 
354  // int startWord = startIndex >> 6;
355  // int endWord = (endIndex-1) >> 6;
356 
357  // long startmask = -1L << startIndex;
358  // long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
359 
360  // if (startWord == endWord) {
361  // bits[startWord] |= (startmask & endmask);
362  // return;
363  // }
364 
365  // bits[startWord] |= startmask;
366  // Arrays.Fill(bits, startWord+1, endWord, -1L);
367  // bits[endWord] |= endmask;
368  //}
369 
370  /* Clears a range of bits.
371  *
372  * @param startIndex lower index
373  * @param endIndex one-past the last bit to clear
374  */
375  public void Clear(int startIndex, int endIndex)
376  {
377  for (int i = startIndex; i < endIndex; i++)
378  {
379  Clear(i);
380  }
381  }
382 
383  //@Override
384  public FixedBitSet Clone()
385  {
386  return new FixedBitSet(this);
387  }
388 
389  /* returns true if both sets have the same bits set */
390  public override bool Equals(Object o)
391  {
392  if (this == o)
393  {
394  return true;
395  }
396 
397  var other = o as FixedBitSet;
398  if (other == null)
399  {
400  return false;
401  }
402 
403  return bits.Equals(other.bits);
404  }
405 
406  public override int GetHashCode()
407  {
408  return bits.GetHashCode();
409  }
410 
411  public override DocIdSetIterator Iterator()
412  {
413  return new FixedBitSetIterator(this);
414  }
415 
420  {
421  private int curDocId = -1;
422  private readonly IEnumerator enumerator;
423 
425  {
426  enumerator = bitset.bits.GetEnumerator();
427  }
428 
429  public override int DocID()
430  {
431  return curDocId;
432  }
433 
434  public override int NextDoc()
435  {
436  while (enumerator.MoveNext())
437  {
438  ++curDocId;
439  if ((bool)enumerator.Current) return curDocId;
440  }
441  return curDocId = NO_MORE_DOCS;
442  }
443 
444  public override int Advance(int target)
445  {
446  int doc;
447  while ((doc = NextDoc()) < target)
448  {
449  }
450  return doc;
451  }
452  }
453  }
454 }