/*******************************************************************************
+
+  LEDA 3.5
+
+  node_set.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_SET_H
#define LEDA_NODE_SET_H

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


//------------------------------------------------------------------------------
// node_set  
//------------------------------------------------------------------------------

#include <LEDA/graph.h>

/*{\Manpage {node_set} {} {Sets of Nodes} }*/

class node_set 
{
/*{\Mdefinition
An instance $S$ of the data type $node\_set$ is a subset of
the nodes of a graph $G$. $S$ is said to be valid for the nodes
of $G$.}*/

  graph* g;
  list<node> L;
  node_array<list_item> A;

public:


/*{\Mcreation S }*/

node_set(const graph& G) : A(G,nil) { g = (graph*)&G; }
/*{\Mcreate creates an instance $S$ of type $node\_set$ valid for all 
            nodes currently contained in graph $G$ and initializes it 
            to the empty set.}*/

node_set(const node_set& S) : g(S.g), L(S.L), A(S.A)
{ list_item it;
  forall_items(it,L) A[L[it]] = it; 
 }

node_set& operator=(const node_set& S)
{ g = S.g;
  L = S.L;
  A.init(*g,nil);
  list_item it;
  forall_items(it,L) A[L[it]] = it; 
  return *this;
}

~node_set() {}


/*{\Moperations 1.3 4 }*/

void insert(node x)  { if (A[x] == nil) A[x] = L.append(x); }
/*{\Mop       adds node $x$ to $S$. }*/

void del(node x)     { if (A[x] != nil) { L.del(A[x]); A[x] = nil;} }
/*{\Mop       removes node $x$ from $S$. }*/

bool member(node x)  { return (A[x] != nil); }
/*{\Mop      returns true if $x$ in $S$, false otherwise. }*/

node choose()  const { return L.head(); }
/*{\Mop      returns a node of $S$. }*/

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

bool empty()   const { return L.empty(); }
/*{\Mop      returns true iff $S$ is the empty set. }*/

void clear()         { L.clear(); A.init(*g,nil); }
/*{\Mop      makes $S$ the empty set. }*/

};

/*{\Mimplementation
A node set $S$ for a graph $G$ is implemented by a combination of a 
list  $L$ of nodes and a node array of list\_items 
associating with each node its position in $L$. All operations 
take constant time, except for clear which takes time $O(|S|)$. The space 
requirement is $O(n)$, where $n$ is the number of nodes of $G$.}*/


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

#endif
