00001 #ifndef STATIC_CONTAINER_LODGE_LIST_H
00002
00003 #define STATIC_CONTAINER_LODGE_LIST_H
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057 #include <gslib/static_container/destruct.h>
00058 #include <gslib/static_container/list_node_pool.h>
00059 #include <gslib/static_container/STATIC_CONTAINER_MEMBERTYPEDEF.h>
00060 #include <gslib/static_container/compare_methods.h>
00061 #include <algorithm>
00062 #include <functional>
00063 #include <boost/call_traits.hpp>
00064 #include <boost/assert.hpp>
00065
00066 namespace gslib {
00067 namespace static_container {
00069
00079 template < typename Value >
00080 class lodge_list : public compare_methods< lodge_list< Value > > {
00081 public:
00082 typedef list_link link;
00083 typedef list_node< Value > node;
00084 typedef abstruct_list_node_pool<
00085 Value > pool;
00086 STATIC_CONTAINER_MEMBERTYPEDEF( Value )
00087 typedef typename boost::call_traits< Value >::param_type param_type;
00088 private:
00089 static void destruct( Value& v ) {
00090 static_container::destruct< Value >( v );
00091 }
00092
00093 class iterator_base {
00094 protected:
00095 link* node_;
00096 void setNext( link* next ) {
00097 BOOST_ASSERT( 0 != node_ );
00098 node_->next = next;
00099 }
00100 void setPrev( link* prev ) {
00101 BOOST_ASSERT( 0 != node_ );
00102 node_->prev = prev;
00103 }
00104 friend class lodge_list;
00105
00106 public:
00107 link* getNode() {
00108 BOOST_ASSERT( 0 != node_ );
00109 return node_;
00110 }
00111 bool equal( iterator_base const& other ) const {
00112 return this->node_ == other.node_;
00113 }
00114 void increment() {
00115 BOOST_ASSERT( 0 != node_ );
00116 node_ = node_->next;
00117 }
00118 void decrement() {
00119 BOOST_ASSERT( 0 != node_ );
00120 node_ = node_->prev;
00121 }
00122 };
00123 public:
00124 class iterator;
00125
00127 class const_iterator :
00128 public iterator_base,
00129 public std::iterator< std::bidirectional_iterator_tag, Value const > {
00130
00131 friend class lodge_list;
00132 friend class iterator;
00133 explicit const_iterator( const link* n ) {
00134 node_ = const_cast< link* >( n );
00135 }
00136 public:
00137 const_iterator() { node_ = 0; }
00138 const_reference operator * () const {
00139 BOOST_ASSERT( 0 != node_ );
00140 return static_cast< const node* >( node_ )->value;
00141 }
00142 const_pointer operator -> () const {
00143 BOOST_ASSERT( 0 != node_ );
00144 return &static_cast< const node* >( node_ )->value;
00145 }
00146 const_iterator& operator ++ () {
00147 increment();
00148 return *this;
00149 }
00150 const_iterator& operator -- () {
00151 decrement();
00152 return *this;
00153 }
00154 const_iterator operator ++ ( int ) {
00155 const_iterator result( *this );
00156 operator ++ ();
00157 return result;
00158 }
00159 const_iterator operator -- ( int ) {
00160 const_iterator result( *this );
00161 operator -- ();
00162 return result;
00163 }
00164 bool operator == (const const_iterator& x) const {
00165 return equal( x );
00166 }
00167 bool operator != (const const_iterator& x) const {
00168 return !equal( x );
00169 }
00170 };
00171
00173 class iterator :
00174 public iterator_base,
00175 public std::iterator< std::bidirectional_iterator_tag, Value > {
00176
00177 friend class lodge_list;
00178 explicit iterator( link* n ) {
00179 node_ = n;
00180 }
00181 public:
00182 operator const_iterator () {
00183 return const_iterator( node_ );
00184 }
00185 iterator() { node_ = 0; }
00186 reference operator * () const {
00187 BOOST_ASSERT( 0 != node_ );
00188 return static_cast< node* >( node_ )->value;
00189 }
00190 Value* operator -> () {
00191 BOOST_ASSERT( 0 != node_ );
00192 return &static_cast< node* >( node_ )->value;
00193 }
00194 iterator& operator ++ () {
00195 increment();
00196 return *this;
00197 }
00198 iterator& operator -- () {
00199 decrement();
00200 return *this;
00201 }
00202 iterator operator ++ ( int ) {
00203 iterator result( *this );
00204 operator ++ ();
00205 return result;
00206 }
00207 iterator operator -- ( int ) {
00208 iterator result( *this );
00209 operator -- ();
00210 return result;
00211 }
00212 bool operator == (const iterator& x) const {
00213 return equal( x );
00214 }
00215 bool operator != (const iterator& x) const {
00216 return !equal( x );
00217 }
00218 };
00219
00220 private:
00221 link end_;
00222 pool* pool_;
00223
00224 void init() {
00225 end_.next = &end_;
00226 end_.prev = &end_;
00227 }
00228
00229 public:
00230 lodge_list( pool& ioPool ) : pool_( &ioPool ) {
00231 init();
00232 }
00233 lodge_list( const lodge_list& other ) : pool_( other.pool_ ) {
00234 init();
00235 insert( begin(), other.begin(), other.end() );
00236 }
00237 ~lodge_list() {
00238 clear();
00239 }
00240
00241 lodge_list& operator = ( const lodge_list& other ) {
00242 if ( this != &other ) {
00243 clear();
00244 pool_ = other.pool_;
00245 insert( begin(), other.begin(), other.end() );
00246 }
00247 return *this;
00248 }
00249
00250 iterator begin() {
00251 return iterator( end_.next );
00252 }
00253 iterator end() {
00254 return iterator( &end_ );
00255 }
00256 const_iterator begin() const {
00257 return const_iterator( end_.next );
00258 }
00259 const_iterator end() const {
00260 return const_iterator( &end_ );
00261 }
00262
00263 reference push_back() {
00264 node* n = pool_->allocate();
00265 BOOST_ASSERT( 0 != n );
00266 return new( &n->value ) Value();
00267 }
00268
00270
00273 Value* allocate( iterator pos = end() ) {
00274 node* n = pool_->allocate();
00275 BOOST_ASSERT( 0 != n );
00276 iterator prev = pos;
00277 --prev;
00278 prev.setNext( n );
00279 pos.setPrev( n );
00280 n->next = pos.getNode();
00281 n->prev = prev.getNode();
00282 return &n->value;
00283 }
00284
00286
00289 void insert( iterator pos, param_type v ) {
00290 Value* val = allocate( pos );
00291
00292 new( val ) Value( v );
00293 }
00294
00296
00299 template < typename It >
00300 void insert( iterator pos, It first, It last ) {
00301 for ( ; first != last; ++first ) {
00302 Value* val = allocate( pos );
00303
00304 new( val ) Value( *first );
00305 }
00306 }
00307
00309 void push_front( param_type v ) {
00310 return insert( begin(), v );
00311 }
00312
00314 void push_back( param_type v ) {
00315 insert( end(), v );
00316 }
00317
00319 void erase( iterator pos ) {
00320
00321 destruct( *pos );
00322
00323
00324 pool_->deallocate( pos.getNode() );
00325 }
00326
00328 void erase( iterator first, iterator last ) {
00329
00330 std::for_each( first, last, destruct );
00331
00332 pool_->deallocate( first.getNode(), last.getNode() );
00333 }
00334
00336 void clear() {
00337 erase( begin(), end() );
00338 }
00339
00341 void pop_front() {
00342 erase( begin() );
00343 }
00344
00346 void pop_back() {
00347 erase( --end() );
00348 }
00349
00351 void remove( const Value& value ) {
00352 remove_if( std::bind2nd( std::equal_to< value_type >(), value ) );
00353 }
00354
00356
00359 template < typename Pred >
00360 void remove_if( Pred pred ) {
00361 for ( iterator it = begin(); end() != it; ) {
00362 if ( pred( *it ) ) {
00363 erase( it++ );
00364 } else {
00365 ++it;
00366 }
00367 }
00368 }
00369
00371 size_type size() const {
00372 return static_cast< size_type >( std::distance( begin(), end() ) );
00373 }
00374
00376 bool empty() const {
00377 return end_.next == &end_;
00378 }
00379
00381 reference front() {
00382 return *begin();
00383 }
00385 param_type front() const {
00386 return *begin();
00387 }
00389 reference back() {
00390 return *( --end() );
00391 }
00393 param_type back() const {
00394 return *( --end() );
00395 }
00396 };
00397 }
00398 }
00399
00400 #endif