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             if (i > fromIndex && el == true)
54                 return to!int(i);
55         }
56         return -1;
57     }
58 
59     public void set(int bitIndex, bool value)
60     {
61         if (bitSet.length <= bitIndex)
62             bitSet.length = bitIndex + 16; // dynamic array need more space
63         bitSet[bitIndex] = value;
64     }
65 
66     /**
67      * @uml
68      * @nothrow
69      */
70     public bool get(int bitIndex) nothrow
71     in
72     {
73         assert(bitSet.length > bitIndex);
74     }
75     do
76     {
77         return bitSet[bitIndex];
78     }
79 
80     public bool isEmpty()
81     {
82         return cardinality == 0;
83     }
84 
85     public string toString()
86     {
87         if (bitSet.length)
88         {
89             string res;
90             foreach (j, b; bitSet)
91             {
92                 if (b == true)
93                 {
94                     res ~= to!string(j) ~ ", ";
95                 }
96             }
97             return format!"{%s}"(res[0 .. $-2]);
98         }
99         else
100             return "{}";
101     }
102 
103     /**
104      * @uml
105      * @trusted
106      */
107     public size_t toHash() @trusted
108     {
109         size_t hash;
110         foreach (el; bitSet)
111             hash = (hash * 9) + el;
112         return hash;
113     }
114 
115     /**
116      * @uml
117      * @const
118      * @pure
119      * @nothrow
120      */
121     public bool opEquals(ref const BitSet bitSet) const pure nothrow
122     {
123         return this.bitSet == bitSet.bitSet;
124     }
125 
126     public void clear()
127     {
128         bitSet.length(0);
129     }
130 
131     public BitSet or(BitSet bits)
132     {
133         BitSet result;
134         auto maxLenght = max(this.bitSet.length, bits.bitSet.length);
135         if (this.bitSet.length < maxLenght)
136             this.bitSet.length = maxLenght;
137         else
138             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         string[] res;
149         int index;
150         foreach(i, el; bitSet)
151         {
152             if(el)
153                 res ~= to!string(i);
154         }
155         return "{" ~ join(res, ",") ~ "}";
156     }
157 
158     public BitArray values()
159     {
160         return bitSet;
161     }
162 
163     public void dup(BitSet old)
164     {
165         this.bitSet = old.bitSet.dup;
166     }
167 
168 }