Диапазоны

Диапазоны – это абстракция доступа к элементу. Эта абстракция позволяет использовать большое количество алгоритмов для большого количества типов контейнеров. Диапазоны подчеркивают nj, как происходит доступ к элементам контейнера, в отличие от того, как реализуются контейнеры. Диапазоны – это очень простая концепция, основанная на том, определяет ли данный тип некоторый набор методов (функций-членов).

Диапазоны являются неотъемлемой частью языка D. Срезы в D являются реализациями самого мощного диапазона – диапазона с произвольным доступом, и в множество возможностей в Phobos явязано с диапазонами. Многие алгоритмы в Phobos возвращают объекты с временным диапазоном. Например, функция filter(), выбирающая элементы, отвечающие некоторому критерию (предикату), фактически возвращает объект диапазона, а не массив.

Диапазоны чисел

Диапазоны чисел используются довольно часто, это диапазоны чисел типа int. Несколько примеров для диапазонов чисел показаны ниже:

// Пример 1 
foreach (value; 3..7)  

// Пример 2 
int[] slice = array[5..10];

Диапазоны в Phobos

Диапазоны, относящиеся к структурам и интерфейсам классов, представляют диапазоны в Phobos. Phobos – официальная среда исполнения и стандартная библиотека, которая поставляется вместе с компилятором языка D.

Существуют различные типы диапазонов, которые включают в себя следующие:

Входной диапазон (InputRange)
Лидирующий диапазон (ForwardRange)
Двунаправленный диапазон (BidirectionalRange)
Диапазон с произвольным доступом (RandomAccessRange)
Выходной диапазон (OutputRange)

Входной диапазон

Самый простой диапазон – это входной диапазон. Другие диапазоны предъявляют больше требований к той реализации, на которой они основаны. Вот три функции, требуемые входным диапазоном:

empty – Она информирует, пуст ли диапазон; она должна возвращать значение true, когда диапазон считается пустым; false в противном случае.
front – Она предоставляет доступ к элементу в начале диапазона.
popFront() – Он сокращает диапазон от начала, удаляя первый элемент.

Пример

import std.stdio; 
import std.string; 
 
struct Student { 
   string name; 
   int number; 
   
   string toString() const { 
      return format("%s(%s)", name, number); 
   } 
}
  
struct School { 
   Student[] students; 
}
struct StudentRange {
   Student[] students; 
   
   this(School school) { 
      this.students = school.students; 
   } 
   @property bool empty() const { 
      return students.length == 0; 
   } 
   @property ref Student front() { 
      return students[0]; 
   } 
   void popFront() { 
      students = students[1 .. $]; 
   } 
}

void main() { 
   auto school = School([ Student("Иванов", 1), Student("Петров", 2), Student("Сидоров", 3)]);
   auto range = StudentRange(school); 
   writeln(range);  
   
   writeln(school.students.length);
   
   writeln(range.front); 
   
   range.popFront;  
   
   writeln(range.empty); 
   writeln(range); 
}

Думаю, этот кусок кода требует некоторого пояснения.

Атрибут @property у метода позволяет вызывать этот метод без скобок, таким образом методы front() и empty() становятся "псевдочленами", и их можно вызывать без скобок: range.front; range.empty;

– прим. пер.

Когда вы скомпилируете и выполните эту программу, она возвратит следующий результат:

[Иванов(1), Петров(2), Сидоров(3)]
3
Иванов(1)
false
[Петров(2), Сидоров(3)]

Лидирующий диапазон

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

import std.array; 
import std.stdio; 
import std.string; 
import std.range;

struct FibonacciSeries { 
   int first = 0; 
   int second = 1; 
   enum empty = false;   //  бесконечный диапазон  
   
   @property int front() const { 
      return first; 
   } 
   void popFront() { 
      int third = first + second; 
      first = second; 
      second = third; 
   }
   @property FibonacciSeries save() const { 
      return this; 
   } 
}
  
void report(T)(const dchar[] title, const ref T range) {
   writefln("%s: %s", title, range.take(5)); 
} 

void main() { 
   auto range = FibonacciSeries(); 
   report("Исходный диапазон", range);
   
   range.popFrontN(2); 
   report("После удаления двух элементов", range); 
   
   auto theCopy = range.save; 
   report("Копия", theCopy);
   
   range.popFrontN(3); 
   report("После удаления еще трех элементов", range); 
   report("Копия", theCopy); 
}

Продолжу свою нудятину:
Многие функции, работающие с диапазонами и несколько готовых диапазонов определены в модуле стандартной библиотеки std.range.

Функция take определена в модуле std.range, она принимает в качестве параметров диапазон и целое число, и выдаёт диапазон с соответствующим количеством элементов исходного диапазона.

Функция popFrontN определена в модуле std.range.primitives, она принимает в качестве параметров диапазон и целое число, и вызывает у диапазона соответствующее количество раз метод popFront(). В диапазонной терминологии это называется "продвинуться" (advances) по диапазону.

Вызов обеих этих функций происходит с помощью так называемой "нотации псевдочленов" языка D (в английских источниках это называется UFCS, Uniform Function Call Syntax)), т.е. если компилятор встречает запись a.fun(b, c) , а у объекта a нет метода fun, то компилятор попробует применить функцию fun с первым аргументом a: fun(a, b, c).

– прим. пер.

Когда вы скомпилируете и выполните эту программу, она возвратит следующий результат:

Исходный диапазон: [0, 1, 1, 2, 3]
После удаления двух элементов: [1, 2, 3, 5, 8]
Копия: [1, 2, 3, 5, 8]
После удаления еще трех элементов: [5, 8, 13, 21, 34]
Копия: [1, 2, 3, 5, 8]

Двунаправленный диапазон

Двунаправленный диапазон предоставляет два метода дополнительно к методам Лидирующего диапазона. Функция back, аналогичная front, обеспечивает доступ к последнему элементу диапазона. Функция popBack аналогична функции popFront и удаляет последний элемент из диапазона.

Пример

import std.array; 
import std.stdio; 
import std.string; 

struct Reversed { 
   int[] range; 
   
   this(int[] range) { 
      this.range = range; 
   } 
   @property bool empty() const { 
      return range.empty; 
   }
   @property int front() const { 
      return range.back;  //  наоборот 
   }
   @property int back() const { 
      return range.front; // наоборот 
   } 
   void popFront() { 
      range.popBack(); 
   }
   void popBack() { 
      range.popFront(); 
   } 
} 
 
void main() { 
   writeln(Reversed([ 1, 2, 3])); 
}

И тут, похоже, нужны пояснения:

Модуль стандартной библиотеки std.range.primitives объявляет функции двунаправленного диапазона (save, empty, popFront, popBack, front, back) для встроенных массивов. Модуль std.array их публично импортирует. Поэтому импортирования любого из этих модулей достаточно, чтобы массивы стали полноценными двунаправленными диапазонами.

– прим. пер.

Когда вы скомпилируете и выполните эту программу, она возвратит следующий результат:

[3, 2, 1]

Бесконечный диапазон с произвольным доступом

Дополнительно к методам Лидирующего диапазона требуется метод opIndex(). Кроме того, во время компиляции должно быть известно, что значение функции empty всегда false. Простой пример, показывающий диапазон квадратов чисел показан ниже.

import std.array; 
import std.stdio; 
import std.string; 
import std.range; 
import std.algorithm; 

class SquaresRange { 
   int first;  
   this(int first = 0) { 
      this.first = first; 
   }
   enum empty = false; 
   @property int front() const { 
      return opIndex(0); 
   }
   void popFront() { 
      ++first; 
   }
   @property SquaresRange save() const { 
      return new SquaresRange(first); 
   }
   int opIndex(size_t index) const { 
      /* Эта функция отрабатывает за постоянное время */ 
      immutable integerValue = first + cast(int)index; 
      return integerValue * integerValue; 
   } 
}
  
bool are_lastTwoDigitsSame(int value) { // Функция, возвращающая true, если последние две цифры одинаковы
   /* Должен иметь как минимум две цифры */ 
   if (value < 10) { 
      return false; 
   } 
   
   /* Число из последних двух цифр должно делиться на 11 */ 
   immutable lastTwoDigits = value % 100; 
   return (lastTwoDigits % 11) == 0; 
} 
 
void main() { 
   auto squares = new SquaresRange(); 
   
   writeln(squares[5]);
   
   writeln(squares[10]); 
   
   squares.popFrontN(5); 
   writeln(squares[0]); 
   
   writeln(squares.take(50).filter!are_lastTwoDigitsSame); 
}

Придётся продолжать:

Функция filter объявлена в модуле стандартной библиотеки std.algorithm.iteration и публично импортируется модулем std.algorithm. Она принимает диапазон и функцию-предикат (в нашем случае функцию are_lastTwoDigitsSame), и выдаёт на выходе новый диапазон с теми элементами исходного диапазона, для которых предикат возвращает true.

– прим. пер.

Когда вы скомпилируете и выполните эту программу, она возвратит следующий результат:

25 
100 
25 
[100, 144, 400, 900, 1444, 1600, 2500]

Конечный диапазон с произвольным доступом

opIndex() и length требуются дополнительно к функциям двунаправленного диапазона. Это объясняется с помощью подробного примера, в котором используется последовательность Фибоначчи и пример с диапазоном квадратов, использованные ранее. Этот пример хорошо работает на обычном D-компиляторе, но не работает в онлайн-компиляторе.

Пример

import std.array; 
import std.stdio; 
import std.string; 
import std.range; 
import std.algorithm; 

struct FibonacciSeries { 
   int first = 0; 
   int second = 1; 
   enum empty = false;   //  бесконечный диапазон  
   
   @property int front() const { 
      return first;
   }
   void popFront() { 
      int third = first + second; 
      first = second; 
      second = third; 
   }
   @property FibonacciSeries save() const { 
      return this; 
   } 
}
  
void report(T)(const dchar[] title, const ref T range) { 
   writefln("%40s: %s", title, range.take(5)); 
}
  
class SquaresRange { 
   int first;  
   this(int first = 0) { 
      this.first = first; 
   } 
   enum empty = false; 
   @property int front() const { 
      return opIndex(0); 
   }
   void popFront() { 
      ++first; 
   }
   @property SquaresRange save() const { 
      return new SquaresRange(first); 
   } 
   int opIndex(size_t index) const { 
      /* Эта функция отрабатывает за постоянное время */ 
      immutable integerValue = first + cast(int)index; 
      return integerValue * integerValue; 
   } 
}
  

struct Together { 
   const(int)[][] slices;  
   this(const(int)[][] slices ...) { 
      this.slices = slices.dup;  
      clearFront(); 
      clearBack(); 
   }
   private void clearFront() { 
      while (!slices.empty && slices.front.empty) { 
         slices.popFront(); 
      } 
   } 
   private void clearBack() { 
      while (!slices.empty && slices.back.empty) { 
         slices.popBack(); 
      } 
   }
   @property bool empty() const { 
      return slices.empty; 
   } 
   @property int front() const { 
      return slices.front.front; 
   }
   void popFront() { 
      slices.front.popFront(); 
      clearFront(); 
   }
   @property Together save() const { 
      return Together(slices.dup); 
   } 
   @property int back() const { 
      return slices.back.back; 
   } 
   void popBack() { 
      slices.back.popBack(); 
      clearBack(); 
   }
   @property size_t length() const { 
      return reduce!((a, b) => a + b.length)(size_t.init, slices); 
   }
   int opIndex(size_t index) const { 
      /* Сохранить индекс для сообщения об ошибке */ 
      immutable originalIndex = index;  

      foreach (slice; slices) { 
         if (slice.length > index) { 
            return slice[index];  
         } else { 
            index -= slice.length; 
         } 
      } 
      throw new Exception( 
         format("Invalid index: %s (length: %s)", originalIndex, this.length));
   } 
}
void main() { 
   auto range = Together(FibonacciSeries().take(10).array, [ 777, 888 ],
      (new SquaresRange()).take(5).array); 
   writeln(range.save); 
}

Когда вы скомпилируете и выполните эту программу, она возвратит следующий результат:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 777, 888, 0, 1, 4, 9, 16]

Выходной диапазон

Выходной диапазон представляет выходной поток элементов, аналогичный отправке символов в stdout. OutputRange требует поддержки операции put(range, element). put() – это функция, определённая в модуле std.range. Она определяет возможности диапазона и элемента во время компиляции и использует наиболее подходящий метод для вывода элементов. Ниже приведен простой пример.

import std.algorithm; 
import std.stdio; 
 
struct MultiFile { 
   string delimiter;
   File[] files;
   
   this(string delimiter, string[] fileNames ...) { 
      this.delimiter = delimiter; 

      /* stdout всегда включен */ 
      this.files ~= stdout; 

      /* Файловый объект для каждого имени файла */ 
      foreach (fileName; fileNames) { 
         this.files ~= File(fileName, "w"); 
      } 
   }
   void put(T)(T element) { 
      foreach (file; files) { 
         file.write(element, delimiter); 
      } 
   }
}
void main() { 
   auto output = MultiFile("\n", "output_0", "output_1"); 
   copy([ 1, 2, 3], output);  
   copy([ "красный", "синий", "зелёный" ], output); 
}

Когда вы скомпилируете и выполните эту программу, она возвратит следующий результат:

[1, 2, 3]
["красный", "синий", "зелёный"]

Предыдущая страница

Следующая страница