libs/container/container.h

   1 /*
   2 Copyright (C) 2001-2006, William Joseph.
   3 All Rights Reserved.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22 #if !defined(INCLUDED_CONTAINER_CONTAINER_H)
  23 #define INCLUDED_CONTAINER_CONTAINER_H
  24
  25 #include <list>
  26 #include <set>
  27
  28 #include "generic/static.h"
  29
  30 /// \brief A single-value container, which can either be empty or full.
  31 template<typename Type>
  32 class Single
  33 {
  34   Type* m_value;
  35 public:
  36   Single() : m_value(0)
  37   {
  38   }
  39   bool empty()
  40   {
  41     return m_value == 0;
  42   }
  43   Type* insert(const Type& other)
  44   {
  45     m_value = new Type(other);
  46     return m_value;
  47   }
  48   void clear()
  49   {
  50     delete m_value;
  51     m_value = 0;
  52   }
  53   Type& get()
  54   {
  55     //ASSERT_MESSAGE(!empty(), "Single: must be initialised before being accessed");
  56     return *m_value;
  57   }
  58   const Type& get() const
  59   {
  60     //ASSERT_MESSAGE(!empty(), "Single: must be initialised before being accessed");
  61     return *m_value;
  62   }
  63 };
  64
  65
  66 /// \brief An adaptor to make std::list into a Unique Sequence - which cannot contain the same value more than once.
  67 /// \param Value Uniquely identifies itself. Must provide a copy-constructor and an equality operator.
  68 template<typename Value>
  69 class UnsortedSet
  70 {
  71   typedef typename std::list<Value> Values;
  72   Values m_values;
  73 public:
  74   typedef typename Values::iterator iterator;
  75   typedef typename Values::const_iterator const_iterator;
  76   typedef typename Values::reverse_iterator reverse_iterator;
  77   typedef typename Values::const_reverse_iterator const_reverse_iterator;
  78
  79   iterator begin()
  80   {
  81     return m_values.begin();
  82   }
  83   const_iterator begin() const
  84   {
  85     return m_values.begin();
  86   }
  87   iterator end()
  88   {
  89     return m_values.end();
  90   }
  91   const_iterator end() const
  92   {
  93     return m_values.end();
  94   }
  95   reverse_iterator rbegin()
  96   {
  97     return m_values.rbegin();
  98   }
  99   const_reverse_iterator rbegin() const
 100   {
 101     return m_values.rbegin();
 102   }
 103   reverse_iterator rend()
 104   {
 105     return m_values.rend();
 106   }
 107   const_reverse_iterator rend() const
 108   {
 109     return m_values.rend();
 110   }
 111
 112   bool empty() const
 113   {
 114     return m_values.empty();
 115   }
 116   std::size_t size() const
 117   {
 118     return m_values.size();
 119   }
 120   void clear()
 121   {
 122     m_values.clear();
 123   }
 124
 125   void swap(UnsortedSet& other)
 126   {
 127     std::swap(m_values, other.m_values);
 128   }
 129   iterator insert(const Value& value)
 130   {
 131     ASSERT_MESSAGE(find(value) == end(), "UnsortedSet::insert: already added");
 132     m_values.push_back(value);
 133     return --end();
 134   }
 135   void erase(const Value& value)
 136   {
 137     iterator i = find(value);
 138     ASSERT_MESSAGE(i != end(), "UnsortedSet::erase: not found");
 139     m_values.erase(i);
 140   }
 141   iterator find(const Value& value)
 142   {
 143     return std::find(begin(), end(), value);
 144   }
 145 };
 146
 147 namespace std
 148 {
 149   /// \brief Swaps the values of \p self and \p other.
 150   /// Overloads std::swap.
 151   template<typename Value>
 152   inline void swap(UnsortedSet<Value>& self, UnsortedSet<Value>& other)
 153   {
 154     self.swap(other);
 155   }
 156 }
 157
 158 /// An adaptor to make std::list into a Unique Associative Sequence - which cannot contain the same value more than once.
 159 /// Key: Uniquely identifies a value. Must provide a copy-constructor and an equality operator.
 160 /// Value: Must provide a copy-constructor.
 161 template<typename Key, typename Value>
 162 class UnsortedMap
 163 {
 164   typedef typename std::list< std::pair<Key, Value> > Values;
 165   Values m_values;
 166 public:
 167   typedef typename Values::value_type value_type;
 168   typedef typename Values::iterator iterator;
 169   typedef typename Values::const_iterator const_iterator;
 170
 171   iterator begin()
 172   {
 173     return m_values.begin();
 174   }
 175   const_iterator begin() const
 176   {
 177     return m_values.begin();
 178   }
 179   iterator end()
 180   {
 181     return m_values.end();
 182   }
 183   const_iterator end() const
 184   {
 185     return m_values.end();
 186   }
 187
 188   bool empty() const
 189   {
 190     return m_values.empty();
 191   }
 192   std::size_t size() const
 193   {
 194     return m_values.size();
 195   }
 196   void clear()
 197   {
 198     m_values.clear();
 199   }
 200
 201   iterator insert(const value_type& value)
 202   {
 203     ASSERT_MESSAGE(find(value.first) == end(), "UnsortedMap::insert: already added");
 204     m_values.push_back(value);
 205     return --m_values.end();
 206   }
 207   void erase(const Key& key)
 208   {
 209     iterator i = find(key);
 210     ASSERT_MESSAGE(i != end(), "UnsortedMap::erase: not found");
 211     erase(i);
 212   }
 213   void erase(iterator i)
 214   {
 215     m_values.erase(i);
 216   }
 217   iterator find(const Key& key)
 218   {
 219     for(iterator i = m_values.begin(); i != m_values.end(); ++i)
 220     {
 221       if((*i).first == key)
 222       {
 223         return i;
 224       }
 225     }
 226     return m_values.end();
 227   }
 228   const_iterator find(const Key& key) const
 229   {
 230     for(const_iterator i = m_values.begin(); i != m_values.end(); ++i)
 231     {
 232       if((*i).first == key)
 233       {
 234         return i;
 235       }
 236     }
 237     return m_values.end();
 238   }
 239
 240   Value& operator[](const Key& key)
 241   {
 242     iterator i = find(key);
 243     if(i != end())
 244     {
 245       return (*i).second;
 246     }
 247
 248     m_values.push_back(Values::value_type(key, Value()));
 249     return m_values.back().second;
 250   }
 251 };
 252
 253 /// An adaptor to assert when duplicate values are added, or non-existent values removed from a std::set.
 254 template<typename Value>
 255 class UniqueSet
 256 {
 257   typedef std::set<Value> Values;
 258   Values m_values;
 259 public:
 260   typedef typename Values::iterator iterator;
 261   typedef typename Values::const_iterator const_iterator;
 262   typedef typename Values::reverse_iterator reverse_iterator;
 263   typedef typename Values::const_reverse_iterator const_reverse_iterator;
 264
 265
 266   iterator begin()
 267   {
 268     return m_values.begin();
 269   }
 270   const_iterator begin() const
 271   {
 272     return m_values.begin();
 273   }
 274   iterator end()
 275   {
 276     return m_values.end();
 277   }
 278   const_iterator end() const
 279   {
 280     return m_values.end();
 281   }
 282   reverse_iterator rbegin()
 283   {
 284     return m_values.rbegin();
 285   }
 286   const_reverse_iterator rbegin() const
 287   {
 288     return m_values.rbegin();
 289   }
 290   reverse_iterator rend()
 291   {
 292     return m_values.rend();
 293   }
 294   const_reverse_iterator rend() const
 295   {
 296     return m_values.rend();
 297   }
 298
 299   bool empty() const
 300   {
 301     return m_values.empty();
 302   }
 303   std::size_t size() const
 304   {
 305     return m_values.size();
 306   }
 307   void clear()
 308   {
 309     m_values.clear();
 310   }
 311
 312   void swap(UniqueSet& other)
 313   {
 314     std::swap(m_values, other.m_values);
 315   }
 316   iterator insert(const Value& value)
 317   {
 318     std::pair<iterator, bool> result = m_values.insert(value);
 319     ASSERT_MESSAGE(result.second, "UniqueSet::insert: already added");
 320     return result.first;
 321   }
 322   void erase(const Value& value)
 323   {
 324     iterator i = find(value);
 325     ASSERT_MESSAGE(i != end(), "UniqueSet::erase: not found");
 326     m_values.erase(i);
 327   }
 328   iterator find(const Value& value)
 329   {
 330     return std::find(begin(), end(), value);
 331   }
 332 };
 333
 334 namespace std
 335 {
 336   /// \brief Swaps the values of \p self and \p other.
 337   /// Overloads std::swap.
 338   template<typename Value>
 339   inline void swap(UniqueSet<Value>& self, UniqueSet<Value>& other)
 340   {
 341     self.swap(other);
 342   }
 343 }
 344
 345 template<typename Type>
 346 class ReferencePair
 347 {
 348   Type* m_first;
 349   Type* m_second;
 350 public:
 351   ReferencePair() : m_first(0), m_second(0)
 352   {
 353   }
 354   void attach(Type& t)
 355   {
 356     ASSERT_MESSAGE(m_first == 0 || m_second == 0, "ReferencePair::insert: pointer already exists");
 357     if(m_first == 0)
 358     {
 359       m_first = &t;
 360     }
 361     else if(m_second == 0)
 362     {
 363       m_second = &t;
 364     }
 365   }
 366   void detach(Type& t)
 367   {
 368     ASSERT_MESSAGE(m_first == &t || m_second == &t, "ReferencePair::erase: pointer not found");
 369     if(m_first == &t)
 370     {
 371       m_first = 0;
 372     }
 373     else if(m_second == &t)
 374     {
 375       m_second = 0;
 376     }
 377   }
 378   template<typename Functor>
 379   void forEach(const Functor& functor)
 380   {
 381     if(m_second != 0)
 382     {
 383       functor(*m_second);
 384     }
 385     if(m_first != 0)
 386     {
 387       functor(*m_first);
 388     }
 389   }
 390 };
 391
 392
 393 #endif