/*******************************************************************************
+
+  LEDA 3.5
+
+  node_slist.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_SLIST_H
#define LEDA_NODE_SLIST_H

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


//------------------------------------------------------------------------------
// node_slist
//------------------------------------------------------------------------------

#include <LEDA/graph.h>

/*{\Manpage {node_slist} {} {Singly Linked Lists of Nodes} }*/


class node_slist {

node_array<node> succ_node;
node first_node;
node last_node;

/*{\Mdefinition
An instance of the data type |\Mname| is a singly 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_slist's cannot be copied)

  node_slist(const node_slist& ) {}

public:

/*{\Mcreation L }*/

  node_slist(const graph& G) : succ_node(G,nil) 
  { first_node = last_node = nil; }
/*{\Mcreate    introduces a variable |\Mvar| of type |\Mname| and initializes
               it with the empty list. }*/


/*{\Moperations 2 4.5 }*/

  bool empty()  { return first_node == nil; }
/*{\Mop   returns true iff |\Mvar| is empty. }*/

  void insert(node v, node w) 
  { if (w == last_node) 
      append(v);
    else
     { succ_node[v] = succ_node[w];
       succ_node[w] = v;
      }
   }
/*{\Mop   inserts $v$ after $w$ into |\Mvar|.\\
          \precond $w \in L$. }*/


  void append(node v) 
  { if (last_node == nil) 
        first_node = last_node = succ_node[v] = v;
    else
     { succ_node[last_node] = succ_node[v] = v;
       last_node = v;
      }
   }
/*{\Mop   appends $v$ to list |\Mvar|. }*/


  void push(node v)  
  { if (first_node == nil)
      first_node = last_node = succ_node[v] = v;
    else
     { succ_node[v] = first_node;
       first_node = v;
      }
   }
/*{\Mop   adds $v$ at the front of |\Mvar|. }*/


  node pop()  
  { node v = first_node;
    first_node = succ_node[v];
    if (first_node == v) first_node = last_node = nil;
    succ_node[v] = nil;
    return v;
   }
/*{\Mop   deletes the first node from |\Mvar| and returns it.\\
          \precond |\Mvar| is not empty. }*/


  GenPtr member(node v) const { return succ_node[v]; }
/*{\Mop    returns true if $v \in L$ and false otherwise. }*/

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

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

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


  node succ(node v) const 
  { node w = succ_node[v]; 
    return (v == w) ? nil : w;
  }
/*{\Mop    returns the successor of $v$ in |\Mvar|.\\ 
           \precond $v \in L$. }*/



// iteration

  node first_item() const { return first(); }
  node last_item()  const { return last(); }
  void loop_to_succ(GenPtr& x) const { x = succ(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 == 350086
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif
