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

Source file:

/Core/Loyc.Collections/VLists/VList.cs

Inheritance diagram for Loyc.Collections.VList< T >:

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...

T	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...

T	this[int index] `[get, set]`

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. More...

int	Count `[get]`

bool	IsReadOnly `[get]`

Properties inherited from Loyc.Collections.IPop< T >
bool	IsEmpty `[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 (IReadOnlyList< T > list)

VList< T >	AddRange (IEnumerable< T > list)

VList< T >	InsertRange (int index, IReadOnlyList< T > list)

VList< T >	RemoveRange (int index, int count)

T	TryPop (out bool isEmpty)
	Removes the last item (at index Count-1) from the list and returns it. More...

T	TryPeek (out bool isEmpty)
	Gets the last item in the list (at index Count-1). More...

T	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)
	Copies the elements of the collection to an Array, starting at a particular array index. More...

bool	Remove (T item)

Enumerator	GetEnumerator ()

IEnumerator< T > IEnumerable< T >.	GetEnumerator ()

System.Collections.IEnumerator System.Collections.IEnumerable.	GetEnumerator ()

T	TryGet (int index, out bool fail)

IRange< T > IListSource< T >.	Slice (int start, int count)

Slice_< T >	Slice (int start, int count=int.MaxValue)

VList< T >	Clone ()

object ICloneable.	Clone ()

VList< T >	SmartWhere (Func< T, bool > 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< T >	SmartSelectMany (Func< T, IReadOnlyList< T >> map)
	Maps a list to another list by concatenating the outputs of a mapping function. More...

VList< T >	Transform (VListTransformer< T > x)
	Transforms a list (combines filtering with selection and more). More...

Public Member Functions inherited from Loyc.Collections.IListSource< T >
IRange< T >	Slice (int start, int count=int.MaxValue)
	Returns a sub-range of this list. More...

Public Member Functions inherited from Loyc.Collections.IContains< T >
bool	Contains (T item)
	Returns true if and only if the collection contains the specified item. More...

Public Member Functions inherited from Loyc.Collections.IPop< T >
T	TryPop (out bool isEmpty)

T	TryPeek (out bool isEmpty)

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

◆ Add() [1/2]

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

inline

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

Referenced by Loyc.Collections.VList< Loyc.Syntax.LNode >.Add(), and Loyc.Collections.VList< Loyc.Syntax.LNode >.Push().

◆ Add() [2/2]

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

inline

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

◆ CopyTo()

void Loyc.Collections.VList< T >.CopyTo	(	T[]	array,
		int	arrayIndex
	)

inline

Copies the elements of the collection to an Array, starting at a particular array index.

It's usually more convenient to call the ToArray() extension method, which calls this method for you.

This method exists for performance reasons (the collection itself can often copy data out faster than an enumerator can).

Exceptions

ArgumentNullException	array is null.
ArgumentOutOfRangeException	arrayIndex is negative.
ArgumentException	The number of elements in the source collection is greater than the available space from arrayIndex to the end of the destination array.

Implements Loyc.Collections.ICollectionSource< T >.

◆ Equals()

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.

◆ IndexOf()

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

inline

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

Parameters

item	Item 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.

◆ operator FVList< T >()

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.

◆ operator FWList< T >()

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.

◆ operator WList< T >()

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.

◆ operator!=()

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.

◆ operator==()

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.

◆ Pop()

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

inline

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

◆ Push()

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

inline

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

◆ SmartSelect()

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

inline

Maps a list to another list of the same length.

Parameters

map	A 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 often processes a list without modifying it at all.

◆ SmartSelectMany()

VList<T> Loyc.Collections.VList< T >.SmartSelectMany ( Func< T, IReadOnlyList< T >> map )

inline

Maps a list to another list by concatenating the outputs of a mapping function.

Parameters

map	A function that transforms each item in the list to a list of items.

Returns: A list that contains all the items returned from map.

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

◆ SmartWhere()

VList<T> Loyc.Collections.VList< T >.SmartWhere ( Func< T, bool > keep )

inline

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

Parameters

keep	A 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.

◆ ToArray()

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

inline

Returns the VList converted to an array.

◆ ToFVList()

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.

◆ ToFWList()

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.

Referenced by Loyc.Collections.VList< Loyc.Syntax.LNode >.operator FWList< T >().

◆ ToWList()

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.

Referenced by Loyc.Collections.VList< Loyc.Syntax.LNode >.operator WList< T >().

◆ Transform()

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

inline

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

Parameters

x	Method 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.

Referenced by Loyc.Collections.VList< Loyc.Syntax.LNode >.WhereSelect().

◆ TryPeek()

T Loyc.Collections.VList< T >.TryPeek ( out bool isEmpty )

inline

Gets the last item in the list (at index Count-1).

Parameters

isEmpty When the list is empty, this is set to true and default(T) is returned.

◆ TryPop()

T Loyc.Collections.VList< T >.TryPop ( out bool isEmpty )

inline

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

Parameters

isEmpty When the list is empty, this is set to true and default(T) is returned.

◆ WhereSelect()

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

inline

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

Parameters

filter A 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 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.

Property Documentation

◆ BlockChainLength

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.

◆ Last

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.

Referenced by Loyc.Collections.VList< Loyc.Syntax.LNode >.Pop(), Loyc.Collections.VList< Loyc.Syntax.LNode >.TryPeek(), and Loyc.Collections.VList< Loyc.Syntax.LNode >.TryPop().

◆ Tail

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.

◆ this[int index, T defaultValue]

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.

Remarks

Nested classes

Public static fields

Properties

Public Member Functions

Static Public Member Functions

Member Function Documentation

◆ Add() [1/2]

◆ Add() [2/2]

◆ CopyTo()

◆ Equals()

◆ IndexOf()

◆ operator FVList< T >()

◆ operator FWList< T >()

◆ operator WList< T >()

◆ operator!=()

◆ operator==()

◆ Pop()

◆ Push()

◆ SmartSelect()

◆ SmartSelectMany()

◆ SmartWhere()

◆ ToArray()

◆ ToFVList()

◆ ToFWList()

◆ ToWList()

◆ Transform()

◆ TryPeek()

◆ TryPop()

◆ WhereSelect()

Property Documentation

◆ BlockChainLength

◆ Last

◆ Tail

◆ this[int index, T defaultValue]