antlr.v4.runtime.misc.BitSet source code

1 /*
2  * Copyright (c) 2012-2020 The ANTLR Project. All rights reserved.
3  * Use of this file is governed by the BSD 3-clause license that
4  * can be found in the LICENSE.txt file in the project root.
5  */
6 
7 module antlr.v4.runtime.misc.BitSet;
8 
9 import std.algorithm;
10 import std.bitmanip;
11 import std.conv;
12 import std.format : format;
13 
14 /**
15  * This struct implements a vector of bits that grows as needed. Each component
16  * of the bit set has a bool value. The bits of a BitSet are indexed by nonnegative integers.
17  * Individual indexed bits can be examined, set, or cleared. One BitSet may be used to modify
18  * the contents of another BitSet through logical AND, logical inclusive OR,
19  * and logical exclusive OR operations.
20  *
21  * By default, all bits in the set initially have the value false.
22  */
23 struct BitSet
24 {
25 
26     private BitArray bitSet;
27 
28     public this(BitArray bitArray)
29     {
30         this.bitSet = bitArray;
31     }
32 
33     public this(size_t initialSize)
34     {
35         this.bitSet.length = initialSize;
36     }
37 
38     public size_t length()
39     {
40         return bitSet.length;
41     }
42 
43     public auto cardinality()
44     {
45         int res;
46         bitSet.each!(v => res += to!int(v));
47         return res;
48     }
49 
50     public int nextSetBit(int fromIndex)
51     {
52         foreach (i, el; bitSet)
53         {
54             if (i > fromIndex && el == true)
55                 return to!int(i);
56         }
57         return -1;
58     }
59 
60     public void set(int bitIndex, bool value)
61     {
62         if (bitSet.length <= bitIndex)
63             bitSet.length = bitIndex + 16; // dynamic array need more space
64         bitSet[bitIndex] = value;
65     }
66 
67     /**
68      * @uml
69      * @nothrow
70      */
71     public bool get(int bitIndex) nothrow
72     in
73     {
74         assert(bitSet.length > bitIndex);
75     }
76     do
77     {
78         return bitSet[bitIndex];
79     }
80 
81     public bool isEmpty()
82     {
83         return cardinality == 0;
84     }
85 
86     public string toString()
87     {
88         if (bitSet.length)
89         {
90             string res;
91             foreach (j, b; bitSet)
92             {
93                 if (b == true)
94                 {
95                     res ~= to!string(j) ~ ", ";
96                 }
97             }
98             return format!"{%s}"(res[0 .. $ - 2]);
99         }
100         else
101             return "{}";
102     }
103 
104     /**
105      * @uml
106      * @trusted
107      */
108     public size_t toHash() @trusted
109     {
110         size_t hash;
111         foreach (el; bitSet)
112             hash = (hash * 9) + el;
113         return hash;
114     }
115 
116     /**
117      * @uml
118      * @const
119      * @pure
120      * @nothrow
121      */
122     public bool opEquals(ref const BitSet bitSet) const pure nothrow
123     {
124         return this.bitSet == bitSet.bitSet;
125     }
126 
127     public void clear()
128     {
129         bitSet.length(0);
130     }
131 
132     public BitSet or(BitSet bits)
133     {
134         BitSet result;
135         auto maxLenght = max(this.bitSet.length, bits.bitSet.length);
136         if (this.bitSet.length < maxLenght)
137             this.bitSet.length = maxLenght;
138         else if (bits.values.length < maxLenght)
139             bits.values.length = maxLenght;
140         result.bitSet = this.bitSet | bits.bitSet;
141         return result;
142     }
143 
144     public string toIndexString()
145     {
146         import std.conv;
147         import std.array : join;
148 
149         string[] res;
150         int index;
151         foreach (i, el; bitSet)
152         {
153             if (el)
154                 res ~= to!string(i);
155         }
156         return "{" ~ join(res, ",") ~ "}";
157     }
158 
159     public BitArray values()
160     {
161         return bitSet;
162     }
163 
164     public void dup(BitSet old)
165     {
166         this.bitSet = old.bitSet.dup;
167     }
168 
169 }