mirror of
https://github.com/mudita/MuditaOS.git
synced 2026-01-16 01:48:42 -05:00
33 lines
1.1 KiB
C++
33 lines
1.1 KiB
C++
// Copyright (c) 2017-2024, Mudita Sp. z.o.o. All rights reserved.
|
|
// For licensing, see https://github.com/mudita/MuditaOS/blob/master/LICENSE.md
|
|
|
|
#pragma once
|
|
|
|
#include "SystemManager/DependencyGraph.hpp"
|
|
|
|
#include <list>
|
|
#include <string_view>
|
|
#include <unordered_map>
|
|
#include <vector>
|
|
|
|
namespace sys::graph
|
|
{
|
|
class TopologicalSort : public DependencySortingStrategy
|
|
{
|
|
public:
|
|
[[nodiscard]] auto sort(const graph::Nodes &nodes) -> graph::Nodes override;
|
|
|
|
private:
|
|
using Edges = std::unordered_map<std::string_view, std::list<std::string_view>>;
|
|
using VisitedMap = std::unordered_map<std::string_view, bool>;
|
|
|
|
[[nodiscard]] auto createEdges(const graph::Nodes &nodes) const -> Edges;
|
|
[[nodiscard]] auto createVisitedMap(const graph::Nodes &nodes) const -> VisitedMap;
|
|
void visit(
|
|
std::string_view node, Edges &edges, VisitedMap &visited, int layer, std::vector<std::string_view> &out);
|
|
|
|
[[nodiscard]] auto prepareOutput(const graph::Nodes &nodes, const std::vector<std::string_view> &sorted) const
|
|
-> graph::Nodes;
|
|
};
|
|
} // namespace sys::graph
|