Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_UTIL_SET_H__
00020 #define __CS_UTIL_SET_H__
00021
00022 #include "csutil/hash.h"
00023
00036 template <class T, class Allocator = CS::Memory::AllocatorMalloc>
00037 class csSet
00038 {
00039 public:
00040 typedef csHash<bool, T, Allocator> HashType;
00041
00042 private:
00043 typedef typename HashType::ConstGlobalIterator ParentIter;
00044 HashType map;
00045
00046 public:
00047
00049 class GlobalIterator
00050 {
00051 protected:
00052 ParentIter iter;
00053 GlobalIterator (const csSet<T>* s) : iter(s->map.GetIterator()) {}
00054
00055 public:
00056 friend class csSet<T>;
00057
00058 GlobalIterator () : iter() {}
00059 GlobalIterator (const GlobalIterator& o) : iter(o.iter) {}
00060 GlobalIterator& operator=(const GlobalIterator& o)
00061 { iter = o.iter; return *this; }
00062
00064 bool HasNext () const
00065 { return iter.HasNext(); }
00066
00068 T Next()
00069 {
00070 T key;
00071 iter.Next(key);
00072 return key;
00073 }
00074 };
00075 friend class GlobalIterator;
00076
00082 csSet (int size = 23, int grow_rate = 5, int max_size = 20000)
00083 : map (size, grow_rate, max_size)
00084 {
00085 }
00086
00091 void Add (const T& object)
00092 {
00093 if (!Contains (object))
00094 AddNoTest (object);
00095 }
00096
00103 void AddNoTest (const T& object)
00104 {
00105 map.Put (object, true);
00106 }
00107
00111 bool Contains (const T& object) const
00112 {
00113 return map.Contains (object);
00114 }
00115
00121 bool In (const T& object) const
00122 { return Contains(object); }
00123
00127 void DeleteAll ()
00128 {
00129 map.DeleteAll ();
00130 }
00131
00133 void Empty() { DeleteAll(); }
00134
00140 bool Delete (const T& object)
00141 {
00142 return map.Delete (object, true);
00143 }
00144
00149 void Union (const csSet& otherSet)
00150 {
00151 GlobalIterator it = otherSet.GetIterator ();
00152 while (it.HasNext ())
00153 Add (it.Next ());
00154 }
00155
00160 inline friend csSet Union (const csSet& s1, const csSet& s2)
00161 {
00162 csSet un (s1);
00163 un.Union (s2);
00164 return un;
00165 }
00166
00171 bool TestIntersect (const csSet& other) const
00172 {
00173 if (GetSize () < other.GetSize ())
00174 {
00175
00176
00177 return other.TestIntersect (*this);
00178 }
00179 GlobalIterator it = other.GetIterator ();
00180 while (it.HasNext ())
00181 {
00182 if (Contains (it.Next ())) return true;
00183 }
00184 return false;
00185 }
00186
00191 inline friend csSet Intersect (const csSet& s1, const csSet& s2)
00192 {
00193 csSet intersection;
00194 GlobalIterator it = s1.GetIterator ();
00195 while (it.HasNext ())
00196 {
00197 T item = it.Next ();
00198 if (s2.Contains (item))
00199 intersection.AddNoTest (item);
00200 }
00201 return intersection;
00202 }
00203
00207 void Subtract (const csSet& otherSet)
00208 {
00209 GlobalIterator it = otherSet.GetIterator ();
00210 while (it.HasNext ())
00211 Delete (it.Next ());
00212 }
00213
00217 inline friend csSet Subtract (const csSet& s1, const csSet& s2)
00218 {
00219 csSet subtraction;
00220 GlobalIterator it = s1.GetIterator ();
00221 while (it.HasNext ())
00222 {
00223 T item = it.Next ();
00224 if (!s2.Contains (item))
00225 subtraction.AddNoTest (item);
00226 }
00227 return subtraction;
00228 }
00229
00231 size_t GetSize () const
00232 {
00233 return map.GetSize ();
00234 }
00235
00241 bool IsEmpty() const
00242 {
00243 return GetSize() == 0;
00244 }
00245
00251 GlobalIterator GetIterator () const
00252 {
00253 return GlobalIterator(this);
00254 }
00255 };
00256
00259 #endif // __CS_UTIL_SET_H__