linked_list.h

Go to the documentation of this file.

#pragma once
#include <cstddef>
#include <initializer_list>
#include <stdexcept>
 
#include "algo/algo_base.h"
#include "details/llist_iterator.h"
#include "details/llist_nodes.h"
#include "utils/allocator.h"
#include "utils/compare.h"
#include "utils/iterators.h"
#include "utils/move.h"
#include "utils/type_traits.h"
 
namespace bmb {
 
template <typename T,
          bool TrackSize = true,
          bool TrackLast = true, typename Allocator = PrimitiveAllocator>
class LinkedList {
    // TODO: refactor iterator/pointers usage
 
    using Node     = llist::Node<T>;
    using BaseNode = llist::BaseNode;
 
    using AllocTraits = AllocatorTraits<Allocator>;
 
    // Used for optional fields. See the end of the definition.
    struct Empty {};
    // [[no_unique_address]] must differentiate
    // fileds of the same type. In this case it is not needed because wastes memory
    struct Empty2 {};
 
public:
    using value_type      = T;
    using reference       = value_type&;
    using const_reference = const value_type&;
    using pointer         = value_type*;
    using const_pointer   = const value_type*;
    using size_type       = size_t;
    using allocator_type  = Allocator;
    using iterator        = detail::LListIter<T, false>;
    using const_iterator  = detail::LListIter<T, true>;
 
    LinkedList() noexcept(noexcept(Allocator())) {
        initOptionalFields();
    }
 
    explicit LinkedList(const Allocator& alloc)
        : alloc_(alloc) {
        initOptionalFields();
    }
 
    explicit LinkedList(size_t count, const value_type& value = value_type(),
                        const Allocator& alloc = Allocator())
        : LinkedList(alloc) {
        // Thanks to delegeting c-tor, if exception is thrown,
        // the destructor will be called automatically
        auto cur_it = cbeforeBegin();
        for (; count > 0; --count, ++cur_it) {
            emplaceAfter(cur_it, value);
        }
    }
 
    template <InputIterator Iter>
    LinkedList(Iter first, Iter last,
               const Allocator& alloc = Allocator())
        : LinkedList(alloc) {
        // Thanks to delegeting c-tor, if exception is thrown,
        // the destructor will be called automatically
        auto cur = beforeBegin();
        for (; first != last; ++first) {
            emplaceAfter(cur, *first);
            ++cur;
        }
    }
 
    LinkedList(std::initializer_list<value_type> init_list,
               const Allocator&                  alloc = Allocator())
        : LinkedList(init_list.begin(), init_list.end(), alloc) {}
 
    LinkedList(const LinkedList& other)
        : LinkedList(other.cbegin(),
                     other.cend(), other.alloc_) {}
 
    LinkedList(LinkedList&& other) noexcept(noexcept(Allocator(move(other.alloc_))))
        : head_(other.head_)
        , size_(other.size_)
        , last_(other.last_)
        , alloc_(move(other.alloc_)) {
        other.head_.next = nullptr;
        if constexpr (TrackSize) other.size_ = 0;
        if constexpr (TrackLast) other.last_ = &other.head_;
    }
 
    LinkedList& operator=(LinkedList other) {
        swap(other);
        return *this;
    }
 
    ~LinkedList() { clear(); }
 
    void swap(LinkedList& other) {
        using bmb::swap;
        // First, swap allocs to provide strong safety
        swap(alloc_, other.alloc_);
 
        // Head never points to itself: either node in heap or nullptr,
        // so it is safe just swap it.
        swap(head_, other.head_);
        if constexpr (TrackSize) swap(size_, other.size_);
        if constexpr (TrackLast) swap(last_, other.last_);
    }
 
    void clear() noexcept {
        eraseAfter(cbeforeBegin(), cend());
    }
 
    iterator insertAfter(const_iterator pos, value_type value) {
        return emplaceAfter(pos, move(value));
    }
 
    iterator insertAfter(const_iterator pos, std::initializer_list<T> init_list) {
        return insertAfter(pos, init_list.begin(), init_list.end());
    }
 
    template <InputIterator Iter>
    iterator insertAfter(const_iterator pos, Iter first, Iter last) {
        // Constructor provides strong exception guarantee.
        // If we used  emplaceAfter(...) for each iterator [first, last),
        // it would be more complex to provide exception guarantee here.
        LinkedList tmp(first, last, getAllocator());
 
        if (tmp.isEmpty()) return pos.constCast();
 
        return spliceAfter(pos, move(tmp));
    }
 
    template <typename... Args>
    iterator emplaceAfter(const_iterator pos, Args&&... args) {
        Node*     new_node   = createNode(forward<Args>(args)...);
        BaseNode* before_new = pos.node_;
 
        // Order of operations does matter
        new_node->next   = before_new->next;
        before_new->next = new_node;
 
        if constexpr (TrackSize) ++size_;
 
        if constexpr (TrackLast) {
            if (isIterToLast(pos)) last_ = new_node;
        }
 
        return iterator(new_node);
    }
 
    template <typename... Args>
    reference emplaceFront(Args&&... args) {
        return *emplaceAfter(cbeforeBegin(), forward<Args>(args)...);
    }
 
    template <typename... Args>
    reference emplaceBack(Args&&... args) {
        return *emplaceAfter(iterator(getLastNode()),
                             forward<Args>(args)...);
    }
 
    iterator eraseAfter(const_iterator pos) noexcept {
        BaseNode* to_destroy = pos.node_->next;
 
        if (to_destroy == nullptr) return pos.constCast();
 
        BaseNode* after_destroyed = to_destroy->next;
 
        pos.node_->next = after_destroyed;
 
        destroyNode(castToNode(to_destroy));
 
        if constexpr (TrackSize) --size_;
 
        if constexpr (TrackLast) {
            // Now `pos` becomes the last element in the list
            if (last_ == to_destroy) last_ = pos.node_;
        }
 
        return iterator(after_destroyed);
    }
 
    iterator eraseAfter(const_iterator first, const_iterator last) noexcept {
        if (first == last) return last.constCast();
 
        while (next(first) != last) {
            eraseAfter(first);
        }
        return last.constCast();
    }
 
    void popFront() noexcept { eraseAfter(cbeforeBegin()); }
 
    void popBack() noexcept {
        // Make sure list is not empty.
        if (begin() == end()) return;
 
        // Find before the last
        BaseNode* before_last = &head_;
        while (before_last->next->next != nullptr) before_last = before_last->next;
 
        eraseAfter(const_iterator(before_last));
    }
 
    template <typename Cmp = less>
    void merge(LinkedList& other, Cmp cmp = Cmp()) {
        merge(move(other), move(cmp));
    }
 
    template <typename Cmp = less>
    void merge(LinkedList&& other, Cmp cmp = Cmp()) {
        // NOTE: If you want, you can try to make merge at least
        // basic exception safety. Just save the last node when
        // node should be linked to the node from other list.
        // If there is exception, link these "lost" nodes to the
        // end of any list - they will be destroyed by destructor.
        //
        // Also if you may make merge be stable.
 
        if (this == &other) return;
 
        if (getAllocator() != other.getAllocator())
            throw std::runtime_error(
                "Try to merge linked list "
                "allocated via different allocator");
 
        // Just to make comparasion less verbose
        auto compare = [this, &cmp](auto a, auto b) -> bool {
            return cmp(castToNode(a)->val, castToNode(b)->val);
        };
 
        auto a    = head_.next;
        auto b    = other.head_.next;
        auto prev = &head_;
 
        while (a && b) {
            // Make `a` always less than `b`
            if (!compare(a, b)) bmb::swap(a, b);
 
            prev->next = a;
            prev       = a;
            a          = a->next;
        }
        prev->next = a != nullptr ? a : b;
 
        other.head_.next = nullptr;
 
        if constexpr (TrackSize) {
            size_ += other.size_;
            other.size_ = 0;
        }
 
        if constexpr (TrackLast) {
            // If nodes from `other` > than from `this`,
            // they will be placed after `last_`, so update it.
            // Remember to handle cases with empty lists.
 
            // `this` is empty, `other` is not
            if (last_ == &head_
                && other.last_ != &other.head_) last_ = other.last_;
            // `this` is not empty, `other` is not empty,
            // and nodes from `other` are after `this->last_`
            else if (last_ != &head_
                     && other.last_ != &other.head_
                     && compare(last_, other.last_)) {
                last_ = other.last_;
            }
 
            other.last_ = &other.head_;
        }
    }
 
    iterator spliceAfter(const_iterator pos, LinkedList& other) {
        return spliceAfter(pos, move(other));
    }
 
    iterator spliceAfter(const_iterator pos, LinkedList&& other) {
        if (this == &other || other.isEmpty()) return pos.constCast();
 
        if (getAllocator() != other.getAllocator())
            throw std::runtime_error(
                "Try to transfer linked list "
                "allocated via different allocator");
 
        // If track last, we can bypass its search.
        if constexpr (TrackLast) {
            auto last_transferred = other.last_;
 
            transferAfter(pos.node_,
                          &other.head_, other.last_);
 
            if (isIterToLast(pos)) last_ = other.last_;
 
            other.last_ = &other.head_;
 
            // Update size
            if constexpr (TrackSize) {
                size_ += other.size_;
                other.size_ = 0;
            }
 
            return iterator(last_transferred);
        }
 
        // If `last_` is not available, use non effective version
        return spliceAfter(pos, move(other),
                           other.beforeBegin(), other.end());
    }
 
    iterator spliceAfter(const_iterator pos, LinkedList& other,
                         const_iterator first, const_iterator last) {
        return spliceAfter(pos, move(other), first, last);
    }
 
    iterator spliceAfter(const_iterator pos, LinkedList&& other,
                         const_iterator first, const_iterator last) {
        if (getAllocator() != other.getAllocator())
            throw std::runtime_error(
                "Try to transfer linked list nodes "
                "allocated via different allocator");
 
        // If no elements to transfer
        if (first == last
            || next(first) == last) return pos.constCast();
 
        // Find last element to transfer(right before `last` iterator)
        auto   before = first.node_;
        auto   end    = before;
        size_t cnt    = 0;
 
        while (end->next != last.node_) {
            end = end->next;
            ++cnt;
        }
 
        if constexpr (TrackSize) {
            // Update only if obtained new elements
            if (this != &other) {
                size_ += cnt;
                other.size_ -= cnt;
            }
        }
 
        if constexpr (TrackLast) {
            if (isIterToLast(pos)) last_ = end;
        }
 
        return iterator(transferAfter(pos.node_, before, end));
    }
 
    void reverse() noexcept {
        BaseNode* left  = nullptr;
        BaseNode* right = head_.next;
        // Left will be point to the new first element
        while (right != nullptr) {
            auto keep   = right->next;
            right->next = left;
            left        = right;
            right       = keep;
        }
 
        if constexpr (TrackLast) {
            if (!isEmpty()) last_ = head_.next;
            // If empty - last points to the `head`
        }
 
        head_.next = left;
    }
 
    reference front() noexcept { return *begin(); }
 
    const_reference front() const noexcept { return *begin(); }
 
    reference back() noexcept {
        return *iterator(getLastNode());
    }
 
    const_reference back() const noexcept {
        return *iterator(getLastNode());
    }
 
    Node* getRawFirstNode() const noexcept {
        return castToNode(begin().node_);
    }
 
    size_t size() const noexcept {
        if constexpr (TrackSize) return size_;
 
        size_t    cnt = 0;
        BaseNode* cur = &head_;
        while (cur->next != nullptr) {
            ++cnt;
            cur = cur->next;
        }
        return cnt;
    }
 
    bool isEmpty() const noexcept {
        // Don't use `size()` here, since
        // it may has linear time complexity
        return head_.next == nullptr;
    }
 
    allocator_type getAllocator() const { return alloc_; }
 
    iterator begin() noexcept { return iterator(head_.next); }
    iterator end() noexcept { return iterator(nullptr); }
 
    const_iterator begin() const noexcept { return const_iterator(head_.next); }
    const_iterator end() const noexcept { return const_iterator(nullptr); }
 
    const_iterator cbegin() const noexcept { return const_iterator(head_.next); }
    const_iterator cend() const noexcept { return const_iterator(nullptr); }
 
    iterator       beforeBegin() noexcept { return iterator(&head_); }
    const_iterator beforeBegin() const noexcept { return const_iterator(&head_); }
    const_iterator cbeforeBegin() const noexcept { return const_iterator(&head_); }
 
    iterator       beforeEnd() noexcept { return iterator(getLastNode()); }
    const_iterator beforeEnd() const noexcept { return const_iterator(getLastNode()); }
    const_iterator cbeforeEnd() const noexcept { return const_iterator(getLastNode()); }
    // reverese_iterator rbegin() ....
 
    bool operator==(const LinkedList& other) const noexcept {
        if constexpr (TrackSize) {
            return size_ == other.size_
                   && equal(begin(), end(), other.begin());
        }
        return equal(begin(), end(), other.begin(), other.end());
    }
 
    auto operator<=>(const LinkedList& other) const noexcept {
        return lexicographical_compare_three_way(begin(), end(),
                                                 other.begin(), other.end());
    }
 
private:
    BaseNode* transferAfter(BaseNode* pos,
                            BaseNode* begin, BaseNode* end) noexcept {
        // By construction, linked list must know the element
        // before the first one to transfer, since we have to update
        // next pointer for it. Also we should know the last element
        // to transfer for proper pointers rearrangment.
 
        auto keep = begin->next;
 
        begin->next = end->next;
        end->next   = pos->next;
 
        pos->next = keep;
        return end;
    }
 
    Node* castToNode(BaseNode* ptr) const noexcept { return static_cast<Node*>(ptr); }
 
    void initOptionalFields() noexcept {
        if constexpr (TrackSize) size_ = 0;
        if constexpr (TrackLast) last_ = &head_;
    }
 
    template <typename... Args>
    Node* createNode(Args&&... args) {
        auto node = AllocTraits::template allocate<Node>(alloc_, 1);
        try {
            AllocTraits::construct(alloc_, node, forward<Args>(args)...);
        } catch (...) {
            AllocTraits::deallocate(alloc_, node, 1);
            throw;
        }
        return node;
    }
 
    void destroyNode(Node* node) noexcept {
        AllocTraits::destroy(alloc_, node);
        AllocTraits::deallocate(alloc_, node, 1);
    }
 
    bool isIterToLast(const_iterator it) const noexcept {
        return it == const_iterator(getLastNode());
    }
 
    BaseNode* getLastNode() const noexcept {
        if constexpr (TrackLast) return last_;
 
        BaseNode* cur = &head_;
        while (cur->next != nullptr) cur = cur->next;
        return cur;
    }
 
    // Make mutable for simplicity of const conversions.
    // Actually needed for const_iterator(&head) for const lists.
    // But const_iterator can be constructed only from non-const
    // BaseNodes.
    mutable BaseNode head_;
 
    // Enables fast access to the list's size.
    // If don't track size, use empty struct that
    // highly(and should in this case) will be optimized and will not use memory.
    [[no_unique_address]]
    conditional_t<TrackSize, size_t, Empty> size_;
 
    // Enables fast access to the last element in the list.
    // Invariant: if list is empty, points to the `head_`, otherwise to the real Node.
    [[no_unique_address]]
    conditional_t<TrackLast, BaseNode*, Empty2> last_;
 
    [[no_unique_address]] Allocator alloc_;
};
 
template <typename T, bool TrackLast,
          typename Allocator = PrimitiveAllocator>
using LListFastSize = LinkedList<T, true, TrackLast, Allocator>;
 
template <typename T, bool TrackSize,
          typename Allocator = PrimitiveAllocator>
using LListFastLast = LinkedList<T, TrackSize, true, Allocator>;
 
template <typename T,
          typename Allocator = PrimitiveAllocator>
using LListTiny = LinkedList<T, false, false, Allocator>;
 
template <typename T,
          typename Allocator = PrimitiveAllocator>
using LListFat = LinkedList<T, true, true, Allocator>;
 
template <typename T,
          bool TrackSize = true,
          bool TrackLast = true, typename Allocator = PrimitiveAllocator>
void swap(LinkedList<T, TrackSize, TrackLast, Allocator>& a,
          LinkedList<T, TrackSize, TrackLast, Allocator>& b) {
    a.swap(b);
}
 
template <InputIterator Iter, typename Allocator = PrimitiveAllocator>
LinkedList(Iter, Iter, Allocator = Allocator()) -> LinkedList<typename IteratorTraits<Iter>::value_type,
                                                              true, true, PrimitiveAllocator>;
 
}  // namespace bmb