bio.core.tinymap source code

1 /*
2     This file is part of BioD.
3     Copyright (C) 2012    Artem Tarasov <lomereiter@gmail.com>
4 
5     Permission is hereby granted, free of charge, to any person obtaining a
6     copy of this software and associated documentation files (the "Software"),
7     to deal in the Software without restriction, including without limitation
8     the rights to use, copy, modify, merge, publish, distribute, sublicense,
9     and/or sell copies of the Software, and to permit persons to whom the
10     Software is furnished to do so, subject to the following conditions:
11     
12     The above copyright notice and this permission notice shall be included in
13     all copies or substantial portions of the Software.
14     
15     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16     IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17     FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18     AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19     LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21     DEALINGS IN THE SOFTWARE.
22 
23 */
24 module bio.core.tinymap;
25 
26 private import std.algorithm;
27 private import std.range;
28 private import std.traits;
29 
30 import std.bitmanip;
31 
32 /// Efficient dictionary for cases when the number of possible keys is small 
33 /// and is known at compile-time. The data is held in a static array, no allocations occur.
34 ///
35 /// Key type must:
36 ///     have static member ValueSetSize (integer)
37 ///     have static method fromInternalCode (returning an instance of Key type);
38 ///     have property $(D internal_code) that maps it to integers 0, 1, ..., ValueSetSize - 1
39 struct TinyMap(K, V, alias TinyMapPolicy=useBitArray) {
40     private V[K.ValueSetSize] _dict;
41     private size_t _size;
42     private mixin TinyMapPolicy!(K, V) Policy;
43     private alias ReturnType!(K.internal_code) TCode;
44 
45     /// Constructor
46     static TinyMap!(K, V, TinyMapPolicy) opCall(Args...)(Args args) {
47         TinyMap!(K, V, TinyMapPolicy) result;
48         result.Policy.init(args);
49         return result;
50     }
51    
52     /// Current number of elements
53     size_t length() @property const {
54         return _size;
55     }
56 
57     /// Indexed access
58     auto ref V opIndex(Key)(auto ref Key key)
59         if(is(Unqual!Key == K))
60     {
61         assert(key in this);
62         return _dict[key.internal_code];
63     }
64 
65     /// ditto
66     auto ref const(V) opIndex(Key)(auto ref Key key) const
67         if(is(Unqual!Key == K))
68     {
69         assert(key in this);
70         return _dict[key.internal_code];
71     }
72 
73 
74     /// ditto
75     V opIndexAssign(V value, K key) {
76         if (key !in this) {
77             ++_size;
78         }
79         _dict[key.internal_code] = value;
80         Policy._onInsert(key);
81         return value;
82     }
83 
84     /// ditto
85     void opIndexOpAssign(string op)(V value, K key) {
86         if (key !in this) {
87             ++_size;
88             _dict[key.internal_code] = V.init;
89         }
90         mixin("_dict[key.internal_code] " ~ op ~ "= value;");
91         Policy._onInsert(key);
92     }
93 
94     /// Check if the key is in the dictionary
95     bool opIn_r(K key) const {
96         return Policy._hasKey(key);
97     }
98 
99     /// Removal
100     bool remove(K key) {
101         if (key in this) {
102             --_size;
103             Policy._onRemove(key);
104             return true;
105         }
106         return false;
107     }
108 
109     /// Range of keys
110     auto keys() @property const {
111         // FIXME: create nice workaround for LDC bug #217
112         K[] _ks;
113         foreach (i; 0 .. K.ValueSetSize) {
114             if (Policy._hasKeyWithCode(i))
115                 _ks ~= K.fromInternalCode(cast(TCode)i);
116         }
117         return _ks;
118     }
119 
120     /// Range of values
121     auto values() @property const {
122         V[] _vs;
123         foreach (i; 0 .. K.ValueSetSize) {
124             if (Policy._hasKeyWithCode(i))
125                 _vs ~= _dict[i];
126         }
127         return _vs;
128     }
129 
130     /// Iteration with foreach
131     int opApply(scope int delegate(V value) dg) {
132         foreach (i; iota(K.ValueSetSize)) {
133             if (Policy._hasKeyWithCode(i)) {
134                 auto ret = dg(_dict[i]);
135                 if (ret != 0) return ret;
136             }
137         }
138         return 0;
139     }
140 
141     /// ditto
142     int opApply(scope int delegate(K key, V value) dg) {
143         foreach (i; iota(K.ValueSetSize)) {
144             if (Policy._hasKeyWithCode(i)) {
145                 auto ret = dg(K.fromInternalCode(cast(TCode)i), _dict[i]);
146                 if (ret != 0) return ret;
147             }
148         }
149         return 0;
150     }
151 }
152 
153 /// For each possible key store 0 if it's absent in the dictionary,
154 /// or 1 otherwise. Bit array is used for compactness.
155 ///
156 /// This is the default option. In this case, size of dictionary is
157 /// roughly (V.sizeof + 1/8) * K.ValueSetSize
158 mixin template useBitArray(K, V) {
159     private BitArray _value_is_set;
160 
161     private void init() {
162         _value_is_set.length = K.ValueSetSize;
163     }
164 
165     private bool _hasKey(K key) const {
166         return _value_is_set[key.internal_code];
167     }
168 
169     private bool _hasKeyWithCode(size_t code) const {
170         return _value_is_set[code];
171     }
172 
173     private void _onInsert(K key) {
174         _value_is_set[key.internal_code] = true;
175     }
176 
177     private void _onRemove(K key) {
178         _value_is_set[key.internal_code] = false;
179     }
180 }
181 
182 /// Use default value specified at construction as an indicator
183 /// of key absence.
184 /// That allows to save K.ValueSetSize bits of memory.
185 ///
186 /// E.g., you might want to use -1 as such indicator if non-negative
187 /// numbers are stored in the dictionary.
188 mixin template useDefaultValue(K, V) {
189     private V _default_value;
190 
191     private void init(V value) {
192         _default_value = value;
193         if (_default_value != V.init) {
194             _dict[] = _default_value;
195         }
196     }
197 
198     private bool _hasKey(K key) const {
199         return _dict[key.internal_code] != _default_value;
200     }
201 
202     private bool _hasKeyWithCode(size_t code) const {
203         return _dict[code] != _default_value;
204     }
205 
206     private void _onInsert(K key) {}
207 
208     private void _onRemove(K key) {
209         this[key] = _default_value;
210     }
211 }
212 
213 /// Allows to set up a dictionary which is always full.
214 mixin template fillNoRemove(K, V) {
215 
216     private void init() {
217         _size = K.ValueSetSize;
218     }
219 
220     private void init(V value) {
221         _size = K.ValueSetSize;
222 
223         for (size_t i = 0; i < _size; ++i)
224             _dict[i] = value;
225     }
226 
227     private bool _hasKey(K key) const {
228         return true;
229     }
230 
231     private bool _hasKeyWithCode(size_t code) const {
232         return true;
233     }
234 
235     private void _onInsert(K key) {}
236 
237     private void _onRemove(K key) {
238         ++_size;
239     }
240 }
241 
242 unittest {
243 
244     import std.array;
245     import bio.core.base;
246 
247     void test(M)(ref M dict) {
248         auto b1 = Base('A');
249         auto b2 = Base('C');
250         auto b3 = Base('G');
251         auto b4 = Base('T');
252         dict[b1] = 2;
253         dict[b2] = 3;
254         assert(dict.length == 2);
255         assert(dict[b1] == 2);
256         assert(b2 in dict);
257         assert(b3 !in dict);
258         assert(b4 !in dict);
259         dict[b4] = 5;
260         assert(equal(sort(array(dict.values)), [2, 3, 5]));
261         dict.remove(b1);
262         assert(b1 !in dict);
263         assert(dict.length == 2);
264         assert(dict[b2] == 3);
265 
266         foreach (k, v; dict) {
267             assert(k in dict);
268             assert(dict[k] == v);
269         }
270     }
271 
272     auto dict1 = TinyMap!(Base, int)();
273     auto dict2 = TinyMap!(Base, int, useDefaultValue)(-1);
274     int[Base] dict3;
275 
276     test(dict1);
277     test(dict2);
278     test(dict3);
279 
280     auto dict4 = TinyMap!(Base, ulong[4])();
281     dict4[Base('A')] = [0, 1, 2, 3];
282     dict4[Base('A')][3] += 1;
283     assert(dict4[Base('A')] == [0, 1, 2, 4]);
284 }
285 
286 /// Convenient mixin template for getting your struct working with TinyMap.
287 ///
288 /// Creates
289 ///     1) private member of type T with name _code
290 ///     2) fromInternalCode static method
291 ///     3) internal_code property
292 ///     4) static member ValueSetSize equal to N
293 ///     5) invariant that _code is always less than ValueSetSize
294 ///
295 /// That is, the only thing which implementation is up to you is
296 /// setting _code appropriately.
297 mixin template TinyMapInterface(uint N, T=ubyte) if (isUnsigned!T) {
298     private T _code;
299 
300     enum ValueSetSize = N;
301     static assert(N <= 2 ^^ (T.sizeof * 8));
302 
303     static typeof(this) fromInternalCode(T code) {
304         typeof(this) obj = void;
305         obj._code = code;
306         return obj;
307     }
308 
309     T internal_code() @property const {
310         return _code;
311     }
312 }