using System;
using System.Runtime;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using VelocityDb;
using VelocityDb.Collection.BTree;
using VelocityDb.Session;

namespace TriangleCounter
{
  class TriangleCounter
  {
    static readonly string systemDir = System.IO.Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments), "VelocityDB", "Databases", "TriangleCounter");

    static int discoverTrianglesSingleCore(BTreeMap<int, int[]> edges)
    {
      int triangles = 0;
      BTreeMapIterator<int, int[]> edgesItr = edges.Iterator();
      while (edgesItr.MoveNext())
      {
        int nodeId = edgesItr.CurrentKey();
        int[] edge = edgesItr.CurrentValue();
        int stop = edge.Length - 1;
        int i = stop;
        int edgeToStart, edgeTo;
        int pos;
        while (i >= 0)
        {
          int[] edgeInfo2;
          edgeToStart = edge[i--];
          if (nodeId < edgeToStart)
          {
            if (edges.TryGetValue(edgeToStart, out edgeInfo2))
            {
              for (int j = stop; j >= i; j--)
              {
                edgeTo = edge[j];
                if (edgeToStart < edgeTo)
                {
                  pos = Array.BinarySearch<int>(edgeInfo2, edgeTo);
                  if (pos >= 0)
                  { // we know this one is connected to edgeInfo.From because it is part of edgeInfo.To
                    triangles++;
                  }
                }
                else
                  break;
              }
            }
          }
          else
            break;
        }
      }
      return triangles;
    }

    static void Main(string[] args)
    {
      long triangles = 0;
      try
      {
        using (SessionNoServer session = new SessionNoServer(systemDir))
        {
          int numberOfWorkerThreads = -1;
          if (args.Length > 0)
          {
            if (!int.TryParse(args[0], out numberOfWorkerThreads))
              Console.WriteLine("First parameter is numberOfWorkerThreads which must be an Int32");
          }
          Placement btreePlace = new Placement(40, 1, 1, 10000, 65500, true);
          Placement edgeInfoPlace = new Placement(40, 10000, 1, 10000, 65500, true);
          session.BeginUpdate();
          BTreeMap<int, int[]> edges;
          BTreeMapIterator<int, int[]> edgesItr;
          int[] edge = null;
          Database edgeDb = session.OpenDatabase(40, false, false);
          if (edgeDb != null)
          {
            session.Commit();
            session.BeginRead();
            edges = (BTreeMap<int, int[]>)session.Open(40, 1, 1, false);
          }
          else
          {
            DatabaseLocation location = session.DatabaseLocations.Default();
            //location.CompressPages = false; // no compression should make it faster (?) 
            session.NewDatabase(40, 395, "Edges");
            edges = new BTreeMap<int, int[]>(null, session, 6000);
            edges.Persist(btreePlace, session, true);
            edgesItr = edges.Iterator();
            using (StreamReader stream = new StreamReader("c:\\edges.txt", true))
            {
              int a;
              int b;
              string line;
              string[] fields;
              while ((line = stream.ReadLine()) != null)
              {
                fields = line.Split(' ');
                if (!int.TryParse(fields[0], out a))
                  break;
                b = int.Parse(fields[1]);
                if (a != b)
                {
                  if (edgesItr.CurrentKey() == a || edgesItr.GoTo(a))
                  {
                    edge = edgesItr.CurrentValue();
                    Array.Resize(ref edge, edge.Length + 1);
                    edge[edge.Length - 1] = b;
                    edgesItr.ReplaceValue(ref edge); // we need to update the value in the BTreeMap
                  }
                  else
                  {
                    edge = new int[1];
                    edge[0] = b;
                    edges.Add(a, edge);
                  }
                }
              }
            }
            edgesItr = edges.Iterator();
            while (edgesItr.MoveNext())
            {
              edge = edgesItr.CurrentValue();
              Array.Sort(edge);
              edgesItr.ReplaceValue(ref edge);
            }
            session.Commit();
            session.BeginRead();
          }
          Console.WriteLine("Number of Nodes found: " + edges.Count);
          if (numberOfWorkerThreads > 0)           
            Console.WriteLine("Start of triangle discovery using " + numberOfWorkerThreads + " threads, time is " + DateTime.Now);
          else if (numberOfWorkerThreads < 0)
            Console.WriteLine("Start of triangle discovery using system automatically selected number of threads, time is " + DateTime.Now);
          else
            Console.WriteLine("Start of triangle discovery using main thread, time is " + DateTime.Now);

          // Start counting triangles !
          if (numberOfWorkerThreads != 0)
          {
            edgesItr = edges.Iterator();
            ParallelOptions pOptions = new ParallelOptions();
            pOptions.MaxDegreeOfParallelism = numberOfWorkerThreads;
            // First type parameter is the type of the source elements
            // Second type parameter is the type of the local data (subtotal)
            Parallel.ForEach<KeyValuePair<int, int[]>, long>(edges, // source collection
              pOptions,
              () => 0, // method to initialize the local variable
              (pair, loop, subtotal) => // method invoked by the loop on each iteration
              {
                int nodeId = pair.Key;
                int[] nodeTo = pair.Value;
                int stop = nodeTo.Length - 1;
                int i = stop;
                int edgeToStart, edgeTo;
                int pos;
                while (i >= 0)
                {
                  int[] edgeInfo2;
                  edgeToStart = nodeTo[i--];
                  if (nodeId < edgeToStart)
                  {
                    if (edges.TryGetValue(edgeToStart, out edgeInfo2))
                    {
                      for (int j = stop; j >= i; j--)
                      {
                        edgeTo = nodeTo[j];
                        if (edgeToStart < edgeTo)
                        {
                          pos = Array.BinarySearch<int>(edgeInfo2, edgeTo);
                          if (pos >= 0)
                          { // we know this one is connected to edgeInfo.From because it is part of edgeInfo.To
                            subtotal++;
                          }
                        }
                        else
                          break;
                      }
                    }
                  }
                  else
                    break;
                }
                return subtotal;
              },
              // Method to be executed when all loops have completed.
              // finalResult is the final value of subtotal. supplied by the ForEach method.
              (finalResult) => Interlocked.Add(ref triangles, finalResult));
          }
          else
            triangles = discoverTrianglesSingleCore(edges);

          session.Commit();

        }
        Console.WriteLine("Number of Triangles found: " + triangles);
      }
      catch (Exception e)
      {
        System.Console.WriteLine(e);
      }
    }
  }
}