hxdeque.hpp

Go to the documentation of this file.

#pragma once
// SPDX-FileCopyrightText: © 2025 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 "hxallocator.hpp"
#include "hxrange.hpp"
#include "hxutility.h"
 
HX_NS_BEGIN_
 
#if HX_CPLUSPLUS >= 202002L
template<typename T_>
concept hxdeque_concept_ = requires(T_& x_) {
    sizeof(T_);
    x_.~T_();
};
#else
#define hxdeque_concept_ typename
#endif

template<hxdeque_concept_ T_, hxsize_t capacity_=hxallocator_dynamic_capacity>
class hxdeque : private hxallocator<T_, capacity_> {
public:
    class const_iterator {
    public:
        const_iterator(void) : m_deque_(hxnull), m_index_(0) { }

        const T_& operator*(void) const { return (*m_deque_)[m_index_]; }

        const_iterator operator+(hxsize_t n_) const { return const_iterator(m_deque_, m_index_ + n_); }

        const_iterator operator-(hxsize_t n_) const { return const_iterator(m_deque_, m_index_ - n_); }

        hxsize_t operator-(const const_iterator& x_) const { return m_index_ - x_.m_index_; }

        const T_& operator[](hxsize_t n_) const { return *operator+(n_); }

        const_iterator& operator++(void) { ++m_index_; return *this; }

        const_iterator operator++(int) { const_iterator t_(*this); ++m_index_; return t_; }

        const_iterator& operator--(void) { --m_index_; return *this; }

        const_iterator operator--(int) { const_iterator t_(*this); operator--(); return t_; }

        bool operator==(const const_iterator& x_) const { return m_index_ == x_.m_index_; }

        bool operator<(const const_iterator& x_) const { return m_index_ < x_.m_index_; }
 
#if HX_CPLUSPLUS < 202002L
        bool operator!=(const const_iterator& x_) const { return m_index_ != x_.m_index_; }
#endif
 
    protected:
        friend class hxdeque;
        const_iterator(const hxdeque* deque_, hxsize_t index_)
            : m_deque_(deque_), m_index_(index_) { }
        const hxdeque* m_deque_;
        hxsize_t m_index_;
    };

    class iterator : public const_iterator {
    public:
        iterator(void) { }

        T_& operator*(void) const { return (*const_cast<hxdeque*>(this->m_deque_))[this->m_index_]; }

        iterator operator+(hxsize_t n_) const { return iterator(const_cast<hxdeque*>(this->m_deque_), this->m_index_ + n_); }

        iterator operator-(hxsize_t n_) const { return iterator(const_cast<hxdeque*>(this->m_deque_), this->m_index_ - n_); }

        hxsize_t operator-(const const_iterator& x_) const { return const_iterator::operator-(x_); }

        T_& operator[](hxsize_t n_) const { return *operator+(n_); }

        iterator& operator++(void) { const_iterator::operator++(); return *this; }

        iterator operator++(int) { iterator t_(*this); const_iterator::operator++(); return t_; }

        iterator& operator--(void) { const_iterator::operator--(); return *this; }

        iterator operator--(int) { iterator t_(*this); const_iterator::operator--(); return t_; }
 
    protected:
        friend class hxdeque;
        iterator(hxdeque* deque_, hxsize_t index_) : const_iterator(deque_, index_) { }
        iterator(const const_iterator& x_) : const_iterator(x_) { }
    };

    explicit hxdeque(hxsize_t dynamic_capacity_=0);

    ~hxdeque(void);

    hxattr_nodiscard const T_& operator[](hxsize_t index_) const;
 
    hxattr_nodiscard T_& operator[](hxsize_t index_);

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

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

    const_iterator begin(void) const { return const_iterator(this, 0); }
 
    iterator begin(void) { return iterator(this, 0); }

    template<hxrange_concept_ range_t_>
    void add_range(range_t_& range_) noexcept;

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

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

    hxattr_nodiscard hxsize_t capacity(void) const;

    const_iterator cbegin(void) const { return const_iterator(this, 0); }

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

    void clear(void) noexcept;

    template<typename... args_t_>
    void emplace_back(args_t_&&... args_) noexcept;

    template<typename... args_t_>
    void emplace_front(args_t_&&... args_) noexcept;

    hxattr_nodiscard bool empty(void) const;

    const_iterator end(void) const { return const_iterator(this, this->size()); }
 
    iterator end(void) { return iterator(this, this->size()); }

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

    hxattr_nodiscard bool full(void) const;

    hxattr_nodiscard hxsize_t max_size(void) const { return this->capacity(); }

    void pop_back(void) noexcept;

    void pop_front(void) noexcept;

    template<typename... args_t_>
    void push_back(args_t_&&... args_) noexcept;

    template<typename... args_t_>
    void push_front(args_t_&&... args_) noexcept;

    void reserve(hxsize_t dynamic_capacity_);

    hxattr_nodiscard hxsize_t size(void) const;
 
private:
    // This is raw underlying data and would not be what was expected.
    using hxallocator<T_, capacity_>::data;
 
    hxdeque(const hxdeque&) = delete;
    void operator=(const hxdeque&) = delete;
 
    size_t m_head_;
    size_t m_tail_;
};
 
#include "detail/hxdeque.inl"
HX_NS_END_