list.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_LIST_H
#define FENNEC_CONTAINERS_LIST_H
 
#include <fennec/containers/dynarray.h>
#include <fennec/containers/list.h>
#include <fennec/containers/optional.h>
#include <fennec/memory/allocator.h>
 
#include <fennec/math/common.h>
 
namespace fennec
{
 
template<class TypeT, class Alloc = allocator<TypeT>>
struct list {
 
// Definitions =========================================================================================================
 
private:
    struct node;
 
public:
    using alloc_t = typename allocator_traits<Alloc>::template rebind<node>;
 
    using value_t = TypeT; 
 
    static constexpr size_t npos = -1; 
 
    class iterator; 
    class const_iterator; 
 
 
// Constructors & Destructor ===========================================================================================
 
 
    constexpr list()
        : _table(), _freed(), _root(npos), _last(npos), _size(0) {
    }
 
    constexpr list(const list& l)
        : list() {
        for (const value_t& it : l) {
            this->push_back(it);
        }
    }
 
 
    constexpr list(list&& l) noexcept
        : _table(fennec::move(l._table))
        , _freed(fennec::move(l._freed))
        , _root(l._root)
        , _last(l._last)
        , _size(l._size) {
    }
 
    constexpr ~list() {
        for (size_t i = 0; i < capacity(); ++i) {
            _table[i].value = nullopt;
        }
    }
 
 
// Assignment ==========================================================================================================
 
 
    constexpr list& operator=(const list& l) {
        this->clear();
        for (const value_t& it : l) {
            this->push_back(it);
        }
        return *this;
    }
 
    constexpr list& operator=(list&& l) noexcept {
        this->clear();
        _table = fennec::move(l._table);
        _freed = fennec::move(l._freed);
        _root  = l._root; _last = l._last;
        _size  = l._size;
        return *this;
    }
 
 
 
// Properties ==========================================================================================================
 
 
    constexpr size_t size() const {
        return _size;
    }
 
    constexpr size_t capacity() const {
        return _table.capacity();
    }
 
    constexpr bool empty() const {
        return _root == npos;
    }
 
 
 
// Access ==============================================================================================================
 
 
    constexpr value_t& operator[](int i) {
        assertd(i >= 0 && size_t(i) < _size, "Index out of Bounds");
        size_t n = _walk(i);
        assertd(n != npos, "Index out of Bounds");
        return *_table[n].value;
    }
 
    constexpr const value_t& operator[](int i) const {
        assertd(i >= 0 && size_t(i) < _size, "Index out of Bounds");
        size_t n = _walk(i);
        assertd(n != npos, "Index out of Bounds");
        return *_table[n].value;
    }
 
    constexpr value_t& front() {
        return *_table[_root].value;
    }
 
    constexpr const value_t& front() const {
        return *_table[_root].value;
    }
 
    constexpr value_t& back() {
        return *_table[_last].value;
    }
 
    constexpr const value_t& back() const {
        return *_table[_last].value;
    }
 
 
 
// Modifiers ===========================================================================================================
 
 
    constexpr size_t insert(const iterator& it, const value_t& x) {
        return this->_insert(it._n, x);
    }
 
    constexpr size_t insert(const iterator& it, value_t&& x) {
        return this->_insert(it._n, fennec::forward<value_t>(x));
    }
 
    constexpr size_t insert(size_t i, const value_t& x) {
        assert(i <= size(), "Index out of Bounds");
 
        size_t n = _walk(min(i, size_t(size() - 1)));
        return this->_insert(n, x);
    }
 
    constexpr size_t insert(size_t i, value_t&& x) {
        assert(i <= size(), "Index out of Bounds");
 
        size_t n = _walk(min(i, size_t(size() - 1)));
        return this->_insert(n, fennec::forward<value_t>(x));
    }
 
    template<typename...ArgsT>
    constexpr size_t emplace(size_t i, ArgsT&&...args) {
        assert(i <= size(), "Index out of Bounds");
 
        size_t n = _walk(min(i, size_t(size() - 1)));
        return this->_insert(n, fennec::forward<ArgsT>(args)...);
    }
 
    constexpr size_t push_front(const value_t& x) {
        return this->_insert(_root, x);
    }
 
    constexpr size_t push_front(value_t&& x) {
        return this->_insert(_root, fennec::forward<value_t>(x));
    }
 
    template<typename...ArgsT>
    constexpr size_t emplace_front(ArgsT&&...args) {
        return this->_insert(_root, fennec::forward<ArgsT>(args)...);
    }
 
    constexpr size_t push_back(const value_t& x) {
        return this->_insert(npos, x);
    }
 
    constexpr size_t push_back(value_t&& x) {
        return this->_insert(npos, fennec::forward<value_t>(x));
    }
 
    template<typename...ArgsT>
    constexpr size_t emplace_back(ArgsT&&...args) {
        return this->_insert(npos, fennec::forward<ArgsT>(args)...);
    }
 
    constexpr void erase(size_t i) {
        assert(i < size(), "Index out of Bounds!");
        size_t n = _walk(i);
        _erase(n);
    }
 
    constexpr void erase(const iterator& it) {
        _erase(it._n);
    }
 
    constexpr void pop_front() {
        _erase(_root);
    }
 
    constexpr void pop_back() {
        _erase(_last);
    }
 
    constexpr void clear() {
        size_t i = _root;
        while (i != npos) {
            fennec::destruct(&_table[i]);
            i = this->_next(i);
        }
        _table.deallocate();
    }
 
 
// ITERATOR ============================================================================================================
 
 
    constexpr iterator begin() {
        return iterator(this, _root);
    }
 
    constexpr iterator end() {
        return iterator(this, npos);
    }
 
    constexpr const_iterator begin() const {
        return const_iterator(this, _root);
    }
 
    constexpr const_iterator end() const {
        return const_iterator(this, npos);
    }
 
 
    class iterator {
    public:
        ~iterator() {
            _list = nullptr;
        }
 
        // prefix operator
        constexpr friend iterator& operator++(iterator& rhs) {
            rhs._n = rhs._list->_next(rhs._n);
            return rhs;
        }
 
        constexpr friend iterator operator++(iterator& lhs, int) {
            iterator prev = lhs;
            ++lhs;
            return prev;
        }
 
        constexpr value_t& operator*() {
            return *(_list->_table[_n].value);
        }
 
        constexpr value_t* operator->() {
            return &*(_list->_table[_n].value);
        }
 
        constexpr bool operator==(const iterator& it) {
            return _list == it._list and _n == it._n;
        }
 
        constexpr bool operator!=(const iterator& it) {
            return _list != it._list or _n != it._n;
        }
 
    private:
        list*  _list;
        size_t _n;
        friend list;
 
        iterator(list* ls, size_t n)
            : _list(ls)
            , _n(n) {
        }
    };
 
    class const_iterator {
    public:
        ~const_iterator() {
            _list = nullptr;
        }
 
        // prefix operator
        constexpr friend const_iterator& operator++(const_iterator& rhs) {
            if (rhs._list->_next(rhs._n) < rhs._list->capacity()) {
                return rhs;
            }
            rhs._n = npos;
            return rhs;
        }
 
        constexpr friend const_iterator operator++(const_iterator& lhs, int) {
            const_iterator prev = lhs;
            ++lhs;
            return prev;
        }
 
        constexpr const value_t& operator*() {
            return *(_list->_table[_n].value);
        }
 
        constexpr const value_t* operator->() {
            return &*(_list->_table[_n].value);
        }
 
        constexpr bool operator==(const const_iterator& it) {
            return _list == it._list and _n == it._n;
        }
 
        constexpr bool operator!=(const const_iterator& it) {
            return _list != it._list or _n != it._n;
        }
 
    private:
        const list*  _list;
        size_t _n;
        friend list;
 
        const_iterator(const list* ls, size_t n)
            : _list(ls)
            , _n(n) {
        }
    };
 
private:
    allocation<node, alloc_t> _table;
    dynarray<size_t> _freed;
    size_t _root, _last, _size;
 
    friend class iterator;
 
    constexpr void _expand() {
        _table.creallocate(fennec::max(_table.capacity(), size_t(1)) * 2);
    }
 
    struct node {
        optional<value_t> value;
        size_t prev, next;
 
        constexpr node()
            : value()
            , prev(npos)
            , next(npos) {
        }
 
        constexpr node(size_t p, size_t n)
            : value()
            , prev(p)
            , next(n) {
        }
 
        constexpr node(size_t p, size_t n, value_t&& val)
            : value(fennec::forward<value_t>(val))
            , prev(p)
            , next(n) {
        }
 
        constexpr ~node() = default;
 
        constexpr void clear() {
            value = nullopt;
            prev = npos;
            next = npos;
        }
    };
 
    constexpr size_t _next(size_t n) const {
        return _table[n].next;
    }
 
    constexpr size_t _prev(size_t n) const {
        return _table[n].prev;
    }
 
    constexpr size_t _walk(size_t i) const {
        size_t n = _root;
        if (n == npos) return n;
        while (i > 0 && n != npos) {
            n = _next(n); --i;
        }
        return n;
    }
 
    constexpr size_t _next_free() {
        if (not _freed.empty()) {
            size_t n = _freed.back();
            _freed.pop_back();
            return n;
        }
        return _size;
    }
 
    template<typename...ArgsT>
    constexpr size_t _insert(size_t n, ArgsT&&...args) {
        if (size() == capacity()) {
            _expand();
        }
 
        size_t i = _next_free();
        ++_size;
        fennec::construct(&_table[i].value, fennec::forward<ArgsT>(args)...);
 
        if (_root == npos) {
            _table[i].prev = npos;
            _table[i].next = npos;
            _root = _last = i;
            return i;
        }
 
        if (n == npos) {
            _table[_last].next = i;
            _table[i].prev = _last;
            _table[i].next = npos;
            _last = i;
            return i;
        }
 
        _table[i].prev = _prev(n);
        _table[i].next = n;
        _table[n].prev = i;
        _root = n == _root ? i : _root;
        return i;
    }
 
    constexpr void _erase(size_t n) {
        if (n == npos) return;
 
        fennec::destruct(&_table[n].value);
        _freed.push_back(n);
        --_size;
 
        size_t prev = _prev(n);
        size_t next = _next(n);
 
        if (prev != npos) {
            _table[prev].next = next;
        }
 
        if (next != npos) {
            _table[next].prev = prev;
        }
 
        _root = (n == _root) ? next : _root;
        _last = (n == _last) ? prev : _last;
    }
};
 
}
 
#endif // FENNEC_CONTAINERS_LIST_H