lib/gl_oset.hh

   1 /* Abstract ordered set data type as a C++ class.
   2    Copyright (C) 2006-2020 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #ifndef _GL_OSET_HH
  19 #define _GL_OSET_HH
  20
  21 #include "gl_oset.h"
  22 #include "gl_xoset.h"
  23
  24 /* gl_OSet is a C++ wrapper around the gl_oset data type.
  25    Its element type is 'ELTYPE *'.
  26
  27    It is merely a pointer, not a smart pointer. In other words:
  28    it does NOT do reference-counting, and the destructor does nothing.  */
  29
  30 template <class T> class gl_OSet;
  31
  32 template <class ELTYPE>
  33 class gl_OSet<ELTYPE *>
  34 {
  35 public:
  36   // ------------------------------ Constructors ------------------------------
  37
  38   gl_OSet ()
  39     : _ptr (NULL)
  40     {}
  41
  42   /* Creates an empty set.
  43      IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
  44      COMPAR_FN is an element comparison function or NULL.
  45      DISPOSE_FN is an element disposal function or NULL.  */
  46   gl_OSet (gl_oset_implementation_t implementation,
  47            int (*compar_fn) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
  48            void (*dispose_fn) (ELTYPE *))
  49     : _ptr (gl_oset_create_empty (implementation,
  50                                   reinterpret_cast<gl_setelement_compar_fn>(compar_fn),
  51                                   reinterpret_cast<gl_setelement_dispose_fn>(dispose_fn)))
  52     {}
  53
  54   /* Copy constructor.  */
  55   gl_OSet (const gl_OSet& x)
  56     { _ptr = x._ptr; }
  57
  58   /* Assignment operator.  */
  59   gl_OSet& operator= (const gl_OSet& x)
  60     { _ptr = x._ptr; return *this; }
  61
  62   // ------------------------------- Destructor -------------------------------
  63
  64   ~gl_OSet ()
  65     { _ptr = NULL; }
  66
  67   // ----------------------- Read-only member functions -----------------------
  68
  69   /* Returns the current number of elements in the ordered set.  */
  70   size_t size () const
  71     { return gl_oset_size (_ptr); }
  72
  73   /* Searches whether an element is already in the ordered set.
  74      Returns true if found, or false if not present in the set.  */
  75   bool search (ELTYPE * elt) const
  76     { return gl_oset_search (_ptr, elt); }
  77
  78   /* Searches the least element in the ordered set that compares greater or equal
  79      to the given THRESHOLD.  The representation of the THRESHOLD is defined
  80      by the THRESHOLD_FN.
  81      Returns true and store the found element in ELT if found, otherwise returns
  82      false.  */
  83   template <typename THT>
  84   bool search_atleast (bool (*threshold_fn) (ELTYPE * /*elt*/, THT * /*threshold*/),
  85                        THT * threshold,
  86                        ELTYPE *& elt) const
  87   { return gl_oset_search_atleast (_ptr, reinterpret_cast<gl_setelement_threshold_fn>(threshold_fn), threshold, &elt); }
  88
  89   // ----------------------- Modifying member functions -----------------------
  90
  91   /* Adds an element to the ordered set.
  92      Returns true if it was not already in the set and added, false otherwise.  */
  93   bool add (ELTYPE * elt)
  94     { return gl_oset_add (_ptr, elt); }
  95
  96   /* Removes an element from the ordered set.
  97      Returns true if it was found and removed.  */
  98   bool remove (ELTYPE * elt)
  99     { return gl_oset_remove (_ptr, elt); }
 100
 101   /* Invokes ACTION (ELT, ACTION_DATA) and updates the ordered set if,
 102      during this invocation, the attributes/properties of the element ELT change
 103      in a way that influences the comparison function.
 104      Warning: During the invocation of ACTION, the ordered set is inconsistent
 105      and must not be accessed!
 106      Returns 1 if the position of the element in the ordered set has changed as
 107      a consequence, 0 if the element stayed at the same position, or -1 if it
 108      collided with another element and was therefore removed.  */
 109   template <typename DT>
 110   int update (ELTYPE * elt,
 111               void (*action) (ELTYPE * /*elt*/, DT * /*action_data*/),
 112               DT *action_data)
 113     {
 114       return gl_oset_update (_ptr, elt,
 115                              reinterpret_cast<void (*) (const void *, void *)> (action),
 116                              action_data);
 117     }
 118
 119   /* Frees the entire ordered set.
 120      (But this call does not free the elements of the set.  It only invokes
 121      the DISPOSE_FN on each of the elements of the set.)  */
 122   void free ()
 123     { gl_oset_free (_ptr); }
 124
 125   // ------------------------------ Private stuff ------------------------------
 126
 127 private:
 128   gl_oset_t _ptr;
 129
 130 public:
 131   // -------------------------------- Iterators --------------------------------
 132   // Only a forward iterator.
 133   // Does not implement the STL operations (++, *, and != .end()), but a simpler
 134   // interface that needs only one virtual function call per iteration instead
 135   // of three.
 136
 137   class iterator {
 138   public:
 139
 140     /* If there is a next element, stores the next element in ELT, advances the
 141        iterator and returns true.  Otherwise, returns false.  */
 142     bool next (ELTYPE *& elt)
 143       {
 144         const void *next_elt;
 145         bool has_next = gl_oset_iterator_next (&_state, &next_elt);
 146         if (has_next)
 147           elt = static_cast<ELTYPE *>(next_elt);
 148         return has_next;
 149       }
 150
 151     ~iterator ()
 152       { gl_oset_iterator_free (&_state); }
 153
 154   #if defined __xlC__ || defined __HP_aCC || defined __SUNPRO_CC
 155   public:
 156   #else
 157   private:
 158     friend iterator gl_OSet::begin ();
 159     template <typename THT>
 160     friend iterator gl_OSet::begin_atleast (bool (*) (ELTYPE *, THT *), THT *);
 161   #endif
 162
 163     iterator (gl_oset_t ptr)
 164       : _state (gl_oset_iterator (ptr))
 165       {}
 166
 167     template <typename THT>
 168     iterator (gl_oset_t ptr,
 169               bool (*threshold_fn) (ELTYPE * /*elt*/, THT * /*threshold*/),
 170               THT * threshold)
 171       : _state (gl_oset_iterator_atleast (ptr, reinterpret_cast<gl_setelement_threshold_fn>(threshold_fn), threshold))
 172       {}
 173
 174   private:
 175
 176     gl_oset_iterator_t _state;
 177   };
 178
 179   /* Creates an iterator traversing the ordered set.
 180      The set's contents must not be modified while the iterator is in use,
 181      except for removing the last returned element.  */
 182   iterator begin ()
 183     { return iterator (_ptr); }
 184
 185   /* Creates an iterator traversing the tail of an ordered set, that comprises
 186      the elements that compare greater or equal to the given THRESHOLD.  The
 187      representation of the THRESHOLD is defined by the THRESHOLD_FN.
 188      The set's contents must not be modified while the iterator is in use,
 189      except for removing the last returned element.  */
 190   template <typename THT>
 191   iterator begin_atleast (bool (*threshold_fn) (ELTYPE * /*elt*/, THT * /*threshold*/),
 192                           THT * threshold)
 193     { return iterator (_ptr, threshold_fn, threshold); }
 194 };
 195
 196 #endif /* _GL_OSET_HH */