+#include "systemscheduler.h"
+#include <limits>
+#include <msp/core/algorithm.h>
+#include <msp/strings/format.h>
+#include "system.h"
+
+using namespace std;
+
+namespace Msp::Game {
+
+SystemScheduler::SystemScheduler(Reflection::Reflector &r):
+ reflector(r)
+{ }
+
+void SystemScheduler::add_system(System &s)
+{
+ nodes.emplace_back(&s, reflector.find_class(typeid(s)));
+}
+
+void SystemScheduler::remove_system(System &s)
+{
+ erase_if(nodes, [&s](const GraphNode &n){ return n.system==&s; });
+ for(auto i=groups.begin(); i!=groups.end(); )
+ {
+ erase_if(i->systems, [&s](System *gs){ return gs==&s; });
+ if(i->systems.empty())
+ i = groups.erase(i);
+ else
+ ++i;
+ }
+}
+
+void SystemScheduler::schedule()
+{
+ for(GraphNode &n: nodes)
+ {
+ n.scheduled_order = ~0U;
+ n.predecessors.clear();
+ }
+
+ for(auto i=nodes.begin(); i!=nodes.end(); ++i)
+ for(auto j=i; ++j!=nodes.end(); )
+ {
+ int order = get_order(*i, *j);
+ if(order<0)
+ j->predecessors.push_back(&*i);
+ else if(order>0)
+ i->predecessors.push_back(&*j);
+ }
+
+ groups.clear();
+ unsigned unscheduled_count = nodes.size();
+ while(unscheduled_count)
+ {
+ unsigned order = groups.size();
+ Group &group = groups.emplace_back();
+ for(GraphNode &n: nodes)
+ if(!~n.scheduled_order && ranges::all_of(n.predecessors, [order](GraphNode *p){ return p->scheduled_order<order; }))
+ {
+ group.systems.push_back(n.system);
+ n.scheduled_order = order;
+ --unscheduled_count;
+ }
+ }
+}
+
+int SystemScheduler::get_order(const GraphNode &node1, const GraphNode &node2)
+{
+ if(int order = get_explicit_order(node1, node2))
+ return order;
+ return get_data_order(node1, node2);
+}
+
+int SystemScheduler::get_explicit_order(const GraphNode &node1, const GraphNode &node2)
+{
+ const vector<System::Dependency> &deps1 = node1.system->get_dependencies();
+ const vector<System::Dependency> &deps2 = node2.system->get_dependencies();
+
+ auto get_dep_type = [](const System::Dependency &d){ return &d.get_type(); };
+ auto i = ranges::find(deps1, node2.type, get_dep_type);
+ int flags1 = (i!=deps1.end() ? i->get_flags()&System::ORDER_MASK : 0);
+ i = ranges::find(deps2, node1.type, get_dep_type);
+ int flags2 = (i!=deps2.end() ? i->get_flags()&System::ORDER_MASK : 0);
+ if(flags1&flags2)
+ throw scheduling_error(format("Conflicting ordering between %s and %s", node1.type->get_name(), node2.type->get_name()));
+ else if(flags1==System::RUN_BEFORE || flags2==System::RUN_AFTER)
+ return -1;
+ else if(flags1==System::RUN_AFTER || flags2==System::RUN_BEFORE)
+ return 1;
+ else
+ return 0;
+}
+
+int SystemScheduler::get_data_order(const GraphNode &node1, const GraphNode &node2)
+{
+ int data_order = 0;
+ const Reflection::ClassBase *ordered_data = nullptr;
+ const Reflection::ClassBase *unordered_data = nullptr;
+ for(const System::Dependency &d1: node1.system->get_dependencies())
+ {
+ int flags1 = d1.get_flags()&System::DATA_MASK;
+ if(!flags1)
+ continue;
+
+ for(const System::Dependency &d2: node2.system->get_dependencies())
+ {
+ int flags2 = d2.get_flags()&System::DATA_MASK;
+ if(!flags2)
+ continue;
+
+ const Reflection::ClassBase *common_type = nullptr;
+ if(&d1.get_type()==&d2.get_type() || d1.get_type().is_base_of(d2.get_type()))
+ common_type = &d1.get_type();
+ else if(d2.get_type().is_base_of(d1.get_type()))
+ common_type = &d2.get_type();
+ else
+ continue;
+
+ int order = 0;
+ // Read-only access to old data always comes first
+ if(flags1==System::READ_OLD)
+ order = -1;
+ else if(flags2==System::READ_OLD)
+ order = 1;
+ // Read-only access to fresh data always comes last
+ else if(flags1==System::READ_FRESH)
+ order = 1;
+ else if(flags2==System::READ_FRESH)
+ order = -1;
+ // Chained updates always come after non-chained writes
+ else if(flags1==System::CHAINED_UPDATE && (flags2==System::WRITE || flags2==System::UPDATE))
+ order = 1;
+ else if(flags2==System::CHAINED_UPDATE && (flags1==System::WRITE || flags1==System::UPDATE))
+ order = -1;
+ else
+ unordered_data = common_type;
+
+ if(order && data_order && order!=data_order)
+ throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s and %s",
+ node1.type->get_name(), node2.type->get_name(), ordered_data->get_name(), common_type->get_name()));
+
+ data_order = order;
+ ordered_data = common_type;
+ }
+ }
+
+ if(!data_order && unordered_data)
+ throw scheduling_error(format("Ambiguous data ordering between %s and %s, accessing %s",
+ node1.type->get_name(), node2.type->get_name(), unordered_data->get_name()));
+
+ return data_order;
+}
+
+} // namespace Msp::Game