diff options
| author | Clifford Wolf <clifford@clifford.at> | 2014-11-07 15:21:03 +0100 |
|---|---|---|
| committer | Clifford Wolf <clifford@clifford.at> | 2014-11-07 15:21:03 +0100 |
| commit | 546e8b5fe7063caf0140d753d8c20614cbeae723 (patch) | |
| tree | 2a877507c2e9b098b3def2ad0bcd68a632ee5630 /kernel/utils.h | |
| parent | 461594bb83a3fd908bb6580763cf7f7aa37ef6a7 (diff) | |
Improved TopoSort determinism
Diffstat (limited to 'kernel/utils.h')
| -rw-r--r-- | kernel/utils.h | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/kernel/utils.h b/kernel/utils.h index 1779a9af..479effdc 100644 --- a/kernel/utils.h +++ b/kernel/utils.h @@ -128,12 +128,12 @@ public: // A simple class for topological sorting // ------------------------------------------------ -template<typename T> +template<typename T, typename C = std::less<T>> struct TopoSort { bool analyze_loops, found_loops; - std::map<T, std::set<T>> database; - std::set<std::set<T>> loops; + std::map<T, std::set<T, C>, C> database; + std::set<std::set<T, C>> loops; std::vector<T> sorted; TopoSort() @@ -145,7 +145,7 @@ struct TopoSort void node(T n) { if (database.count(n) == 0) - database[n] = std::set<T>(); + database[n] = std::set<T, C>(); } void edge(T left, T right) @@ -154,12 +154,12 @@ struct TopoSort database[right].insert(left); } - void sort_worker(const T &n, std::set<T> &marked_cells, std::set<T> &active_cells, std::vector<T> &active_stack) + void sort_worker(const T &n, std::set<T, C> &marked_cells, std::set<T, C> &active_cells, std::vector<T> &active_stack) { if (active_cells.count(n)) { found_loops = true; if (analyze_loops) { - std::set<T> loop; + std::set<T, C> loop; for (int i = GetSize(active_stack)-1; i >= 0; i--) { loop.insert(active_stack[i]); if (active_stack[i] == n) @@ -197,8 +197,8 @@ struct TopoSort sorted.clear(); found_loops = false; - std::set<T> marked_cells; - std::set<T> active_cells; + std::set<T, C> marked_cells; + std::set<T, C> active_cells; std::vector<T> active_stack; for (auto &it : database) |