Program Listing for File dllist.hpp

↰ Return to documentation for file (ckpttncpp/dllist.hpp)

#pragma once

#include <cassert>
// #include <cstdint>
#include <utility> // import std::move()

// Forward declaration for begin() end()
template <typename T>
class dll_iterator;

#pragma pack(push, 1)
template <typename T>
class dllink
{
    friend dll_iterator<T>;

  private:
    dllink* next {this};
    dllink* prev {this};
  public:
    T data {};
    // Int key{}; /*!< key */

    constexpr explicit dllink(T data) noexcept
        : data {std::move(data)}
    {
        static_assert(sizeof(dllink) <= 24, "keep this class small");
    }

    constexpr dllink() = default;
    ~dllink() = default;
    dllink(const dllink&) = delete;                              // don't copy
    constexpr auto operator=(const dllink&) -> dllink& = delete; // don't assign
    constexpr dllink(dllink&&) noexcept = default;
    constexpr auto operator=(dllink&&) noexcept
        -> dllink& = default; // don't assign

    constexpr auto lock() noexcept -> void
    {
        this->next = nullptr;
    }

    [[nodiscard]] constexpr auto is_locked() const noexcept -> bool
    {
        return this->next == nullptr;
    }

    [[nodiscard]] constexpr auto is_empty() const noexcept -> bool
    {
        return this->next == this;
    }

    constexpr auto clear() noexcept -> void
    {
        this->next = this->prev = this;
    }

    constexpr auto detach() noexcept -> void
    {
        assert(!this->is_locked());
        const auto n = this->next;
        const auto p = this->prev;
        p->next = n;
        n->prev = p;
    }

    constexpr auto appendleft(dllink& node) noexcept -> void
    {
        node.next = this->next;
        this->next->prev = &node;
        this->next = &node;
        node.prev = this;
    }

    constexpr auto append(dllink& node) noexcept -> void
    {
        node.prev = this->prev;
        this->prev->next = &node;
        this->prev = &node;
        node.next = this;
    }

    constexpr auto popleft() noexcept -> dllink&
    {
        auto res = this->next;
        this->next = res->next;
        this->next->prev = this;
        return *res;
    }

    constexpr auto pop() noexcept -> dllink&
    {
        auto res = this->prev;
        this->prev = res->prev;
        this->prev->next = this;
        return *res;
    }

    // For iterator

    constexpr auto begin() noexcept -> dll_iterator<T>;

    constexpr auto end() noexcept -> dll_iterator<T>;

    // using coro_t = boost::coroutines2::coroutine<dllink&>;
    // using pull_t = typename coro_t::pull_type;

    // /**
    //  * @brief item generator
    //  *
    //  * @return pull_t
    //  */
    // auto items() noexcept -> pull_t
    // {
    //     auto func = [&](typename coro_t::push_type& yield) {
    //         auto cur = this->next;
    //         while (cur != this)
    //         {
    //             yield(*cur);
    //             cur = cur->next;
    //         }
    //     };
    //     return pull_t(func);
    // }
};
#pragma pack(pop)

template <typename T>
class dll_iterator
{
  private:
    dllink<T>* cur;
  public:
    constexpr explicit dll_iterator(dllink<T>* cur) noexcept
        : cur {cur}
    {
    }

    constexpr auto operator++() noexcept -> dll_iterator&
    {
        this->cur = this->cur->next;
        return *this;
    }

    constexpr auto operator*() noexcept -> dllink<T>&
    {
        return *this->cur;
    }

    friend auto operator==(
        const dll_iterator& lhs, const dll_iterator& rhs) noexcept -> bool
    {
        return lhs.cur == rhs.cur;
    }

    friend auto operator!=(
        const dll_iterator& lhs, const dll_iterator& rhs) noexcept -> bool
    {
        return !(lhs == rhs);
    }
};


template <typename T>
inline constexpr auto dllink<T>::begin() noexcept -> dll_iterator<T>
{
    return dll_iterator<T> {this->next};
}

template <typename T>
inline constexpr auto dllink<T>::end() noexcept -> dll_iterator<T>
{
    return dll_iterator<T> {this};
}