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 "hxptr.hpp"
#include "hxutility.h"
 
HX_NS_BEGIN_

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

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

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

template<typename 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 {
            hxassertmsg(this->m_current_node_ != hxnull
                && this->m_current_node_ != this->m_sentinel_, "invalid_iterator");
            return *static_cast<const T_*>(m_current_node_);
        }

        const T_* operator->(void) const {
            hxassertmsg(this->m_current_node_ != hxnull
                && this->m_current_node_ != this->m_sentinel_, "invalid_iterator");
            return static_cast<const T_*>(m_current_node_);
        }
    protected:
        template<typename, 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 {
            hxassertmsg(this->m_current_node_ != hxnull
                && this->m_current_node_ != this->m_sentinel_, "invalid_iterator");
            return *static_cast<T_*>(this->m_current_node_);
        }

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

    explicit hxlist(deleter_t_ deleter_=deleter_t_());

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

    hxattr_nodiscard T_& back(void);

    hxattr_nodiscard const T_& back(void) const;

    iterator begin(void);

    const_iterator begin(void) const;

    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_size_ == 0; }

    iterator end(void);

    const_iterator end(void) const;

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

    void erase(const_iterator pos_) noexcept;

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

    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 T_& front(void);

    hxattr_nodiscard const T_& front(void) const;

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

    iterator insert_after(const_iterator pos_, T_* ptr_);

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

    iterator insert(const_iterator pos_, 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_size_; }

    void splice(const_iterator pos_, hxlist& other_);
 
private:
    hxlist(const hxlist&) = delete;
    hxlist(hxlist&&) = delete;
    hxlist& operator=(const hxlist&) = delete;
    hxlist& operator=(hxlist&&) = delete;
 
    void insert_(hxlist_node* prev_, hxlist_node* next_, hxlist_node* ptr_);
    void extract_(hxlist_node* prev_, hxlist_node* ptr_);
 
    hxsize_t m_size_;
    hxlist_node m_sentinel_;
    // When empty m_sentinel_.m_list_link_ == 0 and m_tail_ == &m_sentinel_.
    hxlist_node* m_tail_;
};
 
#include "detail/hxlist.inl"
HX_NS_END_