csutil/set.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2003 by Mat Sutcliffe <oktal@gmx.co.uk> 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Lesser General Public 00006 License as published by the Free Software Foundation; either 00007 version 2 of the License, or (at your option) any later version. 00008 00009 This library is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 Library General Public License for more details. 00013 00014 You should have received a copy of the GNU Library General Public 00015 License along with this library; if not, write to the Free 00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 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 /* Unfortunately, MSVC6 barfs if we derive this from ParentIter. */ 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 // Call TestIntersect() on the set with most elements 00176 // so that we iterate over the set with fewest elements. 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__
Generated for Crystal Space 2.0 by doxygen 1.6.1