00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00026
00035
00036
00037 #ifndef _CTTL_XTL_CIRCULARLY_LINKED_LIST_H_INCLUDED_
00038 #define _CTTL_XTL_CIRCULARLY_LINKED_LIST_H_INCLUDED_
00039
00040 namespace cttl_impl {
00041
00052 template< typename LinkT >
00053 class xtl_circular_node
00054 {
00055 protected:
00070 mutable LinkT* m_pnext;
00071
00073 xtl_circular_node()
00074 :
00075 m_pnext( NULL )
00076 {
00077 m_pnext = static_cast< LinkT* >( this );
00078 }
00079
00084 xtl_circular_node( LinkT const& other_ )
00085 :
00086 m_pnext( NULL )
00087 {
00088 m_pnext = static_cast< LinkT* >( this );
00089 other_.list_insert( *static_cast< LinkT* >( this ) );
00090 }
00091
00093 ~xtl_circular_node()
00094 {
00095 list_remove( *static_cast< LinkT* >( this ) );
00096 assert( list_single() );
00097 }
00098
00101 LinkT const& list_insert( LinkT const& other_ ) const
00102 {
00103
00104 assert( other_.list_single() );
00105
00106
00107 assert( -1 == list_distance( other_ ) );
00108
00109 other_.m_pnext = m_pnext;
00110 m_pnext = const_cast< LinkT* >( &other_ );
00111 return other_;
00112 }
00113
00120 size_t list_size() const
00121 {
00122 int size = 1 + m_pnext->list_distance( *static_cast< LinkT* >( this ) );
00123 assert( size > 0 );
00124 return size;
00125 }
00126
00148 int list_distance( LinkT const& other_ ) const
00149 {
00150 if ( &other_ == static_cast< LinkT const* >( this ) && list_single() ) {
00151 return 0;
00152
00153 } else if ( other_.list_single() ) {
00154
00155 return -1;
00156 }
00157
00158 int hops = 1;
00159
00160 LinkT const* previous = static_cast< LinkT const* >( this );
00161 LinkT const* iter = m_pnext;
00162 while ( iter != &other_ ) {
00163 previous = iter;
00164 if ( previous == static_cast< LinkT const* >( this ) ) {
00165 return -1;
00166 }
00167 iter = iter->m_pnext;
00168 ++hops;
00169 }
00170
00171 return hops;
00172 }
00173
00175 bool list_single() const
00176 {
00177 return ( m_pnext == static_cast< LinkT const* >( this ) );
00178 }
00179
00189 bool list_remove( LinkT& other_ )
00190 {
00191 if ( &other_ == static_cast< LinkT* >( this ) ) {
00192
00193 if ( list_single() ) {
00194
00195
00196 return false;
00197 } else {
00198
00199 return m_pnext->list_remove( other_ );
00200 }
00201 }
00202
00203 if ( other_.list_single() )
00204 return false;
00205
00206 LinkT* previous = static_cast< LinkT* >( this );
00207 LinkT* iter = m_pnext;
00208 while ( iter != &other_ ) {
00209 previous = iter;
00210 if ( previous == static_cast< LinkT* >( this ) ) {
00211 assert( other_.list_single() );
00212 return false;
00213 }
00214 iter = iter->m_pnext;
00215 }
00216 previous->m_pnext = iter->m_pnext;
00217
00218
00219 other_.m_pnext = &other_;
00220
00221 return true;
00222 }
00223
00224 private:
00225
00226
00227 xtl_circular_node< LinkT >& operator=( xtl_circular_node< LinkT > const& );
00228
00229 };
00230
00231 }
00232
00233 #endif // _CTTL_XTL_CIRCULARLY_LINKED_LIST_H_INCLUDED_