treewalker.h

/*
  This file is part of the KDAB State Machine Editor Library.

  SPDX-FileCopyrightText: 2014-2021 Klarälvdalens Datakonsult AB, a KDAB Group company <info@kdab.com>
  Author: Kevin Funk <kevin.funk@kdab.com>

  SPDX-License-Identifier: LGPL-2.1-only OR LicenseRef-KDAB-KDStateMachineEditor

  Licensees holding valid commercial KDAB State Machine Editor Library
  licenses may use this file in accordance with the KDAB State Machine Editor
  Library License Agreement provided with the Software.

  Contact info@kdab.com if any conditions of this licensing are not clear to you.
*/

#ifndef KDSME_UTIL_TREEWALKER_H
#define KDSME_UTIL_TREEWALKER_H

#include "kdsme_core_export.h"

#include <QObject>

#include <functional>

namespace KDSME {

template<typename T>
struct TreeWalkerTrait
{
    static QList<T> children(T item) { Q_UNUSED(item); return QList<T>(); }
};

template<typename T>
class TreeWalker
{
public:
    enum VisitResult {
        ContinueWalk, 
        RecursiveWalk, 
        StopWalk 
    };

    enum TraversalType {
        PreOrderTraversal,
        PostOrderTraversal,
    };

    typedef std::function<VisitResult(T)> VisitFunction;

    explicit TreeWalker(TraversalType type = PreOrderTraversal)
        : m_traversalType(type) {}

    bool walkItems(T item, const VisitFunction& visit)
    {
        if (!item)
            return false;

        bool continueWalk = true;
        if (m_traversalType == PreOrderTraversal) {
            continueWalk = (visit(item) == TreeWalker::RecursiveWalk);
        }
        Q_ASSERT(item);
        foreach (T child, TreeWalkerTrait<T>::children(item)) {
            if (!walkItems(child, visit))
                return false;
        }
        if (m_traversalType == PostOrderTraversal) {
            continueWalk = (visit(item) == TreeWalker::RecursiveWalk);
        }
        return continueWalk;
    }

    bool walkChildren(T item, const VisitFunction& visit)
    {
        if (!item)
            return false;

        foreach (T child, TreeWalkerTrait<T>::children(item)) {
            if (!walkItems(child, visit))
                return false;
        }
        return true;
    }

private:
    TraversalType m_traversalType;
};

}

#endif // TREEWALKER_H