| //+------------------------------------------------------------------+
|
| //| HashSet.mqh |
|
| //| Copyright 2000-2025, MetaQuotes Ltd. |
|
| //| https://www.mql5.com |
|
| //+------------------------------------------------------------------+
|
| #include<Generic\Interfaces\ISet.mqh>
|
| #include <Generic\Internal\PrimeGenerator.mqh>
|
| #include <Generic\Interfaces\IEqualityComparer.mqh>
|
| #include <Generic\Internal\DefaultEqualityComparer.mqh>
|
| //+------------------------------------------------------------------+
|
| //| Struct Slot<T>. |
|
| //| Usage: Internal structure for organization CHashSet<T>. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| struct Slot
|
| {
|
| public:
|
| int hash_code;
|
| T value;
|
| int next;
|
| Slot(void): hash_code(0),value((T)NULL),next(0) {}
|
| };
|
| //+------------------------------------------------------------------+
|
| //| Class CHashSet<T>. |
|
| //| Usage: Represents a set of unique values. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| class CHashSet: public ISet<T>
|
| {
|
| protected:
|
| int m_buckets[];
|
| Slot<T> m_slots[];
|
| int m_count;
|
| int m_last_index;
|
| int m_free_list;
|
| IEqualityComparer<T>*m_comparer;
|
| bool m_delete_comparer;
|
|
|
| public:
|
| CHashSet(void);
|
| CHashSet(IEqualityComparer<T>*comparer);
|
| CHashSet(ICollection<T>*collection);
|
| CHashSet(ICollection<T>*collection,IEqualityComparer<T>*comparer);
|
| CHashSet(T &array[]);
|
| CHashSet(T &array[],IEqualityComparer<T>*comparer);
|
| ~CHashSet(void);
|
| //--- methods of filling data
|
| bool Add(T value);
|
| //--- methods of access to protected data
|
| int Count(void) { return(m_count); }
|
| IEqualityComparer<T>* Comparer(void) const { return(m_comparer); }
|
| bool Contains(T item);
|
| void TrimExcess(void);
|
| //--- methods of copy data from collection
|
| int CopyTo(T &ds_array[],const int dst_start=0);
|
| //--- methods of cleaning and deleting
|
| void Clear(void);
|
| bool Remove(T item);
|
| //--- methods of changing sets
|
| void ExceptWith(ICollection<T>*collection);
|
| void ExceptWith(T &array[]);
|
| void IntersectWith(ICollection<T>*collection);
|
| void IntersectWith(T &array[]);
|
| void SymmetricExceptWith(ICollection<T>*collection);
|
| void SymmetricExceptWith(T &array[]);
|
| void UnionWith(ICollection<T>*collection);
|
| void UnionWith(T &array[]);
|
| //--- methods for determining the relationship between sets
|
| bool IsProperSubsetOf(ICollection<T>*collection);
|
| bool IsProperSubsetOf(T &array[]);
|
| bool IsProperSupersetOf(ICollection<T>*collection);
|
| bool IsProperSupersetOf(T &array[]);
|
| bool IsSubsetOf(ICollection<T>*collection);
|
| bool IsSubsetOf(T &array[]);
|
| bool IsSupersetOf(ICollection<T>*collection);
|
| bool IsSupersetOf(T &array[]);
|
| bool Overlaps(ICollection<T>*collection);
|
| bool Overlaps(T &array[]);
|
| bool SetEquals(ICollection<T>*collection);
|
| bool SetEquals(T &array[]);
|
|
|
| private:
|
| void SetCapacity(const int new_size,bool new_hash_codes);
|
| bool AddIfNotPresent(T value);
|
| void Initialize(const int capacity);
|
| void InternalSymmetricExceptWith(CHashSet<T>*set);
|
| bool InternalIsSubsetOf(CHashSet<T>*set);
|
| bool InternalIsSupersetOf(CHashSet<T>*set);
|
| bool InternalIsProperSubsetOf(CHashSet<T>*set);
|
| bool InternalIsProperSupersetOf(CHashSet<T>*set);
|
| };
|
| //+------------------------------------------------------------------+
|
| //| Initializes a new instance of the CHashSet<T> class that is empty|
|
| //| and uses the default equality comparer for the set type. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| CHashSet::CHashSet(void): m_count(0),
|
| m_last_index(0),
|
| m_free_list(-1)
|
| {
|
| //--- use default equality comaprer
|
| m_comparer=new CDefaultEqualityComparer<T>();
|
| m_delete_comparer=true;
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Initializes a new instance of the CHashSet<T> class that is empty|
|
| //| and uses the specified equality comparer for the set type. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| CHashSet::CHashSet(IEqualityComparer<T>*comparer): m_count(0),
|
| m_last_index(0),
|
| m_free_list(-1)
|
| {
|
| //--- check equality comaprer
|
| if(CheckPointer(comparer)==POINTER_INVALID)
|
| {
|
| //--- use default equality comaprer
|
| m_comparer=new CDefaultEqualityComparer<T>();
|
| m_delete_comparer=true;
|
| }
|
| else
|
| {
|
| //--- use specified equality comaprer
|
| m_comparer=comparer;
|
| m_delete_comparer=false;
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Initializes a new instance of the CHashSet<T> class that uses the|
|
| //| default equality comparer for the set type, contains elements |
|
| //| copied from the specified collection, and has sufficient capacity|
|
| //| to accommodate the number of elements copied. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| CHashSet::CHashSet(ICollection<T>*collection): m_count(0),
|
| m_last_index(0),
|
| m_free_list(-1)
|
| {
|
| //--- use default equality comaprer
|
| m_comparer=new CDefaultEqualityComparer<T>();
|
| m_delete_comparer=true;
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return;
|
| //--- set capacity for elements of the collection
|
| int count=collection.Count();
|
| Initialize(count);
|
| //--- add element from collection to the set
|
| this.UnionWith(collection);
|
| if((m_count==0 && ArraySize(m_slots)>3) ||
|
| (m_count>0 && ArraySize(m_slots)/m_count>3))
|
| TrimExcess();
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Initializes a new instance of the CHashSet<T> class that uses the|
|
| //| specified equality comparer for the set type, contains elements |
|
| //| copied from the specified collection, and has sufficient capacity|
|
| //| to accommodate the number of elements copied. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| CHashSet::CHashSet(ICollection<T>*collection,IEqualityComparer<T>*comparer): m_count(0),
|
| m_last_index(0),
|
| m_free_list(-1)
|
| {
|
| //--- check equality comaprer
|
| if(CheckPointer(comparer)==POINTER_INVALID)
|
| {
|
| //--- use default equality comaprer
|
| m_comparer=new CDefaultEqualityComparer<T>();
|
| m_delete_comparer=true;
|
| }
|
| else
|
| {
|
| //--- use specified comaprer
|
| m_comparer=comparer;
|
| m_delete_comparer=false;
|
| }
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return;
|
| //--- set capacity for elements of the collection
|
| int count=collection.Count();
|
| Initialize(count);
|
| //--- add element from collection to the set
|
| this.UnionWith(collection);
|
| if((m_count==0 && ArraySize(m_slots)>3) ||
|
| (m_count>0 && ArraySize(m_slots)/m_count>3))
|
| TrimExcess();
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Initializes a new instance of the CHashSet<T> class that uses the|
|
| //| default equality comparer for the set type, contains elements |
|
| //| copied from the specified array, and has sufficient capacity to |
|
| //| accommodate the number of elements copied. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| CHashSet::CHashSet(T &array[]): m_count(0),
|
| m_last_index(0),
|
| m_free_list(-1)
|
| {
|
| //--- use default equality comaprer
|
| m_comparer=new CDefaultEqualityComparer<T>();
|
| m_delete_comparer=true;
|
| //--- set capacity for elements of the array
|
| int count=ArraySize(array);
|
| Initialize(count);
|
| //--- add element from array to the set
|
| this.UnionWith(array);
|
| if((m_count==0 && ArraySize(m_slots)>3) ||
|
| (m_count>0 && ArraySize(m_slots)/m_count>3))
|
| TrimExcess();
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Initializes a new instance of the CHashSet<T> class that uses the|
|
| //| specified equality comparer for the set type, contains elements |
|
| //| copied from the specified array, and has sufficient capacity to |
|
| //| accommodate the number of elements copied. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| CHashSet::CHashSet(T &array[],IEqualityComparer<T>*comparer): m_count(0),
|
| m_last_index(0),
|
| m_free_list(-1)
|
| {
|
| //--- check equality comaprer
|
| if(CheckPointer(comparer)==POINTER_INVALID)
|
| {
|
| //--- use default equality comaprer
|
| m_comparer=new CDefaultEqualityComparer<T>();
|
| m_delete_comparer=true;
|
| }
|
| else
|
| {
|
| //--- use specified comaprer
|
| m_comparer=comparer;
|
| m_delete_comparer=false;
|
| }
|
| //--- set capacity for elements of the array
|
| int count=ArraySize(array);
|
| Initialize(count);
|
| //--- add element from array to the set
|
| this.UnionWith(array);
|
| if((m_count==0 && ArraySize(m_slots)>3) ||
|
| (m_count>0 && ArraySize(m_slots)/m_count>3))
|
| TrimExcess();
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Destructor. |
|
| //+------------------------------------------------------------------+
|
| template<typename T> CHashSet::~CHashSet(void)
|
| {
|
| if(m_delete_comparer)
|
| delete m_comparer;
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Adds the specified element to a set. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::Add(T value)
|
| {
|
| return AddIfNotPresent(value);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set contains the specified element. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::Contains(T item)
|
| {
|
| //--- check buckets
|
| if(ArraySize(m_buckets)!=0)
|
| {
|
| //--- get hash code for item
|
| int hash_code=m_comparer.HashCode(item)&0x7FFFFFFF;
|
| //--- search item in the slots
|
| for(int i=m_buckets[hash_code%ArraySize(m_buckets)]-1; i>=0; i=m_slots[i].next)
|
| if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,item))
|
| return(true);
|
| }
|
| return(false);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Sets the capacity of a set to the actual number of elements it |
|
| //| contains, rounded up to a nearby, implementation-specific value. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::TrimExcess(void)
|
| {
|
| if(m_count==0)
|
| {
|
| ArrayFree(m_buckets);
|
| ArrayFree(m_slots);
|
| }
|
| else
|
| {
|
| //--- calculate min prime size for current count
|
| int new_size=CPrimeGenerator::GetPrime(m_count);
|
| //--- resize buckets and slots
|
| ArrayResize(m_slots,new_size);
|
| ArrayResize(m_buckets,new_size);
|
| //--- restore buckets and slots
|
| int new_index=0;
|
| for(int i=0; i<m_last_index; i++)
|
| {
|
| if(m_slots[i].hash_code>=0)
|
| {
|
| m_slots[new_index]=m_slots[i];
|
| //--- rehash
|
| int bucket=m_slots[new_index].hash_code%new_size;
|
| m_slots[new_index].next=m_buckets[bucket]-1;
|
| m_buckets[bucket]=new_index+1;
|
| //--- increment index
|
| new_index++;
|
| }
|
| }
|
| m_last_index=new_index;
|
| m_free_list=-1;
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Copies a range of elements from the set to a compatible |
|
| //| one-dimensional array. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| int CHashSet::CopyTo(T &dst_array[],const int dst_start)
|
| {
|
| //--- resize array
|
| if(dst_start+m_count>ArraySize(dst_array))
|
| ArrayResize(dst_array,dst_start+m_count);
|
| //--- start copy
|
| int index=0;
|
| for(int i=0; i<ArraySize(m_slots); i++)
|
| if(m_slots[i].hash_code>=0)
|
| {
|
| if(dst_start+index>=ArraySize(dst_array) || index>=m_count)
|
| return(index);
|
| dst_array[dst_start+index++]=m_slots[i].value;
|
| }
|
| return(index);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Removes all elements from a set. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::Clear(void)
|
| {
|
| if(m_last_index>0)
|
| {
|
| ArrayFree(m_slots);
|
| ArrayFree(m_buckets);
|
| m_last_index=0;
|
| m_count=0;
|
| m_free_list=-1;
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Removes the specified element from a set. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::Remove(T item)
|
| {
|
| if(ArraySize(m_buckets)!=0)
|
| {
|
| //--- get hash code for item
|
| int hash_code=m_comparer.HashCode(item)&0x7FFFFFFF;
|
| int bucket=hash_code%ArraySize(m_buckets);
|
| int last=-1;
|
| //--- search item
|
| for(int i=m_buckets[bucket]-1; i>=0; last=i,i=m_slots[i].next)
|
| {
|
| if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,item))
|
| {
|
| if(last<0)
|
| m_buckets[bucket]=m_slots[i].next+1;
|
| else
|
| m_slots[last].next=m_slots[i].next;
|
| //--- remove item
|
| m_slots[i].hash_code=-1;
|
| m_slots[i].value=(T)NULL;
|
| m_slots[i].next =m_free_list;
|
| //--- decrement count
|
| m_count--;
|
| if(m_count==0)
|
| {
|
| m_last_index= 0;
|
| m_free_list = -1;
|
| }
|
| else
|
| {
|
| m_free_list=i;
|
| }
|
| return(true);
|
| }
|
| }
|
| }
|
| return(false);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Removes all elements in the specified collection from the current|
|
| //| set. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::ExceptWith(ICollection<T>*collection)
|
| {
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return;
|
| //--- this is already the enpty set
|
| if(m_count==0)
|
| return;
|
| //--- special case if collecion is this
|
| //--- a set minus itself is the empty set
|
| if(collection==GetPointer(this))
|
| {
|
| Clear();
|
| return;
|
| }
|
| //--- copy collection to array
|
| T array[];
|
| collection.CopyTo(array,0);
|
| //--- remove every element in collection from this
|
| for(int i=0; i<ArraySize(array); i++)
|
| Remove(array[i]);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Removes all elements in the specified array from the current set.|
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::ExceptWith(T &array[])
|
| {
|
| //--- this is already the enpty set
|
| if(m_count==0)
|
| return;
|
| //--- remove every element in collection from this
|
| for(int i=0; i<ArraySize(array); i++)
|
| Remove(array[i]);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Modifies the current set to contain only elements that are |
|
| //| present in that object and in the specified collection. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::IntersectWith(ICollection<T>*collection)
|
| {
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return;
|
| //--- intersection of anything with empty set is empty set, so return if count is 0
|
| if(m_count==0)
|
| return;
|
| //--- if collection is empty, intersection is empty set
|
| if(collection.Count()==0)
|
| {
|
| Clear();
|
| return;
|
| }
|
| //--- intersect
|
| for(int i=0; i<m_last_index; i++)
|
| {
|
| if(m_slots[i].hash_code>=0)
|
| {
|
| T item=m_slots[i].value;
|
| if(!collection.Contains(item))
|
| Remove(item);
|
| }
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Modifies the current set to contain only elements that are |
|
| //| present in that object and in the specified array. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::IntersectWith(T &array[])
|
| {
|
| //--- intersection of anything with empty set is empty set, so return if count is 0
|
| if(m_count==0)
|
| return;
|
| //--- if collection is empty, intersection is empty set
|
| if(ArraySize(array)==0)
|
| {
|
| Clear();
|
| return;
|
| }
|
| //--- intersect
|
| CHashSet<T>set(array);
|
| for(int i=0; i<m_last_index; i++)
|
| {
|
| if(m_slots[i].hash_code>=0)
|
| {
|
| T item=m_slots[i].value;
|
| if(!set.Contains(item))
|
| Remove(item);
|
| }
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Modifies the current set to contain only elements that are |
|
| //| present either in that set or in the specified collection, but |
|
| //| not both. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::SymmetricExceptWith(ICollection<T>*collection)
|
| {
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return;
|
| //--- if set is empty, then symmetric difference is other
|
| if(m_count==0)
|
| {
|
| UnionWith(collection);
|
| return;
|
| }
|
| //--- special case this; the symmetric difference of a set with itself is the empty set
|
| if(collection==GetPointer(this))
|
| {
|
| Clear();
|
| return;
|
| }
|
| //--- check collection is set
|
| CHashSet<T>*ptr_set=dynamic_cast<CHashSet<T>*>(collection);
|
| if(CheckPointer(ptr_set)!=POINTER_INVALID)
|
| {
|
| InternalSymmetricExceptWith(ptr_set);
|
| }
|
| else
|
| {
|
| //--- create a set based on a specified collection
|
| CHashSet<T>set(collection);
|
| InternalSymmetricExceptWith(GetPointer(set));
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Modifies the current set to contain only elements that are |
|
| //| present either in that set or in the specified array, but not |
|
| //| both. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::SymmetricExceptWith(T &array[])
|
| {
|
| //--- if set is empty, then symmetric difference is other
|
| if(m_count==0)
|
| {
|
| UnionWith(array);
|
| return;
|
| }
|
| //--- symmetric except
|
| CHashSet<T>set(array);
|
| InternalSymmetricExceptWith(GetPointer(set));
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Modifies the current set to contain all elements that are present|
|
| //| in itself, the specified collection, or both. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::UnionWith(ICollection<T>*collection)
|
| {
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return;
|
| //--- get array from collection
|
| T array[];
|
| collection.CopyTo(array);
|
| //--- union array with the current set
|
| UnionWith(array);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Modifies the current set to contain all elements that are present|
|
| //| in itself, the specified array, or both. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::UnionWith(T &array[])
|
| {
|
| for(int i=0; i<ArraySize(array); i++)
|
| AddIfNotPresent(array[i]);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a proper subset of the specified |
|
| //| collection. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::IsProperSubsetOf(ICollection<T>*collection)
|
| {
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return(false);
|
| //--- the empty set is a proper subset of anything but the empty set
|
| if(m_count==0)
|
| return(collection.Count()>0);
|
| //--- check collection is set
|
| CHashSet<T>*ptr_set=dynamic_cast<CHashSet<T>*>(collection);
|
| if(CheckPointer(ptr_set)!=POINTER_INVALID)
|
| {
|
| return InternalIsProperSubsetOf(ptr_set);
|
| }
|
| else
|
| {
|
| //--- create a set based on a specified collection
|
| CHashSet<T>set(collection);
|
| return InternalIsProperSubsetOf(GetPointer(set));
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a proper subset of the specified |
|
| //| array. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::IsProperSubsetOf(T &array[])
|
| {
|
| //--- the empty set is a proper subset of anything but the empty set
|
| if(m_count==0)
|
| return(ArraySize(array)>0);
|
| //--- create a set based on a specified array
|
| CHashSet<T>set(array);
|
| return InternalIsProperSubsetOf(GetPointer(set));
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a proper superset of the specified |
|
| //| collection. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::IsProperSupersetOf(ICollection<T>*collection)
|
| {
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return(m_count>0);
|
| //--- the empty set is a proper subset of anything but the empty set
|
| if(m_count==0)
|
| return(false);
|
| //--- if other is the empty set then this is a superset
|
| if(collection.Count()==0)
|
| return(true);
|
| //--- check collection is set
|
| CHashSet<T>*ptr_set=dynamic_cast<CHashSet<T>*>(collection);
|
| if(CheckPointer(ptr_set)!=POINTER_INVALID)
|
| {
|
| return InternalIsProperSupersetOf(ptr_set);
|
| }
|
| else
|
| {
|
| //--- create a set based on a specified collection
|
| CHashSet<T>set(collection);
|
| return InternalIsProperSupersetOf(GetPointer(set));
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a proper superset of the specified |
|
| //| array. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::IsProperSupersetOf(T &array[])
|
| {
|
| //--- the empty set is a proper subset of anything but the empty set
|
| if(m_count==0)
|
| return(false);
|
| //--- if other is the empty set then this is a superset
|
| if(ArraySize(array)==0)
|
| return(true);
|
| //--- create a set based on a specified array
|
| CHashSet<T>set(array);
|
| return InternalIsProperSupersetOf(GetPointer(set));
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a subset of the specified collection.|
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::IsSubsetOf(ICollection<T>*collection)
|
| {
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return(m_count==0);
|
| //--- The empty set is a subset of any set
|
| if(m_count==0)
|
| return(true);
|
| //--- check collection is set
|
| CHashSet<T>*ptr_set=dynamic_cast<CHashSet<T>*>(collection);
|
| if(CheckPointer(ptr_set)!=POINTER_INVALID)
|
| {
|
| return InternalIsSubsetOf(ptr_set);
|
| }
|
| else
|
| {
|
| //--- create a set based on a specified collection
|
| CHashSet<T>set(collection);
|
| return InternalIsSubsetOf(GetPointer(set));
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a subset of the specified array. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::IsSubsetOf(T &array[])
|
| {
|
| //--- The empty set is a subset of any set
|
| if(m_count==0)
|
| return(true);
|
| //--- create a set based on a specified array
|
| CHashSet<T>set(array);
|
| return InternalIsSubsetOf(GetPointer(set));
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a superset of the specified |
|
| //| collection. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::IsSupersetOf(ICollection<T>*collection)
|
| {
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return(m_count>=0);
|
| //--- if other is the empty set then this is a superset
|
| if(collection.Count()==0)
|
| return(true);
|
| //--- check collection is set
|
| CHashSet<T>*ptr_set=dynamic_cast<CHashSet<T>*>(collection);
|
| if(CheckPointer(ptr_set)!=POINTER_INVALID)
|
| {
|
| return InternalIsSupersetOf(ptr_set);
|
| }
|
| else
|
| {
|
| //--- create a set based on a specified collection
|
| CHashSet<T>set(collection);
|
| return InternalIsSupersetOf(GetPointer(set));
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a superset of the specified array. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::IsSupersetOf(T &array[])
|
| {
|
| //--- if other is the empty set then this is a superset
|
| if(ArraySize(array)==0)
|
| return(true);
|
| //--- create a set based on a specified array
|
| CHashSet<T>set(array);
|
| return InternalIsSupersetOf(GetPointer(set));
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether the current set and a specified collection |
|
| //| share common elements. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::Overlaps(ICollection<T>*collection)
|
| {
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return(false);
|
| //--- check current count
|
| if(m_count==0)
|
| return(false);
|
| //--- get array from collection
|
| T array[];
|
| collection.CopyTo(array);
|
| //--- check overlaps between current set and array
|
| return Overlaps(array);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether the current set and a specified array share |
|
| //| common elements. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::Overlaps(T &array[])
|
| {
|
| //--- check current count
|
| if(m_count==0)
|
| return(false);
|
| //--- try to find any elements from specified array in current set
|
| for(int i=0; i<ArraySize(array); i++)
|
| if(Contains(array[i]))
|
| return(true);
|
| return(false);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set and the specified collection contain the|
|
| //| same elements. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::SetEquals(ICollection<T>*collection)
|
| {
|
| //--- check collection
|
| if(CheckPointer(collection)==POINTER_INVALID)
|
| return(false);
|
| //--- check current set is equal specified collection
|
| if(collection==GetPointer(this))
|
| return(true);
|
| //--- get array from collection
|
| T array[];
|
| collection.CopyTo(array);
|
| //--- check current set is equal specified array
|
| return SetEquals(array);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set and the specified array contain the same|
|
| //| elements. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::SetEquals(T &array[])
|
| {
|
| //--- check size
|
| if(ArraySize(array)!=m_count)
|
| return(false);
|
| //--- check current set is equal specified array
|
| for(int i=0; i<ArraySize(array); i++)
|
| if(!Contains(array[i]))
|
| return(false);
|
| return(true);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Set the underlying buckets array to size new_size and rehash. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::SetCapacity(const int new_size,bool new_hash_codes)
|
| {
|
| //--- resize slots
|
| ArrayResize(m_slots,new_size);
|
| //--- restore slots
|
| if(new_hash_codes)
|
| for(int i=0; i<m_last_index; i++)
|
| if(m_slots[i].hash_code!=-1)
|
| m_slots[i].hash_code=m_comparer.HashCode(m_slots[i].value)&0x7FFFFFFF;
|
| //--- resize buckets
|
| ArrayResize(m_buckets,new_size);
|
| ArrayFill(m_buckets,0,new_size,0);
|
| //--- restore buckets
|
| for(int i=0; i<m_last_index; i++)
|
| {
|
| int bucket=m_slots[i].hash_code%new_size;
|
| m_slots[i].next=m_buckets[bucket]-1;
|
| m_buckets[bucket]=i+1;
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Adds value to set if not contained already. Returns true if added|
|
| //| and false if already present. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::AddIfNotPresent(T value)
|
| {
|
| //--- set minimum capacity
|
| if(ArraySize(m_buckets)==0)
|
| Initialize(0);
|
| //--- get hash code and bucket for value
|
| int hash_code=m_comparer.HashCode(value)&0x7FFFFFFF;
|
| int bucket=hash_code%ArraySize(m_buckets);
|
| //--- check value already in the set
|
| for(int i=m_buckets[hash_code%ArraySize(m_buckets)]-1; i>=0; i=m_slots[i].next)
|
| if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,value))
|
| return(false);
|
| //--- calculate index for value
|
| int index=0;
|
| if(m_free_list>=0)
|
| {
|
| index=m_free_list;
|
| m_free_list=m_slots[index].next;
|
| }
|
| else
|
| {
|
| if(m_last_index==ArraySize(m_slots))
|
| {
|
| int new_size=CPrimeGenerator::ExpandPrime(m_count);
|
| SetCapacity(new_size,false);
|
| bucket=hash_code%ArraySize(m_buckets);
|
| }
|
| index=m_last_index;
|
| m_last_index++;
|
| }
|
| //--- set value
|
| m_slots[index].hash_code=hash_code;
|
| m_slots[index].value=value;
|
| m_slots[index].next=m_buckets[bucket]-1;
|
| m_buckets[bucket]=index+1;
|
| //--- increase count
|
| m_count++;
|
| return(true);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Initialize set with specified capacity. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::Initialize(const int capacity)
|
| {
|
| int size=CPrimeGenerator::GetPrime(capacity);
|
| ArrayResize(m_buckets,size);
|
| ArrayResize(m_slots,size);
|
| ZeroMemory(m_buckets);
|
| ZeroMemory(m_slots);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Modifies the current set to contain only elements that are |
|
| //| present either in that set or in the specified set, but not both.|
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| void CHashSet::InternalSymmetricExceptWith(CHashSet<T>*set)
|
| {
|
| for(int i=0; i<ArraySize(set.m_slots); i++)
|
| {
|
| T item=set.m_slots[i].value;
|
| if(!Remove(item))
|
| AddIfNotPresent(item);
|
| }
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a subset of the specified set. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::InternalIsSubsetOf(CHashSet<T>*set)
|
| {
|
| //--- if this has more elements then it can't be a subset
|
| if(m_count>set.m_count)
|
| return(false);
|
| //--- try to find any elements from current set in specified set
|
| for(int i=0; i<m_count; i++)
|
| {
|
| T item=m_slots[i].value;
|
| if(!set.Contains(item))
|
| return(false);
|
| }
|
| return(true);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a superset of the specified set. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::InternalIsSupersetOf(CHashSet<T>*set)
|
| {
|
| //--- if this has less elements then it can't be a superset
|
| if(set.m_count>m_count)
|
| return(false);
|
| //--- try to find any elements from specified set in current set
|
| for(int i=0; i<set.m_count; i++)
|
| {
|
| T item=set.m_slots[i].value;
|
| if(!Contains(item))
|
| return(false);
|
| }
|
| return(true);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a proper subset of the specified set.|
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::InternalIsProperSubsetOf(CHashSet<T>*set)
|
| {
|
| //--- if this has more or equal elements then it can't be a proper subset
|
| if(m_count>=set.m_count)
|
| return(false);
|
| //--- try to find any elements from current set in specified set
|
| for(int i=0; i<m_count; i++)
|
| {
|
| T item=m_slots[i].value;
|
| if(!set.Contains(item))
|
| return(false);
|
| }
|
| return(true);
|
| }
|
| //+------------------------------------------------------------------+
|
| //| Determines whether a set is a proper superset of the specified |
|
| //| set. |
|
| //+------------------------------------------------------------------+
|
| template<typename T>
|
| bool CHashSet::InternalIsProperSupersetOf(CHashSet<T>*set)
|
| {
|
| //--- if this has less or equal elements then it can't be a proper superset
|
| if(m_count<=set.m_count)
|
| return(false);
|
| //--- try to find any elements from specified set in current set
|
| for(int i=0; i<set.m_count; i++)
|
| {
|
| T item=set.m_slots[i].value;
|
| if(!Contains(item))
|
| return(false);
|
| }
|
| return(true);
|
| }
|
| //+------------------------------------------------------------------+
|
