An immutable, thread-safe, singly-linked list.
- T
- The type of the value to store in the sequence.
This type is thread safe.
CachedSequence<T> is useful for caching the current values within a IEnumerable<T> which come from a generator that will generate different values from each invocation. Consider the following generator:
C# Example internal static IEnumerable<int> RandomValues (Random r, int max) { while (true) yield return r.Next (max); }The above generator does two things: it generates an infinite sequence, and each time IEnumerable<T>.GetEnumerator is called on the IEnumerable<T> that RandomValues() returns, it may return a different sequence:
Example var r = new Random(); // prints e.g.: 6, 2, 8 foreach (var v in RandomValues (r, 10).Take(3)) Console.WriteLine (v); // prints e.g.: 1, 4, 3 foreach (var v in RandomValues (r, 10).Take(3)) Console.WriteLine (v);This is potentially fine if you're aware of the problem, but it can potentially break some algorithms if the generator is referenced multiple times (under the assumption that the sequence won't change):
C# Example var randSeq = RandomValues (new Random (), 100); // this could pass, but that's highly improbable Assert.IsFalse ( randSeq.Take (10).SelectFromEach (randSeq.Take (10), (l, r) => l + r) .All (x => x % 2 == 0));The above algorithm attempts to say: give me two sets of 10 random numbers, add them together, and assert that the results are always even (as any number added to itself will be even). This algorithm fails because the generator returns a different sequence on the second randSeq.Take(10) call.
A fix is to "memoize" the sequence. CachedSequence<T> will record the input sequence, so that subsequent iterations will return the same values as the first iteration. This allows the same algorithm to work:
C# Example var values = new Random (); // Note: wrapping an infinite sequence var randSeq = new CachedSequence<int> (EnumerableTest.RandomValues (values, 10)); Assert.IsTrue ( randSeq.Take (20).SelectFromEach (randSeq.Take (10), (l, r) => l + r) .All (x => x % 2 == 0));CachedSequence<T> has two modes of operation: as a "fully realized" singly-linked list constructed one node at a time, and (as seen above) as a caching wrapper over an IEnumerable<T> sequence.
Node at a time construction is performed with the CachedSequence<T>(`0) and CachedSequence<T>(`0, CachedSequence<`0>) constructors. For both, the T parameter then becomes accessible via CachedSequence<T>.Head, while CachedSequence<T>.Tail is either null (for the first constructor) or the specified CachedSequence<T> value. The second constructor thus allows creating sequences of arbitrary length.
When wrapping IEnumerable<T> sequences via the CachedSequence<T>(IEnumerable<`0>) constructor, an alternate mode is used. The sequence is not immediately executed; instead, the sequence is evaluated on-demand when the CachedSequence<T>.Head and CachedSequence<T>.Tail properties are accessed. This allows infinite sequences to be wrapped without requiring infinite memory, as seen above with the random sequence generator.
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
See Also: Inherited members from object.
⊟ Public Constructors
Constructs and initializes a new instance of the Cadenza.Collections.CachedSequence<T> class which wraps the specified collection. CachedSequence (T)Constructs and initializes a new instance of the Cadenza.Collections.CachedSequence<T> class using the specified head. Constructs and initializes a new instance of the Cadenza.Collections.CachedSequence<T> class using the specified head and tail. ⊟ Public Properties
[read-only] Head T . Returns the value held by this instance. [read-only] Tail CachedSequence<T> . Obtains the items in the sequence following the current item, CachedSequence<T>.Head. ⊟ Public Methods
Append (T) : CachedSequence<T> Clones the current sequence with value appended.Count () : int Returns the number of elements in the sequence.ElementAt (int) : T Returns the value at a specified index in the sequence.First () : T Returns CachedSequence<T>.Head.FirstOrDefault () : T Returns CachedSequence<T>.Head.GetEnumerator () : IEnumerator<T> Returns an enumerator that iterates through the linked list.LongCount () : long Returns the number of elements in the sequence.Prepend (T) : CachedSequence<T> Returns a new Cadenza.Collections.CachedSequence<T> with value as the CachedSequence<T>.Head and the current sequence as the CachedSequence<T>.Tail.Reverse () : CachedSequence<T> Reverse the sequence that the current instance is the start of.⊟ Explicitly Implemented Interface Members
IEnumerable.GetEnumerator Returns an enumerator that iterates through the linked list. ⊟ Extension Methods
⊟ CachedSequence Constructor
Constructs and initializes a new instance of the Cadenza.Collections.CachedSequence<T> class which wraps the specified collection.
public CachedSequence (IEnumerable<T> collection)⊟ Parameters
- collection
- A IEnumerable<T> which is the sequence to wrap. collection may refer to an infinite sequence.
⊟ Exceptions
Type Reason ArgumentNullException collection is null. InvalidOperationException collection contains no elements. ⊟ Remarks
This constructor invokes IEnumerable<T>.GetEnumerator on collection to obtain a IEnumerator<T>. This is referred to as the "underlying enumerator". IEnumerator.MoveNext is invoked on the underlying enumerator; if false is returned, then InvalidOperationException is thrown; otherwise, IEnumerator<T>.Current is used to initialize the CachedSequence<T>.Head property.
The value of the CachedSequence<T>.Tail property is determined lazily, depending upon the state of the underlying enumerator.
The underlying enumerator is IDisposable.Disposed when one of two circumstances occurs:
- The sequence has been completely evaluated (causing CachedSequence<T>.Tail to return null). This can't happen with infinite sequences.
- CachedSequence<T>.GetEnumerator is invoked, and the returned enumerator is disposed. This will cause the underlying enumerator to also be disposed.
Note that disposing the underlying enumerator effectively terminates the sequence. Thus, collection is an infinite sequence, if the CachedSequence<T> is enumerated and the enumerator is disposed, the infinite sequence is also disposed, and no additional elements will be accessible.
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ CachedSequence Constructor
Constructs and initializes a new instance of the Cadenza.Collections.CachedSequence<T> class using the specified head.
public CachedSequence (T head)⊟ Parameters
- head
- A T containing the value to hold.
⊟ Remarks
This constructor initializes the CachedSequence<T>.Head property of the new instance using head. The CachedSequence<T>.Tail property of the new sequence will be null.⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ CachedSequence Constructor
Constructs and initializes a new instance of the Cadenza.Collections.CachedSequence<T> class using the specified head and tail.
public CachedSequence (T head, CachedSequence<T> tail)⊟ Parameters
- head
- A T containing the value to hold.
- tail
- A Cadenza.Collections.CachedSequence<T> which is used to initialize the CachedSequence<T>.Tail property of the created instance.
⊟ Remarks
This constructor initializes the CachedSequence<T>.Head property of the new instance using head, and initializes the CachedSequence<T>.Tail property of the new instance using tail.⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ Append Method
Clones the current sequence with value appended.
public CachedSequence<T> Append (T value)⊟ Parameters
- value
- A T containing the value to append to the sequence.
⊟ Returns
A new Cadenza.Collections.CachedSequence<T> which has value as the last value in the sequence.⊟ Remarks
This is an O(n) operation. Do not use when wrapping infinite sequences.
This creates a new, cloned sequence which is identical to the current sequence except that value is the last element in the sequence. This sequence is unchanged.
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ Count Method
Returns the number of elements in the sequence.
public int Count ()⊟ Returns
A int containing the number of elements in the sequence.⊟ Remarks
This is an O(n) operation, and will immediately evaluate the entire sequence. Do not use when wrapping infinite sequences.⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ ElementAt Method
Returns the value at a specified index in the sequence.
public T ElementAt (int index)⊟ Parameters
- index
- An int which is the in
⊟ Returns
A T which is the value at the index index in the sequence.⊟ Exceptions
Type Reason ArgumentOutOfRangeException index is negative or is larger than CachedSequence<T>.LongCount. ⊟ Remarks
This is an O(index) operation.
If this element or a preceding element was constructed via the CachedSequence<T>(IEnumerable<`0>) constructor, then this may evaluate index values.
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ First Method
Returns CachedSequence<T>.Head.
public T First ()⊟ Returns
A T which is the value held by CachedSequence<T>.Head.⊟ Remarks
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ FirstOrDefault Method
Returns CachedSequence<T>.Head.
public T FirstOrDefault ()⊟ Returns
A T which is the value held by CachedSequence<T>.Head.⊟ Remarks
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ GetEnumerator Method
Returns an enumerator that iterates through the linked list.
public IEnumerator<T> GetEnumerator ()⊟ Returns
An IEnumerator<T> that can be used to iterate through the linked list as a collection.⊟ Remarks
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ Head Property
Returns the value held by this instance.
public T Head { get; }⊟ Value
A T which is the value held by this instance.⊟ Remarks
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ LongCount Method
Returns the number of elements in the sequence.
public long LongCount ()⊟ Returns
A long containing the number of elements in the sequence.⊟ Remarks
This is an O(n) operation, and will immediately evaluate the entire sequence. Do not use when wrapping infinite sequences.⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ Prepend Method
Returns a new Cadenza.Collections.CachedSequence<T> with value as the CachedSequence<T>.Head and the current sequence as the CachedSequence<T>.Tail.
public CachedSequence<T> Prepend (T value)⊟ Parameters
- value
- A T value which should be inserted before the current sequence.
⊟ Returns
A new Cadenza.Collections.CachedSequence<T> with value as the CachedSequence<T>.Head and the current sequence as the CachedSequence<T>.Tail.⊟ Remarks
This is an O(1) operation.
This is equivalent to: new CachedSequence<T>(value, this).
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ Reverse Method
Reverse the sequence that the current instance is the start of.
public CachedSequence<T> Reverse ()⊟ Returns
A new Cadenza.Collections.CachedSequence<T> in which CachedSequence<T>.Head is the last value in the returned sequence, CachedSequence<T>.Tail.Head is the second to last value in the returned sequence, etc.⊟ Remarks
This is an O(n) operation.
This immediately evaluates the entire sequence. Do not use when wrapping infinite sequences.
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ System.Collections.IEnumerable.GetEnumerator Method
Returns an enumerator that iterates through the linked list.
IEnumerator System.Collections.IEnumerable.GetEnumerator ()⊟ Returns
An IEnumerator that can be used to iterate through the linked list as a collection.⊟ Remarks
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0
⊟ Tail Property
Obtains the items in the sequence following the current item, CachedSequence<T>.Head.
public CachedSequence<T> Tail { get; }⊟ Value
A Cadenza.Collections.CachedSequence<T> containing the items in the sequence following CachedSequence<T>.Head. If there are no more items, then null is returned.⊟ Remarks
Operation
If this instance was constructed via the CachedSequence<T>(`0) constructor, null is returned.
If this instance was constructed via the CachedSequence<T>(`0, CachedSequence<`0>) constructor, then the tail parameter is returned (which may be null).
If this instance or an instance preceding this instance was constructed via the CachedSequence<T>(IEnumerable<`0>) constructor, then a lock is taken and IEnumerator.MoveNext is invoked on the underlying enumerator. If false is returned from MoveNext(), then null will be returned. Otherwise, a new Cadenza.Collections.CachedSequence<T> will be returned in which CachedSequence<T>.Head will contain the IEnumerator<T>.Current. value and will gain "ownership" of the underlying IEnumerator<T>.
⊟ Requirements
Namespace: Cadenza.Collections
Assembly: Cadenza (in Cadenza.dll)
Assembly Versions: 0.1.0.0