A reference to a FVList, a so-called persistent list data structure. More...

Source file:

/Core/Loyc.Collections/VLists/FVList.cs

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

Remarks

A reference to a FVList, a so-called persistent list data structure.

An article is available online about the VList data types.

See the remarks of VListBlock<T> for more information about VLists. Items are normally added to, and removed from, the front of a FVList or to the back of a VList; adding, removing or changing items at any other position is inefficient. You can call ToVList() to convert a FVList to its equivalent VList, which is a reverse-order view of the same list that shares the same memory.

Nested classes
struct	Enumerator
	Enumerator for FVList; also used by FWList. More...

Public static fields
static readonly FVList< T >	Empty = new FVList<T>()

Properties
FVList< T >	Tail `[get]`
	Returns a list without the first item. If the list is empty, an empty list is retured. More...

T	First `[get]`
	Returns the front item of the list (at index 0), 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]`

Public Member Functions
	FVList (T firstItem)

	FVList (T itemZero, T itemOne)

	FVList (T[] array)

	FVList (IReadOnlyList< T > list)

FVList< T >	WithoutFirst (int offset)

FVList< T >	PreviousIn (FVList< T > largerList)

FVList< T >	Last (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 ()

FVList< T >	AddRange (FVList< T > list)

FVList< T >	AddRange (FVList< T > list, FVList< T > excludeSubList)

FVList< T >	AddRange (IReadOnlyList< T > list)

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

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

T	Pop ()
	Removes the front item (at index 0) from the list and returns it. More...

FVList< T >	Push (T item)
	Synonym for Add(); adds an item to the front of the list. More...

VList< T >	ToVList ()
	Returns this list as a VList, which effectively reverses the order of the elements. More...

FWList< T >	ToFWList ()
	Returns this list as a FWList. More...

WList< T >	ToWList ()
	Returns this list as a WList, which effectively reverses the order of the elements. More...

T[]	ToArray ()
	Returns the FVList converted to an array. More...

FVList< T >	SmartAdd (T item, FVList< T > original)
	Adds the specified item to the list, or original.WithoutFirst(original.Count - Count - 1) if doing so is equivalent. More...

FVList< T >	SmartAdd (T item, ref FVList< T > original)

int	IndexOf (T item)
	Searches for the specified object and returns the zero-based index of the first occurrence (lowest index) within the entire FVList. More...

void IList< T >.	Insert (int index, T item)

FVList< T >	Insert (int index, T item)

void IList< T >.	RemoveAt (int index)

FVList< T >	RemoveAt (int index)

void ICollection< T >.	Add (T item)
	Inserts an item at the front (index 0) of the FVList. More...

FVList< T >	Add (T item)
	Inserts an item at the front (index 0) of the FVList. More...

void ICollection< T >.	Clear ()

FVList< 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)

FVList< T >	Clone ()

object ICloneable.	Clone ()

FVList< T >	Where (Func< T, bool > filter)
	Applies a filter to a list, to exclude zero or more items. More...

FVList< T >	WhereSelect (Func< T, Maybe< T >> filter)
	Filters and maps a list with a user-defined function. More...

FVList< T >	SmartSelect (Func< T, T > map)
	Maps a list to another list of the same length. More...

FVList< T >	SmartSelectMany (Func< T, IReadOnlyList< T >> map)
	Maps a list to another list by concatenating the outputs of a mapping function. More...

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

Static Public Member Functions
static bool	operator== (FVList< T > lhs, FVList< T > rhs)
	Returns whether the two list references are the same. Does not compare the contents of the lists. More...

static bool	operator!= (FVList< T > lhs, FVList< T > rhs)
	Returns whether the two list references are different. Does not compare the contents of the lists. More...

static	operator VList< T > (FVList< T > list)
	Returns this list as a VList, which effectively reverses the order of the elements. More...

static	operator FWList< T > (FVList< T > list)
	Returns this list as a FWList. More...

static	operator WList< T > (FVList< T > list)
	Returns this list as a WList, which effectively reverses the order of the elements. More...

Member Function Documentation

◆ Add() [1/2]

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

inline

Inserts an item at the front (index 0) of the FVList.

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

Referenced by Loyc.Collections.FVList< T >.Add(), Loyc.Collections.FVList< T >.Push(), Loyc.Collections.VListBlock< T >.ReplaceAt(), and Loyc.Collections.VListBlock< T >.Transform().

◆ Add() [2/2]

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

inline

Inserts an item at the front (index 0) of the FVList.

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

◆ CopyTo()

void Loyc.Collections.FVList< 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.FVList< 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.FVList< 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 FVList.

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; therefore, this method is an O(n) operation, where n is Count.

◆ operator FWList< T >()

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

inlineexplicitstatic

Returns this list as a FWList.

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

References Loyc.Collections.FVList< T >.ToFWList().

◆ operator VList< T >()

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

inlineexplicitstatic

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

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

◆ operator WList< T >()

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

inlineexplicitstatic

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

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

References Loyc.Collections.FVList< T >.ToWList().

◆ operator!=()

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

inlinestatic

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

◆ operator==()

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

inlinestatic

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

◆ Pop()

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

inline

Removes the front item (at index 0) from the list and returns it.

References Loyc.Collections.FVList< T >.First.

◆ Push()

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

inline

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

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

◆ SmartAdd()

FVList<T> Loyc.Collections.FVList< T >.SmartAdd	(	T	item,
		FVList< T >	original
	)

inline

Adds the specified item to the list, or original.WithoutFirst(original.Count - Count - 1) if doing so is equivalent.

Parameters

item	Item to add
original	An old version of the list

Returns: Returns this.

This method helps write functional code in which you process an input list and produce an output list that may or may not be the same as the input list. In case the output list is identical, you would prefer to return the original input list rather than wasting memory on a new list. SmartAdd() helps you do this. The following method demonstrates SmartAdd() by removing all negative numbers from a list:

FVList<int> RemoveNegative(FVList<int> input) { var output = FVList<int>.Empty; // Enumerate tail-to-head foreach (int n in (VList<int>)input) if (n >= 0) output.SmartAdd(n, input); return output; }

You could also do the same thing with input.Filter(delegate(int i) { return i; } >= 0)

◆ SmartSelect()

FVList<T> Loyc.Collections.FVList< 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 FVList structure is not modified.

Note: the items are passed to map in "reverse" order (Last is first) because the function needs to find out at what point the tail changes.

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()

FVList<T> Loyc.Collections.FVList< 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.

Note: the items are passed to map in "reverse" order (Last is first) because the function needs to find out at what point the tail changes.

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.

◆ ToArray()

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

inline

Returns the FVList converted to an array.

References Loyc.Collections.VListBlock< T >.ToArray().

◆ ToFWList()

FWList<T> Loyc.Collections.FVList< T >.ToFWList ( )

inline

Returns this list as a FWList.

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

Referenced by Loyc.Collections.FVList< T >.operator FWList< T >().

◆ ToVList()

VList<T> Loyc.Collections.FVList< T >.ToVList ( )

inline

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

Returns: This is a trivial operation; the VList shares the same memory.

◆ ToWList()

WList<T> Loyc.Collections.FVList< T >.ToWList ( )

inline

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

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

Referenced by Loyc.Collections.FVList< T >.operator WList< T >().

◆ Transform()

FVList<T> Loyc.Collections.FVList< 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

This is my attempt to make an optimized multi-purpose routine for transforming a FVList or VList. It is slightly cumbersome to use, but allows you to do several common operations in one transformer method.

The VListTransformer method takes two arguments: an item and its index in the FVList or VList. It can modify the item if desired, and then it returns a XfAction value, which indicates the action to take. Most often you will return XfAction.Drop, XfAction.Keep, XfAction.Change, which, repectively, drop the item from the output list, copy the item to the output list unchanged (even if you modified the item), and copy the item to the output list (assuming you changed it).

Transform() needs to know if the item changed, at least at first, because if the first items are kept without changes, then the output list can share a common tail with the input list. If the transformer method returns XfAction.Keep for every element, then the output list is exactly the same (operator== returns true).

Of course, it would have been simpler just to return a boolean indicating whether to keep the item, and the Transform method itself could check whether the item changed. But checking for equality is a tad slow in the .NET framework, because there is no bitwise equality operator in .NET, so a virtual function would have to be called instead to test equality, which is especially slow if T is a value type that does not implement IEquatable(of T).

The final possible action, XfAction.Repeat, is like XfAction.Change except that Transform() calls the VListTransformer again. The second call has the form x(~i, ref item), where ~i is the bitwise NOT of the index i, and item is the same item that x returned the first time it was called. On the second call, x() can return XfAction.Change again to get a third call, if it wants.

XfAction.Repeat is best explained by example. In the following examples, assume "list" is a VList holding the numbers (1, 2, 3):

output = list.Transform((i, ref n) => { // This example produces (1, 1, 2, 2, 3, 3) return i >= 0 ? XfAction.Repeat : XfAction.Keep; });

output = list.Transform((i, ref n) => { // This example produces (1, 10, 2, 20, 3, 30) if (i >= 0) return XfAction.Repeat; n *= 10; return XfAction.Change; });

output = list.Transform((i, ref n) => { // This example produces (10, 1, 20, 2, 30, 3) if (i >= 0) { n *= 10; return XfAction.Repeat; } return XfAction.Keep; });

output = list.Transform((i, ref n) => { // This example produces (10, 100, 1000, 20, 200, 30, 300) n *= 10; if (n > 1000) return XfAction.Drop; return XfAction.Repeat; });

And now for some examples using XfAction.Keep, XfAction.Drop and XfAction.Change. Assume list is a VList holding the following integers: (-1, 2, -2, 13, 5, 8, 9)

output = list.Transform((i, ref n) => { // Keep every second item: (2, 13, 8) return (i % 2) == 1 ? XfAction.Keep : XfAction.Drop; });

output = list.Transform((i, ref n) => { // Keep odd numbers: (-1, 13, 5, 9) return (n % 2) != 0 ? XfAction.Keep : XfAction.Drop; });

output = list.Transform((i, ref n) => { // Keep and square all odd numbers: (1, 169, 25, 81) if ((n % 2) != 0) { n *= n; return XfAction.Change; } else return XfAction.Drop; });

output = list.Transform((i, ref n) => { // Increase each item by its index: (-1, 3, 0, 16, 9, 13, 15) n += i; return i == 0 ? XfAction.Keep : XfAction.Change; });

References Loyc.Collections.VListBlock< T >.Transform().

Referenced by Loyc.Collections.FVList< T >.WhereSelect().

◆ Where()

FVList<T> Loyc.Collections.FVList< T >.Where ( Func< T, bool > filter )

inline

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

Parameters

filter 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 (which are the last items in a FVList), those N items are typically not copied, but shared between the existing list and the new one.

◆ WhereSelect()

FVList<T> Loyc.Collections.FVList< 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 does not modify the first N items it is passed (which are the last items in a FVList), those N items are typically not copied, but shared between the existing list and the new one.

References Loyc.Collections.FVList< T >.Transform().

Property Documentation

◆ BlockChainLength

int? Loyc.Collections.FVList< 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 FVList usage patterns can produce long chains.

◆ First

T Loyc.Collections.FVList< T >.First

get

Returns the front item of the list (at index 0), which is the head of the list.

Referenced by Loyc.Collections.VListBlock< T >.AddRange(), and Loyc.Collections.FVList< T >.Pop().

◆ Tail

FVList<T> Loyc.Collections.FVList< T >.Tail

get

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

Referenced by Loyc.Collections.VListBlock< T >.MuMove().

◆ this[int index, T defaultValue]

T Loyc.Collections.FVList< 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 FWList< T >()

◆ operator VList< T >()

◆ operator WList< T >()

◆ operator!=()

◆ operator==()

◆ Pop()

◆ Push()

◆ SmartAdd()

◆ SmartSelect()

◆ SmartSelectMany()

◆ ToArray()

◆ ToFWList()

◆ ToVList()

◆ ToWList()

◆ Transform()

◆ Where()

◆ WhereSelect()

Property Documentation

◆ BlockChainLength

◆ First

◆ Tail

◆ this[int index, T defaultValue]