FourBlockTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph_d.h>
#include <ogdf/basic/NodeArray.h>
 
#include <memory>
#include <vector>
 
namespace ogdf {
 
struct OGDF_EXPORT FourBlockTree {
    FourBlockTree() = default;
    FourBlockTree(const FourBlockTree&) = delete;
    FourBlockTree(FourBlockTree&&) = delete;
    FourBlockTree& operator=(const FourBlockTree&) = delete;
    FourBlockTree& operator=(FourBlockTree&&) = delete;
 
    ~FourBlockTree() {
        // free manually bottom-up to avoid stack overflow in case of deep tree
        postorder([](FourBlockTree& treeNode) -> void { treeNode.children.clear(); });
    }
 
    std::unique_ptr<Graph> g = std::make_unique<Graph>();
 
    NodeArray<node> originalNodes;
 
    adjEntry externalFace;
 
    FourBlockTree* parent;
 
    adjEntry parentFace;
 
    std::vector<std::unique_ptr<FourBlockTree>> children;
 
    static std::unique_ptr<FourBlockTree> construct(const Graph& g, adjEntry externalFace);
 
    template<typename _F>
    void preorder(_F callback) const {
        struct stackEntry {
            const FourBlockTree* node;
            std::vector<std::unique_ptr<FourBlockTree>>::const_iterator nextChild;
        };
 
        std::vector<stackEntry> stack;
        stack.push_back({this, children.begin()});
        callback(*this);
        while (!stack.empty()) {
            auto& it = stack.back().nextChild;
            if (it != stack.back().node->children.end()) {
                const FourBlockTree* child = it->get();
                ++it;
                stack.push_back({child, child->children.begin()});
                callback(*child);
            } else {
                stack.pop_back();
            }
        }
    }
 
    template<typename _F>
    void preorder(_F callback) {
        struct stackEntry {
            FourBlockTree* node;
            std::vector<std::unique_ptr<FourBlockTree>>::iterator nextChild;
        };
 
        std::vector<stackEntry> stack;
        stack.push_back({this, children.begin()});
        callback(*this);
        while (!stack.empty()) {
            auto& it = stack.back().nextChild;
            if (it != stack.back().node->children.end()) {
                FourBlockTree* child = it->get();
                ++it;
                stack.push_back({child, child->children.begin()});
                callback(*child);
            } else {
                stack.pop_back();
            }
        }
    }
 
    template<typename _F>
    void postorder(_F callback) const {
        struct stackEntry {
            const FourBlockTree* node;
            std::vector<std::unique_ptr<FourBlockTree>>::const_iterator nextChild;
        };
 
        std::vector<stackEntry> stack;
        stack.push_back({this, children.begin()});
        while (!stack.empty()) {
            auto& it = stack.back().nextChild;
            if (it != stack.back().node->children.end()) {
                const FourBlockTree* child = it->get();
                ++it;
                stack.push_back({child, child->children.begin()});
            } else {
                callback(*stack.back().node);
                stack.pop_back();
            }
        }
    }
 
    template<typename _F>
    void postorder(_F callback) {
        struct stackEntry {
            FourBlockTree* node;
            std::vector<std::unique_ptr<FourBlockTree>>::iterator nextChild;
        };
 
        std::vector<stackEntry> stack;
        stack.push_back({this, children.begin()});
        while (!stack.empty()) {
            auto& it = stack.back().nextChild;
            if (it != stack.back().node->children.end()) {
                FourBlockTree* child = it->get();
                ++it;
                stack.push_back({child, child->children.begin()});
            } else {
                callback(*stack.back().node);
                stack.pop_back();
            }
        }
    }
};
 
} // namespace ogdf