Extensions.cs

usingSystem;
usingSystem.Collections.Generic;

namespaceDataStructures.ScapegoatTree;

publicstaticclassExtensions
{
/// <summary>
/// Flattens scapegoat tree into a list of nodes.
/// </summary>
/// <param name="root">Scapegoat tree provided as root node.</param>
/// <param name="list">An empty list.</param>
/// <typeparam name="TKey">Scapegoat tree node key type.</typeparam>
publicstaticvoidFlattenTree<TKey>(Node<TKey>root,List<Node<TKey>>list)whereTKey:IComparable
{
if(root.Left!=null)
{
FlattenTree(root.Left,list);
}

list.Add(root);

if(root.Right!=null)
{
FlattenTree(root.Right,list);
}
}

/// <summary>
/// Rebuilds a scapegoat tree from list of nodes.
/// Use with <see cref="FlattenTree{TKey}"/> method.
/// </summary>
/// <param name="list">Flattened tree.</param>
/// <param name="start">Start index.</param>
/// <param name="end">End index.</param>
/// <typeparam name="TKey">Scapegoat tree node key type.</typeparam>
/// <returns>Scapegoat tree root node.</returns>
/// <exception cref="ArgumentException">Thrown if start index is invalid.</exception>
publicstaticNode<TKey>RebuildFromList<TKey>(IList<Node<TKey>>list,intstart,intend)
whereTKey:IComparable
{
if(start>end)
{
thrownewArgumentException("The parameter's value is invalid.",nameof(start));
}

varpivot=Convert.ToInt32(Math.Ceiling(start+(end-start)/2.0));

returnnewNode<TKey>(list[pivot].Key)
{
Left=start>(pivot-1)?null:RebuildFromList(list,start,pivot-1),
Right=(pivot+1)>end?null:RebuildFromList(list,pivot+1,end),
};
}
}