D - Ranges

Ranges are an abstraction of element access. This abstraction enables the use of great number of algorithms over great number of container types. Ranges emphasize how container elements are accessed, as opposed to how the containers are implemented. Ranges are a very simple concept that is based on whether a type defines certain sets of member functions.

Ranges are an integral part of D. D's slices happen to be implementations of the most powerful range RandomAccessRange, and there are many range features in Phobos.Many Phobos algorithms return temporary range objects. For example filter(), which chooses elements that are greater than 10 in the following code, actually returns a range object, not an array:

Number ranges

Number ranges are quite commonly used and these number ranges is of type int. A few examples for number ranges is shown below

// Example 1
foreach (value; 3..7) 
// Example 2
int[] slice = array[5..10]; 

Phobos ranges

Ranges related to structs and class interfaces is phobos ranges. Phobos is the official runtime and standard library that comes with the D language compiler.
There are various types of ranges which include,

• InputRange
• ForwardRange
• BidirectionalRange
• RandomAccessRange
• OutputRange

InputRange

The simplest range is the input range. The other ranges bring more requirements on top of the range that they are based on. There are three functions that InputRange requires,

• empty: specifies whether the range is empty; it must return true when the range is considered to be empty, and false otherwise
• front: provides access to the element at the beginning of the range
• popFront(): shortens the range from the beginning by removing the first element

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("Raj", 1), Student("John", 2) , Student("Ram", 3) ] );

   auto range = StudentRange(school);
   writeln(range);

   writeln(school.students.length);

   writeln(range.front);

   range.popFront;

   writeln(range.empty);
   writeln(range);
}

When the above code is compiled and executed, it produces the following result:

[Raj(1), John(2), Ram(3)]
3
Raj(1)
false
[John(2), Ram(3)]

ForwardRange

ForwardRange additionally requires the save member function part from the other three function of InputRange and return a copy of the range when the save function is called.

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

struct FibonacciSeries
{
   int first = 0;
   int second = 1;
   enum empty = false;   //  infinite range

   @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("Original range", range);

   range.popFrontN(2);
   report("After removing two elements", range);

   auto theCopy = range.save;
   report("The copy", theCopy);

   range.popFrontN(3);
   report("After removing three more elements", range);
   report("The copy", theCopy);
}

When the above code is compiled and executed, it produces the following result:

Original range: [0, 1, 1, 2, 3]
After removing two elements: [1, 2, 3, 5, 8]
The copy: [1, 2, 3, 5, 8]
After removing three more elements: [5, 8, 13, 21, 34]
The copy: [1, 2, 3, 5, 8]

BidirectionalRange

BidirectionalRange additionaly provides two member functions over the member functions of ForwardRange. back function which is similar to front, provides access to the last element of the range. popBack functiom is similar to popFront funtion and it removes the last element from the range.

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

   @property int back() const
   {
      return range.front; // reverse
   }

   void popFront()
   {
      range.popBack();
   }

   void popBack()
   {
      range.popFront();
   }
}

void main()
{
   writeln(Reversed([ 1, 2, 3]));
}

When the above code is compiled and executed, it produces the following result:

[3, 2, 1]

Infinite RandomAccessRange

opIndex() is additionaly required when compared to the ForwardRange. Also the value of empty function to be known at compile time as false. A simple example is explained with squares range is shown below.

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
   {
       /* This function operates at constant time */
      immutable integerValue = first + cast(int)index;
      return integerValue * integerValue;
   }
}

bool are_lastTwoDigitsSame(int value)
{
   /* Must have at least two digits */
   if (value < 10) {
      return false;
   }

   /* Last two digits must be divisible by 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);
}

When the above code is compiled and executed, it produces the following result:

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

Finite RandomAccessRange

opIndex() and length are additionaly required when compared to bidirectional range. This is explained with the help of detailed example that uses the Fibonacci series and Squares Range example used earlier. This example works well on normal D compiler but won't work on online compiler.

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;   //  infinite range

   @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
   {
       /* This function operates at constant time */
      immutable integerValue = first + cast(int)index;
      return integerValue * integerValue;
   }

}

bool are_lastTwoDigitsSame(int value)
{
   /* Must have at least two digits */
   if (value < 10) {
      return false;
   }

   /* Last two digits must be divisible by 11 */
   immutable lastTwoDigits = value % 100;
   return (lastTwoDigits % 11) == 0;
}

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
   {
      /* Save the index for the error message */
      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);
}

When the above code is compiled and executed, it produces the following result:

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

OutputRange

OutputRange represents streamed element output, similar to sending characters to stdout. OutputRange requires support for the put(range, element) operation. put() is a function defined in the std.range module. It determines the capabilities of the range and the element at compile time and uses the most appropriate method to use to output the elements. A simple example is shown below.

import std.algorithm;
import std.stdio;

struct MultiFile
{
   string delimiter;

   File[] files;
   this(string delimiter, string[] fileNames ...)
   {
      this.delimiter = delimiter;
      /* stdout is always included */
      this.files ~= stdout;
      /* A File object for each file name */
      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([ "red", "blue", "green" ], output);
}

When the above code is compiled and executed, it produces the following result:

[1, 2, 3]
["red", "blue", "green"]