1
2
3
4
5
6 using System;
7 using System.Concepts;
8
9 namespace System.Collections
10 {
11 public const long[] hashtablePrimes =
12
;
13 53, 97, 193, 389, 769, 1543, 3079, 6151,
14 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869,
15 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
16 805306457, 1610612741
17 ];
18
19 public inline constexpr nothrow long GetNextHashtablePrime(long n)
20 {
21 const long* p = LowerBound(hashtablePrimes.CBegin(), hashtablePrimes.CEnd(), n);
22 if (p < hashtablePrimes.CEnd())
23 {
24 return *p;
25 }
26 return hashtablePrimes[hashtablePrimes.Length() - 1];
27 }
28
29 public inline nothrow ulong GetHashCode(long x)
30 {
31 return cast<ulong>(x);
32 }
33
34 public inline nothrow ulong GetHashCode(ulong x)
35 {
36 return x;
37 }
38
39 public inline nothrow ulong GetHashCode(char x)
40 {
41 return cast<ulong>(x);
42 }
43
44 public inline nothrow ulong GetHashCode(wchar x)
45 {
46 return cast<ulong>(x);
47 }
48
49 public inline nothrow ulong GetHashCode(uchar x)
50 {
51 return cast<ulong>(x);
52 }
53
54 public inline nothrow ulong GetHashCode(void* x)
55 {
56 return cast<ulong>(x);
57 }
58
59 public inline nothrow ulong GetHashCode(const string& s)
60 {
61 ulong hashCode = 14695981039346656037u;
62 for (char c : s)
63 {
64 hashCode = hashCode ^ cast<ulong>(c);
65 hashCode = hashCode * 1099511628211u;
66 }
67 return hashCode;
68 }
69
70 public inline nothrow ulong GetHashCode(const wstring& s)
71 {
72 ulong hashCode = 14695981039346656037u;
73 for (wchar c : s)
74 {
75 hashCode = hashCode ^ cast<ulong>(c);
76 hashCode = hashCode * 1099511628211u;
77 }
78 return hashCode;
79 }
80
81 public inline nothrow ulong GetHashCode(const ustring& s)
82 {
83 ulong hashCode = 14695981039346656037u;
84 for (uchar c : s)
85 {
86 hashCode = hashCode ^ cast<ulong>(c);
87 hashCode = hashCode * 1099511628211u;
88 }
89 return hashCode;
90 }
91
92 public inline nothrow ulong GetHashCode(const Uuid& uuid)
93 {
94 ulong hashCode = 14695981039346656037u;
95 for (byte b : uuid)
96 {
97 hashCode = hashCode ^ cast<ulong>(b);
98 hashCode = hashCode * 1099511628211u;
99 }
100 return hashCode;
101 }
102
103 public class Hasher<T> : UnaryFun<T, ulong>
104 {
105 public inline nothrow ulong operator()(const T& x)
106 {
107 return GetHashCode(x);
108 }
109 }
110
111 public class Bucket<T> where T is Semiregular
112 {
113 public typedef T ValueType;
114
115 public Bucket(const ValueType& value_, Bucket<ValueType>* next_) : value(value_), next(next_)
116 {
117 }
118 public inline nothrow const ValueType& Value() const
119 {
120 return value;
121 }
122 public inline nothrow ValueType& Value()
123 {
124 return value;
125 }
126 public inline nothrow Bucket<ValueType>* Next() const
127 {
128 return next;
129 }
130 public inline nothrow void SetNext(Bucket<ValueType>* next_)
131 {
132 next = next_;
133 }
134 private ValueType value;
135 private Bucket<ValueType>* next;
136 }
137
138 public class HashtableIterator<T, R, P, H>
139 {
140 public typedef T ValueType;
141 public typedef R ReferenceType;
142 public typedef P PointerType;
143 public typedef H HashtableType;
144 private typedef HashtableIterator<ValueType, ReferenceType, PointerType, HashtableType> Self;
145
146 public inline nothrow HashtableIterator() : table(null), bucket(null)
147 {
148 }
149 public inline nothrow HashtableIterator(HashtableType* table_, Bucket<ValueType>* bucket_) : table(table_), bucket(bucket_)
150 {
151 }
152 public inline ReferenceType operator*()
153 {
154 if (bucket == null)
155 {
156 ThrowNullPointerException();
157 }
158 return bucket->Value();
159 }
160 public inline PointerType operator->()
161 {
162 if (bucket == null)
163 {
164 ThrowNullPointerException();
165 }
166 return &(bucket->Value());
167 }
168 public inline Self& operator++()
169 {
170 if (bucket == null || table == null)
171 {
172 ThrowNullPointerException();
173 }
174 Bucket<ValueType>* old = bucket;
175 bucket = bucket->Next();
176 if (bucket == null)
177 {
178 long index = table->GetBucketIndex(old->Value());
179 if (index == -1)
180 {
181 ThrowPreconditionViolationException();
182 }
183 ++index;
184 long n = table->GetBucketCount();
185 while (bucket == null && index < n)
186 {
187 bucket = table->GetBucket(index);
188 ++index;
189 }
190 }
191 return *this;
192 }
193 public inline nothrow Bucket<ValueType>* GetBucket() const
194 {
195 return bucket;
196 }
197 private HashtableType* table;
198 private Bucket<ValueType>* bucket;
199 }
200
201 public nothrow bool operator==<T, R, P, H>(const HashtableIterator<T, R, P, H>& left, const HashtableIterator<T, R, P, H>& right)
202 {
203 return left.GetBucket() == right.GetBucket();
204 }
205
206 public class Hashtable<KeyType, ValueType, KeyOfValue, HashFun = Hasher<KeyType>, Compare = EqualTo<KeyType>>
207 where KeyType is Semiregular and
208 ValueType is Semiregular and
209 KeySelectionFunction<KeyOfValue, KeyType, ValueType> and
210 HashFunction<HashFun, KeyType> and
211 Compare is Relation and
212 Compare.Domain is KeyType
213 {
214 private typedef Hashtable<KeyType, ValueType, KeyOfValue, HashFun, Compare> Self;
215 public typedef HashtableIterator<ValueType, ValueType&, ValueType*, Self> Iterator;
216 public typedef HashtableIterator<ValueType, const ValueType&, const ValueType*, Self> ConstIterator;
217
218 public nothrow Hashtable() : buckets(), count(0), loadFactor(0.0), maxLoadFactor(0.8), keyOf(), hash(), equal()
219 {
220 }
221 public Hashtable(const Self& that) : buckets(), count(0), loadFactor(that.loadFactor), maxLoadFactor(that.maxLoadFactor), keyOf(that.keyOf), hash(that.hash), equal(that.equal)
222 {
223 CopyFrom(that);
224 }
225 public nothrow Hashtable(Self&& that) :
226 buckets(Rvalue(that.buckets)), count(that.count), loadFactor(that.loadFactor), maxLoadFactor(that.maxLoadFactor), keyOf(that.keyOf), hash(that.hash), equal(that.equal)
227 {
228 that.count = 0;
229 }
230 public void operator=(const Self& that)
231 {
232 Clear();
233 CopyFrom(that);
234 }
235 public nothrow void operator=(Self&& that)
236 {
237 Swap(buckets, that.buckets);
238 Swap(count, that.count);
239 Swap(loadFactor, that.loadFactor);
240 Swap(maxLoadFactor, that.maxLoadFactor);
241 Swap(keyOf, that.keyOf);
242 Swap(hash, that.hash);
243 Swap(equal, that.equal);
244 }
245 public ~Hashtable()
246 {
247 Clear();
248 }
249 public inline nothrow long Count() const
250 {
251 return count;
252 }
253 public inline nothrow bool IsEmpty() const
254 {
255 return count == 0;
256 }
257 public nothrow void Clear()
258 {
259 long n = buckets.Count();
260 for (long i = 0; i < n; ++i;)
261 {
262 Bucket<ValueType>* bucket = buckets[i];
263 while (bucket != null)
264 {
265 Bucket<ValueType>* next = bucket->Next();
266 delete bucket;
267 bucket = next;
268 }
269 buckets[i] = null;
270 }
271 count = 0;
272 }
273 public inline nothrow Iterator Begin()
274 {
275 return Iterator(this, GetFirstBucket());
276 }
277 public inline nothrow ConstIterator Begin() const
278 {
279 return ConstIterator(this, GetFirstBucket());
280 }
281 public inline nothrow ConstIterator CBegin() const
282 {
283 return ConstIterator(this, GetFirstBucket());
284 }
285 public inline nothrow Iterator End()
286 {
287 return Iterator(this, null);
288 }
289 public inline nothrow ConstIterator End() const
290 {
291 return ConstIterator(this, null);
292 }
293 public inline nothrow ConstIterator CEnd() const
294 {
295 return ConstIterator(this, null);
296 }
297 public inline nothrow void SetMaxLoadFactor(double maxLoadFactor_)
298 {
299 maxLoadFactor = maxLoadFactor_;
300 }
301 public Pair<Iterator, bool> Insert(const ValueType& value)
302 {
303 if (buckets.Count() == 0)
304 {
305 buckets.Resize(GetNextHashtablePrime(0));
306 }
307 const KeyType& key = KeyOf(value);
308 long index = Hash(key);
309 if (index == -1)
310 {
311 ThrowPreconditionViolationException();
312 }
313 Bucket<ValueType>* bucket = buckets[index];
314 while (bucket != null)
315 {
316 if (KeysEqual(KeyOf(bucket->Value()), key))
317 {
318 return MakePair(Iterator(this, bucket), false);
319 }
320 bucket = bucket->Next();
321 }
322 bucket = new Bucket<ValueType>(value, buckets[index]);
323 buckets[index] = bucket;
324 ++count;
325 SetLoadFactor();
326 CheckForRehash();
327 return MakePair(Iterator(this, bucket), true);
328 }
329 public nothrow void Remove(const KeyType& key)
330 {
331 long index = Hash(key);
332 if (index == -1) return;
333 Bucket<ValueType>* bucket = buckets[index];
334 Bucket<ValueType>* prev = null;
335 while (bucket != null)
336 {
337 if (KeysEqual(KeyOf(bucket->Value()), key))
338 {
339 if (prev != null)
340 {
341 prev->SetNext(bucket->Next());
342 }
343 else
344 {
345 buckets[index] = bucket->Next();
346 }
347 delete bucket;
348 --count;
349 SetLoadFactor();
350 return;
351 }
352 prev = bucket;
353 bucket = bucket->Next();
354 }
355 }
356 public nothrow void Remove(Iterator pos)
357 {
358 Bucket<ValueType>* bucket = pos.GetBucket();
359 if (bucket != null)
360 {
361 long index = Hash(KeyOf(bucket->Value()));
362 if (index == -1) return;
363 Bucket<ValueType>* b = buckets[index];
364 Bucket<ValueType>* prev = null;
365 while (b != bucket && b != null)
366 {
367 prev = b;
368 b = b->Next();
369 }
370 if (b == bucket)
371 {
372 if (prev != null)
373 {
374 prev->SetNext(b->Next());
375 }
376 else
377 {
378 buckets[index] = b->Next();
379 }
380 delete bucket;
381 --count;
382 SetLoadFactor();
383 }
384 }
385 }
386 public nothrow Iterator Find(const KeyType& key)
387 {
388 long index = Hash(key);
389 if (index >= 0)
390 {
391 Bucket<ValueType>* bucket = buckets[index];
392 while (bucket != null)
393 {
394 if (KeysEqual(KeyOf(bucket->Value()), key))
395 {
396 return Iterator( this, bucket);
397 }
398 bucket = bucket->Next();
399 }
400 }
401 return Iterator(this, null);
402 }
403 public nothrow ConstIterator Find(const KeyType& key) const
404 {
405 long index = Hash(key);
406 if (index >= 0)
407 {
408 Bucket<ValueType>* bucket = buckets[index];
409 while (bucket != null)
410 {
411 if (KeysEqual(KeyOf(bucket->Value()), key))
412 {
413 return ConstIterator(this, bucket);
414 }
415 bucket = bucket->Next();
416 }
417 }
418 return ConstIterator(this, null);
419 }
420 public nothrow ConstIterator CFind(const KeyType& key) const
421 {
422 long index = Hash(key);
423 if (index >= 0)
424 {
425 Bucket<ValueType>* bucket = buckets[index];
426 while (bucket != null)
427 {
428 if (KeysEqual(KeyOf(bucket->Value()), key))
429 {
430 return ConstIterator(this, bucket);
431 }
432 bucket = bucket->Next();
433 }
434 }
435 return ConstIterator(this, null);
436 }
437 public inline nothrow long GetBucketCount() const
438 {
439 return buckets.Count();
440 }
441 public inline nothrow long GetBucketIndex(const ValueType& value) const
442 {
443 return Hash(KeyOf(value));
444 }
445 public inline nothrow Bucket<ValueType>* GetBucket(long index) const
446 {
447 return buckets[index];
448 }
449 private inline nothrow void SetLoadFactor()
450 {
451 long bc = buckets.Count();
452 if (bc == 0)
453 {
454 loadFactor = 1.0;
455 }
456 else
457 {
458 double c = count;
459 loadFactor = c / bc;
460 }
461 }
462 private inline void CheckForRehash()
463 {
464 if (loadFactor > maxLoadFactor)
465 {
466 Rehash();
467 }
468 }
469 private void Rehash()
470 {
471 List<Bucket<ValueType>*> b;
472 Swap(buckets, b);
473 long n = b.Count();
474 buckets.Resize(GetNextHashtablePrime(n + 1));
475 for (long i = 0; i < n; ++i;)
476 {
477 Bucket<ValueType>* bucket = b[i];
478 while (bucket != null)
479 {
480 const KeyType& key = KeyOf(bucket->Value());
481 long index = Hash(key);
482 if (index == -1)
483 {
484 ThrowPreconditionViolationException();
485 }
486 Bucket<ValueType>* next = bucket->Next();
487 bucket->SetNext(buckets[index]);
488 buckets[index] = bucket;
489 bucket = next;
490 }
491 }
492 }
493 private nothrow Bucket<ValueType>* GetFirstBucket() const
494 {
495 Bucket<ValueType>* bucket = null;
496 long n = buckets.Count();
497 for (long i = 0; i < n; ++i;)
498 {
499 bucket = buckets[i];
500 if (bucket != null)
501 {
502 break;
503 }
504 }
505 return bucket;
506 }
507 private void CopyFrom(const Self& that)
508 {
509 long n = that.buckets.Count();
510 buckets.Resize(n);
511 for (long i = 0; i < n; ++i;)
512 {
513 Bucket<ValueType>* bucket = that.buckets[i];
514 while (bucket != null)
515 {
516 buckets[i] = new Bucket<ValueType>(bucket->Value(), buckets[i]);
517 bucket = bucket->Next();
518 }
519 }
520 count = that.count;
521 loadFactor = that.loadFactor;
522 maxLoadFactor = that.maxLoadFactor;
523 }
524 private inline nothrow const KeyType& KeyOf(const ValueType& value) const
525 {
526 return keyOf(value);
527 }
528 private inline nothrow long Hash(const KeyType& key) const
529 {
530 if (buckets.IsEmpty()) return -1;
531 return cast<long>(hash(key) % cast<ulong>(buckets.Count()));
532 }
533 private inline nothrow bool KeysEqual(const KeyType& left, const KeyType& right) const
534 {
535 return equal(left, right);
536 }
537 private List<Bucket<ValueType>*> buckets;
538 private long count;
539 private double loadFactor;
540 private double maxLoadFactor;
541 private KeyOfValue keyOf;
542 private HashFun hash;
543 private Compare equal;
544 }
545 }