namespace NesterovskyBros
{
  using System;

  using System.Collections.Generic;
  using NesterovskyBros.Collections.AVL;

  using Pair = System.Collections.Generic.KeyValuePair<string, int>;
  using Navigator = NesterovskyBros.Collections.AVL.
    TreeNavigator<System.Collections.Generic.KeyValuePair<string, int>>;
  using System.Diagnostics;


  public class Program
  {
    public static void Main(string[] args)
    {
      // Plan:
      // 1. Populate the tree.
      // 2. Print tree.
      // 3. Clone navigator to store branch point.
      // 4. Delete nodes.
      // 5. Print updated tree.
      // 6. Print tree kept in the branch point.

      // Action:
      // 1. Populate the tree.
      Navigator navigator = new Navigator();

      for(int i = 0; i < 17; ++i)
      {
        navigator.Insert(new Pair("Value " + i.ToString("00"), i));
      }

      // 2. Print tree.
      Console.WriteLine("Original navigator:");
      Print(navigator, 0);
      Console.WriteLine("------------------");
      Console.WriteLine();

      // 3. Clone navigator to store branch point.
      Navigator safepointNavigator = navigator.Clone();

      // 4. Delete nodes.
      navigator.RemoveAt(15);
      navigator.RemoveAt(3);

      // 5. Print updated tree.
      Console.WriteLine("Navigator with some nodes deleted:");
      Print(navigator, 0);
      Console.WriteLine("------------------");
      Console.WriteLine();

      // 6. Print tree kept in the branch point.
      Console.WriteLine("Navigator at branch point:");
      Print(safepointNavigator, 0);
      Console.WriteLine("------------------");
      Console.WriteLine();

      int prime = 750000007;
      int iterations = 100;

      Converter<int, int> converter = i => i;
      //Converter<int, long> converter = i => i;
      //Converter<int, string> converter = i => i.ToString();
      //Converter<int, TimeSpan> converter = i => TimeSpan.FromTicks(i);

      MapTest(converter, iterations, prime, 10);
      MapTest(converter, iterations, prime, 50);
      MapTest(converter, iterations, prime, 100);
      MapTest(converter, iterations, prime, 500);
      MapTest(converter, iterations, prime, 1000);
      MapTest(converter, iterations, prime, 5000);
      MapTest(converter, iterations, prime, 10000);
      MapTest(converter, iterations, prime, 50000);
      MapTest(converter, iterations, prime, 100000);
      MapTest(converter, iterations, prime, 500000);
      MapTest(converter, iterations, prime, 1000000);
      MapTest(converter, iterations, prime, 5000000);
      MapTest(converter, iterations, prime, 10000000);
    }

    private static void MapTest<K>(
      Converter<int, K> keyFunction,
      int iterations,
      int module, 
      int size)
    {
      Console.WriteLine("Size: {0}", size);

      Map<K, int> map = new Map<K, int>();

      Stopwatch watch = new Stopwatch();

      for(int c = 0; c < iterations; ++c)
      {
        map.Clear();

        watch.Start();

        // Map.
        int k = 1;

        for(int i = 0; i < size; ++i)
        {
          map[keyFunction(k)] = i;
          k = k * 2 % module;
        }

        watch.Stop();
      }

      Console.WriteLine(
        "Map population:              {0,10} ticks, per item: {1,10}", 
        watch.ElapsedTicks,
        watch.ElapsedTicks / size);

      watch.Reset();

      for(int c = 0; c < iterations; ++c)
      {
        watch.Start();

        int k = 1;

        for(int i = 0; i < size; ++i)
        {
          int value;

          map.TryGetValue(keyFunction(k), out value);
          k = k * 2 % module;
        }

        watch.Stop();
      }

      Console.WriteLine(
        "Map access:                  {0,10} ticks, per item: {1,10}",
        watch.ElapsedTicks,
        watch.ElapsedTicks / size);

      watch.Reset();

      SortedDictionary<K, int> dictionary =
        new SortedDictionary<K, int>();

      for(int c = 0; c < iterations; ++c)
      {
        dictionary.Clear();

        watch.Start();

        // Map.
        int k = 1;

        for(int i = 0; i < size; ++i)
        {
          dictionary[keyFunction(k)] = i;
          k = k * 2 % module;
        }

        watch.Stop();
      }

      Console.WriteLine(
        "SortedDictionary population: {0,10} ticks, per item: {1,10}",
        watch.ElapsedTicks,
        watch.ElapsedTicks / size);

      watch.Reset();

      for(int c = 0; c < iterations; ++c)
      {
        watch.Start();

        int k = 1;

        for(int i = 0; i < size; ++i)
        {
          int value;

          dictionary.TryGetValue(keyFunction(k), out value);
          k = k * 2 % module;
        }

        watch.Stop();
      }

      Console.WriteLine(
        "SortedDictionary access:     {0,10} ticks, per item: {1,10}",
        watch.ElapsedTicks,
        watch.ElapsedTicks / size);

      watch.Reset();

      // Verify correctness

      var heightCounter = new HeightCounter<K>();
      var verifier = new SortedDictionary<K, int>(dictionary, heightCounter);

      int mapMax = 0;
      double mapAvg = 0;
      double mapDev= 0;
      int dictionaryMax = 0;
      double dictionaryAvg = 0;
      double dictionaryDev = 0;
      
      var n = map.Navigator;
      var enumerator = verifier.GetEnumerator();
      var index = 0;

      n.MoveToRoot();
      n.MoveToLeftmost();

      do
      {
        if (!enumerator.MoveNext())
        {
          Console.WriteLine("There are more elements in the map.");

          break;
        }

        var key = n.Current.Value.Key;
        int value;

        // Console.WriteLine(n.Current.Value.Key);

        if (map.Comparer.Compare(key, enumerator.Current.Key) != 0)
        {
          Console.WriteLine("Keys are different for index: {0}.", index);
        }

        if (n.Depth > mapMax)
        {
          mapMax = n.Depth;
        }

        mapAvg += n.Depth;
        mapDev += n.Depth * n.Depth;

        heightCounter.height = 0;
        verifier.TryGetValue(key, out value);

        int height = heightCounter.height;

        if (height > dictionaryMax)
        {
          dictionaryMax = height;
        }

        dictionaryAvg += height;
        dictionaryDev += height * height;

        ++index;
      }
      while(n.MoveToSuccessor());

      if (enumerator.MoveNext())
      {
        Console.WriteLine("There are more elements in the dictionary.");
      }

      mapAvg = mapAvg / n.Count;
      mapDev = Math.Sqrt(mapDev / n.Count - mapAvg * mapAvg);

      dictionaryAvg = dictionaryAvg / n.Count;
      dictionaryDev = Math.Sqrt(dictionaryDev / n.Count - dictionaryAvg * dictionaryAvg);

      Console.WriteLine(
        "Map count:        {0}, max depth: {1}, avg: {2:0.00}, stdev: {3:0.00}",
        n.Count,
        mapMax,
        mapAvg,
        mapDev);

      Console.WriteLine(
        "Dictionary count: {0}, max depth: {1}, avg: {2:0.00}, stdev: {3:0.00}",
        dictionary.Count,
        dictionaryMax,
        dictionaryAvg,
        dictionaryDev);

      Console.WriteLine("------------------------------");
    }

    private class HeightCounter<K>: IComparer<K>
    { 
      public int height = 0;
      public IComparer<K> comparer = Comparer<K>.Default;

      public int  Compare(K x, K y)
      {
 	      ++height;

        return comparer.Compare(x, y);
      }
    }

    private static bool CheckHeight<V>(TreeNavigator<V> navigator)
    {
      int max = 0;

      navigator.MoveToRoot();
      navigator.MoveToLeftmost();

      do
      {
        if (navigator.Depth > max)
        {
          max = navigator.Depth;
        }
      }
      while (navigator.MoveToSuccessor());

      return TreeNavigator<V>.Height(navigator.Count) >= max;
    }

    private static void Print<V>(TreeNavigator<V> navigator, int indent)
    {
      for(int i = 0; i < indent; ++i)
      {
        Console.Write("  ");
      }

      Console.WriteLine(
        "depth: {0}, size: {1}, index: {2}, value: {3}",
        navigator.Depth,
        navigator.Current.Size,
        navigator.Index,
        navigator.Current.Value);

      if (navigator.MoveToLeft())
      {
        for(int i = 0; i < indent; ++i)
        {
          Console.Write("  ");
        }

        Console.WriteLine("left");

        Print(navigator, indent + 1);
        navigator.MoveToParent();
      }

      if (navigator.MoveToRight())
      {
        for(int i = 0; i < indent; ++i)
        {
          Console.Write("  ");
        }

        Console.WriteLine("right");

        Print(navigator, indent + 1);
        navigator.MoveToParent();
      }
    }
  }
}