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