Adds basic scheduling support, although currently produces only debug output and has incomplete DB dependencies

4 files changed, 462 insertions, 0 deletions

diff --git a/p2pvr/daemon/daemon.cpp b/p2pvr/daemon/daemon.cpp
index 1bd328c..58ca66e 100644
--- a/p2pvr/daemon/daemon.cpp
+++ b/p2pvr/daemon/daemon.cpp
@@ -5,6 +5,7 @@
 #include "globalDevices.h"
 #include "maintenance.h"
 #include "si.h"
+#include "schedules.h"
 #include <logger.h>
 
 #include <linux/dvb/frontend.h>
@@ -30,6 +31,7 @@ class P2PvrDaemon : public Daemon {
 			adapter->add(new GlobalDevices(), ic->stringToIdentity("GlobalDevices"));
 			adapter->add(new Maintenance(), ic->stringToIdentity("Maintenance"));
 			adapter->add(new SI(), ic->stringToIdentity("SI"));
+			adapter->add(new Schedules(), ic->stringToIdentity("Schedules"));
 			adapter->activate();
 
 			auto maint = P2PVR::MaintenancePrx::checkedCast(adapter->createProxy(ic->stringToIdentity("Maintenance")));
diff --git a/p2pvr/lib/schedulers/bitDumbScheduler.cpp b/p2pvr/lib/schedulers/bitDumbScheduler.cpp
new file mode 100644
index 0000000..3c16601
--- /dev/null
+++ b/p2pvr/lib/schedulers/bitDumbScheduler.cpp
@@ -0,0 +1,54 @@
+#include "../schedules.h"
+
+class TheBitDumbScheduler : public EpisodeGroup {
+	public:
+		TheBitDumbScheduler(const Episodes & eps) :
+			episodes(eps)
+		{
+		}
+
+	protected:
+		void SelectShowings()
+		{
+			SelectShowings(episodes.begin(), 1);
+		}
+
+	private:
+		void SelectShowings(Episodes::const_iterator e, uint64_t complexityLevel)
+		{
+			if (e != episodes.end()) {
+				complexityLevel *= (*e)->showings.size();
+				if (complexityLevel > 2 << 16) {
+					auto current = showings.size();
+					for (EpisodesIter ne = e; ne != episodes.end(); ne++) {
+						BOOST_FOREACH(const auto & s, (*ne)->showings) {
+							showings.push_back(s);
+							if (SuggestWithFeedback(showings) & 0x1) {
+								break;
+							}
+							showings.pop_back();
+						}
+					}
+					showings.resize(current);
+				}
+				else {
+					EpisodesIter ne = e;
+					ne++;
+					BOOST_FOREACH(const auto & s, (*e)->showings) {
+						showings.push_back(s);
+						SelectShowings(ne, complexityLevel);
+						showings.pop_back();
+					}
+				}
+			}
+			else {
+				Suggest(showings);
+			}
+		}
+
+		mutable Showings showings; // working set
+		const Episodes episodes;
+};
+
+DECLARE_GENERIC_LOADER("BitDumb", EpisodeGroupLoader, TheBitDumbScheduler);
+
diff --git a/p2pvr/lib/schedules.cpp b/p2pvr/lib/schedules.cpp
new file mode 100644
index 0000000..387dba8
--- /dev/null
+++ b/p2pvr/lib/schedules.cpp
@@ -0,0 +1,324 @@
+#include "schedules.h"
+#include "sqlContainerCreator.h"
+#include <rdbmsDataSource.h>
+#include <logger.h>
+#include <Ice/Ice.h>
+#include <sqlVariableBinder.h>
+#include "p2Helpers.h"
+#include <boost/date_time/posix_time/posix_time.hpp> 
+
+// This gets the list of things we want to record (all showings)
+static const std::string GetScheduleConditates = "\
+select (e.title, e.subtitle, e.description)::text what, e.serviceid, e.eventid, sv.transportstreamid, \
+			 e.starttime - max(s.early), e.stoptime - interval '1 second' + max(s.late), \
+			 max(s.priority) \
+from services sv, events e, schedules s \
+where (s.serviceid is null or s.serviceid = e.serviceid) \
+and (s.title is null or lower(s.title) = lower(e.title)) \
+and (s.eventid is null or s.eventid = e.eventid) \
+and (s.search is null or event_tsvector(e) @@ plainto_tsquery(s.search)) \
+and sv.serviceid = e.serviceid \
+and e.starttime > now() \
+and not exists ( \
+	select 1 \
+	from seen \
+	where lower(e.title) = lower(seen.title) \
+	and coalesce(lower(e.subtitle), '') = coalesce(lower(seen.subtitle), '') \
+	and ts_rank(to_tsvector(e.description), plainto_tsquery(seen.description)) + \
+		ts_rank(to_tsvector(seen.description), plainto_tsquery(e.description)) > 1) \
+group by e.serviceid, e.eventid, sv.serviceid \
+order by max(s.priority) desc, e.title, e.subtitle, e.description, sv.transportstreamid, e.starttime \
+";
+
+std::string Schedules::SchedulerAlgorithm;
+
+DECLARE_OPTIONS(Schedules, "P2PVR Scheduler options")
+("p2pvr.scheduler.algorithm", Options::value(&SchedulerAlgorithm, "BitDumb"),
+ "Implementation of episode group scheduler problem solver")
+END_OPTIONS()
+
+typedef boost::tuple<std::string, int, int, int, datetime, datetime, int> ScheduleCandidate;
+typedef boost::shared_ptr<ScheduleCandidate> ScheduleCandidatePtr;
+typedef std::vector<ScheduleCandidatePtr> ScheduleCandidates;
+
+template<>
+void
+CreateColumns<ScheduleCandidatePtr>(const ColumnCreator & cc)
+{
+	cc("what", true);
+	cc("serviceid", false);
+	cc("eventid", false);
+	cc("transportstreamid", false);
+	cc("starttime", false);
+	cc("stoptime", false);
+	cc("priority", false);
+}
+
+template<>
+void
+UnbindColumns(RowState & rs, ScheduleCandidatePtr const & s)
+{
+	rs.fields[0] >> boost::get<0>(*s);
+	rs.fields[1] >> boost::get<1>(*s);
+	rs.fields[2] >> boost::get<2>(*s);
+	rs.fields[3] >> boost::get<3>(*s);
+	rs.fields[4] >> boost::get<4>(*s);
+	rs.fields[5] >> boost::get<5>(*s);
+	rs.fields[6] >> boost::get<6>(*s);
+}
+
+Showing::Showing(unsigned int s, unsigned int e, unsigned int t, datetime start, datetime stop, int p, const Episode * ep) :
+	episode(ep),
+	serviceId(s),
+	eventId(e),
+	priority(p),
+	transportStreamId(t),
+	startTime(start),
+	stopTime(stop),
+	period(start, stop)
+{
+}
+
+Episode::Episode(const std::string & w) :
+	priority(0),
+	what(w)
+{
+}
+
+EpisodeGroup::EpisodeGroup() :
+	tuners(1),
+	sumTimeToStart(0),
+	score(0)
+{
+}
+
+bool
+EpisodeGroup::IsShowingListValid(const Showings & showings) const
+{
+	struct TransOffset {
+		unsigned int trans;
+		char offset;
+	};
+	typedef std::multimap<datetime, TransOffset> Periods;
+	typedef std::map<int, unsigned char> Usage;
+
+	Periods periods;
+	Usage usage;
+
+	BOOST_FOREACH(const auto & s, showings) {
+		if (s) {
+			periods.insert(Periods::value_type(s->startTime, {s->transportStreamId, 1}));
+			periods.insert(Periods::value_type(s->stopTime, {s->transportStreamId, -1}));
+		}
+	}
+	bool result = true;
+	BOOST_FOREACH(const auto & p, periods) {
+		auto & u = usage[p.second.trans];
+		u += p.second.offset;
+		if (std::count_if(usage.begin(), usage.end(), [](const Usage::value_type & uv) { return uv.second > 0;}) > tuners) {
+			result = false;
+			break;
+		}
+	}
+	periods.clear();
+	usage.clear();
+	return result;
+}
+
+template<typename T>
+inline
+bool NotNull(const T & p)
+{
+	return p != NULL;
+}
+
+class SumTimeToStart {
+	public:
+		SumTimeToStart(time_t & t) :
+			total(t),
+			now(boost::posix_time::second_clock::universal_time())
+		{
+			total = 0;
+		}
+		inline void operator()(const ShowingPtr & s) const
+		{
+			if (s) {
+				total += (now - s->startTime).seconds();
+			}
+		}
+	public:
+		time_t & total;
+		datetime now;
+};
+
+const Showings &
+EpisodeGroup::Solve()
+{
+	SelectShowings();
+	return selected;
+}
+
+void
+EpisodeGroup::Suggest(const Showings & showings)
+{
+	unsigned int c = 0;
+	std::for_each(showings.begin(), showings.end(), [&c](const ShowingPtr & s) { if (s) c+= s->episode->priority; });
+	if (c >= score) {
+		time_t stt;
+		std::for_each(showings.begin(), showings.end(), SumTimeToStart(stt));
+		if (stt < sumTimeToStart) {
+			if (IsShowingListValid(showings)) {
+				selected = showings;
+				score = c;
+				sumTimeToStart = stt;
+			}
+		}
+	}
+}
+
+EpisodeGroup::SuggestionResult
+EpisodeGroup::SuggestWithFeedback(const Showings & showings)
+{
+	if (IsShowingListValid(showings)) {
+		unsigned int c = 0;
+		std::for_each(showings.begin(), showings.end(), [&c](const ShowingPtr & s) { if (s) c+= s->episode->priority; });
+		if (c >= score) {
+			time_t stt;
+			std::for_each(showings.begin(), showings.end(), SumTimeToStart(stt));
+			if (stt < sumTimeToStart) {
+				selected = showings;
+				score = c;
+				sumTimeToStart = stt;
+				return SuggestionValidAndAccepted;
+			}
+		}
+		return SuggestionValid;
+	}
+	else {
+		return SuggestionInvalid;
+	}
+}
+
+void
+Schedules::GetEpisodeIntersects(Episodes & all, Episodes & grouped)
+{
+	for (Episodes::iterator aei = all.begin(); aei != all.end(); aei++) {
+		const auto & ae = *aei;
+		BOOST_FOREACH(const auto & ge, grouped) {
+			BOOST_FOREACH(const auto & gs, ge->showings) {
+				BOOST_FOREACH(const auto & as, ae->showings) {
+					if (gs->period.intersects(as->period)) {
+						Logger()->messagebf(LOG_DEBUG, "	added %s", ae->what);
+						grouped.push_back(ae);
+						all.erase(aei);
+						GetEpisodeIntersects(all, grouped);
+						return;
+					}
+				}
+			}
+		}
+	}
+}
+
+void
+Schedules::DoReschedule(const Ice::Current & ice)
+{
+	auto ic = ice.adapter->getCommunicator();
+	auto devs = P2PVR::DevicesPrx::checkedCast(ice.adapter->createProxy(ic->stringToIdentity("GlobalDevices")));
+	unsigned int tunerCount = devs->TunerCount();
+
+	// Load list from database
+	ScheduleCandidates episodes;
+	SqlContainerCreator<ScheduleCandidates, ScheduleCandidate, ScheduleCandidatePtr> cct(episodes);
+	cct.populate(Select(GetScheduleConditates));
+
+	Episodes scheduleList;
+	Showings allShowings;
+	EpisodePtr cur;
+	int minPriority = 0;
+	BOOST_FOREACH(const auto & c, episodes) {
+		const auto & thisWhat = boost::get<0>(*c);
+		if (!cur || cur->what != thisWhat) {
+			cur = new Episode(thisWhat);
+			scheduleList.push_back(cur);
+		}
+		ShowingPtr s = new Showing(boost::get<1>(*c), boost::get<2>(*c), boost::get<3>(*c),
+				boost::get<4>(*c), boost::get<5>(*c), boost::get<6>(*c), cur.get());
+		minPriority = std::min(minPriority, s->priority);
+		cur->showings.push_back(s);
+		allShowings.push_back(s);
+	}
+	Logger()->messagebf(LOG_DEBUG, "%d episodes created", scheduleList.size());
+	BOOST_FOREACH(const auto & e, scheduleList) {
+		Logger()->messagebf(LOG_DEBUG, "	%s", e->what);
+		BOOST_FOREACH(const auto & s, e->showings) {
+			s->priority += 1 - minPriority;
+			e->priority += s->priority;
+		}
+		e->priority /= e->showings.size();
+	}
+
+	// Solve
+	while (!scheduleList.empty()) {
+		auto work = scheduleList.begin();
+		Logger()->messagebf(LOG_DEBUG, "start %s", (*work)->what);
+		Episodes group;
+		group.push_back(*work);
+		scheduleList.erase(work);
+		GetEpisodeIntersects(scheduleList, group);
+		std::sort(group.begin(), group.end(), [](const EpisodePtr & a, const EpisodePtr & b) {
+				if (a->priority > b->priority) return true;
+				if (a->priority < b->priority) return false;
+				return a->what < b->what;
+			});
+
+		Logger()->messagebf(LOG_DEBUG, "group created with %d episodes", group.size());
+		double total = 1;
+		// Measure and add the optional to not record
+		BOOST_FOREACH(const auto & e, group) {
+			Logger()->messagebf(LOG_DEBUG, "	%d * %d:%s", e->showings.size(), e->priority, e->what);
+			e->showings.push_back(NULL);
+			total *= e->showings.size();
+		}
+		Logger()->messagebf(LOG_DEBUG, "group complexity of %d options", total);
+
+		EpisodeGroupPtr sched = EpisodeGroupPtr(EpisodeGroupLoader::createNew(SchedulerAlgorithm, group));
+		sched->tuners = tunerCount;
+		std::set<ShowingPtr> selected;
+		BOOST_FOREACH(const auto & s, sched->Solve()) {
+			if (s) selected.insert(s);
+		}
+
+		BOOST_FOREACH(const auto & c, group) {
+			Logger()->messagebf(LOG_DEBUG, "Episode %s, %d options", c->what, c->showings.size());
+			BOOST_FOREACH(const auto & i, c->showings) {
+				if (selected.find(i) != selected.end()) {
+					Logger()->messagebf(LOG_DEBUG, "	%s - %s (%d) <-", i->startTime, i->stopTime, i->transportStreamId);
+				}
+				else if (i) {
+					Logger()->messagebf(LOG_DEBUG, "	%s - %s (%d)", i->startTime, i->stopTime, i->transportStreamId);
+				}
+			}
+		}
+		Logger()->message(LOG_DEBUG, "----------");
+	}
+}
+
+void
+Schedules::DeleteSchedule(int , const Ice::Current &)
+{
+}
+
+P2PVR::ScheduleList
+Schedules::GetSchedules(const Ice::Current &)
+{
+	P2PVR::ScheduleList rtn;
+	return rtn;
+}
+
+int
+Schedules::UpdateSchedule(const P2PVR::SchedulePtr &, const Ice::Current &)
+{
+	return 0;
+}
+
diff --git a/p2pvr/lib/schedules.h b/p2pvr/lib/schedules.h
new file mode 100644
index 0000000..caee1f7
--- /dev/null
+++ b/p2pvr/lib/schedules.h
@@ -0,0 +1,82 @@
+#ifndef SCHEDULER_H
+#define SCHEDULER_H
+
+#include <p2pvr.h>
+#include <options.h>
+#include "dbClient.h"
+#include <genLoader.h>
+
+typedef boost::posix_time::ptime datetime;
+class Episode;
+
+class Showing : public IntrusivePtrBase {
+	public:
+		Showing(unsigned int s, unsigned int e, unsigned int t, datetime start, datetime stop, int p, const Episode * ep);
+		// Record what?
+		const Episode * episode;
+		const unsigned int serviceId;
+		const unsigned int eventId;
+		int priority;
+		// Requires
+		const unsigned int transportStreamId;
+		const datetime startTime;
+		const datetime stopTime;
+		const boost::posix_time::time_period period;
+};
+typedef boost::intrusive_ptr<Showing> ShowingPtr;
+typedef std::vector<ShowingPtr> Showings;
+typedef Showings::const_iterator ShowingsIter;
+
+class Episode : public IntrusivePtrBase {
+	public:
+		Episode(const std::string & w);
+		int priority;
+		const std::string what;
+		Showings showings;
+};
+typedef boost::intrusive_ptr<Episode> EpisodePtr;
+typedef std::vector<EpisodePtr> Episodes;
+typedef Episodes::const_iterator EpisodesIter;
+
+class EpisodeGroup {
+	public:
+		EpisodeGroup();
+
+		const Showings & Solve();
+		unsigned int tuners;
+
+	protected:
+		enum SuggestionResult {
+			SuggestionInvalid = 0, SuggestionValid = 1, SuggestionValidAndAccepted = 3
+		};
+		SuggestionResult SuggestWithFeedback(const Showings &);
+		void Suggest(const Showings &);
+		virtual void SelectShowings() = 0;
+
+	private:
+		bool IsShowingListValid(const Showings & showings) const;
+		// chosen set
+		time_t sumTimeToStart;
+		unsigned int score;
+		Showings selected;
+};
+
+class Schedules : public P2PVR::Schedules, public DatabaseClient {
+	public:
+		void DeleteSchedule(int id, const Ice::Current &);
+		P2PVR::ScheduleList GetSchedules(const Ice::Current &);
+		int UpdateSchedule(const P2PVR::SchedulePtr &, const Ice::Current &);
+		void DoReschedule(const Ice::Current &);
+
+		INITOPTIONS;
+	protected:
+		static void GetEpisodeIntersects(Episodes &, Episodes &);
+	private:
+		static std::string SchedulerAlgorithm;
+};
+
+typedef GenLoader<EpisodeGroup, std::string, const Episodes &> EpisodeGroupLoader;
+typedef boost::shared_ptr<EpisodeGroup> EpisodeGroupPtr;
+
+#endif
+