Старое доброе ООП: решаем тестовое задание

Да, это еще одна статья, вызванная к жизни все тем же тестовым заданием, про решение которого я уже писал. И которое, вообще-то, объективно не заслуживает такого внимания, но так получилось, что меня оно зацепило. Еще когда я разбирался с крутым решением этого задания во второй посвященной ему статье, меня никак не оставляла в покое мысль — а как решить его, чтобы, с одной стороны, не "на отвали" (как в исходной статье), а с другой — без монад и goto, как в крутом решении во второй статье. И тогда я вспомнил про старое доброе объектно-ориентированное программирование (ООП), про те далекие времена, когда я писал сервисы для Windows на Delphi и подумал: а не написать ли мне решение именно в духе того старого доброго ООП. Я подумал — и я написал. И как ненастоящий программист, не обязанный писать код по долгу службы, но пишущий код исключительно ради своего удовольствия, я решил поделиться и кодом, и удовольствием (если получится) с читателями.

Я не обещаю в этом решении сократить объем кода, используя крутые сторонние библиотеки, или увеличить его производительность крутой оптимизацией под JIT. Я просто хочу продемонстрировать, как можно решить эту задачу, используя старую добрую объектно-ориентированную парадигму, без монад и без goto, руководствуясь здравым смыслом (ну, и небольшим объемом знаний). И как при этом можно написать код — легко* читаемый (* — если вы привыкли использовать ООП) и легко расширяемый, без сторонних библиотек, и оптимизировать его чисто на алгоритмическом уровне, без помощи тонких настроек JIT.

Итак, кому интересно решение этого неинтересного тестового задания в духе старого доброго ООП, и кто не забыл ещё (но уже осилил), что означает ключевое слово virtual — добро пожаловать под кат.

Сразу о старом добром

Немалому числу разработчиков нашего времени при виде аббревиатуры ООП сразу придут на ум SOLID, GoF и много других страшных слов. Так вот, это — не здесь. Здесь не будет ни слова ни про SOLID, ни про "паттерны" — здесь будет только про код. Потому что эти страшные слова тут не нужны: масштаб(небольшое тестовое задание) и время жизни (спихнуть тестовое задание) проекта никак не оправдывают погружения в эти безусловно полезные, но нужные только для куда более крупных и долгоживущих проектов концепции.

Нет, конечно, если поискать, то следы этих концепций тут есть. Например, сложно так широко использовать виртуальные методы, как в этом решении, напрочь игнорируя принцип имени некой Барбары, фамилия которой постоянно вылетает у меня из головы (но точно начинается с буквы L — т.к. это буква L из слова SOLID ) — его ещё называют "принцип подстановки"(но в этом названии нет буквы L) — то есть, нарушать совместимость виртуальных методов по видимой извне их семантике. Но, в целом, для решения задач такого масштаба вполне достаточно всего лишь здравого смысла — того самого, который является неотъемлемой частью старого доброго ООП.

О решении вообще

Сразу сообщу: репозиторий git с кодом решения выложен на github, в нем есть несколько веток с немного разными вариантами решений — о них, зачем они были созданы и чем они отличаются, будет написано далее. Основная ветка, как это положено для старого доброго решения, называется master (и никаких "main"!), и примеры кода по умолчанию надо смотреть в ней. А там, где нужно смотреть в другую ветку — об этом будет сказано явно.

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

Выбор формата данных для представления результата разбора строки расписания также совершенно не оригинален. Сама структура строки расписания, в которой для каждого компонента даты/времени — от миллисекунды до года — задается свое собственное, независимое от других компонентов, ограничение, логично приводит к варианту, выбранному в обеих предыдущих статьях: для представления набора допустимых значений каждого компонента используется массив логических значений: по одному на каждое возможное значение компонента. То есть, результат разбора строки расписания записывается программой-разборщиком в набор массивов обычных логических (bool) значений — по одному массиву для каждого из компонентов даты/времени. А так как количество возможных значений для каждого компонента невелико — 1000 для миллисекунд, 200 — для лет и так далее по убывающей, а суммарно — всяко меньше 2000, то я решил, что нет никакого смысла заморачиваться минимизацией объема памяти для их хранения (например — в виде битовой карты): несколько сэкономленных килобайт того явно не стоят.

    ...
    bool[][] AllowedLists = new bool[PartConsts.NUM_PARTS][];
    if (scheduleString != null)
      MainParser(scheduleString, AllowedLists);
    ...

Поскольку, однако, решение в этой статье предлагается старое доброе объектно-ориентированное, то получившиеся после разбора строки расписания массивы допустимых значений не используются напрямую методами поиска. Вместо этого качестве своего рода внутреннего формата расписания методы поиска используют набор объектов-обработчиков — по одному для каждого компонента даты/времени. При создании объекта-обработчика используемый для этого делегат получает ссылку на массив допустимых значений для соответствующего компонента. Расписание, разрешающее все значения компонента ("*"), представляется пустой ссылкой (null) на массив допустимых значений этого компонента. Это позволяет просто и естественно пропускать в процессе разбора любую обработку для компонентов даты/времени, список допустимых значений для которых в строке расписания отсутствует. В соответствии с методологией ООП все объекты-обработчики принадлежат к подклассам одного базового класса. Базовый класс предоставляет виртуальные методы (полный список этих методов — см. далее), используемые в реализации методов поиска класса Schedule. Реализация методов поиска в классе Schedule вызывает их по ссылке, имеющей тип базового класса. Это позволяет легко заменять реализацию объектов-обработчиков, используемых при поиске методов для каждого компонента даты/времени.

  ...
    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 мог правильно обработать эту подстроку, перекрыв этот метод.

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

Третий класс-разборщик второго уровня, DayOfWeekPartParser, разбирающий расписание для дней недели, устроен совсем просто: поскольку день недели — это просто список значений, то этот класс создает и сохраняет во внутреннем поле экземпляр класса-разборщика списка значений ListParser (о нем — ниже), настроенный через параметры его конструктора на нужный диапазон значений, и вызывает для выполнения распознания и разбора методы Recognize и Parse этого экземпляра соответственно.

Третий уровень — разбор списков допустимых значений компонентов даты и времени

В конце концов, все методы разбора второго уровня вызывают для дальнейшего разбора (а класс 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.

    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.

Метод Parse класса ListParser напрямую реализует первую строку написанного выше формального определения: он в цикле по очереди обрабатывает каждую из разделенных запятыми подстрок. Для каждой подстроки прежде всего он определяет ее тип значения. Для этого он вызывает по очереди методы Recognize всех зарегистрированных экземпляров классов-обработчиков элемента списка. Если метод Recognize экземпляра распознает значение подстроки как принадлежащее обрабатываемому им типу (возвращает true), то ListParser.Parse вызывает метод Parse для этого экземпляра, и, в случае успеха (возврата true) переходит к обработке следующей отделенной запятой подстроке, если такая есть. Если ни один из зарегистрированных классов не распознает подстроку, то разбор прекращается с ошибкой (возвращается false). Методы 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;
        }

Управление памятью для хранения подстрок в процессе разбора

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

Вместо этого я использую для хранения подстроки структуру со ссылкой на исходную строку данных и границами подстроки. Так как для реализации задания сначала был выбран шаблон .NET Framework Class Library (как более старый и более добрый), то у меня не было возможности изначально использовать предназначенную для этого в современном C# структуру ReadOnlyMemory<Char>. Поэтому мне пришлось изобрести свой велосипед в виде класса StringPart. В репозитории он используется почти во всех вариантах решения — всех ветках, кроме netstd21, где я попытался максимально использовать новые возможности, появившиеся в .NET Core/Standard 2.1 (об этом ниже).

    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) избавиться от статического выделения памяти для разбора строки расписания, и, как следствие, необходимости использовать при разборе критическую секцию.

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

Что получилось в результате

Объем кода разборщика (исключая "церемониальные" (boilerplate) using, которые VS лепит при создании файла с классом автоматом и которые мне было лень убирать, а также — исключая совершенно необязательную проверку существования даты, попадающей под расписание) — это ~430 строк (вместе с пустыми строками, строками с единственной фигурной скобкой и т.п.). Конечно, это в два с лишним раза больше, чем в крутом решении из второй статьи, с монадами, но там использовалась (хоть и не оптимально, см. мою предыдущую статью) сторонняя библиотека. У автора изначальной статьи с его торопливо сделанным и лишенным гибкости решением получилось и без сторонней библиотеки тоже сильно меньше — ~230 строк (почти в 2 раза). То есть, получается, что гибкость — она на таких масштабах объема кода стоит заметно дороже. Но — не запредельно.

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

Вторая часть — методы поиска по расписанию

Перейдем теперь к решению второй части задания — реализации методов поиска по расписанию с помощью старого доброго ООП.

О компонентах даты и времени

После разбора строки расписания мы имеем своего рода внутренний формат расписания в виде набора объектов-обработчиков, хранящихся в массиве с индексами, равными номерам компонентов, за обработку которых они отвечают. Посмотрим теперь, что должны делать эти объекты. Самое первое, что они должны уметь делать — это проверить переданное им значение компонента на допустимость, то есть соответствие его расписанию. Но есть у них и другие функции, используемые при поиске ближайшего допустимого значения компонента. И если мы посмотрим на возможные варианты обработки компонентов даты/времени при поиске, то заметим, что способы этой обработки и требуемые для этого методы отличаются.

Во-первых, компоненты делятся на две большие группы. Большинство компонентов, составляющее первую группу, не зависят друг от друга в том смысле, что их значения задается напрямую, а не вычисляются на основе значений других компонентов. Эту группу далее я буду называть независимыми компонентами. Для таких компонентов переход к следующему/предыдущему ближайшему значению сводится (в первом приближении, ибо есть тонкости, рассмотренные далее) к поиску и установке следующего или предыдущего допустимого значения. То есть, для их объектов-обработчиков нужен метод перехода к этому ближайшему допустимому значению. Кроме того, для независимых компонентов нужно реализовать действия, которые производятся, если в нужном направлении нет больше допустимых значений — сообщить о необходимости изменить другие, "старшие" (о старшинстве — подробнее под спойлером) компоненты и одновременно установить правильное значение этого комонента — крайнее допустимое, наибольшее или наименьшее, в зависимости от направления поиска.

Но есть один компонент — день недели, который не относится к первой группе, независимым компонентам. Он является единственным представителем второй группы — зависимых компонентов. Значение компонентов этой группы не задаются напрямую, а косвенно зависят от других компонентов. В случае дня недели — от компонентов даты: число месяца, месяца и года. И ещё, для таких компонентов нет возможности установить допустимое значение напрямую (именно поэтому он называется зависимым): чтобы изменить значение конкретно дня недели, нужно менять другие компоненты даты, после чего — проверять, является ли получившееся после этого значение компонента (дня недели в нашем случае) разрешенным в расписании. Поэтому методы поиска ближайшего значения, определенные для независимых компонентов, для зависимых компонентов, в частности — компонента дня недели, не нужны.

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

Второе отличие между компонентами состоит в том, что есть, по крайней мере, один компонент — число месяца — который, хоть и является независимым с точки зрения установки его значения, но верхний предел значений для этого компонента — число дней в месяце — не фиксирован, а определяется значениями более старших компонентов — месяцем и, иногда, годом. Поэтому некоторые методы должны работать для него по-другому. Что ж, в старом добром объектно-ориентированном программировании для реализации такого поведения как раз есть нужное средство — виртуальные методы: то самое некогда забытое Королем Разработки ключевое слово virtual — здесь оно нам как раз пригодится.

О структуре алгоритма поиска

Самой некрасивой частью обоих решений мне показалась внутренняя часть цикла поиска следующего или предыдущего значения — цикла, который завершается по факту нахождения допустимого значения или исчерпания возможных значений. В первом решении там была ужасного вида совокупность многократно вложенных условных операторов. Впрочем, основной ужас ей IMHO придают огромные отступы, загоняющие код внутренних частей чуть ли не за правый край экрана, и многочисленные строки с единственной фигурной скобкой (в большинстве своем, кстати — совершенно излишние: и с точки зрения синтаксиса, потому что ограничиваемые ими блоки содержат всего один оператор, и для понимания уровня вложенности — для этого вполне было бы достаточно отступов, которые при этом, на мой взгляд следовало бы сделать поменьше). Эти строки и отступы съедают много пространства — сам-то код, если собрать его в одной обозримой области, достаточно прост и понятен (для меня, по крайней мере). Тем не менее, эта куча вложенных if вызвала негативную реакцию у достаточно большого числа комментаторов, поэтому, наверное, лучше так не делать.

Во втором решении эта внутренняя часть цикла, хотя и выглядит, на первый взгляд, привлекательнее, на самом деле, ещё более громоздкая, потому как содержит не один вложенный цикл — по миллисекундам, а несколько вложенных циклов — практически, по одному для каждого компонента даты/времени. Не говоря уж о том, что стремление избежать ещё более громоздких циклов побудило автора использовать пресловутый оператор goto, который древний мыслитель Дейкстра повелел считать вредным.

Короче, в результате чтения именно этого куска кода в обоих решениях у меня возникло желание переписать его так, чтобы не обрабатывать каждый независимый компонент по отдельности, а свернуть обработку всех компонентов в ещё один, внутренний, цикл. Однако проверку допустимости значения зависимого компонента — дня недели — все равно придётся делать после этого внутреннего цикла.

Для внутреннего цикла, по компонентам даты/времени, хранение промежуточного результата поиска в формате DateTime не совсем подходит: компоненты в этом формате не изолированы. Изменение компонента может повлиять на значение более старшего, и это нужно как-то отдельно отслеживать, делая тем самым обработку каждого компонента неявно зависимой от другого компонента (что для цикла IMHO подходит плоховато). А любая прямая установка значения промежуточного результата (через конструктор DateTime, в коде решений из предыдущих статей это делается довольно часто) устанавливает значения младших компонентов жестко в их минимальное или максимальное (в зависимости от направления поиска) значение, делая невозможной кое-какую полезную алгоритмическую оптимизацию (о ней будет рассказано ниже).

Поэтому я принял решение хранить в процессе обработки значение каждого компонента отдельно, как элемент массива компонентов типа int (в коде он обычно называется ValueParts) с индексом, равным номеру компонента.

Объекты-обработчики компонентов даты/времени, как уже было написано выше, при рассмотрении программы разбора строки расписания, тоже хранятся в массиве (с именем ScheduleParts), так что объект-обработчик для текущего компонента всегда можно выбрать по его номеру — индексу массива. Все это дает возможность реализовать внутреннюю часть внешнего цикла как один или несколько внутренних циклов по компонентам. Как именно эта возможность была использована во внутренних методах — об этом ниже. Сейчас же перейдем к внешне видимой части — публичным методам поиска.

Реализация публичных методов поиска

Реализации публичных методов класса Schedule, указанных в задании, сделана через ряд вспомогательных методов. Прежде всего, это — метод SplitDateTimeToParts, заполняющий на основе входного параметра типа DateTime описанный выше массив значений компонентов даты/времени. Он вызывается в начале всех публичных методов: NearestEvent, NearestPrevEvent, NextEvent и PrevEvent. Массив компонентов времени, который нужно заполнить, передается в метод SplitDateTimeToParts по ссылке. Память под этот массив отводится в начале публичных методов и освобождается в их конце. Подробнее про отведение и освобождение памяти будет написано ниже.

Далее в методах NearestEvent/NearestPrevEvent (допускающих исходный момент времени) с помощью вспомогательного метода CheckCurrentEvent производится проверка, что исходный момент времени (указанный в переданном им параметре) является допустимым согласно расписанию. Если в указанных методах это не так, а в другой паре методов, NextEvent/PrevEvent, для которых исходный момент недопустим — в любом случае, вызывается вспомогательный метод StepToNearestEvent чтобы найти следующий или предыдущий допустимый момент времени. Этот метод возвращает в переданном ему по ссылке массиве с исходными значениями компонентов даты/времени ближайший к исходному момент времени, находящийся в нужном направлении, допустимый в расписании. Если такого момента времени нет, то метод возвращает false, что вызывает выброс исключения в публичных методах.

И, наконец, если нужный момент времени был найден, то все публичные методы создают из возвращенных значений компонентов объект 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, получился довольно компактным и код его, смею надеяться, — читабельным.

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

Поиск допустимой комбинации производится в первом внутреннем цикле. Этот цикл имеет довольно сложную структуру: номер обрабатываемого компонента (это, фактически — переменная цикла) может как увеличиваться, так и уменьшаться в зависимости от результата текущей выполняемой операции. Этих операций возможны три: сравнение значения компонента с расписанием (возможное только в начале, до других операций), шаг — изменение значения компонента на следующее/предыдущее допустимое расписанием, и сброс — установка значения компонента в крайнюю (первую для поиска следующего значения или последнюю — для поиска предыдущего) допустимую расписанием величину. Все эти операции выполняются виртуальными методами объектов-обработчиков, назначенных для каждого компонента. Имена этих методов — ValueIsAllowed, StepValue и Wrap соответственно. После этих операций производится изменение номера следующего обрабатываемого компонента: он увеличивается или уменьшается на 1, в зависимости от результата этих операций. Условием окончания этого цикла является выход номера следующего обрабатываемого компонента за пределы допустимого диапазона: это означает либо что все независимые компоненты имеют допустимые расписанием значения (номер меньше 0), либо что допустимых расписанием комбинаций значений независимых компонентов больше нет (номер больше максимального). Полное описание алгоритма — в частности, когда какой метод в первом внутреннем цикле вызывается и в какую сторону в нем меняется номер обрабатываемого компонента на каждом проходе — получилось довольно объемным, поэтому я убрал его под спойлер.

    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, но так было не изначально (если вдруг кому интересно, как и почему — загляните под спойлер).

Четвертый класс объекта-обработчика был написан, в основном, для иллюстрации того, насколько легко старый добрый объектно-ориентированный подход к решению позволяет модифицировать это решение. Он был выбран для обработки компонента миллисекунд, который содержит довольно много — целую тысячу — потенциально допустимых значений. Чтобы избежать вполне возможного в некоторых вариантах расписания довольно длительного линейного сканирования массива разрешенных расписанием значений такого размера, в данном классе используется сканирование по блокам значений. В конструкторе создаются производные массивы логических значений меньшего размера, и каждый элемент такого массива содержит признак, наличия хотя бы одного разрешенного значения в блоке возможных значений, которому этот элемент соответствует. Массивы могут иметь несколько уровней: элемент массива более высокого уровня показывает есть ли разрешенное значение в блоке, объединяющем несколько блоков массива более низкого уровня. Число уровней массивов и размеры блоков для них передаются как параметры конструктора. Такое решение при правильном выборе размеров блоков позволяет снизить асимптотическую сложность поиска разрешенного значения от O(N) до примерно O(корень степени M от N), где M — число уровней массивов. Алгоритм поиска следующего/предыдущего значения в этом классе описан под спойлером.

Результат второй части решения

Итак посмотрим, что получилось в результате. А в результате у нас получилась требуемая в задании реализация методов поиска:

• в которой не используются явно неэффективные структуры данных, требующих слишком большого объема памяти;
• в которой не используются заведомо неэффективные алгоритмы;
• в которой нет (ну, в .NET Framework — почти нет, но вот в .NET Std 2.1 — нет вообще) выделения на время работы методов поиска памяти из кучи с оставлением этой памяти как мусора;
• в которой изначально есть определенная алгоритмическая оптимизация, заключающейся в отказе от проверки заведомо негодных значений — тех, которые не попадают в диапазон между минимальным и максимальным разрешенными;
• которая получилось достаточно компактной и расширяемой, с потенциалом для дальнейшей оптимизации; при необходимости эту оптимизацию легко углубить, сделав специальный объект-обработчик для компонента, являющего узким местом; в принципе (здесь я это не делал, но...), возможно даже выбирать объект-обработчик для компонента в зависимости от конкретного вида расписания для него — например, разный для расписания с одним значением, с небольшим количеством значений и с большим количеством значений.

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

Заключение

Итак, я описал, как можно было бы решить тестовую задачу используя старое доброе ООП, а не просто "на отвали" и, при этом — без использования монад и goto. И на основе этого описания я полагаю, что старое доброе ООП ещё способно послужить людям: у него есть свои преимущества.

Из описания же тестового задания, которое послужило основой всего этого обсуждения, непонятно, что именно искал работодатель. Может быть ему был нужен ли кандидат, способный быстро сделать решение, чтобы подпереть им как костылем падающий рабочий продукт (как оказалось — нет). А может, ему был нужен кандидат, перед совершенством сотворенного которым решения (примерно, как во второй статье) остается только сказать "Круто!" и что его ни в коем случае нельзя упуститьнаверное, ему у нас будет скучно. Но не исключено, что ему на самом деле был нужен кандидат, способный сделать компактное, понятное и расширяемое решение, пусть даже оно будет не стильным, не модным и не молодежным. Тогда кандидат, владеющий старым добрым ООП, способный предоставить решение, подобное описанному в этой статье, ему бы подошел. Но… "Никто этого не знает, и никогда теперь не узнает"((с)Венедикт Ерофеев).