ALib C++ Library
Library Version: 2510 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
bidilist.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 represents a node of a doubly (bidirectional) 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}. For more information on this
14/// design, see explanations of parent type \alib{lang::SidiNodeBase}.
15///
16/// By being derived from the aforementioned type, instances of \p{TElement} may also be added
17/// to single-linked lists of type \alib{lang::SidiListHook}). This is, for example,
18/// used by types \alib{containers;List} and \alib{containers;HashTable} to
19/// collect erased list elements for recycling.
20///
21/// \see Types \alib{lang::SidiNodeBase},<br>
22/// \alib{lang::SidiListHook}, and<br>
23/// \alib{lang::BidiListHook}.
24///
25/// @tparam TElement The "final" node type, containing custom data fields, that is to be derived from
26/// this struct.
27//==================================================================================================
28template<typename TElement>
29struct BidiNodeBase : public SidiNodeBase<TElement>
30{
31 /// Alias name for an instantiation of the base template.
33
34 /// A pointer to the previous element in the list.
35 /// \attention
36 /// If this is the first node in the list, this object will point to the list hook, which is
37 /// an instance of this type instead of template type \p{TElement}.
38 TElement* p;
39
40 /// Default constructor. (Does not initialize the pointer!)
41 BidiNodeBase() noexcept = default;
42
43 /// Deleted copy constructor. This is deleted because it is dangerous, respectively often
44 /// not possible and also mostly not wanted to be able to create copies of derived type
45 /// \p{TElement}
46 BidiNodeBase( const BidiNodeBase& ) = delete;
47
48 /// Defaulted move constructor.
49 BidiNodeBase( BidiNodeBase&& ) noexcept = default;
50
51 /// Deleted copy assignment operator. This is deleted because it is dangerous, respectively
52 /// often not possible and also mostly not wanted to create copies of derived type \p{TElement}.
53 /// @return Not defined.
54 BidiNodeBase& operator=( const BidiNodeBase& ) = delete;
55
56 /// Defaulted move assignment operator.
57 /// @return A reference to this object.
58
59 BidiNodeBase& operator=( BidiNodeBase&& ) noexcept = default;
60
61 /// Constructor accepting a pointer to the next and previous elements.
62 /// @param next Pointer to the next element. Assigned to the inherited field
63 /// \alib{lang::SidiNodeBase::n}.
64 /// @param prev Pointer to the next element. Assigned to the field #p.
65 BidiNodeBase( TElement* next, TElement* prev ) noexcept
66 : SidiNodeBase<TElement>(next)
67 , p (prev) {}
68
69 /// Returns the backward pointer of this node.
70 /// @return Pointer to the previous element.
71 [[nodiscard]]
72 TElement* prev() const noexcept { return p; }
73
74 /// Sets the backward pointer of this node.
75 /// @param previous Pointer to the previous element.
76 void prev(BidiNodeBase* previous) noexcept { p= static_cast<TElement*>(previous); }
77
78 /// Hooks the given element before this node.
79 /// @param elem The element to add.
80 void addBefore( TElement* elem ) noexcept
81 {
82 elem->next( this );
83 elem->prev( prev() );
84 prev()->next(elem);
85 prev(elem);
86 }
87
88 /// Hooks the given element behind this node.
89 /// @param elem The element to add.
90 void addBehind( TElement* elem ) noexcept
91 {
92 elem->next( FWDNode::next() );
93 elem->prev( this );
94 FWDNode::next()->prev( elem );
95 FWDNode::next( elem );
96 }
97
98 /// Unhooks this node from a list.
99 void remove() noexcept
100 {
101 FWDNode::next()->prev(prev());
102 prev()->next( FWDNode::next());
103 }
104
105 /// Unhooks the range of nodes starting with this node and ending with \p{last} a list.
106 /// @param last The last element of the range to remove.
107 void remove( TElement* last ) noexcept
108 {
109 last->next()->prev( prev() );
110 prev()->next( last->next() );
111 }
112
113}; // struct BidiNodeBase
114
115//==================================================================================================
116/// This struct, together with sibling struct \alib{lang::BidiNodeBase} provide the tools to
117/// implement a doubly linked list of \p{TElement} instances.<br>
118///
119/// Template type \p{TElement} has to extend struct BidiNodeBase<TElement>.
120///
121/// \see Types \alib{lang::SidiNodeBase},<br>
122/// \alib{lang::SidiListHook}, and<br>
123/// \alib{lang::BidiNodeBase}.
124///
125/// @tparam TElement The "final" custom type that (by contract) is derived from
126/// \alib{lang::BidiNodeBase}.
127//==================================================================================================
128template<typename TElement>
130{
131 /// An alias for the base type of the node type of this list.
133
134 /// An alias for the node type of this list.
136
137 /// The root node. Points twice to itself when the list is empty.
139
140 /// Default constructor. Initializes this list to be empty.
141 BidiListHook() noexcept
142 {
143 hook.next(&hook);
144 hook.prev(&hook);
145 }
146
147 /// Deleted copy constructor.
148 BidiListHook( const BidiListHook& ) = delete;
149
150 /// Move constructor. Takes elements of \p move and sets \p move to empty.
151 /// @param move The list to move.
152 BidiListHook( BidiListHook&& move) noexcept
153 {
154 if( !move.isEmpty() )
155 {
156 hook.next( move.hook.next() );
157 hook.prev(move.hook.prev());
158 move.reset();
159 }
160 else
161 reset();
162 }
163
164 /// Deleted copy assignment operator.
165 /// @return A reference to this list object.
167
168 /// Defaulted move assignment operator.
169 /// @return A reference to this list object.
170 BidiListHook& operator= ( BidiListHook&&) noexcept = default;
171
172 /// Constructor accepting a pointer to the first element.
173 /// @param first The element to use as the first element of this list.
174 explicit BidiListHook( TElement* first ) noexcept
175 {
176 hook.next( first );
177 hook.prev( first );
178 first->next( &hook );
179 first->prev( &hook );
180 }
181
182 /// Constructor accepting a pointer to the first and last element.
183 /// @param first The element to use as the first element of this list.
184 /// @param last The element to use as the last element of this list.
185 BidiListHook( TElement* first, TElement* last ) noexcept
186 {
187 hook.next( first );
188 hook.prev( last );
189 first->prev( &hook );
190 last->next( &hook );
191 }
192
193 /// Tests if this list is empty.
194 /// @return \c false if the list is empty, \c true otherwise.
195 [[nodiscard]]
196 bool isEmpty() const noexcept { return hook.pointsTo( &hook ); }
197
198 /// Resets this list to zero elements.
199 void reset() noexcept { hook.next(&hook); hook.prev(&hook); }
200
201 /// Returns a pointer to the #hook node cast to a pointer to a mutable element.
202 /// This method must only be used in cases where such conversion is allowed i.e., with
203 /// iterator types that use this pointer exclusively for pointer value comparison but do not
204 /// allow (by contract) to dereference or otherwise use this pointer.
205 /// @return The first element of this list.
206 TElement* end() const noexcept
207 { return static_cast<TElement*>( &const_cast<BidiListHook*>(this)->hook ); }
208
209
210 /// Returns the first element of this list.
211 /// @return The first element of this list.
212 [[nodiscard]]
213 TElement* first() const noexcept { return hook.next(); }
214
215 /// Returns the last element of this list.
216 /// @return The last element of this list.
217 [[nodiscard]]
218 TElement* last() const noexcept { return hook.prev(); }
219
220 /// Tests if given \p{elem} is the first element of this list.
221 /// @param elem The element to test for being the first.
222 /// @return \c true if \p{elem} is the first element of this list, \c false otherwise.
223 [[nodiscard]]
224 bool isFirst( const TElement* elem ) const noexcept { return first() == elem; }
225
226 /// Tests if given \p{elem} is the last element of this list.
227 /// @param elem The element to test for being the last.
228 /// @return \c true if \p{elem} is the last element of this list, \c false otherwise.
229 [[nodiscard]]
230 bool isLast( const TElement* elem ) const noexcept { return last() == elem; }
231
232 /// Hooks the given element to the beginning of this list.
233 /// @param elem The element to insert to at the start.
234 void pushFront( TElement* elem ) noexcept { hook.addBehind( elem ); }
235
236 /// Hooks the given range of elements to the front of this list.
237 /// @param first The first element of the range to insert.
238 /// @param last The last element of the range to insert.
239 void pushFront( TElement* first, TElement* last ) noexcept {hook.addBehind( first, last );}
240
241 /// Hooks the given element to the end of this list.
242 /// @param elem The element to insert to at the start.
243 void pushEnd( TElement* elem ) noexcept { hook.addBefore( elem ); }
244
245 /// Hooks the given range of elements to the end of this list.
246 /// @param first The first element of the range to insert.
247 /// @param last The last element of the range to insert.
248 void pushEnd( TElement* first, TElement* last ) noexcept { hook.addBefore( first, last ); }
249
250 /// Removes and returns the first element from this list.
251 /// Must not be invoked on empty lists.
252 /// @return A pointer to the first element (which was removed).
253 TElement* popFront() noexcept { TElement* first= hook.next(); first->remove(); return first; }
254
255 /// Removes and returns the last element from this list.
256 /// Must not be invoked on empty lists.
257 /// @return A pointer to the last element (which was removed).
258 TElement* popEnd() noexcept
259 {
260 TElement* last= hook.prev();
261 last->remove();
262 return last;
263 }
264
265 /// Counts the number of elements found in the range starting with this list's first element and
266 /// ending with the element before \p{end}.
267 /// @param end The element after the last one to count.
268 /// Defaults to a \c nullptr marking the end of the list.
269 /// @return The number of elements in the range.
270 [[nodiscard]]
271 integer count( const TNode* end= nullptr ) const noexcept
272 {
273 if( end == nullptr )
274 end= &hook;
275
276 integer count= 0;
277 const TNode* node= hook.next();
278 while( node != end )
279 {
280 node= node->next();
281 ++count;
282 }
283 return count;
284 }
285}; // struct BidiListHook
286
287
288} // namespace [alib::detail]
289
#define ALIB_EXPORT
Definition alib.inl:488
platform_specific integer
Definition integers.inl:32
BidiListHook(const BidiListHook &)=delete
Deleted copy constructor.
bool isFirst(const TElement *elem) const noexcept
Definition bidilist.inl:224
NodeBase * first() const noexcept
Definition bidilist.inl:213
void pushEnd(TElement *first, TElement *last) noexcept
Definition bidilist.inl:248
void reset() noexcept
Resets this list to zero elements.
Definition bidilist.inl:199
TElement * popFront() noexcept
Definition bidilist.inl:253
void pushFront(TElement *first, TElement *last) noexcept
Definition bidilist.inl:239
integer count(const TNode *end=nullptr) const noexcept
Definition bidilist.inl:271
bool isLast(const TElement *elem) const noexcept
Definition bidilist.inl:230
TElement * popEnd() noexcept
Definition bidilist.inl:258
void pushFront(TElement *elem) noexcept
Definition bidilist.inl:234
BidiNodeBase< NodeBase > TNode
Definition bidilist.inl:135
BidiListHook & operator=(const BidiListHook &)=delete
SidiNodeBase< NodeBase > TFNode
Definition bidilist.inl:132
BidiListHook(TElement *first, TElement *last) noexcept
Definition bidilist.inl:185
BidiListHook() noexcept
Default constructor. Initializes this list to be empty.
Definition bidilist.inl:141
BidiListHook(BidiListHook &&move) noexcept
Definition bidilist.inl:152
TElement * end() const noexcept
Definition bidilist.inl:206
bool isEmpty() const noexcept
Definition bidilist.inl:196
void pushEnd(TElement *elem) noexcept
Definition bidilist.inl:243
NodeBase * last() const noexcept
Definition bidilist.inl:218
SidiNodeBase< TElement > FWDNode
Alias name for an instantiation of the base template.
Definition bidilist.inl:32
void prev(BidiNodeBase *previous) noexcept
Definition bidilist.inl:76
BidiNodeBase() noexcept=default
Default constructor. (Does not initialize the pointer!)
void remove(TElement *last) noexcept
Definition bidilist.inl:107
void remove() noexcept
Unhooks this node from a list.
Definition bidilist.inl:99
void addBehind(TElement *elem) noexcept
Definition bidilist.inl:90
void addBefore(TElement *elem) noexcept
Definition bidilist.inl:80
TElement * prev() const noexcept
Definition bidilist.inl:72
SidiNodeBase() noexcept=default
Default constructor. (Does not initialize the pointer.)
void next(SidiNodeBase *p)
Definition sidilist.inl:95
TElement * next() const
Definition sidilist.inl:100