ocean.util.container.more.BitSet source code

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