deque.h

Go to the documentation of this file.

// =====================================================================================================================
//  fennec, a free and open source game engine
//  Copyright © 2025  Medusa Slockbower
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <https://www.gnu.org/licenses/>.
// =====================================================================================================================
 
 
#ifndef FENNEC_CONTAINERS_DEQUE_H
#define FENNEC_CONTAINERS_DEQUE_H
 
#include <fennec/memory/allocator.h>
 
// TODO: Document
 
namespace fennec
{
 
template<typename TypeT, typename AllocT = allocator<TypeT>>
struct deque {
 
// Definitions =========================================================================================================
public:
    using value_t = TypeT; 
    class iterator;
 
private:
    struct node {
        value_t value;
        node *prev, *next;
 
        template<typename...ArgsT>
        node(node* prev, node* next, ArgsT&&...args)
            : value(fennec::forward<ArgsT>(args)...)
            , prev(prev), next(next) {
        }
 
        ~node() = default;
    };
 
public:
    using alloc_t = allocator_traits<AllocT>::template rebind<node>;
    using elem_t  = node*;
 
 
// Constructors ========================================================================================================
 
 
    deque()
        : _alloc()
        , _first(nullptr)
        , _last(nullptr)
        , _size(0) {
    }
 
    deque(const alloc_t& alloc)
        : _alloc(alloc)
        , _first(nullptr)
        , _last(nullptr)
        , _size(0) {
    }
 
    deque(const deque& deque)
        : _alloc(deque._alloc)
        , _first(nullptr)
        , _last(nullptr)
        , _size(0) {
        const elem_t node = deque._first;
        while (node) {
            this->push_back(node->value);
            node = node->next;
        }
    }
 
    deque(deque&& deque) noexcept
        : _alloc(deque._alloc)
        , _first(deque._first)
        , _last(deque._last)
        , _size(deque._size) {
        deque._first = nullptr;
        deque._last  = nullptr;
    }
 
    ~deque() {
        clear();
    }
 
 
// Properties ==========================================================================================================
 
 
    constexpr bool empty() const {
        return _size == 0;
    }
 
    constexpr size_t size() const {
        return _size;
    }
 
 
 
// Access ==============================================================================================================
 
 
    value_t& front() {
        assert(not empty(), "Attempted to access an empty deque.");
        return _first->value;
    }
 
    const value_t& front() const {
        assert(not empty(), "Attempted to access an empty deque.");
        return _first->value;
    }
 
    value_t& back() {
        assert(not empty(), "Attempted to access an empty deque.");
        return _last->value;
    }
 
    const value_t& back() const {
        assert(not empty(), "Attempted to access an empty deque.");
        return _last->value;
    }
 
 
 
// Modifiers ===========================================================================================================
 
 
    void push_front(value_t&& elem) {
        this->_push_front(elem);
    }
 
    void push_front(const value_t& elem) {
        this->_push_front(elem);
    }
 
    template<typename...ArgsT>
    void emplace_front(ArgsT&&...args) {
        this->_push_front(fennec::forward<ArgsT>(args)...);
    }
 
 
    void push_back(value_t&& elem) {
        this->_push_back(elem);
    }
 
    void push_back(const value_t& elem) {
        this->_push_back(elem);
    }
 
    template<typename...ArgsT>
    void emplace_back(ArgsT&&...args) {
        this->_push_back(fennec::forward<ArgsT>(args)...);
    }
 
    void clear() {
        elem_t it = _first;
        while (it) {
            elem_t next = it->next;
            fennec::destruct(it);
            _alloc.deallocate(it);
            it = next;
        }
        _first = nullptr;
        _last  = nullptr;
        _size  = 0;
    }
 
    void pop_front() {
        if (_first == nullptr) {
            return;
        }
        elem_t next = _first->next;
        fennec::destruct(_first);
        _alloc.deallocate(_first);
        _first = next;
        _last = next ? _last : nullptr;
        --_size;
    }
 
    void pop_back() {
        if (_last == nullptr) {
            return;
        }
        elem_t prev = _last->prev;
        fennec::destruct(_last);
        _alloc.deallocate(_last);
        _last = prev;
        _first = prev ? _first : nullptr;
        --_size;
    }
 
 
 
// Iteration ===========================================================================================================
 
    /*
     * TODO: Decide whether you should be able to iterate over a deque
     */
 
private:
    alloc_t _alloc;
    node   *_first, *_last;
    size_t  _size;
 
    template<typename...ArgsT>
    void _push_front(ArgsT&&...args) {
        elem_t next = _first;
        _first = _alloc.allocate(1);
        fennec::construct(_first, nullptr, next, fennec::forward<ArgsT>(args)...);
        if (next) {
            next->prev = _first;
        } else {
            _last = _first;
        }
        ++_size;
    }
 
    template<typename...ArgsT>
    void _push_back(ArgsT&&...args) {
        elem_t prev = _last;
        _last = _alloc.allocate(1);
        fennec::construct(_last, prev, nullptr, fennec::forward<ArgsT>(args)...);
        if (prev) {
            prev->next = _last;
        } else {
            _first = _last;
        }
        ++_size;
    }
};
 
 
}
 
#endif // FENNEC_CONTAINERS_DEQUE_H