Line | Branch | Exec | Source |
---|---|---|---|
1 | /** | ||
2 | * @file lib.AbstractList.hpp | ||
3 | * @author Sergey Baigudin, sergey@baigudin.software | ||
4 | * @copyright 2016-2022, Sergey Baigudin, Baigudin Software | ||
5 | */ | ||
6 | #ifndef LIB_ABSTRACTLIST_HPP_ | ||
7 | #define LIB_ABSTRACTLIST_HPP_ | ||
8 | |||
9 | #include "lib.NonCopyable.hpp" | ||
10 | #include "lib.Buffer.hpp" | ||
11 | #include "lib.LinkedNode.hpp" | ||
12 | #include "api.List.hpp" | ||
13 | #include "api.Queue.hpp" | ||
14 | #include "api.Iterable.hpp" | ||
15 | |||
16 | namespace eoos | ||
17 | { | ||
18 | namespace lib | ||
19 | { | ||
20 | |||
21 | /** | ||
22 | * @class AbstractList<T,A> | ||
23 | * @brief Abstract list class. | ||
24 | * | ||
25 | * @tparam T Data type of container element. | ||
26 | * @tparam A Heap memory allocator class. | ||
27 | */ | ||
28 | template <typename T, class A = Allocator> | ||
29 | class AbstractList : | ||
30 | public NonCopyable<A>, | ||
31 | public api::List<T>, | ||
32 | public api::Queue<T>, | ||
33 | public api::Iterable<T>{ | ||
34 | |||
35 | typedef NonCopyable<A> Parent; | ||
36 | typedef LinkedNode<T,A> Node; | ||
37 | |||
38 | public: | ||
39 | |||
40 | using api::List<T>::getListIterator; | ||
41 | |||
42 | /** | ||
43 | * @brief Destructor. | ||
44 | */ | ||
45 | 152 | virtual ~AbstractList() | |
46 | { | ||
47 | 152 | AbstractList<T,A>::clear(); | |
48 | } | ||
49 | |||
50 | /** | ||
51 | * @copydoc eoos::api::Object::isConstructed() | ||
52 | */ | ||
53 | 3574 | virtual bool_t isConstructed() const ///< SCA MISRA-C++:2008 Justified Rule 10-3-1 and Defected Rule 9-3-3 | |
54 | { | ||
55 | 3574 | return Parent::isConstructed(); | |
56 | } | ||
57 | |||
58 | /** | ||
59 | * @copydoc eoos::api::List::add(T const&) | ||
60 | */ | ||
61 | 182 | virtual bool_t add(T const& element) | |
62 | { | ||
63 | 182 | size_t const lenght( getLength() ); | |
64 |
2/2✓ Branch 1 taken 89 times.
✓ Branch 2 taken 6 times.
|
182 | return isConstructed() ? addNode(static_cast<int32_t>(lenght), element) : false; |
65 | } | ||
66 | |||
67 | /** | ||
68 | * @copydoc eoos::api::List::add(int32_t,T const&) | ||
69 | */ | ||
70 | 56 | virtual bool_t add(int32_t const index, T const& element) | |
71 | { | ||
72 |
1/2✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
|
56 | return isConstructed() ? addNode(index, element) : false; |
73 | } | ||
74 | |||
75 | /** | ||
76 | * @copydoc eoos::api::List::clear() | ||
77 | */ | ||
78 | 157 | virtual void clear() | |
79 | { | ||
80 |
2/2✓ Branch 1 taken 76 times.
✓ Branch 2 taken 6 times.
|
157 | if( isConstructed() ) |
81 | { | ||
82 | 145 | size_t lenght( getLength() ); | |
83 | 122 | while(true) | |
84 | { | ||
85 |
2/2✓ Branch 0 taken 76 times.
✓ Branch 1 taken 65 times.
|
267 | if(lenght == 0U) |
86 | { | ||
87 | 145 | break; | |
88 | } | ||
89 | 122 | Node* const node( getNodeByIndex(0) ); | |
90 | 122 | static_cast<void>( removeNode(node) ); | |
91 | 122 | lenght -= 1U; | |
92 | } | ||
93 | } | ||
94 | 157 | } | |
95 | |||
96 | /** | ||
97 | * @copydoc eoos::api::List::removeFirst() | ||
98 | */ | ||
99 | 8 | virtual bool_t removeFirst() | |
100 | { | ||
101 | 8 | return remove(0); | |
102 | } | ||
103 | |||
104 | /** | ||
105 | * @copydoc eoos::api::List::removeLast() | ||
106 | */ | ||
107 | 8 | virtual bool_t removeLast() | |
108 | { | ||
109 | 8 | size_t const length( getLength() ); | |
110 | 8 | return remove( static_cast<int32_t>(length) - 1 ); | |
111 | } | ||
112 | |||
113 | /** | ||
114 | * @copydoc eoos::api::Queue::remove() | ||
115 | */ | ||
116 | 24 | virtual bool_t remove() | |
117 | { | ||
118 | 24 | return remove(0); | |
119 | } | ||
120 | |||
121 | /** | ||
122 | * @copydoc eoos::api::List::remove(int32_t) | ||
123 | */ | ||
124 | 112 | virtual bool_t remove(int32_t const index) | |
125 | { | ||
126 |
2/2✓ Branch 1 taken 54 times.
✓ Branch 2 taken 2 times.
|
112 | return isConstructed() ? removeNode( getNodeByIndex(index) ) : false; |
127 | } | ||
128 | |||
129 | /** | ||
130 | * @copydoc eoos::api::List::removeElement(T const&) | ||
131 | */ | ||
132 | 16 | virtual bool_t removeElement(T const& element) | |
133 | { | ||
134 |
1/2✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
|
16 | return isConstructed() ? removeNode( getNodeByElement(element) ) : false; |
135 | } | ||
136 | |||
137 | /** | ||
138 | * @copydoc eoos::api::Queue::peek(T const&) | ||
139 | */ | ||
140 | 32 | virtual T& peek() | |
141 | { | ||
142 | 32 | return get(0); | |
143 | } | ||
144 | |||
145 | /** | ||
146 | * @copydoc eoos::api::List::getFirst() | ||
147 | */ | ||
148 | 8 | virtual T& getFirst() | |
149 | { | ||
150 | 8 | return get(0); | |
151 | } | ||
152 | |||
153 | /** | ||
154 | * @copydoc eoos::api::List::getLast() | ||
155 | */ | ||
156 | 8 | virtual T& getLast() | |
157 | { | ||
158 | 8 | size_t const length( getLength() ); | |
159 | 8 | return get( static_cast<int32_t>(length) - 1 ); | |
160 | } | ||
161 | |||
162 | /** | ||
163 | * @copydoc eoos::api::List::get() | ||
164 | */ | ||
165 | 326 | virtual T& get(int32_t index) | |
166 | { | ||
167 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 162 times.
|
326 | if( !isConstructed() ) |
168 | { | ||
169 | 4 | return illegal_; ///< SCA MISRA-C++:2008 Justified Rule 9-3-2 | |
170 | } | ||
171 | 322 | Node* const node( getNodeByIndex(index) ); | |
172 |
2/2✓ Branch 0 taken 92 times.
✓ Branch 1 taken 70 times.
|
322 | return (node != NULLPTR) ? node->getElement() : illegal_; |
173 | } | ||
174 | |||
175 | /** | ||
176 | * @copydoc eoos::api::Collection::getLength() | ||
177 | * | ||
178 | * @todo Re-implement to return value of a member variable; | ||
179 | */ | ||
180 | 2287 | virtual size_t getLength() const | |
181 | { | ||
182 | 2287 | size_t length( 0U ); | |
183 |
2/2✓ Branch 1 taken 1161 times.
✓ Branch 2 taken 12 times.
|
2287 | if( isConstructed() ) |
184 | { | ||
185 |
2/2✓ Branch 0 taken 942 times.
✓ Branch 1 taken 219 times.
|
2263 | length = (last_ == NULLPTR) ? 0U : ( static_cast<size_t>(last_->getIndex()) + 1U); |
186 | } | ||
187 | 2287 | return length; | |
188 | } | ||
189 | |||
190 | /** | ||
191 | * @copydoc eoos::api::Collection::isEmpty() | ||
192 | */ | ||
193 | 218 | virtual bool_t isEmpty() const | |
194 | { | ||
195 | 218 | bool_t res( true ); | |
196 |
2/2✓ Branch 1 taken 103 times.
✓ Branch 2 taken 6 times.
|
218 | if( isConstructed() ) |
197 | { | ||
198 | 206 | res =(last_ == NULLPTR) ? true : false; | |
199 | } | ||
200 | 218 | return res; | |
201 | } | ||
202 | |||
203 | /** | ||
204 | * @copydoc eoos::api::IllegalValue::getIllegal() | ||
205 | */ | ||
206 | 36 | virtual T const& getIllegal() const | |
207 | { | ||
208 | 36 | return illegal_; | |
209 | } | ||
210 | |||
211 | /** | ||
212 | * @copydoc eoos::api::IllegalValue::setIllegal(T const&) | ||
213 | */ | ||
214 | 20 | virtual void setIllegal(T const& value) | |
215 | { | ||
216 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
20 | if( isConstructed() ) |
217 | { | ||
218 | 20 | illegal_ = value; | |
219 | } | ||
220 | } | ||
221 | |||
222 | /** | ||
223 | * @copydoc eoos::api::IllegalValue::isIllegal(T const&) | ||
224 | */ | ||
225 | 36 | virtual bool_t isIllegal(T const& value) const | |
226 | { | ||
227 | 36 | bool_t res( false ); | |
228 |
1/2✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
|
36 | if( isConstructed() ) |
229 | { | ||
230 | 36 | res = illegal_ == value; | |
231 | } | ||
232 | 36 | return res; | |
233 | } | ||
234 | |||
235 | /** | ||
236 | * @copydoc eoos::api::List::getIndexOf(T const&) | ||
237 | */ | ||
238 | 32 | virtual int32_t getIndexOf(T const& element) const | |
239 | { | ||
240 | 32 | Node* const node( getNodeByElement(element) ); | |
241 |
2/2✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
|
32 | return (node != NULLPTR) ? node->getIndex() : api::List<T>::ERROR_INDEX; |
242 | } | ||
243 | |||
244 | /** | ||
245 | * @copydoc eoos::api::List::isIndex(T const&) | ||
246 | */ | ||
247 | 765 | virtual bool_t isIndex(int32_t const index) const | |
248 | { | ||
249 | 765 | bool_t res( false ); | |
250 |
2/2✓ Branch 0 taken 383 times.
✓ Branch 1 taken 6 times.
|
765 | if( 0 <= index ) |
251 | { | ||
252 |
2/2✓ Branch 1 taken 296 times.
✓ Branch 2 taken 87 times.
|
753 | if( static_cast<size_t>(index) < getLength() ) |
253 | { | ||
254 | 579 | res = true; | |
255 | } | ||
256 | } | ||
257 | 765 | return res; | |
258 | } | ||
259 | |||
260 | /** | ||
261 | * @copydoc eoos::api::Iterable::getIterator() | ||
262 | */ | ||
263 | 28 | virtual api::Iterator<T>* getIterator() ///< SCA MISRA-C++:2008 Defected Rule 9-3-3 | |
264 | { | ||
265 | 28 | return getListIterator(0); | |
266 | } | ||
267 | |||
268 | protected: | ||
269 | |||
270 | /** | ||
271 | * @brief Constructor. | ||
272 | */ | ||
273 | 9 | AbstractList() | |
274 | : NonCopyable<A>() | ||
275 | , api::List<T>() | ||
276 | , api::Queue<T>() | ||
277 | , api::Iterable<T>() | ||
278 | 9 | , illegal_() | |
279 | 9 | , last_(NULLPTR) | |
280 | 9 | , count_(0) { | |
281 | 9 | } | |
282 | |||
283 | /** | ||
284 | * @brief Constructor. | ||
285 | * | ||
286 | * @note A passed element must be copied to an internal data structure of | ||
287 | * this class by calling a copy constructor so that the element | ||
288 | * might be invalidated after the function called. | ||
289 | * | ||
290 | * @param illegal An illegal element. | ||
291 | */ | ||
292 | 134 | AbstractList(T const& illegal) | |
293 | : NonCopyable<A>() | ||
294 | , api::List<T>() | ||
295 | , api::Queue<T>() | ||
296 | , api::Iterable<T>() | ||
297 | 134 | , illegal_(illegal) | |
298 | 134 | , last_(NULLPTR) | |
299 | 134 | , count_(0) { | |
300 | 134 | } | |
301 | |||
302 | /** | ||
303 | * @brief Inserts new element to the specified position in this list. | ||
304 | * | ||
305 | * Given element will be copied to self nodes structure by a copy constructor calling. | ||
306 | * | ||
307 | * @param index Position in this list. | ||
308 | * @param element Inserting element. | ||
309 | * @return True if element is inserted. | ||
310 | * | ||
311 | * @todo Shall re-implemented according MISRA-C++:2008 Rule 6–6–5 as the delete operator is used. | ||
312 | */ | ||
313 | 226 | bool_t addNode(int32_t const index, T const& element) | |
314 | { | ||
315 |
2/2✓ Branch 1 taken 4 times.
✓ Branch 2 taken 113 times.
|
226 | if(isIndexOutOfBounds(index)) |
316 | { | ||
317 | 8 | return false; | |
318 | } | ||
319 |
2/5✓ Branch 1 taken 103 times.
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
|
218 | Node* const node( new Node(element) ); |
320 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 111 times.
|
218 | if( node == NULLPTR ) |
321 | { | ||
322 | 4 | return false; | |
323 | } | ||
324 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 111 times.
|
214 | if( !node->isConstructed() ) |
325 | { ///< UT Justified Branch: HW dependency | ||
326 | ✗ | delete node; | |
327 | ✗ | return false; | |
328 | } | ||
329 |
2/2✓ Branch 0 taken 46 times.
✓ Branch 1 taken 65 times.
|
214 | if(last_ == NULLPTR) |
330 | { | ||
331 | 87 | last_ = node; | |
332 | 87 | count_++; | |
333 | 87 | return true; | |
334 | } | ||
335 |
2/2✓ Branch 0 taken 59 times.
✓ Branch 1 taken 6 times.
|
127 | if(index > 0) |
336 | { | ||
337 | 115 | Node* const after( getNodeByIndex(index - 1) ); | |
338 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 59 times.
|
115 | if(after == NULLPTR) |
339 | { ///< UT Justified Branch: SW dependency | ||
340 | ✗ | delete node; | |
341 | ✗ | return false; | |
342 | } | ||
343 | 115 | after->insertAfter(node); | |
344 |
2/2✓ Branch 0 taken 53 times.
✓ Branch 1 taken 6 times.
|
115 | if(after == last_) |
345 | { | ||
346 | 103 | last_ = node; | |
347 | } | ||
348 | } | ||
349 | else | ||
350 | { | ||
351 | 12 | Node* const before( getNodeByIndex(0) ); | |
352 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
12 | if(before == NULLPTR) |
353 | { ///< UT Justified Branch: SW dependency | ||
354 | ✗ | delete node; | |
355 | ✗ | return false; | |
356 | } | ||
357 | 12 | before->insertBefore(node); | |
358 | } | ||
359 | 127 | count_++; | |
360 | 127 | return true; | |
361 | } | ||
362 | |||
363 | /** | ||
364 | * @brief Returns a node of this list by index. | ||
365 | * | ||
366 | * @param index Position in this list. | ||
367 | * @return Pointer to the node of this list. | ||
368 | */ | ||
369 | 733 | Node* getNodeByIndex(int32_t const index) | |
370 | { | ||
371 |
2/2✓ Branch 1 taken 89 times.
✓ Branch 2 taken 284 times.
|
733 | if( !isIndex(index) ) |
372 | { | ||
373 | 178 | return NULLPTR; | |
374 | } | ||
375 | 555 | size_t lenght( getLength() ); | |
376 |
2/2✓ Branch 0 taken 145 times.
✓ Branch 1 taken 139 times.
|
555 | if( static_cast<size_t>(index) == (lenght - 1U) ) |
377 | { | ||
378 | 281 | return last_; | |
379 | } | ||
380 | 274 | Node* node( last_->getNext() ); | |
381 |
2/2✓ Branch 0 taken 60 times.
✓ Branch 1 taken 139 times.
|
394 | for(int32_t i(0); i<index; i++) |
382 | { | ||
383 | 120 | node = node->getNext(); | |
384 | } | ||
385 | 274 | return node; | |
386 | } | ||
387 | |||
388 | /** | ||
389 | * @brief Returns a node of this list by element. | ||
390 | * | ||
391 | * @param element Reference to element. | ||
392 | * @return Pointer to the node of this list. | ||
393 | */ | ||
394 | 48 | Node* getNodeByElement(T const& element) const | |
395 | { | ||
396 | 48 | Node* res( NULLPTR ); | |
397 | 48 | size_t const len( getLength() ); | |
398 |
2/2✓ Branch 0 taken 20 times.
✓ Branch 1 taken 4 times.
|
48 | if(len != 0U) |
399 | { | ||
400 | 40 | Node* node( last_->getNext() ); | |
401 |
2/2✓ Branch 0 taken 66 times.
✓ Branch 1 taken 4 times.
|
140 | for(size_t i(0U); i<len; i++) |
402 | { | ||
403 |
2/2✓ Branch 1 taken 50 times.
✓ Branch 2 taken 16 times.
|
132 | if(element != node->getElement()) |
404 | { | ||
405 | 100 | node = node->getNext(); | |
406 | 100 | continue; | |
407 | } | ||
408 | 32 | res = node; | |
409 | 32 | break; | |
410 | } ///< UT Justified Line: Compiler dependency | ||
411 | } | ||
412 | 48 | return res; | |
413 | } | ||
414 | |||
415 | /** | ||
416 | * @brief Removes a node of this list. | ||
417 | * | ||
418 | * @param node Pointer to node. | ||
419 | * @return True if a node is removed successfully. | ||
420 | */ | ||
421 | 246 | bool_t removeNode(Node* const node) | |
422 | { | ||
423 |
2/2✓ Branch 0 taken 16 times.
✓ Branch 1 taken 111 times.
|
246 | if(node == NULLPTR) |
424 | { | ||
425 | 32 | return false; | |
426 | } | ||
427 |
2/2✓ Branch 0 taken 51 times.
✓ Branch 1 taken 60 times.
|
214 | if(node == last_) |
428 | { | ||
429 |
2/2✓ Branch 1 taken 46 times.
✓ Branch 2 taken 5 times.
|
97 | if(getLength() == 1U) |
430 | { | ||
431 | 87 | last_ = NULLPTR; | |
432 | } | ||
433 | else | ||
434 | { | ||
435 | 10 | last_ = last_->getPrevious(); | |
436 | } | ||
437 | } | ||
438 |
1/2✓ Branch 0 taken 111 times.
✗ Branch 1 not taken.
|
214 | delete node; |
439 | 214 | count_++; | |
440 | 214 | return true; | |
441 | } | ||
442 | |||
443 | /** | ||
444 | * @brief Tests if index is out of this list bounds. | ||
445 | * | ||
446 | * @param index Checking position in this list. | ||
447 | * @return True if index is outed. | ||
448 | */ | ||
449 | 300 | bool_t isIndexOutOfBounds(int32_t const index) const | |
450 | { | ||
451 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 150 times.
|
300 | if( index < 0 ) |
452 | { | ||
453 | 8 | return true; | |
454 | } ///< UT Justified Line: Compiler dependency | ||
455 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 2 taken 147 times.
|
292 | else if( static_cast<size_t>(index) > getLength() ) |
456 | { | ||
457 | 6 | return true; | |
458 | } ///< UT Justified Line: Compiler dependency | ||
459 | else | ||
460 | { | ||
461 | 286 | return false; | |
462 | } | ||
463 | } | ||
464 | |||
465 | /** | ||
466 | * @brief Returns reference to self data value. | ||
467 | * | ||
468 | * @return Data value. | ||
469 | */ | ||
470 | 74 | uint32_t& getReferenceToCount() | |
471 | { | ||
472 | 74 | return count_; ///< SCA MISRA-C++:2008 Justified Rule 9-3-2 | |
473 | } | ||
474 | |||
475 | /** | ||
476 | * @brief Returns reference to self data value. | ||
477 | * | ||
478 | * @return Data value. | ||
479 | */ | ||
480 | 74 | Node*& getReferenceToLast() | |
481 | { | ||
482 | 74 | return last_; ///< SCA MISRA-C++:2008 Justified Rule 9-3-2 | |
483 | } | ||
484 | |||
485 | /** | ||
486 | * @brief Returns reference to self data value. | ||
487 | * | ||
488 | * @return Data value. | ||
489 | */ | ||
490 | 37 | T& getReferenceToIllegal() | |
491 | { | ||
492 | 37 | return illegal_; ///< SCA MISRA-C++:2008 Justified Rule 9-3-2 | |
493 | } | ||
494 | |||
495 | private: | ||
496 | |||
497 | /** | ||
498 | * @brief Illegal element of this list. | ||
499 | */ | ||
500 | mutable T illegal_; | ||
501 | |||
502 | /** | ||
503 | * @brief Last node of this list. | ||
504 | */ | ||
505 | Node* last_; | ||
506 | |||
507 | /** | ||
508 | * @brief Number of changes in this list. | ||
509 | */ | ||
510 | uint32_t count_; | ||
511 | |||
512 | }; | ||
513 | |||
514 | } // namespace lib | ||
515 | } // namespace eoos | ||
516 | #endif // LIB_ABSTRACTLIST_HPP_ | ||
517 |