<commit_before>#ifndef TUFAO_DEPENDENCYTREE_H
#define TUFAO_DEPENDENCYTREE_H

#include <QtCore/QSet>
#include <QtCore/QList>
#include <QtCore/QPair>

#include <algorithm>

namespace Tufao {

// If an exception is throw, there will be no memory leaks, but the object state
// may become invalid
template<class T, class Container = QList<T>>
class DependencyTree
{
public:
    DependencyTree() = default;
    DependencyTree(const DependencyTree &) = delete;
    DependencyTree &operator =(const DependencyTree &) = delete;

    bool addNode(const T &value, const Container &dependencies = Container{})
    {
        QSet<T> uniqueDependencies;

        // fill uniqueDependencies
        for (const auto &d: dependencies) {
            if (d != T())
                uniqueDependencies.insert(d);
        }

        if (uniqueDependencies.empty()) {
            if (rootNodes.contains(value))
                return false;

            unsatisfiedDependencies.remove(value);
            rootNodes.insert(value);
            return true;
        }

        auto &edges = this->edges;
        auto &rootNodes = this->rootNodes;

        auto contains = [&edges,&rootNodes](const T &value) -> bool {
            if (rootNodes.contains(value))
                return true;

            for (const auto &edge: edges) {
                if (edge.first == value || edge.second == value)
                    return true;
            }

            return false;
        };

        auto depends = [&edges](const T &first, const T &second) -> bool {
            QList<T> remaining{first};

            for (QSet<T> visited;remaining.size();) {
                T current = remaining.front();

                if (current == second)
                    return true;

                remaining.pop_front();
                visited.insert(current);

                std::for_each(std::lower_bound(edges.begin(), edges.end(),
                                               qMakePair(current, T())),
                              std::upper_bound(edges.begin(), edges.end(),
                                               qMakePair(current, T())),
                              [&visited,&remaining](const QPair<T, T> &value) {
                    if (!visited.contains(value.second))
                        remaining.push_back(value.second);
                });
            }

            return false;
        };

        // Node already was added
        if (contains(value)) {
            // Node metadata already was added
            if (!unsatisfiedDependencies.contains(value))
                return false;

            for (const auto &d: uniqueDependencies) {
                // Circular dependency
                if (depends(d, value))
                    return false;
            }

            unsatisfiedDependencies.remove(value);
        }

        for (const auto &d: uniqueDependencies) {
            if (!contains(d))
                unsatisfiedDependencies.insert(d);

            auto edge = qMakePair(value, d);
            edges.insert(std::lower_bound(edges.begin(), edges.end(), edge),
                         edge);
        }

        return true;
    }

    bool hasUnsatisfiedDependency() const
    {
        return unsatisfiedDependencies.size();
    }

    Container sorted() const
    {
        Container sorted;

        auto current = edges;

        for (const auto &n: rootNodes) {
            sorted.push_back(n);

            for (typename QList<QPair<T, T>>::size_type i = 0
                 ;i != current.size();++i) {
                if (current[i].second == n)
                    current.removeAt(i--);
            }
        }

        auto hasDependencies = [&current](const T &value) -> bool {
            auto it = std::lower_bound(current.begin(), current.end(),
                                       qMakePair(value, T()));

            if (it != current.end() && it->first == value)
                return true;

            return false;
        };

        auto findSink = [&current,&hasDependencies]() -> T {
            for (const auto &e: current) {
                QSet<T> visited;

                if (visited.contains(e.second))
                    continue;

                if (!hasDependencies(e.second))
                    return e.second;

                visited.insert(e.second);
            }

            return T();
        };

        while (current.size()) {
            auto sink = findSink();
            sorted.push_back(sink);

            for (typename QList<QPair<T, T>>::size_type i = 0
                 ;i != current.size();++i) {
                if (current[i].second == sink)
                    current.removeAt(i--);
            }
        }<commit_msg>Fix bugs in DependencyTree<commit_after>#ifndef TUFAO_DEPENDENCYTREE_H
#define TUFAO_DEPENDENCYTREE_H

#include <QtCore/QSet>
#include <QtCore/QList>
#include <QtCore/QPair>

#include <algorithm>

namespace Tufao {

// If an exception is throw, there will be no memory leaks, but the object state
// may become invalid
template<class T, class Container = QList<T>>
class DependencyTree
{
public:
    DependencyTree() = default;
    DependencyTree(const DependencyTree &) = delete;
    DependencyTree &operator =(const DependencyTree &) = delete;

    bool addNode(const T &value, const Container &dependencies = Container{})
    {
        QSet<T> uniqueDependencies;

        // fill uniqueDependencies
        for (const auto &d: dependencies) {
            if (d == value)
                return false;

            if (d != T())
                uniqueDependencies.insert(d);
        }

        if (uniqueDependencies.empty()) {
            auto nodeExists = [this](const T &value) -> bool {
                if (unsatisfiedDependencies.contains(value))
                    return false;

                if (rootNodes.contains(value))
                    return true;

                for (const auto &e: edges) {
                    if (e.first == value || e.second == value)
                        return true;
                }

                return false;
            };

            if (nodeExists(value))
                return false;

            unsatisfiedDependencies.remove(value);
            rootNodes.insert(value);
            return true;
        }

        auto contains = [this](const T &value) -> bool {
            if (rootNodes.contains(value))
                return true;

            for (const auto &edge: edges) {
                if (edge.first == value || edge.second == value)
                    return true;
            }

            return false;
        };

        auto depends = [this](const T &first, const T &second) -> bool {
            QList<T> remaining{first};
            QSet<T> visited;

            while (remaining.size()) {
                T current = remaining.front();

                if (current == second)
                    return true;

                remaining.pop_front();
                visited.insert(current);

                for (auto it = std::lower_bound(edges.begin(), edges.end(),
                                                qMakePair(current, T())),
                         end = edges.end();it != end;++it) {
                    if (it->first != current)
                        break;

                    if (!visited.contains(it->second))
                        remaining.push_back(it->second);
                }
            }

            return false;
        };

        // Node already was added
        if (contains(value)) {
            // Node metadata already was added
            if (!unsatisfiedDependencies.contains(value))
                return false;

            for (const auto &d: uniqueDependencies) {
                // Circular dependency
                if (depends(d, value))
                    return false;
            }

            unsatisfiedDependencies.remove(value);
        }

        for (const auto &d: uniqueDependencies) {
            if (!contains(d))
                unsatisfiedDependencies.insert(d);

            auto edge = qMakePair(value, d);
            edges.insert(std::lower_bound(edges.begin(), edges.end(), edge),
                         edge);
        }

        return true;
    }

    bool hasUnsatisfiedDependency() const
    {
        return unsatisfiedDependencies.size();
    }

    Container sorted() const
    {
        if (unsatisfiedDependencies.size())
            return Container{};

        Container sorted;

        auto current = edges;

        auto nodeExists = [&current,this](const T &value) -> bool {
            if (unsatisfiedDependencies.contains(value))
                return false;

            if (rootNodes.contains(value))
                return true;

            for (const auto &e: current) {
                if (e.first == value || e.second == value)
                    return true;
            }

            return false;
        };

        for (const auto &n: rootNodes) {
            sorted.push_back(n);

            QSet<T> removed;

            for (typename QList<QPair<T, T>>::size_type i = 0
                 ;i != current.size();++i) {
                if (current[i].second == n) {
                    removed.insert(current[i].first);
                    current.removeAt(i--);
                }
            }

            for (const auto &n: removed) {
                if (!nodeExists(n))
                    sorted.push_back(n);
            }
        }

        auto hasDependencies = [&current](const T &value) -> bool {
            auto it = std::lower_bound(current.begin(), current.end(),
                                       qMakePair(value, T()));

            if (it != current.end() && it->first == value)
                return true;

            return false;
        };

        auto findSink = [&current,&hasDependencies,&nodeExists]() -> T {
            QSet<T> visited;

            for (const auto &e: current) {
                if (visited.contains(e.second))
                    continue;

                if (!hasDependencies(e.second))
                    return e.second;

                visited.insert(e.second);
            }

            return T();
        };

        while (current.size()) {
            auto sink = findSink();
            sorted.push_back(sink);

            QSet<T> removed;

            for (typename QList<QPair<T, T>>::size_type i = 0
                 ;i != current.size();++i) {
                if (current[i].second == sink) {
                    removed.insert(current[i].first);
                    current.removeAt(i--);
                }
            }

            for (const auto &n: removed) {
                if (!nodeExists(n))
                    sorted.push_back(n);
            }
        }
{'fraction_non_alphanumeric': 0.11160672799925657, 'fraction_numerical': 0.0003717126661090977, 'mean_word_length': 1.3549234135667396, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4521785', 'n_tokens_mistral': 2887, 'n_tokens_neox': 2661, 'n_words': 665}