814 lines
22 KiB
C++
814 lines
22 KiB
C++
//
|
|
// Created by Patrick Maschek on 19.01.2024.
|
|
//
|
|
|
|
#ifndef UDIFF_CONST_LIST_H_
|
|
#define UDIFF_CONST_LIST_H_
|
|
|
|
#include <concepts>
|
|
#include <functional>
|
|
#include <initializer_list>
|
|
#include <iterator>
|
|
|
|
namespace cc {
|
|
|
|
template<typename D>
|
|
class const_list_node;
|
|
|
|
template<typename Node>
|
|
class const_list;
|
|
|
|
template<typename N, bool _const>
|
|
class _const_list_iterator {
|
|
|
|
public:
|
|
using node_N = const_list_node<N>;
|
|
using const_node_N = const const_list_node<N>;
|
|
|
|
using node_base_type = std::conditional<_const, const_node_N, node_N>::type;
|
|
using node_type = std::conditional<_const, const N, N>::type;
|
|
|
|
using difference_type = std::ptrdiff_t;
|
|
using value_type = node_type;
|
|
using pointer = value_type*;
|
|
using reference = value_type&;
|
|
using iterator_category = std::bidirectional_iterator_tag;
|
|
|
|
node_base_type* _node = nullptr;
|
|
|
|
constexpr _const_list_iterator() noexcept = default;
|
|
constexpr explicit _const_list_iterator(node_base_type *node) noexcept : _node(node) {}
|
|
|
|
template<bool _other_const, std::enable_if_t<_const || (_other_const == _const), bool> = true>
|
|
constexpr _const_list_iterator(const _const_list_iterator<N, _other_const>& other) noexcept
|
|
: _node(other._node) {}
|
|
|
|
constexpr node_type& operator*() const noexcept { return *dynamic_cast<node_type*>(_node); }
|
|
constexpr node_type* operator->() const noexcept { return dynamic_cast<node_type*>(_node); }
|
|
|
|
constexpr _const_list_iterator &operator++() noexcept { _node = _node->_next; return *this; }
|
|
constexpr _const_list_iterator &operator--() noexcept { _node = _node->_prev; return *this; }
|
|
constexpr _const_list_iterator operator++(int) noexcept { auto tmp = *this; _node = _node->_next; return tmp; }
|
|
constexpr _const_list_iterator operator--(int) noexcept { auto tmp = *this; _node = _node->_prev; return tmp; }
|
|
|
|
template<bool _const_other>
|
|
[[nodiscard]] constexpr bool operator==(const _const_list_iterator<N, _const_other> &other) const noexcept { return _node == other._node; }
|
|
|
|
private:
|
|
constexpr _const_list_iterator<N, false> _const_cast() const noexcept
|
|
requires (_const)
|
|
{ return _const_list_iterator<N, false>(const_cast<node_N*>(_node)); }
|
|
|
|
friend class const_list<N>;
|
|
};
|
|
|
|
template<typename Node>
|
|
class const_list {
|
|
private:
|
|
static consteval void asserts() {
|
|
static_assert(std::is_base_of_v<const_list_node<Node>, Node>, "Can only create const_list with elements derived from const_list_node");
|
|
}
|
|
|
|
public:
|
|
|
|
using value_type = Node;
|
|
using size_type = std::size_t;
|
|
using difference_type = std::ptrdiff_t;
|
|
using reference = value_type&;
|
|
using const_reference = const value_type&;
|
|
using pointer = value_type *;
|
|
using const_pointer = const value_type *;
|
|
using iterator = _const_list_iterator<Node, false>;
|
|
using const_iterator = _const_list_iterator<Node, true>;
|
|
using reverse_iterator = std::reverse_iterator<iterator>;
|
|
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
|
|
|
|
private:
|
|
const_list_node<Node> _tail { this };
|
|
|
|
std::size_t _size = 0;
|
|
|
|
public:
|
|
|
|
constexpr const_list() noexcept { asserts(); };
|
|
constexpr const_list(const const_list&) = delete;
|
|
constexpr const_list(const_list&& other) noexcept;
|
|
constexpr const_list(std::initializer_list<std::reference_wrapper<value_type>> init) noexcept;
|
|
|
|
constexpr ~const_list();
|
|
|
|
constexpr const_list& operator=(const const_list&) = delete;
|
|
constexpr const_list& operator=(const_list&& other) noexcept;
|
|
constexpr const_list& operator=(std::initializer_list<std::reference_wrapper<value_type>> init) noexcept;
|
|
|
|
constexpr void assign(std::initializer_list<std::reference_wrapper<value_type>> init) noexcept;
|
|
|
|
[[nodiscard]] constexpr reference front() noexcept { return *dynamic_cast<Node*>(_tail._next); }
|
|
[[nodiscard]] constexpr const_reference front() const noexcept { return *dynamic_cast<Node*>(_tail._next); }
|
|
|
|
[[nodiscard]] constexpr reference back() noexcept { return *dynamic_cast<Node*>(_tail._prev); }
|
|
[[nodiscard]] constexpr const_reference back() const noexcept { return *dynamic_cast<Node*>(_tail._prev); }
|
|
|
|
[[nodiscard]] constexpr iterator begin() noexcept { return iterator(_tail._next); };
|
|
[[nodiscard]] constexpr const_iterator begin() const noexcept { return const_iterator(_tail._next); };
|
|
[[nodiscard]] constexpr const_iterator cbegin() const noexcept { return const_iterator(_tail._next); };
|
|
|
|
[[nodiscard]] constexpr iterator end() noexcept { return iterator(&_tail); };
|
|
[[nodiscard]] constexpr const_iterator end() const noexcept { return const_iterator(&_tail); };
|
|
[[nodiscard]] constexpr const_iterator cend() const noexcept { return const_iterator(&_tail); };
|
|
|
|
[[nodiscard]] constexpr reverse_iterator rbegin() noexcept { return std::reverse_iterator<iterator>(end()); };
|
|
[[nodiscard]] constexpr const_reverse_iterator rbegin() const noexcept { return std::reverse_iterator<const_iterator>(end()); };
|
|
[[nodiscard]] constexpr const_reverse_iterator crbegin() const noexcept { return std::reverse_iterator<const_iterator>(end()); };
|
|
|
|
[[nodiscard]] constexpr reverse_iterator rend() noexcept { return std::reverse_iterator<iterator>(begin()); };
|
|
[[nodiscard]] constexpr const_reverse_iterator rend() const noexcept { return std::reverse_iterator<const_iterator>(begin()); };
|
|
[[nodiscard]] constexpr const_reverse_iterator crend() const noexcept { return std::reverse_iterator<const_iterator>(begin()); };
|
|
|
|
[[nodiscard]] constexpr bool empty() const noexcept { return _size == 0; }
|
|
[[nodiscard]] constexpr size_type size() const noexcept { return _size; }
|
|
[[nodiscard]] constexpr size_type max_size() const noexcept { return SIZE_MAX; }
|
|
|
|
constexpr void clear() noexcept;
|
|
|
|
constexpr iterator insert(const_iterator pos, value_type& value) noexcept;
|
|
constexpr iterator insert(const_list::const_iterator pos, std::initializer_list<std::reference_wrapper<value_type>> values) noexcept;
|
|
|
|
constexpr iterator erase(const_list::const_iterator pos) noexcept;
|
|
constexpr iterator erase(const_list::const_iterator first, const_list::const_iterator last) noexcept;
|
|
|
|
constexpr void push_back(value_type& value) noexcept;
|
|
constexpr void pop_back() noexcept;
|
|
|
|
constexpr void push_front(value_type& value) noexcept;
|
|
constexpr void pop_front() noexcept;
|
|
|
|
constexpr void swap(const_list& other) noexcept;
|
|
|
|
constexpr void merge(const_list& other);
|
|
constexpr void merge(const_list&& other);
|
|
template<typename Compare>
|
|
constexpr void merge(const_list& other, Compare comp);
|
|
template<typename Compare>
|
|
constexpr void merge(const_list&& other, Compare comp);
|
|
|
|
constexpr void splice(const_iterator pos, const_list& other);
|
|
constexpr void splice(const_iterator pos, const_list&& other);
|
|
constexpr void splice(const_iterator pos, const_list& other, const_iterator it);
|
|
constexpr void splice(const_iterator pos, const_list&& other, const_iterator it);
|
|
constexpr void splice(const_iterator pos, const_list& other, const_iterator first, const_iterator last);
|
|
constexpr void splice(const_iterator pos, const_list&& other, const_iterator first, const_iterator last);
|
|
|
|
constexpr size_type remove(const value_type& value) noexcept;
|
|
template<typename UnaryPredicate>
|
|
constexpr size_type remove_if(UnaryPredicate p);
|
|
|
|
constexpr void reverse() noexcept;
|
|
|
|
constexpr size_type unique();
|
|
template<typename BinaryPredicate>
|
|
constexpr size_type unique(BinaryPredicate p);
|
|
|
|
constexpr void sort();
|
|
template<typename Compare>
|
|
constexpr void sort(Compare comp);
|
|
|
|
};
|
|
|
|
template<typename D>
|
|
class const_list_node {
|
|
private:
|
|
static consteval void asserts() {
|
|
static_assert(std::is_base_of_v<const_list_node<D>, D>, "Template parameter has to be a subclass of const_list_node<*self*>");
|
|
}
|
|
|
|
private:
|
|
const_list_node *_prev = this;
|
|
const_list_node *_next = this;
|
|
const_list<D> *_owner = nullptr;
|
|
|
|
void (*_delete_cb)() = nullptr;
|
|
|
|
public:
|
|
constexpr const_list_node() noexcept { asserts(); }
|
|
constexpr const_list_node(const const_list_node& other) noexcept;
|
|
constexpr const_list_node(const_list_node&& other) noexcept;
|
|
virtual constexpr ~const_list_node();
|
|
|
|
constexpr const_list_node<D>& operator=(const const_list_node& other) noexcept;
|
|
constexpr const_list_node<D>& operator=(const_list_node&& other) noexcept;
|
|
|
|
protected:
|
|
constexpr void on_delete(void (*cb)()) noexcept;
|
|
|
|
private:
|
|
constexpr explicit const_list_node(const_list<D> *owner) : _owner(owner) { asserts(); };
|
|
|
|
constexpr void push_before(const_list_node *node) noexcept;
|
|
constexpr void unlink() noexcept;
|
|
|
|
template<typename N, bool c>
|
|
friend class _const_list_iterator;
|
|
friend class const_list<D>;
|
|
};
|
|
|
|
template<typename N1, typename N2>
|
|
constexpr bool operator==(const const_list<N1>& lhs,
|
|
const const_list<N2>& rhs)
|
|
{
|
|
return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
|
|
}
|
|
|
|
template<typename N1, typename N2>
|
|
constexpr auto operator<=>(const const_list<N1>& lhs,
|
|
const const_list<N2>& rhs)
|
|
{
|
|
return std::lexicographical_compare_three_way(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
|
|
}
|
|
|
|
template<typename N>
|
|
constexpr void swap(const const_list<N>& lhs,
|
|
const const_list<N>& rhs)
|
|
{
|
|
lhs.swap(rhs);
|
|
}
|
|
|
|
template<typename N>
|
|
constexpr const_list<N>::size_type erase(const_list<N>& c, const N& value)
|
|
{
|
|
c.remove(value);
|
|
}
|
|
|
|
template<typename N, typename Pred>
|
|
constexpr const_list<N>::size_type erase(const_list<N>& c, Pred pred)
|
|
{
|
|
c.remove_if(pred);
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::const_list(const_list &&other) noexcept
|
|
: _size(other._size)
|
|
{
|
|
asserts();
|
|
|
|
for (auto& node : other) {
|
|
node._owner = this;
|
|
}
|
|
|
|
_tail = std::move(other._tail);
|
|
_tail._owner = this;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::const_list(std::initializer_list<std::reference_wrapper<value_type>> init) noexcept
|
|
: _tail(this),
|
|
_size(init.size())
|
|
{
|
|
asserts();
|
|
|
|
assign(init);
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::~const_list()
|
|
{
|
|
clear();
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node> &const_list<Node>::operator=(const_list &&other) noexcept
|
|
{
|
|
for (auto& node : other) {
|
|
node._owner = this;
|
|
}
|
|
|
|
_tail = std::move(other._tail);
|
|
_tail._owner = this;
|
|
_size = other._size;
|
|
|
|
return *this;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node> &const_list<Node>::operator=(std::initializer_list<std::reference_wrapper<value_type>> init) noexcept
|
|
{
|
|
assign(init);
|
|
return *this;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::assign(std::initializer_list<std::reference_wrapper<value_type>> init) noexcept
|
|
{
|
|
clear();
|
|
|
|
insert(begin(), init);
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::clear() noexcept
|
|
{
|
|
for (auto node = _tail._next; _tail._next != std::addressof(_tail); ) {
|
|
auto next = node->_next;
|
|
node->unlink();
|
|
node = next;
|
|
}
|
|
|
|
_size = 0;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::iterator const_list<Node>::insert(const_iterator pos, value_type &value) noexcept
|
|
{
|
|
auto it = pos._const_cast();
|
|
|
|
it->push_before(value);
|
|
++_size;
|
|
|
|
return --it;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::iterator const_list<Node>::insert(const_list::const_iterator pos,
|
|
std::initializer_list<std::reference_wrapper<value_type>> values) noexcept
|
|
{
|
|
auto it = pos._const_cast();
|
|
|
|
for (auto& value : values) {
|
|
// it's operator-> may fail as it could be the tail node
|
|
it._node->push_before(std::addressof(value.get()));
|
|
}
|
|
|
|
_size += values.size();
|
|
|
|
return it;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::iterator const_list<Node>::erase(const_list::const_iterator pos) noexcept
|
|
{
|
|
auto it = pos._const_cast();
|
|
auto next = std::next(it);
|
|
|
|
it->unlink();
|
|
--_size;
|
|
|
|
return next;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::iterator const_list<Node>::erase(const_list::const_iterator first, const_list::const_iterator last) noexcept
|
|
{
|
|
auto nc_last = last._const_cast();
|
|
|
|
if (first == last) {
|
|
return nc_last;
|
|
}
|
|
|
|
auto next = (last == end() ? end() : std::next(nc_last));
|
|
for (auto it = first._const_cast()._node; it != next._node; ) {
|
|
auto n = it->_next;
|
|
|
|
it->unlink();
|
|
--_size;
|
|
|
|
it = n;
|
|
}
|
|
|
|
return next;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::push_back(value_type &value) noexcept
|
|
{
|
|
_tail.push_before(std::addressof(value));
|
|
++_size;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::pop_back() noexcept
|
|
{
|
|
_tail._prev->unlink();
|
|
--_size;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::push_front(value_type &value) noexcept
|
|
{
|
|
_tail._next->push_before(std::addressof(value));
|
|
++_size;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::pop_front() noexcept
|
|
{
|
|
_tail._next->unlink();
|
|
--_size;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::swap(const_list &other) noexcept
|
|
{
|
|
auto tmp = _tail;
|
|
_tail = other._tail;
|
|
other._tail = tmp;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::merge(const_list &other)
|
|
{
|
|
merge(std::forward<decltype(other)>(other), [](const value_type& v1, const value_type& v2) -> bool { return v1 < v2; });
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::merge(const_list &&other)
|
|
{
|
|
merge(std::forward<decltype(other)>(other), [](const value_type& v1, const value_type& v2) -> bool { return v1 < v2; });
|
|
}
|
|
|
|
template<typename Node>
|
|
template<typename Compare>
|
|
constexpr void const_list<Node>::merge(const_list &other, Compare comp)
|
|
{
|
|
if (std::addressof(other) == this) return;
|
|
|
|
auto first1 = begin();
|
|
auto last1 = end();
|
|
auto first2 = other.begin();
|
|
auto last2 = other.end();
|
|
|
|
while (first1 != last1 && first2 != last2) {
|
|
if (comp(*first2, *first1)) {
|
|
auto next = std::next(first2);
|
|
|
|
first1._node->push_before(first2._node);
|
|
++_size;
|
|
|
|
first2 = next;
|
|
} else {
|
|
++first1;
|
|
}
|
|
}
|
|
|
|
while (first2 != last2) {
|
|
auto next = std::next(first2);
|
|
|
|
_tail.push_before(first2._node);
|
|
++_size;
|
|
|
|
first2 = next;
|
|
}
|
|
|
|
other._size = 0;
|
|
}
|
|
|
|
template<typename Node>
|
|
template<typename Compare>
|
|
constexpr void const_list<Node>::merge(const_list &&other, Compare comp)
|
|
{
|
|
if (std::addressof(other) == this) return;
|
|
|
|
auto first1 = begin();
|
|
auto last1 = end();
|
|
auto first2 = other.begin();
|
|
auto last2 = other.end();
|
|
|
|
while (first1 != last1 && first2 != last2) {
|
|
if (comp(*first2, *first1)) {
|
|
auto next = std::next(first2);
|
|
|
|
first1._node->push_before(first2._node);
|
|
++_size;
|
|
|
|
first2 = next;
|
|
} else {
|
|
++first1;
|
|
}
|
|
}
|
|
|
|
while (first2 != last2) {
|
|
auto next = std::next(first2);
|
|
|
|
_tail.push_before(first2._node);
|
|
++_size;
|
|
|
|
first2 = next;
|
|
}
|
|
|
|
other._size = 0;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::splice(const_list::const_iterator pos, const_list &other)
|
|
{
|
|
if (other._size == 0) return;
|
|
|
|
for (auto& value : other) {
|
|
value._owner = this;
|
|
}
|
|
|
|
auto p = pos._const_cast();
|
|
|
|
p._node->_prev->_next = other._tail._next;
|
|
other._tail._next->_prev = p._node->_prev;
|
|
p._node->_prev = other._tail._prev;
|
|
other._tail._prev->_next = p._node;
|
|
|
|
_size += other._size;
|
|
|
|
other._tail._prev = &other._tail;
|
|
other._tail._next = &other._tail;
|
|
other._size = 0;
|
|
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::splice(const_list::const_iterator pos, const_list &&other)
|
|
{
|
|
if (other._size == 0) return;
|
|
|
|
for (auto& value : other) {
|
|
value._owner = this;
|
|
}
|
|
|
|
auto p = pos._const_cast();
|
|
|
|
p._node->_prev->_next = other._tail->_next;
|
|
p._node->_prev = other._tail->_prev;
|
|
|
|
_size += other._size;
|
|
|
|
other._tail->_prev = &other._tail;
|
|
other._tail->_next = &other._tail;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void
|
|
const_list<Node>::splice(const_list::const_iterator pos, const_list &other, const_list::const_iterator it)
|
|
{
|
|
// if it does point into other, then it has to have a size
|
|
pos._const_cast()._node->push_before(it._const_cast()._node);
|
|
++_size;
|
|
--other._size;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void
|
|
const_list<Node>::splice(const_list::const_iterator pos, const_list &&other, const_list::const_iterator it)
|
|
{
|
|
pos._const_cast()->push_before(it._const_cast()._node);
|
|
++_size;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void
|
|
const_list<Node>::splice(const_list::const_iterator pos, const_list &other, const_list::const_iterator first,
|
|
const_list::const_iterator last)
|
|
{
|
|
auto p = pos._const_cast();
|
|
auto f = first._const_cast();
|
|
auto l = last._const_cast();
|
|
std::size_t dist = 0;
|
|
|
|
for (auto it = f; it != l; ++it) {
|
|
it._node->_owner = this;
|
|
++dist;
|
|
}
|
|
|
|
// we cannot use operator->, since it returns nullptr if it is a tail node
|
|
|
|
auto first_prev = f._node->_prev;
|
|
|
|
p._node->_prev->_next = f._node;
|
|
f._node->_prev->_next = l._node;
|
|
f._node->_prev = p._node->_prev;
|
|
|
|
p._node->_prev = l._node->_prev;
|
|
l._node->_prev->_next = p._node;
|
|
l._node->_prev = first_prev;
|
|
|
|
_size += dist;
|
|
other._size -= dist;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void
|
|
const_list<Node>::splice(const_list::const_iterator pos, const_list &&other, const_list::const_iterator first,
|
|
const_list::const_iterator last)
|
|
{
|
|
auto f = first._const_cast();
|
|
auto l = last._const_cast();
|
|
std::size_t dist = 0;
|
|
|
|
for (auto it = f; it != l; ++it) {
|
|
it->_owner = this;
|
|
++dist;
|
|
}
|
|
|
|
auto first_prev = first->_prev;
|
|
|
|
pos->_prev->_next = f._node;
|
|
f->_prev->_next = l._node;
|
|
f->_prev = pos->_prev;
|
|
|
|
pos->_prev = l->_prev;
|
|
l->_prev->_next = pos._node;
|
|
l->_prev = first_prev;
|
|
|
|
_size += dist;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::size_type const_list<Node>::remove(const value_type &value) noexcept
|
|
{
|
|
// value has to be unique anyway
|
|
if (value._owner == this) {
|
|
const_cast<value_type&>(value).unlink();
|
|
--_size;
|
|
|
|
return 1;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
template<typename Node>
|
|
template<typename UnaryPredicate>
|
|
constexpr const_list<Node>::size_type const_list<Node>::remove_if(UnaryPredicate p)
|
|
{
|
|
auto tail = end();
|
|
size_type nr = 0;
|
|
|
|
for (auto it = begin(); it != tail; ++it) {
|
|
if (p(*it)) {
|
|
it = erase(it);
|
|
++nr;
|
|
--_size;
|
|
}
|
|
}
|
|
|
|
return nr;
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::reverse() noexcept
|
|
{
|
|
auto tail = end();
|
|
|
|
for (auto it = begin(); it != tail; --it) {
|
|
std::swap(it._node->_prev, it._node->_next);
|
|
}
|
|
std::swap(_tail._prev, _tail._next);
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr const_list<Node>::size_type const_list<Node>::unique()
|
|
{
|
|
return unique([](const value_type& n1, const value_type& n2) { return n1 == n2; });
|
|
}
|
|
|
|
template<typename Node>
|
|
template<typename BinaryPredicate>
|
|
constexpr const_list<Node>::size_type const_list<Node>::unique(BinaryPredicate p)
|
|
{
|
|
auto it = begin();
|
|
auto last = end();
|
|
|
|
if (it == last) return 0;
|
|
|
|
const_list to_remove;
|
|
auto next = it;
|
|
while (++next != last) {
|
|
if (p(*it, *next)) {
|
|
to_remove.splice(to_remove.begin(), *this, next);
|
|
} else {
|
|
it = next;
|
|
}
|
|
next = it;
|
|
}
|
|
|
|
return to_remove.size();
|
|
}
|
|
|
|
template<typename Node>
|
|
constexpr void const_list<Node>::sort()
|
|
{
|
|
sort([](const value_type& n1, const value_type& n2) { return n1 < n2; });
|
|
}
|
|
|
|
template<typename Node>
|
|
template<typename Compare>
|
|
constexpr void const_list<Node>::sort(Compare comp)
|
|
{
|
|
auto last = end();
|
|
auto it = begin();
|
|
|
|
const_list sorted;
|
|
auto sorted_end = sorted.end();
|
|
|
|
while (it != last) {
|
|
auto sorted_it = sorted.begin();
|
|
while (sorted_it != sorted_end) {
|
|
if (comp(*it, *sorted_it)) {
|
|
break;
|
|
} else {
|
|
++sorted_it;
|
|
}
|
|
}
|
|
auto sp_it = it;
|
|
++it;
|
|
sorted.splice(sorted_it, *this, sp_it);
|
|
}
|
|
|
|
*this = std::move(sorted);
|
|
}
|
|
|
|
template<typename D>
|
|
constexpr const_list_node<D>::const_list_node(const const_list_node &other) noexcept
|
|
: _delete_cb(other._delete_cb)
|
|
{}
|
|
|
|
template<typename D>
|
|
constexpr const_list_node<D>::const_list_node(const_list_node &&other) noexcept
|
|
: _prev(other._prev),
|
|
_next(other._next),
|
|
_delete_cb(other._delete_cb)
|
|
{
|
|
_prev->_next = this;
|
|
_next->_prev = this;
|
|
|
|
// without this the destructor of other would delete moved nodes
|
|
other._next = std::addressof(other);
|
|
other._prev = std::addressof(other);
|
|
}
|
|
|
|
template<typename D>
|
|
constexpr const_list_node<D>::~const_list_node()
|
|
{
|
|
if (_delete_cb)
|
|
_delete_cb();
|
|
unlink();
|
|
}
|
|
|
|
template<typename D>
|
|
constexpr const_list_node<D> &const_list_node<D>::operator=(const const_list_node &other) noexcept
|
|
{
|
|
return *this;
|
|
}
|
|
|
|
template<typename D>
|
|
constexpr const_list_node<D> &const_list_node<D>::operator=(const_list_node &&other) noexcept
|
|
{
|
|
_prev = other._prev;
|
|
_next = other._next;
|
|
_delete_cb = other._delete_cb;
|
|
|
|
_prev->_next = this;
|
|
_next->_prev = this;
|
|
|
|
// without this the destructor of other would delete moved nodes
|
|
other._next = std::addressof(other);
|
|
other._prev = std::addressof(other);
|
|
|
|
return *this;
|
|
}
|
|
|
|
template<typename D>
|
|
constexpr void const_list_node<D>::on_delete(void (*cb)()) noexcept
|
|
{
|
|
_delete_cb = cb;
|
|
}
|
|
|
|
template<typename D>
|
|
constexpr void const_list_node<D>::unlink() noexcept
|
|
{
|
|
if (_delete_cb)
|
|
_delete_cb();
|
|
|
|
_prev->_next = _next;
|
|
_next->_prev = _prev;
|
|
|
|
_next = this;
|
|
_prev = this;
|
|
|
|
_owner = nullptr;
|
|
}
|
|
|
|
template<typename D>
|
|
constexpr void const_list_node<D>::push_before(const_list_node *node) noexcept
|
|
{
|
|
node->_prev->_next = node->_next;
|
|
node->_next->_prev = node->_prev;
|
|
|
|
node->_prev = _prev;
|
|
node->_next = this;
|
|
|
|
_prev->_next = node;
|
|
_prev = node;
|
|
|
|
node->_owner = _owner;
|
|
}
|
|
|
|
} // cc
|
|
|
|
#endif //UDIFF_CONST_LIST_H_
|