BitSet


1   /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2    * This file is part of Beaver Parser Generator.                       *
3    * Copyright (C) 2003,2004 Alexander Demenchuk <alder@softanvil.com>.  *
4    * All rights reserved.                                                *
5    * See the file "LICENSE" for the terms and conditions for copying,    *
6    * distribution and modification of Beaver.                            *
7    * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
8   
9   package beaver.comp.util;
10  
11  /**
12   * A set for elements 0..N
13   */
14  public class BitSet
15  {
16      private int[] bit_bags;
17      private boolean has_bits;
18  
19      public BitSet(int capacity_in_bits)
20      {
21          bit_bags = new int[(capacity_in_bits + 31) >> 5];
22      }
23  
24      public BitSet()
25      {
26          this(256);
27      }
28  
29      /**
30       * Adds a new element to the set.
31       *
32       * @param i element to add to the set
33       * @return true if element was added and false if it was already there
34       */
35      public boolean add(int i)
36      {
37          int bag_index = i >> 5;
38          ensureIndexWithinRange(bag_index);
39          int bit_index = i & 31;
40          int bit_mask = 1 << bit_index;
41          boolean bit_not_set = (bit_bags[bag_index] & bit_mask) == 0;
42          if (bit_not_set)
43          {
44              bit_bags[bag_index] |= bit_mask;
45              has_bits = true;
46          }
47          return bit_not_set;
48      }
49  
50      /**
51       * Adds every element of another set to this set.
52       *
53       * @param another_set set of elements to be added to this set
54       * @return true if this set has new bits added
55       */
56      public boolean add(BitSet another_set)
57      {
58          boolean new_bits_added = false;
59          if (another_set.has_bits)
60          {
61              int cmp_len = another_set.bit_bags.length;
62              if (cmp_len > bit_bags.length)
63                  expandCapacity(cmp_len);
64              for (int i = 0; i < cmp_len; i++)
65              {
66                  int diff = another_set.bit_bags[i] & ~bit_bags[i];
67                  if (diff != 0)
68                  {
69                      bit_bags[i] |= diff;
70                      has_bits = new_bits_added = true;
71                  }
72              }
73          }
74          return new_bits_added;
75      }
76  
77      /**
78       * Checks whether the element is in the set
79       *
80       * @param i element to check
81       * @return true if the element is present in the set
82       */
83      public boolean isSet(int i)
84      {
85          return has_bits && (bit_bags[i >> 5] & (1 << (i & 31))) != 0;
86      }
87  
88      /**
89       * Checks whether the set has no set bits.
90       *
91       * @return true if all the bits of the set are cleared
92       */
93      public boolean isEmpty()
94      {
95          return !has_bits;
96      }
97  
98      /**
99       * An API that a "bit processor" has to implement.
100      */
101     public static abstract class Processor
102     {
103         /**
104          * A callback. BitSet calls this method for each bit that meets a selection criteria.
105          *
106          * @param bit_index index of s set bit
107          */
108         protected abstract void process(int bit_index);
109     }
110 
111     /**
112      * Invokes a bit processor for each set bit in the set.
113      *
114      * @param proc an action implmentation to be called
115      */
116     public void forEachElementRun(Processor proc)
117     {
118         if (has_bits)
119         {
120             for (int bag_index = 0; bag_index < bit_bags.length; bag_index++)
121             {
122                 for (int bit_index = bag_index << 5, bag = bit_bags[bag_index]; bag != 0; bag >>>= 1, bit_index++)
123                 {
124                     if ((bag & 0x0001) == 0)
125                     {
126                         if ((bag & 0xFFFF) == 0)
127                         {
128                             bit_index += 16;
129                             bag >>>= 16;
130                         }
131                         if ((bag & 0x00FF) == 0)
132                         {
133                             bit_index += 8;
134                             bag >>>= 8;
135                         }
136                         if ((bag & 0x000F) == 0)
137                         {
138                             bit_index += 4;
139                             bag >>>= 4;
140                         }
141                         if ((bag & 0x0003) == 0)
142                         {
143                             bit_index += 2;
144                             bag >>>= 2;
145                         }
146                         if ((bag & 0x0001) == 0)
147                         {
148                             bit_index += 1;
149                             bag >>>= 1;
150                         }
151                     }
152                     proc.process(bit_index);
153                 }
154             }
155         }
156     }
157 
158     /**
159      * Checks that a bag index points within the allocated array of bit bags.
160      *
161      * @param bag_index index of the bit bag
162      */
163     private void ensureIndexWithinRange(int bag_index)
164     {
165         if (bag_index >= bit_bags.length)
166         {
167             if (bag_index > 0xFFFF)
168                 throw new IllegalArgumentException  ("huge bit sets (more than 2M bits) are not supported");
169             // they can easily be supported (with one extra shift below) though, but in the context of
170             // a parser generator it does not make a lot of sence
171 
172             // calculate a new size for the bit bags array as the next pow(2) after a bag_index
173             int new_length = bag_index | bag_index >> 1;
174 
175             new_length |= new_length >> 2;
176             new_length |= new_length >> 4;
177             new_length |= new_length >> 8;
178 
179             expandCapacity(new_length + 1);
180         }
181     }
182 
183     /**
184      * Expands an array of bags to the new size.
185      *
186      * @param new_length new number of bit bags to use
187      */
188     private void expandCapacity(int new_length)
189     {
190         int[] new_bags = new int[new_length];
191         System.arraycopy(bit_bags, 0, new_bags, 0, bit_bags.length);
192         bit_bags = new_bags;
193     }
194 }
195
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags