Идея для разрыва между графиками

Question

Я застрял в моем коде без каких-либо идей.

У меня есть:

QList<QPair<QTime,QTime>> data;

Где моя QPair представляет начальное время, конечное время, которое в основном является временным интервалом, в котором что-то запланировано.

У меня есть этот Qlist, чтобы узнать, какие у меня графики на определенный день.

Мне нужно знать, каковы свободные времена, и у меня заканчиваются идеи о том, как я могу это сделать. Я начинаю с создания Qlist, чтобы поместить все в одно и то же место с точки зрения расписаний, и заказал этот Qlist.

Answer 1

Прежде всего, QPair не очень описательный тип. Имеет смысл иметь собственную структуру:

// https://github.com/KubaO/stackrun/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);
   }
};

Поскольку все операции проще всего выполнять с отдельными событиями, а не с блоками, которые являются парами событий, давайте также представим одно событие. Событие указывает начало или конец отрезка времени, который может быть доступен или занят. Наличие или занятость рассматриваются отдельно. available член указывает, что блок доступности начинается (1) или заканчивается (-1). busy Член также указывает, что период занятости начинается (1) или заканчивается (-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;
   }
};

Затем вам нужно отсортировать блоки по времени их начала, объединить перекрывающиеся блоки, а затем объединить их в соответствии с желаемой операцией. Вы хотите вычесть время занятости из доступного времени, поэтому искомым выходным значением является "AvailableNotBusy": период времени должен быть как изначально доступным, так и не перекрываться с периодом занятости.

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 &);

Например, чтобы получить бесплатное расписание, вы хотите, чтобы все блоки времени были доступны, а также не были заняты:

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);
}

Преобразование между блоками и событиями довольно механическое:

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 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;
}

Теперь, чтобы объединить события, мы перебираем их в порядке времени, отслеживая, в какой момент мы находимся в течение доступного периода и / или в течение занятого периода. На это указывает ненулевое значение текущей суммы available а также busyсоответственно. Значения этих сумм указывают, сколько блоков данного типа перекрываются в любой момент времени. Например busy==3 означает, что мы находимся в пределах 3 перекрывающихся занятых блоков. Операция, которая определяет, какой вывод мы получаем, принимает текущее значение текущих сумм. Результат сбрасывается как объединенное событие каждый раз, когда результат операции изменяется при прохождении момента времени. Перекрывающиеся времена событий обрабатываются только путем поиска изменений в operationрезультат после оставления момента времени. recessiveKind события - это тип события по умолчанию, с которого мы начинаем. Первое изменение результата операции вне этого типа события вызовет появление первого события.

Примечание: в этом коде может быть ошибка:)

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;
}

Есть несколько общих операций, которые вы можете выполнить:

• MergeOp::Available: извлекать только события, связанные с доступностью, игнорируя занятость.

• MergeOp::Busy: извлекать только события, связанные с занятостью, игнорируя доступность.

• MergeOp::AvailableNotBusy: извлекать события, когда (available && !busy) изменения статуса.

• MergeOp::BusyNotAvailable: извлекать события, когда (busy && !available) изменения статуса.

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;
         });
   }
}