summaryrefslogtreecommitdiff
path: root/source/core/dictionary.h
diff options
context:
space:
mode:
Diffstat (limited to 'source/core/dictionary.h')
-rw-r--r--source/core/dictionary.h1695
1 files changed, 846 insertions, 849 deletions
diff --git a/source/core/dictionary.h b/source/core/dictionary.h
index 77f0df515..c052685fd 100644
--- a/source/core/dictionary.h
+++ b/source/core/dictionary.h
@@ -7,1012 +7,1009 @@
#include "slang-math.h"
#include "hash.h"
-namespace CoreLib
+namespace Slang
{
- namespace Basic
+ template<typename TKey, typename TValue>
+ class KeyValuePair
{
- template<typename TKey, typename TValue>
- class KeyValuePair
+ public:
+ TKey Key;
+ TValue Value;
+ KeyValuePair()
+ {}
+ KeyValuePair(const TKey & key, const TValue & value)
{
- public:
- TKey Key;
- TValue Value;
- KeyValuePair()
- {}
- KeyValuePair(const TKey & key, const TValue & value)
- {
- Key = key;
- Value = value;
- }
- KeyValuePair(TKey && key, TValue && value)
- {
- Key = _Move(key);
- Value = _Move(value);
- }
- KeyValuePair(TKey && key, const TValue & value)
- {
- Key = _Move(key);
- Value = value;
- }
- KeyValuePair(const KeyValuePair<TKey, TValue> & _that)
- {
- Key = _that.Key;
- Value = _that.Value;
- }
- KeyValuePair(KeyValuePair<TKey, TValue> && _that)
- {
- operator=(_Move(_that));
- }
- KeyValuePair & operator=(KeyValuePair<TKey, TValue> && that)
- {
- Key = _Move(that.Key);
- Value = _Move(that.Value);
- return *this;
- }
- KeyValuePair & operator=(const KeyValuePair<TKey, TValue> & that)
- {
- Key = that.Key;
- Value = that.Value;
- return *this;
- }
- int GetHashCode()
- {
- return GetHashCode(Key);
- }
- };
-
- template<typename TKey, typename TValue>
- inline KeyValuePair<TKey, TValue> KVPair(const TKey & k, const TValue & v)
+ Key = key;
+ Value = value;
+ }
+ KeyValuePair(TKey && key, TValue && value)
+ {
+ Key = _Move(key);
+ Value = _Move(value);
+ }
+ KeyValuePair(TKey && key, const TValue & value)
+ {
+ Key = _Move(key);
+ Value = value;
+ }
+ KeyValuePair(const KeyValuePair<TKey, TValue> & _that)
+ {
+ Key = _that.Key;
+ Value = _that.Value;
+ }
+ KeyValuePair(KeyValuePair<TKey, TValue> && _that)
+ {
+ operator=(_Move(_that));
+ }
+ KeyValuePair & operator=(KeyValuePair<TKey, TValue> && that)
+ {
+ Key = _Move(that.Key);
+ Value = _Move(that.Value);
+ return *this;
+ }
+ KeyValuePair & operator=(const KeyValuePair<TKey, TValue> & that)
{
- return KeyValuePair<TKey, TValue>(k, v);
+ Key = that.Key;
+ Value = that.Value;
+ return *this;
}
+ int GetHashCode()
+ {
+ return GetHashCode(Key);
+ }
+ };
+
+ template<typename TKey, typename TValue>
+ inline KeyValuePair<TKey, TValue> KVPair(const TKey & k, const TValue & v)
+ {
+ return KeyValuePair<TKey, TValue>(k, v);
+ }
- const float MaxLoadFactor = 0.7f;
+ const float MaxLoadFactor = 0.7f;
- template<typename TKey, typename TValue>
- class Dictionary
+ template<typename TKey, typename TValue>
+ class Dictionary
+ {
+ friend class Iterator;
+ friend class ItemProxy;
+ private:
+ inline int GetProbeOffset(int /*probeId*/) const
{
- friend class Iterator;
- friend class ItemProxy;
- private:
- inline int GetProbeOffset(int /*probeId*/) const
- {
- // quadratic probing
- return 1;
- }
- private:
- int bucketSizeMinusOne, shiftBits;
- int _count;
- IntSet marks;
- KeyValuePair<TKey, TValue>* hashMap;
- void Free()
- {
- if (hashMap)
- delete[] hashMap;
- hashMap = 0;
- }
- inline bool IsDeleted(int pos) const
- {
- return marks.Contains((pos << 1) + 1);
- }
- inline bool IsEmpty(int pos) const
- {
- return !marks.Contains((pos << 1));
- }
- inline void SetDeleted(int pos, bool val)
+ // quadratic probing
+ return 1;
+ }
+ private:
+ int bucketSizeMinusOne, shiftBits;
+ int _count;
+ IntSet marks;
+ KeyValuePair<TKey, TValue>* hashMap;
+ void Free()
+ {
+ if (hashMap)
+ delete[] hashMap;
+ hashMap = 0;
+ }
+ inline bool IsDeleted(int pos) const
+ {
+ return marks.Contains((pos << 1) + 1);
+ }
+ inline bool IsEmpty(int pos) const
+ {
+ return !marks.Contains((pos << 1));
+ }
+ inline void SetDeleted(int pos, bool val)
+ {
+ if (val)
+ marks.Add((pos << 1) + 1);
+ else
+ marks.Remove((pos << 1) + 1);
+ }
+ inline void SetEmpty(int pos, bool val)
+ {
+ if (val)
+ marks.Remove((pos << 1));
+ else
+ marks.Add((pos << 1));
+ }
+ struct FindPositionResult
+ {
+ int ObjectPosition;
+ int InsertionPosition;
+ FindPositionResult()
{
- if (val)
- marks.Add((pos << 1) + 1);
- else
- marks.Remove((pos << 1) + 1);
+ ObjectPosition = -1;
+ InsertionPosition = -1;
}
- inline void SetEmpty(int pos, bool val)
+ FindPositionResult(int objPos, int insertPos)
{
- if (val)
- marks.Remove((pos << 1));
- else
- marks.Add((pos << 1));
+ ObjectPosition = objPos;
+ InsertionPosition = insertPos;
}
- struct FindPositionResult
- {
- int ObjectPosition;
- int InsertionPosition;
- FindPositionResult()
- {
- ObjectPosition = -1;
- InsertionPosition = -1;
- }
- FindPositionResult(int objPos, int insertPos)
- {
- ObjectPosition = objPos;
- InsertionPosition = insertPos;
- }
- };
- template<typename T>
- inline int GetHashPos(T & key) const
- {
- return ((unsigned int)(GetHashCode(key) * 2654435761)) >> shiftBits;
- }
- template<typename T>
- FindPositionResult FindPosition(const T & key) const
+ };
+ template<typename T>
+ inline int GetHashPos(T & key) const
+ {
+ return ((unsigned int)(GetHashCode(key) * 2654435761)) >> shiftBits;
+ }
+ template<typename T>
+ FindPositionResult FindPosition(const T & key) const
+ {
+ int hashPos = GetHashPos((T&)key);
+ int insertPos = -1;
+ int numProbes = 0;
+ while (numProbes <= bucketSizeMinusOne)
{
- int hashPos = GetHashPos((T&)key);
- int insertPos = -1;
- int numProbes = 0;
- while (numProbes <= bucketSizeMinusOne)
+ if (IsEmpty(hashPos))
{
- if (IsEmpty(hashPos))
- {
- if (insertPos == -1)
- return FindPositionResult(-1, hashPos);
- else
- return FindPositionResult(-1, insertPos);
- }
- else if (IsDeleted(hashPos))
- {
- if (insertPos == -1)
- insertPos = hashPos;
- }
- else if (hashMap[hashPos].Key == key)
- {
- return FindPositionResult(hashPos, -1);
- }
- numProbes++;
- hashPos = (hashPos + GetProbeOffset(numProbes)) & bucketSizeMinusOne;
+ if (insertPos == -1)
+ return FindPositionResult(-1, hashPos);
+ else
+ return FindPositionResult(-1, insertPos);
}
- if (insertPos != -1)
- return FindPositionResult(-1, insertPos);
- throw InvalidOperationException("Hash map is full. This indicates an error in Key::Equal or Key::GetHashCode.");
- }
- TValue & _Insert(KeyValuePair<TKey, TValue> && kvPair, int pos)
- {
- hashMap[pos] = _Move(kvPair);
- SetEmpty(pos, false);
- SetDeleted(pos, false);
- return hashMap[pos].Value;
- }
- void Rehash()
- {
- if (bucketSizeMinusOne == -1 || _count / (float)bucketSizeMinusOne >= MaxLoadFactor)
+ else if (IsDeleted(hashPos))
{
- int newSize = (bucketSizeMinusOne + 1) * 2;
- int newShiftBits = shiftBits - 1;
- if (newSize == 0)
- {
- newSize = 16;
- newShiftBits = 28;
- }
- Dictionary<TKey, TValue> newDict;
- newDict.shiftBits = newShiftBits;
- newDict.bucketSizeMinusOne = newSize - 1;
- newDict.hashMap = new KeyValuePair<TKey, TValue>[newSize];
- newDict.marks.SetMax(newSize * 2);
- if (hashMap)
- {
- for (auto & kvPair : *this)
- {
- newDict.Add(_Move(kvPair));
- }
- }
- *this = _Move(newDict);
+ if (insertPos == -1)
+ insertPos = hashPos;
}
- }
-
- bool AddIfNotExists(KeyValuePair<TKey, TValue> && kvPair)
- {
- Rehash();
- auto pos = FindPosition(kvPair.Key);
- if (pos.ObjectPosition != -1)
- return false;
- else if (pos.InsertionPosition != -1)
+ else if (hashMap[hashPos].Key == key)
{
- _count++;
- _Insert(_Move(kvPair), pos.InsertionPosition);
- return true;
+ return FindPositionResult(hashPos, -1);
}
- else
- throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
- }
- void Add(KeyValuePair<TKey, TValue> && kvPair)
- {
- if (!AddIfNotExists(_Move(kvPair)))
- throw KeyExistsException("The key already exists in Dictionary.");
+ numProbes++;
+ hashPos = (hashPos + GetProbeOffset(numProbes)) & bucketSizeMinusOne;
}
- TValue & Set(KeyValuePair<TKey, TValue> && kvPair)
- {
- Rehash();
- auto pos = FindPosition(kvPair.Key);
- if (pos.ObjectPosition != -1)
- return _Insert(_Move(kvPair), pos.ObjectPosition);
- else if (pos.InsertionPosition != -1)
- {
- _count++;
- return _Insert(_Move(kvPair), pos.InsertionPosition);
- }
- else
- throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
- }
- public:
- class Iterator
+ if (insertPos != -1)
+ return FindPositionResult(-1, insertPos);
+ throw InvalidOperationException("Hash map is full. This indicates an error in Key::Equal or Key::GetHashCode.");
+ }
+ TValue & _Insert(KeyValuePair<TKey, TValue> && kvPair, int pos)
+ {
+ hashMap[pos] = _Move(kvPair);
+ SetEmpty(pos, false);
+ SetDeleted(pos, false);
+ return hashMap[pos].Value;
+ }
+ void Rehash()
+ {
+ if (bucketSizeMinusOne == -1 || _count / (float)bucketSizeMinusOne >= MaxLoadFactor)
{
- private:
- const Dictionary<TKey, TValue> * dict;
- int pos;
- public:
- KeyValuePair<TKey, TValue> & operator *() const
- {
- return dict->hashMap[pos];
- }
- KeyValuePair<TKey, TValue> * operator ->() const
+ int newSize = (bucketSizeMinusOne + 1) * 2;
+ int newShiftBits = shiftBits - 1;
+ if (newSize == 0)
{
- return dict->hashMap + pos;
+ newSize = 16;
+ newShiftBits = 28;
}
- Iterator & operator ++()
+ Dictionary<TKey, TValue> newDict;
+ newDict.shiftBits = newShiftBits;
+ newDict.bucketSizeMinusOne = newSize - 1;
+ newDict.hashMap = new KeyValuePair<TKey, TValue>[newSize];
+ newDict.marks.SetMax(newSize * 2);
+ if (hashMap)
{
- if (pos > dict->bucketSizeMinusOne)
- return *this;
- pos++;
- while (pos <= dict->bucketSizeMinusOne && (dict->IsDeleted(pos) || dict->IsEmpty(pos)))
+ for (auto & kvPair : *this)
{
- pos++;
+ newDict.Add(_Move(kvPair));
}
- return *this;
- }
- Iterator operator ++(int)
- {
- Iterator rs = *this;
- operator++();
- return rs;
- }
- bool operator != (const Iterator & _that) const
- {
- return pos != _that.pos || dict != _that.dict;
- }
- bool operator == (const Iterator & _that) const
- {
- return pos == _that.pos && dict == _that.dict;
- }
- Iterator(const Dictionary<TKey, TValue> * _dict, int _pos)
- {
- this->dict = _dict;
- this->pos = _pos;
- }
- Iterator()
- {
- this->dict = 0;
- this->pos = 0;
}
- };
+ *this = _Move(newDict);
+ }
+ }
- Iterator begin() const
+ bool AddIfNotExists(KeyValuePair<TKey, TValue> && kvPair)
+ {
+ Rehash();
+ auto pos = FindPosition(kvPair.Key);
+ if (pos.ObjectPosition != -1)
+ return false;
+ else if (pos.InsertionPosition != -1)
{
- int pos = 0;
- while (pos < bucketSizeMinusOne + 1)
- {
- if (IsEmpty(pos) || IsDeleted(pos))
- pos++;
- else
- break;
- }
- return Iterator(this, pos);
+ _count++;
+ _Insert(_Move(kvPair), pos.InsertionPosition);
+ return true;
}
- Iterator end() const
+ else
+ throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
+ }
+ void Add(KeyValuePair<TKey, TValue> && kvPair)
+ {
+ if (!AddIfNotExists(_Move(kvPair)))
+ throw KeyExistsException("The key already exists in Dictionary.");
+ }
+ TValue & Set(KeyValuePair<TKey, TValue> && kvPair)
+ {
+ Rehash();
+ auto pos = FindPosition(kvPair.Key);
+ if (pos.ObjectPosition != -1)
+ return _Insert(_Move(kvPair), pos.ObjectPosition);
+ else if (pos.InsertionPosition != -1)
{
- return Iterator(this, bucketSizeMinusOne + 1);
+ _count++;
+ return _Insert(_Move(kvPair), pos.InsertionPosition);
}
+ else
+ throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
+ }
+ public:
+ class Iterator
+ {
+ private:
+ const Dictionary<TKey, TValue> * dict;
+ int pos;
public:
- void Add(const TKey & key, const TValue & value)
- {
- Add(KeyValuePair<TKey, TValue>(key, value));
- }
- void Add(TKey && key, TValue && value)
+ KeyValuePair<TKey, TValue> & operator *() const
{
- Add(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
+ return dict->hashMap[pos];
}
- bool AddIfNotExists(const TKey & key, const TValue & value)
+ KeyValuePair<TKey, TValue> * operator ->() const
{
- return AddIfNotExists(KeyValuePair<TKey, TValue>(key, value));
+ return dict->hashMap + pos;
}
- bool AddIfNotExists(TKey && key, TValue && value)
+ Iterator & operator ++()
{
- return AddIfNotExists(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
- }
- void Remove(const TKey & key)
- {
- if (_count == 0)
- return;
- auto pos = FindPosition(key);
- if (pos.ObjectPosition != -1)
+ if (pos > dict->bucketSizeMinusOne)
+ return *this;
+ pos++;
+ while (pos <= dict->bucketSizeMinusOne && (dict->IsDeleted(pos) || dict->IsEmpty(pos)))
{
- SetDeleted(pos.ObjectPosition, true);
- _count--;
+ pos++;
}
+ return *this;
}
- void Clear()
+ Iterator operator ++(int)
{
- _count = 0;
-
- marks.Clear();
+ Iterator rs = *this;
+ operator++();
+ return rs;
}
-
- template<typename T>
- bool ContainsKey(const T & key) const
+ bool operator != (const Iterator & _that) const
{
- if (bucketSizeMinusOne == -1)
- return false;
- auto pos = FindPosition(key);
- return pos.ObjectPosition != -1;
+ return pos != _that.pos || dict != _that.dict;
}
- template<typename T>
- bool TryGetValue(const T & key, TValue & value) const
+ bool operator == (const Iterator & _that) const
{
- if (bucketSizeMinusOne == -1)
- return false;
- auto pos = FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- value = hashMap[pos.ObjectPosition].Value;
- return true;
- }
- return false;
+ return pos == _that.pos && dict == _that.dict;
}
- template<typename T>
- TValue * TryGetValue(const T & key) const
+ Iterator(const Dictionary<TKey, TValue> * _dict, int _pos)
{
- if (bucketSizeMinusOne == -1)
- return nullptr;
- auto pos = FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- return &hashMap[pos.ObjectPosition].Value;
- }
- return nullptr;
+ this->dict = _dict;
+ this->pos = _pos;
}
- class ItemProxy
+ Iterator()
{
- private:
- const Dictionary<TKey, TValue> * dict;
- TKey key;
- public:
- ItemProxy(const TKey & _key, const Dictionary<TKey, TValue> * _dict)
- {
- this->dict = _dict;
- this->key = _key;
- }
- ItemProxy(TKey && _key, const Dictionary<TKey, TValue> * _dict)
- {
- this->dict = _dict;
- this->key = _Move(_key);
- }
- TValue & GetValue() const
- {
- auto pos = dict->FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- return dict->hashMap[pos.ObjectPosition].Value;
- }
- else
- throw KeyNotFoundException("The key does not exists in dictionary.");
- }
- inline TValue & operator()() const
- {
- return GetValue();
- }
- operator TValue&() const
- {
- return GetValue();
- }
- TValue & operator = (const TValue & val) const
- {
- return ((Dictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), val));
- }
- TValue & operator = (TValue && val) const
- {
- return ((Dictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), _Move(val)));
- }
- };
- ItemProxy operator [](const TKey & key) const
+ this->dict = 0;
+ this->pos = 0;
+ }
+ };
+
+ Iterator begin() const
+ {
+ int pos = 0;
+ while (pos < bucketSizeMinusOne + 1)
{
- return ItemProxy(key, this);
+ if (IsEmpty(pos) || IsDeleted(pos))
+ pos++;
+ else
+ break;
}
- ItemProxy operator [](TKey && key) const
+ return Iterator(this, pos);
+ }
+ Iterator end() const
+ {
+ return Iterator(this, bucketSizeMinusOne + 1);
+ }
+ public:
+ void Add(const TKey & key, const TValue & value)
+ {
+ Add(KeyValuePair<TKey, TValue>(key, value));
+ }
+ void Add(TKey && key, TValue && value)
+ {
+ Add(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
+ }
+ bool AddIfNotExists(const TKey & key, const TValue & value)
+ {
+ return AddIfNotExists(KeyValuePair<TKey, TValue>(key, value));
+ }
+ bool AddIfNotExists(TKey && key, TValue && value)
+ {
+ return AddIfNotExists(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
+ }
+ void Remove(const TKey & key)
+ {
+ if (_count == 0)
+ return;
+ auto pos = FindPosition(key);
+ if (pos.ObjectPosition != -1)
{
- return ItemProxy(_Move(key), this);
+ SetDeleted(pos.ObjectPosition, true);
+ _count--;
}
- int Count() const
+ }
+ void Clear()
+ {
+ _count = 0;
+
+ marks.Clear();
+ }
+
+ template<typename T>
+ bool ContainsKey(const T & key) const
+ {
+ if (bucketSizeMinusOne == -1)
+ return false;
+ auto pos = FindPosition(key);
+ return pos.ObjectPosition != -1;
+ }
+ template<typename T>
+ bool TryGetValue(const T & key, TValue & value) const
+ {
+ if (bucketSizeMinusOne == -1)
+ return false;
+ auto pos = FindPosition(key);
+ if (pos.ObjectPosition != -1)
{
- return _count;
+ value = hashMap[pos.ObjectPosition].Value;
+ return true;
}
- private:
- template<typename... Args>
- void Init(const KeyValuePair<TKey, TValue> & kvPair, Args... args)
+ return false;
+ }
+ template<typename T>
+ TValue * TryGetValue(const T & key) const
+ {
+ if (bucketSizeMinusOne == -1)
+ return nullptr;
+ auto pos = FindPosition(key);
+ if (pos.ObjectPosition != -1)
{
- Add(kvPair);
- Init(args...);
+ return &hashMap[pos.ObjectPosition].Value;
}
+ return nullptr;
+ }
+ class ItemProxy
+ {
+ private:
+ const Dictionary<TKey, TValue> * dict;
+ TKey key;
public:
- Dictionary()
+ ItemProxy(const TKey & _key, const Dictionary<TKey, TValue> * _dict)
{
- bucketSizeMinusOne = -1;
- shiftBits = 32;
- _count = 0;
- hashMap = 0;
+ this->dict = _dict;
+ this->key = _key;
}
- template<typename Arg, typename... Args>
- Dictionary(Arg arg, Args... args)
+ ItemProxy(TKey && _key, const Dictionary<TKey, TValue> * _dict)
{
- Init(arg, args...);
+ this->dict = _dict;
+ this->key = _Move(_key);
}
- Dictionary(const Dictionary<TKey, TValue> & other)
- : bucketSizeMinusOne(-1), _count(0), hashMap(0)
+ TValue & GetValue() const
{
- *this = other;
+ auto pos = dict->FindPosition(key);
+ if (pos.ObjectPosition != -1)
+ {
+ return dict->hashMap[pos.ObjectPosition].Value;
+ }
+ else
+ throw KeyNotFoundException("The key does not exists in dictionary.");
}
- Dictionary(Dictionary<TKey, TValue> && other)
- : bucketSizeMinusOne(-1), _count(0), hashMap(0)
+ inline TValue & operator()() const
{
- *this = (_Move(other));
+ return GetValue();
}
- Dictionary<TKey, TValue> & operator = (const Dictionary<TKey, TValue> & other)
+ operator TValue&() const
{
- if (this == &other)
- return *this;
- Free();
- bucketSizeMinusOne = other.bucketSizeMinusOne;
- _count = other._count;
- shiftBits = other.shiftBits;
- hashMap = new KeyValuePair<TKey, TValue>[other.bucketSizeMinusOne + 1];
- marks = other.marks;
- for (int i = 0; i <= bucketSizeMinusOne; i++)
- hashMap[i] = other.hashMap[i];
- return *this;
+ return GetValue();
}
- Dictionary<TKey, TValue> & operator = (Dictionary<TKey, TValue> && other)
+ TValue & operator = (const TValue & val) const
{
- if (this == &other)
- return *this;
- Free();
- bucketSizeMinusOne = other.bucketSizeMinusOne;
- _count = other._count;
- hashMap = other.hashMap;
- shiftBits = other.shiftBits;
- marks = _Move(other.marks);
- other.hashMap = 0;
- other._count = 0;
- other.bucketSizeMinusOne = -1;
- return *this;
+ return ((Dictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), val));
}
- ~Dictionary()
+ TValue & operator = (TValue && val) const
{
- Free();
+ return ((Dictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), _Move(val)));
}
};
+ ItemProxy operator [](const TKey & key) const
+ {
+ return ItemProxy(key, this);
+ }
+ ItemProxy operator [](TKey && key) const
+ {
+ return ItemProxy(_Move(key), this);
+ }
+ int Count() const
+ {
+ return _count;
+ }
+ private:
+ template<typename... Args>
+ void Init(const KeyValuePair<TKey, TValue> & kvPair, Args... args)
+ {
+ Add(kvPair);
+ Init(args...);
+ }
+ public:
+ Dictionary()
+ {
+ bucketSizeMinusOne = -1;
+ shiftBits = 32;
+ _count = 0;
+ hashMap = 0;
+ }
+ template<typename Arg, typename... Args>
+ Dictionary(Arg arg, Args... args)
+ {
+ Init(arg, args...);
+ }
+ Dictionary(const Dictionary<TKey, TValue> & other)
+ : bucketSizeMinusOne(-1), _count(0), hashMap(0)
+ {
+ *this = other;
+ }
+ Dictionary(Dictionary<TKey, TValue> && other)
+ : bucketSizeMinusOne(-1), _count(0), hashMap(0)
+ {
+ *this = (_Move(other));
+ }
+ Dictionary<TKey, TValue> & operator = (const Dictionary<TKey, TValue> & other)
+ {
+ if (this == &other)
+ return *this;
+ Free();
+ bucketSizeMinusOne = other.bucketSizeMinusOne;
+ _count = other._count;
+ shiftBits = other.shiftBits;
+ hashMap = new KeyValuePair<TKey, TValue>[other.bucketSizeMinusOne + 1];
+ marks = other.marks;
+ for (int i = 0; i <= bucketSizeMinusOne; i++)
+ hashMap[i] = other.hashMap[i];
+ return *this;
+ }
+ Dictionary<TKey, TValue> & operator = (Dictionary<TKey, TValue> && other)
+ {
+ if (this == &other)
+ return *this;
+ Free();
+ bucketSizeMinusOne = other.bucketSizeMinusOne;
+ _count = other._count;
+ hashMap = other.hashMap;
+ shiftBits = other.shiftBits;
+ marks = _Move(other.marks);
+ other.hashMap = 0;
+ other._count = 0;
+ other.bucketSizeMinusOne = -1;
+ return *this;
+ }
+ ~Dictionary()
+ {
+ Free();
+ }
+ };
- template<typename TKey, typename TValue>
- class EnumerableDictionary
+ template<typename TKey, typename TValue>
+ class EnumerableDictionary
+ {
+ friend class Iterator;
+ friend class ItemProxy;
+ private:
+ inline int GetProbeOffset(int /*probeIdx*/) const
{
- friend class Iterator;
- friend class ItemProxy;
- private:
- inline int GetProbeOffset(int /*probeIdx*/) const
- {
- // quadratic probing
- return 1;
- }
- private:
- int bucketSizeMinusOne, shiftBits;
- int _count;
- IntSet marks;
+ // quadratic probing
+ return 1;
+ }
+ private:
+ int bucketSizeMinusOne, shiftBits;
+ int _count;
+ IntSet marks;
- // debug op
- struct Op
- {
- TKey key;
- int opType;
- Op()
- {}
- Op(const TKey & key, int t)
- {
- this->key = key;
- opType = t;
- }
- };
- LinkedList<KeyValuePair<TKey, TValue>> kvPairs;
- LinkedNode<KeyValuePair<TKey, TValue>>** hashMap;
- void Free()
- {
- if (hashMap)
- delete[] hashMap;
- hashMap = 0;
- kvPairs.Clear();
- }
- inline bool IsDeleted(int pos) const
- {
- return marks.Contains((pos << 1) + 1);
- }
- inline bool IsEmpty(int pos) const
+ // debug op
+ struct Op
+ {
+ TKey key;
+ int opType;
+ Op()
+ {}
+ Op(const TKey & key, int t)
{
- return !marks.Contains((pos << 1));
+ this->key = key;
+ opType = t;
}
- inline void SetDeleted(int pos, bool val)
+ };
+ LinkedList<KeyValuePair<TKey, TValue>> kvPairs;
+ LinkedNode<KeyValuePair<TKey, TValue>>** hashMap;
+ void Free()
+ {
+ if (hashMap)
+ delete[] hashMap;
+ hashMap = 0;
+ kvPairs.Clear();
+ }
+ inline bool IsDeleted(int pos) const
+ {
+ return marks.Contains((pos << 1) + 1);
+ }
+ inline bool IsEmpty(int pos) const
+ {
+ return !marks.Contains((pos << 1));
+ }
+ inline void SetDeleted(int pos, bool val)
+ {
+ if (val)
+ marks.Add((pos << 1) + 1);
+ else
+ marks.Remove((pos << 1) + 1);
+ }
+ inline void SetEmpty(int pos, bool val)
+ {
+ if (val)
+ marks.Remove((pos << 1));
+ else
+ marks.Add((pos << 1));
+ }
+ struct FindPositionResult
+ {
+ int ObjectPosition;
+ int InsertionPosition;
+ FindPositionResult()
{
- if (val)
- marks.Add((pos << 1) + 1);
- else
- marks.Remove((pos << 1) + 1);
+ ObjectPosition = -1;
+ InsertionPosition = -1;
}
- inline void SetEmpty(int pos, bool val)
+ FindPositionResult(int objPos, int insertPos)
{
- if (val)
- marks.Remove((pos << 1));
- else
- marks.Add((pos << 1));
+ ObjectPosition = objPos;
+ InsertionPosition = insertPos;
}
- struct FindPositionResult
- {
- int ObjectPosition;
- int InsertionPosition;
- FindPositionResult()
- {
- ObjectPosition = -1;
- InsertionPosition = -1;
- }
- FindPositionResult(int objPos, int insertPos)
- {
- ObjectPosition = objPos;
- InsertionPosition = insertPos;
- }
- };
- template<typename T>
- inline int GetHashPos(T & key) const
- {
- return ((unsigned int)(GetHashCode(key) * 2654435761)) >> shiftBits;
- }
- template<typename T>
- FindPositionResult FindPosition(const T & key) const
+ };
+ template<typename T>
+ inline int GetHashPos(T & key) const
+ {
+ return ((unsigned int)(GetHashCode(key) * 2654435761)) >> shiftBits;
+ }
+ template<typename T>
+ FindPositionResult FindPosition(const T & key) const
+ {
+ int hashPos = GetHashPos((T&)key);
+ int insertPos = -1;
+ int numProbes = 0;
+ while (numProbes <= bucketSizeMinusOne)
{
- int hashPos = GetHashPos((T&)key);
- int insertPos = -1;
- int numProbes = 0;
- while (numProbes <= bucketSizeMinusOne)
+ if (IsEmpty(hashPos))
{
- if (IsEmpty(hashPos))
- {
- if (insertPos == -1)
- return FindPositionResult(-1, hashPos);
- else
- return FindPositionResult(-1, insertPos);
- }
- else if (IsDeleted(hashPos))
- {
- if (insertPos == -1)
- insertPos = hashPos;
- }
- else if (hashMap[hashPos]->Value.Key == key)
- {
- return FindPositionResult(hashPos, -1);
- }
- numProbes++;
- hashPos = (hashPos + GetProbeOffset(numProbes)) & bucketSizeMinusOne;
+ if (insertPos == -1)
+ return FindPositionResult(-1, hashPos);
+ else
+ return FindPositionResult(-1, insertPos);
}
- if (insertPos != -1)
- return FindPositionResult(-1, insertPos);
- throw InvalidOperationException("Hash map is full. This indicates an error in Key::Equal or Key::GetHashCode.");
- }
- TValue & _Insert(KeyValuePair<TKey, TValue> && kvPair, int pos)
- {
- auto node = kvPairs.AddLast();
- node->Value = _Move(kvPair);
- hashMap[pos] = node;
- SetEmpty(pos, false);
- SetDeleted(pos, false);
- return node->Value.Value;
- }
- void Rehash()
- {
- if (bucketSizeMinusOne == -1 || _count / (float)bucketSizeMinusOne >= MaxLoadFactor)
+ else if (IsDeleted(hashPos))
{
- int newSize = (bucketSizeMinusOne + 1) * 2;
- int newShiftBits = shiftBits - 1;
- if (newSize == 0)
- {
- newSize = 16;
- newShiftBits = 28;
- }
- EnumerableDictionary<TKey, TValue> newDict;
- newDict.shiftBits = newShiftBits;
- newDict.bucketSizeMinusOne = newSize - 1;
- newDict.hashMap = new LinkedNode<KeyValuePair<TKey, TValue>>*[newSize];
- newDict.marks.SetMax(newSize * 2);
- if (hashMap)
- {
- for (auto & kvPair : *this)
- {
- newDict.Add(_Move(kvPair));
- }
- }
- *this = _Move(newDict);
+ if (insertPos == -1)
+ insertPos = hashPos;
}
- }
-
- bool AddIfNotExists(KeyValuePair<TKey, TValue> && kvPair)
- {
- Rehash();
- auto pos = FindPosition(kvPair.Key);
- if (pos.ObjectPosition != -1)
- return false;
- else if (pos.InsertionPosition != -1)
+ else if (hashMap[hashPos]->Value.Key == key)
{
- _count++;
- _Insert(_Move(kvPair), pos.InsertionPosition);
- return true;
+ return FindPositionResult(hashPos, -1);
}
- else
- throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
- }
- void Add(KeyValuePair<TKey, TValue> && kvPair)
- {
- if (!AddIfNotExists(_Move(kvPair)))
- throw KeyExistsException("The key already exists in Dictionary.");
+ numProbes++;
+ hashPos = (hashPos + GetProbeOffset(numProbes)) & bucketSizeMinusOne;
}
- TValue & Set(KeyValuePair<TKey, TValue> && kvPair)
+ if (insertPos != -1)
+ return FindPositionResult(-1, insertPos);
+ throw InvalidOperationException("Hash map is full. This indicates an error in Key::Equal or Key::GetHashCode.");
+ }
+ TValue & _Insert(KeyValuePair<TKey, TValue> && kvPair, int pos)
+ {
+ auto node = kvPairs.AddLast();
+ node->Value = _Move(kvPair);
+ hashMap[pos] = node;
+ SetEmpty(pos, false);
+ SetDeleted(pos, false);
+ return node->Value.Value;
+ }
+ void Rehash()
+ {
+ if (bucketSizeMinusOne == -1 || _count / (float)bucketSizeMinusOne >= MaxLoadFactor)
{
- Rehash();
- auto pos = FindPosition(kvPair.Key);
- if (pos.ObjectPosition != -1)
+ int newSize = (bucketSizeMinusOne + 1) * 2;
+ int newShiftBits = shiftBits - 1;
+ if (newSize == 0)
{
- hashMap[pos.ObjectPosition]->Delete();
- return _Insert(_Move(kvPair), pos.ObjectPosition);
+ newSize = 16;
+ newShiftBits = 28;
}
- else if (pos.InsertionPosition != -1)
- {
- _count++;
- return _Insert(_Move(kvPair), pos.InsertionPosition);
- }
- else
- throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
- }
- public:
- typedef typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator Iterator;
-
- typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator begin() const
- {
- return kvPairs.begin();
- }
- typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator end() const
- {
- return kvPairs.end();
- }
- public:
- void Add(const TKey & key, const TValue & value)
- {
- Add(KeyValuePair<TKey, TValue>(key, value));
- }
- void Add(TKey && key, TValue && value)
- {
- Add(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
- }
- bool AddIfNotExists(const TKey & key, const TValue & value)
- {
- return AddIfNotExists(KeyValuePair<TKey, TValue>(key, value));
- }
- bool AddIfNotExists(TKey && key, TValue && value)
- {
- return AddIfNotExists(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
- }
- void Remove(const TKey & key)
- {
- if (_count > 0)
+ EnumerableDictionary<TKey, TValue> newDict;
+ newDict.shiftBits = newShiftBits;
+ newDict.bucketSizeMinusOne = newSize - 1;
+ newDict.hashMap = new LinkedNode<KeyValuePair<TKey, TValue>>*[newSize];
+ newDict.marks.SetMax(newSize * 2);
+ if (hashMap)
{
- auto pos = FindPosition(key);
- if (pos.ObjectPosition != -1)
+ for (auto & kvPair : *this)
{
- kvPairs.Delete(hashMap[pos.ObjectPosition]);
- hashMap[pos.ObjectPosition] = 0;
- SetDeleted(pos.ObjectPosition, true);
- _count--;
+ newDict.Add(_Move(kvPair));
}
}
+ *this = _Move(newDict);
}
- void Clear()
+ }
+
+ bool AddIfNotExists(KeyValuePair<TKey, TValue> && kvPair)
+ {
+ Rehash();
+ auto pos = FindPosition(kvPair.Key);
+ if (pos.ObjectPosition != -1)
+ return false;
+ else if (pos.InsertionPosition != -1)
{
- _count = 0;
- kvPairs.Clear();
- marks.Clear();
+ _count++;
+ _Insert(_Move(kvPair), pos.InsertionPosition);
+ return true;
}
- template<typename T>
- bool ContainsKey(const T & key) const
+ else
+ throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
+ }
+ void Add(KeyValuePair<TKey, TValue> && kvPair)
+ {
+ if (!AddIfNotExists(_Move(kvPair)))
+ throw KeyExistsException("The key already exists in Dictionary.");
+ }
+ TValue & Set(KeyValuePair<TKey, TValue> && kvPair)
+ {
+ Rehash();
+ auto pos = FindPosition(kvPair.Key);
+ if (pos.ObjectPosition != -1)
{
- if (bucketSizeMinusOne == -1)
- return false;
- auto pos = FindPosition(key);
- return pos.ObjectPosition != -1;
+ hashMap[pos.ObjectPosition]->Delete();
+ return _Insert(_Move(kvPair), pos.ObjectPosition);
}
- template<typename T>
- TValue * TryGetValue(const T & key) const
+ else if (pos.InsertionPosition != -1)
{
- if (bucketSizeMinusOne == -1)
- return nullptr;
- auto pos = FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- return &(hashMap[pos.ObjectPosition]->Value.Value);
- }
- return nullptr;
+ _count++;
+ return _Insert(_Move(kvPair), pos.InsertionPosition);
}
- template<typename T>
- bool TryGetValue(const T & key, TValue & value) const
+ else
+ throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
+ }
+ public:
+ typedef typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator Iterator;
+
+ typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator begin() const
+ {
+ return kvPairs.begin();
+ }
+ typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator end() const
+ {
+ return kvPairs.end();
+ }
+ public:
+ void Add(const TKey & key, const TValue & value)
+ {
+ Add(KeyValuePair<TKey, TValue>(key, value));
+ }
+ void Add(TKey && key, TValue && value)
+ {
+ Add(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
+ }
+ bool AddIfNotExists(const TKey & key, const TValue & value)
+ {
+ return AddIfNotExists(KeyValuePair<TKey, TValue>(key, value));
+ }
+ bool AddIfNotExists(TKey && key, TValue && value)
+ {
+ return AddIfNotExists(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
+ }
+ void Remove(const TKey & key)
+ {
+ if (_count > 0)
{
- if (bucketSizeMinusOne == -1)
- return false;
auto pos = FindPosition(key);
if (pos.ObjectPosition != -1)
{
- value = hashMap[pos.ObjectPosition]->Value.Value;
- return true;
- }
- return false;
- }
- class ItemProxy
- {
- private:
- const EnumerableDictionary<TKey, TValue> * dict;
- TKey key;
- public:
- ItemProxy(const TKey & _key, const EnumerableDictionary<TKey, TValue> * _dict)
- {
- this->dict = _dict;
- this->key = _key;
- }
- ItemProxy(TKey && _key, const EnumerableDictionary<TKey, TValue> * _dict)
- {
- this->dict = _dict;
- this->key = _Move(_key);
- }
- TValue & GetValue() const
- {
- auto pos = dict->FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- return dict->hashMap[pos.ObjectPosition]->Value.Value;
- }
- else
- {
- throw KeyNotFoundException("The key does not exists in dictionary.");
- }
- }
- inline TValue & operator()() const
- {
- return GetValue();
- }
- operator TValue&() const
- {
- return GetValue();
- }
- TValue & operator = (const TValue & val)
- {
- return ((EnumerableDictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), val));
- }
- TValue & operator = (TValue && val)
- {
- return ((EnumerableDictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), _Move(val)));
+ kvPairs.Delete(hashMap[pos.ObjectPosition]);
+ hashMap[pos.ObjectPosition] = 0;
+ SetDeleted(pos.ObjectPosition, true);
+ _count--;
}
- };
- ItemProxy operator [](const TKey & key) const
- {
- return ItemProxy(key, this);
- }
- ItemProxy operator [](TKey && key) const
- {
- return ItemProxy(_Move(key), this);
}
- int Count() const
- {
- return _count;
- }
- KeyValuePair<TKey, TValue> & First() const
+ }
+ void Clear()
+ {
+ _count = 0;
+ kvPairs.Clear();
+ marks.Clear();
+ }
+ template<typename T>
+ bool ContainsKey(const T & key) const
+ {
+ if (bucketSizeMinusOne == -1)
+ return false;
+ auto pos = FindPosition(key);
+ return pos.ObjectPosition != -1;
+ }
+ template<typename T>
+ TValue * TryGetValue(const T & key) const
+ {
+ if (bucketSizeMinusOne == -1)
+ return nullptr;
+ auto pos = FindPosition(key);
+ if (pos.ObjectPosition != -1)
{
- return kvPairs.First();
+ return &(hashMap[pos.ObjectPosition]->Value.Value);
}
- KeyValuePair<TKey, TValue> & Last() const
+ return nullptr;
+ }
+ template<typename T>
+ bool TryGetValue(const T & key, TValue & value) const
+ {
+ if (bucketSizeMinusOne == -1)
+ return false;
+ auto pos = FindPosition(key);
+ if (pos.ObjectPosition != -1)
{
- return kvPairs.Last();
+ value = hashMap[pos.ObjectPosition]->Value.Value;
+ return true;
}
+ return false;
+ }
+ class ItemProxy
+ {
private:
- template<typename... Args>
- void Init(const KeyValuePair<TKey, TValue> & kvPair, Args... args)
- {
- Add(kvPair);
- Init(args...);
- }
+ const EnumerableDictionary<TKey, TValue> * dict;
+ TKey key;
public:
- EnumerableDictionary()
+ ItemProxy(const TKey & _key, const EnumerableDictionary<TKey, TValue> * _dict)
{
- bucketSizeMinusOne = -1;
- shiftBits = 32;
- _count = 0;
- hashMap = 0;
+ this->dict = _dict;
+ this->key = _key;
}
- template<typename Arg, typename... Args>
- EnumerableDictionary(Arg arg, Args... args)
+ ItemProxy(TKey && _key, const EnumerableDictionary<TKey, TValue> * _dict)
{
- Init(arg, args...);
+ this->dict = _dict;
+ this->key = _Move(_key);
}
- EnumerableDictionary(const EnumerableDictionary<TKey, TValue> & other)
- : bucketSizeMinusOne(-1), _count(0), hashMap(0)
+ TValue & GetValue() const
{
- *this = other;
+ auto pos = dict->FindPosition(key);
+ if (pos.ObjectPosition != -1)
+ {
+ return dict->hashMap[pos.ObjectPosition]->Value.Value;
+ }
+ else
+ {
+ throw KeyNotFoundException("The key does not exists in dictionary.");
+ }
}
- EnumerableDictionary(EnumerableDictionary<TKey, TValue> && other)
- : bucketSizeMinusOne(-1), _count(0), hashMap(0)
+ inline TValue & operator()() const
{
- *this = (_Move(other));
+ return GetValue();
}
- EnumerableDictionary<TKey, TValue> & operator = (const EnumerableDictionary<TKey, TValue> & other)
+ operator TValue&() const
{
- if (this == &other)
- return *this;
- Clear();
- for (auto & item : other)
- Add(item.Key, item.Value);
- return *this;
+ return GetValue();
}
- EnumerableDictionary<TKey, TValue> & operator = (EnumerableDictionary<TKey, TValue> && other)
+ TValue & operator = (const TValue & val)
{
- if (this == &other)
- return *this;
- Free();
- bucketSizeMinusOne = other.bucketSizeMinusOne;
- _count = other._count;
- hashMap = other.hashMap;
- shiftBits = other.shiftBits;
- marks = _Move(other.marks);
- other.hashMap = 0;
- other._count = 0;
- other.bucketSizeMinusOne = -1;
- kvPairs = _Move(other.kvPairs);
- return *this;
+ return ((EnumerableDictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), val));
}
- ~EnumerableDictionary()
+ TValue & operator = (TValue && val)
{
- Free();
+ return ((EnumerableDictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), _Move(val)));
}
};
+ ItemProxy operator [](const TKey & key) const
+ {
+ return ItemProxy(key, this);
+ }
+ ItemProxy operator [](TKey && key) const
+ {
+ return ItemProxy(_Move(key), this);
+ }
+ int Count() const
+ {
+ return _count;
+ }
+ KeyValuePair<TKey, TValue> & First() const
+ {
+ return kvPairs.First();
+ }
+ KeyValuePair<TKey, TValue> & Last() const
+ {
+ return kvPairs.Last();
+ }
+ private:
+ template<typename... Args>
+ void Init(const KeyValuePair<TKey, TValue> & kvPair, Args... args)
+ {
+ Add(kvPair);
+ Init(args...);
+ }
+ public:
+ EnumerableDictionary()
+ {
+ bucketSizeMinusOne = -1;
+ shiftBits = 32;
+ _count = 0;
+ hashMap = 0;
+ }
+ template<typename Arg, typename... Args>
+ EnumerableDictionary(Arg arg, Args... args)
+ {
+ Init(arg, args...);
+ }
+ EnumerableDictionary(const EnumerableDictionary<TKey, TValue> & other)
+ : bucketSizeMinusOne(-1), _count(0), hashMap(0)
+ {
+ *this = other;
+ }
+ EnumerableDictionary(EnumerableDictionary<TKey, TValue> && other)
+ : bucketSizeMinusOne(-1), _count(0), hashMap(0)
+ {
+ *this = (_Move(other));
+ }
+ EnumerableDictionary<TKey, TValue> & operator = (const EnumerableDictionary<TKey, TValue> & other)
+ {
+ if (this == &other)
+ return *this;
+ Clear();
+ for (auto & item : other)
+ Add(item.Key, item.Value);
+ return *this;
+ }
+ EnumerableDictionary<TKey, TValue> & operator = (EnumerableDictionary<TKey, TValue> && other)
+ {
+ if (this == &other)
+ return *this;
+ Free();
+ bucketSizeMinusOne = other.bucketSizeMinusOne;
+ _count = other._count;
+ hashMap = other.hashMap;
+ shiftBits = other.shiftBits;
+ marks = _Move(other.marks);
+ other.hashMap = 0;
+ other._count = 0;
+ other.bucketSizeMinusOne = -1;
+ kvPairs = _Move(other.kvPairs);
+ return *this;
+ }
+ ~EnumerableDictionary()
+ {
+ Free();
+ }
+ };
- class _DummyClass
- {};
+ class _DummyClass
+ {};
- template<typename T, typename DictionaryType>
- class HashSetBase
+ template<typename T, typename DictionaryType>
+ class HashSetBase
+ {
+ protected:
+ DictionaryType dict;
+ private:
+ template<typename... Args>
+ void Init(const T & v, Args... args)
+ {
+ Add(v);
+ Init(args...);
+ }
+ public:
+ HashSetBase()
+ {}
+ template<typename Arg, typename... Args>
+ HashSetBase(Arg arg, Args... args)
+ {
+ Init(arg, args...);
+ }
+ HashSetBase(const HashSetBase & set)
+ {
+ operator=(set);
+ }
+ HashSetBase(HashSetBase && set)
+ {
+ operator=(_Move(set));
+ }
+ HashSetBase & operator = (const HashSetBase & set)
+ {
+ dict = set.dict;
+ return *this;
+ }
+ HashSetBase & operator = (HashSetBase && set)
+ {
+ dict = _Move(set.dict);
+ return *this;
+ }
+ public:
+ class Iterator
{
- protected:
- DictionaryType dict;
private:
- template<typename... Args>
- void Init(const T & v, Args... args)
- {
- Add(v);
- Init(args...);
- }
+ typename DictionaryType::Iterator iter;
public:
- HashSetBase()
- {}
- template<typename Arg, typename... Args>
- HashSetBase(Arg arg, Args... args)
- {
- Init(arg, args...);
- }
- HashSetBase(const HashSetBase & set)
+ Iterator() = default;
+ T & operator *() const
{
- operator=(set);
+ return (*iter).Key;
}
- HashSetBase(HashSetBase && set)
+ T * operator ->() const
{
- operator=(_Move(set));
+ return &(*iter).Key;
}
- HashSetBase & operator = (const HashSetBase & set)
+ Iterator & operator ++()
{
- dict = set.dict;
+ ++iter;
return *this;
}
- HashSetBase & operator = (HashSetBase && set)
- {
- dict = _Move(set.dict);
- return *this;
- }
- public:
- class Iterator
- {
- private:
- typename DictionaryType::Iterator iter;
- public:
- Iterator() = default;
- T & operator *() const
- {
- return (*iter).Key;
- }
- T * operator ->() const
- {
- return &(*iter).Key;
- }
- Iterator & operator ++()
- {
- ++iter;
- return *this;
- }
- Iterator operator ++(int)
- {
- Iterator rs = *this;
- operator++();
- return rs;
- }
- bool operator != (const Iterator & _that) const
- {
- return iter != _that.iter;
- }
- bool operator == (const Iterator & _that) const
- {
- return iter == _that.iter;
- }
- Iterator(const typename DictionaryType::Iterator & _iter)
- {
- this->iter = _iter;
- }
- };
- Iterator begin() const
- {
- return Iterator(dict.begin());
- }
- Iterator end() const
- {
- return Iterator(dict.end());
- }
- public:
- int Count() const
- {
- return dict.Count();
- }
- void Clear()
- {
- dict.Clear();
- }
- bool Add(const T& obj)
+ Iterator operator ++(int)
{
- return dict.AddIfNotExists(obj, _DummyClass());
+ Iterator rs = *this;
+ operator++();
+ return rs;
}
- bool Add(T && obj)
+ bool operator != (const Iterator & _that) const
{
- return dict.AddIfNotExists(_Move(obj), _DummyClass());
+ return iter != _that.iter;
}
- void Remove(const T & obj)
+ bool operator == (const Iterator & _that) const
{
- dict.Remove(obj);
+ return iter == _that.iter;
}
- bool Contains(const T & obj) const
+ Iterator(const typename DictionaryType::Iterator & _iter)
{
- return dict.ContainsKey(obj);
+ this->iter = _iter;
}
};
- template <typename T>
- class HashSet : public HashSetBase<T, Dictionary<T, _DummyClass>>
- {};
+ Iterator begin() const
+ {
+ return Iterator(dict.begin());
+ }
+ Iterator end() const
+ {
+ return Iterator(dict.end());
+ }
+ public:
+ int Count() const
+ {
+ return dict.Count();
+ }
+ void Clear()
+ {
+ dict.Clear();
+ }
+ bool Add(const T& obj)
+ {
+ return dict.AddIfNotExists(obj, _DummyClass());
+ }
+ bool Add(T && obj)
+ {
+ return dict.AddIfNotExists(_Move(obj), _DummyClass());
+ }
+ void Remove(const T & obj)
+ {
+ dict.Remove(obj);
+ }
+ bool Contains(const T & obj) const
+ {
+ return dict.ContainsKey(obj);
+ }
+ };
+ template <typename T>
+ class HashSet : public HashSetBase<T, Dictionary<T, _DummyClass>>
+ {};
- template <typename T>
- class EnumerableHashSet : public HashSetBase<T, EnumerableDictionary<T, _DummyClass>>
+ template <typename T>
+ class EnumerableHashSet : public HashSetBase<T, EnumerableDictionary<T, _DummyClass>>
+ {
+ public:
+ T & First() const
{
- public:
- T & First() const
- {
- return this->dict.First().Key;
- }
- T & Last() const
- {
- return this->dict.Last().Key;
- }
- };
- }
+ return this->dict.First().Key;
+ }
+ T & Last() const
+ {
+ return this->dict.Last().Key;
+ }
+ };
}
#endif
generated by cgit v1.2.3 (git 2.39.1) at 2026-06-04 06:54:40 +0000