Package Loyc.Collections

Contains general-purpose interfaces (Loyc.Collections.IListSource{T}, ranges, etc.), collection implementations (Loyc.Collections.DList{T}, Loyc.Collections.WeakValueDictionary{K,V}, etc.), extension methods (Loyc.Collections.LCExt, Loyc.Collections.EnumerableExt, etc.), helper classes (Loyc.Collections.EmptyList{T}, (Loyc.Collections.Repeated{T}, etc.), and adapter classes (Loyc.Collections.ListSlice{T}, Loyc.Collections.BufferedSequence{T}, etc.). More...

Namespaces
package	Impl
	Contains helper classes and base classes for implementing collections (Loyc.Collections.Impl.InternalList{T}, Loyc.Collections.Impl.ListExBase{T}, Loyc.Collections.Impl.ListSourceBase{T}, etc.) Also contains the AList and CPTrie node classes, which perhaps should not be public...

Classes
class	AList< T >
	An all-purpose list structure with the following additional features beyond what's offered by List{T}: fast insertion and deletion (O(log N)), batch insertion and deletion, observability, fast cloning, freezability, and fast splitting and joining of large collections. More...
class	AListBase< K, T >
	Base class for the indexed tree-based data structures known as AList{T} and BList{T}. More...
class	AListBase< T >
	Common base class of AList{T} and SparseAList{T}. Most of the functionality of the two types is identical, so this class is used to share code between them. More...
struct	AListReverseView< K, T >
	A reverse view of an AList. More...
class	ArrayOf4< T >
struct	ArraySlice< T >
	Adapter: Provides access to a section of an array. More...
class	BDictionary< K, V >
	An sorted dictionary that is efficient for all operations and offers indexed access to its list of key-value pairs. More...
class	Bijection< K1, K2 >
	A bijection is a one-to-one function and its inverse. It is implemented with a pair of dictionaries, one that maps K1 to K2 and another that maps K2 to K1. More...
class	BList< T >
	An sorted in-memory list that is efficient for all operations and offers indexed access to its list. More...
class	BMultiMap< K, V >
	An sorted dictionary that allows multiple values to be associated with a single key. Note: both keys and values must be comparable. More...
class	BufferedSequence< T >
	Adapter: This class wraps an IEnumerator{T} or IEnumerable{T} into an IListSource{T}, lazily reading the sequence as TryGet is called. More...
class	CG
	Contains global functions of Loyc.Collections that don't belong in any specific class. More...
class	CollectionAsReadOnly< T >
	Adapter: a read-only wrapper that implements ICollection(T) and IReadOnlyCollection(T), returned from LCExt.AsReadOnly{T}. More...
class	CollectionDebugView< T >
	This helper class gives a nice view of a custom collection within the debugger. More...
class	CPStringTrie< TValue >
	A compact patricia trie that uses strings as keys. More...
class	CPTrie< T >
	Compact patricia tree class that stores keys as byte arrays. This class is intended to be use as a base class; a derived class can give meaning to the byte arrays, e.g. CPStringTrie encodes strings into byte arrays so they can be placed in the trie. More...
class	CPTrieBenchmark
class	CPTrieTests
	Test suite for CPStringTrie, CPByteTrie and CPIntTrie
class	CPValueCollection< T >
	Provides read-only access to the values of a CPTrie. More...
class	DictionaryDebugView< K, V >
	Workaround for a limitation of the debugger: it doesn't support CollectionDebugView{T} when T is KeyValuePair{K,V}. This class is identical, except that T is replaced with KeyValuePair{K,V}. More...
class	DictionaryExt
	Extension methods for Dictionary{K,V} and IDictionary{K,V}. More...
class	DList
	This class is the same as DList{object} except that it also implements the IList interface. More...
class	DList< T >
	A compact auto-enlarging list that efficiently supports supports insertions at the beginning or end of the list. More...
class	EmptyArray< T >
	EmptyArray{T}.Value lets you avoid allocating an empty array on the heap. More...
class	EmptyEnumerator< T >
	Helper class: an empty enumerator. More...
class	EmptyList< T >
	Helper class: EmptyList{T}.Value is a read-only empty list. More...
class	EmptySequenceException
	An exception thrown by methods or properties that require a non-empty sequence but were provided with an empty sequence. More...
class	EnumerableExt
	Additional extension methods for IEnumerable{T}, beyond what LINQ provides. More...
class	EnumerationException
	An exception thrown by an enumerator when it detects that the collection was modified after enumeration started but before it finished. More...
class	EnumeratorBase< T >
	Base class to help you implement the standard IEnumerator{T} interface. All you have to do is override MoveNext() and, when successful, set the Current property. More...
struct	FVList< T >
	A reference to a FVList, a so-called persistent list data structure. More...
class	FWList< T >
	FWList is the mutable variant of the FVList data structure. More...
interface	IAdd< in T >
	An interface for depositing items. Includes only an Add(T) method. More...
interface	IAddRange< T >
	An interface typically implemented alongside ICollection{T}, for collection types that can add multiple items in one method call. More...
interface	IArray< T >
	This interface models the capabilities of an array: getting and setting elements by index, but not adding or removing elements. More...
interface	IAutoCreatePool< in TKey, out TValue >
	Represents a pool of objects in which an object is automatically created when requested by its key. More...
interface	IAutoSizeArray< T >
	An auto-sizing array is a list structure that allows you to modify the element at any index, including indices that don't yet exist; the collection automatically adds missing indices. More...
interface	IBinumerable< T >
	Interface for a collection that can return IBinumerator{T}s pointing to the beginning and end of the collection. More...
interface	IBinumerator< T >
	Extends the "enumerator" concept to allow backward enumeration. More...
interface	IBRange< out T >
	A bidirectional range. Allows you to read or remove the first or last element in a range. More...
interface	IBRangeEx< R, T >
	A bidirectional range that can perform operations such as intersection and overlap tests on pairs of ranges of the same type. More...
interface	IBRangeEx< T >
	A bidirectional range that can perform operations such as intersection and overlap tests on pairs of ranges. More...
interface	ICharSource
	A read-only list of characters plus a Slice(int,int) method. More...
interface	ICollectionAndReadOnly< T >
	This interface combines the original ICollection{T} with IReadOnlyCollection{T}. It exists for the same reason as IListAndListSource{T}, to fix ambiguity errors. More...
interface	ICollectionEx< T >
	This interface combines the original ICollection(T) interface with IReadOnlyCollection(T), ISinkCollection(T), and IAddRange(T), a convenient way to implement all three. More...
interface	ICount
	Holds the Count property found in nearly all collection interfaces. More...
interface	IDeque< T >
	Represents a double-ended queue that allows items to be added or removed at the beginning or end. More...
interface	IFRange< out T >
	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...
interface	IIsEmpty
	Holds the IsEmpty property that tells you if a collection is empty. More...
interface	IListAndListSource< T >
	This interface combines the original IList{T} interface with its "source" (read-only) component interfaces, including IReadOnlyList{T}, plus IListSource{T}. More...
interface	IListEx< T >
	This interface combines the original IList(T) interface with several IListSource(T), ISinkList(T), IArray(T) and several additional methods (e.g. RemoveAll, InsertRange). More...
interface	IListRangeMethods< T >
	An interface typically implemented alongside IList{T} for collection types that can add or remove multiple items in one method call. More...
interface	IListSource< out T >
	A read-only list indexed by an integer. More...
interface	IMBinumerator< T >
	A mutable bidirectional enumerator interface. Please note that the "Remove" method always moves to the next item, even though the Binumerator is capable of moving backward. More...
interface	IMBRange< T >
	A mutable bidirectional range. More...
interface	IMEnumerator< T >
	A mutable enumerator interface. Provides a "Remove" method like Java iterators have, and allows you to modify the current item. More...
interface	IMFRange< T >
	A mutable forward range. More...
interface	IMRange< T >
	A mutable random-access range. More...
class	IndexedAList< T >
	A simple wrapper around AList that includes an AListIndexer{K,T} that can be used to find items relatively quickly in a large list. When an index is built and the list is large, it accelerates IndexOf(item), Contains(item) and Remove(item). More...
interface	INegArray< T >
	This interface models the capabilities of an array: getting and setting elements by index, but not adding or removing elements. This interface is the counterpart to IListSource{T} for lists whose minimum index is not (necessarily) zero. More...
interface	INegAutoSizeArray< T >
	An auto-sizing array is a list structure that allows you to modify the element at any index, including indexes that don't yet exist; the collection automatically adds missing indexes. More...
interface	INegDeque< T >
	Represents a Deque that supports negative indexes. In this kind of Deque, pushing and popping elements does not affect the indexes of the other elements in the collection. More...
interface	INegListSource< T >
	This interface is the counterpart to IListSource{T} for lists whose minimum index is not (necessarily) zero. More...
interface	INotifyListChanging< T >
	Encapsulates the ListChanging event that notifies listeners of dynamic changes to an indexed list, such as when items get added and removed or the whole list is refreshed. More...
class	InvertibleSet< T >
	An immutable set that can be inverted. For example, an InvertibleSet<int> could contain "everything except 4 and 10", or it could contain a positive set such as "1, 2, and 3". More...
class	InvertibleSetTests
interface	IPop< T >
	Represents a collection that produces a sequence of items, and can return the next item without popping it (the Peek operation). More...
interface	IPush< T >
	Represents a collection that accepts a sequence of items. More...
interface	IQueue< T >
	Represents a FIFO (first-in-first-out) queue. More...
interface	IRange< out T >
	A random-access range, also known as a "slice". Allows you to narrow down the range like IBRange{T} does, and also provides random access via IListSource{T}. More...
interface	IRangeEx< R, T >
	A random-access range that can perform operations such as intersection and overlap tests on pairs of ranges of the same type. More...
interface	IRangeEx< T >
	A random-access range that can perform operations such as intersection and overlap tests on pairs of ranges. More...
interface	ISetImm< T >
	An immutable set that supports numerous set operations. More...
interface	ISetImm< T, SetT >
	An immutable set of type SetT with elements of type T. More...
interface	ISetOperations< in T, in InSetT, out OutSetT >
interface	ISetOperations< in T, SetT >
	Set-combining operations: With, Without, Union, Intersect, Except, Xor. More...
interface	ISetTests< SetT >
	Set testing operations.
interface	ISinkArray< T >
	Represents a write-only array. More...
interface	ISinkCollection< T >
	Represents a write-only collection: you can modify it, but you cannot learn what it contains. More...
interface	ISinkList< T >
	Represents a write-only indexable list class. More...
interface	ISparseList< T >
	Represents a sparse list that allows insertion and removal of items and empty spaces. In a sparse list, some spaces can be "clear" meaning that they have no value. More...
interface	ISparseListEx< T >
	A sparse list that supports additional methods including InsertRange(int, ISparseListSource{T}). More...
interface	ISparseListSource< T >
	Represents a read-only indexed list in which parts of the index space may be unused or "clear". More...
interface	IStack< T >
	Represents a LIFO (last-in-first-out) stack. More...
class	KeyAlreadyExistsException
	An exception thrown by dictionary objects when they are asked to "add" a key-value pair that already exists. More...
class	KeyCollection< TKey, TValue >
	Adapter: this is a read-only collection of Keys read from a generic IDictionary. It is a modified version of Dictionary{TKey, TValue}.KeyCollection from the Mono project, changed to use IDictionary instead of Dictionary. More...
class	LCExt
	Extension methods for Loyc Collection interfaces (such as IListSource{T}) and for Loyc Collection adapters (such as AsReadOnly{T}, which returns a CollectionAsReadOnly{T} adapter.) More...
class	LCInterfaces
	This class contains extension methods that are provided as part of various Loyc.Collections interfaces. For example, it provides methods such as IndexOf(), Contains() and CopyTo(), that the traditional ICollection{T} and IList{T} interfaces require the author to write himself. More...
class	LinqToCollections
	Work in progress. This class will enhance LINQ-to-Objects with type-preserving and/or higher-performance extension methods. More...
class	ListAsListSource< T >
	Helper type returned from LCExt.AsListSource{T}. More...
struct	ListChangeInfo< T >
	Contains information about how a collection is about to change. More...
class	ListExt
	Extension methods and helper methods for List{T}, IList{T}, IReadOnlyList{T}, arrays, IListSource{T}, and for related mutable interfaces such as IArray{T}. More...
struct	ListSlice< T >
	Adapter: a wrapper of a list that provides a view of a range of elements. Objects of this type are returned from ListExt.Slice{T} More...
class	ListSourceAsList< T >
	Adapter: a read-only wrapper that implements IList(T) and IListSource(T), returned from LCExt.AsList{T}. More...
class	ListSourceAsSparse< T >
	Adapter from IListSource{T} to ISparseListSource{T}. More...
class	ListSourceDebugView< T >
	This helper class gives a nice view of a custom collection within the debugger. More...
class	Map< K, V >
	An immutable dictionary. More...
class	MapOrMMap< K, V >
	Common base class that contains code shared between Map{K,V} and MMap{K,V}. More...
class	MMap< K, V >
	A dictionary class built on top of InternalSet<KeyValuePair<K,V>>. More...
class	MSet< T >
	A mutable set. More...
struct	NegList< T >
	Adapter: provides a view of an IList{T} in which the Count is the same, but the minimum index is not necessarily zero. Returned from LCExt.NegView{T}(IList{T},int). More...
struct	NegListSlice< T >
	Adapter: a random-access range for a slice of an INegListSource{T}. More...
struct	NegListSource< T >
	Adapter: provides a view of an IListSource{T} in which the Count is the same, but the minimum index is not necessarily zero. Returned from LCExt.NegView{T}(IListSource{T},int). More...
struct	NestedEnumerable< Frame, T >
	Helper type. You pass a cloneable Frame object to the constructor, and then a copy of this Frame is used to construct a new NestedEnumerator{Frame,T} each time the user calls GetEnumerator. More...
struct	NestedEnumerator< Frame, T >
	Helper class. An enumerator that helps enumerate tree data structures. It maintains a virtual call stack that avoids the performance hit of using nested "yield return" statements in C#. More...
struct	NumRange< Num, Math >
	Represents a range of integers of a specified data type. More...
struct	RangeEnumerator< R, T >
	Helper struct: enumerates through a forward range (IFRange{T}), calling the range methods through R instead of through IFRange{T}. More...
struct	RangeEnumerator< T >
	Helper struct: enumerates through a forward range (IFRange{T}). More...
class	RangeExt
	Extension/helper methods for ranges. More...
class	ReadOnlyAsCollection< T >
	A read-only wrapper that implements ICollection(T) and ISource(T), returned from LCExt.AsCollection{T} More...
struct	Repeated< T >
	Helper struct. A sequence that stores one value, but acts like a list in which that value is repeated a specified number of times. Returned from Range.Repeat{T}. More...
struct	ReverseBinumerator< T >
	Adapter: a IBinumerator{T} that swaps the MoveNext() and MovePrev() methods. More...
struct	ReversedList< T >
	Adapter: a reversed of an IList{T}. TODO: unit tests. More...
class	ReversedListSource< T >
	Adapter: reversed view of IListSource{T} returned from LCExt.Reverse{T}. More...
class	RVListTests
class	RWListTests
class	SelectListSource< T, TResult >
	Helper class: provides a modified view of an IListSource by transforming each element on-demand. Objects of this type are returned from LCExt.Select{T,TResult}(IListSource{T},Func{T,TResult}) More...
class	SelectNegLists< T >
	Adapter: provides a view of an IList{T} in which element [i] is a NegList{T} N such that N[0] refers to element [i] in the original list. See LCExt.NegLists{T}(IList{T}) for more information. More...
class	SelectNegListSources< T >
	Adapter: provides view of an IListSource{T} in which element [i] is a NegListSource{T} N such that N[0] refers to element [i] in the original list. See LCExt.NegLists{T}(IListSource{T}) for more information. More...
struct	Set< T >
	An immutable set. More...
class	SimpleCache< T >
	A cache designed to save memory by sharing instances of identical strings and other immutable objects. More...
class	SimpleCacheTests
struct	Slice_< T >
	Adapter: a random-access range for a slice of an IListSource{T}. More...
class	SparseAList< T >
	A sparse A-List that implements ISparseList{T}. More...
struct	StringSlice
	A random-access slice of System.String. More...
class	UpCastListSource< T, TOut >
	Helper class for treating a collection of a derived type as a collection of a base type or interface. More...
class	UpCastSource< T, TOut >
	Helper class for treating a collection of a derived type as a collection of a base type or interface. More...
class	ValueCollection< TKey, TValue >
	Adapter: this is a read-only collection of Values read from a generic IDictionary. It is a modified version of Dictionary{TKey, TValue}.ValueCollection from the Mono project, changed to use IDictionary instead of Dictionary. More...
struct	VList< T >
	VList represents a reference to a reverse-order FVList. More...
class	VListBlock< T >
	VListBlock implements the core functionality of FVList, VList, FWList and WList. It is not intended to be used directly. More...
class	VListBlockArray< T >
	Implementation of VListBlock(of T) that contains an array. It is always initialized with at least one item, and items cannot be removed unless the list is mutable. More...
class	VListBlockOfTwo< T >
	The tail of a VList contains only one or two items. To improve efficiency slightly, these two-item lists are represented by a VListBlockOfTwo, which is more compact than VListBlockArray. More...
class	VListTests
class	WeakKeyComparer< T >
	Compares objects of the given type or WeakKeyReferences to them for equality based on the given comparer. Note that we can only implement IEqualityComparer{T} for T = object as there is no other common base between T and WeakKeyReference{T}. We need a single comparer to handle both types because we don't want to allocate a new weak reference for every lookup. More...
class	WeakKeyDictionary< TKey, TValue >
	A dictionary with weak keys. More...
class	WeakKeyReference< T >
	Provides a weak reference to an object of the given type to be used in a WeakDictionary along with the given comparer. More...
class	WeakValueDictionary< K, V >
	A dictionary in which the values are weak. When a value has been garbage- collected, the dictionary acts as if the key is not present (except the Remove() method, which saves time by not checking whether the value is dead.) More...
class	WList< T >
	WList is the mutable variant of the VList data structure. More...
class	WListBase< T >
	Shared base class of FWList and WList. More...
class	WListProtected< T >
	WList implementation in which the WList operations are only accessible to a derived class. More...
class	WListTests

Enumerations
enum	AListOperation {   AListOperation.Retrieve = 0, AListOperation.ReplaceIfPresent = 1, AListOperation.Remove = 2,   AListOperation.Add = 3, AListOperation.AddOrReplace = 4, AListOperation.AddIfNotPresent = 5,   AListOperation.AddOrThrow = 6 }
	Indicates the way an add operation (such as BList{T}.Do should behave when an item being added to a set or list is a duplicate of an item that is already present, or when the key of a key-value pair being added to a dictionary is a duplicate of a key that is already present in the dictionary. More...
enum	XfAction {   XfAction.Drop, XfAction.Keep, XfAction.Change,   XfAction.Repeat }
	Values that can be returned by the VListTransformer function that the user passes to the Transform method in FVList, VList, FWList or WList. More...

Functions
delegate void	ListChangingHandler< T > (IListSource< T > sender, ListChangeInfo< T > args)
	Represents the method that handles the INotifyListChanging{T}.ListChanging event. More...
delegate XfAction	VListTransformer< T > (int i, ref T item)
	User-supplied list transformer function. More...

Detailed Description

Contains general-purpose interfaces (Loyc.Collections.IListSource{T}, ranges, etc.), collection implementations (Loyc.Collections.DList{T}, Loyc.Collections.WeakValueDictionary{K,V}, etc.), extension methods (Loyc.Collections.LCExt, Loyc.Collections.EnumerableExt, etc.), helper classes (Loyc.Collections.EmptyList{T}, (Loyc.Collections.Repeated{T}, etc.), and adapter classes (Loyc.Collections.ListSlice{T}, Loyc.Collections.BufferedSequence{T}, etc.).

Enumeration Type Documentation

enum Loyc.Collections.AListOperation

Indicates the way an add operation (such as BList{T}.Do should behave when an item being added to a set or list is a duplicate of an item that is already present, or when the key of a key-value pair being added to a dictionary is a duplicate of a key that is already present in the dictionary.

All the "add" operations are deliberately listed last, so that AListBase{K,T}.DoSingleOperation can use a greater-than operator to figure out whether an item may be added or not.

Enumerator
Retrieve	Default operation. The item with the specified key will be retrieved. The tree will not be modified.
ReplaceIfPresent	Replace an existing item/key if present, or do nothing if there is no matching item/key.
Remove	Remove the item with the specified key if present.
Add	A new item will be added unconditionally, without affecting existing elements, in no particular order with respect to existing items that have the same key.
AddOrReplace	A new item will replace an item that has the same key. If the collection already contains multiple instances of the item/key, the instance to be replaced is undefined.
AddIfNotPresent	A new item will be added if its key doesn't match an existing element. If the item already exists, it is not replaced.
AddOrThrow	The item will be added if its key is not already present, but KeyAlreadyExistsException or InvalidOperationException will be thrown if the new item is equal to an existing element. If this exception occurs during an AddRange() operation, some of the items may have already been added successfully, and the changes will not be rolled back unless otherwise specified in the documentation of the method that performs the add operation.

enum Loyc.Collections.XfAction

Values that can be returned by the VListTransformer function that the user passes to the Transform method in FVList, VList, FWList or WList.

Enumerator
Drop	Do not include the item in the output list
Keep	Include the original item in the output list
Change	Include the modified item in the output list
Repeat	Include the modified item in the output, and transform it again

Function Documentation

delegate void Loyc.Collections.ListChangingHandler< T >	(	IListSource< T >	sender,
		ListChangeInfo< T >	args
	)

Represents the method that handles the INotifyListChanging{T}.ListChanging event.

Parameters

sender	The collection that changed.
args	Information about the change.

delegate XfAction Loyc.Collections.VListTransformer< T >	(	int	i,
		ref T	item
	)

User-supplied list transformer function.

Parameters

item	An item from the FVList or VList
i	Index of the item

Returns

See the documentation of FVList.Transform() for instructions and possible return values.