/*******************************************************************************
+
+  LEDA 7.2.2  
+
+
+  node_set.h
+
+
+  Copyright (c) 1995-2025
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/


#ifndef LEDA_NODE_SET_H
#define LEDA_NODE_SET_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 722189
#include <LEDA/internal/PREAMBLE.h>
#endif


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

#include <LEDA/graph/graph.h>

LEDA_BEGIN_NAMESPACE

/*{\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_map<list_item> A;

public:

typedef list_item item;


/*{\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) const  { 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()         
{ node v;
  forall(v,L) A[v] = nil;
  L.clear(); 
 }
/*{\Mop      makes $S$ the empty set. }*/


// iteration

item first_item()       const { return L.first(); }
item last_item()        const { return L.last(); }
item next_item(item it) const { return it ? L.succ(it) : 0; }
node inf(item it)       const { return L[it]; } 

};

/*{\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 == 722189
#undef LEDA_ROOT_INCL_ID
#include <LEDA/internal/POSTAMBLE.h>
#endif


LEDA_END_NAMESPACE

#endif
