38 #include <EST_UList.h>
40 void EST_UList::clear_and_free(
void (*item_free)(
EST_UItem *p))
44 for (q=head(); q != 0; q = np)
55 int EST_UList::length()
const
60 for (ptr = head(); ptr != 0; ptr = ptr->next())
65 int EST_UList::index(
EST_UItem *item)
const
70 for (ptr = head(); ptr != 0; ptr = ptr->next(), ++n)
77 EST_UItem *EST_UList::nth_pointer(
int n)
const
82 for (i = 0, ptr = head(); ptr != 0; ptr = ptr->next(), ++i)
86 cerr <<
"Requested item #" << n <<
" off end of list" << endl;
100 item->p->n = item->n;
104 item->n->p = item->p;
117 return remove(nth_pointer(n), item_free);
133 new_item->n = prev_item->n;
134 prev_item->n = new_item;
136 new_item->p = prev_item;
137 if (new_item->n == 0)
140 new_item->n->p = new_item;
156 new_item->p = next_item->p;
157 next_item->p = new_item;
159 new_item->n = next_item;
160 if (new_item->p == 0)
163 new_item->p->n = new_item;
174 if ((a==0) || (b==0))
176 cerr <<
"EST_UList:exchange: can't exchange NULL items" << endl;
184 EST_UItem *ap=a->p,*an=a->n,*bn=b->n,*bp=b->p;
186 a->n = bn == a ? b : bn;
189 a->p = bp == a ? b : bp;
193 b->n = an == b ? a : an;
196 b->p = ap == b ? a : ap;
212 void EST_UList::exchange(
int i,
int j)
219 for (k=0,p = head(); p != 0; p = p->next(),k++)
227 if ((a==0) || (b==0))
229 cerr <<
"EST_UList:exchange: can't exchange items " << i <<
230 " and " << j <<
" (off end of list)" << endl;
237 void EST_UList::reverse()
241 for (p=head(); p != 0; p=q)
252 void EST_UList::append(
EST_UItem *new_item)
255 if (new_item == 0)
return;
266 void EST_UList::prepend(
EST_UItem *new_item)
268 if (new_item == 0)
return;
279 bool EST_UList::operator_eq(
const EST_UList &a,
285 for (p = a.head(); p != NULL; p = p->next()){
308 for (ptr = l.head(); ptr != 0; ptr = ptr->next(), ++n)
329 for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
333 if(gt(l_ptr, m_ptr)){
334 l.exchange(l_ptr,m_ptr);
365 if((i != j) && (i->prev() != j)){
386 q = partition(p,r, gt, exchange);
387 qsort_sub(l,p,q, gt, exchange);
388 qsort_sub(l,q->next(),r, gt, exchange);
396 qsort_sub(l,l.head(),l.tail(), gt, exchange);
400 void EST_UList::sort_unique(
EST_UList &l,
413 for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
418 if(gt(l_ptr, m_ptr)){
419 l.exchange(l_ptr,m_ptr);
421 }
else if(eq(l_ptr, m_ptr)){
422 l.remove(m_ptr, item_free);
441 sort_unique(l, eq, gt, item_free);
443 for(m_ptr=m.head(); m_ptr != 0; m_ptr=m_ptr->next()){
447 for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
448 if( gt(l_ptr, m_ptr) ){
449 l.insert_before(l_ptr, m_ptr);
452 }
else if( eq(m_ptr, l_ptr) ){
458 if(!flag && ( gt(m_ptr, l.tail()) ) )