set.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_SET_H
#define FENNEC_CONTAINERS_SET_H
 
// https://programming.guide/robin-hood-hashing.html
 
#include <fennec/containers/optional.h>
#include <fennec/containers/set.h>
#include <fennec/lang/compare.h>
#include <fennec/math/ext/primes.h>
#include <fennec/memory/allocator.h>
#include <fennec/lang/hashing.h>
 
namespace fennec
{
 
template<typename TypeT, class Hash = hash<TypeT>, class Equals = equality<TypeT>, class Alloc = allocator<TypeT>>
struct set {
 
// Definitions =========================================================================================================
public:
    using alloc_t = typename allocator_traits<Alloc>::template rebind<TypeT>;
    using hash_t = Hash;
    using equal_t = Equals;
    using elem_t = TypeT;
 
    class iterator;
    static constexpr size_t npos = -1;
    static constexpr double default_load = 0.8;
 
private:
    struct node {
        optional<elem_t> value;
        int psl;
 
        constexpr node() = default;
        constexpr ~node() = default;
    };
 
// Constructors ========================================================================================================
public:
 
 
    constexpr set()
        : _alloc()
        , _hash()
        , _size(0)
        , _sumpsl(0)
        , _load(default_load) {
    };
 
    constexpr set(const hash_t& hash)
        : _alloc()
        , _hash(hash)
        , _size(0)
        , _sumpsl(0)
        , _load(default_load) {
    }
 
    constexpr set(const alloc_t& alloc)
        : _alloc(alloc)
        , _hash()
        , _size(0)
        , _sumpsl(0)
        , _load(default_load) {
    }
 
    constexpr set(const hash_t& hash, const alloc_t& alloc)
        : _alloc(alloc)
        , _hash(hash)
        , _size(0)
        , _sumpsl(0)
        , _load(default_load) {
    }
 
    constexpr set(const set& set)
        : _alloc(set._alloc)
        , _hash(set._hash)
        , _size(set._size)
        , _sumpsl(set._sumpsl)
        , _load(set._load) {
    }
 
    constexpr set(set&& set) noexcept
        : _alloc(fennec::move(set._alloc))
        , _hash(fennec::move(set._hash))
        , _size(fennec::move(set._size))
        , _sumpsl(set._sumpsl)
        , _load(set._load) {
    }
 
    constexpr ~set() {
        for (size_t i = 0; i < capacity(); ++i) {
            _alloc[i].value = nullopt;
        }
    }
 
 
 
// Properties ==========================================================================================================
 
 
    constexpr size_t size() const {
        return _size;
    }
 
    constexpr bool empty() const {
        return _size == 0;
    }
 
    constexpr size_t capacity() const {
        return _alloc.size();
    }
 
 
 
// Access ==============================================================================================================
 
 
    constexpr iterator find(const elem_t& val) const {
        if (capacity() == 0) {
            return end();
        }
        size_t s = _hash(val) % capacity();              // Initial search index
        int    psl = (_size != 0) ? _sumpsl / _size : 0; // Initial psl
        size_t i = (s + psl) % capacity();               // Median search
        size_t n = 0;
 
        // Check the first element;
        if (_alloc[i].psl >= psl && _alloc[i].value) {
            if (_equal(*_alloc[i].value, val)) {
                return iterator(this, i);
            }
        }
 
        // Loop while there is a value and its psl is greater than our probe
        while (true) {
            ++n;
            size_t i0 = (i + capacity() - n) % capacity(); // Prevent index underflow
            size_t i1 = (i + n) % capacity();
            int    p0 = psl - n, p1 = psl + n;
            bool   c0  = p0 >= 0 && _alloc[i0].psl >= p0, c1 = _alloc[i1].psl >= p1; // Check that we are in range
 
            if (c0 && _alloc[i0].value) {
                if (_equal(*_alloc[i0].value, val)) {
                    return iterator(this, i0);
                }
            }
 
            if (c1 && _alloc[i1].value) {
                if (_equal(*_alloc[i1].value, val)) {
                    return iterator(this, i1);
                }
            }
 
            if (not(c0 or c1)) {
                break;
            }
        }
 
        return iterator(this, npos);
    }
 
    constexpr bool contains(const elem_t& val) const {
        return this->find(val) != end();
    }
 
    constexpr elem_t* at(const iterator& it) {
        if (it == end()) {
            return nullptr;
        }
        if (not _alloc[it._i].value) {
            return nullptr;
        }
        return &*_alloc[it._i].value;
    }
 
    constexpr const elem_t* at(const iterator& it) const {
        if (not _alloc[it._i].value) return nullptr;
        return &*_alloc[it._i].value;
    }
 
 
// Modifiers ===========================================================================================================
 
 
    constexpr iterator insert(elem_t&& val) {
        return this->_insert(fennec::forward<elem_t>(val));
    }
 
    constexpr iterator insert(const elem_t& val) {
        return this->_insert(val);
    }
 
    template<typename...ArgsT>
    constexpr iterator emplace(ArgsT&&...args) {
        return this->_insert(fennec::forward<ArgsT>(args)...);
    }
 
    constexpr void erase(iterator it) {
        size_t i = it._i;
        if (i >= capacity()) {
            return;
        } // These are separated due to compilers being inconsistent
        if (not _alloc[i].value) {
            return;
        }
 
        _alloc[i].value = nullopt;
        _sumpsl -= _alloc[i].psl;
        --_size;
        size_t p = i;
        while (_alloc[i = (i + 1) % capacity()].value) {
            if (_alloc[i].psl == 0) break;
 
            fennec::swap(_alloc[p].value, _alloc[i].value);
            --_alloc[p].psl, --_sumpsl;
            p = i;
        }
    }
 
    constexpr void erase(const elem_t& val) {
        this->erase(this->find(val));
    }
 
    constexpr void clear() {
        for (size_t i = 0; i < _alloc.capacity(); ++i) {
 
        }
    }
 
 
 
// ITERATOR ============================================================================================================
 
 
    constexpr iterator begin() const {
        iterator it(this, 0);
        if (not _alloc[it._i].value) {
            ++it;
        }
        return it;
    }
 
    constexpr iterator end() const {
        return iterator(this, npos);
    }
 
 
    class iterator {
    public:
        constexpr iterator(const set* set, size_t i)
            : _set(set)
            , _i(i) {
        }
 
        constexpr ~iterator() {
            _set = nullptr;
        }
 
        // prefix operator
        constexpr friend iterator& operator++(iterator& rhs) {
            while (++rhs._i < rhs._set->capacity()) {
                if (rhs._set->_alloc[rhs._i].value) {
                    return rhs;
                }
            }
            rhs._i = npos;
            return rhs;
        }
 
        constexpr friend iterator operator++(iterator& lhs, int) {
            iterator prev = lhs;
            ++lhs;
            return prev;
        }
 
        constexpr const elem_t& operator*() const {
            return *_set->_alloc[_i].value;
        }
 
        constexpr const elem_t* operator->() const {
            if (not _set->_alloc[_i].value) return nullptr;
            return &*_set->_alloc[_i].value;
        }
 
        constexpr bool operator==(const iterator& it) const {
            return _set == it._set and _i == it._i;
        }
 
        constexpr bool operator!=(const iterator& it) const {
            return _set != it._set or _i != it._i;
        }
 
        constexpr size_t index() const { return _i; }
 
    private:
        const set* _set;
        size_t _i;
        friend set;
    };
 
 
// PRIVATE =============================================================================================================
 
private:
    constexpr void _expand() {
        set cpy; // Create a new set
        cpy._alloc.resize(
            fennec::next_prime2(_alloc.capacity())
        );
 
        // rehash
        for (size_t i = 0; i < capacity(); ++i) {
            if (_alloc[i].value) {
                cpy.insert(fennec::move(*_alloc[i].value));
            }
        }
 
        // Swap buffers
        fennec::swap(_alloc, cpy._alloc);
    }
 
    template<typename...ArgsT>
    constexpr iterator _insert(ArgsT&&...args) {
        if (_size == 0 or static_cast<float>(_size) / capacity() >= _load) { // expand when full
            _expand();
        }
 
        elem_t value(fennec::forward<ArgsT>(args)...);
        size_t i = _hash(value) % capacity(); // Initial search index
        int psl = 0;
        while (_alloc[i].value) { // Search for empty cell
            if (_equal(*_alloc[i].value, value)) { // Check to see if this element is already inserted
                return iterator(this, i);
            }
            if (psl > _alloc[i].psl) { // When psl is higher, swap
                _sumpsl += psl - _alloc[i].psl;
                fennec::swap(_alloc[i].psl, psl);
                fennec::swap(*_alloc[i].value, value);
            }
            i = (i + 1) % capacity(); ++psl;
        }
        _alloc[i].value = fennec::move(value);
        _sumpsl += (_alloc[i].psl = psl);
        ++_size;
        return iterator(this, npos);
    }
 
    dynarray<node, alloc_t> _alloc;
    hash_t  _hash;
    equal_t _equal;
    size_t  _size;
    size_t  _sumpsl;
    float   _load;
};
 
}
 
#endif // FENNEC_CONTAINERS_SET_H