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((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); }
  16 };
  17
  18 template<class TYPE>
  19 class List {
  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;
  24         }
  25 public:
  26         TYPE *first, *last;
  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; }
  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(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(); }
  52 };
  53
  54 // convenience macros
  55 #define PREVIOUS current->previous
  56 #define NEXT current->next
  57
  58 template<class TYPE>
  59 TYPE* List<TYPE>::append(TYPE *item)
  60 {
  61         item->list = this;  item->next = 0;
  62         if( !last ) { item->previous = 0; first = item; }
  63         else { item->previous = last;  last->next = item; }
  64         return last = item;
  65 }
  66
  67 template<class TYPE>
  68 TYPE* List<TYPE>::insert_before(TYPE *here, TYPE *item)
  69 {
  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;
  74 }
  75
  76 template<class TYPE>
  77 TYPE* List<TYPE>::insert_after(TYPE *here, TYPE *item)
  78 {
  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;
  83 }
  84
  85
  86 template<class TYPE>
  87 void List<TYPE>::remove_pointer(ListItem<TYPE> *item)
  88 {
  89         if( !item ) return;
  90         TYPE *previous = item->previous, *next = item->next;
  91         *( previous ? &previous->next : &first ) = next;
  92         *( next ? &next->previous : &last ) = previous;
  93         item->list = 0;
  94 }
  95
  96 template<class TYPE>
  97 void List<TYPE>::swap(TYPE *item1, TYPE *item2)
  98 {
  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;
 110 }
 111
 112 template<class TYPE>
 113 TYPE *List<TYPE>::split(int (*cmpr)(TYPE *a, TYPE *b), TYPE *l, TYPE *r)
 114 {
 115         for(;;) {
 116                 while( cmpr(r,l) >= 0 ) if( (l=l->next) == r ) return r;
 117                 swap(l, r);
 118                 while( cmpr(l,r) >= 0 ) if( r == (l=l->previous) ) return r;
 119                 swap(l, r);
 120         }
 121 }
 122
 123 template<class TYPE>
 124 void List<TYPE>::sort(int (*cmpr)(TYPE *a, TYPE *b), TYPE *ll, TYPE *rr)
 125 {
 126         for(;;) {
 127                 TYPE *l = !ll ? first : ll->next;
 128                 if( l == rr ) return;
 129                 TYPE *r = !rr ? last  : rr->previous;
 130                 if( l == r ) return;
 131                 TYPE *m = split(cmpr, l, r);
 132                 sort(cmpr, ll, m);
 133                 ll = m;
 134         }
 135 }
 136
 137 template<class TYPE>
 138 void List<TYPE>::concat(List<TYPE> &b)
 139 {
 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; }
 145 }
 146
 147 #endif