Where the structures comes from (Advanced) ¶

• Remove Interfaces: We remove all the interfaces (IStack, IQueue, IBinaryTree, IMap and IBinarySearchTree) in order to reduce overall complexity, and more importantly, to make client code simpler:
  

IStack<int> stack = Stack<int>.Empty; 
Stack<int> stack = Stack<int>.Empty; 

• Flip Real/Empty classes: Due to the previous change, the Empty version of the data structures inherit some fields that they really don't need, so what we did then was, instead of having:
  

public class Stack<T>
{
   class EmptyStack : Stack<T>
   {
       //EmptyStack implementation 
   }

   //FullStack implementation
}

public class Stack<T>
{
   class FullStack : Stack<T>
   {
       //FullStack implementation
   }

   //EmptyStack implementation 
}

• Small changes in usability: Like adding ToString to the collections, or some improvements in AVLTrees (indexer, TryGetValue, and enumerating in order).
  

• Change class names: In order to make them actually usable we had to add Immutable prefix before every collection. Otherwise they conflict with System.Collection.Generic classes.
  

ImmutableStack ¶

public class ImmutableStack<T>: IEnumerable<T>
{
   public static ImmutableStack<T> Empty { get; } //The only way to get a Empty immutable stack. 

   public bool IsEmpty { get; } //returns true if the current instance is empty.
   public ImmutableStack<T> Push(T value) //Creates a new immutable stack with value pushed in the head
   public ImmutableStack<T> Pop() //returns a new stack without the head
   public T Peek() //returns the element in the head
 
   public virtual IEnumerator<T> GetEnumerator()
   public override string ToString()
}

public static class ImmutableStackExtensions
{
    //Reverse the order of elements
    //Stack: [3]->[2]->[1]->[]
    //Result: [1]->[2]->[3]->[]
    public static ImmutableStack<T> Reverse<T>(this ImmutableStack<T> stack); 

    //Reverse the order of elements and concatenates it with initial.
    //Stack: [3]->[2]->[1]->[]
    //Initial: [4]->[]
    //Result: [1]->[2]->[3]->[4]->[]
    public static ImmutableStack<T> Reverse<T>(this ImmutableStack<T> stack, ImmutableStack<T> initial);
}

ImmutableStack<int> stack = ImmutableStack<int>.Empty;

for (int i = 0; i < 10; i++)
    stack = stack.Push(i);

Console.WriteLine(stack.ToString());
//Writes: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

while (!stack.IsEmpty)
{
    Console.Write(stack.Peek());
    stack = stack.Pop();
}
//Writes: 9876543210

Console.WriteLine(stack.ToString());
//Writes: []

ImmutableQueue ¶

public class ImmutableQueue<T> : IEnumerable<T>
{
   public static ImmutableQueue<T> Empty {get;} //The only way of getting a empty queue

   public bool IsEmpty { get; } //Returns true if the instance is empty
   public T Peek() {get;} //returns the element in the head of the queue
   public ImmutableQueue<T> Enqueue(T value) //returns a new queue with one more element in the tail
   public ImmutableQueue<T> Dequeue() //returns a new queue with  no 
 
   public IEnumerator<T> GetEnumerator()
   public override string ToString()
}

ImmutableQueue<int> queue = ImmutableQueue<int>.Empty;

for (int i = 0; i < 10; i++)
    queue = queue.Enqueue(i);

Console.WriteLine(queue.ToString());
//Writes: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

while (!queue.IsEmpty)
{
    Console.WriteLine(queue.Peek());
    queue = queue.Dequeue();
}
//Writes: 0123456789

Console.WriteLine(queue.ToString());
//Writes: []

ImmutableAVLTree ¶

public class ImmutableAVLTree<K, V> 
     where K : IComparable<K>
{
    public static ImmutableAVLTree<K, V> Empty {get;} //The only way to get the empty AVL tree

    public bool IsEmpty { get; } //Returns true if the tree is empty 


    public ImmutableAVLTree<K, V> Add(K key, V value) //Returns a new tree with key and value added
    public ImmutableAVLTree<K, V> Remove(K key) //Returns a new tree without key (and the value associated) 
    public V this[K key]{get; } //Returns the value associated with key
    public bool TryGetValue(K key, out V value)

    public ImmutableAVLTree<K, V> Search(K key)
    public bool Contains(K key) //

    public IEnumerable<K> Keys { get; } //All the keys in order
    public IEnumerable<V> Values { get; } //All the values in order
    public IEnumerable<KeyValuePair<K, V>> Pairs { get; } //All the key and values in order


    public K Key { get; } //Top node Key
    public V Value { get; } //Top node Value 
    public int Height { get; } //Top node hight (max distance to a leaf
    public ImmutableAVLTree<K, V> Left { get; } //Top node Left sub-node
    public ImmutableAVLTree<K, V> Right { get; } //Top node Right sub-node

    public override string ToString()
}

ImmutableAVLTree<int, string> tree = ImmutableAVLTree<int, string>.Empty;
tree = tree.Add(171, "Bengali");
tree = tree.Add(206, "Arabic");
tree = tree.Add(322, "Spanish");
tree = tree.Add(366, "Hindustani");
tree = tree.Add(177, "Portuguese");
tree = tree.Add(873, "Mandarin");
tree = tree.Add(309, "English");
tree = tree.Add(145, "Russian");
tree = tree.Add(122, "Japanese");
            
Console.WriteLine(tree.ToString());
//Writes:
//[122,Japanese]
//[145,Russian]
//[171,Bengali]
//[177,Portuguese]
//[206,Arabic]
//[309,English]
//[322,Spanish]
//[366,Hindustani]
//[873,Mandarin]

string name;
Console.WriteLine(tree.TryGetValue(1000, out name)); //false
Console.WriteLine(tree.TryGetValue(366, out name)); //true, and name = Hindustani

Console.WriteLine(tree[1000]); //throws KeyNotFoundExeption
Console.WriteLine(tree[366]); //Hindustani

tree = tree.Remove(1000); //throws InvalidOperationException
tree = tree.Remove(366); 

while (!tree.IsEmpty)
{
    Console.WriteLine("Key {0} Value {1}", tree.Key, tree.Value);
    tree = tree.Remove(tree.Key); 
}
//Key 206 Value Arabic
//Key 309 Value English
//Key 322 Value Spanish
//Key 171 Value Bengali
//Key 177 Value Portuguese
//Key 145 Value Russian
//Key 873 Value Mandarin
//Key 122 Value Japanese

Console.WriteLine(tree.ToString());
//{Empty}