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 bool empty(){
  39         return m_value == 0;
  40 }
  41 Type* insert( const Type& other ){
  42         m_value = new Type( other );
  43         return m_value;
  44 }
  45 void clear(){
  46         delete m_value;
  47         m_value = 0;
  48 }
  49 Type& get(){
  50         //ASSERT_MESSAGE(!empty(), "Single: must be initialised before being accessed");
  51         return *m_value;
  52 }
  53 const Type& get() const {
  54         //ASSERT_MESSAGE(!empty(), "Single: must be initialised before being accessed");
  55         return *m_value;
  56 }
  57 };
  58
  59
  60 /// \brief An adaptor to make std::list into a Unique Sequence - which cannot contain the same value more than once.
  61 /// \param Value Uniquely identifies itself. Must provide a copy-constructor and an equality operator.
  62 template<typename Value>
  63 class UnsortedSet
  64 {
  65 typedef typename std::list<Value> Values;
  66 Values m_values;
  67 public:
  68 typedef typename Values::iterator iterator;
  69 typedef typename Values::const_iterator const_iterator;
  70 typedef typename Values::reverse_iterator reverse_iterator;
  71 typedef typename Values::const_reverse_iterator const_reverse_iterator;
  72
  73 iterator begin(){
  74         return m_values.begin();
  75 }
  76 const_iterator begin() const {
  77         return m_values.begin();
  78 }
  79 iterator end(){
  80         return m_values.end();
  81 }
  82 const_iterator end() const {
  83         return m_values.end();
  84 }
  85 reverse_iterator rbegin(){
  86         return m_values.rbegin();
  87 }
  88 const_reverse_iterator rbegin() const {
  89         return m_values.rbegin();
  90 }
  91 reverse_iterator rend(){
  92         return m_values.rend();
  93 }
  94 const_reverse_iterator rend() const {
  95         return m_values.rend();
  96 }
  97
  98 bool empty() const {
  99         return m_values.empty();
 100 }
 101 std::size_t size() const {
 102         return m_values.size();
 103 }
 104 void clear(){
 105         m_values.clear();
 106 }
 107
 108 void swap( UnsortedSet& other ){
 109         std::swap( m_values, other.m_values );
 110 }
 111 iterator insert( const Value& value ){
 112         ASSERT_MESSAGE( find( value ) == end(), "UnsortedSet::insert: already added" );
 113         m_values.push_back( value );
 114         return --end();
 115 }
 116 void erase( const Value& value ){
 117         iterator i = find( value );
 118         ASSERT_MESSAGE( i != end(), "UnsortedSet::erase: not found" );
 119         m_values.erase( i );
 120 }
 121 iterator find( const Value& value ){
 122         return std::find( begin(), end(), value );
 123 }
 124 };
 125
 126 namespace std
 127 {
 128 /// \brief Swaps the values of \p self and \p other.
 129 /// Overloads std::swap.
 130 template<typename Value>
 131 inline void swap( UnsortedSet<Value>& self, UnsortedSet<Value>& other ){
 132         self.swap( other );
 133 }
 134 }
 135
 136 /// An adaptor to make std::list into a Unique Associative Sequence - which cannot contain the same value more than once.
 137 /// Key: Uniquely identifies a value. Must provide a copy-constructor and an equality operator.
 138 /// Value: Must provide a copy-constructor.
 139 template<typename Key, typename Value>
 140 class UnsortedMap
 141 {
 142 typedef typename std::list< std::pair<Key, Value> > Values;
 143 Values m_values;
 144 public:
 145 typedef typename Values::value_type value_type;
 146 typedef typename Values::iterator iterator;
 147 typedef typename Values::const_iterator const_iterator;
 148
 149 iterator begin(){
 150         return m_values.begin();
 151 }
 152 const_iterator begin() const {
 153         return m_values.begin();
 154 }
 155 iterator end(){
 156         return m_values.end();
 157 }
 158 const_iterator end() const {
 159         return m_values.end();
 160 }
 161
 162 bool empty() const {
 163         return m_values.empty();
 164 }
 165 std::size_t size() const {
 166         return m_values.size();
 167 }
 168 void clear(){
 169         m_values.clear();
 170 }
 171
 172 iterator insert( const value_type& value ){
 173         ASSERT_MESSAGE( find( value.first ) == end(), "UnsortedMap::insert: already added" );
 174         m_values.push_back( value );
 175         return --m_values.end();
 176 }
 177 void erase( const Key& key ){
 178         iterator i = find( key );
 179         ASSERT_MESSAGE( i != end(), "UnsortedMap::erase: not found" );
 180         erase( i );
 181 }
 182 void erase( iterator i ){
 183         m_values.erase( i );
 184 }
 185 iterator find( const Key& key ){
 186         for ( iterator i = m_values.begin(); i != m_values.end(); ++i )
 187         {
 188                 if ( ( *i ).first == key ) {
 189                         return i;
 190                 }
 191         }
 192         return m_values.end();
 193 }
 194 const_iterator find( const Key& key ) const {
 195         for ( const_iterator i = m_values.begin(); i != m_values.end(); ++i )
 196         {
 197                 if ( ( *i ).first == key ) {
 198                         return i;
 199                 }
 200         }
 201         return m_values.end();
 202 }
 203
 204 Value& operator[]( const Key& key ){
 205         iterator i = find( key );
 206         if ( i != end() ) {
 207                 return ( *i ).second;
 208         }
 209
 210         m_values.push_back( Values::value_type( key, Value() ) );
 211         return m_values.back().second;
 212 }
 213 };
 214
 215 /// An adaptor to assert when duplicate values are added, or non-existent values removed from a std::set.
 216 template<typename Value>
 217 class UniqueSet
 218 {
 219 typedef std::set<Value> Values;
 220 Values m_values;
 221 public:
 222 typedef typename Values::iterator iterator;
 223 typedef typename Values::const_iterator const_iterator;
 224 typedef typename Values::reverse_iterator reverse_iterator;
 225 typedef typename Values::const_reverse_iterator const_reverse_iterator;
 226
 227
 228 iterator begin(){
 229         return m_values.begin();
 230 }
 231 const_iterator begin() const {
 232         return m_values.begin();
 233 }
 234 iterator end(){
 235         return m_values.end();
 236 }
 237 const_iterator end() const {
 238         return m_values.end();
 239 }
 240 reverse_iterator rbegin(){
 241         return m_values.rbegin();
 242 }
 243 const_reverse_iterator rbegin() const {
 244         return m_values.rbegin();
 245 }
 246 reverse_iterator rend(){
 247         return m_values.rend();
 248 }
 249 const_reverse_iterator rend() const {
 250         return m_values.rend();
 251 }
 252
 253 bool empty() const {
 254         return m_values.empty();
 255 }
 256 std::size_t size() const {
 257         return m_values.size();
 258 }
 259 void clear(){
 260         m_values.clear();
 261 }
 262
 263 void swap( UniqueSet& other ){
 264         std::swap( m_values, other.m_values );
 265 }
 266 iterator insert( const Value& value ){
 267         std::pair<iterator, bool> result = m_values.insert( value );
 268         ASSERT_MESSAGE( result.second, "UniqueSet::insert: already added" );
 269         return result.first;
 270 }
 271 void erase( const Value& value ){
 272         iterator i = find( value );
 273         ASSERT_MESSAGE( i != end(), "UniqueSet::erase: not found" );
 274         m_values.erase( i );
 275 }
 276 iterator find( const Value& value ){
 277         return std::find( begin(), end(), value );
 278 }
 279 };
 280
 281 namespace std
 282 {
 283 /// \brief Swaps the values of \p self and \p other.
 284 /// Overloads std::swap.
 285 template<typename Value>
 286 inline void swap( UniqueSet<Value>& self, UniqueSet<Value>& other ){
 287         self.swap( other );
 288 }
 289 }
 290
 291 template<typename Type>
 292 class ReferencePair
 293 {
 294 Type* m_first;
 295 Type* m_second;
 296 public:
 297 ReferencePair() : m_first( 0 ), m_second( 0 ){
 298 }
 299 void attach( Type& t ){
 300         ASSERT_MESSAGE( m_first == 0 || m_second == 0, "ReferencePair::insert: pointer already exists" );
 301         if ( m_first == 0 ) {
 302                 m_first = &t;
 303         }
 304         else if ( m_second == 0 ) {
 305                 m_second = &t;
 306         }
 307 }
 308 void detach( Type& t ){
 309         ASSERT_MESSAGE( m_first == &t || m_second == &t, "ReferencePair::erase: pointer not found" );
 310         if ( m_first == &t ) {
 311                 m_first = 0;
 312         }
 313         else if ( m_second == &t ) {
 314                 m_second = 0;
 315         }
 316 }
 317 template<typename Functor>
 318 void forEach( const Functor& functor ){
 319         if ( m_second != 0 ) {
 320                 functor( *m_second );
 321         }
 322         if ( m_first != 0 ) {
 323                 functor( *m_first );
 324         }
 325 }
 326 };
 327
 328
 329 #endif