Idea for gap between schedules

Question

I am stuck on my code without any ideas.

I have a :

QList<QPair<QTime,QTime>> data;

Where my QPair represents a Initial Time, End time that is basically a time frame where something is scheduled.

I have this Qlist in order to know what schedules I have for a specific day.

I need to know what are the free times and I am run out of ideas about how I can do that. I start with making a Qlist to put everything on the same place in terms of schedules and ordered that Qlist.

Answer 1

First of all, the QPair is not a very descriptive type. It makes sense to have your own structure:

// https://github.com/KubaO/stackoverflown/tree/master/questions/schedule-gap-54294739
#include <QtCore>
#include <type_traits>

struct Block {
   QTime start, end;
   enum class Kind { Null, Available, Busy } kind = Kind::Null;
   Block() = default;
   Block(const Block &) = default;
   Block(const QTime &start, const QTime &end, Block::Kind kind)
       : start(start), end(end), kind(kind) {
      Q_ASSERT(start <= end);
   }
};

Since all of the operations are simplest to perform on individual events, rather than blocks that are pairs of events, let’s also have a representation of a single event. The event indicates the beginning or an end of a chunk of time that may be available, or busy. The availability, or busyness, are considered separately. The available member indicates that a block of availability begins (1) or ends (-1). The busy member indicates similarly that a period of busyness begins (1) or ends (-1).

class Event {
  public:
   int available = 0, busy = 0;
   QTime time;
   enum class Kind { Null, BeginAvailable, EndAvailable, BeginBusy, EndBusy };
   Event() = default;
   Event(const QTime &time, Kind kind)
       : available(kind == Kind::BeginAvailable ? +1
                                                : kind == Kind::EndAvailable ? -1 : 0),
         busy(kind == Kind::BeginBusy ? +1 : kind == Kind::EndBusy ? -1 : 0),
         time(time) {}
   Block::Kind blockKind() const {
      return available ? Block::Kind::Available
                       : busy ? Block::Kind::Busy : Block::Kind::Null;
   }
};

Then you'll want to sort the blocks according to their start time, join the overlapping ones, then merge them according to the desired operation. You want to subtract busy times from available times, so the sought output is “AvailableNotBusy”: the period of time must be both originally available, and not overlapping with busy period.

using Blocks = QVector<Block>;
using Events = QVector<Event>;

Events eventsFromBlocks(const Blocks &);
Events sortedEvents(const Events &);
enum class MergeOp { Available, Busy, AvailableNotBusy, BusyNotAvailable };
Events mergeEvents(const Events &, MergeOp);
Blocks blocksFromEvents(const Events &);

Blocks mergeBlocks(const Blocks &a, const Blocks &b, MergeOp op) {
   auto events = eventsFromBlocks(a);
   events.append(eventsFromBlocks(b));
   events = sortedEvents(std::move(events));
   events = mergeEvents(std::move(events), op);
   return blocksFromEvents(std::move(events));
}

Schedule sortSchedule(const Schedule &);
Schedule joinOverlapping(const Schedule &);
Schedule subtract(const Schedule &, const Schedule &);

For example, to get free schedule you want all blocks of time that were available and also weren't busy:

Blocks freeSchedule(const Blocks &a, const Blocks &b) {
   return mergeBlocks(a, b, MergeOp::AvailableNotBusy);
}

Blocks freeWorkSchedule(const Blocks &busy) {
   return freeSchedule({{{8, 0}, {17, 0}, Block::Kind::Available}}, busy);
}

The conversion between blocks and events is rather mechanical:

Events eventsFromBlocks(const Blocks &schedule) {
   Events events;
   events.reserve(schedule.size() * 2);
   for (auto &block : schedule) {
      if (block.kind == Block::Kind::Available) {
         events.push_back({block.start, Event::Kind::BeginAvailable});
         events.push_back({block.end, Event::Kind::EndAvailable});
      } else if (block.kind == Block::Kind::Busy) {
         events.push_back({block.start, Event::Kind::BeginBusy});
         events.push_back({block.end, Event::Kind::EndBusy});
      }
   }
   return events;
}

Blocks blocksFromEvents(const Events &events) {
   Blocks blocks;
   blocks.reserve(events.size() / 2);
   bool start = true;
   for (auto &event : events) {
      if (start) {
         blocks.push_back({event.time, {}, event.blockKind()});
      } else {
         blocks.back().end = event.time;
         Q_ASSERT(blocks.back().kind == event.blockKind());
      }
      start = !start;
   }
   return blocks;
}

Events are sorted by time:

Events sortedEvents(const Events &events) {
   Events sorted = events;
   std::sort(sorted.begin(), sorted.end(),
             [](const Event &a, const Event &b) { return a.time < b.time; });
   return sorted;
}

Now, to merge the events, we iterate through them in the order of time, while keeping track of whether at any point we’re within an available period, and/or within a busy period. This is indicated by non-zero value of the running sum available and busy, respectively. The values of these sums indicate how many blocks of a given type are overlapping at any given time. E.g. busy==3 means that we’re within 3 overlapping busy blocks. The operation that determines what output we get takes the current value of the running sums. The outcome is dumped as a merged event any time the result of the operation changes upon passing a point in time. Overlapping event times are handled by only looking for changes in operation’s outcome after leaving a time point. The recessiveKind of an event is the default event type we start with. The first change of operation’s result away from that event type will cause the first event to be emitted.

Note: there may be a bug in this code :)

template <typename Op>
std::enable_if_t<std::is_invocable_r_v<Event::Kind, Op, int, int>, Events> mergeEvents(
    const Events &events, Event::Kind recessiveKind, Op operation) {
   Events merged;
   QTime prevTime;
   Event::Kind prevState = recessiveKind;
   int available = 0, busy = 0;
   for (auto ev = events.begin();; ev++) {
      if (ev != events.end()) {
         available += ev->available;
         busy += ev->busy;
      }
      Q_ASSERT(available >= 0);
      Q_ASSERT(busy >= 0);
      if (ev == events.end() || (ev != events.begin() && prevTime != ev->time)) {
         Event::Kind state = operation(available, busy);
         if (prevState != state) {
            merged.push_back({ev->time, state});
            prevState = state;
         }
         prevTime = time;
      }
   }
   return events;
}

There are a few common operations you may wish to perform:

• MergeOp::Available: extract only events related to availability, ignoring busyness.

• MergeOp::Busy: extract only events related to busyness, ignoring availability.

• MergeOp::AvailableNotBusy: extract events when the (available && !busy) status changes.

• MergeOp::BusyNotAvailable: extract events when the (busy && !available) status changes.

Events mergeEvents(const Events &events, MergeOp op) {
   switch (op) {
      case MergeOp::Available:
         return mergeEvents(events, Event::Kind::EndAvailable, [](int a, int) {
            return a ? Event::Kind::BeginAvailable : Event::Kind::EndAvailable;
         });
      case MergeOp::AvailableNotBusy:
         return mergeEvents(events, Event::Kind::EndAvailable, [](int a, int b) {
            return (a && !b) ? Event::Kind::BeginAvailable : Event::Kind::EndAvailable;
         });
      case MergeOp::Busy:
         return mergeEvents(events, Event::Kind::EndBusy, [](int, int b) {
            return b ? Event::Kind::BeginBusy : Event::Kind::EndBusy;
         });
      case MergeOp::BusyNotAvailable:
         return mergeEvents(events, Event::Kind::EndBusy, [](int a, int b) {
            return (b && !a) ? Event::Kind::BeginBusy : Event::Kind::EndBusy;
         });
   }
}