1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #pragma once
#include <unordered_map>
#include <unordered_set>
#include <vector>
namespace easy::utils {
template <class tt> class dep_sort {
public:
struct relation;
using relation_type = relation;
struct result;
using result_type = result;
using value_type = tt;
using map_type = std::unordered_map<value_type, relation_type>;
public:
struct relation {
std::size_t dependencies;
std::unordered_set<value_type> dependents;
};
struct result {
std::vector<value_type> sorted;
std::vector<value_type> non_sorted;
bool has_cycles() const { return non_sorted.empty() == false; }
};
private:
map_type _values;
public:
bool has_node(const value_type& node) {
return _values.contains(node);
}
void clear() { _values.clear(); }
bool add_node(const value_type &node) {
auto res = _values.insert({node, {}});
return res.second;
}
bool add_node(value_type &&node) {
auto res = _values.insert({std::move(node), {}});
return res.second;
}
bool has_dependency(const value_type &node, const value_type &dependency) {
if (!has_node(node))
return false;
const auto &value = _values.at(node);
return value.dependents.find(dependency) != value.dependents.end();
}
bool add_dependency(const value_type &node, value_type &&dependency) {
if (node == dependency)
return false;
auto res_value = _values.insert({std::move(dependency), {}});
auto &dependents = res_value.first->second.dependents;
if (dependents.find(node) == dependents.end()) {
dependents.insert(node);
_values[node].dependencies += 1;
return true;
}
return false;
}
bool add_dependency(const value_type &node, const value_type &dependency) {
if (node == dependency)
return false;
auto res_value = _values.insert({dependency, {}});
auto &dependents = res_value.first->second.dependents;
if (dependents.find(node) == dependents.end()) {
dependents.insert(node);
_values[node].dependencies += 1;
return true;
}
return false;
}
template <template <typename, typename...> class container_tt, typename... container_tt_params>
bool add_dependencies(
const value_type &node,
const container_tt<value_type, container_tt_params...> &dependencies) {
for (const auto &one : dependencies) {
if (!add_dependency(node, one))
return false;
}
return true;
}
result_type sort() const {
auto copyed = *this;
result_type res;
for (const auto &[node, relations] : copyed._values) {
if (relations.dependencies == 0) {
res.sorted.push_back(node);
}
}
for (std::size_t index = 0; index < res.sorted.size(); ++index) {
for (const auto &one : copyed._values[res.sorted.at(index)].dependents) {
if (--copyed._values[one].dependencies == 0) {
res.sorted.push_back(one);
}
}
}
for (const auto &[node, relations] : copyed._values) {
if (relations.dependencies != 0) {
res.non_sorted.push_back(node);
}
}
return res;
}
};
};
|
