antlr.v4.runtime.misc.BitSet source code

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