aboutsummaryrefslogtreecommitdiff
path: root/src/list.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/list.h127
1 files changed, 112 insertions, 15 deletions
diff --git a/src/list.h b/src/list.h
index d8c5a4a..f76c505 100644
--- a/src/list.h
+++ b/src/list.h
@@ -11,7 +11,8 @@
11#include <memory> 11#include <memory>
12#include "bu/exceptionbase.h" 12#include "bu/exceptionbase.h"
13#include "bu/sharedcore.h" 13#include "bu/sharedcore.h"
14//#include "bu/util.h" 14#include "bu/archivebase.h"
15#include "bu/heap.h"
15 16
16namespace Bu 17namespace Bu
17{ 18{
@@ -23,7 +24,7 @@ namespace Bu
23 ListLink *pPrev; 24 ListLink *pPrev;
24 }; 25 };
25 26
26 template<typename value, typename cmpfunc, typename valuealloc, 27 template<typename value, typename valuealloc,
27 typename linkalloc> 28 typename linkalloc>
28 struct ListCore 29 struct ListCore
29 { 30 {
@@ -42,7 +43,6 @@ namespace Bu
42 Link *pFirst; 43 Link *pFirst;
43 Link *pLast; 44 Link *pLast;
44 long nSize; 45 long nSize;
45 cmpfunc cmp;
46 linkalloc la; 46 linkalloc la;
47 valuealloc va; 47 valuealloc va;
48 48
@@ -189,16 +189,15 @@ namespace Bu
189 *@param linkalloc (typename) Memory Allocator for the list links. 189 *@param linkalloc (typename) Memory Allocator for the list links.
190 *@ingroup Containers 190 *@ingroup Containers
191 */ 191 */
192 template<typename value, typename cmpfunc=__basicGTCmp<value>, 192 template<typename value, typename valuealloc=std::allocator<value>,
193 typename valuealloc=std::allocator<value>,
194 typename linkalloc=std::allocator<struct ListLink<value> > > 193 typename linkalloc=std::allocator<struct ListLink<value> > >
195 class List : public SharedCore< struct ListCore<value, cmpfunc, valuealloc, 194 class List : public SharedCore< struct ListCore<value, valuealloc,
196 linkalloc> > 195 linkalloc> >
197 { 196 {
198 private: 197 private:
199 typedef struct ListLink<value> Link; 198 typedef struct ListLink<value> Link;
200 typedef class List<value, cmpfunc, valuealloc, linkalloc> MyType; 199 typedef class List<value, valuealloc, linkalloc> MyType;
201 typedef struct ListCore<value, cmpfunc, valuealloc, linkalloc> Core; 200 typedef struct ListCore<value, valuealloc, linkalloc> Core;
202 201
203 protected: 202 protected:
204 using SharedCore< Core >::core; 203 using SharedCore< Core >::core;
@@ -241,6 +240,26 @@ namespace Bu
241 return *this; 240 return *this;
242 } 241 }
243 242
243 bool operator==( const MyType &rhs )
244 {
245 if( getSize() != rhs.getSize() )
246 return false;
247
248 for( typename MyType::const_iterator a = begin(), b = rhs.begin();
249 a; a++, b++ )
250 {
251 if( *a != *b )
252 return false;
253 }
254
255 return true;
256 }
257
258 bool operator!=( const MyType &rhs )
259 {
260 return !(*this == rhs);
261 }
262
244 /** 263 /**
245 * Clear the data from the list. 264 * Clear the data from the list.
246 */ 265 */
@@ -350,6 +369,41 @@ namespace Bu
350 return *this; 369 return *this;
351 } 370 }
352 371
372 template<typename cmptype>
373 void sort( cmptype cmp )
374 {
375 Heap<value, cmptype, valuealloc> hSort( cmp, getSize() );
376 for( typename MyType::iterator i = begin(); i; i++ )
377 {
378 hSort.enqueue( *i );
379 }
380 clear();
381 while( !hSort.isEmpty() )
382 {
383 append( hSort.dequeue() );
384 }
385 }
386
387 void sort()
388 {
389 sort<__basicLTCmp<value> >();
390 }
391
392 template<typename cmptype>
393 void sort()
394 {
395 Heap<value, cmptype, valuealloc> hSort( getSize() );
396 for( typename MyType::iterator i = begin(); i; i++ )
397 {
398 hSort.enqueue( *i );
399 }
400 clear();
401 while( !hSort.isEmpty() )
402 {
403 append( hSort.dequeue() );
404 }
405 }
406
353 /** 407 /**
354 * Insert a new item in sort order by searching for the first item that 408 * Insert a new item in sort order by searching for the first item that
355 * is larger and inserting this before it, or at the end if none are 409 * is larger and inserting this before it, or at the end if none are
@@ -357,7 +411,8 @@ namespace Bu
357 * List all items will be sorted. To use this, the value type must 411 * List all items will be sorted. To use this, the value type must
358 * support the > operator. 412 * support the > operator.
359 */ 413 */
360 MyType &insertSorted( const value &v ) 414 template<typename cmptype>
415 MyType &insertSorted( cmptype cmp, const value &v )
361 { 416 {
362 _hardCopy(); 417 _hardCopy();
363 if( core->pFirst == NULL ) 418 if( core->pFirst == NULL )
@@ -371,7 +426,7 @@ namespace Bu
371 Link *pCur = core->pFirst; 426 Link *pCur = core->pFirst;
372 for(;;) 427 for(;;)
373 { 428 {
374 if( !core->cmp( v, *(pCur->pValue)) ) 429 if( cmp( v, *(pCur->pValue)) )
375 { 430 {
376 core->insert( pCur, v ); 431 core->insert( pCur, v );
377 return *this; 432 return *this;
@@ -385,6 +440,18 @@ namespace Bu
385 } 440 }
386 } 441 }
387 } 442 }
443
444 MyType &insertSorted( const value &v )
445 {
446 return insertSorted<__basicLTCmp<value> >( v );
447 }
448
449 template<typename cmptype>
450 MyType &insertSorted( const value &v )
451 {
452 cmptype cmp;
453 return insertSorted( cmp, v );
454 }
388 455
389 /** 456 /**
390 * An iterator to iterate through your list. 457 * An iterator to iterate through your list.
@@ -392,7 +459,7 @@ namespace Bu
392 typedef struct iterator 459 typedef struct iterator
393 { 460 {
394 friend struct const_iterator; 461 friend struct const_iterator;
395 friend class List<value, cmpfunc, valuealloc, linkalloc>; 462 friend class List<value, valuealloc, linkalloc>;
396 private: 463 private:
397 Link *pLink; 464 Link *pLink;
398 465
@@ -559,7 +626,7 @@ namespace Bu
559 */ 626 */
560 typedef struct const_iterator 627 typedef struct const_iterator
561 { 628 {
562 friend class List<value, cmpfunc, valuealloc, linkalloc>; 629 friend class List<value, valuealloc, linkalloc>;
563 private: 630 private:
564 Link *pLink; 631 Link *pLink;
565 632
@@ -844,11 +911,11 @@ namespace Bu
844 class Formatter; 911 class Formatter;
845 Formatter &operator<<( Formatter &rOut, char *sStr ); 912 Formatter &operator<<( Formatter &rOut, char *sStr );
846 Formatter &operator<<( Formatter &rOut, signed char c ); 913 Formatter &operator<<( Formatter &rOut, signed char c );
847 template<typename a, typename b, typename c, typename d> 914 template<typename a, typename b, typename c>
848 Formatter &operator<<( Formatter &f, const Bu::List<a,b,c,d> &l ) 915 Formatter &operator<<( Formatter &f, const Bu::List<a,b,c> &l )
849 { 916 {
850 f << '['; 917 f << '[';
851 for( typename Bu::List<a,b,c,d>::const_iterator i = l.begin(); i; i++ ) 918 for( typename Bu::List<a,b,c>::const_iterator i = l.begin(); i; i++ )
852 { 919 {
853 if( i != l.begin() ) 920 if( i != l.begin() )
854 f << ", "; 921 f << ", ";
@@ -858,6 +925,36 @@ namespace Bu
858 925
859 return f; 926 return f;
860 } 927 }
928
929 template<typename value, typename a, typename b>
930 ArchiveBase &operator<<( ArchiveBase &ar, const List<value,a,b> &h )
931 {
932 ar << h.getSize();
933 for( typename List<value>::const_iterator i = h.begin(); i != h.end(); i++ )
934 {
935 ar << (*i);
936 }
937
938 return ar;
939 }
940
941 template<typename value, typename a, typename b>
942 ArchiveBase &operator>>( ArchiveBase &ar, List<value,a,b> &h )
943 {
944 h.clear();
945 long nSize;
946 ar >> nSize;
947
948 for( long j = 0; j < nSize; j++ )
949 {
950 value v;
951 ar >> v;
952 h.append( v );
953 }
954
955 return ar;
956 }
957
861} 958}
862 959
863#endif 960#endif