| /* Abstract ordered set data type as a C++ class. |
| Copyright (C) 2006-2020 Free Software Foundation, Inc. |
| Written by Bruno Haible <bruno@clisp.org>, 2006. |
| |
| This program is free software: you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3 of the License, or |
| (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
| |
| #ifndef _GL_OSET_HH |
| #define _GL_OSET_HH |
| |
| #include "gl_oset.h" |
| #include "gl_xoset.h" |
| |
| /* gl_OSet is a C++ wrapper around the gl_oset data type. |
| Its element type is 'ELTYPE *'. |
| |
| It is merely a pointer, not a smart pointer. In other words: |
| it does NOT do reference-counting, and the destructor does nothing. */ |
| |
| template <class T> class gl_OSet; |
| |
| template <class ELTYPE> |
| class gl_OSet<ELTYPE *> |
| { |
| public: |
| // ------------------------------ Constructors ------------------------------ |
| |
| gl_OSet () |
| : _ptr (NULL) |
| {} |
| |
| /* Creates an empty set. |
| IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET. |
| COMPAR_FN is an element comparison function or NULL. |
| DISPOSE_FN is an element disposal function or NULL. */ |
| gl_OSet (gl_oset_implementation_t implementation, |
| int (*compar_fn) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/), |
| void (*dispose_fn) (ELTYPE *)) |
| : _ptr (gl_oset_create_empty (implementation, |
| reinterpret_cast<gl_setelement_compar_fn>(compar_fn), |
| reinterpret_cast<gl_setelement_dispose_fn>(dispose_fn))) |
| {} |
| |
| /* Copy constructor. */ |
| gl_OSet (const gl_OSet& x) |
| { _ptr = x._ptr; } |
| |
| /* Assignment operator. */ |
| gl_OSet& operator= (const gl_OSet& x) |
| { _ptr = x._ptr; return *this; } |
| |
| // ------------------------------- Destructor ------------------------------- |
| |
| ~gl_OSet () |
| { _ptr = NULL; } |
| |
| // ----------------------- Read-only member functions ----------------------- |
| |
| /* Returns the current number of elements in the ordered set. */ |
| size_t size () const |
| { return gl_oset_size (_ptr); } |
| |
| /* Searches whether an element is already in the ordered set. |
| Returns true if found, or false if not present in the set. */ |
| bool search (ELTYPE * elt) const |
| { return gl_oset_search (_ptr, elt); } |
| |
| /* Searches the least element in the ordered set that compares greater or equal |
| to the given THRESHOLD. The representation of the THRESHOLD is defined |
| by the THRESHOLD_FN. |
| Returns true and store the found element in ELT if found, otherwise returns |
| false. */ |
| bool search_atleast (bool (*threshold_fn) (ELTYPE * /*elt*/, ELTYPE * /*threshold*/), |
| ELTYPE * threshold, |
| ELTYPE *& elt) const |
| { return gl_oset_search_atleast (_ptr, reinterpret_cast<gl_setelement_threshold_fn>(threshold_fn), threshold, &elt); } |
| |
| // ----------------------- Modifying member functions ----------------------- |
| |
| /* Adds an element to the ordered set. |
| Returns true if it was not already in the set and added, false otherwise. */ |
| bool add (ELTYPE * elt) |
| { return gl_oset_add (_ptr, elt); } |
| |
| /* Removes an element from the ordered set. |
| Returns true if it was found and removed. */ |
| bool remove (ELTYPE * elt) |
| { return gl_oset_remove (_ptr, elt); } |
| |
| /* Frees the entire ordered set. |
| (But this call does not free the elements of the set. It only invokes |
| the DISPOSE_FN on each of the elements of the set.) */ |
| void free () |
| { gl_oset_free (_ptr); } |
| |
| // ------------------------------ Private stuff ------------------------------ |
| |
| private: |
| gl_oset_t _ptr; |
| |
| public: |
| // -------------------------------- Iterators -------------------------------- |
| // Only a forward iterator. |
| // Does not implement the STL operations (++, *, and != .end()), but a simpler |
| // interface that needs only one virtual function call per iteration instead |
| // of three. |
| |
| class iterator { |
| public: |
| |
| /* If there is a next element, stores the next element in ELT, advances the |
| iterator and returns true. Otherwise, returns false. */ |
| bool next (ELTYPE *& elt) |
| { return gl_oset_iterator_next (&_state, reinterpret_cast<const void **>(&elt)); } |
| |
| ~iterator () |
| { gl_oset_iterator_free (&_state); } |
| |
| #if defined __xlC__ || defined __HP_aCC || defined __SUNPRO_CC |
| public: |
| #else |
| private: |
| friend iterator gl_OSet::begin (); |
| #endif |
| |
| iterator (gl_oset_t ptr) |
| : _state (gl_oset_iterator (ptr)) |
| {} |
| |
| private: |
| |
| gl_oset_iterator_t _state; |
| }; |
| |
| /* Creates an iterator traversing the ordered set. |
| The set's contents must not be modified while the iterator is in use, |
| except for removing the last returned element. */ |
| iterator begin () |
| { return iterator (_ptr); } |
| }; |
| |
| #endif /* _GL_OSET_HH */ |