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