1 // =================================
  2 // Copyright (c) 2021 Seppo Laakko
  3 // Distributed under the MIT license
  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<Tulong>
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<TRPH>
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<ValueTypeReferenceTypePointerTypeHashtableType> 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==<TRPH>(const HashtableIterator<TRPH>& leftconst HashtableIterator<TRPH>& right)
202     {
203         return left.GetBucket() == right.GetBucket();
204     }
205 
206     public class Hashtable<KeyTypeValueTypeKeyOfValueHashFun = Hasher<KeyType>Compare = EqualTo<KeyType>>
207         where KeyType is Semiregular and 
208             ValueType is Semiregular and 
209             KeySelectionFunction<KeyOfValueKeyTypeValueType> and 
210             HashFunction<HashFunKeyType> and 
211             Compare is Relation and 
212             Compare.Domain is KeyType
213     {
214         private typedef Hashtable<KeyTypeValueTypeKeyOfValueHashFunCompare> Self;
215         public typedef HashtableIterator<ValueTypeValueType&ValueType*Self> Iterator;
216         public typedef HashtableIterator<ValueTypeconst 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(bucketsthat.buckets);
238             Swap(countthat.count);
239             Swap(loadFactorthat.loadFactor);
240             Swap(maxLoadFactorthat.maxLoadFactor);
241             Swap(keyOfthat.keyOf);
242             Swap(hashthat.hash);
243             Swap(equalthat.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(thisGetFirstBucket());
276         }
277         public inline nothrow ConstIterator Begin() const
278         {
279             return ConstIterator(thisGetFirstBucket());
280         }
281         public inline nothrow ConstIterator CBegin() const
282         {
283             return ConstIterator(thisGetFirstBucket());
284         }
285         public inline nothrow Iterator End()
286         {
287             return Iterator(thisnull);
288         }
289         public inline nothrow ConstIterator End() const
290         {
291             return ConstIterator(thisnull);
292         }
293         public inline nothrow ConstIterator CEnd() const
294         {
295             return ConstIterator(thisnull);
296         }
297         public inline nothrow void SetMaxLoadFactor(double maxLoadFactor_)
298         {
299             maxLoadFactor = maxLoadFactor_;
300         }
301         public Pair<Iteratorbool> 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(thisbucket)false);
319                 }
320                 bucket = bucket->Next();
321             }
322             bucket = new Bucket<ValueType>(valuebuckets[index]);
323             buckets[index] = bucket;
324             ++count;
325             SetLoadFactor();
326             CheckForRehash();
327             return MakePair(Iterator(thisbucket)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( thisbucket);
397                     }
398                     bucket = bucket->Next();
399                 }
400             }
401             return Iterator(thisnull);
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(thisbucket);
414                     }
415                     bucket = bucket->Next();
416                 }
417             }
418             return ConstIterator(thisnull);
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(thisbucket);
431                     }
432                     bucket = bucket->Next();
433                 }
434             }
435             return ConstIterator(thisnull);
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(bucketsb);
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& leftconst KeyType& right) const
534         {
535             return equal(leftright);
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 }