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 // Struct BitSet
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         import std.format : format;
88         return format("%b", bitSet);
89     }
90 
91     /**
92      * @uml
93      * @trusted
94      */
95     public size_t toHash() @trusted
96     {
97         size_t hash;
98         foreach (el; bitSet)
99             hash = (hash * 9) + el;
100         return hash;
101     }
102 
103     /**
104      * @uml
105      * @const
106      * @pure
107      * @nothrow
108      */
109     public bool opEquals(ref const BitSet bitSet) const pure nothrow
110     {
111         return this.bitSet == bitSet.bitSet;
112     }
113 
114     public void clear()
115     {
116         bitSet.length(0);
117     }
118 
119     public BitSet or(BitSet bits)
120     {
121         BitSet result;
122         auto maxLenght = max(this.bitSet.length, bits.bitSet.length);
123         if (this.bitSet.length < maxLenght)
124             this.bitSet.length = maxLenght;
125         else
126             if (bits.values.length < maxLenght)
127                 bits.values.length = maxLenght;
128         result.bitSet = this.bitSet | bits.bitSet;
129         return result;
130     }
131 
132     public string toIndexString()
133     {
134         import std.conv;
135         import std.array : join;
136         string[] res;
137         int index;
138         foreach(i, el; bitSet)
139         {
140             if(el)
141                 res ~= to!string(i);
142         }
143         return "{" ~ join(res, ",") ~ "}";
144     }
145 
146     public BitArray values()
147     {
148         return bitSet;
149     }
150 
151     public void dup(BitSet old)
152     {
153         this.bitSet = old.bitSet.dup;
154     }
155 
156 }