Почему не все тестовые задания одинаково полезны: С++ edition

Вначале было слово, и было два байта, и ничего больше не было. Но отделил Бог ноль от единицы, и понял, что это хорошо.

Потом, опуская некоторые незначительные события мироздания, была вот эта статья от @novar.

Ну а еще некоторое время спустя вышел разбор задания из оригинальной статьи от @PsyHaSTe.

И обожемой, как этот разбор мне понравился. Серьезно, @PsyHaSTe, я теперь твой подписчик. Пиши еще, статья восхитительная, всем рекомендую.

Однако, покрутив немного сам код решения, я понял, что есть ряд моментов, которые я бы сделал иначе (так бывает, зачастую есть более одного способа решить задачу). В частности, меня зацепил вот этот кусок.

        public ScheduleInterval(int begin, int end)
        {
            Begin = begin;
            End = end;
            _allowedPoints = new bool[end - begin + 1];
        }

Получается, что при ограничении на миллисекунды [0,999], мы будем хранить килобайт памяти на каждый объект расписания, просто чтобы итерироваться по миллисекундам. Мой внутренний хомяк схватился за сердце. В упомянутых в статье библиотеках cron и Quartz проблема менее критична: в кроне точность расписания до минуты, а в кварце до секунды. Но у нас - тысячи миллисекунд.

Ладно, допустим использование памяти можно сократить, используя BitSet, но потом, в расписании типа 0:0:0.999 мы действительно 1000 раз пройдемся по элементам битсета, чтобы узнать, какая следующая миллисекунда валидная. Но ведь мы сразу знаем: нам подходит только 999.

Ну а после я глянул Closest<T>, где код везде разный, но уж очень напоминает копипасту, и рука сама потянулась глянуть, что получится у самого: критикуешь - предлагай.

Задача

Дан cron-подобый формат, включающий годы, месяца, дни, дни недели, часы, минуты, секунды, миллисекунды:

yyyy.MM.dd w HH:mm:ss.fff

Например, расписание "10 утра и 10 вечера с понедельника по пятницу" будет выглядеть так:

*.*.* 1-5 10,22:0:0.000

Требуется написать структуру данных, которая конструируется из расписания, и умеет быстро

• По заданному моменту времени находить ближайший следующий момент времени, подходящий под это расписание.

• По заданному моменту времени находить ближайший предыдущий момент времени, подходящий под это расписание.

Часть 0: Выбор языка

Поначалу хотелось сделать все на C#, чтобы честное сравнение получилось, но потом передумал: С++ я знаю лучше (хотя С++ и "знаю" - вообще такое себе сочетание), да и pet-проекты надо писать на том, что любишь, даже если любовь эта больше походит на стокгольмский синдром. Ну и, если совсем честно, на фоне монад от @PsyHaSTe мой С# будет выглядеть студенческой лабораторной.

Поэтому включаем VS, новый проект на крестах, пристегнулись и погнали.

Часть 1: Последовательности

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

Для начала сделаем обход "тривиальных условий": условий без списка ( 10-20/3 - тривиальное, 1,5,8 - нетривиальное). И будем рассматривать только обход вперед: обход назад добавим потом.

Таких условий не так и много: константа, любое значение(данного типа), диапазон, и последние два с заданным шагом.

Самое главное: хочется иметь некий "генератор следующих значений". Чтобы мы шли по "последовательности правильных", вместо того, чтобы проходить по всем и проверять, правильное ли текущее значение. Для тривиальных условий это понятно как сделать: если у нас ограничение 5, то мы генерируем следующее значение 5, а потом говорим, что новых значений нет. Если есть ограничение 1-5, то мы отдаем 1, потом 2, ... , потом 5, а потом говорим, что числа кончились.

Плюс, нам надо уметь "инициализировать" подобные "генераторы" числом (чтобы можно было начать с 3-й секунды, даже если диапазон 1-5), и сбросить на "начало" (если мы увеличиваем час, то генератор минуты должны сброситься на начало). В принципе, для всех тривиальных условий это задача концептуально решаемая. Осталось решить, как это будет выглядеть в коде.

Как известно, С++ программист за жизнь должен сделать 3 вещи:

• Построить велосипед

• Посадить зрение

• Написать итератор

Со временем пытаешься сделать все максимально похожим на итераторы, поэтому вот какой получился интерфейс для нашей "последовательности":

using Unit = int16_t;

class ISequence {
 public:
  // Setup condition with current value
  virtual void init(const Unit current) = 0;
  // Reset condition to the beginning
  virtual void reset() = 0;
  // returns false if there is no current value
  virtual operator bool() const = 0;
  // returns current value
  virtual Unit operator*() const = 0;
  // iterate to the next value
  virtual ISequence& operator++() = 0;
};

Изначально назывался ICondition, но не пережил рефакторинга.

Предполагается пользоваться такими последовательностями как-то так:

  AnyDay day;
  day.init(12);
  while (day) {
    std::cout << "AnyDay: " << *day << std::endl;
    ++day;
  }
  
  Range r(9, 17);
  r.init(12);
  while (r) {
    std::cout << "Range: " << *r << std::endl;
    ++r;
  }
  
  
  RangeStep rs(4, 10, 20);
  rs.init(12);
  while (rs) {
    std::cout << "RangeStep: " << *rs << std::endl;
    ++rs;
  }

В условии while (r) проверяем, есть ли валидное значение, если есть, то оператор "звездочка" *r вернет нам это значение, а оператор инкремента ++r попробует получить следующее значение.

Сделаем пару реализаций:

// header
template <Unit Begin, Unit End>
class Any : public ISequence {
  typedef Any<Begin, End> self_t;

 protected:
  Unit _current;

 public:
  Any();

  /*overrides*/
  void init(const Unit current) override final;
  void reset() override final;
  operator bool() const override final;
  Unit operator*() const override final;
  self_t& operator++() override;
};

using AnyYear = Any<2000, 2100>;
using AnyMonth = Any<1, 12>;
using AnyDay = Any<1, 31>;

// source
template <Unit Begin, Unit End>

// Any
template <Unit Begin, Unit End>
Any<Begin, End>::Any() : _current(Begin) {}

template <Unit Begin, Unit End>
void Any<Begin, End>::init(const Unit current) {
  _current = current;
}

template <Unit Begin, Unit End>
void Any<Begin, End>::reset() {
  _current = Begin;
}

template <Unit Begin, Unit End>
Any<Begin, End>::operator bool() const {
  return _current <= End;
}

template <Unit Begin, Unit End>
Unit Any<Begin, End>::operator*() const {
  return _current;
}

template <Unit Begin, Unit End>
typename Any<Begin, End>::self_t& Any<Begin, End>::operator++() {
  ++_current;
  return *this;
}


template class Any<2000, 2100>;
template class Any<1, 12>;
template class Any<1, 31>;

Все оказалось действительно довольно просто. Любое значение: мы просто сохраняем текущее значение и возвращаем его. При инициализации мы подразумеваем, что стартовое значение внутри диапазона, а валидация проводилась при парсинге (это допущение можно сделать в последовательности "любое значение", но нельзя в последовательности "диапазон": диапазон 10-20 можно инициализировать значением 5).
Мы перестаем выдавать новые значения, когда наше "текущее" значение вышло за границы дозволенного. Сбросить на начало - просто поставить стартовое значение.

Добавим тесты к нашей последовательности.

namespace UnitTests
{
typedef std::vector<scheduling::Unit> Units;

TEST_CLASS(TestConditions)
{
    static void FillResults(Units& units, scheduling::ISequence& condition) {
      units.clear();
      while (condition) {
        units.push_back(*condition);
        ++condition;
      }
    }
    public:
        
    TEST_METHOD(TestYears)
    {
        Units units;
        scheduling::AnyYear condition;

        condition.init(2020);
        FillResults(units, condition);

        Units expected;
        for (int i = 2020; i <= 2100; ++i) {
            expected.push_back(i);
        }

        Assert::IsTrue(units == expected);
    }
};
}  // namespace UnitTests

На самом деле, остальные тоже делаются легко, уточню два момента.

В последовательности "константа" мы храним флаг. Если мы инициализируем последовательность числом не большим нашей константы, флаг возводится (это означает, что существует "следующее значение последовательности", и мы его вернем).

Попытка получить следующий элемент последовательности всегда сбивает этот флаг.

// Const
Const::Const(const Unit val) : _val(val), _active(true) {}
void Const::init(const Unit current) { _active = current <= _val; }
void Const::reset() { _active = true; }
Const::operator bool() const { return _active; }
Unit Const::operator*() const { return _val; }
Const& Const::operator++() {
  _active = false;
  return *this;
}

Последовательности "с шагом" можно унаследовать от обычных последовательностей: при движении вперед там достаточно поменять инкремент и инициализацию, чтобы при инициализации мы сразу попадали в "валидное состояние".

// RangeStep
RangeStep::RangeStep(const Unit step, const Unit from, const Unit to)
    : Range(from, to), _step(step) {}

void RangeStep::init(const Unit current) {
  if (current <= _from) {
    _current = _from;
    return;
  }
  _current = current;
  auto diffmod = (_current - _from) % _step;
  if (diffmod != 0) {
    _current += _step - diffmod;
  }
}

RangeStep& RangeStep::operator++() {
  _current += _step;
  return *this;
}

// header
#pragma once
#include <cstdint>

namespace scheduling {

using Unit = int16_t;

class ISequence {
 public:
  // Setup condition with current value
  virtual void init(const Unit current) = 0;
  // Reset condition to the beginning
  virtual void reset() = 0;
  // returns false if there is no next value
  virtual operator bool() const = 0;
  // returns next available value
  virtual Unit operator*() const = 0;
  // iterates to the next iterator
  virtual ISequence& operator++() = 0;
};

template <Unit Begin, Unit End>
class Any : public ISequence {
  typedef Any<Begin, End> self_t;

 protected:
  Unit _current;

 public:
  Any();

  /*overrides*/
  void init(const Unit current) override;
  void reset() override final;
  operator bool() const override final;
  Unit operator*() const override final;
  self_t& operator++() override;
};

class Const final : public ISequence {
  const Unit _val;
  bool _active;

 public:
  explicit Const(const Unit val);

  /*overrides*/
  void init(const Unit current) override final;
  void reset() override final;
  operator bool() const override final;
  Unit operator*() const override final;
  Const& operator++() override final;
};

class Range : public ISequence {
  const Unit _to;

 protected:
  const Unit _from;

 protected:
  Unit _current;

 public:
  Range(const Unit from, const Unit to);

  /*overrides*/
  void init(const Unit current) override;
  void reset() override final;
  operator bool() const override final;
  Unit operator*() const override final;
  Range& operator++() override;
};

template <Unit Begin, Unit End>
class AnyStep final : public Any<Begin, End> {
  const Unit _step;

 public:
  explicit AnyStep(Unit step);

  /*overrides*/
  void init(const Unit current) override final;
  AnyStep& operator++() override final;
};

class RangeStep final : public Range {
  const Unit _step;

 public:
  explicit RangeStep(const Unit step, const Unit from, const Unit to);

  /*overrides*/
  void init(const Unit current) override final;
  RangeStep& operator++() override final;
};

using AnyYear = Any<2000, 2100>;
using AnyMonth = Any<1, 12>;
using AnyDay = Any<1, 31>;
using AnyHour = Any<0, 23>;
using AnyMinute = Any<0, 59>;
using AnySecond = Any<0, 59>;
using AnyMillisecond = Any<0, 999>;

using LastDay = Any<28, 31>;

using AnyStepYear = AnyStep<2000, 2100>;
using AnyStepMonth = AnyStep<1, 12>;
using AnyStepDay = AnyStep<1, 31>;
using AnyStepHour = AnyStep<0, 23>;
using AnyStepMinute = AnyStep<0, 59>;
using AnyStepSecond = AnyStep<0, 59>;
using AnyStepMillisecond = AnyStep<0, 999>;



}  // namespace scheduling

// source
#include "pch.h"
#include "framework.h"

#include <conditions.h>
#include <algorithm>

namespace scheduling {

// Any
template <Unit Begin, Unit End>
Any<Begin, End>::Any() : _current(Begin) {}

template <Unit Begin, Unit End>
void Any<Begin, End>::init(const Unit current) {
  // NB: exctra check. We could assume current >= Begin
  _current = std::max(current, Begin);
}

template <Unit Begin, Unit End>
void Any<Begin, End>::reset() {
  _current = Begin;
}

template <Unit Begin, Unit End>
Any<Begin, End>::operator bool() const {
  return _current <= End;
}

template <Unit Begin, Unit End>
Unit Any<Begin, End>::operator*() const {
  return _current;
}

template <Unit Begin, Unit End>
typename Any<Begin, End>::self_t& Any<Begin, End>::operator++() {
  ++_current;
  return *this;
}

// Const
Const::Const(const Unit val) : _val(val), _active(true) {}
void Const::init(const Unit current) { _active = current <= _val; }
void Const::reset() { _active = true; }
Const::operator bool() const { return _active; }
Unit Const::operator*() const { return _val; }
Const& Const::operator++() {
  _active = false;
  return *this;
}

// Range
Range::Range(const Unit from, const Unit to)
    : _to(to), _from(from), _current(from) {}
void Range::init(const Unit current) { _current = std::max(current, _from); }
void Range::reset() { _current = _from; }
Range::operator bool() const { return _current <= _to; }
Unit Range::operator*() const { return _current; }
Range& Range::operator++() {
  ++_current;
  return *this;
}

// Any step
template <Unit Begin, Unit End>
AnyStep<Begin, End>::AnyStep(Unit step) : _step(step) {}

// todo: copypast with Range
template <Unit Begin, Unit End>
void AnyStep<Begin, End>::init(const Unit current) {
  if (current <= Begin) {
    Any<Begin, End>::_current = Begin;
    return;
  }
  Any<Begin, End>::_current = current;

  auto diffmod = (current - Begin) % _step;
  if (diffmod != 0) {
    Any<Begin, End>::_current += _step - diffmod;
  }
}

template <Unit Begin, Unit End>
AnyStep<Begin, End>& AnyStep<Begin, End>::operator++() {
  Any<Begin, End>::_current += _step;
  return *this;
}


// RangeStep
RangeStep::RangeStep(const Unit step, const Unit from, const Unit to)
    : Range(from, to), _step(step) {}

void RangeStep::init(const Unit current) {
  if (current <= _from) {
    _current = _from;
    return;
  }
  _current = current;
  auto diffmod = (_current - _from) % _step;
  if (diffmod != 0) {
    _current += _step - diffmod;
  }
}

RangeStep& RangeStep::operator++() {
  _current += _step;
  return *this;
}

template class Any<2000, 2100>;
template class Any<1, 12>;
template class Any<1, 31>;
template class Any<0, 23>;
template class Any<0, 59>;
template class Any<0, 999>;

template class Any<28, 31>;

template class AnyStep<2000, 2100>;
template class AnyStep<1, 12>;
template class AnyStep<1, 31>;
template class AnyStep<0, 23>;
template class AnyStep<0, 59>;
template class AnyStep<0, 999>;
}  // namespace scheduling

Часть 2: Комбайнёр

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

С этим нам поможет структура данных "куча" (heap).

Куча - это структура данных, которая позволяет иметь быстрый O(1) доступ к минимальному/максимальному содержащемуся элементу, и позволяет относительно быстро добавлять и убирать из нее элементы. "Окучивание" - создание кучи - делается за O(n).

Полезная особенность реализации кучи в стандартной библиотеке С++: она работает в уже выделенном массиве, а значит не требует аллокаций/деаллокаций памяти.

Идея ее использования следующая: если у нас комбинация из нескольких разных последовательностей, давайте соберем их в кучу. "Текущее" значение мы всегда сможем получить за O(1) из вершины кучи: нам ведь нужно самое маленькое из валидных, правда?

Что нам делать при инкременте? Давайте вытащим последовательность из кучи. Вызовем у нее инкремент, и если в ней еще остались значения, засунем обратно в кучу. Не остались - не засунем.

Ну и понятно, что когда у нас куча опустеет, мы прошлись по всем значениям во всех наших последовательностях.

Есть один тонкий момент: наши "последовательности" могут пересекаться. Это вполне нормально, например, 10-20,*/3. Но мы не хотим из нашей "объединенной" последовательности возвращать одинаковые значения. Поэтому мы выкидываем из кучи не только "топовую" последовательность, но и все те, у которых такое же текущее значение.

Ну и просто для красоты: комбайнёр последовательности - это тоже последовательность. Если бы вначале я дал четкое определение последовательности, то сейчас бы магическим образом показал, что комбайнёр удовлетворяет всем требованиям последовательности, но математик во мне ленится в последнее время. Тем не менее, с точки зрения кода это значит, что мы можем унаследовать комбайнёра от того же интерфейса.

namespace scheduling {

class Combiner final : public ISequence {
  typedef std::unique_ptr<ISequence> condition_ptr;
  typedef std::vector<condition_ptr> Conditions;

  Conditions _conditions;
  Conditions::iterator _heapEnd;

  static bool heap_cmp(const condition_ptr& l, const condition_ptr& r);

  void makeHeap();

 public:
  Combiner();
  // todo: move to constructor??
  void emplace(condition_ptr&& ptr);

  // Inherited via ICondition
  virtual void init(const Unit current) override;
  virtual void reset() override;
  virtual operator bool() const override;
  virtual Unit operator*() const override;
  virtual Combiner& operator++() override;
};

}  // namespace scheduling

#include <algorithm>

namespace scheduling {

bool Combiner::heap_cmp(const condition_ptr& l, const condition_ptr& r) {
  return **l > **r;
}

void Combiner::makeHeap() {
  // filter conditions without value
  _heapEnd = std::partition(_conditions.begin(), _conditions.end(),
                            [](const auto& c) { return bool(*c); });

  // heap from what rest
  if (_conditions.begin() != _heapEnd) {
    std::make_heap(_conditions.begin(), _heapEnd, heap_cmp);
  }
}

Combiner::Combiner(): _heapEnd(_conditions.begin()) {}

void Combiner::emplace(condition_ptr&& ptr) { _conditions.emplace_back(std::move(ptr)); }

void Combiner::init(const Unit current) {
  for (auto& c : _conditions) {
    c->init(current);
  }
  makeHeap();
}

void Combiner::reset() {
  for (auto& c : _conditions) {
    c->reset();
  }
  makeHeap();
}

Combiner::operator bool() const { return _heapEnd != _conditions.begin(); }

Unit Combiner::operator*() const { return **_conditions.front(); }

Combiner& Combiner::operator++() {
  Unit val = **_conditions.front();
  while (_conditions.begin() != _heapEnd && val == **_conditions.front()) {
    std::pop_heap(_conditions.begin(), _heapEnd, heap_cmp);
    --_heapEnd;
    ++(**_heapEnd);
    if (**_heapEnd) {
      ++_heapEnd;
      std::push_heap(_conditions.begin(), _heapEnd, heap_cmp);
    }
  }
  return *this;
}

}  // namespace scheduling

отдельный комментарий вот этой строчке:

_heapEnd = std::partition(_conditions.begin(), _conditions.end(),
                            [](const auto& c) { return bool(*c); });

Она отфильтровывает последовательности в которых нет значений. В результате мы можем сделать сразу валидную кучу.

Как это работает, покажем при помощи косвенной документации (также известной как тесты):

  TEST_METHOD(TestConstCombiner) {
    Units units;

    // 3,6,15,2,7,28
    scheduling::Combiner combiner;
    combiner.emplace(std::make_unique<scheduling::Const>(3));
    combiner.emplace(std::make_unique<scheduling::Const>(6));
    combiner.emplace(std::make_unique<scheduling::Const>(15));
    combiner.emplace(std::make_unique<scheduling::Const>(2));
    combiner.emplace(std::make_unique<scheduling::Const>(7));
    combiner.emplace(std::make_unique<scheduling::Const>(28));

    combiner.init(6);
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{6, 7, 15, 28});

    combiner.reset();
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{2, 3, 6, 7, 15, 28});

    combiner.init(26);
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{28});

    combiner.init(30);
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{});

    combiner.reset();
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{2, 3, 6, 7, 15, 28});

  }  
  
  TEST_METHOD(TestComplexCombiner) {
    Units units;

    // */10, 11-14, 16-28/5, 23
    scheduling::Combiner combiner;
    combiner.emplace(std::make_unique<scheduling::AnyStepMinute>(10));
    combiner.emplace(std::make_unique<scheduling::Range>(11, 14));
    combiner.emplace(std::make_unique<scheduling::RangeStep>(5, 16, 28));
    combiner.emplace(std::make_unique<scheduling::Const>(23));

    combiner.init(5);
    FillResults(units, combiner);
    Assert::IsTrue(units ==
                   Units{10, 11, 12, 13, 14, 16, 20, 21, 23, 26, 30, 40, 50});

    combiner.reset();
    FillResults(units, combiner);
    Assert::IsTrue(units ==
                   Units{0, 10, 11, 12, 13, 14, 16, 20, 21, 23, 26, 30, 40, 50});

    combiner.init(13);
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{13, 14, 16, 20, 21, 23, 26, 30, 40, 50});

    combiner.init(16);
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{16, 20, 21, 23, 26, 30, 40, 50});

    combiner.init(17);
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{20, 21, 23, 26, 30, 40, 50});

    combiner.init(27);
    FillResults(units, combiner);
    Assert::IsTrue(units == Units{30, 40, 50});
  } 

Заметим: это универсальная последовательность, которую можно использовать и для месяцев, и для часов, и для секунд, и даже для дней недели.

Время собрать все воедино.

Часть 3: Глупенький итератор

Давайте на этом этапе предположим, что фильтра по дням недели нет, а в каждом месяце 31 день. (^◕.◕^)

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

Итак, глупенький итератор со своими странными представлениями об устройстве календаря.

#pragma once

#include <chrono>
#include <combiner.h>

namespace scheduling {

class Iter {
 public:
  typedef std::chrono::system_clock::time_point TimePoint;
  typedef std::chrono::system_clock::duration Duration;

  Combiner yearsSequence;
  Combiner monthsSequence;
  Combiner daysSequence;

  Combiner hoursSequence;
  Combiner minutesSequence;
  Combiner secondsSequence;
  Combiner millisecondsSequence;

  // init with current date
  void init(const TimePoint& current);
  // returns false if there is no next value
  operator bool() const;
  // returns next available value
  TimePoint operator*() const;
  // iterates to the next time point
  Iter& operator++();
};

}  // namespace scheduling

Как получить текущее значение понятно: просто берем значение из всех комбайнеров, склеиваем в тип даты. Проинициализировать - тут сложнее. Пока просто разберем на составляющие дату и проинициализируем каждый комбайнер отдельно (это баг, так делать нельзя, но мы поправим это в части 5).

Вопрос: как инкрементировать, и когда останавливаться?

А оказывается, тут все просто: мы инкрементируем миллисекунды. Удалось - следующее значение получено. Не удалось - сбрасываем последовательность на "стартовое значение" и пытаемся инкрементировать секунды. И так далее, до года: год сбрасывать нельзя - если мы вышли за границы года, то новых значений не будет. О! А вот и условие остановки.

Iter& Iter::operator++() {
  for (auto* s : std::vector<Combiner*>{
           &millisecondsSequence,
           &secondsSequence,
           &minutesSequence,
           &hoursSequence,
           &daysSequence,
           &monthsSequence,
    }) {
    ++(*s);
    // if sequence have next value -found
    if (*s) {
      return *this;
    }

    s->reset();
  }

  ++yearsSequence,
  return *this;
}

Iter::operator bool() const { return *yearsSequence; }

Мммм. Похоже что имея комбинированные последовательности глупенький итератор создается легко.

Часть 4: Итератор так-и-сяк (валидация дней месяца)

К этому моменту пришло осознание, что C++20 присутствует на VS только в оооооочень усеченном режиме, и функций работы с датой решительно не хватает.

Поэтому для хранения даты теперь объявлена своя структура, и появилась зависимость на boost (но только в одном файле (все так говорят, а потом....)).

Итак, нам надо как-то решить проблему с 31 февраля и иже с ними. Просто генераторами это решить сложно: появляется зависимость между генераторами дней, месяцев и лет, а это плохо.

Вместо этого разделим инкремент на две части: инкремент времени и инкремент даты.

Если удалось получить следующее время - все хорошо (мы уже в валидном дне), если нет: инкрементируем дату, а потом проверяем, валидна ли она. Если нет - инкрементируем дату снова (да, мы пытались этого избежать, но вы не понимаете, это другое).

Мы действительно генерируем "кандидатов" нашими последовательностями, а потом фильтруем их на пригодность. Получился некий гибрид подходов.

Iter& Iter::operator++() {
  // If found next time at the same date - done
  if (increment_time()) {
    return *this;
  }

  increment_date();

  // Increment date until the end of iterator or until first valid date is found
  while (bool(*this) && !is_valid_date()) {
    increment_date();
  }

  return *this;
}

bool Iter::increment_sector(const std::vector<Combiner*>& sector) {
  for (auto* s : sector) {
    ++(*s);
    // if sequence have next value: found next valid value
    if (*s) {
      return true;
    }
    s->reset();
  }

  // Next value was not found: reset all time sequence
  return false;
}

bool Iter::is_valid_date() {
  return boost::gregorian::gregorian_calendar::end_of_month_day(
             *yearsSequence, *monthsSequence) >= *daysSequence;
}

bool Iter::increment_time() {
  return increment_sector(std::vector<Combiner*>{
      &millisecondsSequence,
      &secondsSequence,
      &minutesSequence,
      &hoursSequence,
  });
}

bool Iter::increment_date() {
  return increment_sector(std::vector<Combiner*>{
      &daysSequence,
      &monthsSequence,
      &yearsSequence,
  });
}

Тут нам и пригодился буст: end_of_month_day.

Часть 5: Умненький итератор (инициализация)

Теперь давайте разберемся с самой сложной частью: инициализацией. Здесь я полностью согласен с @PsyHaSTe: иногда goto оправдан. Например, когда нам надо выйти из блока вложенных циклов. Правда у меня его использование выглядит немного не так как в предыдущей статье.

void Iter::init(const DateTime& current) {
  // NB: suppose to use std::chrono::year_month_day
  //     and std::chrono::hh_mm_ss
  // But VS does not support C++20 yet


  // reset all
  for (auto* s : std::vector<Combiner*>{
           &millisecondsSequence,
           &secondsSequence,
           &minutesSequence,
           &hoursSequence,
           &daysSequence,
           &monthsSequence,
           &yearsSequence,
       }) {
    s->reset();
  }

  // NB: init block 
  {
    yearsSequence.init(current.date.years);
    if (!yearsSequence) goto end_init_block;
    if (*yearsSequence != current.date.years) goto end_init_block;


    for (auto [seq, val] : std::vector<std::pair<Combiner*, Unit>>{
             {&monthsSequence, current.date.months},
             {&daysSequence, current.date.days}}) {
      seq->init(val);
      if (!*seq) goto end_init_block;
      if (**seq != val) goto end_init_block;
    }

    if (!is_valid_date()) goto end_init_block;

    for (auto [seq, val] : std::vector<std::pair<Combiner*, Unit>>{
             {&hoursSequence, current.time.hours},
             {&minutesSequence, current.time.minutes},
             {&secondsSequence, current.time.seconds},
             {&millisecondsSequence, current.time.milliseconds}}) {
      seq->init(val);
      if (!*seq) goto end_init_block;
      if (**seq != val) goto end_init_block;
    }
  }
  end_init_block:


  // Fix combiners without valid value (max one at a time)
  for (auto [seq, prev] : std::vector<std::pair<Combiner*, Combiner*>>{
           {&millisecondsSequence, &secondsSequence},
           {&secondsSequence, &minutesSequence},
           {&minutesSequence, &hoursSequence},
           {&hoursSequence, &daysSequence},
           {&daysSequence, &monthsSequence},
           {&monthsSequence, &yearsSequence},
       }) {
    if (!*seq) {
      seq->reset();
      ++(*prev);
    }
  }
  
  // Increment until valid date
  while (bool(*this) && !is_valid_date()) {
    increment_date();
  }

}

Разберем код по блокам.

Первый цикл сбрасывает все последовательности. Если, например, мы инициализировали часы числом 3, а у нас условие 5,6, то первое возможное значение часов будет 5. Значит минуты, секунды и др надо будет сбросить на "начальное" значение, потому что чем бы мы не пытались их инициализировать, мы уже на другом часу. Если же все последовательности предварительно сброшены - мы просто заканчиваем работу.

Второй блок пытается поочередно инициализировать все последовательности. Что может случиться на этом этапе?

1. Мы можем получить не то текущее значение, которым инициализировали. Тогда дальше ничего не надо инициализировать: см выше.

2. Мы можем попасть в не валидную дату.

3. Мы можем попасть вне блока (инициализировать "10-20" числом "30"). В этом случае надо будет увеличить предыдущую последовательность (условие ".10." при инициализации "2010.11.1" должно указывать на 2011 год)

Третий блок исправляет ошибку из условия 3.
Последний блок исправляет ошибку из условия 2.

Очень надеюсь, что понятно объяснил. Судя по тестам, оно даже работает.

  TEST_METHOD(TestInitIterator2) {
    // "2010.5.5 10:01:01.001"
    scheduling::Iter iter;
    iter.yearsSequence.emplace(std::make_unique<scheduling::Const>(2010));
    iter.monthsSequence.emplace(std::make_unique<scheduling::Const>(5));
    iter.daysSequence.emplace(std::make_unique<scheduling::Const>(5));

    iter.hoursSequence.emplace(std::make_unique<scheduling::Const>(10));
    iter.minutesSequence.emplace(std::make_unique<scheduling::Const>(1));
    iter.secondsSequence.emplace(std::make_unique<scheduling::Const>(1));
    iter.millisecondsSequence.emplace(std::make_unique<scheduling::Const>(1));

    iter.init(scheduling::DateTime{scheduling::Date{6, 6, 2011},
                                   scheduling::Time{11, 2, 2, 2}});

    Assert::IsFalse(iter);

    iter.init(scheduling::DateTime{scheduling::Date{6, 6, 2009},
                                   scheduling::Time{11, 2, 2, 2}});
    Assert::IsTrue(*iter ==
                   scheduling::DateTime{scheduling::Date{5, 5, 2010},
                                        scheduling::Time{1, 1, 1, 10}});
    ++iter;
    Assert::IsFalse(iter);
  }

Часть 5: Фильтр последнего дня месяца и дня недели

Эти два фильтра вписываются в текущий итератор элементарно: мы просто дописываем два условия в функцию is_valid_date Да, мы опять фильтруем, но вы опять не понимаете, это опять другое.

bool Iter::is_valid_date() {
  auto end_of_month_day =
      boost::gregorian::gregorian_calendar::end_of_month_day(*yearsSequence,
                                                             *monthsSequence);
  if (end_of_month_day < *daysSequence) {
    return false;
  }

  if (lastMonth && (end_of_month_day != *daysSequence)) {
    return false;
  }
  boost::gregorian::greg_year_month_day ymd(*yearsSequence, *monthsSequence,
                                            *daysSequence);
  if (filterWeek &&
      !valid_weekday(boost::gregorian::gregorian_calendar::day_of_week(ymd))) {
    return false; 
  }

  return true;
}

bool Iter::valid_weekday(Unit weekDay) {
  weekdaySequence.reset();
  do {
    if (*weekdaySequence == weekDay) {
      return true;
    }
    ++weekdaySequence;
  } while (weekdaySequence);
  return false;
}

TEST_METHOD(TestWeekdayFilterIterator) {
    // "*.*.* 0-2,4"
    scheduling::Iter iter;
    iter.yearsSequence.emplace(std::make_unique<scheduling::AnyYear>());
    iter.monthsSequence.emplace(std::make_unique<scheduling::AnyMonth>());
    iter.daysSequence.emplace(std::make_unique<scheduling::AnyDay>());

    iter.hoursSequence.emplace(std::make_unique<scheduling::Const>(0));
    iter.minutesSequence.emplace(std::make_unique<scheduling::Const>(0));
    iter.secondsSequence.emplace(std::make_unique<scheduling::Const>(0));
    iter.millisecondsSequence.emplace(std::make_unique<scheduling::Const>(0));

    iter.filterWeek = true;
    iter.weekdaySequence.emplace(std::make_unique<scheduling::Const>(4));
    iter.weekdaySequence.emplace(std::make_unique<scheduling::Range>(0,2));

    iter.init(scheduling::DateTime{scheduling::Date{13, 8, 2021},
                                   scheduling::Time{0, 0, 0, 0}});

    Assert::IsTrue(*iter ==
                   scheduling::DateTime{scheduling::Date{15, 8, 2021},
                                        scheduling::Time{0, 0, 0, 0}});
    ++iter;

    Assert::IsTrue(*iter == scheduling::DateTime{scheduling::Date{16, 8, 2021},
                                                 scheduling::Time{0, 0, 0, 0}});
    ++iter;

    Assert::IsTrue(*iter == scheduling::DateTime{scheduling::Date{17, 8, 2021},
                                                 scheduling::Time{0, 0, 0, 0}});
    ++iter;

    Assert::IsTrue(*iter == scheduling::DateTime{scheduling::Date{19, 8, 2021},
                                                 scheduling::Time{0, 0, 0, 0}});
    ++iter;

    Assert::IsTrue(*iter == scheduling::DateTime{scheduling::Date{22, 8, 2021},
                                                 scheduling::Time{0, 0, 0, 0}});
    ++iter;

}

Часть 6: Итерации в обратную сторону

Теперь, когда мы полноценно решаем задачу в одну сторону, хочется получить то же самое, но в обратную сторону.

Базовые последовательности лучше просто написать новые: попытка их обобщить приведет только к усложнению кода, а никак не наоборот. Кроме того, есть ряд важных отличий, для примера можно посмотреть различия между RangeStep и RRangeStep.

А вот комбайнёра можно и переиспользовать: ему все-равно, какие последовательности у него под капотом. Важно только правильно построить кучу: в обычном комбайнёре мы берем последовательность с самым, маленьким текущем значением, а в обратном надо брать с самым большим.

Сделаем это опять шаблонами и во время компиляции.

template<bool Reversed = false>
class CombinerBase final : public ISequence {
// ... 


using Combiner = CombinerBase<false>;
using RCombiner = CombinerBase<true>;

template <bool Reversed>
bool CombinerBase<Reversed>::heap_cmp(const condition_ptr& l,
                                      const condition_ptr& r) {
  if constexpr (Reversed) {
    return **l < **r;
  } else {
    return **l > **r;
  }
}

А теперь итератор. Ну, итератору тоже достаточно все-равно, ему надо только задать тип комбайнёра

template<bool Reversed>
class IterBase {

  typedef CombinerBase<Reversed> combiner_t;

  bool increment_sector(const std::vector<combiner_t*>& sector);

  bool increment_date();
  bool is_valid_date();
  bool increment_time();

  bool valid_weekday(Unit weekDay);

 public:
  combiner_t yearsSequence;
  combiner_t monthsSequence;
  combiner_t daysSequence;

  combiner_t hoursSequence;
  combiner_t minutesSequence;
  combiner_t secondsSequence;
  combiner_t millisecondsSequence;

  bool lastMonth = false;
  bool filterWeek = false;

  Combiner weekdaySequence;

  // init with current date
  // Sets the first valid date
  void init(const DateTime& current);
  // returns false if there is no next value
  operator bool() const;
  // returns next available value
  DateTime operator*() const;
  // iterates to the next time point
  IterBase<Reversed>& operator++();
};


using Iter = IterBase<false>;
using RIter = IterBase<true>;

И все, обратный итератор готов.

  TEST_METHOD(TestReverseIterator) {
    // *.4.6,7 * *:*:*.1,2,3-5,10-20/3
    scheduling::RIter iter;

    iter.yearsSequence.emplace(std::make_unique<scheduling::RAnyYear>());
    iter.monthsSequence.emplace(std::make_unique<scheduling::RConst>(4));
    iter.daysSequence.emplace(std::make_unique<scheduling::RConst>(6));
    iter.daysSequence.emplace(std::make_unique<scheduling::RConst>(7));

    iter.hoursSequence.emplace(std::make_unique<scheduling::RAnyHour>());
    iter.minutesSequence.emplace(std::make_unique<scheduling::RAnyMinute>());
    iter.secondsSequence.emplace(std::make_unique<scheduling::RAnySecond>());

    iter.millisecondsSequence.emplace(std::make_unique<scheduling::RConst>(1));
    iter.millisecondsSequence.emplace(std::make_unique<scheduling::RConst>(2));
    iter.millisecondsSequence.emplace(
        std::make_unique<scheduling::RRange>(3, 5));
    iter.millisecondsSequence.emplace(
        std::make_unique<scheduling::RRangeStep>(3, 10, 20));


    iter.init(scheduling::DateTime{scheduling::Date{7, 4, 2021},
                                   scheduling::Time{7, 0, 0, 0}});

    
    Assert::IsTrue(*iter == scheduling::DateTime{scheduling::Date{7, 4, 2021},
                                                 scheduling::Time{5, 0, 0, 0}});
    ++iter;

    Assert::IsTrue(*iter == scheduling::DateTime{scheduling::Date{7, 4, 2021},
                                                 scheduling::Time{4, 0, 0, 0}});
    ++iter; // 3
    ++iter; // 2
    ++iter; // 1
    Assert::IsTrue(*iter == scheduling::DateTime{scheduling::Date{7, 4, 2021},
                                                 scheduling::Time{1, 0, 0, 0}});
    ++iter; // 0 is not valid millisecond. Prev day

    Assert::IsTrue(*iter == scheduling::DateTime{scheduling::Date{6, 4, 2021},
                                                 scheduling::Time{19, 59, 59, 23}});
  }

Часть 7: Парсер

Ну, парсера не будет. На этом этапе я уже достаточно сильно подустал, да и не думаю, что смогу здесь сделать какую-то революцию.

Берите библиотеки на свой вкус (я бы, наверное, попробовал PEGTL) и преобразуйте строки в последовательности итератора.

Часть 8: Замеры времени

Несмотря на отсутствие парсинга, замерить время работы самого итератора можно. Например, я повторил тесты из статьи @PsyHaSTe:

Те результаты не привожу, если интересно - сами посмотрите.

Только отдельно хочу заметить, что время работы нельзя сравнивать (!!) тупо "в лоб". По крайней мере потому, что там дата парсится из строки, а здесь передается структурой.

Да и вообще, мы тут не таймингами мериться пришли, а подходами к решению задачи обмениваться.

Заключение

Ну, в первую очередь, спасибо @PsyHaSTe и @novar за то, что эта статья оказалось написана.

Надеюсь, кому-то было полезно, или по крайней мере интересно.

В статье хотел показать еще один из вариантов решения задачи, который не требует хранения "допустимых" секунд. Пусть в итоге не дописал парсер, но на мой взгляд, все-равно вышло довольно любопытно.

При этом времени я потратил более 12 часов, что несколько больше, чем предыдущие два автора. Зато побочным эффектом мы получили фичу, которая не подразумевалась в изначальном задании: после инициализации итератора, мы можем очень быстро и эффективно получить сразу N следующих последовательных дат.

Если будут какие-то конструктивные замечания/предложения - буду очень рад услышать.

Ссылка на гитовую репу тут.

Всем спасибо за внимание.