Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
set.h
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 3k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

set.h：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  set.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_SET_H
  14. #define LEDA_SET_H
  16. //------------------------------------------------------------------------------
  17. // set             
  18. //------------------------------------------------------------------------------
  20. #include <LEDA/basic.h>
  21. #include <LEDA/impl/rs_tree.h>
  24. /*{Manpage {set} {E} {Sets}}*/
  26. template<class E>
  28. class set : private rs_tree {
  30. /*{Mdefinition
  31. An instance $S$ of the parameterized data type name is a collection of
  32. elements of the linearly ordered type $E$, called the element type of $S$. The
  33. size of $S$ is the number of elements in $S$, a set of size zero is called the
  34. empty set.}*/
  36. int  int_type()              const { return LEDA_INT_TYPE(E); }
  37. int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(E,x,y); }
  38. void clear_key(GenPtr& x)    const { LEDA_CLEAR(E,x); }
  39. void copy_key(GenPtr& x)     const { LEDA_COPY(E,x); }
  41. public:
  43. /*{Mcreation S }*/
  45.  set() {}
  46. /*{Mcreate creates an instance var of type name and initializes it to 
  47.             the empty set.}*/
  49.  set(const set<E>& S) : rs_tree(S) {}
  50. ~set() { clear(); }
  51.  set<E>& operator=(const set<E>& S) 
  52.  { rs_tree::operator=(S); return *this;}
  55. /*{Moperations 1.8 5}*/
  57. virtual void insert(E x) { rs_tree::insert(Convert(x),0); }
  58. /*{Mop        adds $x$ to var.}*/
  60. virtual void del(E x) { rs_tree::del(Convert(x)); }
  61. /*{Mop        deletes $x$ from var.}*/
  63. virtual bool member(E x) const { return (rs_tree::lookup(Convert(x))!=nil); }
  64. /*{Mop        returns true if $x$ in var, false otherwise.}*/
  66. virtual E choose() const 
  67. { return LEDA_ACCESS(E,rs_tree::key(rs_tree::min())); }
  68. /*{Mop        returns an element of var.\
  69.                precond var is not empty.}*/
  71. virtual bool empty() const {return rs_tree::empty();}
  72. /*{Mop        returns true if var is empty, false otherwise.}*/
  74. virtual int size() const {return rs_tree::size();}
  75. /*{Mop        returns the size of var.}*/
  77. virtual void clear() { rs_tree::clear(); }
  78. /*{Mop        makes var the empty set.}*/
  81. // iteration
  83. virtual GenPtr first_item()  const { return rs_tree::first_item(); }
  85. virtual void loop_to_succ(GenPtr& x) const 
  86. { x=rs_tree::next_item(rs_tree_item(x)); }
  88. virtual GenPtr forall_loop_test(GenPtr it, E& y) const
  89. { if (it) y = LEDA_ACCESS(E,rs_tree::key(rs_tree_item(it)));
  90.   return it;
  91.  }
  93. #if defined(__ELSE_SCOPE_BUG__)
  94.   GenPtr forall_loop_item;
  95.   GenPtr& Forall_Loop_Item() const { return (GenPtr&)forall_loop_item; }
  96. #endif
  99. /*{Mtext
  100. bigskip
  101. {bf Iteration}
  103. medskip
  104. {bf forall}($x,S$) 
  105. ${$  ``the elements of $S$ are successively assigned to $x$''  $}$ }*/
  108. };
  110. /*{Mimplementation
  111. Sets are implemented by randomized search trees cite{AS89}. Operations insert,
  112. del, member take time $O(log n)$, empty, size take time $O(1)$, and clear 
  113. takes time $O(n)$, where $n$ is the current size of the set.}*/
  115. #endif