distortos  v0.5.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 
153  bool empty() const
154  {
156  }
157 
163  {
165  }
166 
172  {
174  }
175 
181  {
183  }
184 
190  {
192  }
193 
203  {
204  return UnsortedIntrusiveList::insert(implementation_.findInsertPosition(newElement), newElement);
205  }
206 
211  void pop_back()
212  {
214  }
215 
220  void pop_front()
221  {
223  }
224 
231  void splice(const iterator splicedElement)
232  {
233  UnsortedIntrusiveList::splice(implementation_.findInsertPosition(*splicedElement), splicedElement);
234  }
235 
243  {
245  }
246 
257  static iterator erase(const iterator position)
258  {
259  return UnsortedIntrusiveList::erase(position);
260  }
261 
262  SortedIntrusiveList(const SortedIntrusiveList&) = delete;
264  const SortedIntrusiveList& operator=(const SortedIntrusiveList&) = delete;
265  SortedIntrusiveList& operator=(SortedIntrusiveList&&) = delete;
266 
267 private:
268 
270  struct Implementation : public Compare
271  {
278  constexpr explicit Implementation(const Compare& comparee) :
279  Compare{comparee},
280  intrusiveList{}
281  {
282 
283  }
284 
295  {
296  return std::find_if(intrusiveList.begin(), intrusiveList.end(),
297  [this, &newElement](const_reference& element) -> bool
298  {
299  return this->Compare::operator()(element, newElement);
300  }
301  );
302  }
303 
310  void swap(Implementation& other)
311  {
313  using std::swap;
314  swap(static_cast<Compare&>(*this), static_cast<Compare&>(other));
315  }
316 
317  Implementation(const Implementation&) = delete;
318  Implementation(Implementation&&) = default;
319  const Implementation& operator=(const Implementation&) = delete;
320  Implementation& operator=(Implementation&&) = delete;
321 
324  };
325 
328 };
329 
344 template<typename Compare, typename T, IntrusiveListNode T::* NodePointer, typename U = T>
347 {
348  left.swap(right);
349 }
350 
351 } // namespace estd
352 
353 #endif // ESTD_SORTEDINTRUSIVELIST_HPP_
Collection of useful templates.
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:1035
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:220
U value_type
value linked in the list
Definition: IntrusiveList.hpp:956
void swap(IntrusiveList &other)
Swaps contents with another list.
Definition: IntrusiveList.hpp:1122
void swap(Implementation &other)
Swaps contents with another instance.
Definition: SortedIntrusiveList.hpp:310
iterator end()
Definition: IntrusiveList.hpp:1044
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
typename UnsortedIntrusiveList::reverse_iterator reverse_iterator
reverse iterator of elements on the list
Definition: SortedIntrusiveList.hpp:63
const_iterator end() const
Definition: SortedIntrusiveList.hpp:171
void pop_back()
Unlinks the last element from the list.
Definition: SortedIntrusiveList.hpp:211
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:1175
constexpr Implementation(const Compare &comparee)
Implementation&#39;s constructor.
Definition: SortedIntrusiveList.hpp:278
SortedIntrusiveList class is an IntrusiveList with sorted elements.
Definition: SortedIntrusiveList.hpp:40
const_reference front() const
Definition: SortedIntrusiveList.hpp:189
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
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:327
iterator findInsertPosition(const_reference newElement)
Finds insert position that satisfies sorting criteria.
Definition: SortedIntrusiveList.hpp:294
iterator begin()
Definition: IntrusiveList.hpp:990
const_iterator cbegin() const
Definition: SortedIntrusiveList.hpp:126
UnsortedIntrusiveList intrusiveList
internal unsorted IntrusiveList
Definition: SortedIntrusiveList.hpp:323
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:231
constexpr SortedIntrusiveList(const Compare &compare=Compare{})
SortedIntrusiveList&#39;s constructor.
Definition: SortedIntrusiveList.hpp:80
static iterator erase(const iterator position)
Unlinks the element at position from the list.
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:1080
reference front()
Definition: SortedIntrusiveList.hpp:180
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:1137
void pop_front()
Unlinks the first element from the list.
Definition: IntrusiveList.hpp:1089
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:270
reference front()
Definition: IntrusiveList.hpp:1062
iterator insert(reference newElement)
Links the element in the list, keeping it sorted.
Definition: SortedIntrusiveList.hpp:202
void swap(SortedIntrusiveList &other)
Swaps contents with another list.
Definition: SortedIntrusiveList.hpp:242
void swap(SortedIntrusiveList< Compare, T, NodePointer, U > &left, SortedIntrusiveList< Compare, T, NodePointer, U > &right)
Swaps contents of two lists.
Definition: SortedIntrusiveList.hpp:345
static iterator insert(const iterator position, reference newElement)
Links the element in the list before position.
Definition: IntrusiveList.hpp:1155
std::reverse_iterator< iterator > reverse_iterator
reverse iterator of elements on the list
Definition: IntrusiveList.hpp:947
iterator end()
Definition: SortedIntrusiveList.hpp:162
reference back()
Definition: SortedIntrusiveList.hpp:90
bool empty() const
Definition: SortedIntrusiveList.hpp:153
IntrusiveList template class header.