1 /******************************************************************************* 2 3 Template for a class implementing a set of hashed keys. The set is built on 4 top of an efficient bucket algorithm, allowing for fast look up of keys in 5 the set. 6 7 Usage example: 8 9 --- 10 11 import ocean.util.container.map.HashSet; 12 13 // A set of hash_t's 14 auto set = new HashSet; 15 16 hash_t hash = 232323; 17 18 // Add a hash 19 set.put(hash); 20 21 // Check if a hash exists in the set (null if not found) 22 auto exists = hash in set; 23 24 // Remove a hash from the set 25 set.remove(hash); 26 27 // Clear the set 28 set.clear(); 29 30 --- 31 32 Copyright: 33 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 34 All rights reserved. 35 36 License: 37 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 38 Alternatively, this file may be distributed under the terms of the Tango 39 3-Clause BSD License (see LICENSE_BSD.txt for details). 40 41 *******************************************************************************/ 42 43 module ocean.util.container.map.Set; 44 45 46 47 import ocean.meta.types.Qualifiers; 48 49 import ocean.util.container.map.model.BucketSet; 50 51 import ocean.util.container.map.model.Bucket; 52 53 import ocean.util.container.map.model.MapIterator; 54 55 import ocean.util.container.map.model.StandardHash; 56 57 version (UnitTestVerbose) import ocean.io.Stdout; 58 59 /******************************************************************************* 60 61 Debug switch for verbose unittest output (uncomment if desired) 62 63 *******************************************************************************/ 64 65 //version = UnitTestVerbose; 66 67 version ( UnitTestVerbose ) 68 { 69 import ocean.io.Stdout; 70 } 71 72 /******************************************************************************* 73 74 StandardKeyHashingSet class template. Manages a set of K's with fast lookup 75 using a standard way of hash calculation: 76 77 - If K is a primitive type (integer, floating point, character), the hash 78 value is calculated from the raw key data using the FNV1a hash function. 79 - If K is a dynamic or static array of a primitive type, the hash value is 80 calculated from the raw data of the key array content using the FNV1a hash 81 function. 82 - If K is a class, struct or union, it is expected to implement toHash(), 83 which will be used. 84 - Other key types (arrays of non-primitive types, classes/structs/unions 85 which do not implement toHash(), pointers, function references, delegates, 86 associative arrays) are not supported by this class template. 87 88 *******************************************************************************/ 89 90 public class StandardHashingSet ( K ) : Set!(K) 91 { 92 /*************************************************************************** 93 94 Constructor. 95 96 Params: 97 n = expected number of elements in mapping 98 load_factor = ratio of n to the number of internal buckets. The 99 desired (approximate) number of elements per bucket. For 100 example, 0.5 sets the number of buckets to double n; for 2 the 101 number of buckets is the half of n. load_factor must be greater 102 than 0. The load factor is basically a trade-off between memory 103 usage (number of buckets) and search time (number of elements 104 per bucket). 105 106 ***************************************************************************/ 107 108 public this ( size_t n, float load_factor = 0.75 ) 109 { 110 super(n, load_factor); 111 } 112 113 /*************************************************************************** 114 115 Constructor. 116 117 Params: 118 allocator = custom bucket elements allocator 119 n = expected number of elements in mapping 120 load_factor = ratio of n to the number of internal buckets. The 121 desired (approximate) number of elements per bucket. For 122 example, 0.5 sets the number of buckets to double n; for 2 the 123 number of buckets is the half of n. load_factor must be greater 124 than 0. The load factor is basically a trade-off between memory 125 usage (number of buckets) and search time (number of elements 126 per bucket). 127 128 ***************************************************************************/ 129 130 public this ( IAllocator allocator, size_t n, float load_factor = 0.75 ) 131 { 132 super(allocator, n, load_factor); 133 } 134 135 /*************************************************************************** 136 137 Mixin of the toHash() method which is declared abstract in BucketSet. 138 139 ***************************************************************************/ 140 141 override: 142 mixin StandardHash.toHash!(K); 143 } 144 145 146 /******************************************************************************* 147 148 Set class. Manages a set of K's with fast lookup. The toHash() method must 149 be implemented. 150 151 *******************************************************************************/ 152 153 public abstract class Set ( K ) : BucketSet!(0, K) 154 { 155 private alias .MapIterator!(void, K) SetIterator; 156 157 /*************************************************************************** 158 159 Mixin of the specialized iterator classes which inherit from 160 BucketSet.Iterator. 161 162 This makes available three iterator classes that can be newed to allow 163 certain iteration behaviors: 164 165 * Iterator — just a normal iterator 166 * InterruptibleIterator — an iterator that can be interrupted and 167 resumed, but that has to be manually reset with reset() if the 168 iteration is meant to be repeated 169 170 If the map is modified between interrupted iterations, it can happen 171 that new elements that were added in the mean time won't appear in the 172 iteratation, depending on whether they end up in a bucket that was 173 already iterated or not. 174 175 Iterator usage example 176 --- 177 auto map = new HashMap!(size_t); 178 179 auto it = map.new Iterator(); 180 181 // A normal iteration over the map 182 foreach ( k, v; it ) 183 { 184 .. 185 } 186 187 // Equal to 188 foreach ( k, v; map ) 189 { 190 .. 191 } 192 --- 193 194 InterruptibleIterator 195 --- 196 auto map = new HashMap!(size_t); 197 198 auto interruptible_it = map.new InterruptibleIterator(); 199 200 // Iterate over the first 100k elements 201 foreach ( i, k, v; interruptible_it ) 202 { 203 .. 204 // Break after 100k elements 205 if ( i % 100_000 == 0 ) break; 206 } 207 208 // Iterate over the next 100k elments 209 foreach ( i, k, v; interruptible_it ) 210 { 211 .. 212 // Break after 100k elements 213 if ( i % 100_000 == 0 ) break; 214 } 215 216 // Assuming the map had 150k elements, the iteration is done now, 217 // so this won't do anything 218 foreach ( i, k, v; interruptible_it ) 219 { 220 .. 221 // Break after 100k elements 222 if ( i % 100_000 == 0 ) break; 223 } 224 225 assert ( interruptible_it.finished() == true ); 226 --- 227 228 See also: BucketSet.Iterator, MapIterator.IteratorClass 229 230 ***************************************************************************/ 231 232 mixin IteratorClass!(BucketSet!(0,K).Iterator, SetIterator); 233 234 /*************************************************************************** 235 236 Constructor. 237 238 Params: 239 n = expected number of elements in mapping 240 load_factor = ratio of n to the number of internal buckets. The 241 desired (approximate) number of elements per bucket. For 242 example, 0.5 sets the number of buckets to double n; for 2 the 243 number of buckets is the half of n. load_factor must be greater 244 than 0. The load factor is basically a trade-off between memory 245 usage (number of buckets) and search time (number of elements 246 per bucket). 247 248 ***************************************************************************/ 249 250 protected this ( size_t n, float load_factor = 0.75 ) 251 { 252 super(n, load_factor); 253 } 254 255 /*************************************************************************** 256 257 Constructor. 258 259 Params: 260 allocator = custom bucket elements allocator 261 n = expected number of elements in mapping 262 load_factor = ratio of n to the number of internal buckets. The 263 desired (approximate) number of elements per bucket. For 264 example, 0.5 sets the number of buckets to double n; for 2 the 265 number of buckets is the half of n. load_factor must be greater 266 than 0. The load factor is basically a trade-off between memory 267 usage (number of buckets) and search time (number of elements 268 per bucket). 269 270 ***************************************************************************/ 271 272 protected this ( IAllocator allocator, size_t n, float load_factor = 0.75 ) 273 { 274 super(allocator, n, load_factor); 275 } 276 277 278 /*************************************************************************** 279 280 Looks up key in the set. 281 282 Params: 283 key = key to look up 284 285 Returns: 286 true if found or false if not. 287 288 ***************************************************************************/ 289 290 public bool opIn_r ( K key ) 291 { 292 return this.get_(key) !is null; 293 } 294 295 296 /*************************************************************************** 297 298 Support for the 'in' operator 299 300 Aliased to opIn_r, for backwards compatibility 301 302 ***************************************************************************/ 303 304 public alias opBinaryRight ( istring op : "in" ) = opIn_r; 305 306 307 /*************************************************************************** 308 309 Puts key into the set. 310 311 Params: 312 key = key to put into set 313 314 Returns: 315 true if the key was already on the set, false otherwise 316 317 ***************************************************************************/ 318 319 public bool put ( K key ) 320 { 321 bool added; 322 323 this.put_(key, added); 324 325 return !added; 326 } 327 328 329 /*************************************************************************** 330 331 'foreach' iteration over set. 332 333 Note: It is possible to have interruptible iterations, see documentation 334 for mixin of IteratorClass 335 336 See also: BucketSet.Iterator, MapIterator.IteratorClass 337 338 Notes: 339 - During iteration it is forbidden to call clear() or redistribute() or 340 remove map elements. If elements are added, the iteration may or may 341 not include these elements. 342 - If K is a static array, the iteration variable is a dynamic array of 343 the same base type and slices the key of the element in the map. 344 (The reason is that static array 'ref' parameters are forbidden in D.) 345 In this case DO NOT modify the key in any way! 346 - It is not recommended to do a 'ref' iteration over the keys. If you do 347 it anyway, DO NOT modify the key in-place! 348 349 ***************************************************************************/ 350 351 public int opApply ( SetIterator.Dg dg ) 352 { 353 scope it = this.new Iterator; 354 355 return it.opApply(dg); 356 } 357 358 /*************************************************************************** 359 360 Same as above, but includes a counter 361 362 ***************************************************************************/ 363 364 public int opApply ( SetIterator.Dgi dgi ) 365 { 366 scope it = this.new Iterator; 367 368 return it.opApply(dgi); 369 } 370 }