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