/*******************************************************************************
+
+  LEDA 3.5
+
+  node_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_NODE_LIST_H
#define LEDA_NODE_LIST_H

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


//------------------------------------------------------------------------------
// node_list
//
// S. Naeher (1995)
//------------------------------------------------------------------------------

#include <LEDA/graph.h>

/*{\Manpage {node_list} {} {Lists of Nodes} }*/


class node_list : public c_obj_list {

/*{\Mdefinition
An instance of the data type |\Mname| is a doubly linked list of nodes. It
is implemented more efficiently than the general list type $list\<node\>$ 
(\ref{Linear Lists}). However, it can only be used with the 
restriction that every node is contained in at most one |\Mname|.  }*/


// private copy constructor (node_list's cannot be copied)

  node_list(const node_list& ) {}

public:

/*{\Mcreation L }*/

  node_list() {};
/*{\Mcreate    introduces a variable |\Mvar| of type |\Mname| and initializes
               it with the empty list. }*/


/*{\Moperations 2 4.5 }*/

  static void del_node(node v) { v->del_item(); }

  void append(node v) { c_obj_list::append(v); }
/*{\Mop   appends $v$ to list |\Mvar|. }*/

  void push(node v)   { c_obj_list::push(v); }
/*{\Mop   adds $v$ at the front of |\Mvar|. }*/

  void insert(node v, node w) { c_obj_list::insert(v,w); }
/*{\Mop   inserts $v$ after $w$ into |\Mvar|.\\
          \precond $w \in L$. }*/


  node pop()  { return node(c_obj_list::pop()); }
/*{\Mop   deletes the first node from |\Mvar| and returns it.\\
          \precond |\Mvar| is not empty. }*/

  void del(node v) { c_obj_list::del(v); }
/*{\Mop   deletes $v$ from |\Mvar|.\\
          \precond $v \in L$. }*/

  bool member(node v) const { return v->succ_link != nil; }
/*{\Mop    returns true if $v \in L$ and false otherwise. }*/

  bool operator()(node v) const { return member(v); }
/*{\Mfunop    returns true if $v \in L$ and false otherwise. }*/

/*{\Moptions nextwarning=no}*/
  node head() const { return node(c_obj_list::first()); }
  node first()const { return node(c_obj_list::first()); }
/*{\Mop    returns the first node in |\Mvar| (nil if |\Mvar| is empty).}*/

/*{\Moptions nextwarning=no}*/
  node tail() const { return node(c_obj_list::last());  }
  node last() const { return node(c_obj_list::last());  }
/*{\Mop    returns the last node in |\Mvar| (nil if |\Mvar| is empty).}*/


  node succ(node v) const { return node(c_obj_list::succ(v)); }
/*{\Mop    returns the successor of $v$ in |\Mvar|.\\ 
           \precond $v \in L$. }*/

  node pred(node v) const { return node(c_obj_list::pred(v)); }
/*{\Mop    returns the predecessor of $v$ in |\Mvar|.\\ 
           \precond $v \in L$. }*/

  node cyclic_succ(node v) const { return node(c_obj_list::cyclic_succ(v)); }
/*{\Mop    returns the cyclic successor of $v$ in |\Mvar|.\\ 
           \precond $v \in L$. }*/

  node cyclic_pred(node v) const { return node(c_obj_list::cyclic_pred(v)); }
/*{\Mop    returns the cyclic predecessor of $v$ in |\Mvar|.\\ 
           \precond $v \in L$. }*/

  bool empty() const { return c_obj_list::empty(); }
/*{\Mop    returns |true| is |\Mvar| is empty and |false| otherwise. }*/

// iteration

  node first_item() const { return first(); }
  node last_item()  const { return last(); }

  void loop_to_succ(GenPtr& x) const { x = succ(node(x)); }
  void loop_to_pred(GenPtr& x) const { x = pred(node(x)); }

  GenPtr forall_loop_test(GenPtr x, node& v) const { return v = node(x); }

};

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



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

#endif
