Да, это еще одна статья, вызванная к жизни все тем же тестовым заданием, про решение которого я уже писал. И которое, вообще-то, объективно не заслуживает такого внимания, но так получилось, что меня оно зацепило. Еще когда я разбирался с крутым решением этого задания во второй посвященной ему статье, меня никак не оставляла в покое мысль — а как решить его, чтобы, с одной стороны, не "на отвали" (как в исходной статье), а с другой — без монад и goto, как в крутом решении во второй статье. И тогда я вспомнил про старое доброе объектно-ориентированное программирование (ООП), про те далекие времена, когда я писал сервисы для Windows на Delphi и подумал: а не написать ли мне решение именно в духе того старого доброго ООП. Я подумал — и я написал. И как ненастоящий программист, не обязанный писать код по долгу службы, но пишущий код исключительно ради своего удовольствия, я решил поделиться и кодом, и удовольствием (если получится) с читателями.
Я не обещаю в этом решении сократить объем кода, используя крутые сторонние библиотеки, или увеличить его производительность крутой оптимизацией под JIT. Я просто хочу продемонстрировать, как можно решить эту задачу, используя старую добрую объектно-ориентированную парадигму, без монад и без goto, руководствуясь здравым смыслом (ну, и небольшим объемом знаний). И как при этом можно написать код — легко* читаемый (* — если вы привыкли использовать ООП) и легко расширяемый, без сторонних библиотек, и оптимизировать его чисто на алгоритмическом уровне, без помощи тонких настроек JIT.
Итак, кому интересно решение этого неинтересного тестового задания в духе старого доброго ООП, и кто не забыл ещё (но уже осилил), что означает ключевое слово virtual — добро пожаловать под кат.
Сразу о старом добром
Немалому числу разработчиков нашего времени при виде аббревиатуры ООП сразу придут на ум SOLID, GoF и много других страшных слов. Так вот, это — не здесь. Здесь не будет ни слова ни про SOLID, ни про "паттерны" — здесь будет только про код. Потому что эти страшные слова тут не нужны: масштаб(небольшое тестовое задание) и время жизни (спихнуть тестовое задание) проекта никак не оправдывают погружения в эти безусловно полезные, но нужные только для куда более крупных и долгоживущих проектов концепции.
Нет, конечно, если поискать, то следы этих концепций тут есть. Например, сложно так широко использовать виртуальные методы, как в этом решении, напрочь игнорируя принцип имени некой Барбары, фамилия которой постоянно вылетает у меня из головы (но точно начинается с буквы L — т.к. это буква L из слова SOLID ) — его ещё называют "принцип подстановки"(но в этом названии нет буквы L) — то есть, нарушать совместимость виртуальных методов по видимой извне их семантике. Но, в целом, для решения задач такого масштаба вполне достаточно всего лишь здравого смысла — того самого, который является неотъемлемой частью старого доброго ООП.
О решении вообще
Сразу сообщу: репозиторий git с кодом решения выложен на github, в нем есть несколько веток с немного разными вариантами решений — о них, зачем они были созданы и чем они отличаются, будет написано далее. Основная ветка, как это положено для старого доброго решения, называется master (и никаких "main"!), и примеры кода по умолчанию надо смотреть в ней. А там, где нужно смотреть в другую ветку — об этом будет сказано явно.
Общая структура рассматриваемого решения по существу повторяет оба предыдущих. Сначала в конструкторе класса Schedule производится разбор строки расписания и преобразование (компиляция) его во внутренний формат, а потом методы поиска используют расписание в этом внутреннем формате для своей работы.
Выбор формата данных для представления результата разбора строки расписания также совершенно не оригинален. Сама структура строки расписания, в которой для каждого компонента даты/времени — от миллисекунды до года — задается свое собственное, независимое от других компонентов, ограничение, логично приводит к варианту, выбранному в обеих предыдущих статьях: для представления набора допустимых значений каждого компонента используется массив логических значений: по одному на каждое возможное значение компонента. То есть, результат разбора строки расписания записывается программой-разборщиком в набор массивов обычных логических (bool) значений — по одному массиву для каждого из компонентов даты/времени. А так как количество возможных значений для каждого компонента невелико — 1000 для миллисекунд, 200 — для лет и так далее по убывающей, а суммарно — всяко меньше 2000, то я решил, что нет никакого смысла заморачиваться минимизацией объема памяти для их хранения (например — в виде битовой карты): несколько сэкономленных килобайт того явно не стоят.
Ссылка на каждый такой массив логических значений хранится тоже в массиве — локальной переменной AllowedLists в конструкторе. Индекс для ссылки на массив с разрешенными значениями компонента даты/времени равен номеру компонента: от 0 для миллисекунд до 7 для дня недели. Ссылка на этот массив ссылок — AllowedLists — передается (как параметр с тем же именем) в методы разбора строки второго уровня (см. ниже), которые отвечают за отведение памяти под массивы разрешенных значений компонента.
...
bool[][] AllowedLists = new bool[PartConsts.NUM_PARTS][];
if (scheduleString != null)
MainParser(scheduleString, AllowedLists);
...Поскольку, однако, решение в этой статье предлагается старое доброе объектно-ориентированное, то получившиеся после разбора строки расписания массивы допустимых значений не используются напрямую методами поиска. Вместо этого качестве своего рода внутреннего формата расписания методы поиска используют набор объектов-обработчиков — по одному для каждого компонента даты/времени. При создании объекта-обработчика используемый для этого делегат получает ссылку на массив допустимых значений для соответствующего компонента. Расписание, разрешающее все значения компонента ("*"), представляется пустой ссылкой (null) на массив допустимых значений этого компонента. Это позволяет просто и естественно пропускать в процессе разбора любую обработку для компонентов даты/времени, список допустимых значений для которых в строке расписания отсутствует. В соответствии с методологией ООП все объекты-обработчики принадлежат к подклассам одного базового класса. Базовый класс предоставляет виртуальные методы (полный список этих методов — см. далее), используемые в реализации методов поиска класса Schedule. Реализация методов поиска в классе Schedule вызывает их по ссылке, имеющей тип базового класса. Это позволяет легко заменять реализацию объектов-обработчиков, используемых при поиске методов для каждого компонента даты/времени.
Создание этих объектов-обработчиков в данном решении производится делегатами, которые хранятся в массиве SchedulePartCreators, инициализуемом статически (т.е. его содержимое прописано в исходном тексте). Делегат для создания объекта-обработчика для компонента даты/времени хранится в элементе с индексом, равным номеру компонента. Создание компонентов-обработчиков производится в цикле по значению номера компонента. Тело цикла вызывает делегат из массива SchedulePartCreators, передает ему в качестве параметра ссылку на массив допустимых значений из массива AllowedLists и помещает созданный объект в массив объектов-обработчиков ScheduleParts в элемент с индексом, равным номеру компонента.
...
for (int i = 0; i < PartConsts.NUM_PARTS; i++)
ScheduleParts[i] = SchedulePartCreators[i](AllowedLists[i]);
...
static readonly AllowedDateTimePartCreator[] SchedulePartCreators = new AllowedDateTimePartCreator[PartConsts.NUM_PARTS] {
AllowedList=> AllowedDateTimePartMapped.CreateDateTimePart(PartConsts.FIRST_MSEC, PartConsts.LAST_MSEC, AllowedList, PartConsts.MSECS,new int[]{10,10}),
AllowedList=> AllowedDateTimePart.CreateDateTimePart(PartConsts.FIRST_SEC, PartConsts.LAST_SEC, AllowedList, PartConsts.SECS),
AllowedList=> AllowedDateTimePart.CreateDateTimePart(PartConsts.FIRST_MIN, PartConsts.LAST_MIN, AllowedList, PartConsts.MINUTES),
AllowedList=> AllowedDateTimePart.CreateDateTimePart(PartConsts.FIRST_HOUR, PartConsts.LAST_HOUR, AllowedList, PartConsts.HOURS),
AllowedDayPart.CreateDateTimePart,
AllowedList=> AllowedDateTimePart.CreateDateTimePart(PartConsts.FIRST_MONTH, PartConsts.LAST_MONTH, AllowedList, PartConsts.MONTHS),
AllowedList=> AllowedDateTimePart.CreateDateTimePart(PartConsts.FIRST_YEAR, PartConsts.LAST_YEAR, AllowedList, PartConsts.YEARS),
AllowedDowPart.CreateDateTimePart
};Первая часть — разбор строки расписания
Старый добрый объектно-ориентированный подход позволяет достаточно просто и быстро, не прибегая к сторонним средствам, сделать вполне компактное и расширяемое решение для разборщика строки расписания — куда более изящное, чем отписка сделанная автором первой статьи, и при этом — состоящее из набора слабо связанных довольно простых компонентов. Для этого нужно неформально использовать формальную грамматику строки расписания. Конечно, можно сделать и использовать формальное описание грамматики строки расписания формально — т.е. сделать разборщик автоматически, скормив какому-нибудь генератору разборщиков эту формальную грамматику, но, как автор второй статьи совершенно разумно пишет, это будет из пушки по воробьям (AKA overkill). Но старый добрый объектно-ориентированный подход позволяет и без всяких сторонних средств использовать формальную грамматику (или нечто, на нее похожее) как основу, на базе которых проектируются и реализуются классы, составляющие программу разбора. А так как формальное описание строки расписания раскладывает ее на отдельные независимые компоненты, тои функциональность каждого из компонентов кода — классов, разбирающих эти составные части, — оказывается слабо связанной с другими.
Короче, я написал эту программ разбора, пользуясь старым добрым ООП, и это было куда проще и быстрее, чем написать описание разборщика. Однако приступим к описанию. Программа разбора писалась методом сверху-вниз, в соответствии с описанием ее грамматики в том же порядке. вот в этом же порядке она и будет описана.
Верхний уровень — разбор полной строки расписания
Формат верхнего уровня строки расписания, который на языке, напоминающем язык BNF (далее в статье буду называть это "формальный язык"), выглядит примерно так:
строка_расписания ::= дата ' ' день_недели ' ' время | дата ' ' время | времяКак видим, строка расписания в любом из вариантов состоит из одной или нескольких подстрок разделенных пробелами. Нам нужно определить, с каким из вариантов мы имеем дело, а потом разобрать каждую из подстрок в соответствии с ее форматом. Так что сначала основной метода разбора (MainParser в классе Schedule) разбивает строку на подстроки по разделителям-пробелам. Затем этот метод определяет, с каким именно из вариантов он имеет дело. Для описания вариантов строки расписания заведен массив SecondLevelParsers, так что каждому допустимому варианту расписания соответствует элемент массива SecondLevelParsers. Каждый элемент описания варианта формата строки расписания — это массив ссылок на экземпляры классов-наследников абстрактного класса SecondLevelParser, расположенных в том порядке, в котором они встречаются в строке. Каждый из этих классов-наследников отвечает за работу со своей частью расписания (такой, как дата или время). Таким образом, добавление нового формата расписания потребует всего лишь добавления нового элемента в массив SecondLevelParsers.
static readonly SecondLevelParser[][] SecondLevelParsers = new SecondLevelParser[][] {
new SecondLevelParser[] {new DatePartParser(), new DayOfWeekPartParser(), new TimePartParser() }, //yyyy.MM.dd w HH:mm:ss.fff, yyyy.MM.dd w HH:mm:ss
new SecondLevelParser[] {new DatePartParser(), new TimePartParser() }, //yyyy.MM.dd HH:mm:ss.fff, yyyy.MM.dd HH:mm:ss
new SecondLevelParser[] {new TimePartParser() }, //HH:mm:ss.fff., HH:mm:ss
};
const int MAX_SCHEDULE_PARTS = 3;
static readonly StringPartArray _mainPartsSpace = new StringPartArray(MAX_SCHEDULE_PARTS);
static StringPartArray SplitInitialString (String scheduleString)
{
return scheduleString.Split(' ', _mainPartsSpace);
}
static internal void MainParser(String scheduleString, bool[][] AllowedLists)
{
lock(_mainPartsSpace)
{
StringPartArray scheduleParts = SplitInitialString(scheduleString);
bool parse_failed = scheduleParts==null;
if (!parse_failed) {
bool recognized = false;
SecondLevelParser[] parser_list = null;
foreach (SecondLevelParser[] second_level_parser_list in SecondLevelParsers) {
recognized = false;
if (second_level_parser_list.Length == scheduleParts.Length) {
for (int i = 0; i < scheduleParts.Length; i++)
recognized = recognized || second_level_parser_list[i].Recognize(scheduleParts[i]);
}
if (recognized) {
parser_list = second_level_parser_list;
break;
}
}
if (recognized) {
for (int i = 0; i < parser_list.Length; i++)
parse_failed = parse_failed || !parser_list[i].Parse(scheduleParts[i], ref AllowedLists);
}
else parse_failed = true;
}
if (parse_failed) throw new InvalidOperationException("Parsing the scheduling string'" + scheduleString + "' failed");
}
}
Абстрактный класс SecondLevelParser, в соответствии с задачей, имеет два абстрактных виртуальных метода. Первый метод, Recognize предназначен для распознавания "своей" части на этапе определения варианта: он принимает подстроку и сообщает (true/false) считает ли он(грубо прикидывая) эту подстроку соответствующей "своему" формату. Хотя в текущей задаче распознание подстрок не требуется (вариант можно распознать просто по числу подстрок), но я решил заложить сразу возможность расширения для разбора, например, строки вида "время ' ' дата ' ' день_недели", благо такое расширение стоит недорого — все реализации Recognize очень просты.
Второй метод класса SecondLevelParser, Parse производит собственно разбор подстроки части расписания: принимает подстроку и создает массивы допустимых значений тех компонентов, за которые он отвечает, устанавливает в этих массивах значения true/false в соответствии с расписанием и записывает ссылки на эти массивы в соответствующие позиции массива ссылок (который передается ему как второй параметр). Те позиции в массиве ссылок, куда нужно записывать ссылки на массивы допустимых значений, определяются номерами соответствующих компонентов даты/времени. В случае успеха метод Parse возвращает true, в случае неуспеха — false.
Классы-наследники абстрактного класса SecondLevelParser реализуют второй уровень разбора.
Второй уровень — разбор подстрок даты, времени и дня недели
У класса SecondLevelParser, есть три класса-наследника, каждый из которых реализует распознание и разбор одной из трех возможных в этом задании на втором уровне частей расписания: даты (класс DatePartParser), времени (класс TimePartParser) и дня недели (класс DowPartParser). Строки, которые они должны разбирать, состоят из частей, разделенных разделителями (день недели — из одной части без разделителей), и имеют на формальном языке следующий вид
дата ::= год '.' месяц '.' число_месяца
время ::= часы ':' минуты ':' (секунды | секунды '.' миллисекунды)
день_недели ::= список_значенийПри этом, все части строк даты и времени, на которые они разбиваются разделителями (':' или '.'), имеют следующий, совершенно одинаковый формат:
год ::= список_значений
месяц ::= список_значений
число_месяца ::= список_значений
часы ::= список_значений
минуты ::= список_значений
секунды ::= список_значений
миллисекунды ::= список_значенийПри реализации классов объектов-разборщиков даты и времени оказалось, что можно убрать часть дублирующегося в них кода в общий класс, потому что форматы строк даты и времени сходны: обе эти строки выглядят как подстроки, разделенные двумя одинаковыми (но разными для даты и для времени) разделителями, и обе строки после разбиения по разделителям состоят из одинаковых по формату первых двух подстрок — списков значений. А потому код распознания (метод Recognize), код выделения первых двух подстрок-списков значений и код разбора подстрок списков значений, на которые разбиваются строки обоих этих форматов является для этих двух классов-разборщиков одинаковым. Этот общий код вынесен в промежуточный класс-наследник SecondLevelParser — TwoDelimParser, от которого уже унаследованы классы разбора даты (DateParser) и времени (TimeParser). Класс TwoDelimParser реализует метод Recognize и общую часть разбора строки в методе Parse: разбиение строки на части по разделителю с выделением первых двух подстрок-списков значений (оно выделено в метод SplitForParts) и разбор подстрок-списков значений компонентов даты/времени. Т.к. для строки времени третья подстрока, получающаяся после разбиения по основному разделителю(':'), может состоять из двух подстрок-списков значений, то метод SplitForParts сделан виртуальным, чтобы класс TimeParser мог правильно обработать эту подстроку, перекрыв этот метод.
Я осознаю, что такого рода оптимизация, с вынесением повторяющегося кода в отдельную функцию или отдельный класс, может привести к неприятным последствиям при расширении функциональности — когда в результате последующего развития повторяющийся код перестанет быть повторяющимся, обрастет вариантами обработки и сделает функцию или метод класса нечитаемыми. Но тут, думаю, не тот случай, и вынесение общего кода в отдельный класс оправдано: вероятность опасного изменения формата даты и времени невелика. Все же, обычно время и дату записывают сходным образом, возможно — с другими разделителями или другим порядком компонентов (как в американском формате даты, разборщик которого, кстати, вполне можно тоже унаследовать от TwoDelimParser). Но все равно, компоненты там остаются теми же самыми. А для серьезных изменений формата с уменьшением числа компонентов — например, реализовать возможность оставить только два компонента (к примеру "день.месяц", подразумевая текущий год, или "часы: минуты", подразумевая что секунды с миллисекундами равны нулю) — можно и отдельный класс-разборщик завести: он в архитектуру такого решения вполне впишется.
Чтобы учесть специфику разбора для даты и для времени в конструктор класса TwoDelimParser из конструктора производного класса передаются следующие параметры:
- символ-разделитель
- объект "набор подстрок" класса StringPartArray, управляющий памятью для хранения частей-подстрок (об управлении памятью для подстрок в разборщике см. ниже).
- список экземпляров объектов-разборщиков (все они имеют один и тот же класс ListParser) для компонентов с дополнительными параметрами (в виде массива структур PartListParserSpecifier)
public abstract class TwoDelimParser: SecondLevelParser { readonly char _delim; readonly StringPartArray _spaceForParts; readonly PartListParserSpecifier[] _partParsers; protected TwoDelimParser(Char Delim, StringPartArray SpaceForParts, PartListParserSpecifier[] PartParsers) { _delim = Delim; _spaceForParts = SpaceForParts; _partParsers = PartParsers; } ... }
Метод Recognize опознает строку как имеющую нужный формат по наличию двух символов-разделителей (передаваемых через первый параметр конструктора).
Метод Parse сначала разбивает строку на подстроки, используя виртуальный метод SplitForParts. Подстроки помещаются в набор подстрок(переданный через второй параметр конструктора). Затем метод Parse производит разбор каждой из подстрок-списков значений. Т.к. формат всех подстрок-списков значений одинаков, то разбор этих подстрок выполняют объекты одного и того же класса ListParser (он будет рассмотрен ниже) путем вызова их методов Parse. Результат разбора каждой части в виде массива логических значений (или null, если разрешены все значения), возвращенный этим методом (через параметр-ссылку на нужный элемент массива ссылок) оказывается в соответствующем элементе массива ссылок, переданного через параметр AllowedLists. Какой именно экземпляр класса ListParser — эти экземпляры различаются границами допустимых значений, передаваемых в их конструкторы — будет использоваться для разбора и в какую позицию массива ссылок будет записан результат, указывается в структуре PartListParserSpecifier. Эта структура является элементом массива, передаваемого в конструктор TwoDelimParser в качестве третьего параметра. Индекс используемого элемента-структуры — это порядковый номер подстроки. Содержимое этого массива в решении задается статически, в исходном коде класса-наследника. Конструктор структуры PartListParserSpecifier принимает три параметра: верхнюю и нижнюю границы диапазона допустимых значений компонента даты/времени — они передаются в конструктор класса ListParser, экземпляр которого создается в конструкторе этой структуры — и номер компонента-индекс в массиве ссылок — он сохраняется в поле этой структуры.
public override bool Parse(StringPart Part, ref bool[][] AllowedLists)
{
StringPartArray parts = SplitForParts(Part, _delim, _spaceForParts);
bool result = true;
if (parts != null)
for (int i = 0; i < parts.Length && result; i++) {
result = result && _partParsers[i].Parser.Parse(parts[i], ref AllowedLists[_partParsers[i].Index]);
}
else result = false;
return result;
}
Базовая реализация метода SplitForParts разбивает строку на три части по символу-разделителю. Переопределенная реализация этого метода в классе TimePartParser сначала вызывает базовую реализацию. Затем она проверяет наличие в последней части символа разделителя миллисекунд (точки). Если символ найден, то эта часть усекается, оставляя только подстроку секунд, а подстрока миллисекунд добавляется как следующая часть. В противном случае в качестве следующей части добавляется '0', чтобы получить правильное, заданное условиями тестового задания, расписание для миллисекунд.
Кроме того, в текущей реализации класс DatePartParser перекрывает метод Parse с целью организации углубленной проверки результатов разбора даты на предмет наличия в нем хотя бы одной допустимой комбинации года, месяца и числа. Отсутствие такой комбинации считается ошибкой разбора. В оригинальной постановке тестовой задачи это не требуется, и метод Parse в DatePartParser можно было бы и не перекрывать. Но так как я не тест решал, я решил это сделать, чисто для себя.
Третий класс-разборщик второго уровня, DayOfWeekPartParser, разбирающий расписание для дней недели, устроен совсем просто: поскольку день недели — это просто список значений, то этот класс создает и сохраняет во внутреннем поле экземпляр класса-разборщика списка значений ListParser (о нем — ниже), настроенный через параметры его конструктора на нужный диапазон значений, и вызывает для выполнения распознания и разбора методы Recognize и Parse этого экземпляра соответственно.
Чисто ради занудства упомяну: границы списка допустимых значений для конструктора ListParser в DayOfWeekParser заданы соответствующими именованными константами. А в метод Parse класса ListParser передается ссылка на элемент для дня недели в массиве ссылок, с индексом, равным номеру компонента для дня недели (задается именованной константой).
Третий уровень — разбор списков допустимых значений компонентов даты и времени
В конце концов, все методы разбора второго уровня вызывают для дальнейшего разбора (а класс DayOfWeekPartParser — и для распознания) методы класса ListParser. Класс ListParser предназначен для разбора списка допустимых значений для компонента даты/времени, описываемого на формальном языке следующим образом:
список_значений ::= значение | значение ',' список значений
значение ::= диапазон_с_шагом | диапазон | любое_значение | число
диапазон_с_шагом ::= диапазон '/' шаг | любое_значение '/' шаг
диапазон ::= число '-' число
любое_значение ::= '*'
число ::= цифра | цифра число
цифра ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'Помимо формата, объект класса ListParser использует информацию о допустимом диапазоне (минимуме и максимуме) значений компонента, для проверки правильности расписания. Диапазон значений передается в качестве параметров конструктора объекта класса ListParser и запоминается во внутренних полях созданного экземпляра. При обнаружении в процессе разбора списка (в методе Parse) значений, выходящих за допустимый диапазон, фиксируется ошибка разбора (как именно это делается — см. ниже) и метод Parse возвращает false.
В соответствии с используемым объектно-ориентированным подходом каждому из возможных типов значения соответствует свой класс элемента списка, являющийся наследником абстрактного класса ListElementParser — разборщика элемента списка значений: класс StepWiseParser работает со значением типа "диапазон_с_шагом", RangeParser — "диапазон", AnyParser — "любое значение"(т.е. *), NumberParser — "число". Все эти классы переопределяют методы абстрактного класса ListElementParser: Recognize и Parse.
Ссылки на объекты (созданные статически) классов-разборщиков элементов списка, используемые в классе ListParser, зарегистрированы (т.е. хранятся в порядке, определяемом приоритетом их распознавания) в статическом массиве _listElementParsers. Т.е. фактически этот массив, вместе с методами Recognize класса ListElementParser напрямую реализует строку определения синтаксического элемента "значение" в приведенном выше формально определении. А потому добавление нового типа значения элемента списка, сводится к добавлению класса-наследника ListElementParser для обработки нового типа и добавлению ссылки на его экземпляр в указанный массив. Таким образом, старый добрый объектно-ориентированный подход обеспечивает легкую расширяемость синтаксиса расписания строки (в данном случае — в плане добавления новых типов элементов списка).
static readonly ListElementParser[] _listElementParsers=new ListElementParser[] //Parsers for the list elements, in the order ow lowering priority
{
StepwiseParser.STEPWISE_PARSER,
RangeParser.RANGE_PARSER,
AnyParser.ANY_PARSER,
NumberParser.NUMBER_PARSER
};Метод Recognize класса ListParser используется только разборщиком второго уровня DayOfWeekPartParser.
Он опознает подстроку как список, прежде всего, по наличию в подстроке символа "запятая" (возвращает true при наличии). Если же такого символа там нет — т.е. список состоит из одного элемента — то этот метод для опознания вызывает по очереди метод Recognize всех возможных типов элементов (экземпляров классов, зарегистрированных в массиве _listElementParsers), и в случае, если хотя бы один из них распознает подстроку, опознает эту подстроку как список и возвращает true. Иначе, если подстрока не опознана ни одним из классов элементов списка, возвращается false.
Метод Parse класса ListParser напрямую реализует первую строку написанного выше формального определения: он в цикле по очереди обрабатывает каждую из разделенных запятыми подстрок. Для каждой подстроки прежде всего он определяет ее тип значения. Для этого он вызывает по очереди методы Recognize всех зарегистрированных экземпляров классов-обработчиков элемента списка. Если метод Recognize экземпляра распознает значение подстроки как принадлежащее обрабатываемому им типу (возвращает true), то ListParser.Parse вызывает метод Parse для этого экземпляра, и, в случае успеха (возврата true) переходит к обработке следующей отделенной запятой подстроке, если такая есть. Если ни один из зарегистрированных классов не распознает подстроку, то разбор прекращается с ошибкой (возвращается false). Методы Parse классов-разборщиков элемента списка устанавливают разрешенные значения компонента даты и времени из обрабатываемого элемента — подстроки. Эти же методы отвечают и за поверку того, что разрешенные значения из обрабатываемой подстроки не выходят за пределы допустимого диапазона, если же такое происходит, то они сообщают об ошибке, возвращая false.
Для упрощения методы Recognize классов типов значений сделаны так, что они не производят полный разбор, а опознают тип по характерному элементу: наличию символа '/' для диапазона с шагом, '-' — для диапазона, '*' — для элемента типа "любое_значение", и только для числа производится проверка, что все символы в подстроке — цифры (мне показалось, что так его реализовать удобнее — иначе из-за способа хранения подстрок(это — не просто строки типа String, об этом — ниже) мне бы пришлось реализовывать для используемого при хранении класса метод IndexOfAny.
Так как число подстрок-элементов в списке может быть произвольным и довольно большим, то предварительное разбиение строки с помещением элементов в набор подстрок не используется. Вместо этого метод ListParser в цикле выбирает очередную подстроку и анализирует ее. Перед тем, как начать разбор списка значений элементов, метод Parse класса ListParser создает массив допустимых расписанием значений компонента даты/времени (все элементы его будут содержать false) и сохраняет ссылку на него в переданном ему по ссылке параметре — элементе массива ссылок. Эта ссылка на массив допустимых значений передается в методы Parse разборщиков элемента списка опять-таки по ссылке, так что их метод Parse может заменить ссылку на массив на значение null — оно, напоминаю, означает, что допустимы все значения компонента даты/времени. И метод AnyParser.Parse (обрабатывающий элемент '*') действительно так делает. При этом, если ссылка на массив сбрасывается разборщиком элемента в null, то метод ListParser.Parse проверяет, что этот элемент является единственным в списке (то есть, ни до него, ни после него никаких других элементов нет) и, если это не так, прекращает разбор по ошибке, возвращая false.
public bool Parse(in StringPart Part, ref bool[] AllowedList)
{
int list_delim_pos=-1;
StringPart work_part = AcquireWorkPart();
int array_length = _end - _start + 1;
AllowedList = new bool[array_length];
try {
do
{
if (null == AllowedList) return false; //Проверка на наличие '*' в начале подстроки, если был - это ошибка
int old_pos = list_delim_pos + 1;
list_delim_pos = Part.IndexOf(DELIM, old_pos);
StringPart element_part = Part.SubPart(old_pos, (list_delim_pos < 0 ? Part.Length : list_delim_pos), work_part);
ListElementParser element_parser = _listElementParsers.FirstOrDefault(curparser => curparser.Recognize(element_part));
if (element_parser == null) return false;
if (element_parser.Parse(element_part, ref AllowedList, _start, _end)) { //
if (AllowedList == null && old_pos > 0) return false; //Если это '*' и перед ней что-то есть - это ошибка
}
else return false;
} while (list_delim_pos >= 0);
} finally
{
ReleaseWorkPart(work_part);
}
bool result = AllowedList==null;
for (int i = 0; !result && i < array_length; i++)
result = result || AllowedList[i];
return result;
}Методы остальных классов-наследников ListElementParser, кроме AnyParser, устроены так, что они записывают true в те элементы массива допустимых значений, которые разрешены разбираемыми ими элементами списка. Таким образом, массиве допустимых значений накапливается объединение всех допустимых расписанием значений из списка.
Для проверки правильности значений элемента списка в метод и других надобностей, если они возникнут, в метод Parse классов-разборщиков элементов списка передается не только разбираемая подстрока, но и границы диапазона допустимых значений. Так сделано, чтобы для разбора любого компонента даты/времени (а они отличаются диапазоном допустимых значений) можно было использовать единственный статически созданный экземпляр класса-разборщика элемента (из массива _listElementParsers): как сказано выше, ответственность за проверку того, что границы допустимых значений компонента в разбираемом элементе списка не нарушаются, лежит на именно методе Parse класса-разборщика элемента списка.
Несколько слов о реализации классов элементов списка. Реализация методов Parse классов NumberParser и AnyParser тривиальна, а вот с методами Parse классов StepWiseParser и RangeParser дело обстоит немного сложнее, поэтому я здесь их опишу подробнее.
Класс StepWiseParser по факту имеет дело со строкой состоящей из диапазона (символ "*" он тоже считает диапазоном, с границами — минимальным и максимальным значениями, которые были переданы в его метод Parse) и шагом, разделенными символом "/". Поэтому его метод Parse разбивает переданную ему подстроку по разделителю "/" на две. Далее этот метод из первой подстроки получает границы диапазона (виртуальным методом ParseRange класса Parser), из второй подстроки — величину шага (методом NumberParser.ParseInt), и, в случае успеха разбора обеих этих подстрок, записывает фиксирует в результирующем массиве разрешенные значения (записывая true в соответствующие им элементы массива), начиная с начала диапазона и с указанным шагом. Чтобы указание символа * в качестве диапазона для элемента типа "диапазон_с_шагом" работало, класс AnyParser унаследован от класса RangeParser и реализует перекрытие его метода ParseRange(см. ниже), возвращая в качестве границ диапазона минимальное и максимальное допустимые значения.
Класс RangeParser определяет дополнительный метод ParseRange. Этот метод сделан виртуальным, чтобы его можно было перекрыть в классе AnyParser и единообразно использовать оба эти класса для разбора строки диапазона с шагом в классе StepWiseParser (см. выше). Этот метод разбивает переданную ему подстроку по символу-разделителю границ диапазона "-" на две и разбирает каждую из получившихся подстрок, если она не пустая, как число методом NumberParser.ParseInt. Пустые строки вместо границ диапазона считаются недопустимыми, в этом случае возвращается ошибка (false). В случае допустимых значений обеих границ метод RangeParser возвращает true в качестве результата и границы в качестве значений out-параметров. Метод RangeParser.Parse реализован через метод RangeParser.ParseRange — вызывает его, и в случае успеха, заполняет величиной true список допустимых расписанием значений в указанном диапазоне.
Управление памятью для хранения подстрок в процессе разбора
Для завершения описания того, как устроен разбор строки расписания, нужно упомянуть еще, как именно хранятся подстроки, выделяемые в процессе разбора. При написании кода разбора я решил провести небольшую и недорогую оптимизацию: отказаться от хранения подстрок, на которые разбивается строка расписания при разборе, в виде экземпляров класса string, чтобы не нагружать сборщик мусора: для string, как известно, требуется выделение памяти в куче каждый раз при их создании, и оставление этой памяти в качестве мусора после завершения надобности в подстроке приводит к необходимости в сборке мусора.
Вместо этого я использую для хранения подстроки структуру со ссылкой на исходную строку данных и границами подстроки. Так как для реализации задания сначала был выбран шаблон .NET Framework Class Library (как более старый и более добрый), то у меня не было возможности изначально использовать предназначенную для этого в современном C# структуру ReadOnlyMemory<Char>. Поэтому мне пришлось изобрести свой велосипед в виде класса StringPart. В репозитории он используется почти во всех вариантах решения — всех ветках, кроме netstd21, где я попытался максимально использовать новые возможности, появившиеся в .NET Core/Standard 2.1 (об этом ниже).
В полях класса StringPart хранятся ссылка на оригинальную строку (объект класса string) и границы подстрок, а методы этого класса реализуют, с некоторым изменением, те методы класса string, которые нужны в решении задания.
public class StringPart
{
internal string _baseString;
internal int _start, _end;
public StringPart(String BaseString) {...}
public int Length { get { return _end - _start; } }
public Char this[int Index] {get{...};set{...};}
public bool Truncate(int NewLength) {...}
public int IndexOf(char Value, int StartPos=0) {...}
public override string ToString() {...}
public StringPart SubPart(int RelativeStart, int RelativeEnd, StringPart WorkSpace) {...}
public StringPartArray Split(char Delimiter, StringPartArray ResultSpace){...}
}Другое важное принятое решение — как хранить память, занимаемою самими объектами класса StringPart. Выделять каждый раз под память из кучи под эту структуру не хотелось ровно по тем же соображениям, что и использовать string. Поэтому, и поскольку число подстрок, выделяемых при обработке, обычно заранее известно и весьма невелико, я решил выделить память под все обрабатываемые подстроки статически (в виде массивов) один раз в конструкторах классов и в дальнейшем использовать только эту, заранее выделенную память. Для управления этой памятью (например, для работы с массивом, заполненным не до конца) реализован класс StringPartArray. Память для экземпляров StringPartArray тоже выделяется статически, вместе с памятью для массивов StringPart. Поэтому в метод StringPart.Split, разделяющий строку на подстроки, передается ссылка на экземпляр класса StringPartArray, который предназначен для хранения этих подстрок.
Использование статического выделения памяти имеет, однако, тот недостаток, что требует ограничения параллелизма: параллельный процесс разбора нескольких строк расписания одновременно недопустим во избежание возникновения конфликтов обращения к статической памяти. Чтобы избежать конфликтов, основной метод разбора Schedule.MainParser использует критическую секцию (оператор lock), позволяющую вести только один одновременный разбор.
После переноса проекта в .NET Standard 2.1 я предпринял попытку переписать программу с целью задействовать вместо самопального класса StringPart стандартную структуру ReadOnlyMemory<Char>(или, возможно ReadOnlySpan) для хранения подстрок. Результат (ветка netstd21 репозитория) получился противоречивым. С одной стороны, от самопального класса StringPart мне избавиться удалось: подстроки теперь хранятся в виде экземпляров стандартной структуры ReadOnlyMemory<Char>. С другой стороны, не удалось (по крайней мере, без указателей и других небезопасных средств языка C# и .NET) избавиться от статического выделения памяти для разбора строки расписания, и, как следствие, необходимости использовать при разборе критическую секцию.
Массив структур ReadOnlyMemory<Char> разместить на стеке (с помощью stackalloc) не получается из-за ограничений .NET, т.к. ReadOnlyMemory<Char> — это управляемый тип. Использовать для хранения подстрок <Span<Span<Char>>, чтобы разместить его на стеке, тоже не получается: Span, как и любая другая ref struct, в которой он допустим в качестве типа поля, не может быть аргументом типа для Span, а использовать Span в качестве типа поля обычных классов и структур невозможно.
То есть качественное улучшение в плане ликвидации статического выделения памяти и обеспечения тем самым возможности параллельного выполнения разбора все равно достигнуто не было.
Что получилось в результате
Объем кода разборщика (исключая "церемониальные" (boilerplate) using, которые VS лепит при создании файла с классом автоматом и которые мне было лень убирать, а также — исключая совершенно необязательную проверку существования даты, попадающей под расписание) — это ~430 строк (вместе с пустыми строками, строками с единственной фигурной скобкой и т.п.). Конечно, это в два с лишним раза больше, чем в крутом решении из второй статьи, с монадами, но там использовалась (хоть и не оптимально, см. мою предыдущую статью) сторонняя библиотека. У автора изначальной статьи с его торопливо сделанным и лишенным гибкости решением получилось и без сторонней библиотеки тоже сильно меньше — ~230 строк (почти в 2 раза). То есть, получается, что гибкость — она на таких масштабах объема кода стоит заметно дороже. Но — не запредельно.
Однако, взамен было получено гибкое решение из слабо завязанных друг на друга компонентов, причем значительная часть связи между компонентами описывается декларативно — путем задания содержимого статических массивов. Такое решение куда проще модифицировать, ничуть не сложнее, чем решение на основе компонентов из сторонней библиотеки во второй статье — но без необходимости в сторонней библиотеке. Так что можно считать, что задача разбора строки расписания решается с использованием старого доброго ООП успешно и без особых потерь.
Вторая часть — методы поиска по расписанию
Перейдем теперь к решению второй части задания — реализации методов поиска по расписанию с помощью старого доброго ООП.
О компонентах даты и времени
После разбора строки расписания мы имеем своего рода внутренний формат расписания в виде набора объектов-обработчиков, хранящихся в массиве с индексами, равными номерам компонентов, за обработку которых они отвечают. Посмотрим теперь, что должны делать эти объекты. Самое первое, что они должны уметь делать — это проверить переданное им значение компонента на допустимость, то есть соответствие его расписанию. Но есть у них и другие функции, используемые при поиске ближайшего допустимого значения компонента. И если мы посмотрим на возможные варианты обработки компонентов даты/времени при поиске, то заметим, что способы этой обработки и требуемые для этого методы отличаются.
Во-первых, компоненты делятся на две большие группы. Большинство компонентов, составляющее первую группу, не зависят друг от друга в том смысле, что их значения задается напрямую, а не вычисляются на основе значений других компонентов. Эту группу далее я буду называть независимыми компонентами. Для таких компонентов переход к следующему/предыдущему ближайшему значению сводится (в первом приближении, ибо есть тонкости, рассмотренные далее) к поиску и установке следующего или предыдущего допустимого значения. То есть, для их объектов-обработчиков нужен метод перехода к этому ближайшему допустимому значению. Кроме того, для независимых компонентов нужно реализовать действия, которые производятся, если в нужном направлении нет больше допустимых значений — сообщить о необходимости изменить другие, "старшие" (о старшинстве — подробнее под спойлером) компоненты и одновременно установить правильное значение этого комонента — крайнее допустимое, наибольшее или наименьшее, в зависимости от направления поиска.
Компоненты даты/времени логически имеют определенное старшинство, от миллисекунд до лет: сначала меняется самый младший компонент, однако затем, если он выходит за допустимый предел, то изменение переносится в следующий по старшинству, а более младший устанавливается в значение предела с другой стороны (например было 999 миллисекунд — стало 0) — и так далее. Именно это старшинство устанавливает порядок номеров компонента — индексов, по которым в массивах хранятся все данные и все объекты, связанные с компонентами. И методы классов-обработчиков независимых компонентов обязаны должным образом отрабатывать такие переносы (подробности будут далее).
Но есть один компонент — день недели, который не относится к первой группе, независимым компонентам. Он является единственным представителем второй группы — зависимых компонентов. Значение компонентов этой группы не задаются напрямую, а косвенно зависят от других компонентов. В случае дня недели — от компонентов даты: число месяца, месяца и года. И ещё, для таких компонентов нет возможности установить допустимое значение напрямую (именно поэтому он называется зависимым): чтобы изменить значение конкретно дня недели, нужно менять другие компоненты даты, после чего — проверять, является ли получившееся после этого значение компонента (дня недели в нашем случае) разрешенным в расписании. Поэтому методы поиска ближайшего значения, определенные для независимых компонентов, для зависимых компонентов, в частности — компонента дня недели, не нужны.
По ряду причин, связанных с алгоритмом поиска допустимого значения даты, являющейся одновременно и допустимым значением дня недели, удобно выбрать номер компонента дня недели большим, чем все компоненты, от которых он зависит (т.е. число, месяц, год), но, в общем-то, выбор номера компонента для зависимого компонента произволен.
В общем-то, у зависимых и независимых компонентов есть только один общий метод, используемый для проверки значения на соответствие расписанию. Остальные требуемые для них методы разные.
Второе отличие между компонентами состоит в том, что есть, по крайней мере, один компонент — число месяца — который, хоть и является независимым с точки зрения установки его значения, но верхний предел значений для этого компонента — число дней в месяце — не фиксирован, а определяется значениями более старших компонентов — месяцем и, иногда, годом. Поэтому некоторые методы должны работать для него по-другому. Что ж, в старом добром объектно-ориентированном программировании для реализации такого поведения как раз есть нужное средство — виртуальные методы: то самое некогда забытое Королем Разработки ключевое слово virtual — здесь оно нам как раз пригодится.
И поскольку я изначально не гнался за жесткой оптимизацией с агрессивным встраиванием (inlining) методов, то мне ничто не помешает им воспользоваться: на первых порах несколько лишних обращений к памяти для косвенного вызова виртуального метода не является непомерной платой. Конечно, если жизнь вдруг заставит оптимизировать все до упора — то вместо старого доброго объектно-ориентированного придется и цикл (о нем чуть позже) развернуть, и методы конкретного класса на каждой позиции (бывшей итерации цикла) встроить, и приемы метапрограммирования из арсенала C++ использовать (благо C# теперь в это умеет, см. решение второго автора). Но все это, как я думаю, вряд ли нужно для выполнения исходного тестового задания: там, если я правильно понял задумку его авторов, главное — не нарваться на неоправданную алгоритмическую сложность, а серьезной оптимизации прямо в этом решении не требуется. Так что, думаю, можно остановиться на старом добром объектно-ориентированном решении.
Кстати, по жизни оно тоже примерно так же: например великий гуру программирования Дональд Кнут советует, с одной стороны, не заниматься преждевременной оптимизацией, а с другой — избегать заведомо неэффективных алгоритмов, и в этих советах велика истина есть. Но это я отвлекся.
О структуре алгоритма поиска
Самой некрасивой частью обоих решений мне показалась внутренняя часть цикла поиска следующего или предыдущего значения — цикла, который завершается по факту нахождения допустимого значения или исчерпания возможных значений. В первом решении там была ужасного вида совокупность многократно вложенных условных операторов. Впрочем, основной ужас ей IMHO придают огромные отступы, загоняющие код внутренних частей чуть ли не за правый край экрана, и многочисленные строки с единственной фигурной скобкой (в большинстве своем, кстати — совершенно излишние: и с точки зрения синтаксиса, потому что ограничиваемые ими блоки содержат всего один оператор, и для понимания уровня вложенности — для этого вполне было бы достаточно отступов, которые при этом, на мой взгляд следовало бы сделать поменьше). Эти строки и отступы съедают много пространства — сам-то код, если собрать его в одной обозримой области, достаточно прост и понятен (для меня, по крайней мере). Тем не менее, эта куча вложенных if вызвала негативную реакцию у достаточно большого числа комментаторов, поэтому, наверное, лучше так не делать.
Во втором решении эта внутренняя часть цикла, хотя и выглядит, на первый взгляд, привлекательнее, на самом деле, ещё более громоздкая, потому как содержит не один вложенный цикл — по миллисекундам, а несколько вложенных циклов — практически, по одному для каждого компонента даты/времени. Не говоря уж о том, что стремление избежать ещё более громоздких циклов побудило автора использовать пресловутый оператор goto, который древний мыслитель Дейкстра повелел считать вредным.
Короче, в результате чтения именно этого куска кода в обоих решениях у меня возникло желание переписать его так, чтобы не обрабатывать каждый независимый компонент по отдельности, а свернуть обработку всех компонентов в ещё один, внутренний, цикл. Однако проверку допустимости значения зависимого компонента — дня недели — все равно придётся делать после этого внутреннего цикла.
И именно это желание, собственно, и вызвало исходно к жизни идею сделать решение этого тестового задания в старом добром объектно-ориентированном стиле — то самое решение, про которое я здесь пишу: поскольку каждый компонент времени нужно обрабатывать в цикле, в целом, одинаково, но иногда немного по-разному, то в голову мне сразу пришло, что здесь как раз есть место инкапсуляции и полиморфизму — и все заверте...
Для внутреннего цикла, по компонентам даты/времени, хранение промежуточного результата поиска в формате DateTime не совсем подходит: компоненты в этом формате не изолированы. Изменение компонента может повлиять на значение более старшего, и это нужно как-то отдельно отслеживать, делая тем самым обработку каждого компонента неявно зависимой от другого компонента (что для цикла IMHO подходит плоховато). А любая прямая установка значения промежуточного результата (через конструктор DateTime, в коде решений из предыдущих статей это делается довольно часто) устанавливает значения младших компонентов жестко в их минимальное или максимальное (в зависимости от направления поиска) значение, делая невозможной кое-какую полезную алгоритмическую оптимизацию (о ней будет рассказано ниже).
Поэтому я принял решение хранить в процессе обработки значение каждого компонента отдельно, как элемент массива компонентов типа int (в коде он обычно называется ValueParts) с индексом, равным номеру компонента.
В объекты-обработчики передается ссылка на весь массив компонентов (Array или Span, в зависимости от реализации, см. далее), а каждый объект-обработчик знает индекс массива — номер компонента, с которым он работает (он задается в конструкторе), и проверяет/изменяет именно значение нужного элемента массива. Но при необходимости объект-обработчик может посмотреть и значение других компонентов (например, обработчик дня в месяце — значения месяца и/или года для определения числа дней в текущем месяце).
Объекты-обработчики компонентов даты/времени, как уже было написано выше, при рассмотрении программы разбора строки расписания, тоже хранятся в массиве (с именем ScheduleParts), так что объект-обработчик для текущего компонента всегда можно выбрать по его номеру — индексу массива. Все это дает возможность реализовать внутреннюю часть внешнего цикла как один или несколько внутренних циклов по компонентам. Как именно эта возможность была использована во внутренних методах — об этом ниже. Сейчас же перейдем к внешне видимой части — публичным методам поиска.
Реализация публичных методов поиска
Реализации публичных методов класса Schedule, указанных в задании, сделана через ряд вспомогательных методов. Прежде всего, это — метод SplitDateTimeToParts, заполняющий на основе входного параметра типа DateTime описанный выше массив значений компонентов даты/времени. Он вызывается в начале всех публичных методов: NearestEvent, NearestPrevEvent, NextEvent и PrevEvent. Массив компонентов времени, который нужно заполнить, передается в метод SplitDateTimeToParts по ссылке. Память под этот массив отводится в начале публичных методов и освобождается в их конце. Подробнее про отведение и освобождение памяти будет написано ниже.
Далее в методах NearestEvent/NearestPrevEvent (допускающих исходный момент времени) с помощью вспомогательного метода CheckCurrentEvent производится проверка, что исходный момент времени (указанный в переданном им параметре) является допустимым согласно расписанию. Если в указанных методах это не так, а в другой паре методов, NextEvent/PrevEvent, для которых исходный момент недопустим — в любом случае, вызывается вспомогательный метод StepToNearestEvent чтобы найти следующий или предыдущий допустимый момент времени. Этот метод возвращает в переданном ему по ссылке массиве с исходными значениями компонентов даты/времени ближайший к исходному момент времени, находящийся в нужном направлении, допустимый в расписании. Если такого момента времени нет, то метод возвращает false, что вызывает выброс исключения в публичных методах.
Вообще-то в задании не указано, что делать в этом случае, но т.к. публичные методы возвращают DateTime — а это структура и потому не может иметь значение null, — то выброс исключения является логичным решением. Впрочем, если требуется, чтобы такие случаи не снижали быстродействие, то можно не выбрасывать исключение, а вернуть default(DateTime): всё это — вопрос соглашений, которые в исходном задании не прописаны.
И, наконец, если нужный момент времени был найден, то все публичные методы создают из возвращенных значений компонентов объект DateTime, который возвращается в качестве результата (это делает метод JoinDateTimeFromParts).
Отдельный вопрос — выделение памяти под обрабатываемый массив значений компонентов даты/времени. Логичное место для размещения этого массива — стек: поскольку этот массив имеет фиксированный размер, то можно в начале каждого публичного метода отвести память под него в стеке, и она будет автоматически освобождена после завершения метода. Но в процессе работы выяснилось, что я изначально переборщил с старостью и добротой: я создал проект под .NET Framework, а в нем такая возможность не предусмотрена — он не поддерживает .NET Standard 2.1, а потому ни stackalloc, ни Span (в его полноценной реализации через управляемый указатель) не с нами. Поэтому я вынужден был завести пару методов, которые выделяют/освобождают память. Исходно (в основной ветке репозитория master) это делалось через обычное размещение в куче (т.е., здравствуй, GC), но централизация процесса управления памятью позволяет, в принципе, использовать и какую-либо ещё другую стратегию (singleton с блокировкой, пул и т.д.).
Чуть позже я для примера реализовал выделение памяти из неблокируемого пула — этот вариант я поместил в отдельную ветку master-memmgr. При использовании этого варианта выделение памяти из кучи для массива компонентов происходит только при необходимости (когда пул пуст), а использованная память возвращается в этот пул — таким образом, при вызове методов поиска класса Schedule в этом варианте практически не происходит вызывающего сборку мусора многократного выделения/освобождения памяти из кучи — исключая лишь редкие конфликты при увеличении размера пула.
И, наконец, когда я дописал код, я все же перенес исходный Framework-проект в .NET Standard 2.1 (который, как известно, совместим с .NET Core и 5+, но не с Framework) и заменил выделение памяти из кучи на выделение ее в стеке посредством stackalloc, а массив — на Span<int>. Этот вариант лежит в ветке netstd21-StringPart (или в netstd21, в части реализации методов поиска между ними разницы нет) в репозитории. В результате в этом варианте мы так же получаем, что выделения памяти из кучи при вызове методов поиска класса Schedule вообще не происходит.
Вспомогательный метод поиска следующего/предыдущего значения
После некоторого количества раздумий алгоритм поиска ближайшего допустимого значения, реализованный в методе StepToNearestEvent, получился довольно компактным и код его, смею надеяться, — читабельным.
Если заглянуть в код метода StepToNearestEvent в репозитории, то можно увидеть в нем необычно большое для нашего времени количество комментариев. Это от того, что над алгоритмом обработки в методе StepToNearestEvent я много думал, и нужный вариант родился не сразу. А я в таких нетривиальных случаях обычно сначала пишу алгоритм на псевдокоде в виде комментариев, анализирую в уме на предмет корректности, а потом уже расписываю его в коде.
Если коротко, общая идея алгоритма состоит в том, чтобы в цикле (внешнем) сначала находить (в первом внутреннем цикле) допустимую расписанием комбинацию независимых (изменяемых напрямую) компонентов времени (от миллисекунды до года), двигаясь по оси времени в нужном направлении (к следующим или предыдущим моментам), а потом проверять, соответствуют ли расписанию все компоненты, зависимые от этих независимых компонентов (в реальности такой компонент один — день недели), и если соответствия нет — повторить выполнение тела этого внешнего цикла.
Поиск допустимой комбинации производится в первом внутреннем цикле. Этот цикл имеет довольно сложную структуру: номер обрабатываемого компонента (это, фактически — переменная цикла) может как увеличиваться, так и уменьшаться в зависимости от результата текущей выполняемой операции. Этих операций возможны три: сравнение значения компонента с расписанием (возможное только в начале, до других операций), шаг — изменение значения компонента на следующее/предыдущее допустимое расписанием, и сброс — установка значения компонента в крайнюю (первую для поиска следующего значения или последнюю — для поиска предыдущего) допустимую расписанием величину. Все эти операции выполняются виртуальными методами объектов-обработчиков, назначенных для каждого компонента. Имена этих методов — ValueIsAllowed, StepValue и Wrap соответственно. После этих операций производится изменение номера следующего обрабатываемого компонента: он увеличивается или уменьшается на 1, в зависимости от результата этих операций. Условием окончания этого цикла является выход номера следующего обрабатываемого компонента за пределы допустимого диапазона: это означает либо что все независимые компоненты имеют допустимые расписанием значения (номер меньше 0), либо что допустимых расписанием комбинаций значений независимых компонентов больше нет (номер больше максимального). Полное описание алгоритма — в частности, когда какой метод в первом внутреннем цикле вызывается и в какую сторону в нем меняется номер обрабатываемого компонента на каждом проходе — получилось довольно объемным, поэтому я убрал его под спойлер.
Метод StepToNearestEvent, реализующий алгоритм поиска следующего или предыдущего допустимого значения момента времени в расписании, состоит из вложенных циклов двух уровней. В теле внешнего цикла сначала происходит поиск допустимой расписанием комбинации независимых компонентов даты/времени путем проверки и изменения только их в первом внутреннем цикле. После этого найденное значение проверяется на соответствие расписанию для всех зависимых компонентов (хотя у нас такой компонент только один — день недели, но алгоритм на это не закладывается, он написан для общего случая) во втором внутреннем цикле. Условием выхода из внешнего цикла является либо соответствие расписанию всех — и зависимых, и независимых — компонентов для найденного значения даты/времени, либо отсутствие допустимого момента времени в расписании в нужном направлении. Последнее выясняется в первом внутреннем цикле, при поиске следующей комбинации независимых компонентов в нужном направлении, соответствующей расписанию. Если этот поиск заканчивается неудачей, то второй внутренний цикл не выполняется, а происходит выход из внешнего цикла.
Как уже сказано, поиск допустимой расписанием комбинации независимых компонентов в методе StepToNearestEvent производится в первом внутреннем цикле. При работе этого цикла обрабатываются только независимые компоненты — те, для которых метод IsDependent их объекта-обработчика возвращает false. Зависимые компоненты при обработке пропускаются. Номер обрабатываемого компонента задается переменной part_number. Первый внутренний цикл при первом его запуске начинается со старшего компонента, с максимальным номером — для этого part_number устанавливается в это значение перед запуском внешнего цикла. Выполнение алгоритма начинается с того, что для всех независимых компонентов, кроме самого младшего (миллисекунды) проверяется, соответствует ли текущее значение компонента расписанию. Проверка выполняется вызовом виртуального метода ValueIsAllowed соответствующего объекта-обработчика. Выполнение этой, начальной проверки контролируется логической переменно still_valid, которая устанавливается в начальное значение true перед входом во внешний цикл и сбрасывается в false по окончанию этой проверки, когда она успешно закончена (проверены все компоненты, кроме миллисекунд) или когда текущий проверяемый компонент недопустим в расписании. Если же значение проверяемого компонента допустимо расписанием, то номер обрабатываемого компонента уменьшается на 1, и, если цикл проверки еще не добрался до миллисекунд, производится проверка следующего, более младшего независимого компонента (полностью про изменение номера обрабатываемого компонента см. ниже, при обсуждении изменяющего его кода). В конце концов, мы либо находим независимый компонент, значение которого расписанию не соответствует, либо добираемся до миллисекунд. И теперь нам нужно найти следующее/предыдущее значение обрабатываемого компонента, допустимое расписанием, на текущем уровне, при значении part_number, равном номеру текущего компонента Далее я буду называть эту процедуру "сделать шаг" или просто "шаг". Отметим, что перед этой процедурой мы всегда имеем состояние, в котором все независимые компоненты, которые старше обрабатываемого, уже имеют допустимое расписанием значение. Сам шаг выполняется виртуальным методом StepValue соответствующего объекта-обработчика. Этот метод возвращает true или false (возвращаемое значение сохраняется в логической переменной no_wrap) в зависимости от того, найдено ли такое значение в нужном направлении.
Если в результате шага в нужном направлении допустимое значение не найдено (далее такая ситуация называется "перехлест", ей соответствует равное false возвращаемое значение и значение переменной no_wrap, куда оно копируется), то это означает, что необходимо сделать шаг в нужном направлении для более старшего независимого компонента (если такой еще остался, конечно). С этой целью номер обрабатываемого компонента для выполнения следующей итерации цикла будет увеличен в конце этого внутреннего цикла на 1, и, если этот номер всё ещё остается допустимым индексом в массиве компонентов, то уже для этого номера компонента выполняется шаг — который тоже или вызывает, или не вызывает перехлест. Если и для старшего компонента происходит перехлест, то повторяется предыдущее действие — увеличение номера обрабатываемого компонента и выполнение шага. В конце концов эта последовательность действий приводит к тому, что либо номер обрабатываемого шага превышает число компонентов, либо эта последовательность оканчивается на том, что очередной шаг выполняется без перехлеста.
Первый случай означает, что в расписании в нужном направлении больше нет допустимых моментов времени. Так как условие продолжения внутреннего цикла состоит в том, что номер обрабатываемого компонента является допустимым индексом в массиве компонентов, то в этом случае происходит выход из внутреннего цикла со значением false логической переменной no_wrap. После этого происходит и выход из внешнего цикла в обход проверки зависимых компонентов, и метод StepToNearestEvent возвращает значение false (подробнее об этом ниже).
Во втором случае, когда последний шаг был успешен, то это означает, что новое значение для обрабатываемого компонента найдено. Метод StepValue объекта-обработчика сохраняет найденное значение в "своем" элементе массива значений компонентов. И теперь мы имеем ситуацию, что все значения независимых компонентов в массиве, начиная с текущего номера обрабатываемого компонента, имеют допустимые расписанием значения. Однако, поскольку значения компонентов в массиве, в отличие от варианта с хранением момента времени в DateTime, независимы, нужно ещё позаботиться и о правильных значениях более младших независимых компонентов. Для этого производится операция сброса их к нужному граничному (т.е. минимальному или максимальному допустимому, в зависимости от направления шага) значению компонента для всех младших независимых компонентов. Начинается она с уменьшения на 1 номера обрабатываемого компонента, чтобы выбрать самый старший из младших (независимых, зависимые компоненты просто пропускаются) компонентов.
Операция сброса компонента производится вызовом виртуального метода Wrap его объекта-обработчика. Возможны случаи, когда операция сброса компонента тоже может закончиться неудачей, т.к. в расписании для данного компонента просто нет значений, разрешенных при данной комбинации значений старших компонентов. Например, если в расписании для чисел месяца есть только одно разрешенное значение 31, а номер месяца был увеличен с 8(август) до 9(сентябрь), то сброс значения для числа месяца окончится неудачей: в сентябре, как известно, только 30 дней. Неудача сброса значения приводит ровно к тем же последствиям, что и перехлест при шаге — необходимости изменить значение старшего компонента, т.е., сделать для него шаг. Поэтому ее можно считать разновидностью перехлеста и обрабатывать аналогично: возвращаемое методом Wrap значение точно так же записывается в переменную no_wrap, и, если оно равно false, то точно так же, как описано выше, производится увеличение номера обрабатываемого компонента и шаг для него.
При успехе сброса метод Wrap сохраняет нужное граничное (максимальное или минимальное допустимое расписанием) значение в "своем" элементе массива значений компонентов. После этого номер обрабатываемого компонента ещё раз уменьшается на 1, и, если более младший компонент(независимый) с таким номером существует, то сброс производится уже для него. В конце концов, последовательность успешных сбросов приводит к тому, что значения всех независимых компонентов устанавливаются в нужное граничное значение, и происходит выход из внутреннего цикла, т.к. уменьшенный на 1 номер обрабатываемого компонента перестает быть допустимым значением индекса массива компонентов. При таком выходе из первого внутреннего цикла переменная no_wrap будет иметь значение true.
Остановимся теперь подробнее на коде, изменяющем номер обрабатываемого компонента (значение переменной part_number) перед проверкой условия выхода из внутреннего цикла. Если внимательно рассмотреть все изложенные выше условия изменения этого номера, то мы увидим, что направление его изменения и после операции шага (метод StepValue), и после операции сброса (метод Wrap) полностью определяется значением переменной no_wrap, в которую записывается возвращаемое этими методами значение. А после успешной операции начальной проверки на соответствие расписанию (метод ValueIsAllowed), которая выполняется только на первом проходе внешнего цикла, значенние no_wrap остается равным исходному — тоже true. То есть, при значении no_wrap, равном true, после любой операции номер обрабатываемого компонента должен быть уменьшен на 1, равном false — увеличен на 1. Именно так и реализовано изменение номера обрабатываемого компонента. А так как при обработке(т.е. пропуске) зависимого компонента значение no_wrap не меняется, то это обеспечивает сохранение направления и при пропуске зависимого компонента.
Правильное значение переменной no_wrap (true) для стадии начальной проверки, обеспечивающее уменьшение номера обрабатываемого компонента в процессе проверки, задается присвоением ей перед выполнением внутреннего цикла значения переменой still_valid: это значение равно true как раз только тогда, когда нужно выполнить стадию начальной проверки — в первом проходе внешнего цикла, после чего оно сбрасывается в false. Так что no_wrap получает значение true, нужное для правильной работы при начальной проверке, только на первом проходе внешнего цикла. На следующих проходах начальное значение no_wrap будет false (т.е. начальная проверка уже прошла), но это не повлияет ни на что: оно будет перезаписано еще до конца тела внутреннего цикла вызовом метода StepValue, который обязательно произойдет при таком значении.
Продолжим теперь рассмотрение других внутренностей внешнего цикла. После нахождения допустимой комбинации значений независимых компонентов даты/времени необходимо ещё и произвести проверку на соответствия расписанию зависимых компонентов. Такой компонент, по факту, только один — день недели, но алгоритм не завязан на то, что он — единственный, а производит проверку для всех имеющихся зависимых компонентов, сколько бы их ни было. Перед проверкой зависимых компонентов установленное в результате работы первого внутреннего цикла значение переменной no_wrap копируется в переменную step_made. Если это значение — true, то производится проверка на соответствие расписанию для всех зависимых компонентов вызовом метода ValueIsAllowed объекта-обработчика для зависимого компонента (второй внутренний цикл). Если проверка для какого-нибудь из них (т.е., реально — для дня недели) неудачна, то производится повторение внешнего цикла для перезапуска поиска следующей допустимой расписанием комбинации значений независимых компонентов. Для этого переменная step_made сбрасывается в false, чтобы условие повторения для внешнего цикла выполнилось.
Перезапуск первого внутреннего цикла производится с самого младшего компонента, от которого зависит не прошедший проверку зависимый компонент. Номер требуемого независимого компонента возвращается методом MinimalDependentPart объекта-обработчика не прошедшего проверку зависимого компонента и присваивается переменной part_number как начальное для повторения внутреннего цикла. После перезапуска тела внешнего цикла первый внутренний цикл начинает с выполнения шага для этого компонента, после чего работает обычным образом.
Условие продолжения внешнего цикла заключается в том, что комбинация значений всех независимых компонентов допустима расписанием (значение переменной no_wrap равно true), но проверка для независимых компонентов не пройдена (переменная step_made имеет значение false). В противном случае происходит выход из внешнего цикла и возврат значения переменной step_made: оно будет равно true, только если все компоненты соответствуют расписанию.
internal bool StepToNearestEvent(bool ToNext, int[] ValueParts)
{
bool step_made;
int part_number = PartConsts.NUM_PARTS - 1;
bool still_valid = true;
bool no_wrap; //Flag showing that no wrap on the current stage occured (but see also a comment at the start of the outer loop)
do {
no_wrap = still_valid;
do {
if (!ScheduleParts[part_number].IsDependent) {
if (still_valid || !no_wrap) {
if (still_valid)
still_valid = part_number>0 && ScheduleParts[part_number].ValueIsAllowed(ValueParts);
if (!still_valid)
no_wrap= ScheduleParts[part_number].StepValue(ToNext, ValueParts);
}
else
no_wrap = ScheduleParts[part_number].Wrap(ToNext, ValueParts);
}
if (no_wrap) part_number--; else part_number++;
} while (part_number >= 0 && part_number < PartConsts.NUM_PARTS);
step_made = no_wrap;
if (step_made)
for (part_number = 0; part_number < PartConsts.NUM_PARTS; part_number++) {
if(ScheduleParts[part_number].IsDependent) {
if (!ScheduleParts[part_number].ValueIsAllowed(ValueParts)) {
part_number = ScheduleParts[part_number].MinimalDependentPart;
step_made = false;
break;
}
}
}
} while (!step_made && no_wrap);
return step_made;
}Вот такой вот алгоритм. Достаточно компактно, но совсем не тривиально: если бы я вдруг делал это задание как тестовое, я бы вряд ли стал этот алгоритм использовать (разве что я бы нашел его где-нибудь в надежном источнике или твердо знал заранее). Для тестового задания (а также — в случае горящего срока на работе) я бы написал что-нибудь попроще — больно уж нетривиальным выглядит этот алгоритм на первый взгляд.
Объекты-обработчики компонентов даты и времени
Рассмотрим теперь сами объекты-обработчики компонентов даты/времени. Как написано выше, они делятся на обработчики для независимых компонентов и для зависимых.
Эти две группы обработчиков имеют несколько разные интерфейсы. Все обработчики должны иметь метод ValueIsAllowed, проверяющий, разрешено ли значение компонента расписанием. Кроме того, обработчики независимых компонентов должны иметь описанные выше методы изменения значения: StepValue (поиск и установки следующего/предыдущего допустимого расписанием значения) и Wrap (сброс значения компонента в граничное — максимальное или минимальное, допустимое расписанием). Для обработчика же зависимого компонента требуется метод MinimalDependentPart, чтобы узнать, с какого компонента перезапускать поиск допустимого зависимым компонентом значения.
Если бы проект был сложнее, то все эти методы стоило бы, конечно, разнести по разным интерфейсам. Но поскольку данный проект весьма простой — классов изначально намечалось всего три, потом я добавил в целях иллюстрации расширяемости решения четвертый — то я решил не устраивать из решения "энтерпрайз эдишн", а сделать минимальную иерархию классов, определив все нужные виртуальные методы в базовом классе. Для различения обработчиков на независимые и зависимые используется метод IsDependent.
Базовым классом иерархии является AllowedDateTimePart, в котором все виртуальные методы определены и реализованы для поиска допустимого значения независимого компонента в расписании с фиксированным диапазоном значений. Метод MinimalDependentPart, нужный только для обработчика зависимого компонента, в базовом классе тоже определен, но возвращает фиктивное значение. В базовом классе обработчика компонентов сразу предусмотрена определенная оптимизация (о которой я писал ранее): его конструктор сохраняет максимальное и минимальное допустимые расписаниями значения, так что шаг (метод StepValue) выполняется в соответствующую сторону только до этих значений, а при сбросе (метод Wrap) сразу подставляется соответствующее граничное значение, и итераций для поиска его по массиву логических значений не производится. В определенных сценариях (например, при использовании расписания с временем в формате без миллисекунд, где из тысячи разрешенных значений компонента миллисекунд разрешено всего одно) это может дать серьезный выигрыш. Возможность такой оптимизации — это преимущество обработки даты/времени не в формате DateTime, а в формате значений массива компонентов.
Базовый класс используется для обработки почти всех компонентов, кроме числа месяца (т.к. допустимый диапазон этого компонента зависит от других) и дня недели (т.к. это — зависимый компонент), а также — миллисекунд, для которого я в процессе реализации решения написал и использовал модифицированный обработчик (о нем см. ниже).
Производный от базового класс AllowedDayPart реализует поиск числа месяца, и его методы учитывают, что число дней в месяце меняется в зависимости от месяца (и, иногда, года). Этот класс также производит специальную обработку, если в расписании указан в качестве допустимого последний день месяца — число 32.
Другой производный от исходного базового класс, AllowedDowPart, предназначен для обработки единственного в этой задаче зависимого компонента — дня недели, а потому методы StepValue и Wrap он не реализует (выбрасывает исключение NotImplementedException при их вызове). Однако, как положено обработчику зависимого компонента, данный класс реализует метод MinimalDependentPart, в котором возвращает номер компонента для числа месяца. Другое отличие этого обработчика — число месяца он вычисляет самостоятельно. В текущей реализации он просто пользуется для этого классом DateTime, но так было не изначально (если вдруг кому интересно, как и почему — загляните под спойлер).
Но в более ранних реализацией этого метода был свой велосипед (в цепочке коммитов в репозитории его код сохранился, кому интересно — могут найти и посмотреть), написанный с целью ускорить специфический, но часто встречающийся в работе описанного выше алгоритма случай — постепенное изменение даты в небольших пределах: предполагалось, что компоненты даты от предыдущего вызова будут сохраняться в данном объекте в качестве его состояния. Но потом я подумал о параллелизме и от сохранения состояния отказался.
По скорости (конкретно для этого случая я простейшие замеры производительности таки произвел) выигрыш от своего велосипеда в наилучшем случае был, хоть и небольшой. Но в наихудшем — при промежутке между предыдущей и текущей датой в несколько лет — свой велосипед, наоборот, проигрывал простой и короткой реализации через DateTime. По этой причине я от своего велосипеда решил отказаться.
Четвертый класс объекта-обработчика был написан, в основном, для иллюстрации того, насколько легко старый добрый объектно-ориентированный подход к решению позволяет модифицировать это решение. Он был выбран для обработки компонента миллисекунд, который содержит довольно много — целую тысячу — потенциально допустимых значений. Чтобы избежать вполне возможного в некоторых вариантах расписания довольно длительного линейного сканирования массива разрешенных расписанием значений такого размера, в данном классе используется сканирование по блокам значений. В конструкторе создаются производные массивы логических значений меньшего размера, и каждый элемент такого массива содержит признак, наличия хотя бы одного разрешенного значения в блоке возможных значений, которому этот элемент соответствует. Массивы могут иметь несколько уровней: элемент массива более высокого уровня показывает есть ли разрешенное значение в блоке, объединяющем несколько блоков массива более низкого уровня. Число уровней массивов и размеры блоков для них передаются как параметры конструктора. Такое решение при правильном выборе размеров блоков позволяет снизить асимптотическую сложность поиска разрешенного значения от O(N) до примерно O(корень степени M от N), где M — число уровней массивов. Алгоритм поиска следующего/предыдущего значения в этом классе описан под спойлером.
Если обратить внимание на количество комментариев в коде, видно, что этот алгоритм мне тоже дался не сразу.
Метод StepValue ищет допустимое расписанием значение только в границах блока, а если не находит — переходит к следующему уровню и ищет допустимый расписанием элемент уже там. Если поиск производится в массиве максимального уровня, то допустимый элемент ищется по всему массиву, если нет — то тоже только в границах блока для текущего уровня, а при ненахождении — поиск переходит на следующий более высокий уровень. Если блок с допустимым значением найден, то поиск возвращается на более низкий уровень. На этом уровне производится поиск в блоке первого/последнего (в зависимости от направления шага) более мелкого блока, содержащего допустимое значение, или самого значения, в зависимости от уровня, на который вернулся поиск. Если поиск производился не на уровне значений, то поиск возвращается дальше, на ещё более низкий уровень — и так до тех пор, пока не будет найдено допустимое значение.
Результат второй части решения
Итак посмотрим, что получилось в результате. А в результате у нас получилась требуемая в задании реализация методов поиска:
- в которой не используются явно неэффективные структуры данных, требующих слишком большого объема памяти;
- в которой не используются заведомо неэффективные алгоритмы;
- в которой нет (ну, в .NET Framework — почти нет, но вот в .NET Std 2.1 — нет вообще) выделения на время работы методов поиска памяти из кучи с оставлением этой памяти как мусора;
- в которой изначально есть определенная алгоритмическая оптимизация, заключающейся в отказе от проверки заведомо негодных значений — тех, которые не попадают в диапазон между минимальным и максимальным разрешенными;
- которая получилось достаточно компактной и расширяемой, с потенциалом для дальнейшей оптимизации; при необходимости эту оптимизацию легко углубить, сделав специальный объект-обработчик для компонента, являющего узким местом; в принципе (здесь я это не делал, но...), возможно даже выбирать объект-обработчик для компонента в зависимости от конкретного вида расписания для него — например, разный для расписания с одним значением, с небольшим количеством значений и с большим количеством значений.
То есть, и вторую часть задания — реализацию поиска по расписанию с использованием старого доброго объектно-ориентированного подхода — можно считать успешно выполненной.
Заключение
Итак, я описал, как можно было бы решить тестовую задачу используя старое доброе ООП, а не просто "на отвали" и, при этом — без использования монад и goto. И на основе этого описания я полагаю, что старое доброе ООП ещё способно послужить людям: у него есть свои преимущества.
Из описания же тестового задания, которое послужило основой всего этого обсуждения, непонятно, что именно искал работодатель. Может быть ему был нужен ли кандидат, способный быстро сделать решение, чтобы подпереть им как костылем падающий рабочий продукт (как оказалось — нет). А может, ему был нужен кандидат, перед совершенством сотворенного которым решения (примерно, как во второй статье) остается только сказать "Круто!" и что его ни в коем случае нельзя упуститьнаверное, ему у нас будет скучно. Но не исключено, что ему на самом деле был нужен кандидат, способный сделать компактное, понятное и расширяемое решение, пусть даже оно будет не стильным, не модным и не молодежным. Тогда кандидат, владеющий старым добрым ООП, способный предоставить решение, подобное описанному в этой статье, ему бы подошел. Но… "Никто этого не знает, и никогда теперь не узнает"((с)Венедикт Ерофеев).
