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