distortos  v0.7.0
object-oriented C++ RTOS for microcontrollers
SortedIntrusiveList.hpp
Go to the documentation of this file.
1 
12 #ifndef ESTD_SORTEDINTRUSIVELIST_HPP_
13 #define ESTD_SORTEDINTRUSIVELIST_HPP_
14 
15 #include "estd/IntrusiveList.hpp"
16 
17 #include <algorithm>
18 
19 namespace estd
20 {
21 
39 template<typename Compare, typename T, IntrusiveListNode T::* NodePointer, typename U = T>
41 {
42 public:
43 
46 
49 
52 
55 
58 
61 
64 
67 
70 
73 
80  constexpr explicit SortedIntrusiveList(const Compare& compare = Compare{}) :
81  implementation_{compare}
82  {
83 
84  }
85 
91  {
93  }
94 
100  {
102  }
103 
109  {
111  }
112 
118  {
120  }
121 
127  {
129  }
130 
136  {
138  }
139 
144  void clear()
145  {
147  }
148 
154  {
156  }
157 
164  {
166  }
167 
172  bool empty() const
173  {
175  }
176 
182  {
184  }
185 
191  {
193  }
194 
200  {
202  }
203 
209  {
211  }
212 
222  {
223  return UnsortedIntrusiveList::insert(implementation_.findInsertPosition(newElement), newElement);
224  }
225 
230  void pop_back()
231  {
233  }
234 
239  void pop_front()
240  {
242  }
243 
249  {
251  }
252 
258  {
260  }
261 
268  {
270  }
271 
278  {
280  }
281 
288  void splice(const iterator splicedElement)
289  {
290  UnsortedIntrusiveList::splice(implementation_.findInsertPosition(*splicedElement), splicedElement);
291  }
292 
300  {
302  }
303 
314  static iterator erase(const iterator position)
315  {
316  return UnsortedIntrusiveList::erase(position);
317  }
318 
319  SortedIntrusiveList(const SortedIntrusiveList&) = delete;
321  const SortedIntrusiveList& operator=(const SortedIntrusiveList&) = delete;
322  SortedIntrusiveList& operator=(SortedIntrusiveList&&) = delete;
323 
324 private:
325 
327  struct Implementation : public Compare
328  {
335  constexpr explicit Implementation(const Compare& comparee) :
336  Compare{comparee},
337  intrusiveList{}
338  {
339 
340  }
341 
352  {
353  return std::find_if(intrusiveList.begin(), intrusiveList.end(),
354  [this, &newElement](const_reference& element) -> bool
355  {
356  return this->Compare::operator()(element, newElement);
357  }
358  );
359  }
360 
367  void swap(Implementation& other)
368  {
370  using std::swap;
371  swap(static_cast<Compare&>(*this), static_cast<Compare&>(other));
372  }
373 
374  Implementation(const Implementation&) = delete;
375  Implementation(Implementation&&) = default;
376  const Implementation& operator=(const Implementation&) = delete;
377  Implementation& operator=(Implementation&&) = delete;
378 
381  };
382 
384  Implementation implementation_;
385 };
386 
401 template<typename Compare, typename T, IntrusiveListNode T::* NodePointer, typename U = T>
404 {
405  left.swap(right);
406 }
407 
408 } // namespace estd
409 
410 #endif // ESTD_SORTEDINTRUSIVELIST_HPP_
Collection of useful templates.
Definition: DmaChannel.hpp:121
IntrusiveList class is an intrusive circular doubly linked list.
Definition: IntrusiveList.hpp:927
const U * const_pointer
const pointer to value linked in the list
Definition: IntrusiveList.hpp:938
typename UnsortedIntrusiveList::iterator iterator
iterator of elements on the list
Definition: SortedIntrusiveList.hpp:60
U & reference
reference to value linked in the list
Definition: IntrusiveList.hpp:953
const_iterator begin() const
Definition: SortedIntrusiveList.hpp:117
const_iterator cend() const
Definition: IntrusiveList.hpp:1017
typename UnsortedIntrusiveList::pointer pointer
pointer to value linked in the list
Definition: SortedIntrusiveList.hpp:66
bool empty() const
Definition: IntrusiveList.hpp:1054
const_iterator cbegin() const
Definition: IntrusiveList.hpp:1008
U * pointer
pointer to value linked in the list
Definition: IntrusiveList.hpp:950
IntrusiveListIterator< T, NodePointer, U > iterator
iterator of elements on the list
Definition: IntrusiveList.hpp:944
void pop_front()
Unlinks the first element from the list.
Definition: SortedIntrusiveList.hpp:239
const_reverse_iterator crbegin() const
Definition: SortedIntrusiveList.hpp:153
U value_type
value linked in the list
Definition: IntrusiveList.hpp:956
void swap(IntrusiveList &other)
Swaps contents with another list.
Definition: IntrusiveList.hpp:1179
void swap(Implementation &other)
Swaps contents with another instance.
Definition: SortedIntrusiveList.hpp:367
reverse_iterator rend()
Definition: IntrusiveList.hpp:1158
iterator end()
Definition: IntrusiveList.hpp:1063
void clear()
Unlinks all elements from the list.
Definition: SortedIntrusiveList.hpp:144
typename UnsortedIntrusiveList::value_type value_type
value linked in the list
Definition: SortedIntrusiveList.hpp:72
const_reverse_iterator crend() const
Definition: IntrusiveList.hpp:1045
reverse_iterator rend()
Definition: SortedIntrusiveList.hpp:267
typename UnsortedIntrusiveList::reverse_iterator reverse_iterator
reverse iterator of elements on the list
Definition: SortedIntrusiveList.hpp:63
const_iterator end() const
Definition: SortedIntrusiveList.hpp:190
const_reverse_iterator rend() const
Definition: SortedIntrusiveList.hpp:277
reverse_iterator rbegin()
Definition: SortedIntrusiveList.hpp:248
void pop_back()
Unlinks the last element from the list.
Definition: SortedIntrusiveList.hpp:230
void clear()
Unlinks all elements from the list.
Definition: IntrusiveList.hpp:1026
static void splice(const iterator position, const iterator splicedElement)
Transfers the element from one list to another list before position.
Definition: IntrusiveList.hpp:1232
constexpr Implementation(const Compare &comparee)
Implementation's constructor.
Definition: SortedIntrusiveList.hpp:335
SortedIntrusiveList class is an IntrusiveList with sorted elements.
Definition: SortedIntrusiveList.hpp:40
const_reference front() const
Definition: SortedIntrusiveList.hpp:208
typename UnsortedIntrusiveList::const_pointer const_pointer
const pointer to value linked in the list
Definition: SortedIntrusiveList.hpp:54
std::reverse_iterator< const_iterator > const_reverse_iterator
const reverse iterator of elements on the list
Definition: IntrusiveList.hpp:935
const_reverse_iterator crbegin() const
Definition: IntrusiveList.hpp:1035
typename UnsortedIntrusiveList::const_iterator const_iterator
const iterator of elements on the list
Definition: SortedIntrusiveList.hpp:48
const_iterator cend() const
Definition: SortedIntrusiveList.hpp:135
IntrusiveListConstIterator< T, NodePointer, U > const_iterator
const iterator of elements on the list
Definition: IntrusiveList.hpp:932
iterator begin()
Definition: SortedIntrusiveList.hpp:108
Implementation implementation_
internal Implementation object - unsorted IntrusiveList and Compare instance
Definition: SortedIntrusiveList.hpp:384
iterator findInsertPosition(const_reference newElement)
Finds insert position that satisfies sorting criteria.
Definition: SortedIntrusiveList.hpp:351
iterator begin()
Definition: IntrusiveList.hpp:990
const_iterator cbegin() const
Definition: SortedIntrusiveList.hpp:126
UnsortedIntrusiveList intrusiveList
internal unsorted IntrusiveList
Definition: SortedIntrusiveList.hpp:380
reference back()
Definition: IntrusiveList.hpp:972
void splice(const iterator splicedElement)
Transfers the element from another list to this one, keeping it sorted.
Definition: SortedIntrusiveList.hpp:288
constexpr SortedIntrusiveList(const Compare &compare=Compare{})
SortedIntrusiveList's constructor.
Definition: SortedIntrusiveList.hpp:80
static iterator erase(const iterator position)
Unlinks the element at position from the list.
Definition: SortedIntrusiveList.hpp:314
void swap(IntrusiveForwardListNode &left, IntrusiveForwardListNode &right)
Swaps contents of two nodes.
Definition: IntrusiveForwardList.hpp:172
const_reverse_iterator rbegin() const
Definition: SortedIntrusiveList.hpp:257
typename UnsortedIntrusiveList::const_reverse_iterator const_reverse_iterator
const reverse iterator of elements on the list
Definition: SortedIntrusiveList.hpp:51
void pop_back()
Unlinks the last element from the list.
Definition: IntrusiveList.hpp:1099
reference front()
Definition: SortedIntrusiveList.hpp:199
typename UnsortedIntrusiveList::const_reference const_reference
const reference to value linked in the list
Definition: SortedIntrusiveList.hpp:57
const U & const_reference
const reference to value linked in the list
Definition: IntrusiveList.hpp:941
const_reference back() const
Definition: SortedIntrusiveList.hpp:99
static iterator erase(const iterator position)
Unlinks the element at position from the list.
Definition: IntrusiveList.hpp:1194
void pop_front()
Unlinks the first element from the list.
Definition: IntrusiveList.hpp:1108
typename UnsortedIntrusiveList::reference reference
reference to value linked in the list
Definition: SortedIntrusiveList.hpp:69
Implementation struct is used primarily for "Empty Base Optimization" with Compare type.
Definition: SortedIntrusiveList.hpp:327
reference front()
Definition: IntrusiveList.hpp:1081
iterator insert(reference newElement)
Links the element in the list, keeping it sorted.
Definition: SortedIntrusiveList.hpp:221
void swap(SortedIntrusiveList &other)
Swaps contents with another list.
Definition: SortedIntrusiveList.hpp:299
void swap(SortedIntrusiveList< Compare, T, NodePointer, U > &left, SortedIntrusiveList< Compare, T, NodePointer, U > &right)
Swaps contents of two lists.
Definition: SortedIntrusiveList.hpp:402
static iterator insert(const iterator position, reference newElement)
Links the element in the list before position.
Definition: IntrusiveList.hpp:1212
std::reverse_iterator< iterator > reverse_iterator
reverse iterator of elements on the list
Definition: IntrusiveList.hpp:947
const_reverse_iterator crend() const
Definition: SortedIntrusiveList.hpp:163
reverse_iterator rbegin()
Definition: IntrusiveList.hpp:1139
iterator end()
Definition: SortedIntrusiveList.hpp:181
reference back()
Definition: SortedIntrusiveList.hpp:90
bool empty() const
Definition: SortedIntrusiveList.hpp:172
IntrusiveList template class header.