Очень часто в разных задачах встречается один и тот же однотипный шаблон: в зависимости от того, в какой из нескольких, известных заранее, интервалов попало значение, следует предпринять разное действие. Обычно, таким действием является вычисление некоего числа или в общем случае, некой величины (необязательно числовой). Когда интервалов достаточно много, то начинается уже рутина с операторами if или switch, а это повышает вероятность ошибок, да и код смотрится, мягко говоря, не очень…
В таких случаях, нам бы хотелось иметь в D нечто вроде функции cond из LISP-family языков или мощный генератор сопоставлений а-ля match из некоторых современных языков. Но в D этого нет и не планируется к добавлению, а это значит, что проблемой необходимо заниматься программисту.
К счастью, мы кое-что уже придумали…
Для начала реализуем просто саму абстракцию интервала, подразумевая то, что в интервале могут быть значения самых разных типов, но при том, что начало и конец (т.е нижняя и верхняя границы) имеют тот же самый тип, что и будущее значение, попадание в интервал которого и будет проверятся. Таким образом, все что требуется от интервала — это наличие границ и метод, который проверяет попадание некой величины в этот самый интервал.
Однако, просто наличия нижней и верхней границы для интервала недостаточно, необходимо также, чтобы у интервала было некое качество, которое показывает как именно контролируются его границы. Дело в том, что интервал может иметь различные комбинации такого параметра как включенность/исключенность нижней/верхней границы из рассмотрения попадания в него некоторого значения:
- закрытый интервал (CLOSED) — и нижняя, и верхняя границы не включены в рассматриваемый интервал (т.е. значение, если оно равно нижней/верхней границе в интервал не попадет);
- закрыто-открытый (CLOSED-OPEN) — нижняя граница включена в интервал, а верхняя — нет;
- открыто-закрытый (OPEN-CLOSED) — нижняя граница в интервал не включена, а верхняя включена
- открытый (OPEN) — обе границы входят в интервал.
Примечание автора. Терминологию мы брали отсюда. Поскольку, не удается вспомнить, как именно на русском языке, правильно называются эти типы интервалов.
Реализация интервала, в нашем представлении выглядит так:
import std.stdio; import std.algorithm; import std.range; import std.conv; import std.math : abs; import std.string; // свойство template addProperty(T, string propertyName, string defaultValue = T.init.to!string) { import std.string : format, toLower; const char[] addProperty = format( ` private %2$s %1$s = %4$s; void set%3$s(%2$s %1$s) { this.%1$s = %1$s; } %2$s get%3$s() { return %1$s; } `, "_" ~ propertyName.toLower, T.stringof, propertyName, defaultValue ); } enum INTERVAL_TYPE { CLOSED, // e.g : (x; y) CLOSED_OPEN, // e.g: [x; y) OPEN_CLOSED, // e.g: (x; y] OPEN // e.g: [x; y] }; class Interval(T) { // upper bound mixin(addProperty!(T,"UpperBound", "0")); // lower bound mixin(addProperty!(T, "LowerBound", "0")); // kind of interval mixin(addProperty!(INTERVAL_TYPE, "Type", "INTERVAL_TYPE.CLOSED")); bool isContain(T)(T value) { bool result; final switch (_type) with (INTERVAL_TYPE) { case CLOSED: result = ((value > _lowerbound) && (value < _upperbound)); break; case CLOSED_OPEN: result = ((value >= _lowerbound) && (value < _upperbound)); break; case OPEN_CLOSED: result = ((value > _lowerbound) && (value <= _upperbound)); break; case OPEN: result = ((value >= _lowerbound) && (value <= _upperbound)); break; } return result; } }
Таким образом, мы получаем в свое распоряжение тип, который позволяет устанавливать собственные границы (set/getUpperBound, set/getLowerBound) и проверяет с помощью isContain вхождение некоторого значения в заданный интервал. Код достаточно простой и гибкий.
Примечание автора. Бдительные читатели, конечно, тут кое-что заметят. А именно то, как изобразить интервалы с плюс и минус бесконечностью. На это у меня есть хитрый ответ: если вы используете знаковый тип для интервала, то вы помните о том, что у любого элементарного типа в D есть свойство .max
, которое показывает максимально возможную для типа величину и ее можно взять за условную плюс-бесконечность. Соответственно, эту величину с обратным знаком (т.е. с минусом) можно взять за условную минус-бесконечность. В конце концов, все равно вам же не нужна реальная бесконечность, не так ли ?
Согласитесь, не очень-то удобно каждый раз вспоминать как конструируется интервал, да и легко запутаться в том, какого он типа. Легче было бы, если можно было описывать интервал так, как это принято в математических областях. Именно, поэтому мы придумали функцию преобразование строчного описания интервала (имеется в виду чисто математической нотации со скобками) в интервальный тип:
auto toInterval(T)(string formula) { import std.algorithm; import std.conv; import std.string; string data = formula.strip; char firstBracket = data[0]; char lastBracket = data[$-1]; INTERVAL_TYPE type; if (firstBracket == '(') { if (lastBracket == ')') { type = INTERVAL_TYPE.CLOSED; } else { type = INTERVAL_TYPE.OPEN_CLOSED; } } else { if (lastBracket == ')') { type = INTERVAL_TYPE.CLOSED_OPEN; } else { type = INTERVAL_TYPE.OPEN; } } auto unbracket = data[1..$-1].to!string.split(";"); auto upper = unbracket[1].strip.to!T; auto lower = unbracket[0].strip.to!T; Interval!T xs = new Interval!T; xs.setLowerBound(lower); xs.setUpperBound(upper); xs.setType(type); return xs; }
Теперь, когда у нас есть тип интервала, можно реализовать интересную схему ухода от цепочки if-ов, преобразовав один интересный паттерн в цепочку последовательного прохода проверок по интервалам. Мы говорим о паттерне проектирования, который называется «Цепочка обязанностей»: в этом паттерне есть класс, который инкапсулирует некий запрос к другому классу (классу-обработчику или просто обработчику) и обработчик, в зависимости от вида запроса, может либо выполнить его, либо переадресовать его другому классу со схожим интерфейсом.
Подобную идею мы модифицируем под использование с интервалами — создадим «цепочку интервалов»: поскольку каждый интервал имеет в своем составе метод isContain, то можно создать некую структуру-контейнер, которая сохранит в себе целый массив структур-интервалов и осуществляет перебор на попадание значения в некую область значений.
Реализуется идея следующим образом:
struct CoI(T) { mixin(addProperty!(Interval!T[], "Intervals")); mixin(addProperty!(T[], "Values")); auto run(T)(T x) { import std.range : zip; T result; foreach (e; zip(_intervals, _values)) { if (e[0].isContain(x)) { result = e[1]; break; } } return result; } }
В нашей «цепочке интервалов» (chain of intervals, CoI) применена обычная структура, в которую добавлены с помощью генератора сеттеров/геттеров два свойства: Intervals, которое включает в себя набор интервалов для проверки, и Values, которое включает в себя набор значений, которые соответствуют каждому из интервалов. Для начала работы с цепочкой в нее с помощью соответствующих сеттеров загружаются подготовленные интервалы и значений, после чего структура полностью готова к работе и может проверить некое значение на попадание в интервал и выдать соответствующую ему величину из возможных величин. Достигается подобное с помощью параметризованного метода run, принимающего в себя значение под испытание, и конкатенируя в единый диапазон интервалы и значения, проводит их через цикл foreach. В цикле аккуратно разбирается аггрегат типов (то, что содержится в переменной e
) и используется метод isContain
каждого (!) отдельно взятого интервала до тех пор, пока либо проверка не достигает своей цели (испытуемое значение попадает в интервал).
Вот небольшой пример:
void main() { auto xs = [ "(-1; 10]".toInterval!int, "(10; 20]".toInterval!int, "(20; 1000)".toInterval!int ]; writeln(xs); CoI!int coi; coi.setIntervals(xs); coi.setValues([1, 8, -2]); coi.run(0).writeln; coi.run(20).writeln; coi.run(21).writeln; }
На выходе получаем: