using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading;

namespace PDP_Lab8
{
    using Graph = ConcurrentDictionary<Int32, List<Int32>>;
    using State = List<Int32>;
    using StateQueue = ConcurrentQueue<List<Int32>>;

    class Task
    {
        public Task(Graph g, StateQueue q)
        {
            m_Graph = g;
            m_Queue = q;
            m_Cycles = new List<State>();
        }

        public void Run()
        {
            Console.WriteLine("Starting thread...");
            try
            {
                while (!m_Done)
                {
                    //Thread.Sleep(new Random().Next(50, 100));
                    State currentState;
                    if (m_Queue.TryDequeue(out currentState))
                    {
                        Int32 node = currentState[currentState.Count - 1];
                        if (m_Graph.Count == currentState.Count && m_Graph[node].Contains(currentState[0]))
                        {
                            m_Cycles.Add(currentState);
                            m_Done = true;
                            return;
                        }
                        foreach (Int32 neighbour in m_Graph[node])
                        {
                            if (!currentState.Contains(neighbour))
                            {
                                State newState = new State();
                                newState.AddRange(currentState);
                                newState.Add(neighbour);
                                m_Queue.Enqueue(newState);
                            }
                        }
                    }
                }
            }
            catch { }
        }

        public Graph m_Graph;
        public StateQueue m_Queue;
        public List<State> m_Cycles;
        public bool m_Done = false;
    }

    class Program
    {
        public static Graph GenerateGraph(Int32 nrOfNodes, Int32 nrOfEdges)
        {
            Graph g = new Graph();
            Random r = new Random();
            for (Int32 i = 0; i < nrOfEdges; ++i)
            {
                Int32 x = r.Next(1, nrOfNodes + 1);
                Int32 y = r.Next(1, nrOfNodes + 1);
                while (g.ContainsKey(x) && g[x].Contains(y))
                {
                    x = r.Next(1, nrOfNodes + 1);
                    y = r.Next(1, nrOfNodes + 1);
                }

                if (g.ContainsKey(x))
                    g[x].Add(y);
                else
                    g.TryAdd(x, new State { y });
            }
            String[] lines = new String[nrOfEdges];
            Int32 edge = 0;
            foreach (Int32 node in g.Keys)
                foreach (Int32 neighbour in g[node])
                {
                    lines[edge] = node.ToString() + " " + neighbour.ToString();
                    edge++;
                }

            System.IO.File.WriteAllLines("data.txt", lines);
            return g;
        }

        public static Graph ReadGraph()
        {
            Graph g = new Graph();
            String[] text = System.IO.File.ReadAllLines("data.txt");
            foreach (String line in text)
            {
                String[] tokens = line.Split(' ');
                Int32 n1, n2;
                Int32.TryParse(tokens[0], out n1);
                Int32.TryParse(tokens[1], out n2);

                if (g.ContainsKey(n1))
                    g[n1].Add(n2);
                else
                    g.TryAdd(n1, new State{ n2 });
            }


            return g;
        }

        static void Main(string[] args)
        {
            Int32 threads = 8;
            Graph g = ReadGraph();
            StateQueue sq = new StateQueue();

            foreach (Int32 node in g.Keys)
                sq.Enqueue(new State { node });

            Task task = new Task(g, sq);
            var tasks = new System.Threading.Tasks.Task[threads];
            var watch = System.Diagnostics.Stopwatch.StartNew();
            for (Int32 i = 0; i < threads; ++i)
                tasks[i] = System.Threading.Tasks.Task.Factory.StartNew(() => task.Run());

            System.Threading.Tasks.Task.WaitAll(tasks);
            watch.Stop();
            if (task.m_Cycles.Count > 0)
            {
                Console.WriteLine("Found Hamiltonean Cycle:");
                foreach (Int32 node in task.m_Cycles[0])
                    Console.Write(node.ToString() + " ");
                Console.WriteLine();
            }
            else
                Console.WriteLine("No Hamiltonean Cycle.");
            Console.WriteLine("Total runtime: " + watch.ElapsedMilliseconds.ToString() + "ms.");
        }
    }
}