ALib C++ Library
Library Version: 2412 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
sidilist.hpp
Go to the documentation of this file.
1//==================================================================================================
2/// \file
3/// This header file is part of the \aliblong. It does not belong to an \alibmod and is
4/// included in any \alibdist.
5///
6/// \emoji :copyright: 2013-2024 A-Worx GmbH, Germany.
7/// Published under \ref mainpage_license "Boost Software License".
8//==================================================================================================
9#ifndef HPP_ALIB_LANG_SIDILIST
10#define HPP_ALIB_LANG_SIDILIST 1
11#pragma once
13
14namespace alib::lang {
15
16//==================================================================================================
17/// This is a generic base type that may be used to represent a node of a single linked list.
18/// The effective (instantiated) nodes of the list are to be derived from this type by specifying
19/// their very own type name as template parameter \p{TElement}. The following quick sample
20/// demonstrates this:
21///
22/// \code{.cpp}
23/// // The contents to store with each element of a list
24/// class MyData
25/// {
26/// //...
27/// };
28///
29/// // The custom list node derived from this type, giving its own type as template parameter
30/// struct MyElement : public lang::SidiNodeBase<MyElement>
31/// {
32/// MyData nodeValue;
33/// };
34/// \endcode
35///
36/// With this mechanism in place, pointers to nodes of this type may either point to a node
37/// or to a "full" element of derived class.
38/// This concept allows having field #n of this class of derived type \p{TElement}, which makes
39/// debugging end-user code much easier because the custom values of the derived types are
40/// visible within debugging tools.
41///
42/// This type provides some helper methods, which, together with those of sibling
43/// struct \alib{lang::SidiListHook}, provide all basic mechanisms to implement a single linked
44/// list.
45///
46/// Because pointers to nodes and elements are statically castable to each other (which is a noop),
47/// most helper methods accept and/or return pointers to derived type \p{TElement}. It has
48/// to be ensured by the caller that these pointers are only dereferenced when it is ensured that
49/// they do not refer to this base type! Therefore, the helper-classes are designed for
50/// "internal use" and reside in the \e detail namespace.
51/// As an example, class \alib{containers;List} of module \alib_containers is built using these
52/// helpers internally but publishes a full type safe interface, including iterator classes.
53///
54/// \see Types \alib{lang::SidiListHook},<br>
55/// \alib{lang::BidiNodeBase}, and<br>
56/// \alib{lang::BidiListHook}.
57///
58/// @tparam TElement The "final" node type, containing custom data fields, that is to be derived from
59/// this struct.
60//==================================================================================================
61template<typename TElement>
63{
64 /// A pointer to the next element in the list.
65 /// \attention
66 /// In case of using type \alib{lang::BidiListHook}, this may point to an instance of the
67 /// base type \alib{lang::BidiNodeBase}.
68 TElement* n;
69
70
71 /// Default constructor. (Does not initialize the pointer.)
72 SidiNodeBase() noexcept = default;
73
74 /// Deleted copy constructor. This is deleted because it is dangerous, respectively often
75 /// not possible and also mostly not wanted to be able to create copies of derived type
76 /// \p{TElement}
77 SidiNodeBase( const SidiNodeBase& ) = delete;
78
79 /// Defaulted move constructor.
80 SidiNodeBase( SidiNodeBase&& ) noexcept = default;
81
82 /// Deleted copy assignment operator. This is deleted because it is dangerous, respectively
83 /// often not possible and also mostly not wanted to create copies of derived type
84 /// \p{TElement}
85 /// @return Not defined.
86 SidiNodeBase& operator=( const SidiNodeBase& ) = delete;
87
88 /// Defaulted move assignment operator.
89 /// @return A reference to this object.
90 SidiNodeBase& operator=( SidiNodeBase&& ) noexcept = default;
91
92 /// Constructor accepting a pointer to the next element.
93 /// @param next Pointer to the next element. Assigned to field #n.
94 explicit
95 SidiNodeBase( TElement* next ) noexcept
96 : n(next) {}
97
98 /// Sets the successor of this node or element.
99 /// @param p The node that this node should point to, respectively \c nullptr if this node
100 /// should represent the last element of the list.
101 void next(SidiNodeBase* p) { n= static_cast<TElement*>(p); }
102
103 /// Returns the successor of this node or element.
104 /// @return The element following this one, respectively \c nullptr if this is the last
105 /// element of the list.
106 TElement* next() const { return n; }
107
108 /// Test if this node or element has set an element in filed #n.
109 /// @return \c false if field #n equals \c nullptr, otherwise \c true.
110 [[nodiscard]]
111 bool hasNext() const { return n != nullptr; }
112
113 /// Test if \p{elem} is the successor for this node or element.
114 /// @param elem The element to test for being a successor of this.
115 /// @return \c true if field #n equals \p{elem} , otherwise \c false.
116 [[nodiscard]]
117 bool pointsTo( const SidiNodeBase* elem ) const { return n == elem; }
118
119 /// Unhooks and returns the element after this node or element.
120 /// \note
121 /// Field #n of the returned element is \b not set to \c nullptr.
122 ///
123 /// @return The unhooked element.
124 TElement* removeNext() noexcept
125 {
126 auto* result= next();
127 next( next()->next() );
128 return result;
129 }
130
131 /// Unhooks successors until \p last. If \p last equals field #n, only this next
132 /// element is unhooked.
133 /// \attention
134 /// Field #n of given \p{last} is \b not set to \c nullptr.
135 ///
136 /// @param last The last element of the range
137 /// <b>[</b>\ref n "n"<b>, </b> \p{last}<b>]</b> which is removed.
138 ///
139 /// @return The start of the range (the current successor of this node or element).
140 TElement* removeRangeBehind( TElement* last ) noexcept
141 {
142 TElement* result= next();
143 next( last->next() );
144 return result;
145 }
146
147 /// Hooks the given element behind this node or element.
148 /// @param elem The element to insert behind this node or element.
149 /// @return The element that given \p{elem} pointed to before the insertion.
150 TElement* addBehind( TElement* elem ) noexcept
151 {
152 TElement* result = elem->next();
153 elem->next(next());
154 next( elem );
155 return result;
156 }
157
158 /// Counts the number of elements found in the range starting with the next node (in
159 /// consideration that this node is the 'hook' node) and ending with the element before \p{end}.
160 ///
161 /// @param end Pointer to the element after the last one to count.
162 /// Defaults to \c nullptr, marking the end of a list.
163 /// @return The number of elements in the range.
164 [[nodiscard]]
165 integer count( SidiNodeBase* end= nullptr ) const noexcept
166 {
167 integer result= 0;
168 SidiNodeBase* start= next();
169 while( start != end )
170 {
171 start= start->next();
172 ++result;
173 }
174 return result;
175 }
176}; // struct SidiNodeBase
177
178
179//==================================================================================================
180/// This class, together with sibling class \alib{lang::SidiNodeBase} provide the tools to
181/// implement a single linked list of \p{TElement} instances.
182///
183/// \see Types \alib{lang::SidiNodeBase},<br>
184/// \alib{lang::BidiNodeBase}, and<br>
185/// \alib{lang::BidiListHook}.
186///
187/// @tparam TElement The "final" custom type that (by contract) is derived from
188/// \alib{lang::SidiNodeBase}.
189//==================================================================================================
190template<typename TElement>
191struct SidiListHook : SidiNodeBase<TElement>
192{
193 /// An alias for the node type.
195
196 /// Default constructor. Initializes this list to be empty.
197 SidiListHook() noexcept
198 : TNode(nullptr) {}
199
200 /// Deleted copy constructor.
201 /// \note Copy construction is a duty of derived usable types.
202 SidiListHook( const SidiListHook& copy ) = delete;
203
204 /// Move constructor.
205 /// Copies the link from \p{move} and sets the link of \p{move} to \c nullptr.
206 SidiListHook( SidiListHook&& ) noexcept = default;
207
208 /// Deleted copy assignment operator.
209 /// @return Not applicable
210 SidiListHook& operator= ( const SidiListHook& ) noexcept = delete;
211
212 /// Move assignment operator.
213 /// Copies the link to the first element from \p{move} and sets the link in \p{move} to
214 /// \c nullptr.
215 /// @return A reference to this list object.
216 SidiListHook& operator= ( SidiListHook&& ) noexcept = default;
217
218 /// Tests if this list is empty.
219 /// @return \c false if the list is empty, \c true otherwise.
220 [[nodiscard]]
221 bool isEmpty() const noexcept { return first() == nullptr; }
222
223 /// Resets this list to zero elements.
224 void reset() noexcept { TNode::next(nullptr); }
225
226 /// Returns the start element of this list.
227 /// @return The first element of this list, respectively \c nullptr if this list is empty.
228 [[nodiscard]]
229 TElement* first() const noexcept { return TNode::next(); }
230
231 /// Hooks the given element to the beginning of this list.
232 /// @param elem The element to insert to at the start.
233 void pushFront( TElement* elem ) noexcept
234 {
235 elem->next( TNode::next() );
236 TNode::next( elem );
237 }
238
239 /// Hooks the given range of elements to the front of this list.
240 /// @param first The first element of the range to insert.
241 /// @param last The last element of the range to insert.
242 void pushFront( TElement* first, TElement* last )
243 {
244 last->next(this->first());
245 TNode::next(first);
246 }
247
248 /// Removes and returns the first element from this list.
249 /// @return A pointer to the element, respectively \c nullptr if the list was empty.
250 TElement* popFront() noexcept
251 {
252 TElement* result= first();
253 if( result )
254 TNode::next(result->next());
255 return result;
256 }
257
258 /// Searches and returns the last element.
259 /// \note
260 /// This method must only be invoked on non-empty lists (#isEmpty returns \c false).
261 /// Otherwise, this method has undefined behavior (dereference of a \c nullptr).
262 /// To find the pointer to the last element, use #findLastBefore providing \c nullptr.
263 /// @return The last element of this list.
264 [[nodiscard]]
265 TElement* findLast() const noexcept
266 {
267 TElement* elem= first();
268 while( elem->hasNext() )
269 elem= elem->next();
270 return elem;
271 }
272
273 /// Searches and returns the last element.
274 /// @param hint An element of this list used to start the search.
275 /// @return The last element of this list.
276 [[nodiscard]]
277 TElement* findLast( TElement* hint ) const noexcept
278 {
279 TElement* elem= hint;
280 while( elem->hasNext() )
281 elem= elem->next();
282 return elem;
283 }
284
285 /// Searches the node or element that points to the given element.
286 /// \attention The element has to exist. Otherwise, a \c nullptr exception will occur!
287 /// @param elem The element to search for.
288 /// @return The node (this object) or element pointing to \p{elem}.
289 [[nodiscard]]
290 TElement* findLastBefore( TElement* elem ) noexcept
291 {
292 TNode* it= this;
293 while( !it->pointsTo(elem) )
294 it= it->next();
295 return static_cast<TElement*>( it );
296 }
297
298 /// Searches the predecessor of the given element using #findLastBefore and unhooks the element
299 /// from the list.
300 /// \attention
301 /// It is not checked whether a predecessor was found, aka whether \p{elem} is an element
302 /// of this list. If not, the behavior is undefined (<c>nullptr access</c>).<br>
303 /// Furthermore, the successor of given \p{elem} is not changed, although it is removed
304 /// from the list.
305 ///
306 /// @param elem The element to remove.
307 /// @return The node (this object) or element that pointed to given \p{elem} before the
308 /// invocation and now points to the successor of \p{elem}.
309 TNode* findAndRemove( TElement* elem ) noexcept
310 {
311 TNode* previous= findLastBefore(elem);
312 previous->removeNext();
313 return previous;
314 }
315
316 /// Counts the number of elements found in the range starting with this list's first element and
317 /// ending with the element before \p{end}.
318 /// @param end The element after the last one to count.
319 /// Defaults to a \c nullptr marking the end of the list.
320 /// @return The number of elements in the range.
321 [[nodiscard]]
322 integer count( TElement* end= nullptr ) const noexcept { return TNode::count( end ); }
323}; // struct SidiListHook
324
325} // namespace [alib::lang]
326
327
328#endif // HPP_ALIB_LANG_SIDILIST
329
platform_specific integer
Definition integers.hpp:43
TElement * popFront() noexcept
Definition sidilist.hpp:250
void reset() noexcept
Resets this list to zero elements.
Definition sidilist.hpp:224
void pushFront(TElement *elem) noexcept
Definition sidilist.hpp:233
TElement * findLastBefore(TElement *elem) noexcept
Definition sidilist.hpp:290
integer count(TElement *end=nullptr) const noexcept
Definition sidilist.hpp:322
TElement * findLast(TElement *hint) const noexcept
Definition sidilist.hpp:277
TElement * findLast() const noexcept
Definition sidilist.hpp:265
TNode * findAndRemove(TElement *elem) noexcept
Definition sidilist.hpp:309
TElement * first() const noexcept
Definition sidilist.hpp:229
SidiListHook(SidiListHook &&) noexcept=default
SidiListHook() noexcept
Default constructor. Initializes this list to be empty.
Definition sidilist.hpp:197
bool isEmpty() const noexcept
Definition sidilist.hpp:221
SidiListHook(const SidiListHook &copy)=delete
void pushFront(TElement *first, TElement *last)
Definition sidilist.hpp:242
TElement * next() const
Definition sidilist.hpp:106
TElement * removeNext() noexcept
Definition sidilist.hpp:124
void next(SidiNodeBase *p)
Definition sidilist.hpp:101
bool pointsTo(const SidiNodeBase *elem) const
Definition sidilist.hpp:117
TElement * removeRangeBehind(TElement *last) noexcept
Definition sidilist.hpp:140
SidiNodeBase() noexcept=default
Default constructor. (Does not initialize the pointer.)
TElement * addBehind(TElement *elem) noexcept
Definition sidilist.hpp:150
integer count(SidiNodeBase *end=nullptr) const noexcept
Definition sidilist.hpp:165