lib/gl_list.hh

   1 /* Abstract sequential list 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_LIST_HH
  19 #define _GL_LIST_HH
  20
  21 #include "gl_list.h"
  22 #include "gl_xlist.h"
  23 #include "gl_sublist.h"
  24 #include "gl_xsublist.h"
  25
  26 /* gl_List is a C++ wrapper around the gl_list 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_List;
  33
  34 template <class ELTYPE>
  35 class gl_List<ELTYPE *>
  36 {
  37 public:
  38   // ------------------------------ Constructors ------------------------------
  39
  40   gl_List ()
  41     : _ptr (NULL)
  42     {}
  43
  44   /* Creates an empty list.
  45      IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
  46      GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
  47      GL_RBTREEHASH_LIST.
  48      EQUALS_FN is an element comparison function or NULL.
  49      HASHCODE_FN is an element hash code function or NULL.
  50      DISPOSE_FN is an element disposal function or NULL.
  51      ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
  52      the list. The implementation may verify this at runtime.  */
  53   gl_List (gl_list_implementation_t implementation,
  54            bool (*equals_fn) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
  55            size_t (*hashcode_fn) (ELTYPE *),
  56            void (*dispose_fn) (ELTYPE *),
  57            bool allow_duplicates)
  58     : _ptr (gl_list_create_empty (implementation,
  59                                   reinterpret_cast<gl_listelement_equals_fn>(equals_fn),
  60                                   reinterpret_cast<gl_listelement_hashcode_fn>(hashcode_fn),
  61                                   reinterpret_cast<gl_listelement_dispose_fn>(dispose_fn),
  62                                   allow_duplicates))
  63     {}
  64
  65   /* Creates a list with given contents.
  66      IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
  67      GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
  68      GL_RBTREEHASH_LIST.
  69      EQUALS_FN is an element comparison function or NULL.
  70      HASHCODE_FN is an element hash code function or NULL.
  71      DISPOSE_FN is an element disposal function or NULL.
  72      ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
  73      the list. The implementation may verify this at runtime.
  74      COUNT is the number of initial elements.
  75      CONTENTS[0..COUNT-1] is the initial contents.  */
  76   gl_List (gl_list_implementation_t implementation,
  77            bool (*equals_fn) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
  78            size_t (*hashcode_fn) (ELTYPE *),
  79            void (*dispose_fn) (ELTYPE *),
  80            bool allow_duplicates,
  81            size_t count, ELTYPE **contents)
  82     : _ptr (gl_list_create (implementation,
  83                             reinterpret_cast<gl_listelement_equals_fn>(equals_fn),
  84                             reinterpret_cast<gl_listelement_hashcode_fn>(hashcode_fn),
  85                             reinterpret_cast<gl_listelement_dispose_fn>(dispose_fn),
  86                             allow_duplicates,
  87                             count, contents))
  88     {}
  89
  90   /* Creates a sublist of a given list.
  91      This is the list of elements with indices i, start_index <= i < end_index.
  92      The sublist is backed by the given list, which means:
  93        - Modifications to the sublist affect the whole list.
  94        - Modifications to the whole list are immediately visible in the sublist.
  95        - The sublist is only valid as long as the whole list is valid.
  96        - The sublist must not be passed to the gl_list_sortedlist_add() function.
  97    */
  98   gl_List (const gl_List& whole_list, size_t start_index, size_t end_index)
  99     : _ptr (gl_sublist_create (whole_list._ptr, start_index, end_index))
 100     {}
 101
 102   /* Copy constructor.  */
 103   gl_List (const gl_List& x)
 104     { _ptr = x._ptr; }
 105
 106   /* Assignment operator.  */
 107   gl_List& operator= (const gl_List& x)
 108     { _ptr = x._ptr; return *this; }
 109
 110   // ------------------------------- Destructor -------------------------------
 111
 112   ~gl_List ()
 113     { _ptr = NULL; }
 114
 115   // ----------------------- Read-only member functions -----------------------
 116
 117   /* Returns the current number of elements in the list.  */
 118   size_t size () const
 119     { return gl_list_size (_ptr); }
 120
 121   /* Returns the element value represented by a list node.  */
 122   ELTYPE * node_value (gl_list_node_t node) const
 123     { return static_cast<ELTYPE *>(gl_list_node_value (_ptr, node)); }
 124
 125   /* Returns the node immediately after the given node in the list, or NULL
 126      if the given node is the last (rightmost) one in the list.  */
 127   gl_list_node_t next_node (gl_list_node_t node) const
 128     { return gl_list_next_node (_ptr, node); }
 129
 130   /* Returns the node immediately before the given node in the list, or NULL
 131      if the given node is the first (leftmost) one in the list.  */
 132   gl_list_node_t previous_node (gl_list_node_t node) const
 133     { return gl_list_previous_node (_ptr, node); }
 134
 135   /* Returns the element at a given position in the list.
 136      POSITION must be >= 0 and < gl_list_size (list).  */
 137   ELTYPE * get_at (size_t position) const
 138     { return static_cast<ELTYPE *>(gl_list_get_at (_ptr, position)); }
 139
 140   /* Returns the element at the first position in the list.
 141      The list must be non-empty.  */
 142   ELTYPE * get_first () const
 143     { return static_cast<ELTYPE *>(gl_list_get_first (_ptr)); }
 144
 145   /* Returns the element at the last position in the list.
 146      The list must be non-empty.  */
 147   ELTYPE * get_last () const
 148     { return static_cast<ELTYPE *>(gl_list_get_last (_ptr)); }
 149
 150   /* Searches whether an element is already in the list.
 151      Returns its node if found, or NULL if not present in the list.  */
 152   gl_list_node_t search (ELTYPE * elt) const
 153     { return gl_list_search (_ptr, elt); }
 154
 155   /* Searches whether an element is already in the list,
 156      at a position >= START_INDEX.
 157      Returns its node if found, or NULL if not present in the list.  */
 158   gl_list_node_t search_from (size_t start_index, ELTYPE * elt) const
 159     { return gl_list_search_from (_ptr, start_index, elt); }
 160
 161   /* Searches whether an element is already in the list,
 162      at a position >= START_INDEX and < END_INDEX.
 163      Returns its node if found, or NULL if not present in the list.  */
 164   gl_list_node_t search_from_to (size_t start_index, size_t end_index, ELTYPE * elt) const
 165     { return gl_list_search_from_to (_ptr, start_index, end_index, elt); }
 166
 167   /* Searches whether an element is already in the list.
 168      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 169   size_t indexof (ELTYPE * elt) const
 170     { return gl_list_indexof (_ptr, elt); }
 171
 172   /* Searches whether an element is already in the list,
 173      at a position >= START_INDEX.
 174      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 175   size_t indexof_from (size_t start_index, ELTYPE * elt) const
 176     { return gl_list_indexof_from (_ptr, start_index, elt); }
 177
 178   /* Searches whether an element is already in the list,
 179      at a position >= START_INDEX and < END_INDEX.
 180      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 181   size_t indexof_from_to (size_t start_index, size_t end_index, ELTYPE * elt) const
 182     { return gl_list_indexof_from_to (_ptr, start_index, end_index, elt); }
 183
 184   // ----------------------- Modifying member functions -----------------------
 185
 186   /* Replaces the element value represented by a list node.  */
 187   void node_set_value (gl_list_node_t node, ELTYPE * elt)
 188     { gl_list_node_set_value (_ptr, node, elt); }
 189
 190   /* Replaces the element at a given position in the list.
 191      POSITION must be >= 0 and < gl_list_size (list).
 192      Returns its node.  */
 193   gl_list_node_t set_at (size_t position, ELTYPE * elt)
 194     { return gl_list_set_at (_ptr, position, elt); }
 195
 196   /* Replaces the element at the first position in the list.
 197      Returns its node.
 198      The list must be non-empty.  */
 199   gl_list_node_t set_first (ELTYPE * elt)
 200     { return gl_list_set_first (_ptr, elt); }
 201
 202   /* Replaces the element at the last position in the list.
 203      Returns its node.
 204      The list must be non-empty.  */
 205   gl_list_node_t set_last (ELTYPE * elt)
 206     { return gl_list_set_last (_ptr, elt); }
 207
 208   /* Adds an element as the first element of the list.
 209      Returns its node.  */
 210   gl_list_node_t add_first (ELTYPE * elt)
 211     { return gl_list_add_first (_ptr, elt); }
 212
 213   /* Adds an element as the last element of the list.
 214      Returns its node.  */
 215   gl_list_node_t add_last (ELTYPE * elt)
 216     { return gl_list_add_last (_ptr, elt); }
 217
 218   /* Adds an element before a given element node of the list.
 219      Returns its node.  */
 220   gl_list_node_t add_before (gl_list_node_t node, ELTYPE * elt)
 221     { return gl_list_add_before (_ptr, node, elt); }
 222
 223   /* Adds an element after a given element node of the list.
 224      Return its node.  */
 225   gl_list_node_t add_after (gl_list_node_t node, ELTYPE * elt)
 226     { return gl_list_add_after (_ptr, node, elt); }
 227
 228   /* Adds an element at a given position in the list.
 229      POSITION must be >= 0 and <= gl_list_size (list).  */
 230   gl_list_node_t add_at (size_t position, ELTYPE * elt)
 231     { return gl_list_add_at (_ptr, position, elt); }
 232
 233   /* Removes an element from the list.
 234      Returns true.  */
 235   bool remove_node (gl_list_node_t node)
 236     { return gl_list_remove_node (_ptr, node); }
 237
 238   /* Removes an element at a given position from the list.
 239      POSITION must be >= 0 and < gl_list_size (list).
 240      Returns true.  */
 241   bool remove_at (size_t position)
 242     { return gl_list_remove_at (_ptr, position); }
 243
 244   /* Removes the element at the first position from the list.
 245      Returns true if it was found and removed,
 246      or false if the list was empty.  */
 247   bool remove_first ()
 248     { return gl_list_remove_first (_ptr); }
 249
 250   /* Removes the element at the last position from the list.
 251      Returns true if it was found and removed,
 252      or false if the list was empty.  */
 253   bool remove_last ()
 254     { return gl_list_remove_last (_ptr); }
 255
 256   /* Searches and removes an element from the list.
 257      Returns true if it was found and removed.  */
 258   bool remove (ELTYPE * elt)
 259     { return gl_list_remove (_ptr, elt); }
 260
 261   /* Frees the entire list.
 262      (But this call does not free the elements of the list.  It only invokes
 263      the DISPOSE_FN on each of the elements of the list, and only if the list
 264      is not a sublist.)  */
 265   void free ()
 266     { gl_list_free (_ptr); _ptr = NULL; }
 267
 268   // -------------------- Member functions for sorted lists --------------------
 269
 270   /* The following functions are for lists without duplicates where the
 271      order is given by a sort criterion.  */
 272
 273   /* Searches whether an element is already in the list.
 274      The list is assumed to be sorted with COMPAR.
 275      Returns its node if found, or NULL if not present in the list.
 276      If the list contains several copies of ELT, the node of the leftmost one is
 277      returned.  */
 278   gl_list_node_t sortedlist_search (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 279                                     ELTYPE * elt)
 280     { return gl_sortedlist_search (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 281
 282   /* Searches whether an element is already in the list.
 283      The list is assumed to be sorted with COMPAR.
 284      Only list elements with indices >= START_INDEX and < END_INDEX are
 285      considered; the implementation uses these bounds to minimize the number
 286      of COMPAR invocations.
 287      Returns its node if found, or NULL if not present in the list.
 288      If the list contains several copies of ELT, the node of the leftmost one is
 289      returned.  */
 290   gl_list_node_t sortedlist_search_from_to (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 291                                             size_t start_index,
 292                                             size_t end_index,
 293                                             ELTYPE * elt)
 294     { return gl_sortedlist_search_from_to (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), start_index, end_index, elt); }
 295
 296   /* Searches whether an element is already in the list.
 297      The list is assumed to be sorted with COMPAR.
 298      Returns its position if found, or (size_t)(-1) if not present in the list.
 299      If the list contains several copies of ELT, the position of the leftmost one
 300      is returned.  */
 301   size_t sortedlist_indexof (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 302                              ELTYPE * elt)
 303     { return gl_sortedlist_indexof (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 304
 305   /* Searches whether an element is already in the list.
 306      The list is assumed to be sorted with COMPAR.
 307      Only list elements with indices >= START_INDEX and < END_INDEX are
 308      considered; the implementation uses these bounds to minimize the number
 309      of COMPAR invocations.
 310      Returns its position if found, or (size_t)(-1) if not present in the list.
 311      If the list contains several copies of ELT, the position of the leftmost one
 312      is returned.  */
 313   size_t sortedlist_indexof_from_to (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 314                                      size_t start_index,
 315                                      size_t end_index,
 316                                      ELTYPE * elt)
 317     { return gl_sortedlist_indexof_from_to (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), start_index, end_index, elt); }
 318
 319   /* Adds an element at the appropriate position in the list.
 320      The list is assumed to be sorted with COMPAR.
 321      Returns its node.  */
 322   gl_list_node_t sortedlist_add (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 323                                  ELTYPE * elt)
 324     { return gl_sortedlist_add (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 325
 326   /* Searches and removes an element from the list.
 327      The list is assumed to be sorted with COMPAR.
 328      Returns true if it was found and removed.
 329      If the list contains several copies of ELT, only the leftmost one is
 330      removed.  */
 331   bool sortedlist_remove (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 332                           ELTYPE * elt)
 333     { return gl_sortedlist_remove (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 334
 335   // ------------------------------ Private stuff ------------------------------
 336
 337 private:
 338   gl_list_t _ptr;
 339
 340 public:
 341   // -------------------------------- Iterators --------------------------------
 342   // Only a forward iterator.
 343   // Does not implement the STL operations (++, *, and != .end()), but a simpler
 344   // interface that needs only one virtual function call per iteration instead
 345   // of three.
 346
 347   class iterator {
 348   public:
 349
 350     /* If there is a next element, stores the next element in ELT, advances
 351        the iterator and returns true.
 352        Otherwise, returns false.  */
 353     bool next (ELTYPE *& elt)
 354       {
 355         const void *next_elt;
 356         bool has_next = gl_list_iterator_next (&_state, &next_elt, NULL);
 357         if (has_next)
 358           elt = static_cast<ELTYPE *>(next_elt);
 359         return has_next;
 360       }
 361
 362     /* If there is a next element, stores the next element in ELT, stores its
 363        node in *NODEP if NODEP is non-NULL, advances the iterator and returns true.
 364        Otherwise, returns false.  */
 365     bool next (ELTYPE *& elt, gl_list_node_t *nodep)
 366       {
 367         const void *next_elt;
 368         bool has_next = gl_list_iterator_next (&_state, &next_elt, nodep);
 369         if (has_next)
 370           elt = static_cast<ELTYPE *>(next_elt);
 371         return has_next;
 372       }
 373
 374     ~iterator ()
 375       { gl_list_iterator_free (&_state); }
 376
 377   #if defined __xlC__ || defined __HP_aCC || defined __SUNPRO_CC
 378   public:
 379   #else
 380   private:
 381     friend iterator gl_List::begin ();
 382   #endif
 383
 384     iterator (gl_list_t ptr)
 385       : _state (gl_list_iterator (ptr))
 386       {}
 387
 388     iterator (gl_list_t ptr, size_t start_index, size_t end_index)
 389       : _state (gl_list_iterator_from_to (ptr, start_index, end_index))
 390       {}
 391
 392   private:
 393
 394     gl_list_iterator_t _state;
 395   };
 396
 397   /* Creates an iterator traversing the list.
 398      The list contents must not be modified while the iterator is in use,
 399      except for replacing or removing the last returned element.  */
 400   iterator begin ()
 401     { return iterator (_ptr); }
 402
 403   /* Creates an iterator traversing the element with indices i,
 404      start_index <= i < end_index, of a list.
 405      The list contents must not be modified while the iterator is in use,
 406      except for replacing or removing the last returned element.  */
 407   iterator begin (size_t start_index, size_t end_index)
 408     { return iterator (_ptr, start_index, end_index); }
 409 };
 410
 411 #endif /* _GL_LIST_HH */