BitMap


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: BitMap.java,v 1.5 2006/10/30 21:14:28 bostic Exp $
7    */
8   
9   package com.sleepycat.je.utilint;
10  
11  import java.util.BitSet  ;
12  import java.util.HashMap  ;
13  import java.util.Iterator  ;
14  import java.util.Map  ;
15  
16  /**
17   * Bitmap which supports indexing with long arguments. java.util.BitSet
18   * provides all the functionality and performance we need, but requires integer
19   * indexing.
20   *
21   * Long indexing is implemented by keeping a Map of java.util.BitSets, where
22   * each bitset covers 2^16 bits worth of values. The Bitmap may be sparse, in
23   * that each segment is only instantiated when needed.
24   *
25   * Note that this class is currently not thread safe; adding a new bitset
26   * segment is not protected.
27   */
28  public class BitMap {
29  
30      private static final int SEGMENT_SIZE = 16;
31      private static final int SEGMENT_MASK = 0xffff;
32  
33      /* 
34       * Map of segment value -> bitset, where the segment value is index >>16
35       */
36      private Map   bitSegments;
37  
38      public BitMap() {
39          bitSegments = new HashMap  ();
40      }
41  
42      /*
43       * @throws IndexOutOfBoundsException if index is negative.
44       */
45      public void set(long index)
46          throws IndexOutOfBoundsException   {
47  
48          if (index < 0) {
49              throw new IndexOutOfBoundsException  (index + " is negative.");
50          }
51          
52          BitSet   bitset = getBitSet(index, true);
53      if (bitset == null) {
54          throw new IllegalArgumentException  (index + " is out of bounds");
55      }
56          int useIndex = getIntIndex(index);
57          bitset.set(useIndex);
58      }
59  
60      /*
61       * @throws IndexOutOfBoundsException if index is negative.
62       */
63      public boolean get(long index) 
64          throws IndexOutOfBoundsException   {
65  
66          if (index < 0) {
67              throw new IndexOutOfBoundsException  (index + " is negative.");
68          }
69  
70          BitSet   bitset = getBitSet(index, false);
71          if (bitset == null) {
72              return false;
73          }
74  
75          int useIndex = getIntIndex(index);
76          return bitset.get(useIndex);
77      }
78  
79      /* 
80       * Since the BitMap is implemented by a collection of BitSets, return
81       * the one which covers the numeric range for this index.
82       *
83       * @param index the bit we want to access
84       * @param allowCreate if true, return the BitSet that would hold this
85       * index even if it wasn't previously set. If false, return null
86       * if the bit has not been set.
87       */
88      private BitSet   getBitSet(long index, boolean allowCreate) {
89  
90          Long   segmentId = new Long  (index >> SEGMENT_SIZE);
91  
92          BitSet   bitset = (BitSet  ) bitSegments.get(segmentId);
93          if (allowCreate) {
94              if (bitset == null) {
95                  bitset = new BitSet  ();
96                  bitSegments.put(segmentId, bitset);
97              }
98          }
99  
100         return bitset;
101     }
102 
103     private int getIntIndex(long index) {
104         return (int) (index & SEGMENT_MASK);
105     }
106 
107     /* For unit testing. */
108     int getNumSegments() {
109         return bitSegments.size();
110     }
111 
112     /* 
113      * Currently for unit testing, though note that java.util.BitSet does
114      * support cardinality().
115      */
116     int cardinality() {
117         int count = 0;
118         Iterator   iter = bitSegments.values().iterator();
119         while (iter.hasNext()) {
120             BitSet   b = (BitSet  ) iter.next();
121             count += b.cardinality();
122         }
123         return count;
124     }
125 }
126
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags