include/AD/contain/treeset.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef tree_based_set_h
  26 #define tree_based_set_h
  27
  28 /////////////////////////////////////////////////////////////////////////////
  29 //  Class TreeSet<T> implements a set derived from a search tree
  30 /////////////////////////////////////////////////////////////////////////////
  31
  32 #include <AD/contain/set.h>  // Sets
  33
  34 /////////////////////////////////////////////////////////////////////////////
  35 //  Class TreeSet<T,H>
  36 /////////////////////////////////////////////////////////////////////////////
  37 template<class T, class H>
  38    class TreeSet : public Set<T> {
  39
  40       H set;   // a tree object
  41
  42    public:
  43       ///////////////////////////////////////////////////////////////////////
  44       //  Inherit types
  45       ///////////////////////////////////////////////////////////////////////
  46       typedef Set<T>         Super;
  47       typedef Super::Element Element;
  48
  49       ///////////////////////////////////////////////////////////////////////
  50       //  Constructors and destructor
  51       ///////////////////////////////////////////////////////////////////////
  52       TreeSet() {}
  53       TreeSet(const Collection<T>& C) { *this = C; }
  54       TreeSet(const TreeSet<T,H>& s)  { set = s; }
  55      ~TreeSet() {}
  56
  57       ///////////////////////////////////////////////////////////////////////
  58       // Assignment
  59       ///////////////////////////////////////////////////////////////////////
  60       // void operator = (const Collection<T>&); // inherited
  61       void operator = (const TreeSet<T,H>& S) { *this = (Collection<T>&)S; }
  62
  63       ///////////////////////////////////////////////////////////////////////
  64       //  Selectors
  65       ///////////////////////////////////////////////////////////////////////
  66       inline int  size()                const { return set.size(); }
  67       inline int  capacity()            const { return set.capacity(); }
  68       inline Bool is_empty()            const { return set.is_empty(); }
  69       inline Bool is_full()             const { return set.is_full(); }
  70       inline Bool contains (const T& e) const { return set.contains(e); }
  71       inline Ix   lookup   (const T& e) const { return set.lookup(e); }
  72
  73       ///////////////////////////////////////////////////////////////////////
  74       //  In place set operations
  75       ///////////////////////////////////////////////////////////////////////
  76       inline void clear()             { set.clear(); }             // make
  77       inline Ix   insert (const T& e) { return set.insert(e,0); }  // add an element
  78       inline Bool remove (const T& e) { return set.remove(e); }    // remove an element
  79       // void Union        (const Set& s);  // inherited
  80       // void Difference   (const Set& s);  // inherited
  81       // void Intersection (const Set& s);  // inherited
  82
  83       ///////////////////////////////////////////////////////////////////////
  84       //  Iteration
  85       ///////////////////////////////////////////////////////////////////////
  86       inline Ix       first()            const { return set.first(); }
  87       inline Ix       next(Ix i)         const { return set.next(i); }
  88       inline const T& operator () (Ix i) const { return (T&)set.key(i); }
  89       inline       T& operator () (Ix i)       { return (T&)set.key(i); }
  90
  91       ///////////////////////////////////////////////////////////////////////
  92       // Class name
  93       ///////////////////////////////////////////////////////////////////////
  94       const char * myName() const { return "TreeSet"; }
  95    };
  96
  97 #endif