1 /******************************************************************************* 2 3 Map template with a fixed set of keys. 4 5 Map template with a fixed set of keys, specified in the class' constructor. 6 If an item is added whose key is not in the fixed set, an exception is 7 thrown. 8 9 Such a map can be faster than a standard hash map, as the fixed set of 10 possible keys means that a fast binary search can be used to find the index 11 of the corresponding value. This of course only holds true when the time 12 taken to generate a hash from a key would be slower than the time taken to 13 do a binary search over the key. In the case of char[] keys, tests have 14 shown that for keys of 5 characters or longer, the FixedKeyMap starts to be 15 faster than the StandardKeyHashingMap, and that in the case of long keys 16 (100 characters) it is an order of magnitude faster. 17 18 Usage example: 19 20 --- 21 22 import ocean.util.container.FixedKeyMap; 23 24 // Create map instance 25 auto map = new FixedKeyMap!(char[], char[])("first", "second", "third"); 26 27 // Add and check an entry 28 map["first"] = "hello"; 29 assert(map["first"] == "hello"); 30 31 // Example of adding an entry which will be rejected 32 try 33 { 34 map["fifth"] = "should fail"; 35 } 36 catch ( map.FixedKeyMapException e ) 37 { 38 // expected 39 } 40 41 // Example of checking if a key is in the map (this does not throw an 42 // exception if the key is not found) 43 auto nine = "ninth" in map; 44 45 --- 46 47 Copyright: 48 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 49 All rights reserved. 50 51 License: 52 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 53 Alternatively, this file may be distributed under the terms of the Tango 54 3-Clause BSD License (see LICENSE_BSD.txt for details). 55 56 *******************************************************************************/ 57 58 module ocean.util.container.FixedKeyMap; 59 60 61 62 63 import ocean.meta.types.Qualifiers; 64 import ocean.core.Array; 65 import ocean.core.Array: copy, bsearch; 66 import ocean.core.Enforce; 67 68 debug import ocean.io.Stdout; 69 70 version (unittest) import ocean.core.Test; 71 72 73 /******************************************************************************* 74 75 Fixed key map class template. 76 77 Params: 78 K = mapping key type 79 V = mapping value type 80 81 *******************************************************************************/ 82 83 public class FixedKeyMap ( K, V ) 84 { 85 /*************************************************************************** 86 87 List of keys in mapping. 88 89 The keys are set once (in the constructor) and sorted. 90 91 ***************************************************************************/ 92 93 private K[] keys; 94 95 96 /*************************************************************************** 97 98 List of values in mapping. This list is always the same length as the 99 keys array, and has the same ordering (i.e. the value in values[0] is 100 associated with the key in keys[0]). 101 102 ***************************************************************************/ 103 104 private V[] values; 105 106 107 /*************************************************************************** 108 109 Exception instance 110 111 ***************************************************************************/ 112 113 static public class FixedKeyMapException : Exception 114 { 115 public this () 116 { 117 super(null); 118 super.file = __FILE__; 119 } 120 121 public typeof(this) set ( istring msg, long line = __LINE__ ) 122 { 123 super.msg = msg; 124 super.line = line; 125 return this; 126 } 127 } 128 129 private FixedKeyMapException exception; 130 131 132 /*************************************************************************** 133 134 Constructor. The passed list of allowed keys is shallow copied into the 135 keys class member. 136 137 Params: 138 keys = list of allowed keys 139 140 ***************************************************************************/ 141 142 public this ( const(K[]) keys ) 143 { 144 this.keys.copy(keys); 145 sort(this.keys); 146 147 this.values.length = this.keys.length; 148 149 this.exception = new FixedKeyMapException; 150 } 151 152 153 /*************************************************************************** 154 155 Returns: 156 length of mapping (the number of keys) 157 158 ***************************************************************************/ 159 160 public size_t length ( ) 161 { 162 return this.keys.length; 163 } 164 165 166 /*************************************************************************** 167 168 Gets a value for a key. 169 170 Params: 171 key = key to look up 172 173 Returns: 174 value corresponding to key 175 176 Throws: 177 if key is not in map (see this.keyIndex) 178 179 ***************************************************************************/ 180 181 public V opIndex ( const(K) key ) 182 { 183 return this.values[this.keyIndex(key, true)]; 184 } 185 186 187 /*************************************************************************** 188 189 Sets a value for a key. 190 191 Params: 192 value = value to set 193 key = key to set value for 194 195 Throws: 196 if key is not in map (see this.keyIndex) 197 198 ***************************************************************************/ 199 200 public void opIndexAssign ( V value, const(K) key ) 201 { 202 this.values[this.keyIndex(key, true)] = value; 203 } 204 205 206 /*************************************************************************** 207 208 Checks whether a key is in the map, and returns a pointer to the 209 corresponding value, or null if the key does not exist. 210 211 Params: 212 key = key to look up 213 214 Returns: 215 pointer to value corresponding to key, or null if key not in map 216 217 ***************************************************************************/ 218 219 public V* opIn_r ( const(K) key ) 220 { 221 auto pos = this.keyIndex(key, false); 222 auto found = pos < this.keys.length; 223 224 return found ? &this.values[pos] : null; 225 } 226 227 228 /*************************************************************************** 229 230 Support for the 'in' operator 231 232 Aliased to opIn_r, for backwards compatibility 233 234 ***************************************************************************/ 235 236 public alias opBinaryRight ( istring op : "in" ) = opIn_r; 237 238 239 /*************************************************************************** 240 241 foreach operator over keys in the map. 242 243 ***************************************************************************/ 244 245 public int opApply ( scope int delegate ( ref K ) dg ) 246 { 247 int res; 248 foreach ( key; this.keys ) 249 { 250 res = dg(key); 251 if ( res ) break; 252 } 253 return res; 254 } 255 256 257 /*************************************************************************** 258 259 foreach operator over keys and values in the map. 260 261 ***************************************************************************/ 262 263 public int opApply ( scope int delegate ( ref K, ref V ) dg ) 264 { 265 int res; 266 foreach ( i, key; this.keys ) 267 { 268 res = dg(key, this.values[i]); 269 if ( res ) break; 270 } 271 return res; 272 } 273 274 275 /*************************************************************************** 276 277 foreach operator over keys, values and indices in the map. 278 279 ***************************************************************************/ 280 281 public int opApply ( scope int delegate ( ref size_t, ref K, ref V ) dg ) 282 { 283 int res; 284 foreach ( i, key; this.keys ) 285 { 286 res = dg(i, key, this.values[i]); 287 if ( res ) break; 288 } 289 return res; 290 } 291 292 293 /*************************************************************************** 294 295 Finds a key in the keys array. 296 297 Params: 298 key = key to look up 299 throw_if_not_found = if true, an exception is thrown when looking up 300 a key which isn't in the array 301 302 Returns: 303 index of key in array, or keys.length if throw_if_not_found is false 304 and key is not found 305 306 Throws: 307 if throw_if_not_found is true and the key is not in the array 308 309 ***************************************************************************/ 310 311 private size_t keyIndex ( const(K) key, bool throw_if_not_found ) 312 { 313 size_t pos; 314 auto found = ocean.core.Array.bsearch(this.keys, key, pos); 315 316 if ( !found ) 317 { 318 if ( throw_if_not_found ) 319 { 320 throw this.exception.set("Key not in map"); 321 } 322 else 323 { 324 pos = this.keys.length; 325 } 326 } 327 328 return pos; 329 } 330 } 331 332 333 334 unittest 335 { 336 auto map = new FixedKeyMap!(istring, istring)(["first", "second", "third"]); 337 test(("first" in map) !is null); 338 test(("second" in map) !is null); 339 test(("third" in map) !is null); 340 test(("fourth" in map) is null); 341 342 test(*("first" in map) == ""); 343 test(*("second" in map) == ""); 344 test(*("third" in map) == ""); 345 346 map["first"] = "hello"; 347 test(("first" in map) !is null); 348 test(*("first" in map) == "hello"); 349 test(map["first"] == "hello"); 350 351 map["first"] = "world"; 352 test(("first" in map) !is null); 353 test(*("first" in map) == "world"); 354 test(map["first"] == "world"); 355 356 bool caught; 357 try 358 { 359 map["fifth"]; 360 } 361 catch ( map.FixedKeyMapException e ) 362 { 363 caught = true; 364 } 365 test(caught); 366 }