aboutsummaryrefslogtreecommitdiff
path: root/src/stable/list.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2012-11-05 22:41:51 +0000
committerMike Buland <eichlan@xagasoft.com>2012-11-05 22:41:51 +0000
commitec05778d5718a7912e506764d443a78d6a6179e3 (patch)
tree78a9a01532180030c095acefc45763f07c14edb8 /src/stable/list.h
parentb20414ac1fe80a71a90601f4cd1767fa7014a9ba (diff)
downloadlibbu++-ec05778d5718a7912e506764d443a78d6a6179e3.tar.gz
libbu++-ec05778d5718a7912e506764d443a78d6a6179e3.tar.bz2
libbu++-ec05778d5718a7912e506764d443a78d6a6179e3.tar.xz
libbu++-ec05778d5718a7912e506764d443a78d6a6179e3.zip
Converted tabs to spaces with tabconv.
Diffstat (limited to 'src/stable/list.h')
-rw-r--r--src/stable/list.h2032
1 files changed, 1016 insertions, 1016 deletions
diff --git a/src/stable/list.h b/src/stable/list.h
index 4f9d4aa..b7fb1d1 100644
--- a/src/stable/list.h
+++ b/src/stable/list.h
@@ -16,1022 +16,1022 @@
16 16
17namespace Bu 17namespace Bu
18{ 18{
19 /** @cond DEVEL */ 19 /** @cond DEVEL */
20 template<typename value> 20 template<typename value>
21 struct ListLink 21 struct ListLink
22 { 22 {
23 value *pValue; 23 value *pValue;
24 ListLink *pNext; 24 ListLink *pNext;
25 ListLink *pPrev; 25 ListLink *pPrev;
26 }; 26 };
27 27
28 template<typename value, typename valuealloc, typename linkalloc> 28 template<typename value, typename valuealloc, typename linkalloc>
29 class List; 29 class List;
30 30
31 template<typename value, typename valuealloc, typename linkalloc> 31 template<typename value, typename valuealloc, typename linkalloc>
32 struct ListCore 32 struct ListCore
33 { 33 {
34 friend class List<value, valuealloc, linkalloc>; 34 friend class List<value, valuealloc, linkalloc>;
35 friend class SharedCore< 35 friend class SharedCore<
36 List<value, valuealloc, linkalloc>, 36 List<value, valuealloc, linkalloc>,
37 ListCore<value, valuealloc, linkalloc> 37 ListCore<value, valuealloc, linkalloc>
38 >; 38 >;
39 private: 39 private:
40 typedef struct ListLink<value> Link; 40 typedef struct ListLink<value> Link;
41 ListCore() : 41 ListCore() :
42 pFirst( NULL ), 42 pFirst( NULL ),
43 pLast( NULL ), 43 pLast( NULL ),
44 nSize( 0 ) 44 nSize( 0 )
45 { } 45 { }
46 46
47 virtual ~ListCore() 47 virtual ~ListCore()
48 { 48 {
49 clear(); 49 clear();
50 } 50 }
51 51
52 Link *pFirst; 52 Link *pFirst;
53 Link *pLast; 53 Link *pLast;
54 long nSize; 54 long nSize;
55 linkalloc la; 55 linkalloc la;
56 valuealloc va; 56 valuealloc va;
57 57
58 /** 58 /**
59 * Append a value to the list. 59 * Append a value to the list.
60 *@param v (const value_type &) The value to append. 60 *@param v (const value_type &) The value to append.
61 */ 61 */
62 Link *append( const value &v ) 62 Link *append( const value &v )
63 { 63 {
64 Link *pNew = la.allocate( 1 ); 64 Link *pNew = la.allocate( 1 );
65 pNew->pValue = va.allocate( 1 ); 65 pNew->pValue = va.allocate( 1 );
66 va.construct( pNew->pValue, v ); 66 va.construct( pNew->pValue, v );
67 nSize++; 67 nSize++;
68 if( pFirst == NULL ) 68 if( pFirst == NULL )
69 { 69 {
70 // Empty list 70 // Empty list
71 pFirst = pLast = pNew; 71 pFirst = pLast = pNew;
72 pNew->pNext = pNew->pPrev = NULL; 72 pNew->pNext = pNew->pPrev = NULL;
73 } 73 }
74 else 74 else
75 { 75 {
76 pNew->pNext = NULL; 76 pNew->pNext = NULL;
77 pNew->pPrev = pLast; 77 pNew->pPrev = pLast;
78 pLast->pNext = pNew; 78 pLast->pNext = pNew;
79 pLast = pNew; 79 pLast = pNew;
80 } 80 }
81 return pNew; 81 return pNew;
82 } 82 }
83 83
84 /** 84 /**
85 * Prepend a value to the list. 85 * Prepend a value to the list.
86 *@param v (const value_type &) The value to prepend. 86 *@param v (const value_type &) The value to prepend.
87 */ 87 */
88 Link *prepend( const value &v ) 88 Link *prepend( const value &v )
89 { 89 {
90 Link *pNew = la.allocate( 1 ); 90 Link *pNew = la.allocate( 1 );
91 pNew->pValue = va.allocate( 1 ); 91 pNew->pValue = va.allocate( 1 );
92 va.construct( pNew->pValue, v ); 92 va.construct( pNew->pValue, v );
93 nSize++; 93 nSize++;
94 if( pFirst == NULL ) 94 if( pFirst == NULL )
95 { 95 {
96 // Empty list 96 // Empty list
97 pFirst = pLast = pNew; 97 pFirst = pLast = pNew;
98 pNew->pNext = pNew->pPrev = NULL; 98 pNew->pNext = pNew->pPrev = NULL;
99 } 99 }
100 else 100 else
101 { 101 {
102 pNew->pNext = pFirst; 102 pNew->pNext = pFirst;
103 pNew->pPrev = NULL; 103 pNew->pPrev = NULL;
104 pFirst->pPrev = pNew; 104 pFirst->pPrev = pNew;
105 pFirst = pNew; 105 pFirst = pNew;
106 } 106 }
107 return pNew; 107 return pNew;
108 } 108 }
109 109
110 void clear() 110 void clear()
111 { 111 {
112 Link *pCur = pFirst; 112 Link *pCur = pFirst;
113 for(;;) 113 for(;;)
114 { 114 {
115 if( pCur == NULL ) break; 115 if( pCur == NULL ) break;
116 va.destroy( pCur->pValue ); 116 va.destroy( pCur->pValue );
117 va.deallocate( pCur->pValue, 1 ); 117 va.deallocate( pCur->pValue, 1 );
118 Link *pTmp = pCur->pNext; 118 Link *pTmp = pCur->pNext;
119 la.destroy( pCur ); 119 la.destroy( pCur );
120 la.deallocate( pCur, 1 ); 120 la.deallocate( pCur, 1 );
121 pCur = pTmp; 121 pCur = pTmp;
122 } 122 }
123 pFirst = pLast = NULL; 123 pFirst = pLast = NULL;
124 nSize = 0; 124 nSize = 0;
125 } 125 }
126 126
127 Link *insert( Link *pLink, const value &v ) 127 Link *insert( Link *pLink, const value &v )
128 { 128 {
129 Link *pAfter = pLink; 129 Link *pAfter = pLink;
130 if( pAfter == NULL ) 130 if( pAfter == NULL )
131 { 131 {
132 return append( v ); 132 return append( v );
133 } 133 }
134 Link *pPrev = pAfter->pPrev; 134 Link *pPrev = pAfter->pPrev;
135 if( pPrev == NULL ) 135 if( pPrev == NULL )
136 { 136 {
137 return prepend( v ); 137 return prepend( v );
138 } 138 }
139 139
140 Link *pNew = la.allocate( 1 ); 140 Link *pNew = la.allocate( 1 );
141 pNew->pValue = va.allocate( 1 ); 141 pNew->pValue = va.allocate( 1 );
142 va.construct( pNew->pValue, v ); 142 va.construct( pNew->pValue, v );
143 nSize++; 143 nSize++;
144 144
145 pNew->pNext = pAfter; 145 pNew->pNext = pAfter;
146 pNew->pPrev = pPrev; 146 pNew->pPrev = pPrev;
147 pAfter->pPrev = pNew; 147 pAfter->pPrev = pNew;
148 pPrev->pNext = pNew; 148 pPrev->pNext = pNew;
149 149
150 return pNew; 150 return pNew;
151 } 151 }
152 152
153 /** 153 /**
154 * Erase an item from the list. 154 * Erase an item from the list.
155 *@param i (iterator) The item to erase. 155 *@param i (iterator) The item to erase.
156 */ 156 */
157 void erase( Link *pLink ) 157 void erase( Link *pLink )
158 { 158 {
159 Link *pCur = pLink; 159 Link *pCur = pLink;
160 if( pCur == NULL ) return; 160 if( pCur == NULL ) return;
161 Link *pPrev = pCur->pPrev; 161 Link *pPrev = pCur->pPrev;
162 if( pPrev == NULL ) 162 if( pPrev == NULL )
163 { 163 {
164 va.destroy( pCur->pValue ); 164 va.destroy( pCur->pValue );
165 va.deallocate( pCur->pValue, 1 ); 165 va.deallocate( pCur->pValue, 1 );
166 pFirst = pCur->pNext; 166 pFirst = pCur->pNext;
167 la.destroy( pCur ); 167 la.destroy( pCur );
168 la.deallocate( pCur, 1 ); 168 la.deallocate( pCur, 1 );
169 if( pFirst == NULL ) 169 if( pFirst == NULL )
170 pLast = NULL; 170 pLast = NULL;
171 else 171 else
172 pFirst->pPrev = NULL; 172 pFirst->pPrev = NULL;
173 nSize--; 173 nSize--;
174 } 174 }
175 else 175 else
176 { 176 {
177 va.destroy( pCur->pValue ); 177 va.destroy( pCur->pValue );
178 va.deallocate( pCur->pValue, 1 ); 178 va.deallocate( pCur->pValue, 1 );
179 Link *pTmp = pCur->pNext; 179 Link *pTmp = pCur->pNext;
180 la.destroy( pCur ); 180 la.destroy( pCur );
181 la.deallocate( pCur, 1 ); 181 la.deallocate( pCur, 1 );
182 pPrev->pNext = pTmp; 182 pPrev->pNext = pTmp;
183 if( pTmp != NULL ) 183 if( pTmp != NULL )
184 pTmp->pPrev = pPrev; 184 pTmp->pPrev = pPrev;
185 else 185 else
186 pLast = pPrev; 186 pLast = pPrev;
187 nSize--; 187 nSize--;
188 } 188 }
189 } 189 }
190 }; 190 };
191 /** @endcond */ 191 /** @endcond */
192 192
193 /** 193 /**
194 * Linked list template container. This class is similar to the stl list 194 * Linked list template container. This class is similar to the stl list
195 * class except for a few minor changes. First, when const, all 195 * class except for a few minor changes. First, when const, all
196 * members are only accessable const. Second, erasing a location does not 196 * members are only accessable const. Second, erasing a location does not
197 * invalidate the iterator used, it simply points to the next valid 197 * invalidate the iterator used, it simply points to the next valid
198 * location, or end() if there are no more. Other iterators pointing to 198 * location, or end() if there are no more. Other iterators pointing to
199 * the deleted record will, of course, no longer be valid. 199 * the deleted record will, of course, no longer be valid.
200 * 200 *
201 *@param value (typename) The type of data to store in your list 201 *@param value (typename) The type of data to store in your list
202 *@param valuealloc (typename) Memory Allocator for your value type 202 *@param valuealloc (typename) Memory Allocator for your value type
203 *@param linkalloc (typename) Memory Allocator for the list links. 203 *@param linkalloc (typename) Memory Allocator for the list links.
204 *@extends SharedCore 204 *@extends SharedCore
205 *@ingroup Containers 205 *@ingroup Containers
206 */ 206 */
207 template<typename value, typename valuealloc=std::allocator<value>, 207 template<typename value, typename valuealloc=std::allocator<value>,
208 typename linkalloc=std::allocator<struct ListLink<value> > > 208 typename linkalloc=std::allocator<struct ListLink<value> > >
209 class List /** @cond */ : public SharedCore< 209 class List /** @cond */ : public SharedCore<
210 List<value, valuealloc, linkalloc>, 210 List<value, valuealloc, linkalloc>,
211 ListCore<value, valuealloc, linkalloc> 211 ListCore<value, valuealloc, linkalloc>
212 > /** @endcond */ 212 > /** @endcond */
213 { 213 {
214 private: 214 private:
215 typedef struct ListLink<value> Link; 215 typedef struct ListLink<value> Link;
216 typedef class List<value, valuealloc, linkalloc> MyType; 216 typedef class List<value, valuealloc, linkalloc> MyType;
217 typedef struct ListCore<value, valuealloc, linkalloc> Core; 217 typedef struct ListCore<value, valuealloc, linkalloc> Core;
218 218
219 protected: 219 protected:
220 using SharedCore<MyType, Core>::core; 220 using SharedCore<MyType, Core>::core;
221 using SharedCore<MyType, Core>::_hardCopy; 221 using SharedCore<MyType, Core>::_hardCopy;
222 using SharedCore<MyType, Core>::_allocateCore; 222 using SharedCore<MyType, Core>::_allocateCore;
223 223
224 public: 224 public:
225 struct const_iterator; 225 struct const_iterator;
226 struct iterator; 226 struct iterator;
227 227
228 List() 228 List()
229 { 229 {
230 } 230 }
231 231
232 List( const MyType &src ) : 232 List( const MyType &src ) :
233 SharedCore<MyType, Core >( src ) 233 SharedCore<MyType, Core >( src )
234 { 234 {
235 } 235 }
236 236
237 List( const value &v ) 237 List( const value &v )
238 { 238 {
239 append( v ); 239 append( v );
240 } 240 }
241 241
242 ~List() 242 ~List()
243 { 243 {
244 } 244 }
245 245
246 MyType &operator+=( const value &v ) 246 MyType &operator+=( const value &v )
247 { 247 {
248 _hardCopy(); 248 _hardCopy();
249 append( v ); 249 append( v );
250 return *this; 250 return *this;
251 } 251 }
252 252
253 MyType &operator+=( const MyType &src ) 253 MyType &operator+=( const MyType &src )
254 { 254 {
255 _hardCopy(); 255 _hardCopy();
256 append( src ); 256 append( src );
257 return *this; 257 return *this;
258 } 258 }
259 259
260 MyType operator+( const MyType &src ) 260 MyType operator+( const MyType &src )
261 { 261 {
262 MyType lNew( *this ); 262 MyType lNew( *this );
263 lNew += src; 263 lNew += src;
264 return lNew; 264 return lNew;
265 } 265 }
266 266
267 bool operator==( const MyType &rhs ) const 267 bool operator==( const MyType &rhs ) const
268 { 268 {
269 if( getSize() != rhs.getSize() ) 269 if( getSize() != rhs.getSize() )
270 return false; 270 return false;
271 271
272 for( typename MyType::const_iterator a = begin(), b = rhs.begin(); 272 for( typename MyType::const_iterator a = begin(), b = rhs.begin();
273 a; a++, b++ ) 273 a; a++, b++ )
274 { 274 {
275 if( *a != *b ) 275 if( *a != *b )
276 return false; 276 return false;
277 } 277 }
278 278
279 return true; 279 return true;
280 } 280 }
281 281
282 bool operator!=( const MyType &rhs ) const 282 bool operator!=( const MyType &rhs ) const
283 { 283 {
284 return !(*this == rhs); 284 return !(*this == rhs);
285 } 285 }
286 286
287 /** 287 /**
288 * Clear the data from the list. 288 * Clear the data from the list.
289 */ 289 */
290 void clear() 290 void clear()
291 { 291 {
292 _hardCopy(); 292 _hardCopy();
293 core->clear(); 293 core->clear();
294 } 294 }
295 295
296 MyType &enqueue( const value &v ) 296 MyType &enqueue( const value &v )
297 { 297 {
298 _hardCopy(); 298 _hardCopy();
299 append( v ); 299 append( v );
300 300
301 return *this; 301 return *this;
302 } 302 }
303 303
304 value dequeue() 304 value dequeue()
305 { 305 {
306 // _hardCopy(); erase will call this for me 306 // _hardCopy(); erase will call this for me
307 value v = *core->pFirst->pValue; 307 value v = *core->pFirst->pValue;
308 308
309 erase( begin() ); 309 erase( begin() );
310 310
311 return v; 311 return v;
312 } 312 }
313 313
314 MyType &push( const value &v ) 314 MyType &push( const value &v )
315 { 315 {
316 _hardCopy(); 316 _hardCopy();
317 prepend( v ); 317 prepend( v );
318 318
319 return *this; 319 return *this;
320 } 320 }
321 321
322 MyType &pop() 322 MyType &pop()
323 { 323 {
324 _hardCopy(); 324 _hardCopy();
325 erase( begin() ); 325 erase( begin() );
326 326
327 return *this; 327 return *this;
328 } 328 }
329 329
330 value peekPop() 330 value peekPop()
331 { 331 {
332 value v = first(); 332 value v = first();
333 pop(); 333 pop();
334 return v; 334 return v;
335 } 335 }
336 336
337 value &peek() 337 value &peek()
338 { 338 {
339 return first(); 339 return first();
340 } 340 }
341 341
342 /** 342 /**
343 * Append a value to the list. 343 * Append a value to the list.
344 *@param v (const value_type &) The value to append. 344 *@param v (const value_type &) The value to append.
345 */ 345 */
346 MyType &append( const value &v ) 346 MyType &append( const value &v )
347 { 347 {
348 _hardCopy(); 348 _hardCopy();
349 core->append( v ); 349 core->append( v );
350 350
351 return *this; 351 return *this;
352 } 352 }
353 353
354 MyType &append( const MyType &rSrc ) 354 MyType &append( const MyType &rSrc )
355 { 355 {
356 _hardCopy(); 356 _hardCopy();
357 for( typename MyType::const_iterator i = rSrc.begin(); 357 for( typename MyType::const_iterator i = rSrc.begin();
358 i != rSrc.end(); i++ ) 358 i != rSrc.end(); i++ )
359 { 359 {
360 core->append( *i ); 360 core->append( *i );
361 } 361 }
362 362
363 return *this; 363 return *this;
364 } 364 }
365 365
366 /** 366 /**
367 * Prepend a value to the list. 367 * Prepend a value to the list.
368 *@param v (const value_type &) The value to prepend. 368 *@param v (const value_type &) The value to prepend.
369 */ 369 */
370 MyType &prepend( const value &v ) 370 MyType &prepend( const value &v )
371 { 371 {
372 _hardCopy(); 372 _hardCopy();
373 core->prepend( v ); 373 core->prepend( v );
374 374
375 return *this; 375 return *this;
376 } 376 }
377 377
378 /** 378 /**
379 * Prepend another list to the front of this one. This will prepend 379 * Prepend another list to the front of this one. This will prepend
380 * the rSrc list in reverse order...I may fix that later. 380 * the rSrc list in reverse order...I may fix that later.
381 */ 381 */
382 MyType &prepend( const MyType &rSrc ) 382 MyType &prepend( const MyType &rSrc )
383 { 383 {
384 _hardCopy(); 384 _hardCopy();
385 for( typename MyType::const_iterator i = rSrc.begin(); 385 for( typename MyType::const_iterator i = rSrc.begin();
386 i != rSrc.end(); i++ ) 386 i != rSrc.end(); i++ )
387 { 387 {
388 core->prepend( *i ); 388 core->prepend( *i );
389 } 389 }
390 390
391 return *this; 391 return *this;
392 } 392 }
393 393
394 MyType &insert( MyType::iterator &i, const value &v ) 394 MyType &insert( MyType::iterator &i, const value &v )
395 { 395 {
396 _hardCopy(); 396 _hardCopy();
397 397
398 core->insert( i.pLink, v ); 398 core->insert( i.pLink, v );
399 399
400 return *this; 400 return *this;
401 } 401 }
402 402
403 template<typename cmptype> 403 template<typename cmptype>
404 void sort( cmptype cmp ) 404 void sort( cmptype cmp )
405 { 405 {
406 Heap<value, cmptype, valuealloc> hSort( cmp, getSize() ); 406 Heap<value, cmptype, valuealloc> hSort( cmp, getSize() );
407 for( typename MyType::iterator i = begin(); i; i++ ) 407 for( typename MyType::iterator i = begin(); i; i++ )
408 { 408 {
409 hSort.enqueue( *i ); 409 hSort.enqueue( *i );
410 } 410 }
411 clear(); 411 clear();
412 while( !hSort.isEmpty() ) 412 while( !hSort.isEmpty() )
413 { 413 {
414 append( hSort.dequeue() ); 414 append( hSort.dequeue() );
415 } 415 }
416 } 416 }
417 417
418 void sort() 418 void sort()
419 { 419 {
420 sort<__basicLTCmp<value> >(); 420 sort<__basicLTCmp<value> >();
421 } 421 }
422 422
423 template<typename cmptype> 423 template<typename cmptype>
424 void sort() 424 void sort()
425 { 425 {
426 Heap<value, cmptype, valuealloc> hSort( getSize() ); 426 Heap<value, cmptype, valuealloc> hSort( getSize() );
427 for( typename MyType::iterator i = begin(); i; i++ ) 427 for( typename MyType::iterator i = begin(); i; i++ )
428 { 428 {
429 hSort.enqueue( *i ); 429 hSort.enqueue( *i );
430 } 430 }
431 clear(); 431 clear();
432 while( !hSort.isEmpty() ) 432 while( !hSort.isEmpty() )
433 { 433 {
434 append( hSort.dequeue() ); 434 append( hSort.dequeue() );
435 } 435 }
436 } 436 }
437 437
438 /** 438 /**
439 * Insert a new item in sort order by searching for the first item that 439 * Insert a new item in sort order by searching for the first item that
440 * is larger and inserting this before it, or at the end if none are 440 * is larger and inserting this before it, or at the end if none are
441 * larger. If this is the only function used to insert data in the 441 * larger. If this is the only function used to insert data in the
442 * List all items will be sorted. To use this, the value type must 442 * List all items will be sorted. To use this, the value type must
443 * support the > operator. 443 * support the > operator.
444 */ 444 */
445 template<typename cmptype> 445 template<typename cmptype>
446 iterator insertSorted( cmptype cmp, const value &v ) 446 iterator insertSorted( cmptype cmp, const value &v )
447 { 447 {
448 _hardCopy(); 448 _hardCopy();
449 if( core->pFirst == NULL ) 449 if( core->pFirst == NULL )
450 { 450 {
451 // Empty list 451 // Empty list
452 return iterator( core->append( v ) ); 452 return iterator( core->append( v ) );
453 } 453 }
454 else 454 else
455 { 455 {
456 Link *pCur = core->pFirst; 456 Link *pCur = core->pFirst;
457 for(;;) 457 for(;;)
458 { 458 {
459 if( cmp( v, *(pCur->pValue)) ) 459 if( cmp( v, *(pCur->pValue)) )
460 { 460 {
461 return iterator( core->insert( pCur, v ) ); 461 return iterator( core->insert( pCur, v ) );
462 } 462 }
463 pCur = pCur->pNext; 463 pCur = pCur->pNext;
464 if( pCur == NULL ) 464 if( pCur == NULL )
465 { 465 {
466 return iterator( core->append( v ) ); 466 return iterator( core->append( v ) );
467 } 467 }
468 } 468 }
469 } 469 }
470 } 470 }
471 471
472 iterator insertSorted( const value &v ) 472 iterator insertSorted( const value &v )
473 { 473 {
474 return insertSorted<__basicLTCmp<value> >( v ); 474 return insertSorted<__basicLTCmp<value> >( v );
475 } 475 }
476 476
477 template<typename cmptype> 477 template<typename cmptype>
478 iterator insertSorted( const value &v ) 478 iterator insertSorted( const value &v )
479 { 479 {
480 cmptype cmp; 480 cmptype cmp;
481 return insertSorted( cmp, v ); 481 return insertSorted( cmp, v );
482 } 482 }
483 483
484 /** 484 /**
485 * An iterator to iterate through your list. 485 * An iterator to iterate through your list.
486 */ 486 */
487 typedef struct iterator 487 typedef struct iterator
488 { 488 {
489 friend struct const_iterator; 489 friend struct const_iterator;
490 friend class List<value, valuealloc, linkalloc>; 490 friend class List<value, valuealloc, linkalloc>;
491 private: 491 private:
492 Link *pLink; 492 Link *pLink;
493 493
494 iterator( Link *pLink ) : 494 iterator( Link *pLink ) :
495 pLink( pLink ) 495 pLink( pLink )
496 { 496 {
497 } 497 }
498 498
499 public: 499 public:
500 iterator() : 500 iterator() :
501 pLink( NULL ) 501 pLink( NULL )
502 { 502 {
503 } 503 }
504 504
505 iterator( const iterator &i ) : 505 iterator( const iterator &i ) :
506 pLink( i.pLink ) 506 pLink( i.pLink )
507 { 507 {
508 } 508 }
509 509
510 /** 510 /**
511 * Equals comparison operator. 511 * Equals comparison operator.
512 *@param oth (const iterator &) The iterator to compare to. 512 *@param oth (const iterator &) The iterator to compare to.
513 *@returns (bool) Are they equal? 513 *@returns (bool) Are they equal?
514 */ 514 */
515 bool operator==( const iterator &oth ) const 515 bool operator==( const iterator &oth ) const
516 { 516 {
517 return ( pLink == oth.pLink ); 517 return ( pLink == oth.pLink );
518 } 518 }
519 519
520 /** 520 /**
521 * Equals comparison operator. 521 * Equals comparison operator.
522 *@param pOth (const Link *) The link to compare to. 522 *@param pOth (const Link *) The link to compare to.
523 *@returns (bool) Are they equal? 523 *@returns (bool) Are they equal?
524 */ 524 */
525 bool operator==( const Link *pOth ) const 525 bool operator==( const Link *pOth ) const
526 { 526 {
527 return ( pLink == pOth ); 527 return ( pLink == pOth );
528 } 528 }
529 529
530 /** 530 /**
531 * Not equals comparison operator. 531 * Not equals comparison operator.
532 *@param oth (const iterator &) The iterator to compare to. 532 *@param oth (const iterator &) The iterator to compare to.
533 *@returns (bool) Are they not equal? 533 *@returns (bool) Are they not equal?
534 */ 534 */
535 bool operator!=( const iterator &oth ) const 535 bool operator!=( const iterator &oth ) const
536 { 536 {
537 return ( pLink != oth.pLink ); 537 return ( pLink != oth.pLink );
538 } 538 }
539 539
540 /** 540 /**
541 * Not equals comparison operator. 541 * Not equals comparison operator.
542 *@param pOth (const Link *) The link to compare to. 542 *@param pOth (const Link *) The link to compare to.
543 *@returns (bool) Are they not equal? 543 *@returns (bool) Are they not equal?
544 */ 544 */
545 bool operator!=( const Link *pOth ) const 545 bool operator!=( const Link *pOth ) const
546 { 546 {
547 return ( pLink != pOth ); 547 return ( pLink != pOth );
548 } 548 }
549 549
550 /** 550 /**
551 * Dereference operator. 551 * Dereference operator.
552 *@returns (value_type &) The value. 552 *@returns (value_type &) The value.
553 */ 553 */
554 value &operator*() 554 value &operator*()
555 { 555 {
556 return *(pLink->pValue); 556 return *(pLink->pValue);
557 } 557 }
558 558
559 /** 559 /**
560 * Pointer access operator. 560 * Pointer access operator.
561 *@returns (value_type *) A pointer to the value. 561 *@returns (value_type *) A pointer to the value.
562 */ 562 */
563 value *operator->() 563 value *operator->()
564 { 564 {
565 return pLink->pValue; 565 return pLink->pValue;
566 } 566 }
567 567
568 iterator &operator++() 568 iterator &operator++()
569 { 569 {
570 if( pLink == NULL ) 570 if( pLink == NULL )
571 throw Bu::ExceptionBase( 571 throw Bu::ExceptionBase(
572 "Attempt to iterate past end of list."); 572 "Attempt to iterate past end of list.");
573 pLink = pLink->pNext; 573 pLink = pLink->pNext;
574 return *this; 574 return *this;
575 } 575 }
576 576
577 iterator &operator--() 577 iterator &operator--()
578 { 578 {
579 if( pLink == NULL ) 579 if( pLink == NULL )
580 throw Bu::ExceptionBase( 580 throw Bu::ExceptionBase(
581 "Attempt to iterate past begining of list."); 581 "Attempt to iterate past begining of list.");
582 pLink = pLink->pPrev; 582 pLink = pLink->pPrev;
583 return *this; 583 return *this;
584 } 584 }
585 585
586 iterator &operator++( int ) 586 iterator &operator++( int )
587 { 587 {
588 if( pLink == NULL ) 588 if( pLink == NULL )
589 throw Bu::ExceptionBase( 589 throw Bu::ExceptionBase(
590 "Attempt to iterate past end of list."); 590 "Attempt to iterate past end of list.");
591 pLink = pLink->pNext; 591 pLink = pLink->pNext;
592 return *this; 592 return *this;
593 } 593 }
594 594
595 iterator &operator--( int ) 595 iterator &operator--( int )
596 { 596 {
597 if( pLink == NULL ) 597 if( pLink == NULL )
598 throw Bu::ExceptionBase( 598 throw Bu::ExceptionBase(
599 "Attempt to iterate past begining of list."); 599 "Attempt to iterate past begining of list.");
600 pLink = pLink->pPrev; 600 pLink = pLink->pPrev;
601 return *this; 601 return *this;
602 } 602 }
603 603
604 iterator operator+( int iDelta ) 604 iterator operator+( int iDelta )
605 { 605 {
606 iterator ret( *this ); 606 iterator ret( *this );
607 for( int j = 0; j < iDelta; j++ ) 607 for( int j = 0; j < iDelta; j++ )
608 { 608 {
609 if( ret.pLink == NULL ) 609 if( ret.pLink == NULL )
610 throw Bu::ExceptionBase( 610 throw Bu::ExceptionBase(
611 "Attempt to iterate past begining of list."); 611 "Attempt to iterate past begining of list.");
612 ret.pLink = ret.pLink->pNext; 612 ret.pLink = ret.pLink->pNext;
613 } 613 }
614 return ret; 614 return ret;
615 } 615 }
616 616
617 iterator operator-( int iDelta ) 617 iterator operator-( int iDelta )
618 { 618 {
619 iterator ret( *this ); 619 iterator ret( *this );
620 for( int j = 0; j < iDelta; j++ ) 620 for( int j = 0; j < iDelta; j++ )
621 { 621 {
622 if( ret.pLink == NULL ) 622 if( ret.pLink == NULL )
623 throw Bu::ExceptionBase( 623 throw Bu::ExceptionBase(
624 "Attempt to iterate past begining of list."); 624 "Attempt to iterate past begining of list.");
625 ret.pLink = ret.pLink->pPrev; 625 ret.pLink = ret.pLink->pPrev;
626 } 626 }
627 return ret; 627 return ret;
628 } 628 }
629 629
630 operator bool() 630 operator bool()
631 { 631 {
632 return pLink != NULL; 632 return pLink != NULL;
633 } 633 }
634 634
635 bool isValid() 635 bool isValid()
636 { 636 {
637 return pLink != NULL; 637 return pLink != NULL;
638 } 638 }
639 639
640 /** 640 /**
641 * Assignment operator. 641 * Assignment operator.
642 *@param oth (const iterator &) The other iterator to set this 642 *@param oth (const iterator &) The other iterator to set this
643 * one to. 643 * one to.
644 */ 644 */
645 iterator &operator=( const iterator &oth ) 645 iterator &operator=( const iterator &oth )
646 { 646 {
647 pLink = oth.pLink; 647 pLink = oth.pLink;
648 return *this; 648 return *this;
649 } 649 }
650 } iterator; 650 } iterator;
651 651
652 /** 652 /**
653 *@see iterator 653 *@see iterator
654 */ 654 */
655 typedef struct const_iterator 655 typedef struct const_iterator
656 { 656 {
657 friend class List<value, valuealloc, linkalloc>; 657 friend class List<value, valuealloc, linkalloc>;
658 private: 658 private:
659 Link *pLink; 659 Link *pLink;
660 660
661 const_iterator( Link *pLink ) : 661 const_iterator( Link *pLink ) :
662 pLink( pLink ) 662 pLink( pLink )
663 { 663 {
664 } 664 }
665 665
666 public: 666 public:
667 const_iterator() : 667 const_iterator() :
668 pLink( NULL ) 668 pLink( NULL )
669 { 669 {
670 } 670 }
671 671
672 const_iterator( const iterator &i ) : 672 const_iterator( const iterator &i ) :
673 pLink( i.pLink ) 673 pLink( i.pLink )
674 { 674 {
675 } 675 }
676 676
677 bool operator==( const const_iterator &oth ) const 677 bool operator==( const const_iterator &oth ) const
678 { 678 {
679 return ( pLink == oth.pLink ); 679 return ( pLink == oth.pLink );
680 } 680 }
681 681
682 bool operator==( const Link *pOth ) const 682 bool operator==( const Link *pOth ) const
683 { 683 {
684 return ( pLink == pOth ); 684 return ( pLink == pOth );
685 } 685 }
686 686
687 bool operator!=( const const_iterator &oth ) const 687 bool operator!=( const const_iterator &oth ) const
688 { 688 {
689 return ( pLink != oth.pLink ); 689 return ( pLink != oth.pLink );
690 } 690 }
691 691
692 bool operator!=( const Link *pOth ) const 692 bool operator!=( const Link *pOth ) const
693 { 693 {
694 return ( pLink != pOth ); 694 return ( pLink != pOth );
695 } 695 }
696 696
697 const value &operator*() 697 const value &operator*()
698 { 698 {
699 return *(pLink->pValue); 699 return *(pLink->pValue);
700 } 700 }
701 701
702 const value *operator->() 702 const value *operator->()
703 { 703 {
704 return pLink->pValue; 704 return pLink->pValue;
705 } 705 }
706 706
707 const_iterator &operator++() 707 const_iterator &operator++()
708 { 708 {
709 if( pLink == NULL ) 709 if( pLink == NULL )
710 throw Bu::ExceptionBase( 710 throw Bu::ExceptionBase(
711 "Attempt to iterate past end of list."); 711 "Attempt to iterate past end of list.");
712 pLink = pLink->pNext; 712 pLink = pLink->pNext;
713 return *this; 713 return *this;
714 } 714 }
715 715
716 const_iterator &operator--() 716 const_iterator &operator--()
717 { 717 {
718 if( pLink == NULL ) 718 if( pLink == NULL )
719 throw Bu::ExceptionBase( 719 throw Bu::ExceptionBase(
720 "Attempt to iterate past begining of list."); 720 "Attempt to iterate past begining of list.");
721 pLink = pLink->pPrev; 721 pLink = pLink->pPrev;
722 return *this; 722 return *this;
723 } 723 }
724 724
725 const_iterator &operator++( int ) 725 const_iterator &operator++( int )
726 { 726 {
727 if( pLink == NULL ) 727 if( pLink == NULL )
728 throw Bu::ExceptionBase( 728 throw Bu::ExceptionBase(
729 "Attempt to iterate past end of list."); 729 "Attempt to iterate past end of list.");
730 pLink = pLink->pNext; 730 pLink = pLink->pNext;
731 return *this; 731 return *this;
732 } 732 }
733 733
734 const_iterator &operator--( int ) 734 const_iterator &operator--( int )
735 { 735 {
736 if( pLink == NULL ) 736 if( pLink == NULL )
737 throw Bu::ExceptionBase( 737 throw Bu::ExceptionBase(
738 "Attempt to iterate past begining of list."); 738 "Attempt to iterate past begining of list.");
739 pLink = pLink->pPrev; 739 pLink = pLink->pPrev;
740 return *this; 740 return *this;
741 } 741 }
742 742
743 const_iterator operator+( int iDelta ) 743 const_iterator operator+( int iDelta )
744 { 744 {
745 const_iterator ret( *this ); 745 const_iterator ret( *this );
746 for( int j = 0; j < iDelta; j++ ) 746 for( int j = 0; j < iDelta; j++ )
747 { 747 {
748 if( ret.pLink == NULL ) 748 if( ret.pLink == NULL )
749 throw Bu::ExceptionBase( 749 throw Bu::ExceptionBase(
750 "Attempt to iterate past begining of list."); 750 "Attempt to iterate past begining of list.");
751 ret.pLink = ret.pLink->pNext; 751 ret.pLink = ret.pLink->pNext;
752 } 752 }
753 return ret; 753 return ret;
754 } 754 }
755 755
756 const_iterator operator-( int iDelta ) 756 const_iterator operator-( int iDelta )
757 { 757 {
758 const_iterator ret( *this ); 758 const_iterator ret( *this );
759 for( int j = 0; j < iDelta; j++ ) 759 for( int j = 0; j < iDelta; j++ )
760 { 760 {
761 if( ret.pLink == NULL ) 761 if( ret.pLink == NULL )
762 throw Bu::ExceptionBase( 762 throw Bu::ExceptionBase(
763 "Attempt to iterate past begining of list."); 763 "Attempt to iterate past begining of list.");
764 ret.pLink = ret.pLink->pPrev; 764 ret.pLink = ret.pLink->pPrev;
765 } 765 }
766 return ret; 766 return ret;
767 } 767 }
768 768
769 const_iterator &operator=( const iterator &oth ) 769 const_iterator &operator=( const iterator &oth )
770 { 770 {
771 pLink = oth.pLink; 771 pLink = oth.pLink;
772 return *this; 772 return *this;
773 } 773 }
774 774
775 const_iterator &operator=( const const_iterator &oth ) 775 const_iterator &operator=( const const_iterator &oth )
776 { 776 {
777 pLink = oth.pLink; 777 pLink = oth.pLink;
778 return *this; 778 return *this;
779 } 779 }
780 780
781 operator bool() 781 operator bool()
782 { 782 {
783 return pLink != NULL; 783 return pLink != NULL;
784 } 784 }
785 785
786 bool isValid() 786 bool isValid()
787 { 787 {
788 return pLink != NULL; 788 return pLink != NULL;
789 } 789 }
790 } const_iterator; 790 } const_iterator;
791 791
792 /** 792 /**
793 * Get an iterator pointing to the first item in the list. 793 * Get an iterator pointing to the first item in the list.
794 *@returns (iterator) 794 *@returns (iterator)
795 */ 795 */
796 iterator begin() 796 iterator begin()
797 { 797 {
798 _hardCopy(); 798 _hardCopy();
799 return iterator( core->pFirst ); 799 return iterator( core->pFirst );
800 } 800 }
801 801
802 /** 802 /**
803 * Get a const iterator pointing to the first item in the list. 803 * Get a const iterator pointing to the first item in the list.
804 *@returns (const const_iterator) 804 *@returns (const const_iterator)
805 */ 805 */
806 const_iterator begin() const 806 const_iterator begin() const
807 { 807 {
808 return const_iterator( core->pFirst ); 808 return const_iterator( core->pFirst );
809 } 809 }
810 810
811 /** 811 /**
812 * Get an iterator pointing to a place just past the last item in 812 * Get an iterator pointing to a place just past the last item in
813 * the list. 813 * the list.
814 *@returns (const Link *) 814 *@returns (const Link *)
815 */ 815 */
816 const iterator end() 816 const iterator end()
817 { 817 {
818 return iterator( NULL ); 818 return iterator( NULL );
819 } 819 }
820 820
821 /** 821 /**
822 * Get an iterator pointing to a place just past the last item in 822 * Get an iterator pointing to a place just past the last item in
823 * the list. 823 * the list.
824 *@returns (const Link *) 824 *@returns (const Link *)
825 */ 825 */
826 const const_iterator end() const 826 const const_iterator end() const
827 { 827 {
828 return const_iterator( NULL ); 828 return const_iterator( NULL );
829 } 829 }
830 830
831 /** 831 /**
832 * Erase an item from the list. 832 * Erase an item from the list.
833 *@param i (iterator) The item to erase. 833 *@param i (iterator) The item to erase.
834 */ 834 */
835 MyType &erase( iterator i ) 835 MyType &erase( iterator i )
836 { 836 {
837 _hardCopy(); 837 _hardCopy();
838 core->erase( i.pLink ); 838 core->erase( i.pLink );
839 839
840 return *this; 840 return *this;
841 } 841 }
842 842
843 /** 843 /**
844 * Erase an item from the list. 844 * Erase an item from the list.
845 *@param i (iterator) The item to erase. 845 *@param i (iterator) The item to erase.
846 */ 846 */
847 MyType &erase( const_iterator i ) 847 MyType &erase( const_iterator i )
848 { 848 {
849 _hardCopy(); 849 _hardCopy();
850 core->erase( i.pLink ); 850 core->erase( i.pLink );
851 851
852 return *this; 852 return *this;
853 } 853 }
854 854
855 /** 855 /**
856 * Erase an item from the list if you already know the item. 856 * Erase an item from the list if you already know the item.
857 *@param v The item to find and erase. 857 *@param v The item to find and erase.
858 */ 858 */
859 MyType &erase( const value &v ) 859 MyType &erase( const value &v )
860 { 860 {
861 for( const_iterator i = begin(); i != end(); i++ ) 861 for( const_iterator i = begin(); i != end(); i++ )
862 { 862 {
863 if( (*i) == v ) 863 if( (*i) == v )
864 { 864 {
865 erase( i ); 865 erase( i );
866 return *this; 866 return *this;
867 } 867 }
868 } 868 }
869 869
870 return *this; 870 return *this;
871 } 871 }
872 872
873 /** 873 /**
874 * Erases the first item in the list, identical to pop, but better for 874 * Erases the first item in the list, identical to pop, but better for
875 * lists that aren't built as stacks, since you know where it will be 875 * lists that aren't built as stacks, since you know where it will be
876 * erasing from. 876 * erasing from.
877 */ 877 */
878 MyType &eraseFirst() 878 MyType &eraseFirst()
879 { 879 {
880 _hardCopy(); 880 _hardCopy();
881 erase( begin() ); 881 erase( begin() );
882 882
883 return *this; 883 return *this;
884 } 884 }
885 885
886 /** 886 /**
887 * Erases the last item in the list. 887 * Erases the last item in the list.
888 */ 888 */
889 MyType &eraseLast() 889 MyType &eraseLast()
890 { 890 {
891 _hardCopy(); 891 _hardCopy();
892 core->erase( core->pLast ); 892 core->erase( core->pLast );
893 893
894 return *this; 894 return *this;
895 } 895 }
896 896
897 iterator find( const value &v ) 897 iterator find( const value &v )
898 { 898 {
899 for( iterator i = begin(); i; i++ ) 899 for( iterator i = begin(); i; i++ )
900 { 900 {
901 if( (*i) == v ) 901 if( (*i) == v )
902 return i; 902 return i;
903 } 903 }
904 904
905 return end(); 905 return end();
906 } 906 }
907 907
908 const_iterator find( const value &v ) const 908 const_iterator find( const value &v ) const
909 { 909 {
910 for( const_iterator i = begin(); i; i++ ) 910 for( const_iterator i = begin(); i; i++ )
911 { 911 {
912 if( (*i) == v ) 912 if( (*i) == v )
913 return i; 913 return i;
914 } 914 }
915 915
916 return end(); 916 return end();
917 } 917 }
918 918
919 /** 919 /**
920 * Get the current size of the list. 920 * Get the current size of the list.
921 *@returns (int) The current size of the list. 921 *@returns (int) The current size of the list.
922 */ 922 */
923 long getSize() const 923 long getSize() const
924 { 924 {
925 return core->nSize; 925 return core->nSize;
926 } 926 }
927 927
928 /** 928 /**
929 * Get the first item in the list. 929 * Get the first item in the list.
930 *@returns (value_type &) The first item in the list. 930 *@returns (value_type &) The first item in the list.
931 */ 931 */
932 value &first() 932 value &first()
933 { 933 {
934 if( core->pFirst->pValue == NULL ) 934 if( core->pFirst->pValue == NULL )
935 throw Bu::ExceptionBase("Attempt to read first element from empty list."); 935 throw Bu::ExceptionBase("Attempt to read first element from empty list.");
936 _hardCopy(); 936 _hardCopy();
937 return *core->pFirst->pValue; 937 return *core->pFirst->pValue;
938 } 938 }
939 939
940 /** 940 /**
941 * Get the first item in the list. 941 * Get the first item in the list.
942 *@returns (const value_type &) The first item in the list. 942 *@returns (const value_type &) The first item in the list.
943 */ 943 */
944 const value &first() const 944 const value &first() const
945 { 945 {
946 if( core->pFirst->pValue == NULL ) 946 if( core->pFirst->pValue == NULL )
947 throw Bu::ExceptionBase("Attempt to read first element from empty list."); 947 throw Bu::ExceptionBase("Attempt to read first element from empty list.");
948 return *core->pFirst->pValue; 948 return *core->pFirst->pValue;
949 } 949 }
950 950
951 /** 951 /**
952 * Get the last item in the list. 952 * Get the last item in the list.
953 *@returns (value_type &) The last item in the list. 953 *@returns (value_type &) The last item in the list.
954 */ 954 */
955 value &last() 955 value &last()
956 { 956 {
957 _hardCopy(); 957 _hardCopy();
958 return *core->pLast->pValue; 958 return *core->pLast->pValue;
959 } 959 }
960 960
961 /** 961 /**
962 * Get the last item in the list. 962 * Get the last item in the list.
963 *@returns (const value_type &) The last item in the list. 963 *@returns (const value_type &) The last item in the list.
964 */ 964 */
965 const value &last() const 965 const value &last() const
966 { 966 {
967 return *core->pLast->pValue; 967 return *core->pLast->pValue;
968 } 968 }
969 969
970 bool isEmpty() const 970 bool isEmpty() const
971 { 971 {
972 return (core->nSize == 0); 972 return (core->nSize == 0);
973 } 973 }
974 974
975 protected: 975 protected:
976 virtual Core *_copyCore( Core *src ) 976 virtual Core *_copyCore( Core *src )
977 { 977 {
978 Core *pRet = _allocateCore(); 978 Core *pRet = _allocateCore();
979 for( Link *pCur = src->pFirst; pCur; pCur = pCur->pNext ) 979 for( Link *pCur = src->pFirst; pCur; pCur = pCur->pNext )
980 { 980 {
981 pRet->append( *pCur->pValue ); 981 pRet->append( *pCur->pValue );
982 } 982 }
983 return pRet; 983 return pRet;
984 } 984 }
985 985
986 private: 986 private:
987 }; 987 };
988 988
989 class Formatter; 989 class Formatter;
990 Formatter &operator<<( Formatter &rOut, char *sStr ); 990 Formatter &operator<<( Formatter &rOut, char *sStr );
991 Formatter &operator<<( Formatter &rOut, signed char c ); 991 Formatter &operator<<( Formatter &rOut, signed char c );
992 template<typename a, typename b, typename c> 992 template<typename a, typename b, typename c>
993 Formatter &operator<<( Formatter &f, const Bu::List<a,b,c> &l ) 993 Formatter &operator<<( Formatter &f, const Bu::List<a,b,c> &l )
994 { 994 {
995 f << '['; 995 f << '[';
996 for( typename Bu::List<a,b,c>::const_iterator i = l.begin(); i; i++ ) 996 for( typename Bu::List<a,b,c>::const_iterator i = l.begin(); i; i++ )
997 { 997 {
998 if( i != l.begin() ) 998 if( i != l.begin() )
999 f << ", "; 999 f << ", ";
1000 f << *i; 1000 f << *i;
1001 } 1001 }
1002 f << ']'; 1002 f << ']';
1003 1003
1004 return f; 1004 return f;
1005 } 1005 }
1006 1006
1007 template<typename value, typename a, typename b> 1007 template<typename value, typename a, typename b>
1008 ArchiveBase &operator<<( ArchiveBase &ar, const List<value,a,b> &h ) 1008 ArchiveBase &operator<<( ArchiveBase &ar, const List<value,a,b> &h )
1009 { 1009 {
1010 ar << h.getSize(); 1010 ar << h.getSize();
1011 for( typename List<value>::const_iterator i = h.begin(); i != h.end(); i++ ) 1011 for( typename List<value>::const_iterator i = h.begin(); i != h.end(); i++ )
1012 { 1012 {
1013 ar << (*i); 1013 ar << (*i);
1014 } 1014 }
1015 1015
1016 return ar; 1016 return ar;
1017 } 1017 }
1018 1018
1019 template<typename value, typename a, typename b> 1019 template<typename value, typename a, typename b>
1020 ArchiveBase &operator>>( ArchiveBase &ar, List<value,a,b> &h ) 1020 ArchiveBase &operator>>( ArchiveBase &ar, List<value,a,b> &h )
1021 { 1021 {
1022 h.clear(); 1022 h.clear();
1023 long nSize; 1023 long nSize;
1024 ar >> nSize; 1024 ar >> nSize;
1025 1025
1026 for( long j = 0; j < nSize; j++ ) 1026 for( long j = 0; j < nSize; j++ )
1027 { 1027 {
1028 value v; 1028 value v;
1029 ar >> v; 1029 ar >> v;
1030 h.append( v ); 1030 h.append( v );
1031 } 1031 }
1032 1032
1033 return ar; 1033 return ar;
1034 } 1034 }
1035 1035
1036} 1036}
1037 1037
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 04:56:30 +0000