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