4 template<class TYPE> class List;
12 int get_item_number() { return !list ? -1 : list->number_of((TYPE*)this); }
13 ListItem() { list = 0; previous = next = 0; }
14 ListItem(List<TYPE> *me) { list = me; previous = next = 0; }
15 virtual ~ListItem() { if( list ) list->remove_pointer(this); }
20 TYPE *split(int (*cmpr)(TYPE *a, TYPE *b),TYPE *l, TYPE *r);
21 static int cmpr(TYPE *a, TYPE *b) {
22 if( *a == *b ) return 0;
23 return *a > *b ? 1 : -1;
27 void remove(TYPE *item) { if(item) delete item; }
28 void remove_pointer(ListItem<TYPE> *item);
29 TYPE *append(TYPE *new_item);
30 TYPE *append() { return append(new TYPE()); }
31 void destroy() { while(last) delete last; }
32 TYPE *insert_before(TYPE *here, TYPE *item);
33 TYPE *insert_before(TYPE *here) { return insert_before(here, new TYPE()); }
34 TYPE *insert_after(TYPE *here, TYPE *item);
35 TYPE *insert_after(TYPE *here) { return insert_after(here, new TYPE()); }
36 int total() { TYPE *p=first; int n=0; while(p) { p=p->next; ++n; } return n; }
37 TYPE *get_item_number(int i) { TYPE *p=first;
38 while(p && i>0) { --i; p=p->next; }
41 TYPE &operator[](int i) { return *get_item_number(i); }
42 int number_of(TYPE *item) { TYPE *p=first; int i=0;
43 while(p && p!=item) { ++i; p=p->next; }
46 void swap(TYPE *item1, TYPE *item2);
47 void sort(TYPE *ap=0, TYPE *bp=0) { return sort(cmpr,ap,bp); }
48 void sort(int (*cmp)(TYPE *a, TYPE *b), TYPE *ap=0, TYPE *bp=0);
49 void concat(List<TYPE> &b);
50 List() { first = last = 0; }
51 virtual ~List() { destroy(); }
55 #define PREVIOUS current->previous
56 #define NEXT current->next
59 TYPE* List<TYPE>::append(TYPE *item)
61 item->list = this; item->next = 0;
62 if( !last ) { item->previous = 0; first = item; }
63 else { item->previous = last; last->next = item; }
68 TYPE* List<TYPE>::insert_before(TYPE *here, TYPE *item)
70 if( !here || !last ) return append(item);
71 item->list = this; item->next = here;
72 *( !(item->previous=here->previous) ? &first : &here->previous->next ) = item;
73 return here->previous = item;
77 TYPE* List<TYPE>::insert_after(TYPE *here, TYPE *item)
79 if( !here || !last ) return append(item);
80 item->list = this; item->previous = here;
81 *( !(item->next=here->next) ? &last : &here->next->previous ) = item;
82 return here->next = item;
87 void List<TYPE>::remove_pointer(ListItem<TYPE> *item)
90 TYPE *previous = item->previous, *next = item->next;
91 *( previous ? &previous->next : &first ) = next;
92 *( next ? &next->previous : &last ) = previous;
97 void List<TYPE>::swap(TYPE *item1, TYPE *item2)
99 if( item1 == item2 ) return;
100 TYPE *item1_previous = item1->previous, *item1_next = item1->next;
101 TYPE *item2_previous = item2->previous, *item2_next = item2->next;
102 *( item1_previous ? &item1_previous->next : &first ) = item2;
103 *( item1_next ? &item1_next->previous : &last ) = item2;
104 *( item2_previous ? &item2_previous->next : &first ) = item1;
105 *( item2_next ? &item2_next->previous : &last ) = item1;
106 item1->previous = item2_previous == item1 ? item2 : item2_previous;
107 item1->next = item2_next == item1 ? item2 : item2_next;
108 item2->previous = item1_previous == item2 ? item1 : item1_previous;
109 item2->next = item1_next == item2 ? item1 : item1_next;
113 TYPE *List<TYPE>::split(int (*cmpr)(TYPE *a, TYPE *b), TYPE *l, TYPE *r)
116 while( cmpr(r,l) >= 0 ) if( (l=l->next) == r ) return r;
118 while( cmpr(l,r) >= 0 ) if( r == (l=l->previous) ) return r;
124 void List<TYPE>::sort(int (*cmpr)(TYPE *a, TYPE *b), TYPE *ll, TYPE *rr)
127 TYPE *l = !ll ? first : ll->next;
128 if( l == rr ) return;
129 TYPE *r = !rr ? last : rr->previous;
131 TYPE *m = split(cmpr, l, r);
138 void List<TYPE>::concat(List<TYPE> &b)
140 if( !b.first ) return;
141 *(last ? &last->next : &first) = b.first;
142 b.first->previous = last; last = b.last;
143 TYPE *bp = b.first; b.first = b.last = 0;
144 while( bp ) { bp->list = this; bp = bp->next; }