blob: a6cd5384c70addf2d9514aa3214658bbb184a35d (
plain)
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
|
#include "Dependency_Sorter.h"
#include <algorithm>
#include <vector>
namespace DAnCE
{
/// Add a handler which has no dependencies
void
Dependency_Sorter::add_nondependent (const std::string &subject)
{
this->dep_map_[subject] = IH_DEPS ();
}
/// Add a dependency to the map.
void
Dependency_Sorter::add_dependency (const std::string &subject,
const IH_DEPS &deps)
{
this->dep_map_[subject] = deps;
}
void
Dependency_Sorter::add_dependency (const std::string &subject,
const std::string &install_after)
{
DEP_MAP::iterator after = this->dep_map_.find (install_after);
if (after == this->dep_map_.end ())
{
IH_DEPS tmp;
tmp.insert (install_after);
this->dep_map_[subject] = tmp;
}
else
{
after->second.insert (install_after);
}
}
void
Dependency_Sorter::calculate_order (Dependency_Sorter::INSTALL_ORDER &retval)
{
// Deps which have been added to the install order
IH_DEPS selected;
DEP_MAP tmp_dep = this->dep_map_;
while (retval.size () != this->dep_map_.size ())
{
bool updated (false);
for (DEP_MAP::iterator i = tmp_dep.begin ();
i != tmp_dep.end ();
++i)
{
if (i->second.size () == 0) // i.e., no dependencies
{
retval.push_back (i->first);
selected.insert (i->first);
updated = true;
tmp_dep.erase (i);
break;
}
if (selected.size () >= i->second.size ())
{
std::vector< std::string > tmp (i->second.size ());
std::set_intersection (i->second.begin (), i->second.end (),
selected.begin (), selected.end (),
tmp.begin ());
if (tmp.size () == i->second.size ()) // i.e., all deps satisfied
{
retval.push_back (i->first);
selected.insert (i->first);
updated = true;
tmp_dep.erase (i);
break;
}
}
}
if (!updated) // i.e., we weren't able to add a new dep
{
throw Invalid_Install_Order ();
}
}
}
}
|
