Enhanced C#
Language of your choice: library documentation

Documentation moved to ecsharp.net

GitHub doesn't support HTTP redirects, so you'll be redirected in 3 seconds.

 All Classes Namespaces Functions Variables Enumerations Enumerator Properties Events Pages
Nested classes | Public static fields | Properties | Public Member Functions | Static Public Member Functions | List of all members
Loyc.Collections.VList< T > Struct Template Reference

VList represents a reference to a reverse-order FVList. More...


Source file:
Inheritance diagram for Loyc.Collections.VList< T >:
Loyc.Collections.IListAndListSource< T > Loyc.ICloneable< out T > Loyc.Collections.IListSource< out T > Loyc.Collections.ICollectionAndReadOnly< T > Loyc.Collections.VList< T >.Enumerator

Remarks

VList represents a reference to a reverse-order FVList.

An article is available online about the VList data types.

The VList is a persistent list data structure described in Phil Bagwell's 2002 paper "Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays". Originally, this type was called RVList because it works in the reverse order to the original VList type: new items are normally added at the beginning of a VList, which is normal in functional languages, but this VList acts like a normal .NET list, so it is optimized for new items to be added at the end. The name "RVList" is ugly, though, since it misleadingly appears to be related to Recreational Vehicles. So as of LeMP 1.5, it's called simply VList.

In contrast, the FVList{T} type acts like the original VList; its Add method puts new items at the beginning (index 0).

See the remarks of VListBlock{T} for a more detailed description.

Nested classes

struct  Enumerator
 Enumerates through a VList from index 0 up to index Count-1. More...
 

Public static fields

static readonly VList< T > Empty = new VList<T>()
 

Properties

VList< T > Tail [get]
 Returns a list without the last item. If the list is empty, an empty list is retured. More...
 
Last [get]
 Returns the last item of the list (at index Count-1), which is the head of the list. More...
 
bool IsEmpty [get]
 
int BlockChainLength [get]
 Gets the number of blocks used by this list. More...
 
this[int index] [get, set]
 
this[int index, T defaultValue] [get]
 Gets an item from the list at the specified index; returns defaultValue if the index is not valid. More...
 
int Count [get]
 
bool IsReadOnly [get]
 

Public Member Functions

 VList (T firstItem)
 
 VList (T itemZero, T itemOne)
 
 VList (T[] array)
 
 VList (IEnumerable< T > list)
 
 VList (VList< T > list)
 
VList< T > WithoutLast (int offset)
 
VList< T > NextIn (VList< T > largerList)
 
VList< T > First (int count)
 
override bool Equals (object rhs_)
 Returns whether the two list references are the same. Does not compare the contents of the lists. More...
 
override int GetHashCode ()
 
VList< T > AddRange (VList< T > list)
 
VList< T > AddRange (VList< T > list, VList< T > excludeSubList)
 
VList< T > AddRange (IList< T > list)
 
VList< T > AddRange (IEnumerable< T > list)
 
VList< T > InsertRange (int index, IList< T > list)
 
VList< T > RemoveRange (int index, int count)
 
Pop ()
 Removes the last item (at index Count-1) from the list and returns it. More...
 
VList< T > Push (T item)
 Synonym for Add(); adds an item to the front of the list. More...
 
FVList< T > ToFVList ()
 Returns this list as a FVList, which effectively reverses the order of the elements. More...
 
FWList< T > ToFWList ()
 Returns this list as a FWList, which effectively reverses the order of the elements. More...
 
WList< T > ToWList ()
 Returns this list as an WList. More...
 
T[] ToArray ()
 Returns the VList converted to an array. More...
 
int IndexOf (T item)
 Searches for the specified object and returns the zero-based index of the first occurrence (lowest index) within the entire VList. More...
 
void IList< T >. Insert (int index, T item)
 
VList< T > Insert (int index, T item)
 
void IList< T >. RemoveAt (int index)
 
VList< T > RemoveAt (int index)
 
void ICollection< T >. Add (T item)
 Inserts an item at the back (index Count) of the VList. More...
 
VList< T > Add (T item)
 Inserts an item at the back (index Count) of the VList. More...
 
void ICollection< T >. Clear ()
 
VList< T > Clear ()
 
bool Contains (T item)
 
void CopyTo (T[] array, int arrayIndex)
 
bool Remove (T item)
 
Enumerator GetEnumerator ()
 
IEnumerator< T > IEnumerable< T >. GetEnumerator ()
 
System.Collections.IEnumerator
System.Collections.IEnumerable. 
GetEnumerator ()
 
TryGet (int index, out bool fail)
 Gets the item at the specified index, and does not throw an exception on failure. More...
 
IRange< T > IListSource< T >. Slice (int start, int count)
 Returns a sub-range of this list. More...
 
Slice_< T > Slice (int start, int count=int.MaxValue)
 Returns a sub-range of this list. More...
 
VList< T > Clone ()
 
object ICloneable. Clone ()
 
VList< T > Where (Predicate< T > keep)
 Applies a filter to a list, to exclude zero or more items. More...
 
VList< T > WhereSelect (Func< T, Maybe< T >> filter)
 Filters and maps a list with a user-defined function. More...
 
VList< T > SmartSelect (Func< T, T > map)
 Maps a list to another list of the same length. More...
 
VList< Out > Select< Out > (Func< T, Out > map)
 Maps a list to another list of the same length. More...
 
VList< T > Transform (VListTransformer< T > x)
 Transforms a list (combines filtering with selection and more). More...
 

Static Public Member Functions

static bool operator== (VList< T > lhs, VList< T > rhs)
 Returns whether the two list references are the same. Does not compare the contents of the lists. More...
 
static bool operator!= (VList< T > lhs, VList< T > rhs)
 Returns whether the two list references are different. Does not compare the contents of the lists. More...
 
static operator FVList< T > (VList< T > list)
 Returns this list as a FVList, which effectively reverses the order of the elements. More...
 
static operator FWList< T > (VList< T > list)
 Returns this list as a FWList, which effectively reverses the order of the elements. More...
 
static operator WList< T > (VList< T > list)
 Returns this list as an WList. More...
 

Member Function Documentation

void ICollection<T>. Loyc.Collections.VList< T >.Add ( item)
inline

Inserts an item at the back (index Count) of the VList.

References Loyc.Collections.VList< T >.Add().

Referenced by Loyc.Collections.VList< T >.Add().

VList<T> Loyc.Collections.VList< T >.Add ( item)
inline

Inserts an item at the back (index Count) of the VList.

override bool Loyc.Collections.VList< T >.Equals ( object  rhs_)
inline

Returns whether the two list references are the same. Does not compare the contents of the lists.

int Loyc.Collections.VList< T >.IndexOf ( item)
inline

Searches for the specified object and returns the zero-based index of the first occurrence (lowest index) within the entire VList.

Parameters
itemItem to locate (can be null if T can be null)
Returns
Index of the item, or -1 if it was not found.

This method determines equality using the default equality comparer EqualityComparer.Default for T, the type of values in the list.

This method performs a linear search, and is typically an O(n) operation, where n is Count. However, because the list is searched upward from index 0 to Count-1, if the list's blocks do not increase in size exponentially (due to the way that the list has been modified in the past), the search can have worse performance; the (unlikely) worst case is O(n^2). FVList(of T).IndexOf() doesn't have this problem.

static Loyc.Collections.VList< T >.operator FVList< T > ( VList< T >  list)
inlineexplicitstatic

Returns this list as a FVList, which effectively reverses the order of the elements.

This is a trivial operation; the FVList shares the same memory.

static Loyc.Collections.VList< T >.operator FWList< T > ( VList< T >  list)
inlineexplicitstatic

Returns this list as a FWList, which effectively reverses the order of the elements.

The list contents are not copied until you modify the FWList.

static Loyc.Collections.VList< T >.operator WList< T > ( VList< T >  list)
inlineexplicitstatic

Returns this list as an WList.

The list contents are not copied until you modify the WList.

static bool Loyc.Collections.VList< T >.operator!= ( VList< T >  lhs,
VList< T >  rhs 
)
inlinestatic

Returns whether the two list references are different. Does not compare the contents of the lists.

static bool Loyc.Collections.VList< T >.operator== ( VList< T >  lhs,
VList< T >  rhs 
)
inlinestatic

Returns whether the two list references are the same. Does not compare the contents of the lists.

T Loyc.Collections.VList< T >.Pop ( )
inline

Removes the last item (at index Count-1) from the list and returns it.

VList<T> Loyc.Collections.VList< T >.Push ( item)
inline

Synonym for Add(); adds an item to the front of the list.

References Loyc.Collections.Add.

VList<Out> Loyc.Collections.VList< T >.Select< Out > ( Func< T, Out >  map)
inline

Maps a list to another list of the same length.

Parameters
mapA function that transforms each item in the list.
Returns
The list after the map function is applied to each item. The original VList structure is not modified.
IRange<T> IListSource<T>. Loyc.Collections.VList< T >.Slice ( int  start,
int  count 
)
inline

Returns a sub-range of this list.

Parameters
startThe new range will start at this index in the current list (this location will be index [0] in the new range).
countThe desired number of elements in the new range, or int.MaxValue to get all elements until the end of the list.
Returns
Returns a sub-range of this range.
Exceptions
ArgumentExceptionThe start index was below zero.

The (start, count) range is allowed to be invalid, as long as start is zero or above.

  • If count is below zero, or if start is above the original Count, the Count of the new slice is set to zero.
  • if (start + count) is above the original Count, the Count of the new slice is reduced to this.Count - start. Implementation note: do not compute (start + count) because it may overflow. Instead, test whether (count > this.Count - start).

Most collections should use the following implementation:

IRange<T> IListSource<T>.Slice(int start, int count) { return Slice(start, count); }
public Slice_<T> Slice(int start, int count) { return new Slice_<T>(this, start, count); }

Implements Loyc.Collections.IListSource< out T >.

References Loyc.Collections.VList< T >.Slice().

Referenced by Loyc.Collections.VList< T >.Slice().

Slice_<T> Loyc.Collections.VList< T >.Slice ( int  start,
int  count = int.MaxValue 
)
inline

Returns a sub-range of this list.

Parameters
startThe new range will start at this index in the current list (this location will be index [0] in the new range).
countThe desired number of elements in the new range, or int.MaxValue to get all elements until the end of the list.
Returns
Returns a sub-range of this range.
Exceptions
ArgumentExceptionThe start index was below zero.

The (start, count) range is allowed to be invalid, as long as start is zero or above.

  • If count is below zero, or if start is above the original Count, the Count of the new slice is set to zero.
  • if (start + count) is above the original Count, the Count of the new slice is reduced to this.Count - start. Implementation note: do not compute (start + count) because it may overflow. Instead, test whether (count > this.Count - start).

Most collections should use the following implementation:

IRange<T> IListSource<T>.Slice(int start, int count) { return Slice(start, count); }
public Slice_<T> Slice(int start, int count) { return new Slice_<T>(this, start, count); }

Implements Loyc.Collections.IListSource< out T >.

VList<T> Loyc.Collections.VList< T >.SmartSelect ( Func< T, T >  map)
inline

Maps a list to another list of the same length.

Parameters
mapA function that transforms each item in the list.
Returns
The list after the map function is applied to each item. The original VList structure is not modified.

This method is called "Smart" because of what happens if the map doesn't do anything. If the map function returns the first N items unmodified, those N items are typically not copied, but shared between the existing list and the new one. This is useful for functional code that sometimes processes a list without modifying it at all.

T [] Loyc.Collections.VList< T >.ToArray ( )
inline

Returns the VList converted to an array.

FVList<T> Loyc.Collections.VList< T >.ToFVList ( )
inline

Returns this list as a FVList, which effectively reverses the order of the elements.

Returns
This is a trivial operation; the FVList shares the same memory.
FWList<T> Loyc.Collections.VList< T >.ToFWList ( )
inline

Returns this list as a FWList, which effectively reverses the order of the elements.

The list contents are not copied until you modify the FWList.

WList<T> Loyc.Collections.VList< T >.ToWList ( )
inline

Returns this list as an WList.

The list contents are not copied until you modify the WList.

VList<T> Loyc.Collections.VList< T >.Transform ( VListTransformer< T >  x)
inline

Transforms a list (combines filtering with selection and more).

Parameters
xMethod to apply to each item in the list
Returns
A list formed from transforming all items in the list

See the documentation of FVList.Transform() for more information.

T Loyc.Collections.VList< T >.TryGet ( int  index,
out bool  fail 
)
inline

Gets the item at the specified index, and does not throw an exception on failure.

Parameters
indexAn index in the range 0 to Count-1.
failA flag that is set on failure.
Returns
The element at the specified index, or default(T) if the index is not valid.

In my original design, the caller could provide a value to return on failure, but this would not allow T to be marked as "out" in C# 4. For the same reason, we cannot have a ref/out T parameter. Instead, the following extension methods are provided:

bool TryGet(int index, ref T value);
T TryGet(int, T defaultValue);

Implements Loyc.Collections.IListSource< out T >.

VList<T> Loyc.Collections.VList< T >.Where ( Predicate< T >  keep)
inline

Applies a filter to a list, to exclude zero or more items.

Parameters
keepA function that chooses which items to include (exclude items by returning false).
Returns
The list after filtering has been applied. The original list structure is not modified.

If the predicate keeps the first N items it is passed, those N items are typically not copied, but shared between the existing list and the new one.

VList<T> Loyc.Collections.VList< T >.WhereSelect ( Func< T, Maybe< T >>  filter)
inline

Filters and maps a list with a user-defined function.

Parameters
filterA function that chooses which items to include in a new list, and what to change them to.
Returns
The list after filtering has been applied. The original list structure is not modified.

This is a smart function. If the filter does not modify the first N items it is passed, those N items are typically not copied, but shared between the existing list and the new one.

Property Documentation

int Loyc.Collections.VList< T >.BlockChainLength
get

Gets the number of blocks used by this list.

You might look at this property when optimizing your program, because the runtime of some operations increases as the chain length increases. This property runs in O(BlockChainLength) time. Ideally, BlockChainLength is proportional to log_2(Count), but certain VList usage patterns can produce long chains.

T Loyc.Collections.VList< T >.Last
get

Returns the last item of the list (at index Count-1), which is the head of the list.

VList<T> Loyc.Collections.VList< T >.Tail
get

Returns a list without the last item. If the list is empty, an empty list is retured.

T Loyc.Collections.VList< T >.this[int index, T defaultValue]
get

Gets an item from the list at the specified index; returns defaultValue if the index is not valid.