Go to the documentation of this file.00001
00009
00010
00011
00012
00013 #pragma once
00014
00015 #include <stdlib.h>
00016
00017 typedef unsigned int lsize ;
00018 typedef const lsize clsize ;
00019
00020
00022 template <typename T> class List
00023
00024 {
00025
00026 public :
00027 class node ;
00028 class iterator ;
00029 class const_iterator ;
00030
00031
00032
00033 public :
00035 List() : _first((node*)NULL) {}
00036
00038 List( const T &val ) : _first((node*)NULL) { insert(val) ; }
00039
00041 List( const List<T> &l ) : _first((node*)NULL)
00042 {
00043 for( const_iterator it = l.cbegin() ; it() ; ++it )
00044 insert( *it ) ;
00045 }
00046
00048 List<T> &operator = ( const List<T> &l ) { if( this != &l) { clear() ; for( const_iterator it = l.cbegin() ; it() ; ++it ) insert( *it ) ; } return *this; }
00049
00051 ~List() { clear() ; }
00052
00054 clsize size() const { lsize n = 0 ; for( const_iterator it = cbegin() ; it() ; ++it ) ++n ; return n ; }
00055
00057 bool size_greater( clsize m ) const { lsize n = 0 ; for( const_iterator it = cbegin() ; it() ; ++it ) { if(++n > m) return true ; } return false ; }
00058
00060 bool size_greater_or_equal( clsize m ) const { if( m == 0 ) return true ; lsize n = 0 ; for( const_iterator it = cbegin() ; it() ; ++it ) { if(++n >= m) return true ; } return false ; }
00061
00063 bool empty () const { return _first == (node*)NULL ; }
00064
00066 bool single() const { return !empty() && _first->next() == (node*)NULL ; }
00067
00069 bool pair () const { return !empty() && _first->next() != (node*)NULL && _first->next()->next() == (node*)NULL ; }
00070
00072 bool triple() const { return !empty() && _first->next() != (node*)NULL && _first->next()->next() != (node*)NULL ; }
00073
00074 const T first () const { return _first->val() ; }
00075 T &first () { return _first->val() ; }
00076 const T second() const { return _first->next()->val() ; }
00077 T &second() { return _first->next()->val() ; }
00078 const T third () const { return _first->next()->next()->val() ; }
00079 T &third () { return _first->next()->next()->val() ; }
00080
00082 bool firsts( T &t1, T &t2 ) const { if( !empty() ) { t1 = first() ; if( !single() ) { t2 = second() ; return true ; } } return false ; }
00084 bool firsts( T &t1, T &t2, T &t3 ) const { if( firsts( t1,t2 ) ) { if( !pair() ) t3 = third() ; return true ; } return false ; }
00085
00086 const T top () const { return _first->val() ; }
00087 T &top () { return _first->val() ; }
00088
00089
00090
00091 public :
00093 void clear()
00094 {
00095 node *p = _first ;
00096 while( p != (node*)NULL )
00097 {
00098 node *n = p->next() ;
00099 delete p ;
00100 p = n ;
00101 }
00102 _first = (node*)NULL ;
00103 }
00104
00106 inline bool empty() { return _first == (node*)NULL ; }
00107
00108
00109
00110 public :
00112 const_iterator cfind( const T &val ) const { for( const_iterator it = cbegin() ; it() ; ++it ) if( (*it) == val ) return it ; return cend() ; }
00113
00115 iterator find( const T &val ) { for( iterator it = begin() ; it() ; ++it ) if( (*it) == val ) return it ; return end() ; }
00116
00118 iterator find( const T &val, iterator &lst ) { lst = end() ; for( iterator it = begin() ; it() ; ++it ) { if( *it == val ) return it ; lst = it ; } return end() ; }
00119
00121 clsize pos( const T &val ) const { lsize i = 0 ; for( const_iterator it = cbegin() ; it() ; ++it, ++i ) if( *it == val ) return i ; return (clsize)-1 ; }
00122
00124 const_iterator min_val() const { if( empty() ) return cend() ; const_iterator it = cbegin(), m = it ; for( ++it ; it() ; ++it ) { if( *it < *m ) m = it ; } return m ; }
00125
00127 iterator min_val() { if( empty() ) return end() ; iterator it = begin(), m = it ; for( ++it ; it() ; ++it ) { if( *it < *m ) m = it ; } return m ; }
00128
00130 const_iterator max_val() const { if( empty() ) return cend() ; const_iterator it = cbegin(), m = it ; for( ++it ; it() ; ++it ) { if( *it > *m ) m = it ; } return m ; }
00131
00133 iterator max_val() { if( empty() ) return end() ; iterator it = begin(), m = it ; for( ++it ; it() ; ++it ) { if( *it > *m ) m = it ; } return m ; }
00134
00136 clsize replace( const T &old_val, const T &new_val )
00137 {
00138 lsize n = 0 ;
00139 for( iterator it = begin() ; it() ; ++it )
00140 if( *it == old_val ) { *it = new_val ; ++n ; }
00141 return n ;
00142 }
00143
00144
00145
00146 public :
00148 inline void push_front( const T &val ) { _first = new node( val, _first ) ; }
00149
00151 iterator push_after( const T &val, iterator i = begin() )
00152 {
00153 if( i == end() ) { push_front( val ) ; return begin() ; }
00154 i._node->next() = new node( val, i._node->next() ) ;
00155 return ++i ;
00156 }
00157
00159 iterator push_back( const T &val )
00160 {
00161 return push_after( val, last() ) ;
00162 }
00163
00165 inline void insert( const T &val ) { push_front( val ) ; }
00166
00168 inline void push( const T &val ) { push_front( val ) ; }
00169
00171 inline bool insert_unique( const T &val ) { if( !find(val)() ) {push_front( val ); return true;} return false; }
00172
00173
00175 void insert( const List<T> &l )
00176 { for( const_iterator lit = l.cbegin() ; lit() ; ++lit ) insert( *lit ) ; }
00177
00179 void insert_unique( const List<T> &l )
00180 { for( const_iterator lit = l.cbegin() ; lit() ; ++lit ) insert_unique( *lit ) ; }
00181
00183 void insert_ordered( const List<T> &l )
00184 {
00185 const_iterator lit = l.cbegin() ;
00186 iterator it = push_back( *lit ) ;
00187 for( ; lit() ; ++lit )
00188 it = push_after( *lit, it ) ;
00189 }
00190
00191
00193 void insert_and_clear( List<T> &l )
00194 {
00195 if( this == &l ) return ;
00196 iterator lst = last() ;
00197 if( lst() )
00198 lst._node->next() = l._first ;
00199 else
00200 _first = l._first ;
00201 l._first = NULL ;
00202 }
00203
00204
00205
00206 public :
00208 void remove_first()
00209 {
00210 node *p = _first->next() ;
00211 delete _first ;
00212 _first = p ;
00213 }
00214
00216 void pop() { remove_first() ; }
00217
00219 void remove_next( iterator &prev )
00220 {
00221 node *p ;
00222 if( prev == end() )
00223 { p = _first->next() ; delete _first ; _first = p ; }
00224 else if( prev._node )
00225 { p = prev._node->next() ; prev._node->next() = p->next() ; delete p ; }
00226 }
00227
00229 bool remove( T &val )
00230 {
00231 iterator prev = end() ;
00232 for( iterator it = begin() ; it() ; )
00233 {
00234 if( *it != val ) { prev = it ; ++it ; continue ; }
00235 val = *it ;
00236 node *p ;
00237 if( prev == end() )
00238 { p = _first->next() ; delete _first ; _first = p ; it = begin() ; }
00239 else
00240 { p = it._node ; prev._node->next() = it._node->next() ; delete p ; it = prev ; ++it ; }
00241 return true ;
00242 }
00243 return false ;
00244 }
00245
00247 clsize remove_all( const T &val )
00248 {
00249 lsize n = 0 ;
00250 iterator prev = end() ;
00251 for( iterator it = begin() ; it() ; )
00252 {
00253 if( *it != val ) { prev = it ; ++it ; continue ; }
00254 node *p ;
00255 if( prev == end() )
00256 { p = _first->next() ; delete _first ; _first = p ; it = begin() ; }
00257 else
00258 { p = it._node ; prev._node->next() = it._node->next() ; delete p ; it = prev ; ++it ; }
00259 ++n ;
00260 if( !it() ) return n ;
00261 }
00262 return n ;
00263 }
00264
00265
00266
00267
00268 public :
00270 void get_array( T *a, clsize sz )
00271 {
00272 lsize i = 0 ;
00273 for( const_iterator it = cbegin() ; it() && i < sz ; ++it, ++i )
00274 a[i] = *it ;
00275 }
00276
00278 T *get_array( clsize sz )
00279 {
00280 T *a = new T[sz] ;
00281 get_array( a,sz ) ;
00282 return a ;
00283 }
00284
00286 void set_array( clsize sz = 0, const T *a = (const T*)NULL )
00287 {
00288 clear() ;
00289 if( sz == 0 ) return ;
00290 push_front( a[0] ) ;
00291 iterator it = begin() ;
00292 for( lsize i = 1 ; i < sz ; ++i )
00293 it = push_after( a[i], it ) ;
00294 }
00295
00297 void sort( int compare(const void*,const void*) )
00298 {
00299 clsize sz = size() ;
00300 T *a = get_array( sz ) ;
00301 qsort( (void*)a, sz, sizeof(T), compare ) ;
00302 set_array( sz, a ) ;
00303 delete [] a ;
00304 }
00305
00306
00307
00308 private :
00309 node *_first;
00310
00311
00312
00313
00314
00315
00316 public :
00318 class node
00319 {
00320 public :
00321
00323 node( T val_, node *next_ = (node*)NULL ) : _val (val_) , _next (next_) {}
00324
00326 ~node() {}
00327
00329 node( const node &n ) : _val(n.val()), _next(n.next()) {}
00330
00332 node &operator = ( const node &n )
00333 { _val = n.val(); _next = n.next(); return this; }
00334
00335
00336
00337 public :
00338 inline const T &val () const { return _val ; }
00339 inline const node *next() const { return _next ; }
00340
00341 inline T &val () { return _val ; }
00342 inline node *&next() { return _next ; }
00343
00344
00345
00346 private :
00347 T _val ;
00348 node *_next;
00349 };
00350
00351
00352
00353
00354 public :
00356 class const_iterator
00357 {
00358 public :
00359
00361 const_iterator( node *n = (node*)NULL ) : _node(n) {}
00362
00364 ~const_iterator() {}
00365
00367 const_iterator( const const_iterator &i ) : _node(i._node) {}
00368
00370 const_iterator &operator = ( const const_iterator &i )
00371 { _node = i._node; return *this; }
00372
00373 friend class List<T> ;
00374
00375
00376
00377 public :
00378 inline bool operator ==( const const_iterator &i ) const { return _node == i._node ; }
00379 inline bool operator !=( const const_iterator &i ) const { return _node != i._node ; }
00380 inline bool operator ()() const { return _node != (node*)NULL ; }
00381 inline const T &operator * () const { return _node->val() ; }
00382 inline const_iterator &operator ++() { _node = _node->next() ; return *this ; }
00383
00384
00385
00386 private :
00387 node *_node;
00388 };
00389
00390
00391
00392
00393 public :
00395 class iterator
00396 {
00397 public :
00398
00400 iterator( node *n = (node*)NULL ) : _node(n) {}
00401
00403 ~iterator() {}
00404
00406 iterator( const iterator &i ) : _node(i._node) {}
00407
00409 iterator &operator = ( const iterator &i )
00410 { _node = i._node; return *this; }
00411
00412 friend class List <T> ;
00413
00414
00415
00416 public :
00417 inline bool operator ==( const iterator &i ) const { return _node == i._node ; }
00418 inline bool operator !=( const iterator &i ) const { return _node != i._node ; }
00419 inline bool operator ()() const { return _node != (node*)NULL ; }
00420 inline T &operator * () const { return _node->val() ; }
00421 inline iterator &operator ++() { _node = _node->next() ; return *this ; }
00422
00423
00424
00425 private :
00426 node *_node;
00427 };
00428
00429
00430
00431 public :
00432 inline const_iterator cbegin() const { return const_iterator( _first ) ; }
00433 inline const_iterator cend () const { return const_iterator( (node*)NULL ) ; }
00434 inline iterator begin() { return iterator( _first ) ; }
00435 inline iterator end () { return iterator( (node*)NULL ) ; }
00436
00438 iterator last () { iterator lst = end(), it = begin() ; while( it() ) { lst = it ; ++it ; } return lst ; }
00439 };
00440
00441
00442
00443
00444
00445
00447 template <typename T> class Queue : public List<T>
00448
00449 {
00450
00451
00452 public :
00454 Queue() : List<T>() { _last = this->end() ; }
00455
00457 Queue( const T &val ) : List<T>( val ) { _last = this->begin() ; }
00458
00460 Queue( const Queue<T> &q ) : List<T>()
00461 { for( typename List<T>::const_iterator it = q.cbegin() ; it() ; ++it ) Queue<T>::insert( *it ) ; }
00462
00464 Queue<T> &operator = ( const Queue<T> &q )
00465 { if( this != &q) { this->clear() ; for( typename List<T>::const_iterator it = q.cbegin() ; it() ; ++it ) insert( *it ) ; } return *this; }
00466
00468 ~Queue() { this->clear() ; }
00469
00470
00471
00472
00473 public :
00475 inline void insert( const T &val )
00476 { _last = push_after( val, _last ) ; }
00477
00479 void insert( const Queue<T> &l )
00480 { for( typename List<T>::const_iterator lit = l.cbegin() ; lit() ; ++lit ) insert( *lit ) ; }
00481
00482
00483
00484 public :
00486 inline const T front() const { return this->first() ; }
00487
00489 inline void push( const T &val ) { this->insert( val ) ; }
00490
00492 inline void pop () { this->remove_first() ; if( this->empty() ) _last = this->end() ; }
00493
00494
00495
00496
00497 private :
00498 typename List<T>::iterator _last;
00499 };
00500
00501
00502