/*******************************************************************************
+
+  LEDA 3.5
+
+  _dlist.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
//------------------------------------------------------------------------------
// Doubly Linked Lists
//
// S. Naeher 
//
// last modifications: January 1997 (STL iterators and operations)
//                     March   1997 (sorting)
//------------------------------------------------------------------------------

#include <LEDA/impl/dlist.h>
#include <ctype.h>

#ifdef SWAP
#undef SWAP
#endif

#define SWAP(a,b) { dlink* x = *a; *a = *b; *b = x; }

dlist::dlist()      
{ h=0; 
  t=0;
  count=0;
  iterator=0; 
}

dlist::dlist(GenPtr a) 
{ h=t=new dlink(a,0,0);
  count=1; 
  iterator=0;  
}

dlist::dlist(const dlist& x)
{ dlink* p;

  iterator=h=t=0; 
  count = 0; 
                              
  for (p = x.h; p; p = p->succ) append(p->e); 

  int type_id = el_type_id();
  if (type_id != INT_TYPE_ID && type_id != PTR_TYPE_ID)
    for (p = h; p; p = p->succ) x.copy_el(p->e);
}


void dlist::recompute_length() const
{ int n = 0;
  for(dlink* it = h; it; it = it->succ)  n++;
  *(int*)&count = n;
}



#if defined(LEDA_OLD_ITERATION)

dlink* dlist::move_iterator(int dir) const 
{ if (iterator) 
     set_iterator(dir ? iterator->pred : iterator->succ);
  else 
     set_iterator(dir ? t : h);
  return iterator;
 } 

bool dlist::current_element(GenPtr& x) const 
{ if (iterator) 
  { x = iterator->e; 
    return true; 
   } 
  return false; 
 }

bool dlist::next_element(GenPtr& x)    const 
{ if (iterator) 
     set_iterator(iterator->succ);
  else 
     set_iterator(h);

  if (iterator) 
  { x = iterator->e;
    return true; 
   } 
  return false; 
 }

bool dlist::prev_element(GenPtr& x)  const
{ if (iterator) 
     set_iterator(iterator->pred);
  else 
     set_iterator(t);

  if (iterator) 
  { x = iterator->e;
    return true; 
   } 
  return false; 
 }

#endif



//------------------------------------------------------------------------------

dlink* dlist::get_item(int i) const
{ dlink* p = h;
  while ( p && i--) p = p->succ; 
  return p;
}

dlink* dlist::succ(dlink* p, int i)  const
{ while ( p && i--) p = p->succ; 
  return p;
}

dlink* dlist::pred(dlink* p, int i) const
{ while ( p && i--) p = p->pred; 
  return p;
}

dlink* dlist::search(GenPtr x) const  /* linear search */
{ dlink* p = h;
  while ( p && cmp(p->e,x) != 0) p = p->succ; 
  return p;
} 

void dlist::remove(GenPtr x)
{ dlink* p = h;

  switch (el_type_id()) {
  
      case INT_TYPE_ID:
           { int y = LEDA_ACCESS(int,x);
             while (p)
             { dlink* n = p->succ;
               if (n && LEDA_ACCESS(int,n->e) == y) del(n);
               else p = n;
              }
            }
           break;
  
      case DOUBLE_TYPE_ID:
           { double y = LEDA_ACCESS(double,x);
             while (p)
             { dlink* n = p->succ;
               if (n && LEDA_ACCESS(double,n->e) == y) del(n);
               else p = n;
              }
            }
           break;
  
      default:
           while (p)
           { dlink* n = p->succ;
             if (n && cmp(n->e,x) == 0) del(n);
             else p = n;
            }
           break;
  }
} 



int dlist::rank(GenPtr x)   const   /* rank by linear search */
{ dlink* p = h;
  int r = 1;
  while ( p && cmp(p->e,x) != 0)
  { p = p->succ; 
    r++;
   }
  return (p) ? r : 0;
} 

GenPtr dlist::pop()    
{ if (h==nil) 
    error_handler(1,"dlist: pop on empty list.");
  dlink* x=h; 
  h = h->succ;
  if (h) h->pred = 0;
  else t = nil;
  GenPtr p = x->e;
  delete x;
  count--;
  return p;
}


GenPtr dlist::Pop()    
{ if (h==nil) 
    error_handler(1,"dlist: Pop on empty list.");
  dlink* x=t; 
  t = t->pred;
  if (t) t->succ = 0;
  else h = nil;
  GenPtr p = x->e;
  delete x;
  count--;
  return p;
}

dlink* dlist::insert(GenPtr a, dlink* l, int dir) 
{ 
  //if (l==0) return dir ? append(a) : push(a); 
  //if (l==0) error_handler(1,"dlist::insert: nil position argument.");

  // for stl insert
  if (l==0) return append(a);

  dlink* s=l->succ;
  dlink* p=l->pred;
  dlink* n;
  
  if (dir==0) //insert after l
  { n= new dlink(a,l,s);
    l->succ = n;
    if (l==t) t=n;
    else s->pred = n;}

  else //insert before l
  { n= new dlink(a,p,l);
    l->pred = n;
    if (l==h) h=n;
    else p->succ = n;}

  if (count >= 0) count++;
 
  return n;
}


void dlist::swap(dlist& l)
{ dlink* tmp;
  int tmp1;
  tmp = l.h; l.h = h; h = tmp;
  tmp = l.t; l.t = t; t = tmp;
  tmp = l.iterator; l.iterator = iterator; iterator = tmp;
  tmp1 = l.count; l.count = count; count = tmp1;
}


void dlist::conc(dlist& l, int dir)
{ 
  if (h==nil)
   { h = l.h; 
     t = l.t; 
    }
  else
  { if (dir==0)  // append l 
    { t->succ = l.h;
      if (l.h) { l.h->pred = t; t = l.t; } 
     }
    else // prepend l
    { h->pred = l.t;
      if (l.t) { l.t->succ= h; h = l.h; } 
     }
   }

 if (count < 0 || l.count < 0)
    count = -1;
 else
    count += l.count;

 l.h = l.t = 0;
 l.count = 0;
}


void dlist::splice(dlink* pos, dlist& l)
{ if (this == &l)
     error_handler(1,"list::splice: cannot splice list into itself");

  if (l.h == nil) return;
  if (pos == 0) { conc(l); return; }
  dlist l1;
  split(pos,*this,l1);
  conc(l);
  conc(l1);
 }

void dlist::splice(dlink* pos, dlist& l0, dlink* it1, dlink* it2)
{ if (l0.h == nil) return;
  dlist l1,l2;
  if (it1 == 0) it1 = l0.h;
  l0.split(it1,l0,l1);
  if (it2) l1.split(it2,l1,l2);
  l0.conc(l2);
  splice(pos,l1);
}

void dlist::splice(dlink* pos, dlist& l0, dlink* it)
{ if (it && pos != it && pos != it->succ)
    splice(pos,l0,it,it->succ); 
 }



void dlist::unique(int special)
{ dlink* p = h;

  int type_id = (special) ? el_type_id() : UNKNOWN_TYPE_ID;

  while (p)
  { dlink* q = p->succ;

    switch (type_id) {
  
      case INT_TYPE_ID:
           while (q && LEDA_ACCESS(int,p->e) == LEDA_ACCESS(int,q->e))
           { del(q);
             q = p->succ;
            }
           break;
  
      case DOUBLE_TYPE_ID:
           while (q && LEDA_ACCESS(double,p->e) == LEDA_ACCESS(double,q->e)) 
           { clear_el(q->e);
             del(q);
             q = p->succ;
            }
           break;
  
      default:
           while (q && cmp(p->e, q->e) == 0) 
           { clear_el(q->e);
             del(q);
             q = p->succ;
            }
           break;
     }

    p = q;
   }
}


void dlist::merge(dlist& L, int special)
{ 
  if (h == 0 && L.h == 0) return;

  int type_id = (special) ? el_type_id() : UNKNOWN_TYPE_ID;

/* we will maintain the invariant that p1 points to the last element of 
   the result list and that the two lists to be merged start at q = p1 -> succ
   and p2. In particular, p1 -> e is at most as large as q -> e and p2 -> e
   (if defined). The order between the latter elements is unknown. 

   we establish the invariant by making p1 the head of a non-empty list
   and, if both lists are non-empty the head of the list with the smaller
   first element (ties are broken arbitrarily) 
*/


  dlink* p1 = h;
  dlink* p2 = L.h;

  if (p1 == 0 || ( p2 && cmp(p1->e,p2->e) > 0 )) 
  { p1 = L.h; 
    p2 = h;
   }

  h = p1;
  dlink* q = p1 -> succ;  // to establish the invariant about q

  switch (type_id) {

    case INT_TYPE_ID:
         while (p2)
         { int x = LEDA_ACCESS(int,p2->e);
           while (q && LEDA_ACCESS(int,q->e) <= x) { p1 = q; q = q->succ; }
           // we have p1->e <= p2->e < p1->succ->e, where p1->succ may
           // or may not exist. It is safe to p1 to p2 and p2 to p1->succ. 
           p1->succ = p2;
           p2->pred = p1;
           p1 = p2;
           p2 = q;
           q = p1 -> succ;
          }
         break;

    case DOUBLE_TYPE_ID:
         while (p2)
         { double x = LEDA_ACCESS(double,p2->e);
           while (q && LEDA_ACCESS(double,q->e) <= x) { p1 = q; q = q->succ; }
           p1->succ = p2;
           p2->pred = p1;
           p1 = p2;
           p2 = q;
           q = p1 -> succ;
          }
         break;

    default:
         while (p2)
         { GenPtr x = p2->e;
           while (q && cmp(q->e,x) <= 0) { p1 = q; q = q->succ; }
           p1->succ = p2;
           p2->pred = p1;
           p1 = p2;
           p2 = q;
           q = p1 -> succ;
          }
         break;
   }

  while (p1->succ) p1 = p1->succ;

  t = p1;

  if (count < 0 || L.count < 0)
    count = -1;
  else
    count += L.count;

  L.h = L.t = nil;
  L.count = 0;
}



void dlist::split(dlink* p, dlist& L1, dlist& L2, int dir)
{ 
  // split L0 at item p into L1 and L2 and  L is made empty
  // if p == nil copy L0 to L2 and make L1 empty (if not identical to L0)
  // if p != nil we have to distinguish two cases
  // dir == 0: p becomes first item of L2
  // dir != 0: p becomes last item of L1

  if (h == nil) error_handler(1,"dlist::split: list is empty.");
  if (&L1 == &L2) error_handler(1,"dlist::split: identical arguments.");

  if (this != &L1) L1.clear();
  if (this != &L2) L2.clear();

  if (p == nil) 
  { p = h;
    dir = 0;
   }

 /* The first item of L1 is either h or nil depending whether L1 is non-empty
  * or not. L1 is empty if dir == 0 and p->pred does not exist. A similar 
  * argument applies to L2. 
  */

  dlink* L1_last  = (dir != 0) ? p : p->pred;
  dlink* L1_first = (L1_last)  ? h : nil;

  dlink* L2_first = (dir == 0) ? p : p->succ;
  dlink* L2_last =  (L2_first) ? t : nil;

  h = t = 0;
  count = 0;

  L1.h = L1_first;
  L1.t = L1_last;
  L1.count = -1; // size unknown
  if (L1_last) L1_last->succ = 0;

  L2.h = L2_first;
  L2.t = L2_last;
  L2.count = -1; // size unknown
  if (L2_first) L2_first->pred = 0;
}


void dlist::move_to_front(dlink* it)
{
  if (it == nil) 
     error_handler(1,"dlist::move_to_front: nil argument");

  dlink*  p = it->pred; 
  dlink*  s = it->succ; 

  if (p == nil) return;  // first item, nothing to do

  // unchain

  p->succ = s;

  if (s != nil)
     s->pred = p;
  else
     t = p;

  // insert at front

  it->pred = nil;
  it->succ = h;

  h->pred = it;
  h = it;
}



void dlist::move_to_back(dlink* it)
{
  if (it == nil) 
     error_handler(1,"dlist::move_to_back: nil argument");

  dlink*  p = it->pred; 
  dlink*  s = it->succ; 

  if (s == nil) return;  // last item, nothing to do

  // unchain

  s->pred = p;

  if (p != nil)
     p->succ = s;
  else
     h = s;

  // insert at rear end

  it->succ = nil;
  it->pred = t;

  t->succ = it;
  t = it;
}
  
  


GenPtr dlist::del(dlink* it)
{ 
  if (it==nil) error_handler(999,"dlist: delete nil-item");
  if (it==h)   return pop();
  if (it==t)   return Pop();
  dlink*  p = it->pred;
  dlink*  s = it->succ;
  GenPtr x = it->e;
  p->succ = s;
  s->pred = p;
  count--;
  delete it;
  return x;
}

dlink* dlist::cyclic_succ(dlink* it) const
{ if (it==0) return 0;
  return it->succ? it->succ : h;
}

dlink* dlist::cyclic_pred(dlink* it) const
{ if (it==0) return 0;
  return it->pred? it->pred : t;
}


dlink* dlist::max() const
{ if (h==0) return 0;
  dlink* m=h;
  dlink* p=m->succ;

  while (p)
  { if (cmp(p->e,m->e) > 0) m=p;
    p=p->succ;
   }

  return m;
}

dlink* dlist::min() const
{ if (h==0) return 0;
  dlink* m=h;
  dlink* p=m->succ;

  while (p)
  { if (cmp(p->e,m->e) < 0) m=p;
    p=p->succ;
   }

  return m;
}


void dlist::apply()
{ dlink* p = h;
  while (p)
  { app(p->e);
    p = p->succ;
   }
}



void dlist::reverse_items()
{ 
  length();

  list_item* A = new list_item[count+2];
  list_item x = h;
  int j;

  A[0] = A[count+1] = 0;
 
  for(j=count; j > 0; j--)
  { A[j] = x;
    x = x->succ;
   }

  for(j=1; j<=count; j++) 
  { A[j]->succ = A[j+1];
    A[j]->pred = A[j-1];
   }

  h = A[1];
  t = A[count];
  
  delete[] A;
}


void dlist::reverse_items(list_item it1, list_item it2)
{ //reverse sublist between it1 and it2 (inclusive)
  if (it1 == nil || it2 == nil) 
        error_handler(1,"dlist::reverse: nil argument.");

  if (it1 == it2) return;

  list_item p = it1;
  while (p && p != it2) p = p->succ;
  if (p == nil)
      error_handler(1,"dlist::reverse(it1,it2): it1 not before it2");

  if (it2 == it1->succ)
  { list_item p = it1->pred;
    list_item s = it2->succ;
    it1->succ = s;
    it1->pred = it2;
    if (s) 
       s->pred = it1;
    else
       t = it1;
    it2->succ = it1;
    it2->pred = p;
    if (p) 
      p->succ = it2; 
    else
      h = it2;
    return;
  }


  int n = count;

  dlist L1;
  dlist L2;
  split(it1,L1,L2);
  conc(L1);
  L2.split(it2,L1,L2);
  L1.reverse_items();
  conc(L1);
  conc(L2);
  count = n;
}

        


void dlist::permute()
{ 
  length();

  list_item* A = new list_item[count+2];
  list_item x = h;
  int j;

  A[0] = A[count+1] = 0;
 
  for(j=1; j <= count; j++)
  { A[j] = x;
    x = x->succ;
   }

  for(j=1; j<count; j++)  
  { int r = rand_int(j,count);
    x = A[j];
    A[j] = A[r];
    A[r] = x;
   }

  for(j=1; j<=count; j++) 
  { A[j]->succ = A[j+1];
    A[j]->pred = A[j-1];
   }

  h = A[1];
  t = A[count];
  
  delete[] A;
}
        

void dlist::bucket_sort(int i, int j)
{ 
  if (h==nil) return; // empty list

  int n = j-i+1;

  list_item* bucket= new list_item[n+1];

  if (bucket == 0)
    error_handler(1,
      string("list::bucketsort: cannot allocate %d buckets (out of memory)",n));
  
  list_item* stop = bucket + n;
  list_item* p;

  list_item q;
  list_item x;

  for(p=bucket;p<=stop;p++)  *p = 0;

  while (h) 
  { x = h; 
    h = h->succ;
    int k = ord(x->e);
    if (k >= i && k <= j) 
     { p = bucket+k-i;
       x->pred = *p;
       if (*p) (*p)->succ = x;
       *p = x;
      }
    else 
       error_handler(4,string("bucket_sort: value %d out of range",k)) ;
   }

 for(p=stop; *p==0; p--); 

 // now p points to the end of the rightmost non-empty bucket
 // make it the new head  of the list (remember: list is not empty)

 t = *p;
 t->succ = nil;

 for(q = *p; q->pred; q = q->pred); // now q points to the start of this bucket

 // link buckets together from right to left:
 // q points to the start of the last bucket
 // p points to end of the next bucket

 while(--p >= bucket) 
   if (*p)
   { (*p)->succ = q;
     q->pred = *p;
     for(q = *p; q->pred; q = q->pred); 
    }

 h = q;   // head = start of leftmost non-empty bucket

 delete[] bucket;
}


void dlist::bucket_sort()
{ 
  if (h==nil) return; // empty list
  int i = ord(h -> e);
  int j = i;
  
  list_item p = h -> succ;
  
  while (p)
  { int o = ord(p -> e);
    if ( o < i ) i = o;
    if ( o > j ) j = o;
    p = p -> succ;
  }

  bucket_sort(i,j);
}



void dlist::sort(int min_d, int special)
{ 
  if (min_d < 1) min_d = 1;

  if (length() <= 1) return;    // nothing to sort

  int type_id = (special) ? el_type_id() : UNKNOWN_TYPE_ID;

  dlink** A = new dlink*[count+2];
  dlink** left  = A+1;
  dlink** right = A+count;

  dlink** p = A+1;
  for(dlink* it = h; it; it = it->succ) *p++ = it;

  switch (type_id) {

    case INT_TYPE_ID: {
         int* D = new int[count+2];
         int* dp = D+1;
         for(dlink** q=left; q<=right; q++) *dp++ = LEDA_ACCESS(int,(*q)->e);
         int_quick_sort(A,D,1,count,min_d);
         delete[] D;
         if (min_d > 1)
           int_insertion_sort(left,right,right);
         break;
       }

    case FLOAT_TYPE_ID: {
         min_d = 1;
         float* D = new float[count+2];
         float* dp = D+1;
         for(dlink** q=left; q<=right; q++) *dp++ = LEDA_ACCESS(float,(*q)->e);
         float_quick_sort(A,D,1,count,min_d);
         delete[] D;
         break;
       }

    case DOUBLE_TYPE_ID: {
         double* D = new double[count+2];
         double* dp = D+1;
         for(dlink** q=left; q<=right; q++) *dp++ = LEDA_ACCESS(double,(*q)->e);
         double_quick_sort(A,D,1,count,min_d);
         delete[] D;
         if (min_d > 1)
           double_insertion_sort(left,right,right);
         break;
       }

    default: {
         GenPtr* D = new GenPtr[count+2];
         GenPtr* dp = D+1;
         for(dlink** q=left; q<=right; q++) *dp++ = (*q)->e;
         gen_quick_sort(A,D,1,count,min_d);
         delete[] D;
         if (min_d > 1)
           gen_insertion_sort(left,right,right);
         break;
      }
   }


  A[0] = A[count+1] = 0;

  for(dlink** q=left; q<=right; q++) 
  { (*q)->succ = *(q+1);
    (*q)->pred = *(q-1);
   }

  h = *left;
  t = *right;

  delete[] A;
}


/*
#define QS_SELECT(l,r) (l+rand_int()%(r-l))
*/
#define QS_SELECT(l,r) ((l+r)/2)

#define QS_SWAP(type,A,D,x,y) \
{ dlink* tmp_p = A[x]; A[x] = A[y]; A[y] = tmp_p; \
  type   tmp_d = D[x]; D[x] = D[y]; D[y] = tmp_d; }

#define QS_BODY(type,func)                                   \
  int d = r-l;                                               \
  if (d <= 2)                                                \
  { if (is_smaller(D[r],D[l])) QS_SWAP(type,A,D,l,r);        \
    if (d == 2)                                              \
    { int m = l+1;                                           \
      if (is_smaller(D[m],D[l])) QS_SWAP(type,A,D,l,m)       \
      else if (is_smaller(D[r],D[m])) QS_SWAP(type,A,D,m,r); \
     }                                                       \
    return;                                                  \
   }                                                         \
  int j = QS_SELECT(l,r);                                    \
  QS_SWAP(type,A,D,l,j);                                     \
  type s = D[l];                                             \
  D[count+1] = s;                                            \
  int i = l;                                                 \
  int k = r+1;                                               \
  for(;;)                                                    \
  { while (is_smaller(D[++i],s));                            \
    while (is_smaller(s,D[--k]));                            \
    if (i<k) QS_SWAP(type,A,D,i,k) else break;               \
   }                                                         \
  QS_SWAP(type,A,D,l,k);                                     \
  if (k > l+min_d) func(A,D,l,k-1,min_d);                    \
  if (r > k+min_d) func(A,D,k+1,r,min_d);                    \
 

void dlist::gen_quick_sort(dlink** A, GenPtr* D, int l, int r, int min_d)
{ QS_BODY(GenPtr,gen_quick_sort) }

void dlist::int_quick_sort(dlink** A, int* D, int l, int r, int min_d)
{ QS_BODY(int,int_quick_sort) }

void dlist::float_quick_sort(dlink** A, float* D, int l, int r, int min_d)
{ QS_BODY(float,float_quick_sort) }

void dlist::double_quick_sort(dlink** A, double* D, int l, int r, int min_d)
{ QS_BODY(double,double_quick_sort) }



        
void dlist::gen_insertion_sort(dlink** l, dlink** r, dlink** min_stop)
{
  dlink** min=l;
  dlink** run;
  dlink** p;
  dlink** q;

  GenPtr e_min = (*min)->e;

  for (run = l+1; run <= min_stop; run++)
  { GenPtr e_run = (*run)->e;
    if (cmp(e_run,e_min) < 0) 
    { min = run;
      e_min = e_run;
     }
   }

  SWAP(min,l);

  if (r == l+1) return; 

  for(run=l+2; run <= r; run++)
  { GenPtr e_run = (*run)->e;
    min = run-1; 
    while (cmp(e_run,(*min)->e) < 0) min--;
    min++;
    if (run != min) 
    { dlink* save = *run;
      for(p=run, q = run-1; p > min; p--,q--) *p = *q;
      *min = save;
     }
   }
}


void dlist::int_insertion_sort(dlink** l, dlink** r, dlink** min_stop)
{ dlink** min=l;
  dlink** run;
  dlink** p;
  dlink** q;

  for (run = l+1; run <= min_stop; run++)
   if (LEDA_ACCESS(int,(*run)->e) < LEDA_ACCESS(int,(*min)->e)) min = run;

  SWAP(min,l);

  if (r == l+1) return; 

  for(run=l+2; run <= r; run++)
  { min=run-1;
    while (LEDA_ACCESS(int,(*run)->e) < LEDA_ACCESS(int,(*min)->e)) min--;
    min++;
    if (run != min) 
    { dlink* save = *run;
      for(p=run, q = run-1; p > min; p--,q--) *p = *q;
      *min = save;
     }
   }
}


void dlist::double_insertion_sort(dlink** l, dlink** r, dlink** min_stop)
{ dlink** min=l;
  dlink** run;
  dlink** p;
  dlink** q;

  double d_min = LEDA_ACCESS(double,(*min)->e);

  for (run = l+1; run <= min_stop; run++)
  { double d_run = LEDA_ACCESS(double,(*run)->e); 
    if (d_run < d_min) 
    { min = run;
      d_min = d_run;
     }
   }

  SWAP(min,l);

  if (r == l+1) return; 

  for(run=l+2; run <= r; run++)
  { double d_run = LEDA_ACCESS(double,(*run)->e); 
    min=run-1;
    while (d_run < LEDA_ACCESS(double,(*min)->e)) min--;
    min++;
    if (run != min) 
    { dlink* save = *run;
      for(p=run, q = run-1; p > min; p--,q--) *p = *q;
      *min = save;
     }
   }
}

  


dlist& dlist::operator=(const dlist& x)
{ dlink* p;

  clear();

  for (p = x.h; p; p = p->succ) append(p->e); 

  int type_id = el_type_id();
  if (type_id != INT_TYPE_ID && type_id != PTR_TYPE_ID)
    for (p = h; p; p = p->succ) copy_el(p->e);
                                
  return *this;
}


dlist dlist::operator+(const dlist& x)  // concatenation
{ dlist y = x;
  dlink* p = t;
  while (p) { y.push(p->e);    
              x.copy_el(p->e);
              p = p->pred;}
  return y;
}


void dlist::clear()
{ if (h==nil) return;

  int type_id = el_type_id();

  if (type_id != INT_TYPE_ID && type_id != PTR_TYPE_ID)
    for(dlink* p = h; p; p = p->succ) clear_el(p->e);

  std_memory.deallocate_list(h,t,sizeof(dlink));
  iterator=h=t=nil;
  count=0;
}

void dlist::print(ostream& out, string s, char space) const
{ list_item l = h;
  cout << s;
  if (l)
  { print_el(l->e,out); 
    l = l->succ;
    while (l)
      { out << string(space);
        print_el(l->e,out); 
        l = l->succ;
       }
  }
  out.flush();
}


void dlist::read(istream& in, string s, int delim)
{ char c;
  GenPtr x;
  cout << s;
  clear();
  if (delim == EOF)
     for(;;)
     { while (in.get(c) && isspace(c));
       if (!in) break;
       in.putback(c);
       read_el(x,in); 
       append(x);
      }
  else
     for(;;)
     { while (in.get(c) && isspace(c) && c!=delim);
       if (!in || c==delim) break;
       in.putback(c);
       read_el(x,in); 
       append(x);
      }
}
