lib/gl_oset.hh

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