Class TreeDictionary<TKey, TValue>

Namespace

LfrlAnvil.Collections

Assembly

LfrlAnvil.Collections.dll

Represents a generic tree data structure with the ability to identify nodes by keys.

public class TreeDictionary<TKey, TValue> : ITreeDictionary<TKey, TValue>, IReadOnlyTreeDictionary<TKey, TValue>, IReadOnlyDictionary<TKey, TValue>, IReadOnlyCollection<KeyValuePair<TKey, TValue>>, IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable where TKey : notnull

Type Parameters

TKey

Key type.

TValue

Value type.

Inheritance

object

TreeDictionary<TKey, TValue>

Implements

ITreeDictionary<TKey, TValue>

IReadOnlyTreeDictionary<TKey, TValue>

IReadOnlyDictionary<TKey, TValue>

IReadOnlyCollection<KeyValuePair<TKey, TValue>>

IDictionary<TKey, TValue>

ICollection<KeyValuePair<TKey, TValue>>

IEnumerable<KeyValuePair<TKey, TValue>>

IEnumerable

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

EnumerableExtensions.ToMultiDictionary<TKey, TValue>(IEnumerable<KeyValuePair<TKey, TValue>>)

EnumerableExtensions.ToMultiDictionary<TKey, TValue>(IEnumerable<KeyValuePair<TKey, TValue>>, IEqualityComparer<TKey>)

EnumerableExtensions.ToMultiDictionary<TKey, TValue>(IEnumerable<TValue>, Func<TValue, TKey>)

EnumerableExtensions.ToMultiDictionary<TKey, TValue>(IEnumerable<TValue>, Func<TValue, TKey>, IEqualityComparer<TKey>)

EnumerableExtensions.ToMultiDictionary<TSource, TKey, TValue>(IEnumerable<TSource>, Func<TSource, TKey>, Func<TSource, TValue>)

EnumerableExtensions.ToMultiDictionary<TSource, TKey, TValue>(IEnumerable<TSource>, Func<TSource, TKey>, Func<TSource, TValue>, IEqualityComparer<TKey>)

EnumerableExtensions.ToMultiHashSet<T>(IEnumerable<T>)

EnumerableExtensions.ToMultiHashSet<T>(IEnumerable<T>, IEqualityComparer<T>)

EnumerableExtensions.ToSequentialDictionary<TSource, TKey>(IEnumerable<TSource>, Func<TSource, TKey>)

EnumerableExtensions.ToSequentialDictionary<TSource, TKey>(IEnumerable<TSource>, Func<TSource, TKey>, IEqualityComparer<TKey>)

EnumerableExtensions.ToSequentialDictionary<TSource, TKey, TValue>(IEnumerable<TSource>, Func<TSource, TKey>, Func<TSource, TValue>)

EnumerableExtensions.ToSequentialDictionary<TSource, TKey, TValue>(IEnumerable<TSource>, Func<TSource, TKey>, Func<TSource, TValue>, IEqualityComparer<TKey>)

EnumerableExtensions.ToSequentialHashSet<T>(IEnumerable<T>)

EnumerableExtensions.ToSequentialHashSet<T>(IEnumerable<T>, IEqualityComparer<T>)

Constructors

TreeDictionary()

Creates a new empty TreeDictionary<TKey, TValue> instance with Default key comparer.

public TreeDictionary()

TreeDictionary(IEqualityComparer<TKey>)

Creates a new empty TreeDictionary<TKey, TValue> instance.

public TreeDictionary(IEqualityComparer<TKey> comparer)

Parameters

comparer IEqualityComparer<TKey>

Key equality comparer.

Properties

Comparer

Key equality comparer.

public IEqualityComparer<TKey> Comparer { get; }

Property Value

IEqualityComparer<TKey>

Count

Gets the number of elements in the collection.

public int Count { get; }

Property Value

int

The number of elements in the collection.

this[TKey]

Gets or sets the element with the specified key.

public TValue this[TKey key] { get; set; }

Parameters

key TKey

The key of the element to get or set.

Property Value

TValue

The element with the specified key.

Exceptions

ArgumentNullException

key is null.

KeyNotFoundException

The property is retrieved and key is not found.

NotSupportedException

The property is set and the IDictionary<TKey, TValue> is read-only.

Keys

Gets an ICollection<T> containing the keys of the IDictionary<TKey, TValue>.

public IEnumerable<TKey> Keys { get; }

Property Value

IEnumerable<TKey>

An ICollection<T> containing the keys of the object that implements IDictionary<TKey, TValue>.

Nodes

Returns a new IEnumerable<T> instance that contains all nodes of this tree.

public IEnumerable<TreeDictionaryNode<TKey, TValue>> Nodes { get; }

Property Value

IEnumerable<TreeDictionaryNode<TKey, TValue>>

Root

Represents this tree's root node. Equal to null when the tree is empty.

public TreeDictionaryNode<TKey, TValue>? Root { get; }

Property Value

TreeDictionaryNode<TKey, TValue>

Values

Gets an ICollection<T> containing the values in the IDictionary<TKey, TValue>.

public IEnumerable<TValue> Values { get; }

Property Value

IEnumerable<TValue>

An ICollection<T> containing the values in the object that implements IDictionary<TKey, TValue>.

Methods

Add(TreeDictionaryNode<TKey, TValue>)

Adds the provided node to this tree.

public void Add(TreeDictionaryNode<TKey, TValue> node)

Parameters

node TreeDictionaryNode<TKey, TValue>

Node to add.

Remarks

Created node will become this tree's root if it was empty, otherwise it will be attached to the current root node as its child.

Exceptions

InvalidOperationException

When node already belongs to any tree.

ArgumentException

When node's key already exists in this tree.

Add(TKey, TValue)

Adds the provided (key, value) pair to this tree.

public TreeDictionaryNode<TKey, TValue> Add(TKey key, TValue value)

Parameters

key TKey

Node's key.

value TValue

Node's value.

Returns

TreeDictionaryNode<TKey, TValue>

Created ITreeDictionaryNode<TKey, TValue> instance.

Remarks

Created node will become this tree's root if it was empty, otherwise it will be attached to the current root node as its child.

Exceptions

ArgumentException

When node's key already exists in this tree.

AddSubtree(ITreeDictionaryNode<TKey, TValue>)

Adds a sub-tree with its root at the provided node to this tree.

public TreeDictionaryNode<TKey, TValue> AddSubtree(ITreeDictionaryNode<TKey, TValue> node)

Parameters

node ITreeDictionaryNode<TKey, TValue>

Root of the sub-tree to add.

Returns

TreeDictionaryNode<TKey, TValue>

Created ITreeDictionaryNode<TKey, TValue> instance of the added sub-tree's root node.

Remarks

Created sub-tree's root node will become this tree's root if it was empty, otherwise it will be attached to the current root node as its child.

Exceptions

InvalidOperationException

When node belongs to this tree.

ArgumentException

When any of the sub-tree's node's keys already exist in this tree.

AddSubtreeTo(TreeDictionaryNode<TKey, TValue>, ITreeDictionaryNode<TKey, TValue>)

Adds a sub-tree with its root at the provided node to this tree and attaches it to the specified parent node as its child.

public TreeDictionaryNode<TKey, TValue> AddSubtreeTo(TreeDictionaryNode<TKey, TValue> parent, ITreeDictionaryNode<TKey, TValue> node)

Parameters

parent TreeDictionaryNode<TKey, TValue>

Parent node.

node ITreeDictionaryNode<TKey, TValue>

Root of the sub-tree to add.

Returns

TreeDictionaryNode<TKey, TValue>

Exceptions

InvalidOperationException

When node belongs to this tree.

ArgumentException

When parent node does not belong to this tree or when any of the sub-tree's node's keys already exist in this tree.

AddSubtreeTo(TKey, ITreeDictionaryNode<TKey, TValue>)

Adds a sub-tree with its root at the provided node to this tree and attaches it to the specified parent node as its child.

public TreeDictionaryNode<TKey, TValue> AddSubtreeTo(TKey parentKey, ITreeDictionaryNode<TKey, TValue> node)

Parameters

parentKey TKey

Parent node's key.

node ITreeDictionaryNode<TKey, TValue>

Root of the sub-tree to add.

Returns

TreeDictionaryNode<TKey, TValue>

Exceptions

KeyNotFoundException

When parent node's key does not exist in this tree.

InvalidOperationException

When node belongs to this tree.

ArgumentException

When any of the sub-tree's node's keys already exist in this tree.

AddTo(TreeDictionaryNode<TKey, TValue>, TreeDictionaryNode<TKey, TValue>)

Adds the provided node to this tree and attaches it to the specified parent node as its child.

public void AddTo(TreeDictionaryNode<TKey, TValue> parent, TreeDictionaryNode<TKey, TValue> node)

Parameters

parent TreeDictionaryNode<TKey, TValue>

Parent node.

node TreeDictionaryNode<TKey, TValue>

Node to add.

Exceptions

InvalidOperationException

When parent node does not belong to this tree or when node already belongs to any tree.

ArgumentException

When node's key already exists in this tree.

AddTo(TreeDictionaryNode<TKey, TValue>, TKey, TValue)

Adds the provided (key, value) pair to this tree and attaches it to the specified parent node as its child.

public TreeDictionaryNode<TKey, TValue> AddTo(TreeDictionaryNode<TKey, TValue> parent, TKey key, TValue value)

Parameters

parent TreeDictionaryNode<TKey, TValue>

Parent node.

key TKey

Node's key.

value TValue

Node's value.

Returns

TreeDictionaryNode<TKey, TValue>

Created ITreeDictionaryNode<TKey, TValue> instance.

Exceptions

InvalidOperationException

When parent node does not belong to this tree.

ArgumentException

When node's key already exists in this tree.

AddTo(TKey, TreeDictionaryNode<TKey, TValue>)

Adds the provided node to this tree and attaches it to the specified parent node as its child.

public void AddTo(TKey parentKey, TreeDictionaryNode<TKey, TValue> node)

Parameters

parentKey TKey

Parent node's key.

node TreeDictionaryNode<TKey, TValue>

Node to add.

Exceptions

InvalidOperationException

When node already belongs to any tree.

KeyNotFoundException

When parent node's key does not exist in this tree.

ArgumentException

When node's key already exists in this tree.

AddTo(TKey, TKey, TValue)

Adds the provided (key, value) pair to this tree and attaches it to the specified parent node as its child.

public TreeDictionaryNode<TKey, TValue> AddTo(TKey parentKey, TKey key, TValue value)

Parameters

parentKey TKey

Parent node's key.

key TKey

Node's key.

value TValue

Node's value.

Returns

TreeDictionaryNode<TKey, TValue>

Created ITreeDictionaryNode<TKey, TValue> instance.

Exceptions

KeyNotFoundException

When parent node's key does not exist in this tree.

ArgumentException

When node's key already exists in this tree.

Clear()

Removes all items from the ICollection<T>.

public void Clear()

Exceptions

NotSupportedException

The ICollection<T> is read-only.

ContainsKey(TKey)

Determines whether the IDictionary<TKey, TValue> contains an element with the specified key.

[Pure]
public bool ContainsKey(TKey key)

Parameters

key TKey

The key to locate in the IDictionary<TKey, TValue>.

Returns

bool

true if the IDictionary<TKey, TValue> contains an element with the key; otherwise, false.

Exceptions

ArgumentNullException

key is null.

CreateSubtree(TKey)

Creates a new TreeDictionary<TKey, TValue> instance equivalent to the sub-tree with a node associated with the provided key as its root node.

[Pure]
public TreeDictionary<TKey, TValue> CreateSubtree(TKey key)

Parameters

key TKey

Root node's key.

Returns

TreeDictionary<TKey, TValue>

New TreeDictionary<TKey, TValue> instance. Result will be empty if the provided key does not exist.

GetEnumerator()

Returns an enumerator that iterates through the collection.

[Pure]
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()

Returns

IEnumerator<KeyValuePair<TKey, TValue>>

An enumerator that can be used to iterate through the collection.

GetNode(TKey)

Attempts to return an ITreeDictionaryNode<TKey, TValue> associated with the provided key.

[Pure]
public TreeDictionaryNode<TKey, TValue>? GetNode(TKey key)

Parameters

key TKey

Key to check.

Returns

TreeDictionaryNode<TKey, TValue>

An ITreeDictionaryNode<TKey, TValue> instance associated with the provided key or null if key does not exist.

MoveSubtreeTo(TreeDictionaryNode<TKey, TValue>, TreeDictionaryNode<TKey, TValue>)

Moves the sub-tree with the provided root node to a different parent node.

public void MoveSubtreeTo(TreeDictionaryNode<TKey, TValue> parent, TreeDictionaryNode<TKey, TValue> node)

Parameters

parent TreeDictionaryNode<TKey, TValue>

Parent node.

node TreeDictionaryNode<TKey, TValue>

Sub-tree's root node to move.

Remarks

This operation is equivalent to removing the sub-tree from this tree and re-adding it to the specified parent node.

Exceptions

InvalidOperationException

When parent node or node do not belong to this tree or node is moved to itself or to one of its descendants.

MoveSubtreeTo(TreeDictionaryNode<TKey, TValue>, TKey)

Moves the sub-tree with root node associated with the provided key to a different parent node.

public TreeDictionaryNode<TKey, TValue> MoveSubtreeTo(TreeDictionaryNode<TKey, TValue> parent, TKey key)

Parameters

parent TreeDictionaryNode<TKey, TValue>

Parent node.

key TKey

Key of the sub-tree's root node to move.

Returns

TreeDictionaryNode<TKey, TValue>

Node associated with the provided key.

Remarks

This operation is equivalent to removing the sub-tree from this tree and re-adding it to the specified parent node.

Exceptions

KeyNotFoundException

When key does not exist in this tree.

InvalidOperationException

When parent node does not belong to this tree or node is moved to itself or to one of its descendants.

MoveSubtreeTo(TKey, TreeDictionaryNode<TKey, TValue>)

Moves the sub-tree with the provided root node to a different parent node.

public void MoveSubtreeTo(TKey parentKey, TreeDictionaryNode<TKey, TValue> node)

Parameters

parentKey TKey

Parent node's key.

node TreeDictionaryNode<TKey, TValue>

Sub-tree's root node to move.

Remarks

This operation is equivalent to removing the sub-tree from this tree and re-adding it to the specified parent node.

Exceptions

KeyNotFoundException

When parentKey does not exist in this tree.

InvalidOperationException

When node does not belong to this tree or it's moved to itself or to one of its descendants.

MoveSubtreeTo(TKey, TKey)

Moves the sub-tree with root node associated with the provided key to a different parent node.

public TreeDictionaryNode<TKey, TValue> MoveSubtreeTo(TKey parentKey, TKey key)

Parameters

parentKey TKey

Parent node's key.

key TKey

Key of the sub-tree's root node to move.

Returns

TreeDictionaryNode<TKey, TValue>

Node associated with the provided key.

Remarks

This operation is equivalent to removing the sub-tree from this tree and re-adding it to the specified parent node.

Exceptions

KeyNotFoundException

When parentKey or key does not exist in this tree.

InvalidOperationException

When node is moved to itself or to one of its descendants.

MoveTo(TreeDictionaryNode<TKey, TValue>, TreeDictionaryNode<TKey, TValue>)

Moves the provided node to a different parent node.

public void MoveTo(TreeDictionaryNode<TKey, TValue> parent, TreeDictionaryNode<TKey, TValue> node)

Parameters

parent TreeDictionaryNode<TKey, TValue>

Parent node.

node TreeDictionaryNode<TKey, TValue>

Node to move.

Remarks

This operation is equivalent to removing the node from this tree and re-adding it to the specified parent node.

Exceptions

InvalidOperationException

When parent node or node do not belong to this tree or node is moved to itself.

MoveTo(TreeDictionaryNode<TKey, TValue>, TKey)

Moves the node associated with the provided key to a different parent node.

public TreeDictionaryNode<TKey, TValue> MoveTo(TreeDictionaryNode<TKey, TValue> parent, TKey key)

Parameters

parent TreeDictionaryNode<TKey, TValue>

Parent node.

key TKey

Key of the node to move.

Returns

TreeDictionaryNode<TKey, TValue>

Node associated with the provided key.

Remarks

This operation is equivalent to removing the node from this tree and re-adding it to the specified parent node.

Exceptions

KeyNotFoundException

When key does not exist in this tree.

InvalidOperationException

When parent node does not belong to this tree or node is moved to itself.

MoveTo(TKey, TreeDictionaryNode<TKey, TValue>)

Moves the provided node to a different parent node.

public void MoveTo(TKey parentKey, TreeDictionaryNode<TKey, TValue> node)

Parameters

parentKey TKey

Parent node's key.

node TreeDictionaryNode<TKey, TValue>

Node to move.

Remarks

This operation is equivalent to removing the node from this tree and re-adding it to the specified parent node.

Exceptions

KeyNotFoundException

When parentKey does not exist in this tree.

InvalidOperationException

When node does not belong to this tree or it's moved to itself.

MoveTo(TKey, TKey)

Moves the node associated with the provided key to a different parent node.

public TreeDictionaryNode<TKey, TValue> MoveTo(TKey parentKey, TKey key)

Parameters

parentKey TKey

Parent node's key.

key TKey

Key of the node to move.

Returns

TreeDictionaryNode<TKey, TValue>

Node associated with the provided key.

Remarks

This operation is equivalent to removing the node from this tree and re-adding it to the specified parent node.

Exceptions

KeyNotFoundException

When parentKey or key does not exist in this tree.

InvalidOperationException

When node is moved to itself.

Remove(TreeDictionaryNode<TKey, TValue>)

Removes the provided node from this tree.

public void Remove(TreeDictionaryNode<TKey, TValue> node)

Parameters

node TreeDictionaryNode<TKey, TValue>

Node to remove.

Remarks

When the removed node is the root node, then its first child becomes the new root node and the following children become that new root node's children, otherwise removed node's children become its parent's children.

Exceptions

InvalidOperationException

When node does not belong to this tree.

Remove(TKey)

Removes the element with the specified key from the IDictionary<TKey, TValue>.

public bool Remove(TKey key)

Parameters

key TKey

The key of the element to remove.

Returns

bool

true if the element is successfully removed; otherwise, false. This method also returns false if key was not found in the original IDictionary<TKey, TValue>.

Remarks

When the removed node is the root node, then its first child becomes the new root node and the following children become that new root node's children, otherwise removed node's children become its parent's children.

Exceptions

ArgumentNullException

key is null.

NotSupportedException

The IDictionary<TKey, TValue> is read-only.

Remove(TKey, out TValue)

Removes a node associated with the provided key from this tree.

public bool Remove(TKey key, out TValue removed)

Parameters

key TKey

Key of the node to remove.

removed TValue

out parameter that returns removed node's value.

Returns

bool

true when the node has been removed, otherwise false.

Remarks

When the removed node is the root node, then its first child becomes the new root node and the following children become that new root node's children, otherwise removed node's children become its parent's children.

RemoveSubtree(TreeDictionaryNode<TKey, TValue>)

Removes the provided node and all of its descendants from this tree.

public int RemoveSubtree(TreeDictionaryNode<TKey, TValue> node)

Parameters

node TreeDictionaryNode<TKey, TValue>

Root node of the sub-tree to remove.

Returns

int

Number of removed nodes.

Exceptions

InvalidOperationException

When node does not belong to this tree.

RemoveSubtree(TKey)

Removes the node associated with the provided key and all of its descendants from this tree.

public int RemoveSubtree(TKey key)

Parameters

key TKey

Kee of the root node of the sub-tree to remove.

Returns

int

Number of removed nodes.

SetRoot(TreeDictionaryNode<TKey, TValue>)

Adds the provided node to this tree as a root node.

public void SetRoot(TreeDictionaryNode<TKey, TValue> node)

Parameters

node TreeDictionaryNode<TKey, TValue>

Node to set as root.

Remarks

Old root node, if exists, will be attached to the new root node as its child.

Exceptions

InvalidOperationException

When node already belongs to any tree.

ArgumentException

When node's key already exists in this tree.

SetRoot(TKey, TValue)

Adds the provided (key, value) pair to this tree as a root node.

public TreeDictionaryNode<TKey, TValue> SetRoot(TKey key, TValue value)

Parameters

key TKey

Root's key.

value TValue

Root's value.

Returns

TreeDictionaryNode<TKey, TValue>

Created ITreeDictionaryNode<TKey, TValue> instance.

Remarks

Old root node, if exists, will be attached to the new root node as its child.

Exceptions

ArgumentException

When node's key already exists in this tree.

Swap(TreeDictionaryNode<TKey, TValue>, TreeDictionaryNode<TKey, TValue>)

Swaps position of two nodes of this tree.

public void Swap(TreeDictionaryNode<TKey, TValue> firstNode, TreeDictionaryNode<TKey, TValue> secondNode)

Parameters

firstNode TreeDictionaryNode<TKey, TValue>

First node.

secondNode TreeDictionaryNode<TKey, TValue>

Second node.

Remarks

Positions of parents and children of swapped nodes are not modified.

Exceptions

InvalidOperationException

When firstNode or secondNode do not belong to this tree.

Swap(TKey, TKey)

Swaps position of two nodes of this tree.

public void Swap(TKey firstKey, TKey secondKey)

Parameters

firstKey TKey

First node's key.

secondKey TKey

Second node's key.

Remarks

Positions of parents and children of swapped nodes are not modified.

Exceptions

KeyNotFoundException

When firstKey or secondKey do not exist in this tree.

TryGetValue(TKey, out TValue)

Gets the value associated with the specified key.

public bool TryGetValue(TKey key, out TValue result)

Parameters

key TKey

The key whose value to get.

result TValue

Returns

bool

true if the object that implements IDictionary<TKey, TValue> contains an element with the specified key; otherwise, false.

Exceptions

ArgumentNullException

key is null.