25eeaf2f8a38788422931b0d9d14b4d3e9606f2d
[goodguy/history.git] / cinelerra-5.1 / guicast / linklist.h
1 #ifndef LINKLIST_H
2 #define LINKLIST_H
3
4 template<class TYPE> class List;
5
6 template<class TYPE>
7 class ListItem {
8 public:
9         TYPE *previous, *next;
10         List<TYPE> *list;
11
12         int get_item_number() { return !list ? -1 : list->number_of(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); }
16 };
17
18 template<class TYPE>
19 class List {
20         TYPE *split(int (*cmpr)(TYPE *a, TYPE *b),TYPE *l, TYPE *r);
21         void sort(int (*cmpr)(TYPE *a, TYPE *b),TYPE *ll, TYPE *rr);
22         static int cmpr(TYPE *a, TYPE *b) {
23                 if( *a == *b ) return 0;
24                 return *a > *b ? 1 : -1;
25         }
26 public:
27         TYPE *first, *last;
28         void remove(TYPE *item) { if(item) delete item; }
29         void remove_pointer(ListItem<TYPE> *item);
30         TYPE *append(TYPE *new_item);
31         TYPE *append() { return append(new TYPE()); }
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; }
39                 return p;
40         }
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; }
44                 return p ? i : -1;
45         }
46         void swap(TYPE *item1, TYPE *item2);
47         void sort(int (*cmp)(TYPE *a, TYPE *b) = 0) {
48                 return sort(cmp ? cmp : cmpr,0,0); }
49         List() { first = last = 0; }
50         virtual ~List() { while(last) delete last; }
51 };
52
53 // convenience macros
54 #define PREVIOUS current->previous
55 #define NEXT current->next
56
57 template<class TYPE>
58 TYPE* List<TYPE>::append(TYPE *item)
59 {
60         item->list = this;  item->next = 0;
61         if( !last ) { item->previous = 0; first = item; }
62         else { item->previous = last;  last->next = item; }
63         return last = item;
64 }
65
66 template<class TYPE>
67 TYPE* List<TYPE>::insert_before(TYPE *here, TYPE *item)
68 {
69         if( !here || !last ) return append(item);
70         item->list = this;  item->next = here;
71         *( !(item->previous=here->previous) ? &first : &here->previous->next ) = item;
72         return here->previous = item;
73 }
74
75 template<class TYPE>
76 TYPE* List<TYPE>::insert_after(TYPE *here, TYPE *item)
77 {
78         if( !here || !last ) return append(item);
79         item->list = this;  item->previous = here;
80         *( !(item->next=here->next) ? &last : &here->next->previous ) = item;
81         return here->next = item;
82 }
83
84
85 template<class TYPE>
86 void List<TYPE>::remove_pointer(ListItem<TYPE> *item)
87 {
88         if( !item ) return;
89         TYPE *previous = item->previous, *next = item->next;
90         *( previous ? &previous->next : &first ) = next;
91         *( next ? &next->previous : &last ) = previous;
92         item->list = 0;
93 }
94
95 template<class TYPE>
96 void List<TYPE>::swap(TYPE *item1, TYPE *item2)
97 {
98         if( item1 == item2 ) return;
99         TYPE *item1_previous = item1->previous, *item1_next = item1->next;
100         TYPE *item2_previous = item2->previous, *item2_next = item2->next;
101         *( item1_previous ? &item1_previous->next : &first ) = item2;
102         *( item1_next     ? &item1_next->previous : &last  ) = item2;
103         *( item2_previous ? &item2_previous->next : &first ) = item1;
104         *( item2_next     ? &item2_next->previous : &last  ) = item1;
105         item1->previous = item2_previous == item1 ? item2 : item2_previous;
106         item1->next     = item2_next     == item1 ? item2 : item2_next;
107         item2->previous = item1_previous == item2 ? item1 : item1_previous;
108         item2->next     = item1_next     == item2 ? item1 : item1_next;
109 }
110
111 template<class TYPE>
112 TYPE *List<TYPE>::split(int (*cmpr)(TYPE *a, TYPE *b), TYPE *l, TYPE *r)
113 {
114         for(;;) {
115                 while( cmpr(r,l) >= 0 ) if( (l=l->next) == r ) return r;
116                 swap(l, r);
117                 while( cmpr(l,r) >= 0 ) if( r == (l=l->previous) ) return r;
118                 swap(l, r);
119         }
120 }
121
122 template<class TYPE>
123 void List<TYPE>::sort(int (*cmpr)(TYPE *a, TYPE *b), TYPE *ll, TYPE *rr)
124 {
125         for(;;) {
126                 TYPE *l = !ll ? first : ll->next;
127                 if( l == rr ) return;
128                 TYPE *r = !rr ? last  : rr->previous;
129                 if( l == r ) return;
130                 TYPE *m = split(cmpr, l, r);
131                 sort(cmpr, ll, m);
132                 ll = m;
133         }
134 }
135
136 #endif