A forward range. Allows you to read the first element from the range or skip it. The forward range lays the foundation for IBRange<T> and IRange<T>. More...

Source file:

/Core/Loyc.Interfaces/Collections/IRanges.cs

Inheritance diagram for Loyc.Collections.IFRange< out out T >:

Remarks

A forward range. Allows you to read the first element from the range or skip it. The forward range lays the foundation for IBRange<T> and IRange<T>.

Ranges are a concept I first saw formalized in the D programming language. They are generally more useful than .NET enumerators because there are more kinds of them:

A forward range (IFRange<T>) is a sequence of values accessed starting with the first, like IEnumerator<T>. A forward range is like IEnumerator, except that it can be cloned, so you can restart from the same place later. This is more powerful than IEnumerable<T>, which can only restart from the beginning.
A bidirectional range inherits from the forward range, and provides access to the back of the sequence as well as the front. A bidirectional iterators may, for example, represent a linked list, or a UTF-8 string that provides access to the first and last 32-bit code point (note that random access by character index is not really possible in UTF-8 data, since the size of N characters is unknown).
A random-access range is a sequence that provides array-like access to a section of a list. A section of a list is called a "slice".

A range is read-only by default, but has a writable variant marked with the letter M, meaning "Mutable": IMFRange<T>, IMBRange<T>, IMRange<T>.

It is fair to ask why IFRange exists–since it behaves like an enumerator, why not simply use IEnumerator directly? Well, this interface serves as the base interface for the other ranges, so its interface needs to make sense in that context. IEnumerator has "Current" and "MoveNext" methods, but in a bidirectional or random-access range, there is no single "Current" or "Next" item.

Also, when used through an interface, IFRange is potentially more efficient than IEnumerator: you only need to call a single method, PopFirst(), to get the next item, unlike IEnumerator which requires two interface calls per iteration. That can improve performance, since interface calls cannot be inlined. It is a bit inconvenient to use PopFirst(out bool) because of its "out" argument, and more convenient extension methods would have been provided if C# supported "ref Type this", which would be needed since ranges are often value types.

Ranges are useful for implementing algorithms; they are comparable to the concept of "iterators" in C++, except that a range represents a pair of iterators instead of a single iterator. And like C++ iterators, they are a useful starting point for writing generic algorithms.

When using a range that is not typed IFRange<T>, you need to be careful how you use it because the range could be a struct type. Much like an enumerator, a range is often a small wrapper around a larger data structure; therefore, it often makes sense to implement a range as a struct. When a range is a struct, normally you are making a copy of it whenever you assign it to a different variable, or pass it to another method:

Range b = a;

a.PopFirst(); // may not affect b if Range is a struct

In fact, a range should not be copied this way because assignment may or may not create a copy. You should avoid simple assignment, and use Clone() to copy a range instead:

Range b = a.Clone();

a.PopFirst(); // will not affect b, and you can be sure of it

However, if a range is a reference type or a reference to IFRange, you are not making a copy of it when you assign it or pass it to another method:

IFRange<T> a = ...;
IFRange<T> b = a;
a.PopFirst(); // The item was popped from b also

When writing generic code, you may want to use range types directly, as in:

void DoSomethingWithRange<R,T>(R range) where R : IRange<T> {...}

Using a range type directly can improve performance if R happens to be a struct type, since there is no need to box the range when passing it to this method. However, it is very important to keep in mind that "R" may be a struct or a class. If this method is not intended to modify the range from the perspective of the caller, the method must start by cloning the range, in case R is a class or interface type:

void DoSomethingWithRange<R,T>(R range) where R : IBRange<T> {
    range = range.Clone();
    ...
}

On the other hand, if this method wants the caller to see the changes to the range, R must be passed by reference, in case it is a struct type:

void DoSomethingWithRange<R,T>(ref R range) where R : IBRange<T> {
    ...
}

To avoid these subtle difficulties, you can access the range through the IFRange<T> interface; just remember to Clone() the range when necessary.

Remember that a range is an alias for some underlying data structure. If the original data structure is modified, a range will "see" those changes. For instance, suppose that a range provides a slice from indexes 5 to 12 inclusive within an IList<T> object that contains 15 items:

    IList  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 
           a  b  c  d  e  f  g  h  i  j  k  l  m  n  o 
    IRange                0  1  2  3  4  5  6  7

Thus, [0] in the range corresponds to item [5] in the list, "f". Now, if the first three items in the list are removed, then [0] in the range will still correspond to item [5] in the list, but the item at this location, marked "i", used to be at index [8]:

    IList  0  1  2  3  4  5  6  7  8  9 10 11
           d  e  f  g  h  i  j  k  l  m  n  o
    IRange                0  1  2  3  4  5  6  7

The exact behavior of the range at this point is implementation-dependent. The Count property may remain at 8, or it may drop to 7; perhaps the range will return default(T) when you read index [7], or perhaps it will throw IndexOutOfRangeException. Because of this lack of predictability, you should avoid keeping a range that points to a list whose size is decreasing. If individual elements are modified but not the list size, the range is safe to use and will see the changes. If new elements are added to the end of the list, the range may or may not continue working as expected, depending on how the collection works and how the range works. In most cases the range will be unaffected, in contrast to common C++ containers such as std::vector, in which iterators are "invalidated" by any size change, and when an invalid iterator is accessed, it may return bad data or crash the program.

Currently there are no interfaces in Loyc.Essentials that return forward or bidirectional ranges; the only notable method that returns a range is IListSource<T>.Slice, which returns a random-access range. Since a random-access range is also a bidirectional range, you can begin writing algorithms that accept forward and bidirectional ranges (for read access). Any collection that implements IListSource<T> can be treated as a range using the ListExt.AsRange<T>(IListSource<T>) extension method, which is like calling Slice(0).

The design philosophy of Loyc.Essentials is that potentially useful interfaces should be included even if there are no implementations of the interface. That's why there are interfaces like IMFRange<T> that are not implemented by any classes. Why offer unused interfaces? Because this library is designed to be extended by third parties, who might want to implement the interface, e.g. if someone else creates mutable data structures such as the B+ tree, the doubly-linked list or the trie, they should offer implementations of IMBRange<T> and/or IMBinumerator<T>.

Implementors note: IFRange<T> includes IEnumerable<T>, and you can use the following implementation of IEnumerable provided that your range type R implements ICloneable<R>:

IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
IEnumerator<T> IEnumerable<T>.GetEnumerator() { return GetEnumerator(); }
public RangeEnumerator<R,T> GetEnumerator()
{
    return new RangeEnumerator<R,T>(this);
}

TODO: write RangeBinumerator for IBRange{T}, RangeMBinumerator for IMBRange{T}, and RangeMEnumerator for IMEnumerator{T}.

Properties
T	First `[get]`
	Returns the first value in the range, without popping it. More...

Properties inherited from Loyc.Collections.IIsEmpty
bool	IsEmpty `[get]`

Public Member Functions
T	PopFirst (out bool fail)
	Removes the first item from the range and returns it. More...

Member Function Documentation

◆ PopFirst()

T Loyc.Collections.IFRange< out out T >.PopFirst ( out bool fail )

Removes the first item from the range and returns it.

Parameters

fail	Receives the current value of IIsEmpty.IsEmpty.

Returns: The first item of the range, or default(T) if IsEmpty.

This method is a little unweildy in plain C#, but in EC# it will be a bit more convenient to use via extension methods like T PopFirst(ref this Range range, T defaultValue) and T? PopFirst(ref this Range range), which are illegal in plain C#.

I wanted to give this method the signature "bool PopFirst(out T first)" but the generic parameter "T" is covariant, i.e. it is marked "out T" which, ironically, is not compatible with "out T" parameters, only with return values.

Referenced by Loyc.Collections.RangeExt.Skip< R, T >().

Property Documentation

◆ First

T Loyc.Collections.IFRange< out out T >.First

get

Returns the first value in the range, without popping it.

Exceptions

EmptySequenceException The sequence is empty.

A possible default implementation:

T First { get { return Range.PopFirst(Clone()); } }

Remarks

Properties

Public Member Functions

Member Function Documentation

◆ PopFirst()

Property Documentation

◆ First