1 /* Abstract ordered set data type as a C++ class. 2 Copyright (C) 2006-2021 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 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 */