hierarchy_operations.h

#pragma once
 
#include <cstddef>
#include <vector>
 
#include <glm/glm.hpp>
 
#include "ecs/scene.h"
#include "ecs/component/core/hierarchy.h"
#include "ecs/component/core/transform.h"
 
namespace Vkm::Engine::HierarchyOperations {

void setParent(Scene& scene, EntityId child, EntityId parent, EntityId before = {});

void removeFromParent(Scene& scene, EntityId entity);

glm::mat4 computeWorldMatrix(const Scene& scene, EntityId entity);

constexpr uint32_t MAX_DEPTH = 32;

void warnWalkBound(const char* walk, size_t bound);
 
namespace detail {

class SearchQueue {
    public:
        SearchQueue();
        ~SearchQueue();
 
        SearchQueue(const SearchQueue& other) = delete;
        SearchQueue& operator=(const SearchQueue& other) = delete;
 
        SearchQueue(SearchQueue && other) = delete;
        SearchQueue& operator=(SearchQueue && other) = delete;
 
    public:
        std::vector<EntityId>& entries() { return m_queue; }
 
    private:
        std::vector<EntityId> m_queue;
};
 
} // namespace detail

template<typename Fn>
void forEachChild(const Scene& scene, EntityId parent, Fn&& fn) {
    const Hierarchy* node = scene.tryGet<Hierarchy>(parent);
    if (!node) return;
 
    const size_t bound = scene.entityCount();
    size_t       step  = 0;
    for (EntityId child = node->firstChild; child; ++step) {
        if (step >= bound) {
            warnWalkBound("sibling-list walk", bound);
            return;
        }
        // Read before fn, which may remove this child's Hierarchy.
        const Hierarchy* held = scene.tryGet<Hierarchy>(child);
        const EntityId   next = held ? held->nextSibling : EntityId{};
        fn(child);
        child = next;
    }
}

template<typename Fn>
void forSelfAndAncestors(const Scene& scene, EntityId entity, Fn&& fn) {
    EntityId at = entity;
    for (uint32_t step = 0; at; ++step) {
        if (step >= MAX_DEPTH) {
            warnWalkBound("ancestor walk", MAX_DEPTH);
            return;
        }
        if (!fn(at)) return;
        const Hierarchy* node = scene.tryGet<Hierarchy>(at);
        if (!node) return;
        at = node->parent;
    }
}

template<typename Match>
EntityId findInSelfOrDescendantsIf(const Scene& scene, EntityId root, Match match) {
    if (!root) return {};
    if (match(root)) return root;
 
    detail::SearchQueue queue;
    std::vector<EntityId>& pending = queue.entries();
    pending.push_back(root);
    const size_t bound = scene.entityCount();
    for (size_t i = 0; i < pending.size(); ++i) {
        if (pending.size() > bound) {
            warnWalkBound("breadth-first search", bound);
            return {};
        }
        EntityId found{};
        forEachChild(scene, pending[i], [&](EntityId child) {
            if (!found && match(child)) found = child;
            pending.push_back(child);
        });
        if (found) return found;
    }
    return {};
}

template<typename T>
EntityId findInSelfOrDescendants(const Scene& scene, EntityId root) {
    return findInSelfOrDescendantsIf(scene, root, [&](EntityId id) { return scene.has<T>(id); });
}

template<typename T>
EntityId findInSelfOrAncestors(const Scene& scene, EntityId leaf) {
    EntityId found{};
    forSelfAndAncestors(scene, leaf, [&](EntityId at) {
        if (scene.has<T>(at)) found = at;
        return !found;
    });
    return found;
}

inline bool isAncestorOf(const Scene& scene, EntityId ancestor, EntityId node) {
    if (!ancestor || !node || ancestor == node) return false;
 
    const Hierarchy* at = scene.tryGet<Hierarchy>(node);
    for (size_t step = 0; at && at->parent && step < scene.entityCount(); ++step) {
        if (at->parent == ancestor) return true;
        at = scene.tryGet<Hierarchy>(at->parent);
    }
    return false;
}

void destroyHierarchy(Scene& scene, EntityId entity);

std::vector<EntityId> collectSubtree(const Scene& scene, EntityId root);
 
} // namespace Vkm::Engine::HierarchyOperations