tango.util.container.more.BitSet source code

1 /*******************************************************************************
2 
3         copyright:      Copyright (c) 2009 Kris Bell. All rights reserved
4 
5         license:        BSD style: $(LICENSE)
6 
7         version:        Sept 2009: Initial release
8 
9         since:          0.99.9
10 
11         author:         Kris
12 
13 *******************************************************************************/
14 
15 module tango.util.container.more.BitSet;
16 
17 private import core.bitop;
18 
19 /******************************************************************************
20 
21         A fixed or dynamic set of bits. Note that this does no memory 
22         allocation of its own when Size != 0, and does heap allocation 
23         when Size is zero. Thus you can have a fixed-size low-overhead 
24         'instance, or a heap oriented instance. The latter has support
25         for resizing, whereas the former does not.
26 
27         Note that leveraging intrinsics is slower when using dmd ...
28 
29 ******************************************************************************/
30 
31 struct BitSet (int Count=0) 
32 {               
33         private enum           width = size_t.sizeof * 8;
34         
35         const bool opBinary(immutable(char)[] s : "&")(size_t i)
36         {
37             return and(i);
38         }
39         
40         void opOpAssign(immutable(char)[] s : "|")(size_t i)
41         {
42             or(i);
43         }
44         
45         void opOpAssign(immutable(char)[] s : "^")(size_t i)
46         {
47             xor(i);
48         }
49 
50         static if (Count == 0)
51                    private size_t[] bits;
52                else
53                   private size_t [(Count+width-1)/width] bits;
54 
55         /**********************************************************************
56 
57                 Set the indexed bit, resizing as necessary for heap-based
58                 instances (IndexOutOfBounds for statically-sized instances)
59 
60         **********************************************************************/
61 
62         void add (size_t i)
63         {
64                 static if (Count == 0)
65                            size (i);
66                 or (i);
67         }
68 
69         /**********************************************************************
70 
71                 Test whether the indexed bit is enabled 
72 
73         **********************************************************************/
74 
75         const bool has (size_t i)
76         {
77                 auto idx = i / width;
78                 return idx < bits.length && (bits[idx] & (1 << (i % width))) != 0;
79                 //return idx < bits.length && bt(&bits[idx], i % width) != 0;
80         }
81 
82         /**********************************************************************
83 
84                 Like get() but a little faster for when you know the range
85                 is valid
86 
87         **********************************************************************/
88 
89         const bool and (size_t i)
90         {
91                 return (bits[i / width] & (1 << (i % width))) != 0;
92                 //return bt(&bits[i / width], i % width) != 0;
93         }
94 
95         /**********************************************************************
96 
97                 Turn on an indexed bit
98 
99         **********************************************************************/
100 
101         void or (size_t i)
102         {
103                 bits[i / width] |= (1 << (i % width));
104                 //bts (&bits[i / width], i % width);
105         }
106         
107         /**********************************************************************
108 
109                 Invert an indexed bit
110 
111         **********************************************************************/
112 
113         void xor (size_t i)
114         {
115                 bits[i / width] ^= (1 << (i % width));
116                 //btc (&bits[i / width], i % width);
117         }
118         
119         /**********************************************************************
120 
121                 Clear an indexed bit
122 
123         **********************************************************************/
124 
125         void clr (size_t i)
126         {
127                 bits[i / width] &= ~(1 << (i % width));
128                 //btr (&bits[i / width], i % width);
129         }
130 
131         /**********************************************************************
132 
133                 Clear all bits
134 
135         **********************************************************************/
136 
137         BitSet* clr ()
138         {
139                 bits[] = 0;
140                 return &this;
141         }
142         
143         /**********************************************************************
144 
145                 Clone this BitSet and return it
146 
147         **********************************************************************/
148 
149         @property const BitSet dup ()
150         {
151                 BitSet x;
152                 static if (Count == 0)
153                            x.bits.length = this.bits.length;
154                 x.bits[] = bits[];
155                 return x;
156         }
157 
158         /**********************************************************************
159 
160                 Return the number of bits we have room for
161 
162         **********************************************************************/
163 
164         @property const size_t size ()
165         {
166                 return width * bits.length;
167         }
168 
169         /**********************************************************************
170 
171                 Expand to include the indexed bit (dynamic only)
172 
173         **********************************************************************/
174 
175         static if (Count == 0) BitSet* size (size_t i)
176         {
177                 i = i / width;
178                 if (i >= bits.length)
179                     bits.length = i + 1;
180                 return &this;
181         }
182 }