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