hxlist.hpp

Go to the documentation of this file.

#pragma once
// SPDX-FileCopyrightText: © 2017-2026 Adrian Johnston.
// SPDX-License-Identifier: MIT
// This file is licensed under the MIT license found in the LICENSE.md file.

 
#include "libhatchet.h"
 
// HX_USE_MACROS_WITH_MODULE allows including macros alongside the module.
#if HX_USE_MACROS_WITH_MODULE
#error Header does not provide macros alone.
#endif
 
#include "hxrange.hpp"
#include "hxptr.hpp"
#include "hxutility.h"
 
HX_NS_BEGIN_
 
class hxlist_node;
 
#if HX_CPLUSPLUS >= 202002L
template<typename T_>
concept hxlist_concept_ = requires(T_& x_, T_* ptr_) {
    sizeof(T_);
    x_.~T_();
    { ptr_ } -> hxconvertible_to<hxlist_node*>; // T_ must derive from hxlist_node.
};
#else
#define hxlist_concept_ typename
#endif

class hxlist_node {
public:
    hxlist_node(void) : m_list_link_(0) { }

    hxlist_node(const hxlist_node&) : hxlist_node() { }

    hxlist_node& operator=(const hxlist_node& x_) {
        hxassertf(this != &x_, "self_assignment"); (void)x_;
        return *this;
    }
 
private:
    friend class hxlist_base_;
    template<hxlist_concept_, typename> friend class hxlist;
    intptr_t m_list_link_; // Previous address XOR next address.
};

class hxlist_base_ {
private:
    template<hxlist_concept_, typename> friend class hxlist;
 
    hxlist_base_(void);
    void extract_(hxlist_node* prev_, hxlist_node* current_);
    hxlist_node* front_(void) const;
    void insert_after_(hxlist_node* prev_, hxlist_node* current_, hxlist_node* ptr_);
    void insert_before_(hxlist_node* prev_, hxlist_node* current_, hxlist_node* ptr_);
    hxlist_node* pop_back_(void);
    hxlist_node* pop_front_(void);
    void push_back_(hxlist_node* ptr_);
    void push_front_(hxlist_node* ptr_);
    void release_all_(void);
    void reverse_(void);
    void splice_(hxlist_node* prev_, hxlist_node* current_, hxlist_base_& x_);
 
    hxsize_t m_size_;
    hxlist_node m_sentinel_;
    hxlist_node* m_tail_;
};

template<hxlist_concept_ T_, typename deleter_t_=hxdefault_delete>
class hxlist : private deleter_t_ {
public:
    using T = T_;

    class const_iterator {
    public:
        const_iterator(void) : m_prev_(hxnull), m_current_node_(hxnull)
#if (HX_HARDENING_MODE) == HX_HARDENING_MODE_DEBUG
            , m_sentinel_(hxnull)
#endif
        { }

        const_iterator& operator++(void);
        const_iterator operator++(int);
        const_iterator& operator--(void);
        const_iterator operator--(int);
        bool operator==(const const_iterator& x_) const;
#if HX_CPLUSPLUS < 202002L // C++20 defaults != from ==.
        bool operator!=(const const_iterator& x_) const { return !(*this == x_); }
#endif
        const T_& operator*(void) const {
            hxassertf(this->m_current_node_ != hxnull
                && this->m_current_node_ != this->m_sentinel_, "bad_iter");
            return *static_cast<const T_*>(m_current_node_);
        }

        const T_* operator->(void) const {
            hxassertf(this->m_current_node_ != hxnull
                && this->m_current_node_ != this->m_sentinel_, "bad_iter");
            return static_cast<const T_*>(m_current_node_);
        }
    protected:
        template<hxlist_concept_, typename> friend class hxlist;
        const_iterator(hxlist_node* prev_, hxlist_node* current_, const hxlist_node* sentinel_)
            : m_prev_(prev_), m_current_node_(current_)
#if (HX_HARDENING_MODE) == HX_HARDENING_MODE_DEBUG
            , m_sentinel_(sentinel_)
#endif
        { (void)sentinel_; }
        hxlist_node* m_prev_;
        hxlist_node* m_current_node_;
#if (HX_HARDENING_MODE) == HX_HARDENING_MODE_DEBUG
        const hxlist_node* m_sentinel_;
#endif
    };

    class iterator : public const_iterator {
    public:
        iterator(void) { }
        iterator& operator++(void) { const_iterator::operator++(); return *this; }
        iterator operator++(int);
        iterator& operator--(void) { const_iterator::operator--(); return *this; }
        iterator operator--(int);
        T_& operator*(void) const {
            hxassertf(this->m_current_node_ != hxnull
                && this->m_current_node_ != this->m_sentinel_, "bad_iter");
            return *static_cast<T_*>(this->m_current_node_);
        }

        T_* operator->(void) const {
            hxassertf(this->m_current_node_ != hxnull
                && this->m_current_node_ != this->m_sentinel_, "bad_iter");
            return static_cast<T_*>(this->m_current_node_);
        }
    private:
        template<hxlist_concept_, typename> friend class hxlist;
        iterator(hxlist_node* prev_, hxlist_node* current_, const hxlist_node* sentinel_)
            : const_iterator(prev_, current_, sentinel_) { }
        iterator(const const_iterator& x_) : const_iterator(x_) { }
    };

    explicit hxlist(deleter_t_ deleter_=deleter_t_());

    ~hxlist(void) { this->clear(this->deleter()); }

    hxattr_nodiscard bool operator==(const hxlist& x_) const;

    hxattr_nodiscard bool operator<(const hxlist& x_) const;

    template<hxrange_concept_ range_t_,
        hxenable_if_t<!hxis_lvalue_reference<range_t_>(), int> = 0>
    void add_range(range_t_&& range_) noexcept;

    hxattr_nodiscard const T_& back(void) const;
 
    hxattr_nodiscard T_& back(void);

    const_iterator begin(void) const;
 
    iterator begin(void);

    const_iterator cbegin(void) const { return this->begin(); }

    const_iterator cend(void) const { return this->end(); }

    template<typename deleter_u_>
    void clear(deleter_u_&& deleter_) noexcept;

    void clear(void) { this->clear(this->deleter()); }

    hxattr_nodiscard bool empty(void) const { return m_base_.m_size_ == 0; }

    const_iterator end(void) const;
 
    iterator end(void);

    template<typename deleter_u_>
    void erase(const_iterator it_, deleter_u_&& deleter_) noexcept;

    void erase(const_iterator it_) noexcept;

    hxptr<T_, deleter_t_> extract(const_iterator it_);

    template<typename callable_t_>
    hxattr_nodiscard const_iterator find_if(callable_t_&& callable_) const;

    template<typename callable_t_>
    hxattr_nodiscard iterator find_if(callable_t_&& callable_);

    template<typename callable_t_>
    void for_each(callable_t_&& callable_) const;

    template<typename callable_t_>
    void for_each(callable_t_&& callable_);

    hxattr_nodiscard const deleter_t_& deleter(void) const;
 
    hxattr_nodiscard deleter_t_& deleter(void);

    hxattr_nodiscard const T_& front(void) const;
 
    hxattr_nodiscard T_& front(void);

    template<typename deleter_u_>
    iterator insert_after(const_iterator it_, hxptr<T_, deleter_u_>&& ptr_);

    iterator insert_after(const_iterator it_, T_* ptr_);

    template<typename deleter_u_>
    iterator insert(const_iterator it_, hxptr<T_, deleter_u_>&& ptr_);

    iterator insert(const_iterator it_, T_* ptr_);

    hxptr<T_, deleter_t_> pop_back(void);

    hxptr<T_, deleter_t_> pop_front(void);

    template<typename deleter_u_>
    iterator push_back(hxptr<T_, deleter_u_>&& ptr_);

    iterator push_back(T_* ptr_);

    template<typename deleter_u_>
    iterator push_front(hxptr<T_, deleter_u_>&& ptr_);

    iterator push_front(T_* ptr_);

    void release_all(void);

    template<typename callable_t_, typename deleter_u_>
    hxsize_t remove_if(callable_t_&& callable_, deleter_u_&& deleter_) noexcept;

    template<typename callable_t_>
    hxsize_t remove_if(callable_t_&& callable_) noexcept;

    void reverse(void);

    hxattr_nodiscard hxsize_t size(void) const { return m_base_.m_size_; }

    void splice(const_iterator it_, hxlist& x_);
 
private:
    hxlist(const hxlist&) = delete;
    hxlist(hxlist&&) = delete;
    hxlist& operator=(const hxlist&) = delete;
    hxlist& operator=(hxlist&&) = delete;
 
    hxlist_base_ m_base_;
};
 
#include "detail/hxlist.inl"
HX_NS_END_