FreeList.hpp

Go to the documentation of this file.

//
// Created by cbihan on 20/08/2021.
//
 
#pragma once
 
#include <functional>
 
namespace Babel
{
 
    template<class T>
    class FreeList
    {
    public:
        static constexpr int EndOfList = -1;
 
        FreeList();
 
        int insert(T element);
 
        void remove(int n);
 
        void clear();
 
        [[nodiscard]] size_t size() const;
 
        void reset();
 
        [[nodiscard]] std::vector<T> toVector() const;
 
        [[nodiscard]] int range() const;
 
        [[nodiscard]] int findIndex(T element) const;
 
        T &operator[](int n);
 
        const T &operator[](int n) const;
 
        void forEach(std::function<bool(T &, int)> pred);
 
        void forEach(std::function<bool(T &)> pred);
 
        void forEach(std::function<bool(const T &, int)> pred) const;
 
        void forEach(std::function<bool(const T &)> pred) const;
 
    private:
        std::vector<std::pair<T, int>> _data{};
        int _firstFree;
    };
 
    template<class T>
    FreeList<T>::FreeList()
        : _firstFree(EndOfList)
    {
    }
 
    template<class T>
    int FreeList<T>::insert(T element)
    {
        if (this->_firstFree != EndOfList) {
            const int index = this->_firstFree;
            this->_firstFree = this->_data[this->_firstFree].second;
            this->_data[index].first = std::move(element);
            return index;
        } else {
            this->_data.push_back({element, EndOfList});
            return static_cast<int>(this->_data.size() - 1);
        }
    }
 
    template<class T>
    void FreeList<T>::remove(int n)
    {
        // the this->_firstFree index should be the lowest available and so on to use the lowest possible index at each insertion
        // it helps for the forEach function and if we want to shrink the vector
        if (n < this->_firstFree || this->_firstFree == EndOfList) {
            this->_data[n].second = this->_firstFree;
            this->_firstFree = n;
        } else {
            int freeIndex = this->_firstFree;
            int prevFreeIndex = freeIndex;
            while (freeIndex < n && freeIndex != EndOfList) {
                prevFreeIndex = freeIndex;
                freeIndex = this->_data[freeIndex].second;
            }
            this->_data[n].second = freeIndex;
            this->_data[prevFreeIndex].second = n;
        }
    }
 
    template<class T>
    void FreeList<T>::clear()
    {
        this->_data.clear();
        this->_firstFree = EndOfList;
    }
 
    template<class T>
    int FreeList<T>::range() const
    {
        return static_cast<int>(this->_data.size());
    }
 
    template<class T>
    T &FreeList<T>::operator[](int n)
    {
        return this->_data[n].first;
    }
 
    template<class T>
    const T &FreeList<T>::operator[](int n) const
    {
        return this->_data[n].first;
    }
 
    template<class T>
    int FreeList<T>::findIndex(T element) const
    {
        int indexFound = -1;
        this->forEach([&element, &indexFound](const auto &elementList, int elementIndex) {
            if (element == elementList) {
                indexFound = elementIndex;
                return false;
            }
            return true;
        });
        return indexFound;
    }
 
    template<class T>
    void FreeList<T>::forEach(std::function<bool(T &, int)> pred)
    {
        int next_empty_index = this->_firstFree;
 
        for (int i = 0; i < static_cast<int>(this->_data.size()); i++) {
            if (i == next_empty_index) {
                next_empty_index = this->_data[i].second;
                continue;
            }
            if (!pred(this->_data[i].first, i)) {
                break;
            }
        }
    }
 
    template<class T>
    void FreeList<T>::forEach(std::function<bool(T &)> pred)
    {
        this->forEach([&pred](T &element, int) {
            return pred(element);
        });
    }
 
    template<class T>
    void FreeList<T>::forEach(std::function<bool(const T &, int)> pred) const
    {
        int next_empty_index = this->_firstFree;
 
        for (int i = 0; i < static_cast<int>(this->_data.size()); i++) {
            if (i == next_empty_index) {
                next_empty_index = this->_data[i].second;
                continue;
            }
            if (!pred(this->_data[i].first, i)) {
                break;
            }
        }
    }
 
    template<class T>
    void FreeList<T>::forEach(std::function<bool(const T &)> pred) const
    {
        this->forEach([&pred](const T &element, int) {
            return pred(element);
        });
    }
 
    template<class T>
    std::vector<T> FreeList<T>::toVector() const
    {
        std::vector<T> v;
        this->forEach([&v](const T &element) {
            v.push_back(element);
            return true;
        });
        return v;
    }
 
    template<class T>
    void FreeList<T>::reset()
    {
        if (this->_data.empty()) {
            return;
        }
        int size = this->_data.size();
        this->_firstFree = 0;
        for (int i = 0; i < size; i++) {
            this->_data[i].second = i == size - 1 ? EndOfList : i + 1;
        }
    }
 
    template<class T>
    size_t FreeList<T>::size() const
    {
        size_t size = 0;
        this->forEach([&size](const T &, int) {
            size++;
            return true;
        });
        return size;
    }
}