CrystalSpace

Public API Reference

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.7.6.1