#ifndef TILE_BASE_INTERNAL_SINGLY_LINKED_LIST_H
#define TILE_BASE_INTERNAL_SINGLY_LINKED_LIST_H

#pragma once

#include "tile/base/internal/logging.h"

#include <cstddef>
#include <utility>

namespace tile {
namespace internal {
struct SinglyLinkedListEntry {
    SinglyLinkedListEntry *next = this;
};

template<typename T, SinglyLinkedListEntry T::*kEntry>
class SinglyLinkedList {
public:
    class iterator;
    class const_iterator;

    constexpr SinglyLinkedList();
    T &front() noexcept;
    T &back() noexcept;

    constexpr const T &front() const noexcept;
    constexpr const T &back() const noexcept;

    T *pop_front() noexcept;
    void push_front(T *entry) noexcept;
    void push_back(T *entry) noexcept;

    void splice(SinglyLinkedList &&other) noexcept;
    void swap(SinglyLinkedList &other) noexcept;

    constexpr std::size_t size() const noexcept;

    constexpr bool empty() const noexcept;

    iterator begin() noexcept;
    iterator end() noexcept;
    constexpr const_iterator begin() const noexcept;
    constexpr const_iterator end() const noexcept;

    SinglyLinkedList(SinglyLinkedList &&other) noexcept;
    SinglyLinkedList &operator=(SinglyLinkedList &&otehr) noexcept;

    SinglyLinkedList(const SinglyLinkedList &)            = delete;
    SinglyLinkedList &operator=(const SinglyLinkedList &) = delete;

private:
    static const std::uintptr_t kSinglyLinkedListEntryOffset =
        reinterpret_cast<std::uintptr_t>(&(reinterpret_cast<T *>(0)->*kEntry));
    static constexpr SinglyLinkedListEntry *node_cast(T *ptr) noexcept;
    static constexpr const SinglyLinkedListEntry *node_cast(const T *ptr) noexcept;

    static constexpr T *object_cast(SinglyLinkedListEntry *entry) noexcept;
    static constexpr const T *object_cast(const SinglyLinkedListEntry *entry) noexcept;

private:
    std::size_t size_{};
    SinglyLinkedListEntry *next_{};
    SinglyLinkedListEntry *tail_{};
};

template<typename T, SinglyLinkedListEntry T::*kEntry>
class SinglyLinkedList<T, kEntry>::iterator {
public:
    constexpr iterator() : current_(nullptr) {}

    iterator &operator++() noexcept
    {
        current_ = current_->next;
        return *this;
    }

    iterator operator++(int) noexcept
    {
        iterator copy = *this;
        current_      = current_->next;
        return copy;
    }

    constexpr T *operator->() const noexcept { return object_cast(current_); }

    constexpr T &operator*() const noexcept { return *object_cast(current_); }

    constexpr bool operator!=(const iterator &other) const noexcept { return current_ != other.current_; }

    constexpr bool operator==(const iterator &other) const noexcept { return current_ == other.current_; }

private:
    friend class SinglyLinkedList<T, kEntry>;

    constexpr iterator(SinglyLinkedListEntry *start) : current_(start) {}

private:
    SinglyLinkedListEntry *current_;
};

template<typename T, SinglyLinkedListEntry T::*kEntry>
class SinglyLinkedList<T, kEntry>::const_iterator {
public:
    constexpr const_iterator() : current_(nullptr) {}

    constexpr const_iterator(const iterator &from) : current_(from.current_) {}

    const_iterator &operator++() noexcept
    {
        current_ = current_->next;
        return *this;
    }

    const_iterator operator++(int) noexcept
    {
        const_iterator copy = *this;
        current_            = current_->next;
        return copy;
    }

    constexpr T *operator->() const noexcept { return object_cast(current_); }

    constexpr T &operator*() const noexcept { return *object_cast(current_); }

    constexpr bool operator!=(const const_iterator &other) const noexcept { return current_ != other.current_; }

    constexpr bool operator==(const const_iterator &other) const noexcept { return current_ == other.current_; }

private:
    SinglyLinkedListEntry *current_;
};

template<typename T, SinglyLinkedListEntry T::*kEntry>
const std::uintptr_t SinglyLinkedList<T, kEntry>::kSinglyLinkedListEntryOffset;

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr inline SinglyLinkedList<T, kEntry>::SinglyLinkedList() = default;

template<class T, SinglyLinkedListEntry T::*kEntry>
T &
SinglyLinkedList<T, kEntry>::front() noexcept
{
    TILE_DCHECK(!empty(), "Calling `front()` on empty list is undefined.");
    return *object_cast(next_);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr const T &
SinglyLinkedList<T, kEntry>::front() const noexcept
{
    return const_cast<SinglyLinkedList *>(this)->front();
}

template<class T, SinglyLinkedListEntry T::*kEntry>
T &
SinglyLinkedList<T, kEntry>::back() noexcept
{
    TILE_DCHECK(!empty(), "Calling `back()` on empty list is undefined.");
    return *object_cast(tail_);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr const T &
SinglyLinkedList<T, kEntry>::back() const noexcept
{
    return const_cast<SinglyLinkedList *>(this)->back();
}

template<class T, SinglyLinkedListEntry T::*kEntry>
T *
SinglyLinkedList<T, kEntry>::pop_front() noexcept
{
    TILE_DCHECK(!empty(), "Calling `pop_front()` on empty list is undefined.");
    auto rc = next_;
    next_   = next_->next;
    if (!--size_) {
        tail_ = nullptr;
        TILE_DCHECK(!next_);
    }
    return object_cast(rc);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
void
SinglyLinkedList<T, kEntry>::push_front(T *entry) noexcept
{
    auto ptr  = node_cast(entry);
    ptr->next = next_;
    next_     = ptr;
    if (!size_++) { tail_ = next_; }
}

template<class T, SinglyLinkedListEntry T::*kEntry>
void
SinglyLinkedList<T, kEntry>::push_back(T *entry) noexcept
{
    auto ptr  = node_cast(entry);
    ptr->next = nullptr;
    if (!empty()) {
        tail_ = tail_->next = ptr;
    } else {
        next_ = tail_ = ptr;
    }
    ++size_;
}

template<class T, SinglyLinkedListEntry T::*kEntry>
void
SinglyLinkedList<T, kEntry>::splice(SinglyLinkedList &&from) noexcept
{
    if (empty()) {
        swap(from);
        return;
    }
    if (from.empty()) { return; }
    tail_->next = from.next_;
    tail_       = from.tail_;
    size_ += from.size_;
    from.next_ = from.tail_ = nullptr;
    from.size_              = 0;
}

template<class T, SinglyLinkedListEntry T::*kEntry>
void
SinglyLinkedList<T, kEntry>::swap(SinglyLinkedList &other) noexcept
{
    std::swap(next_, other.next_);
    std::swap(tail_, other.tail_);
    std::swap(size_, other.size_);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr std::size_t
SinglyLinkedList<T, kEntry>::size() const noexcept
{
    return size_;
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr bool
SinglyLinkedList<T, kEntry>::empty() const noexcept
{
    // TILE_DCHECK(!size_ == !next_);
    return !size_;
}

template<class T, SinglyLinkedListEntry T::*kEntry>
typename SinglyLinkedList<T, kEntry>::iterator
SinglyLinkedList<T, kEntry>::begin() noexcept
{
    return iterator(next_);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
typename SinglyLinkedList<T, kEntry>::iterator
SinglyLinkedList<T, kEntry>::end() noexcept
{
    return iterator(nullptr);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr typename SinglyLinkedList<T, kEntry>::const_iterator
SinglyLinkedList<T, kEntry>::begin() const noexcept
{
    return const_iterator(next_);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr typename SinglyLinkedList<T, kEntry>::const_iterator
SinglyLinkedList<T, kEntry>::end() const noexcept
{
    return const_iterator(nullptr);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
SinglyLinkedList<T, kEntry>::SinglyLinkedList(SinglyLinkedList &&other) noexcept
{
    swap(other);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
SinglyLinkedList<T, kEntry> &
SinglyLinkedList<T, kEntry>::operator=(SinglyLinkedList &&other) noexcept
{
    TILE_CHECK(empty(), "Moving into non-empty list will likely leak.");
    swap(other);
    return *this;
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr SinglyLinkedListEntry *
SinglyLinkedList<T, kEntry>::node_cast(T *ptr) noexcept
{
    return &(ptr->*kEntry);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr const SinglyLinkedListEntry *
SinglyLinkedList<T, kEntry>::node_cast(const T *ptr) noexcept
{
    return &(ptr->*kEntry);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr T *
SinglyLinkedList<T, kEntry>::object_cast(SinglyLinkedListEntry *entry) noexcept
{
    return reinterpret_cast<T *>(reinterpret_cast<std::uintptr_t>(entry) - kSinglyLinkedListEntryOffset);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
constexpr const T *
SinglyLinkedList<T, kEntry>::object_cast(const SinglyLinkedListEntry *entry) noexcept
{
    return reinterpret_cast<const T *>(reinterpret_cast<std::uintptr_t>(entry) - kSinglyLinkedListEntryOffset);
}

template<class T, SinglyLinkedListEntry T::*kEntry>
void
swap(SinglyLinkedList<T, kEntry> &left, SinglyLinkedList<T, kEntry> &right) noexcept
{
    left.swap(right);
}

}// namespace internal
}// namespace tile

#endif// TILE_BASE_INTERNAL_SINGLY_LINKED_LIST_H
