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

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


//------------------------------------------------------------------------------
// set             
//------------------------------------------------------------------------------

#include <LEDA/basic.h>
#include <LEDA/impl/rs_tree.h>


/*{\Manpage {set} {E} {Sets}}*/

template<class E>

class set : private rs_tree {

/*{\Mdefinition
An instance $S$ of the parameterized data type |\Mname| is a collection of
elements of the linearly ordered type $E$, called the element type of $S$. The
size of $S$ is the number of elements in $S$, a set of size zero is called the
empty set.}*/

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

int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(E,x,y); }
void clear_key(GenPtr& x)    const { LEDA_CLEAR(E,x); }
void copy_key(GenPtr& x)     const { LEDA_COPY(E,x); }
void print_key(GenPtr x)     const { LEDA_PRINT(E,x,cout); }

public:

/*{\Mcreation S }*/

 set() {}
/*{\Mcreate creates an instance |\Mvar| of type |\Mname| and initializes it to 
            the empty set.}*/

 set(const set<E>& S) : rs_tree(S) {}
~set() { clear(); }
 set<E>& operator=(const set<E>& S) 
 { rs_tree::operator=(S); return *this;}


/*{\Moperations 1.8 5}*/

virtual void insert(const E& x) { rs_tree::insert(leda_cast(x),0); }
/*{\Mop        adds $x$ to |\Mvar|.}*/

virtual void del(const E& x) { rs_tree::del(leda_cast(x)); }
/*{\Mop        deletes $x$ from |\Mvar|.}*/

virtual bool member(const E& x) const 
{ return rs_tree::lookup(leda_cast(x))!=nil; }
/*{\Mop        returns true if $x$ in |\Mvar|, false otherwise.}*/

virtual E choose() const 
{ return LEDA_ACCESS(E,rs_tree::key(rs_tree::min())); }
/*{\Mop        returns an element of |\Mvar|.\\
               \precond |\Mvar| is not empty.}*/


virtual set<E> join(const set<E>& T) const
{ set<E> tmp = *this;
  tmp.rs_tree::add(T); 
  return tmp;
}

/*{\Mop    returns |\Mvar| $\cup$ |T|. }*/

virtual set<E> diff(const set<E>& T) const
{ set<E> tmp = *this;
  tmp.rs_tree::subtract(T); 
  return tmp;
}
/*{\Mop    returns |\Mvar| $-$ |T|. }*/


virtual set<E> intersect(const set<E>& T) const 
{ set<E> tmp = *this;
  tmp.rs_tree::intersect_with(T); 
  return tmp;
}
/*{\Mop    returns |\Mvar| $\cap$ |T|. }*/

virtual set<E> symdiff(const set<E>& T) const 
{ set<E> tmp = join(T);
  tmp.subtract(intersect(T));
  return tmp;
}
/*{\Mop    returns the symetric difference of |\Mvar| and |T|. }*/




virtual set<E>  operator+(const set<E>& T) const { return join(T); }
/*{\Mbinop    returns |\Mvar.join(T)|. }*/

virtual set<E>  operator-(const set<E>& T) const { return diff(T); }
/*{\Mbinop    returns |\Mvar.diff(T)|. }*/

virtual set<E>  operator&(const set<E>& T) const { return intersect(T); }
/*{\Mbinop    returns |\Mvar.intersect(T)|. }*/

virtual set<E>  operator%(const set<E>& T) const { return symdiff(T); }
/*{\Mbinop    returns |\Mvar.symdiff(T)|. }*/


virtual set<E>& operator+=(const set<E>& T) 
{ rs_tree::add(T); return *this;}
/*{\Mbinop    assigns |\Mvar.join(T)| to |\Mvar| and returns |\Mvar|. }*/

virtual set<E>& operator-=(const set<E>& T) 
{ rs_tree::subtract(T); return *this;}
/*{\Mbinop    assigns |\Mvar.diff(T)| to |\Mvar| and returns |\Mvar|. }*/

virtual set<E>& operator&=(const set<E>& T) 
{ rs_tree::intersect_with(T); return *this;}
/*{\Mbinop    assigns |\Mvar.intersect(T)| to |\Mvar| and returns |\Mvar|. }*/

virtual set<E>& operator%=(const set<E>& T) 
{ set<E> tmp = *this;
  rs_tree::add(T);
  tmp.intersect_with(T);
  subtract(tmp);
  return *this;
}
/*{\Mbinop    assigns |\Mvar.symdiff(T)| to |\Mvar| and returns |\Mvar|. }*/



virtual bool operator<=(const set<E>& T) const 
{ return T.rs_tree::contains(*this); }
/*{\Mbinop    returns true if $\Mvar \subseteq T$, false otherwise. }*/

virtual bool operator>=(const set<E>& T) const 
{ return rs_tree::contains(T); }
/*{\Mbinop    returns true if $T \subseteq \Mvar$, false otherwise. }*/

virtual bool operator==(const set<E>& T) const 
{ return rs_tree::size() == T.rs_tree::size() && rs_tree::contains(T); }
/*{\Mbinop    returns true if $\Mvar = T$, false otherwise. }*/

virtual bool operator!=(const set<E>& T) const 
{ return rs_tree::size() != T.rs_tree::size() ||  !rs_tree::contains(T); }
/*{\Mbinop    returns true if $\Mvar \not= T$, false otherwise. }*/

virtual bool operator<(const set<E>& T) const 
{ return rs_tree::size() < T.rs_tree::size() &&  T.rs_tree::contains(*this); }
/*{\Mbinop    returns true if $\Mvar \subset T$, false otherwise. }*/

virtual bool operator>(const set<E>& T) const 
{ return rs_tree::size() > T.rs_tree::size() &&  rs_tree::contains(T); }
/*{\Mbinop    returns true if $T \subset \Mvar$, false otherwise. }*/





virtual bool empty() const {return rs_tree::empty();}
/*{\Mop        returns true if |\Mvar| is empty, false otherwise.}*/

virtual int size() const {return rs_tree::size();}
/*{\Mop        returns the size of |\Mvar|.}*/

virtual void clear() { rs_tree::clear(); }
/*{\Mop        makes |\Mvar| the empty set.}*/


// iteration

virtual GenPtr first_item()  const { return rs_tree::first_item(); }

virtual void loop_to_succ(GenPtr& x) const 
{ x=rs_tree::next_item(rs_tree_item(x)); }

virtual GenPtr forall_loop_test(GenPtr it, E& y) const
{ if (it) y = LEDA_ACCESS(E,rs_tree::key(rs_tree_item(it)));
  return it;
 }


/*{\Mtext
\bigskip
{\bf Iteration}

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


friend ostream& operator<<(ostream& out, const set<E>&) { return out; }
friend istream& operator>>(istream& in, set<E>&) { return in; }

};

/*{\Mimplementation
Sets are implemented by randomized search trees \cite{AS89}. Operations insert,
del, member take time $O(\log n)$, empty, size take time $O(1)$, and clear 
takes time $O(n)$, where $n$ is the current size of the set.}*/


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

#endif

