Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

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

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

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

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

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

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

  • Разглядеть равенство 2-х диапазонов
  • Разглядеть пересечение, объединение, разность и т.д. 2-х диапазонов
  • Рассматривать диапазоны, значения которых являются дискретными величинами (типа «все чётные целые числа в диапазоне от 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,WithInclusiveLowerBoundWithLowerBound и т.д., которые при вызове будут возвращать новосозданный экземпляр с соответствующими настройками. Ещё одним архитектурным решением было бы создание отдельного статического необобщённого класса-фабрики, фабричные обобщённые способы которого принимали бы параметры, выводили бы из этих параметров тип и возвращали бы экземпляр диапазонного класса. Я имею ввиду что-то типа этого:

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

Бесспорно, что всё это — сто
Вновь-таки, тут есть уйма вариантов. Тут особенно значимый момент состоит в том, что нам сразу же нужно отбросить «неверный» механизм, заключающийся в продолжении перебора элементов до тех пор, пока следующий элемент не окажется вне диапазона. В качестве блестящего примера, отчего данный вариант ущербен, представьте диапазон (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) касательно примитивна, но мы обязаны ничего не упустить. Нам необходимо поменять местами верхнюю и нижнюю границы, поменять местами флаги «включит

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB