SortedIntrusiveList.hpp

Go to the documentation of this file.

#ifndef ESTD_SORTEDINTRUSIVELIST_HPP_
#define ESTD_SORTEDINTRUSIVELIST_HPP_

#include "estd/IntrusiveList.hpp"

#include <algorithm>

namespace estd
{

template<typename Compare, typename T, IntrusiveListNode T::* NodePointer, typename U = T>
class SortedIntrusiveList
{
public:

    using UnsortedIntrusiveList = IntrusiveList<T, NodePointer, U>;

    using const_iterator = typename UnsortedIntrusiveList::const_iterator;

    using const_reverse_iterator = typename UnsortedIntrusiveList::const_reverse_iterator;

    using const_pointer = typename UnsortedIntrusiveList::const_pointer;

    using const_reference = typename UnsortedIntrusiveList::const_reference;

    using iterator = typename UnsortedIntrusiveList::iterator;

    using reverse_iterator = typename UnsortedIntrusiveList::reverse_iterator;

    using pointer = typename UnsortedIntrusiveList::pointer;

    using reference = typename UnsortedIntrusiveList::reference;

    using value_type = typename UnsortedIntrusiveList::value_type;

    constexpr explicit SortedIntrusiveList(const Compare& compare = Compare{}) :
            implementation_{compare}
    {

    }

    reference back()
    {
        return implementation_.intrusiveList.back();
    }

    const_reference back() const
    {
        return implementation_.intrusiveList.back();
    }

    iterator begin()
    {
        return implementation_.intrusiveList.begin();
    }

    const_iterator begin() const
    {
        return implementation_.intrusiveList.begin();
    }

    const_iterator cbegin() const
    {
        return implementation_.intrusiveList.cbegin();
    }

    const_iterator cend() const
    {
        return implementation_.intrusiveList.cend();
    }

    void clear()
    {
        implementation_.intrusiveList.clear();
    }

    const_reverse_iterator crbegin() const
    {
        return implementation_.intrusiveList.crbegin();
    }

    const_reverse_iterator crend() const
    {
        return implementation_.intrusiveList.crend();
    }

    bool empty() const
    {
        return implementation_.intrusiveList.empty();
    }

    iterator end()
    {
        return implementation_.intrusiveList.end();
    }

    const_iterator end() const
    {
        return implementation_.intrusiveList.end();
    }

    reference front()
    {
        return implementation_.intrusiveList.front();
    }

    const_reference front() const
    {
        return implementation_.intrusiveList.front();
    }

    iterator insert(reference newElement)
    {
        return UnsortedIntrusiveList::insert(implementation_.findInsertPosition(newElement), newElement);
    }

    void pop_back()
    {
        implementation_.intrusiveList.pop_back();
    }

    void pop_front()
    {
        implementation_.intrusiveList.pop_front();
    }

    reverse_iterator rbegin()
    {
        return implementation_.intrusiveList.rbegin();
    }

    const_reverse_iterator rbegin() const
    {
        return implementation_.intrusiveList.rbegin();
    }

    reverse_iterator rend()
    {
        return implementation_.intrusiveList.rend();
    }

    const_reverse_iterator rend() const
    {
        return implementation_.intrusiveList.rend();
    }

    void splice(const iterator splicedElement)
    {
        UnsortedIntrusiveList::splice(implementation_.findInsertPosition(*splicedElement), splicedElement);
    }

    void swap(SortedIntrusiveList& other)
    {
        implementation_.swap(other.implementation_);
    }

    static iterator erase(const iterator position)
    {
        return UnsortedIntrusiveList::erase(position);
    }

    SortedIntrusiveList(const SortedIntrusiveList&) = delete;
    SortedIntrusiveList(SortedIntrusiveList&&) = default;
    const SortedIntrusiveList& operator=(const SortedIntrusiveList&) = delete;
    SortedIntrusiveList& operator=(SortedIntrusiveList&&) = delete;

private:

    struct Implementation : public Compare
    {
        constexpr explicit Implementation(const Compare& comparee) :
                Compare{comparee},
                intrusiveList{}
        {

        }

        iterator findInsertPosition(const_reference newElement)
        {
            return std::find_if(intrusiveList.begin(), intrusiveList.end(),
                    [this, &newElement](const_reference& element) -> bool
                    {
                        return this->Compare::operator()(element, newElement);
                    }
            );
        }

        void swap(Implementation& other)
        {
            intrusiveList.swap(other.intrusiveList);
            using std::swap;
            swap(static_cast<Compare&>(*this), static_cast<Compare&>(other));
        }

        Implementation(const Implementation&) = delete;
        Implementation(Implementation&&) = default;
        const Implementation& operator=(const Implementation&) = delete;
        Implementation& operator=(Implementation&&) = delete;

        UnsortedIntrusiveList intrusiveList;
    };

    Implementation implementation_;
};

template<typename Compare, typename T, IntrusiveListNode T::* NodePointer, typename U = T>
inline void swap(SortedIntrusiveList<Compare, T, NodePointer, U>& left,
        SortedIntrusiveList<Compare, T, NodePointer, U>& right)
{
    left.swap(right);
}

}   // namespace estd

#endif  // ESTD_SORTEDINTRUSIVELIST_HPP_