cinelerra-5.1/guicast/linklist.h

   1 /*
   2  * CINELERRA
   3  * Copyright (C) 2008 Adam Williams <broadcast at earthling dot net>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18  *
  19  */
  20
  21
  22 #ifndef LINKLIST_H
  23 #define LINKLIST_H
  24
  25 template<class TYPE> class List;
  26
  27 template<class TYPE>
  28 class ListItem {
  29 public:
  30         TYPE *previous, *next;
  31         List<TYPE> *list;
  32
  33         int get_item_number() { return !list ? -1 : list->number_of((TYPE*)this); }
  34         ListItem() { list = 0;  previous = next = 0; }
  35         ListItem(List<TYPE> *me) { list = me;  previous = next = 0; }
  36         virtual ~ListItem() { if( list ) list->remove_pointer(this); }
  37 };
  38
  39 template<class TYPE>
  40 class List {
  41         TYPE *split(int (*cmpr)(TYPE *a, TYPE *b),TYPE *l, TYPE *r);
  42         static int cmpr(TYPE *a, TYPE *b) {
  43                 if( *a == *b ) return 0;
  44                 return *a > *b ? 1 : -1;
  45         }
  46 public:
  47         TYPE *first, *last;
  48         void remove(TYPE *item) { if(item) delete item; }
  49         void remove_pointer(ListItem<TYPE> *item);
  50         TYPE *append(TYPE *new_item);
  51         TYPE *append() { return append(new TYPE()); }
  52         void destroy() { while(last) delete last; }
  53         TYPE *insert_before(TYPE *here, TYPE *item);
  54         TYPE *insert_before(TYPE *here) { return insert_before(here, new TYPE()); }
  55         TYPE *insert_after(TYPE *here, TYPE *item);
  56         TYPE *insert_after(TYPE *here) { return insert_after(here, new TYPE()); }
  57         int total() { TYPE *p=first; int n=0; while(p) { p=p->next; ++n; } return n; }
  58         TYPE *get_item_number(int i) { TYPE *p=first;
  59                 while(p && i>0) { --i; p=p->next; }
  60                 return p;
  61         }
  62         TYPE &operator[](int i) { return *get_item_number(i); }
  63         int number_of(TYPE *item) { TYPE *p=first; int i=0;
  64                 while(p && p!=item) { ++i; p=p->next; }
  65                 return p ? i : -1;
  66         }
  67         void swap(TYPE *item1, TYPE *item2);
  68         void sort(TYPE *ap=0, TYPE *bp=0) { return sort(cmpr,ap,bp); }
  69         void sort(int (*cmp)(TYPE *a, TYPE *b), TYPE *ap=0, TYPE *bp=0);
  70         void concat(List<TYPE> &b);
  71         List() { first = last = 0; }
  72         virtual ~List() { destroy(); }
  73 };
  74
  75 // convenience macros
  76 #define PREVIOUS current->previous
  77 #define NEXT current->next
  78
  79 template<class TYPE>
  80 TYPE* List<TYPE>::append(TYPE *item)
  81 {
  82         item->list = this;  item->next = 0;
  83         if( !last ) { item->previous = 0; first = item; }
  84         else { item->previous = last;  last->next = item; }
  85         return last = item;
  86 }
  87
  88 template<class TYPE>
  89 TYPE* List<TYPE>::insert_before(TYPE *here, TYPE *item)
  90 {
  91         if( !here || !last ) return append(item);
  92         item->list = this;  item->next = here;
  93         *( !(item->previous=here->previous) ? &first : &here->previous->next ) = item;
  94         return here->previous = item;
  95 }
  96
  97 template<class TYPE>
  98 TYPE* List<TYPE>::insert_after(TYPE *here, TYPE *item)
  99 {
 100         if( !here || !last ) return append(item);
 101         item->list = this;  item->previous = here;
 102         *( !(item->next=here->next) ? &last : &here->next->previous ) = item;
 103         return here->next = item;
 104 }
 105
 106
 107 template<class TYPE>
 108 void List<TYPE>::remove_pointer(ListItem<TYPE> *item)
 109 {
 110         if( !item ) return;
 111         TYPE *previous = item->previous, *next = item->next;
 112         *( previous ? &previous->next : &first ) = next;
 113         *( next ? &next->previous : &last ) = previous;
 114         item->list = 0;
 115 }
 116
 117 template<class TYPE>
 118 void List<TYPE>::swap(TYPE *item1, TYPE *item2)
 119 {
 120         if( item1 == item2 ) return;
 121         TYPE *item1_previous = item1->previous, *item1_next = item1->next;
 122         TYPE *item2_previous = item2->previous, *item2_next = item2->next;
 123         *( item1_previous ? &item1_previous->next : &first ) = item2;
 124         *( item1_next     ? &item1_next->previous : &last  ) = item2;
 125         *( item2_previous ? &item2_previous->next : &first ) = item1;
 126         *( item2_next     ? &item2_next->previous : &last  ) = item1;
 127         item1->previous = item2_previous == item1 ? item2 : item2_previous;
 128         item1->next     = item2_next     == item1 ? item2 : item2_next;
 129         item2->previous = item1_previous == item2 ? item1 : item1_previous;
 130         item2->next     = item1_next     == item2 ? item1 : item1_next;
 131 }
 132
 133 template<class TYPE>
 134 TYPE *List<TYPE>::split(int (*cmpr)(TYPE *a, TYPE *b), TYPE *l, TYPE *r)
 135 {
 136         for(;;) {
 137                 while( cmpr(r,l) >= 0 ) if( (l=l->next) == r ) return r;
 138                 swap(l, r);
 139                 while( cmpr(l,r) >= 0 ) if( r == (l=l->previous) ) return r;
 140                 swap(l, r);
 141         }
 142 }
 143
 144 template<class TYPE>
 145 void List<TYPE>::sort(int (*cmpr)(TYPE *a, TYPE *b), TYPE *ll, TYPE *rr)
 146 {
 147         for(;;) {
 148                 TYPE *l = !ll ? first : ll->next;
 149                 if( l == rr ) return;
 150                 TYPE *r = !rr ? last  : rr->previous;
 151                 if( l == r ) return;
 152                 TYPE *m = split(cmpr, l, r);
 153                 sort(cmpr, ll, m);
 154                 ll = m;
 155         }
 156 }
 157
 158 template<class TYPE>
 159 void List<TYPE>::concat(List<TYPE> &b)
 160 {
 161         if( !b.first ) return;
 162         *(last ? &last->next : &first) = b.first;
 163         b.first->previous = last;  last = b.last;
 164         TYPE *bp = b.first;  b.first = b.last = 0;
 165         while( bp ) { bp->list = this;  bp = bp->next; }
 166 }
 167
 168 #endif