/*******************************************************************************
+
+  LEDA 3.5
+
+  list.h
+
+  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.
+ 
*******************************************************************************/
#ifndef LEDA_LIST_H
#define LEDA_LIST_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350070
#include <LEDA/REDEFINE_NAMES.h>
#endif


/*{\Manpage {list} {E} {Linear Lists}}*/


#include <LEDA/impl/dlist.h>

template<class E> 

class list : public dlist 
{

typedef list_item item;

#if !defined(LEDA_COMPARE_TEMPLATE)
decl_compare_func<E> cmp_func;
#endif

/*{\Mdefinition
An instance $L$ of the parameterized data type |\Mname| is a sequence of items
($list\_item$). Each item in $L$ contains an element of data type $E$, called
the element type of $L$. The number of items in $L$ is called the length of $L$.
If $L$ has length zero it is called the empty list. In the sequel $\<x\>$ is 
used to denote a list item containing the element $x$ and $L[i]$ is used to 
denote the contents of list item $i$ in $L$.}*/


int  (*cmp_ptr)(const E&, const E&); // pointer to user supplied cmp function 
int  (*ord_ptr)(const E&);           // pointer to user supplied ord function 
void (*app_ptr)(E&);                 // pointer to user supplied apply function 

int  el_type_id() const { return LEDA_TYPE_ID(E); }


int  cmp(GenPtr x, GenPtr y) const 
{ return (*cmp_ptr)(LEDA_ACCESS(E,x),LEDA_ACCESS(E,y)); }


int  ord(GenPtr x)  const { return (*ord_ptr)(LEDA_ACCESS(E,x)); }
void app(GenPtr& x) const { (*app_ptr)(LEDA_ACCESS(E,x)); }

void clear_el(GenPtr& x)     const { LEDA_CLEAR(E,x); }
void copy_el(GenPtr& x)      const { LEDA_COPY(E,x); }
void print_el(GenPtr& x,ostream& out) const { LEDA_PRINT(E,x,out);  }
void read_el(GenPtr& x,istream& in)   const { LEDA_READ(E,x,in);    }

GenPtr buf;

public:

typedef E value_type;


/*{\Mcreation L }*/ 

list() { LEDA_CREATE(E,buf); }
/*{\Mcreate creates  an instance |\Mvar| of type |\Mname| and initializes it to 
            the empty list.}*/

list(const E& a) : dlist(leda_copy(a)) { LEDA_CREATE(E,buf); }

list(const list<E>& a) : dlist(a) { LEDA_CREATE(E,buf); }

virtual ~list() { clear(); LEDA_CLEAR(E,buf); }


/*{\Moperations 2 5 }*/

/*{\Mtext
\medskip
{\bf 3.1 Access Operations}
\medskip }*/

int length() const {return dlist::length();}
/*{\Mop      returns the length of $L$.}*/

int size() const {return dlist::size();}
/*{\Mop      returns $L$.length().}*/

bool empty() const {return dlist::empty();}
/*{\Mop      returns true if $L$ is empty, false otherwise.}*/

list_item first() const {return dlist::first();}
/*{\Mop      returns the first item of $L$ (nil if $L$ is empty).}*/

list_item last() const {return dlist::last();}
/*{\Mop      returns the last item of $L$. (nil if $L$ is empty)}*/

list_item get_item(int i) const {return dlist::get_item(i);}
/*{\Mop      returns the item at position $i$ (the first position is 0).\\
             \precond $i < L$.length().}*/

list_item succ(list_item it) const {return dlist::succ(it);}
/*{\Mop      returns the successor item of item $it$, nil if
	     $it=L$.last().\\
	     \precond $it$ is an item in $L$.}*/

list_item pred(list_item it) const {return dlist::pred(it);}
/*{\Mop      returns the predecessor item of item $it$, nil if
	     $it=L$.first().\\
	     \precond $it$ is an item in $L$.}*/

list_item cyclic_succ(list_item it) const {return dlist::cyclic_succ(it);}
/*{\Mop      returns the cyclic successor of item $it$, i.e.,
	     $L$.first() if $it = L$.last(), $L$.succ($it$) otherwise.}*/

list_item cyclic_pred(list_item it) const
{return dlist::cyclic_pred(it);}
/*{\Mop      returns the cyclic predecessor of item $it$, i.e,
             $L$.last() if $it = L$.first(), $L$.pred($it$) otherwise.}*/

list_item search(const E& x) const   
{ int (*p)(const E&, const E&) = compare; ((GenPtr&)cmp_ptr) = p;
  return dlist::search(leda_cast(x)); 
}
/*{\Mop      returns the first item of $L$ that contains $x$,
	     nil if $x$ is not an element of $L$.\\
	     \precond{compare has to be defined for type $E$.} }*/

void remove(const E& x)
{ int (*p)(const E&, const E&) = compare; ((GenPtr&)cmp_ptr) = p;
  dlist::remove(leda_cast(x)); 
}
/*{\Mop      removes all items with contents $x$ from $L$.
	     \precond{compare has to be defined for type $E$.} }*/


E contents(list_item it) const { return LEDA_ACCESS(E,dlist::contents(it)); }
/*{\Mop      returns the contents $L[it]$ of item $it$.\\
	     \precond $it$ is an item in $L$.}*/


E inf(list_item it) const { return contents(it); }
/*{\Mop      returns $L$.contents($it$).}*/


E front() const { return LEDA_ACCESS(E,dlist::head()); }
/*{\Mop      returns the first element of $L$, i.e. the contents
	     of $L$.first().\\
	     \precond $L$ is not empty.}*/

E head() const { return front(); }
/*{\Mop  see |L.front()|. }*/

E back() const { return LEDA_ACCESS(E,dlist::tail()); }
/*{\Mop      returns the last element of $L$, i.e. the contents
	     of $L$.last().\\
	     \precond $L$ is not empty.}*/

E tail() const { return back(); }
/*{\Mop  see |L.back()|. }*/


int rank(const E& x) const   
{ int (*p)(const E&, const E&) = compare;
  ((GenPtr&)cmp_ptr) = p;
  return dlist::rank(leda_cast(x)); 
}
/*{\Mop      returns the rank of $x$ in $L$, i.e. its first
	     position in $L$ as an integer from [1\dots $\Labs{L}$]
	     (0 if $x$ is not in $L$). }*/



/*{\Mtext
\medskip
{\bf 3.2 Update Operations}
\medskip }*/

list_item push(const E& x)   { return dlist::push(leda_copy(x));}
/*{\Mop      adds a new item $\<x\>$ at the front of $L$ and 
	     returns it ( $L$.insert($x,L$.first$(),before$) ).}*/

list_item push_front(const E& x) { return push(x); }
/*{\Mop   see |L.push(x)|. }*/

list_item append(const E& x) { return dlist::append(leda_copy(x));}
/*{\Mop      appends a new item $\<x\>$ to $L$ and returns
             it ( $L$.insert($x,L$.last$(),after$) ).}*/

list_item push_back(const E& x)  { return append(x);    }
/*{\Mop   see |L.append(x)|. }*/


list_item insert(const E& x, list_item pos, int dir=after)
{ return dlist::insert(leda_copy(x),pos,dir); }
/*{\Mopl     inserts a new item $\<x\>$ after (if $dir=after$)
	     or before (if $dir=before$) item $pos$ into $L$ and
	     returns it (here $after$ and $before$
	     are predefined constants).\\ 
	     \precond $it$ is an item in $L$.}*/



GenPtr forall_loop_test(GenPtr it, E& x) const
{ if (it) x = contents(list_item(it));

  return it;
 }

E  pop() 
{ LEDA_CLEAR(E,buf); buf = dlist::pop(); return LEDA_ACCESS(E,buf); } 
/*{\Mop      deletes the first item from $L$ and returns its contents.\\
	     \precond $L$ is not empty.}*/

E pop_front() { return pop(); }
/*{\Mop   see |L.pop()|. }*/

E  Pop() 
{ LEDA_CLEAR(E,buf); buf = dlist::Pop(); return LEDA_ACCESS(E,buf); } 
/*{\Mop      deletes the last item from $L$ and returns its contents.\\
	     \precond $L$ is not empty.}*/

E pop_back()  { return Pop(); }
/*{\Mop   see |L.Pop()|. }*/



void  erase(list_item it)   { dlist::del(it);  }
/*{\Mop      deletes the item $it$ from $L$.\\
	     \precond $it$ is an item in $L$.}*/


E  del_item(list_item it) 
{ LEDA_CLEAR(E,buf); buf = dlist::del(it); return LEDA_ACCESS(E,buf); } 
/*{\Mop      deletes the item $it$ from $L$ and returns its contents $L[it]$.\\
	     \precond $it$ is an item in $L$.}*/

E  del(list_item it) { return del_item(it); }
/*{\Mop      same as |\Mvar.del_iem(it)|. }*/



void  move_to_front(list_item it) { dlist::move_to_front(it); }
/*{\Mop      moves $it$ to the front end of $L$. }*/
 
/*{\Moptions nextwarning=no }*/
void  move_to_back(list_item it) { dlist::move_to_back(it); }
void  move_to_rear(list_item it) { dlist::move_to_back(it); }
/*{\Mop      moves $it$ to the rear end of $L$. }*/



void  assign(list_item it, E x) { dlist::assign(it,leda_copy(x));}
/*{\Mop      makes $x$ the contents of item $it$.\\
	     \precond $it$ is an item in $L$.}*/

void  splice(list_item pos, list<E>& L1)
{ dlist::splice(pos,(dlist&)L1); }

void  splice(list_item pos, list<E>& L1,list_item it)
{ dlist::splice(pos,(dlist&)L1,it); }

void  splice(list_item pos, list<E>& L1,list_item it1, list_item it2)
{ dlist::splice(pos,(dlist&)L1,it1,it2); }


void  conc(list<E>& L1, int dir = after) { dlist::conc((dlist&)L1,dir); }
/*{\Mop      appends ($|dir| = |after|$ or prepends (|dir| = |before|) 
             list $L_1$ to list $L$ and makes $L_1$ the empty list.\\
	     \precond: $L \ne L_1$}*/


void  swap(list<E>& L1) { dlist::swap(L1); }
/*{\Mop      swaps lists of items of $L$ and $L1$; }*/


void  split(list_item it, list<E>& L1, list<E>& L2)
                                 { dlist::split(it,(dlist&)L1,(dlist&)L2);}
/*{\Mopl     splits $L$ at item $it$ into lists $L1$ and $L2$. More precisely,
	     if $it \ne nil$ and $ L = x_1,\dots,x_{k-1},it,x_{k+1},\dots,x_n$
             then $L1 = x_1,\dots,x_{k-1}$ and $L2 = it,x_{k+1},\dots,x_n$. If
             $it = nil$ then $L1$ is made empty and $L2$ a copy of $L$. Finally
             $L$ is made empty if it is not identical to $L1$ or $L2$.\\
	     \precond $it$ is an item of $L$ or $nil$.}*/


void  split(list_item it, list<E>& L1, list<E>& L2, int dir)
                                 { dlist::split(it,(dlist&)L1,(dlist&)L2,dir);}
/*{\Mopl     splits $L$ at item $it$ into lists $L1$ and $L2$. Item $it$ 
             becomes the first item of $L2$ if $dir==0$ and the last item
             of $L1$ otherwise.\\ \precond $it$ is an item of $L$.}*/


/*{\Moptions nextwarning=no }*/
void  sort(int (*cmp)(const E&, const E&), int d) 
{ cmp_ptr = cmp; dlist::sort(d,0); }

void  sort(int (*cmp)(const E&, const E&)) { cmp_ptr = cmp; dlist::sort(1,0); }
/*{\Mopl      sorts the items of $L$ using the ordering defined
	     by the compare function $cmp : E\times E \longrightarrow int$,
	     with\\
 	     $$cmp(a,b)\ \ \cases{< 0,  &if $a < b$\cr
		                  = 0,  &if $a = b$\cr
		                  > 0,  &if $a > b$\cr}$$
	     More precisely, if $(in_1,\dots,in_n)$ and 
	     $(out_1,\dots,out_n)$ denote the values of $L$
	     before and after the call of sort, then
	     $cmp(L[out_j], L[out_{j+1}]) \le 0$ for
	     $1\le j<n$ and there is a
	     permutation
	     $\pi$ of $[1..n]$ such that $out_i = in_{\pi_i}$ for
	     $1 \le i \le n$
	     .}*/

/*{\Moptions nextwarning=no }*/
void  sort(int d) { cmp_ptr = compare; dlist::sort(d,1); }

void  sort() { cmp_ptr = compare; dlist::sort(1,1); }
/*{\Mop      sorts the items of $L$ using the default ordering of type $E$,
             i.e., the linear order defined by function 
             $int$ compare$(const\ E\&,\ const\ E\&)$. }*/


void unique() { cmp_ptr = compare; dlist::unique(1); }
/*{\Mop      removes duplicates from $L$. /precond $L$ is sorted 
             incresingly according to the default ordering of type $E$.}*/

void unique(int (*cmp)(const E&, const E&)) 
{ cmp_ptr = cmp; dlist::unique(0); }
/*{\Mop      removes duplicates from $L$. /precond $L$ is sorted 
             incresingly according to the ordering defined by $cmp$.}*/


void  merge(list<E>& L1) { cmp_ptr = compare; dlist::merge(L1,1); }
/*{\Mop      merges the items of $L$ and $L1$ using the default ordering of 
             type $E$. The result is assigned to $L$ and $L1$ is made empty.
             /precond $L$ and $L1$ are sorted incresingly according to the 
             default ordering of type $E$.}*/

void  merge(list<E>& L1, int (*cmp)(const E&, const E&)) 
{ cmp_ptr = cmp; dlist::merge(L1,0); }
/*{\Mop      merges the items of $L$ and $L1$ using the ordering 
             defined by $cmp$.}*/



list_item min(int (*cmp)(const E&, const E&)) 
                                { cmp_ptr = cmp; return dlist::min(); }
/*{\Mopl      returns the item with the minimal contents with respect
             to the linear order defined by compare function $cmp$. }*/

list_item min() { cmp_ptr = compare; return dlist::min(); }
/*{\Mop      returns the item with the minimal contents with respect
             to the default linear order of type $E$. }*/


list_item max(int (*cmp)(const E&, const E&)) 
                                { cmp_ptr = cmp; return dlist::max(); }
/*{\Mopl      returns the item with the maximal contents with respect
             to the linear order defined by compare function $cmp$. }*/

list_item max() { cmp_ptr = compare; return dlist::max(); }
/*{\Mop      returns the item with the maximal contents with respect
             to the default linear order of type $E$. }*/

void  apply(void (*f)(E& x))   { app_ptr = f; dlist::apply(); }
/*{\Mop      for all items $\<x\>$ in $L$ function $f$ is
	     called with argument $x$ (passed by reference).}*/



void reverse_items() { dlist::reverse_items(); }
/*{\Mop      reverses the sequence of items of $L$. }*/

void reverse() { dlist::reverse_items(); }
/*{\Mop      as above. }*/

void reverse_items(list_item it1, list_item it2) 
{ dlist::reverse_items(it1,it2); }
/*{\Mop      reverses the sub-sequence $it1,\dots,it2$ of items of $L$. 
             \precond  $it1 = it2$ or $it1$ appears before $it2$ in $L$. }*/

void reverse(list_item it1, list_item it2) { dlist::reverse_items(it1,it2); }
/*{\Mop      as above. }*/


void permute() {dlist::permute();}
/*{\Mop      randomly permutes the items of $L$.}*/


void  bucket_sort(int i, int j, int (*f)(const E&))
                                     { ord_ptr = f; dlist::bucket_sort(i,j); }
/*{\Mopl     sorts the items of $L$ using bucket sort,
	     where $f : E \longrightarrow int$ with $f(x) \in [i..j]$ for
	     all elements $x$ of $L$. The sort is stable,
	     i.e., if $f(x)=f(y)$ and $\<x\>$ is before $\<y\>$ in
	     $L$ then $\<x\>$ is before $\<y\>$ after the sort.}*/

void  bucket_sort(int (*f)(const E&)) { ord_ptr = f; dlist::bucket_sort(); }
/*{\Mopl     same as |bucket_sort(i,j,f)| where |i| and |j| are the
             minimal and maximal value of |f(e)| as |e| ranges over 
             all elements of |L|. }*/




void clear() {dlist::clear();}
/*{\Mop      makes $L$ the empty list. }*/

/*{\Mtext
\bigskip
{\bf 3.3 Input and Output} }*/

void read(istream& I, char delim = (char)EOF) { dlist::read(I,delim); }
/*{\Mopl     reads a sequence of objects of type $E$ terminated
	     by the delimiter $delim$ from the input stream $I$
	     using  |operator>>(istream&,E&)|.
	     $L$ is made a list of appropriate length and the
	     sequence is stored in $L$.}*/

void read(char delim = '\n') { dlist::read(delim); }
/*{\Mop      calls $L$.read($cin$, $delim$) to read $L$ from
	     the standard input stream $cin$.}*/

void read(string s,char delim = '\n') {dlist::read(s,delim);}
/*{\Mopl     As above, but uses string $s$ as a prompt.}*/

void print(ostream& O, char space = ' ') const { dlist::print(O,space); }
/*{\Mopl     prints the contents of list $L$ to the output
	     tream $O$ using |operator<<(ostream&,const E&)|
	     to print each element. The elements are separated by 
             character $space$.}*/

void print(char space = ' ') const { dlist::print(space); }
/*{\Mop      calls $L$.print($cout$, $space$) to print $L$ on
	     the standard output stream $cout$.}*/

void print(string s,char space = ' ') const { dlist::print(s,space); }
/*{\Mopl     As above, but uses string $s$ as a header.}*/


/*{\Mtext
\bigskip
{\bf 3.4 Operators} }*/

/*{\Moptions nextwarning=no }*/
list<E>& operator=(const list<E>& L1) 
{ dlist::operator=(L1); return *this;}
/*
list<E>& operator=(const list& L1) 
*/
/*{\Mbinop   The assignment operator makes $L$ a copy of
	     list $L_1$. More precisely if $L_1$ is the sequence
	     of items $x_1, x_2, \dots , x_n$ then $L$ is made a
	     sequence of items $y_1, y_2, \dots , y_n$ with
	     $L[y_i] = L_1[x_i]$ for $1 \le i \le n$.}*/


#if !defined(__sgi)
list<E>  operator+(const list<E>& a) 
{ dlist L = *(dlist*)this + *(dlist*)&a; return *(list<E>*)&L; }
#endif

list_item operator+=(const E& x)   { return append(x); }
/*{\Mbinop   appends $x$ to |\Mvar|.}*/

list_item operator[](int i) const   { return get_item(i); }
/*{\Marrop   returns the i-th item of |\Mvar|.}*/

E&  operator[](list_item it) { return LEDA_ACCESS(E,dlist::entry(it)); }
/*{\Marrop   returns a reference to the contents of $it$.}*/

const E&  operator[](list_item it) const 
{ return LEDA_CONST_ACCESS(E,dlist::entry(it)); }


friend ostream& operator<<(ostream& out, const list<E>& L) 
{ L.print(out); return out;}

friend istream& operator>>(istream& in,  list<E>& L)
{ L.read(in); return in;}


// STL iterators and operations

#if defined(__GNUC__) || (!defined(hpux) && !defined(__DECCXX) && !defined(__xlC__))

#define LEDA_STL_LIST

STL_ITERATORS(list<E>,list_item,E)

list(const E* first, const E* end)    
{ while (first != end) append(*first++); }

iterator insert(iterator pos, const E& x) 
{ return iterator(this,insert(x,pos,before)); }

void insert(iterator pos, const E* first, const E* last) 
{ while (first != last) insert(pos, *first++); }

void insert(iterator pos, const_iterator first, const_iterator last) 
{ while (first != last) insert(pos, *first++); }

void insert(iterator pos, int n, const E& x) 
{ while (n--) insert(pos, x); }

void  erase(iterator first, iterator end)  
{ while (first != end) erase(first++); }


#endif


#if defined(LEDA_OLD_ITERATION)

//------------------------------------------------------------------------------
// old iteration stuff
// will not be supported in future versions 
//------------------------------------------------------------------------------

void set_iterator(list_item it)  const { dlist::set_iterator(it); }
void init_iterator()             const { dlist::init_iterator(); }
list_item get_iterator()         const { return dlist::get_iterator(); }
list_item move_iterator(int dir) const { return dlist::move_iterator(dir); }

bool current_element(E& x) const 
{ GenPtr y; 
  bool b=dlist::current_element(y);
  if (b) x = LEDA_ACCESS(E,y); 
  return b; 
 }

bool next_element(E& x) const 
{ GenPtr y; 
  bool b = dlist::next_element(y);
  if (b) x = LEDA_ACCESS(E,y); 
  return b; 
 }

bool prev_element(E& x) const  
{ GenPtr y; 
  bool b = dlist::prev_element(y);
  if (b) x = LEDA_ACCESS(E,y); 
  return b; 
 }
#endif

}; 


/*
template <class T>
inline T* value_type(const list<T>::iterator&) { return  (*T)0; }
*/


//------------------------------------------------------------------------------
// Iteration Macros
//------------------------------------------------------------------------------


/*{\Mtext
\bigskip
{\bf 3.5 Iterations Macros}

{\bf forall\_items}($it,L$)       
$\{$ ``the items of $L$ are successively assigned to $it$'' $\}$

{\bf forall}($x,L$)       
$\{$ ``the elements of $L$ are successively assigned to $x$'' $\}$ }*/



/*{\Mimplementation
The data type list is realized by doubly linked linear lists. All operations
take constant time except for the following operations: search and rank take 
linear time $O(n)$, item($i$) takes time $O(i)$, bucket\_sort takes time 
$O(n + j - i)$ and sort takes time $O(n\cdot c\cdot\log n$) where $c$ is the 
time complexity of the compare function. $n$ is always the current length of 
the list.}*/


#if LEDA_ROOT_INCL_ID == 350070
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif

