00001 /* 00002 FALCON - The Falcon Programming Language. 00003 FILE: llist.h 00004 00005 Inlined linked list templates. 00006 ------------------------------------------------------------------- 00007 Author: Giancarlo Niccolai 00008 Begin: ven dic 3 2004 00009 00010 ------------------------------------------------------------------- 00011 (C) Copyright 2004: the FALCON developers (see list in AUTHORS file) 00012 00013 See LICENSE file for licensing details. 00014 */ 00015 00020 #ifndef FLC_LLIST_H 00021 #define FLC_LLIST_H 00022 #include <falcon/types.h> 00023 00024 namespace Falcon { 00025 00028 class LinkableElement 00029 { 00030 LinkableElement *m_next; 00031 LinkableElement *m_prev; 00032 00033 public: 00034 00035 LinkableElement( LinkableElement *prev=0, LinkableElement *next=0 ): 00036 m_next( next ), 00037 m_prev( prev ) 00038 {} 00039 00040 LinkableElement *next() const { return m_next; } 00041 void next( LinkableElement *n ) { m_next = n; } 00042 LinkableElement *prev() const { return m_prev; } 00043 void prev( LinkableElement *p ) { m_prev = p; } 00044 }; 00045 00056 template< class _T > 00057 class LinkedList 00058 { 00059 LinkableElement *m_head; 00060 LinkableElement *m_tail; 00061 uint32 m_size; 00062 00063 public: 00064 LinkedList(): 00065 m_head(0), 00066 m_tail(0), 00067 m_size(0) 00068 {} 00069 00070 void push_front( _T *e ) 00071 { 00072 LinkableElement *elem = static_cast< LinkableElement *>( e ); 00073 elem->next( m_head ); 00074 elem->prev(0); 00075 m_head = elem; 00076 if( m_tail == 0 ) 00077 m_tail = elem; 00078 m_size++; 00079 } 00080 00081 void push_back( _T *e ) 00082 { 00083 LinkableElement *elem = static_cast< LinkableElement *>( e ); 00084 elem->next( 0 ); 00085 elem->prev( m_tail ); 00086 m_tail = elem; 00087 if( m_head == 0 ) 00088 m_head = elem; 00089 m_size++; 00090 } 00091 00092 _T *front() { return static_cast<_T *>( m_head ); } 00093 _T *back() { return static_cast<_T *>( m_tail ); } 00094 00095 _T *pop_front() 00096 { 00097 _T *h = static_cast<_T *>( m_head ); 00098 if (m_head != 0 ) { 00099 m_head = m_head->next(); 00100 if ( m_head != 0 ) 00101 m_head->prev(0); 00102 else 00103 m_tail = 0; 00104 m_size--; 00105 } 00106 return h; 00107 } 00108 00109 _T *pop_back() 00110 { 00111 _T *t = static_cast<_T *>( m_tail ); 00112 if (m_tail != 0 ) { 00113 m_tail = m_tail->prev(); 00114 if ( m_tail != 0 ) 00115 m_tail->next(0); 00116 else 00117 m_head = 0; 00118 m_size--; 00119 } 00120 return t; 00121 } 00122 00123 void remove( _T * e ) { 00124 LinkableElement *elem = static_cast< LinkableElement *>( e ); 00125 if ( m_size == 0 ) return; 00126 if ( elem == m_head ) { 00127 m_head = elem->next(); 00128 } 00129 else { 00130 elem->prev()->next( elem->next() ); 00131 } 00132 00133 if ( elem == m_tail ) { 00134 m_tail = elem->prev(); 00135 } 00136 else { 00137 elem->next()->prev( elem->prev() ); 00138 } 00139 m_size--; 00140 } 00141 00142 uint32 size() const { return m_size; } 00143 bool empty() const { return m_size == 0; } 00144 }; 00145 00146 } 00147 00148 #endif 00149 00150 /* end of llist.h */
1.5.8