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