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 }