Работа с диапазонами и границами в .NET

От переводчика. Тема диапазонов (интервалов) в .NET по праву относится к вечно зелёным и молодым. Сотни заданных на форумах вопросов, десятки написанных статей… кажется, что это закончится только тогда, когда Microsoft наконец-то введёт в Framework Class Library свой механизм по работе с диапазонами. И этому есть логичное объяснение — наверное, каждый программист рано или поздно сталкивается с необходимостью использования некоего диапазона значений, будь то числа, даты или какие-либо другие величины. Возникла такая необходимость и у меня, однако, помня о том, что свои велосипеды — не лучшее решение, я прошерстил Интернет и попал на превосходную статью Джона Скита, перевод которой, собственно, и представляю вашему вниманию.

В первом издании моей книги «C# in Depth» приводился абстрактный обобщённый класс Range, в котором для прохода по элементам в диапазоне использовались виртуальные методы. К сожалению, этот класс был неидеален, так как не учитывал определённые пограничные случаи. Однако данная статья повествует не столько о проектировании идеального класса по работе с диапазонами, сколько о том, какие следует учитывать нюансы и соображения. Моя библиотека классов MiscUtil содержит класс, в котором учтено большинство вещей, рассмотренных в этой статье, но, конечно же, и этот класс далеко неидеален. Вообще, в январе 2008 года я написал небольшую статью о диапазонах в своём блоге, но с тех пор утекло много воды, я много чего переосмыслил и решил более детально раскрыть тему в виде данной статьи.

Постановка задачи

Давайте сначала определимся с тем, что мы хотим и что мы можем сделать, причём сформулируем задачу как можно более однозначно.

• Создать механизм хранения диапазона значений для любого подходящего типа
• Итерировать по множестве этих значений с использованием пользовательской функции перебора

Кажется, будто мы вроде как всё и описали, но помним, что дьявол кроется в деталях. Нам надо также учитывать следующие вещи, а именно:

• Рассмотреть равенство двух диапазонов
• Рассмотреть пересечение, объединение, разность и т.д. двух диапазонов
• Учитывать диапазоны, значения которых являются дискретными величинами (типа «все чётные целые числа в диапазоне от 0 до 100»)
• Разобраться с функциями перебора, которые должны «передвигаться» по диапазону (т.е. определиться, в каком направлении они должны двигаться и т.д.)

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

Детали

Прежде всего, давайте подумаем о типах, которые вообще допустимы для использования в диапазонах. Мы хотим, чтобы класс диапазона был обобщённым (generic), и мы хотим иметь возможность сравнить (compare) между собой два значения, чтобы знать, какое из них является большим, а какое — меньшим. Мы можем этого достичь, применив такой ограничитель к типу T, который требовал бы, чтобы тип T реализовал интерфейс IComparable<T>. Однако если мы так поступим, то тем самым сделаем невозможным использование типов, которые были спроектированы до появления обобщённого функционала в C# — эти типы ничего не знают об обобщённом интерфейсе IComparable<T>. Кроме того, если мы будем использовать компаратор по умолчанию, то он потом может нас немного ограничивать. К примеру, на мой взгляд, одним из способов изменения диапазона на обратный (reversing) является замена нижней и верхней границы на противоположные и одновременное изменение компаратора, но с компаратором по умолчанию всё будет сложнее. Впрочем, об этом в конце.

Буду честным — я не могу представить себе диапазон, элементы которого мы бы не смогли сравнить между собой на определение «больше-меньше», но я твёрдо убеждён, что для диапазона мы должны иметь возможность задать свой собственный механизм сравнения (компаратор). Теперь у нас есть другой выбор: будем ли мы выражать сравнение через IComparer<T>, или же через Comparison<T>? Эти обобщённые интерфейсы эквивалентны, но IComparer<T>, вероятно, более распространён и часто используем, поэтому мы остановимся на нём. Это также значит, что мы сможем использовать свойство Comparer<T>.Default для естественного сравнения безо всяких лишних телодвижений. Если же коду, использующему наш диапазонный класс, непременно будет требоваться использование Comparison<T>, то это легко сделать, создав класс-адаптер (что и сделано в MiscUtil).

Возвращаясь к нашему решению с ограничением элементов диапазона, следует заметить, что здесь перед нами стоит интересное архитектурное решение: будем ли мы ограничивать потенциальных пользователей нашего «диапазонного» класса слишком сильно, не давая им возможности воспользоваться диапазоном, если тип их элементов не имеет естественного сравнения, или же позволим воспользоваться, подвергаясь риску попасть на «неадекватный» с точки зрения диапазона тип элементов? Я, в целом, предпочту работать без ограничений, хотя только «за», если пользователи API будут придерживаться адекватных решений.

Итак, мы знаем, что в нас будет сравнение, а это значит, что мы будем иметь верхнюю и нижнюю границы. И этот факт порождает новые вопросы:

1. Должны ли границы (пределы) быть включающими (inclusive) или исключающими (exclusive), другими словами, должен ли диапазон быть закрытым или открытым.
2. Нужны ли в одном диапазоне обе границы, или может существовать диапазон, в которого есть лишь одна граница? Допустим ли диапазон, в которого нет обоих границ, т.е. который покрывает множество всех существующих элементов?
3. Как будет проходить итерация по диапазону, если нижняя граница является исключающей (открытой)?
4. Как будет проходить итерация по диапазону, если нижняя граница вообще отсутствует?

Так как я не хочу чрезмерного раздувания сложности в этой статье, то давайте остановимся на конечных диапазонах, т.е. таких, в которых заданы одновременно и верхняя, и нижняя границы. Определимся, что при создании нового экземпляра диапазона нижняя граница будет устанавливаться включающей (закрытой), а верхняя — исключающей (открытой). Вместе с тем, в конструкторе будут присутствовать опциональные параметры, позволяющие точно указать «включающесть» или «исключающесть» любой границы. Аналогично этому, для сравнения будет установлен компаратор по умолчанию для указанного типа, но через опциональный параметр можно будет явно указать свой кастомный компаратор. В случае опционального параметра для компаратора дефолтным значением будет null и таким образом я смогу «обойти» потенциальный баг, когда кто-то явно передаст в параметр null; ведь для кода будет «всё равно», откуда взялся этот null — был ли он указан явно, или же пользователь опустил опциональный параметр конструктора. Более того, это значит, что если вы явно хотите использовать компаратор по умолчанию, то вам необходимо передать в конструктор выражение default(IComparer<T>), которое, естественно, возвратит всё тот же null. Ну а проблему итерации по диапазону при исключающей нижней границе мы рассмотрим позже.

Ну и последний архитектурный момент перед тем, как ринуться в код: наш тип будет неизменяемым (immutable). Что, естественно, не отменяет того факта, что мы не можем контролировать изменяемость или неизменяемость элементов нашего диапазона, однако будем помнить, что наиболее «адекватные» элементы для использования в диапазонах (такие, как числа) уже являются неизменяемыми.

Первые шаги в реализации диапазона

Пришло время кодинга. Начнём с малого — только конструктор и определитель наличия элемента в диапазоне.

public sealed class Range<T>  {      public T LowerBound { get; private set; }      public T UpperBound { get; private set; }      public bool InclusiveLowerBound { get; private set; }      public bool InclusiveUpperBound { get; private set; }      public IComparer<T> Comparer { get; private set; }       public Range(T lowerBound, T upperBound,                    bool inclusiveLowerBound = true,                    bool inclusiveUpperBound = false,                    IComparer<T> comparer = null)      {          LowerBound = lowerBound;          UpperBound = upperBound;          InclusiveLowerBound = inclusiveLowerBound;          InclusiveUpperBound = inclusiveUpperBound;          Comparer = comparer ?? Comparer<T>.Default;           if (Comparer.Compare(LowerBound, UpperBound) > 0)          {              throw new ArgumentException("Invalid bounds");          }      }       public bool Contains(T item)      {          int lowerCompare = Comparer.Compare(LowerBound, item);          if (lowerCompare > (InclusiveLowerBound ? 0 : -1))          {              return false;          }          int upperCompare = Comparer.Compare(item, UpperBound);          if (upperCompare > (InclusiveUpperBound ? 0 : -1))          {              return false;          }          return true;      }  } 

Тот факт, что у нас дублируется код для верхней и нижней границы, наводит меня на мысль, что следовало бы инкапсулировать сущность границы диапазона в свой собственный тип … но не будем слишком быстро всё усложнять. Отмечу, что если бы мы таки решили создать диапазон с «бесконечной» (т.е. не заданной) верхней и/или нижней границей, то идея инкапсуляции границы в отдельный тип стала бы существенно более полезной. Код метода Contains далёк от совершенства, но индикаторы выполнения юнит-тестов светятся зелёным, и я этим доволен.

Ради краткости я использовал автогенерируемые свойства с публичными геттерами (аксессорами) и приватными сеттерами (мутаторами). Благодаря этому тип становится неизменяемым извне, но остаётся изменяемым изнутри него самого, что не есть гуд. Идеальным решением было бы использовать поля только для чтения (readonly) и свойства-геттеры к ним, но в таком случае код бы распух и сместил бы внимание с общей концепции на детали.

К классу можно добавить статические методы типа WithExclusiveLowerBound, WithInclusiveLowerBound, WithLowerBound и т.д., которые при вызове будут возвращать новосозданный экземпляр с соответствующими настройками. Ещё одним архитектурным решением было бы создание отдельного статического необобщённого класса-фабрики, фабричные обобщённые методы которого принимали бы параметры, выводили бы из этих параметров тип и возвращали бы экземпляр диапазонного класса. Я имею ввиду что-то типа этого:

var range = Range.Of(5, 10); 

Несомненно, что всё это — сто́ящие архитектурные подходы, но по отношению к цели статьи они не столь интересны, поэтому я больше их касаться не буду. Ну а что более интересно, так это то, как мы собираемся итерировать по диапазону.

Итерирование

Давайте вернёмся к основоположным архитектурным вопросам диапазонного класса. Я полагаю, что предельно ясным является наличие некой итерирующей функции (функции перебора, stepping function), которая может перемещаться от текущего элемента до следующего за ним. В таком случае в нас осталось два вопроса: что считать первым элементом, и как знать, что пора остановиться.

С чего начинать?

Ответ на этот вопрос будет очень простым, если нижняя граница диапазона является включающей — мы начинаем прямо с этой границы. Сложности появляются тогда, когда нижняя граница — исключающая. Предположим, что мы имеем диапазон (0, 50), причём верхняя и нижняя границы исключающие, и что размер одного шага — 5. Должно ли первым элементом быть число 1 (наименьший элемент в диапазоне) или же число 5 (результат старта с 0 и пропуска первого элемента)? Поиск минимального элемента именно в диапазоне сложен в большинстве случаев, а в некоторых случаях вообще невозможен, в частности, когда задан кастомный (пользовательский) компаратор. К примеру, в своих юнит-тестах у меня есть кастомный компаратор IComparer<int>, который просто сравнивает две последние цифры в числах. С таким «извращённым» компаратором вполне реально иметь диапазон (41, 37), который будет содержать 23, 12 и 44, но не 38. А теперь попробуйте определить для этого диапазона минимально возможное значение.

Мы могли бы спроектировать наш класс так, чтобы требовать у пользователя начальное значение, но такое решение мне противно. Мне кажется, что наиболее простое решение — это просто пропускать первый элемент, так, чтобы эти две итерируемые функции были эквивалентны:

var range = new Range<int>(0, 50, false, false); var simpleIterable = range.StepBy(x => x + 5); var equivalentIterable = range.WithInclusiveLowerBound()                                .StepBy(x => x + 5)                                .Skip(1); 

Но мы ненароком пришли к новому архитектурному нюансу: мы собираемся иметь метод, который будет возвращать IEnumerable<T>. Мы могли бы возвратить и IEnumerator<T>, но не будем усложнять жизнь и возвратим IEnumerable<T>: он даст нам возможность использовать foreach, LINQ и т.д.
Ну а что касательно второго вопроса, то…

Когда остановиться?

Снова-таки, здесь есть множество вариантов. Здесь наиболее важный момент состоит в том, что нам сразу же надо отбросить «неверный» механизм, заключающийся в продолжении перебора элементов до тех пор, пока очередной элемент не окажется вне диапазона. В качестве яркого примера, почему этот вариант ущербен, представьте диапазон (0, 255) с включающей верхней границей для типа Byte. А поэтому в нас остаются следующие варианты действий:

• Создать и использовать две функции перебора: одна будет определять, существует ли следующий элемент, а вторая — определять значение этого элемента.
• Использовать одну функцию перебора, которая будет возвращать оба этих значения за один «проход». В этом случае в нас есть следующие подварианты:
       * Использовать Func<Tuple<bool, T>>, которая будет возвращать два значения вместе.
       * Использовать делегат с выводным (out) параметром (это мне не нравится)
       * Попробовать использовать null в случае «элементов больше нет», но в этом случае нас ждут проблемы, если тип элемента T является значимым типом.
• Останавливать перебор, либо когда значение следующего элемента уже «вылезло» из-за диапазона, либо когда оно (значение) меньше или равно значению предыдущего элемента (и таким образом предотвращая «закольцовывание»).

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

Реализация

Теперь, когда мы знаем, что именно хотим сделать, реализация не отнимет много сил. В отличие от реализации в MiscUtil, мы просто добавим методы, использующие блок итератора для тяжелой работы — в этом случае нет нужды в отдельном публичном типе. Чтобы не особо отклоняться от темы этой статьи, я также буду требовать от пользователей класса непосредственно указывать функцию перебора. В MiscUtil я использовал хитроумную поддержку обобщённых операторов от Марка Грэвелла (Marc Gravell), которая позволяет сделать простой перебор для любого типа, который поддерживает оператор сложения (+), но сейчас я не буду это использовать, дабы не отклоняться от темы статьи.

Итак, изначальная реализация:

public IEnumerable<T> StepBy(Func<T, T> step)  {      T current = LowerBound;      // Если нижняя граница исключающая, то переходим к следующему значению      if (!InclusiveLowerBound)      {          current = step(current);      }      while (Contains(current))      {          yield return current;          T next = step(current);          // Handle a stepping function which wraps          // round from a value near the end to one          // near the start; or a stepping function          // which does nothing.          if (Comparer.Compare(next, current) <= 0)          {              yield break;          }          current = next;      }  } 

Здесь есть один потенциальный изъян: мы проверяем «попадание» нового значения в диапазон в цикле, тогда как вызываем функцию перебора, возвращающую новое значение, ещё до цикла при исключающей нижней границе. К счастью, эта проблема решается естественным способом: если функция перебора возвращает первое значение, которое меньше, чем нижняя граница, то это значение, само собой, не будет попадать в диапазон, а значит, и не пройдёт предусловие цикла.

Альтернативный вариант определения точки старта (вместо if) — использовать тернарный условный оператор:

T current = InclusiveLowerBound ? LowerBound : step(LowerBound); 

Какой вариант более удобочитаемый — этот или предыдущий, — зависит от вас.

И последний момент: мы всегда выполняем перебор от нижней границы к верхней. А что, если мы захотим сделать наоборот — от верхней к нижней?

Изменение диапазона на противоположный

Реализация изменения диапазона на противоположный (reversing) относительно проста, но мы должны ничего не упустить. Нам нужно поменять местами верхнюю и нижнюю границы, поменять местами флаги «включительности» и/или «исключительности» этих границ, а также поменять компаратор. К счастью, написание обратного компаратора (reversing comparer) достаточно просто — по крайней мере, до тех пор, пока вы не попадёте в неприятную ловушку. Вот код обратного компаратора, который действует противоположно «обычному» компаратору:

public sealed class ReverseComparer<T> : IComparer<T>  {      private readonly IComparer<T> originalComparer;       public ReverseComparer(IComparer<T> originalComparer)      {          this.originalComparer = originalComparer;      }       public int Compare(T x, T y)      {          return originalComparer.Compare(y, x);      }  } 

Так что же это за «неприятная ловушка», о которой я сказал? Так вот, в методе Compare так заманчиво просто взять и обратить (negate) результат оригинального сравнения на противоположный … но это не сработает, если оригинальный результат originalComparer.Compare будет int.MinValue. Ведь в таком случае, переставив аргументы местами, мы тоже получим int.MinValue. Есть альтернативные варианты реализации обратного компаратора — вы можете учитывать и изменять на противоположный знак оригинального результата, но замена операндов местами, даже при всех этих минусах, всё равно очень изящна.

От переводчика. Данный абзац может быть несколько непонятен для некоторых читателей, поэтому распишу проблему с int.MinValue более детально. Документация по интерфейсу IComparer<T> требует, чтобы тип, реализующий этот интерфейс, определял метод int Compare<T>(T x, T y) таким образом, чтобы этот метод: при равенстве x и y возвращал число 0; если x меньше y, то число меньше 0; если x больше, чем y, то число больше 0. Типы из .NET Framework, реализующие этот метод, возвращают в случае неравенства x и y числа -1 и +1, однако никто не мешает создать метод, который будет возвращать int.MinValue (если x меньше y) и int.MaxValue (если x больше y). Именно в этом случае нас и подстрекает проблема, о которой пишет Скит. Так как число 0 относится к положительным, то
|int.MinValue| == int.MaxValue + 1. А это значит, что в результате выполнения кода
Int32 i = Int32.MinValue; Int32 j = -i; переменной j будет присвоено значение int.MinValue, но не int.MaxValue, как оно кажется разумным. Конечно, если для данного кода включена проверка переполнений (checked), то будет выброшено исключение System.OverflowException, однако проверка переполнений в production-коде встречается довольно редко.

Теперь, когда мы имеем обратный компаратор, мы легко можем реализовать в классе Range метод Reverse:

public Range<T> Reverse()  {      return new Range<T>(          lowerBound: UpperBound,          upperBound: LowerBound,          inclusiveLowerBound: InclusiveUpperBound,          inclusiveUpperBound: InclusiveLowerBound,          comparer:new ReverseComparer<T>(Comparer));  } 

Конечно, тут можно применять новые оптимизации, такие как определение обратного компаратора, чтобы не «оборачивать» обратный компаратор ещё раз (вместо этого можно использовать оригинальный, получив его из поля обратного), но я опустил все эти детали ради простоты кода. Также ради ясности я использовал именованные и опциональные аргументы, введённые в C# 4, но, конечно же, это необязательно, и вы вполне можете достичь того же функционала при помощи перегрузок конструктора.

И ещё один момент, который нельзя забывать: в некоторых случаях результат инвертирования последовательности, сгенерированной оригинальным диапазоном, не будет таким же, как результат инвертирования диапазона и вызова из него инвертированной функции перебора. Например, рассмотрим диапазон [0, 5] (т.е. от 0 и до 5 включительно), функция перебора которого возвращает новый элемент, добавляя число 2 к текущему элементу. В таком случае этот диапазон сгенерирует последовательность { 0, 2, 4 }. Однако если вы инвертируете этот диапазон [0, 5] на [5, 0], изменив функцию перебора на обратную (которая будет возвращать новый элемент, вычитая из текущего число 2), то такой диапазон сгенерирует последовательность { 5, 3, 1 }. И если мы инвертируем оригинальную последовательность при помощи, например, LINQ, то результат { 4, 2, 0 } — это определённо не { 5, 3, 1 }.

Заключение

Как видите, в этой статье нет «сотен кода», и нам удалось завершить задачу при помощи маленького, но полезного класса. Вначале такой работы очень важно определить функционал, фундаментальные рамки нашего класса; ведь, учитывай мы те же отсутствующие границы, и нам пришлось бы полностью переписать его реализацию. Так само важно учитывать все пограничные случаи типа оболочки, функций перебора, которые не изменяют оригинальное значение, и компараторов, возвращающих int.MinValue. Весь код, написанный здесь, доступен для свободного скачивания и включает краткие юнит-тесты, проверяющие корректность решения на многих значениях.

---

От переводчика

Для желающих копать по теме диапазонов дальше я сделал подбор ссылок на статьи, посвящённые, как и эта, реализации диапазонов в .NET.

• Dmitri Nеstеruk. Ranges in C#
• Qwertie. D-style ranges in C# (.NET)
• Sean Hederman. Building a Generic Range class
• Scott McMaster. RangeSet: A Low-Memory Set Data Structure for Integers
• Jay Bazuzi. Comparing ranges
• Sergio Pereira. Language Envy — C# needs Ranges
• Andy Clymer. Ruby Ranges in .NET

Если же говорить о мне, то я остановился на диапазоне от Джона Скита, который входит в состав его библиотеки MiscUtil. Этот диапазон построен на основе диапазона, описываемого в этой статье, однако имеет несколько крайне полезных улучшений. Во-первых, как кратко описал Скит, благодаря использованию деревьев выражений появляется поддержка операций сложения и вычитания для всех типов, поддерживающих подобные операции. Также класс Range из MiscUtil имеет улучшенную поддержку символьных диапазонов, а механизм итерации вынесен в отдельный, более функциональный класс RangeIterator<T>. Негативным моментом может быть то, что данный класс довольно тесно связан с очень многими компонентами из MiscUtil, поэтому придётся либо использовать всю библиотеку, либо же провести кропотливую работу по «вырезанию зависимостей».

Если же вам надо работать с диапазонами дат и времени, то тут абсолютным лидером является библиотека Time Period Library от Jani Giannoudis. Обладатель двух призов за март 2011 на CodeProject, данная библиотека активно обновляется (последнее обновление — 1 октября 2013), интенсивно покрыта юнит-тестами (объём кода юнит-тестов трижды превышает объём кода самой библиотеки), а также поддерживает платформы Silverlight и Windows Phone. Ну и как overkill в данном случае выступает качественный перевод её описания на русский язык от hDrummer.