Вначале было слово, и было два байта, и ничего больше не было. Но отделил Бог ноль от единицы, и понял, что это хорошо.
Потом, опуская некоторые незначительные события мироздания, была вот эта статья от @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>, где код везде разный, но уж очень напоминает копипасту, и рука сама потянулась глянуть, что получится у самого: критикуешь - предлагай.
yyyy.MM.dd w HH:mm:ss.fff
Например, расписание "10 утра и 10 вечера с понедельника по пятницу" будет выглядеть так:
*.*.* 1-5 10,22:0:0.000
Требуется написать структуру данных, которая конструируется из расписания, и умеет быстро
Поэтому включаем VS, новый проект на крестах, пристегнулись и погнали.
Для начала сделаем обход "тривиальных условий": условий без списка ( 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>:
perator bool() const {
return _current <= End;
}
template <Unit Begin, Unit End>
Unit Any<Begin, End>:perator*() const {
return _current;
}
template <Unit Begin, Unit End>
typename Any<Begin, End>::self_t& Any<Begin, End>:perator++() {
++_current;
return *this;
}
template class Any<2000, 2100>;
template class Any<1, 12>;
template class Any<1, 31>;
Все оказалось действительно довольно просто. Любое значение: мы просто сохраняем текущее значение и возвращаем его. При инициализации мы подразумеваем, что стартовое значение внутри диапазона, а валидация проводилась при парсинге (это допущение можно сделать в последовательности "любое значение", но нельзя в последовательности "диапазон": диапазон 10-20 можно инициализировать значением 5).
Мы перестаем выдавать новые значения, когда наше "текущее" значение вышло за границы дозволенного. Сбросить на начало - просто поставить стартовое значение.
Небольшое отступление по синтаксису (если вы не С++ программист)
Параметры Begin и End - это параметры времени компиляции со всеми вытекающими: оптимизации где это возможно, для их хранения не используются переменные (не для каждого экземпляра: где-то в коде они есть), и т.д. Фактически, AnyYear, AnyMonth, AnyDay - это три разных класса, просто один шаблон.
При этом, этот шаблон не перекомпилируется: в заголовочном файле нет ни одной реализации(definition), только объявления (declaration), а в cpp файле последние строчки - это указание скомпилировать класс именно с этими константами. Такое возможно только потому, что мы заранее знаем все константы, с которыми будет использоваться этот класс.
Зато если мы где-то попробуем использовать, например Any<0, 17>, сборка упадет: он не найдет определение функций класса Any<0, 17>.
Добавим тесты к нашей последовательности.
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:perator bool() const { return _active; }
Unit Const:perator*() const { return _val; }
Const& Const:perator++() {
_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:perator++() {
_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>:perator bool() const {
return _current <= End;
}
template <Unit Begin, Unit End>
Unit Any<Begin, End>:perator*() const {
return _current;
}
template <Unit Begin, Unit End>
typename Any<Begin, End>::self_t& Any<Begin, End>:perator++() {
++_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:perator bool() const { return _active; }
Unit Const:perator*() const { return _val; }
Const& Const:perator++() {
_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:perator bool() const { return _current <= _to; }
Unit Range:perator*() const { return _current; }
Range& Range:perator++() {
++_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>:perator++() {
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:perator++() {
_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
С этим нам поможет структура данных "куча" (heap).
Куча - это структура данных, которая позволяет иметь быстрый O(1) доступ к минимальному/максимальному содержащемуся элементу, и позволяет относительно быстро добавлять и убирать из нее элементы. "Окучивание" - создание кучи - делается за O.
Полезная особенность реализации кучи в стандартной библиотеке С++: она работает в уже выделенном массиве, а значит не требует аллокаций/деаллокаций памяти.
Идея ее использования следующая: если у нас комбинация из нескольких разных последовательностей, давайте соберем их в кучу. "Текущее" значение мы всегда сможем получить за 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:artition(_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:perator bool() const { return _heapEnd != _conditions.begin(); }
Unit Combiner:perator*() const { return **_conditions.front(); }
Combiner& Combiner:perator++() {
Unit val = **_conditions.front();
while (_conditions.begin() != _heapEnd && val == **_conditions.front()) {
std:op_heap(_conditions.begin(), _heapEnd, heap_cmp);
--_heapEnd;
++(**_heapEnd);
if (**_heapEnd) {
++_heapEnd;
std:ush_heap(_conditions.begin(), _heapEnd, heap_cmp);
}
}
return *this;
}
} // namespace scheduling
отдельный комментарий вот этой строчке:
_heapEnd = std:artition(_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});
}
Заметим: это универсальная последовательность, которую можно использовать и для месяцев, и для часов, и для секунд, и даже для дней недели.
Время собрать все воедино.
Это не шутка, мы потом допилим напильником итератор до нужной кондиции: большие коммиты сложно пишутся, плохо читаются, плохо тестируются, и т.п. Надо пытаться декомпозировать задачу на маленькие и относительно понятные кусочки.
Итак, глупенький итератор со своими странными представлениями об устройстве календаря.
#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:perator++() {
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:perator bool() const { return *yearsSequence; }
Мммм. Похоже что имея комбинированные последовательности глупенький итератор создается легко.
Поэтому для хранения даты теперь объявлена своя структура, и появилась зависимость на boost (но только в одном файле (все так говорят, а потом....)).
Итак, нам надо как-то решить проблему с 31 февраля и иже с ними. Просто генераторами это решить сложно: появляется зависимость между генераторами дней, месяцев и лет, а это плохо.
Вместо этого разделим инкремент на две части: инкремент времени и инкремент даты.
Если удалось получить следующее время - все хорошо (мы уже в валидном дне), если нет: инкрементируем дату, а потом проверяем, валидна ли она. Если нет - инкрементируем дату снова (да, мы пытались этого избежать, но вы не понимаете, это другое).
Мы действительно генерируем "кандидатов" нашими последовательностями, а потом фильтруем их на пригодность. Получился некий гибрид подходов.
Iter& Iter:perator++() {
// 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.
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:air<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:air<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:air<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. Значит минуты, секунды и др надо будет сбросить на "начальное" значение, потому что чем бы мы не пытались их инициализировать, мы уже на другом часу. Если же все последовательности предварительно сброшены - мы просто заканчиваем работу.
Второй блок пытается поочередно инициализировать все последовательности. Что может случиться на этом этапе?
Последний блок исправляет ошибку из условия 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:ateTime{scheduling:ate{6, 6, 2011},
scheduling::Time{11, 2, 2, 2}});
Assert::IsFalse(iter);
iter.init(scheduling:ateTime{scheduling:ate{6, 6, 2009},
scheduling::Time{11, 2, 2, 2}});
Assert::IsTrue(*iter ==
scheduling:ateTime{scheduling:ate{5, 5, 2010},
scheduling::Time{1, 1, 1, 10}});
++iter;
Assert::IsFalse(iter);
}
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:ateTime{scheduling:ate{13, 8, 2021},
scheduling::Time{0, 0, 0, 0}});
Assert::IsTrue(*iter ==
scheduling:ateTime{scheduling:ate{15, 8, 2021},
scheduling::Time{0, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:ateTime{scheduling:ate{16, 8, 2021},
scheduling::Time{0, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:ateTime{scheduling:ate{17, 8, 2021},
scheduling::Time{0, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:ateTime{scheduling:ate{19, 8, 2021},
scheduling::Time{0, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:ateTime{scheduling:ate{22, 8, 2021},
scheduling::Time{0, 0, 0, 0}});
++iter;
}
Базовые последовательности лучше просто написать новые: попытка их обобщить приведет только к усложнению кода, а никак не наоборот. Кроме того, есть ряд важных отличий, для примера можно посмотреть различия между 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:ateTime{scheduling:ate{7, 4, 2021},
scheduling::Time{7, 0, 0, 0}});
Assert::IsTrue(*iter == scheduling:ateTime{scheduling:ate{7, 4, 2021},
scheduling::Time{5, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:ateTime{scheduling:ate{7, 4, 2021},
scheduling::Time{4, 0, 0, 0}});
++iter; // 3
++iter; // 2
++iter; // 1
Assert::IsTrue(*iter == scheduling:ateTime{scheduling:ate{7, 4, 2021},
scheduling::Time{1, 0, 0, 0}});
++iter; // 0 is not valid millisecond. Prev day
Assert::IsTrue(*iter == scheduling:ateTime{scheduling:ate{6, 4, 2021},
scheduling::Time{19, 59, 59, 23}});
}
Берите библиотеки на свой вкус (я бы, наверное, попробовал PEGTL) и преобразуйте строки в последовательности итератора.
Те результаты не привожу, если интересно - сами посмотрите.
Только отдельно хочу заметить, что время работы нельзя сравнивать (!!) тупо "в лоб". По крайней мере потому, что там дата парсится из строки, а здесь передается структурой.
Да и вообще, мы тут не таймингами мериться пришли, а подходами к решению задачи обмениваться.
Надеюсь, кому-то было полезно, или по крайней мере интересно.
В статье хотел показать еще один из вариантов решения задачи, который не требует хранения "допустимых" секунд. Пусть в итоге не дописал парсер, но на мой взгляд, все-равно вышло довольно любопытно.
При этом времени я потратил более 12 часов, что несколько больше, чем предыдущие два автора. Зато побочным эффектом мы получили фичу, которая не подразумевалась в изначальном задании: после инициализации итератора, мы можем очень быстро и эффективно получить сразу N следующих последовательных дат.
Если будут какие-то конструктивные замечания/предложения - буду очень рад услышать.
Ссылка на гитовую репу тут.
Всем спасибо за внимание.
habr.com
Потом, опуская некоторые незначительные события мироздания, была вот эта статья от @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>:
perator bool() const {return _current <= End;
}
template <Unit Begin, Unit End>
Unit Any<Begin, End>:
perator*() const {return _current;
}
template <Unit Begin, Unit End>
typename Any<Begin, End>::self_t& Any<Begin, End>:
perator++() {++_current;
return *this;
}
template class Any<2000, 2100>;
template class Any<1, 12>;
template class Any<1, 31>;
Все оказалось действительно довольно просто. Любое значение: мы просто сохраняем текущее значение и возвращаем его. При инициализации мы подразумеваем, что стартовое значение внутри диапазона, а валидация проводилась при парсинге (это допущение можно сделать в последовательности "любое значение", но нельзя в последовательности "диапазон": диапазон 10-20 можно инициализировать значением 5).
Мы перестаем выдавать новые значения, когда наше "текущее" значение вышло за границы дозволенного. Сбросить на начало - просто поставить стартовое значение.
Небольшое отступление по синтаксису (если вы не С++ программист)
Параметры Begin и End - это параметры времени компиляции со всеми вытекающими: оптимизации где это возможно, для их хранения не используются переменные (не для каждого экземпляра: где-то в коде они есть), и т.д. Фактически, AnyYear, AnyMonth, AnyDay - это три разных класса, просто один шаблон.
При этом, этот шаблон не перекомпилируется: в заголовочном файле нет ни одной реализации(definition), только объявления (declaration), а в cpp файле последние строчки - это указание скомпилировать класс именно с этими константами. Такое возможно только потому, что мы заранее знаем все константы, с которыми будет использоваться этот класс.
Зато если мы где-то попробуем использовать, например Any<0, 17>, сборка упадет: он не найдет определение функций класса Any<0, 17>.
Добавим тесты к нашей последовательности.
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:
perator bool() const { return _active; }Unit Const:
perator*() const { return _val; }Const& Const:
perator++() {_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:
perator++() {_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>:
perator bool() const {return _current <= End;
}
template <Unit Begin, Unit End>
Unit Any<Begin, End>:
perator*() const {return _current;
}
template <Unit Begin, Unit End>
typename Any<Begin, End>::self_t& Any<Begin, End>:
perator++() {++_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:
perator bool() const { return _active; }Unit Const:
perator*() const { return _val; }Const& Const:
perator++() {_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:
perator bool() const { return _current <= _to; }Unit Range:
perator*() const { return _current; }Range& Range:
perator++() {++_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>:
perator++() {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:
perator++() {_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
.Полезная особенность реализации кучи в стандартной библиотеке С++: она работает в уже выделенном массиве, а значит не требует аллокаций/деаллокаций памяти.
Идея ее использования следующая: если у нас комбинация из нескольких разных последовательностей, давайте соберем их в кучу. "Текущее" значение мы всегда сможем получить за 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:
artition(_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:
perator bool() const { return _heapEnd != _conditions.begin(); }Unit Combiner:
perator*() const { return **_conditions.front(); }Combiner& Combiner:
perator++() {Unit val = **_conditions.front();
while (_conditions.begin() != _heapEnd && val == **_conditions.front()) {
std:
op_heap(_conditions.begin(), _heapEnd, heap_cmp);--_heapEnd;
++(**_heapEnd);
if (**_heapEnd) {
++_heapEnd;
std:
ush_heap(_conditions.begin(), _heapEnd, heap_cmp);}
}
return *this;
}
} // namespace scheduling
отдельный комментарий вот этой строчке:
_heapEnd = std:
artition(_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:
perator++() {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:
perator bool() const { return *yearsSequence; }Мммм. Похоже что имея комбинированные последовательности глупенький итератор создается легко.
Часть 4: Итератор так-и-сяк (валидация дней месяца).
К этому моменту пришло осознание, что C++20 присутствует на VS только в оооооочень усеченном режиме, и функций работы с датой решительно не хватает.Поэтому для хранения даты теперь объявлена своя структура, и появилась зависимость на boost (но только в одном файле (все так говорят, а потом....)).
Итак, нам надо как-то решить проблему с 31 февраля и иже с ними. Просто генераторами это решить сложно: появляется зависимость между генераторами дней, месяцев и лет, а это плохо.
Вместо этого разделим инкремент на две части: инкремент времени и инкремент даты.
Если удалось получить следующее время - все хорошо (мы уже в валидном дне), если нет: инкрементируем дату, а потом проверяем, валидна ли она. Если нет - инкрементируем дату снова (да, мы пытались этого избежать, но вы не понимаете, это другое).
Мы действительно генерируем "кандидатов" нашими последовательностями, а потом фильтруем их на пригодность. Получился некий гибрид подходов.
Iter& Iter:
perator++() {// 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:
air<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:
air<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:
air<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. Значит минуты, секунды и др надо будет сбросить на "начальное" значение, потому что чем бы мы не пытались их инициализировать, мы уже на другом часу. Если же все последовательности предварительно сброшены - мы просто заканчиваем работу.
Второй блок пытается поочередно инициализировать все последовательности. Что может случиться на этом этапе?
- Мы можем получить не то текущее значение, которым инициализировали. Тогда дальше ничего не надо инициализировать: см выше.
- Мы можем попасть в не валидную дату.
- Мы можем попасть вне блока (инициализировать "10-20" числом "30"). В этом случае надо будет увеличить предыдущую последовательность (условие ".10." при инициализации "2010.11.1" должно указывать на 2011 год)
Последний блок исправляет ошибку из условия 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:
ateTime{scheduling:ate{6, 6, 2011},scheduling::Time{11, 2, 2, 2}});
Assert::IsFalse(iter);
iter.init(scheduling:
ateTime{scheduling:ate{6, 6, 2009},scheduling::Time{11, 2, 2, 2}});
Assert::IsTrue(*iter ==
scheduling:
ateTime{scheduling:ate{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:
ateTime{scheduling:ate{13, 8, 2021},scheduling::Time{0, 0, 0, 0}});
Assert::IsTrue(*iter ==
scheduling:
ateTime{scheduling:ate{15, 8, 2021},scheduling::Time{0, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:
ateTime{scheduling:ate{16, 8, 2021},scheduling::Time{0, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:
ateTime{scheduling:ate{17, 8, 2021},scheduling::Time{0, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:
ateTime{scheduling:ate{19, 8, 2021},scheduling::Time{0, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:
ateTime{scheduling:ate{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:
ateTime{scheduling:ate{7, 4, 2021},scheduling::Time{7, 0, 0, 0}});
Assert::IsTrue(*iter == scheduling:
ateTime{scheduling:ate{7, 4, 2021},scheduling::Time{5, 0, 0, 0}});
++iter;
Assert::IsTrue(*iter == scheduling:
ateTime{scheduling:ate{7, 4, 2021},scheduling::Time{4, 0, 0, 0}});
++iter; // 3
++iter; // 2
++iter; // 1
Assert::IsTrue(*iter == scheduling:
ateTime{scheduling:ate{7, 4, 2021},scheduling::Time{1, 0, 0, 0}});
++iter; // 0 is not valid millisecond. Prev day
Assert::IsTrue(*iter == scheduling:
ateTime{scheduling:ate{6, 4, 2021},scheduling::Time{19, 59, 59, 23}});
}
Часть 7: Парсер.
Ну, парсера не будет. На этом этапе я уже достаточно сильно подустал, да и не думаю, что смогу здесь сделать какую-то революцию.Берите библиотеки на свой вкус (я бы, наверное, попробовал PEGTL) и преобразуйте строки в последовательности итератора.
Часть 8: Замеры времени.
Несмотря на отсутствие парсинга, замерить время работы самого итератора можно. Например, я повторил тесты из статьи @PsyHaSTe:| pattern | date | P90 | P95 | P98 |
| *.*.1 0:0:0 | 01-01-2001 | 700 ns; | 705 ns; | 770 ns; |
| *.*.1 0:0:0 | 05-05-2080 | 539 ns; | 542 ns; | 662 ns; |
| *.4.6,7 * *:*:*.1,2,3-5,10-20/3 | 01-01-2001 | 540 ns; | 542 ns; | 582 ns; |
| *.4.6,7 * *:*:*.1,2,3-5,10-20/3 | 05-05-2080 | 581 ns; | 615 ns; | 794 ns; |
| 2100.12.31 23:59:59.999 | 01-01-2001 | 384 ns; | 612 ns; | 649 ns; |
| 2100.12.31 23:59:59.999 | 05-05-2080 | 352 ns; | 353 ns; | 431 ns; |
Только отдельно хочу заметить, что время работы нельзя сравнивать (!!) тупо "в лоб". По крайней мере потому, что там дата парсится из строки, а здесь передается структурой.
Да и вообще, мы тут не таймингами мериться пришли, а подходами к решению задачи обмениваться.
Заключение.
Ну, в первую очередь, спасибо @PsyHaSTe и @novar за то, что эта статья оказалось написана.Надеюсь, кому-то было полезно, или по крайней мере интересно.
В статье хотел показать еще один из вариантов решения задачи, который не требует хранения "допустимых" секунд. Пусть в итоге не дописал парсер, но на мой взгляд, все-равно вышло довольно любопытно.
При этом времени я потратил более 12 часов, что несколько больше, чем предыдущие два автора. Зато побочным эффектом мы получили фичу, которая не подразумевалась в изначальном задании: после инициализации итератора, мы можем очень быстро и эффективно получить сразу N следующих последовательных дат.
Если будут какие-то конструктивные замечания/предложения - буду очень рад услышать.
Ссылка на гитовую репу тут.
Всем спасибо за внимание.
Почему не все тестовые задания одинаково полезны: С++ edition
Вначале было слово, и было два байта, и ничего больше не было. Но отделил Бог ноль от единицы, и понял, что это хорошо. Потом, опуская некоторые незначительные события мироздания, была вот эта статья...
habr.com