using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;

namespace Ex7
{
    class LockFreePathCounter
    {
        //Count total paths from start to end of dag

        public static BigInteger count(IDAG dag)
        {
            TraversalNode[] traversalNodes = new TraversalNode[dag.NumNodes];

            for (var i = 0; i < dag.NumNodes; i += 1)
               traversalNodes[i] = new TraversalNode(dag.GetNode(i));

            LockFreeQueue<int> queue = new LockFreeQueue<int>(); // Aenderung

            queue.Enqueue(dag.StartNode.Index);
            traversalNodes[dag.StartNode.Index].numReachingPaths = 1;
            while (traversalNodes[dag.EndNode.Index].numUnfinishedPredecessors != 0)
            {
                int ni;
                if (queue.TryDequeue(out ni))
                {
                    TraversalNode n = traversalNodes[ni];
                    // Aenderung
                    Parallel.ForEach(n.node.Successors, (s) =>
                    {
                        traversalNodes[s.Index].numReachingPaths += n.numReachingPaths;
                        traversalNodes[s.Index].numUnfinishedPredecessors -= 1;

                        if (traversalNodes[s.Index].numUnfinishedPredecessors == 0)
                        {
                            queue.Enqueue(s.Index);
                        }
                    });
                }
            }
            return traversalNodes[dag.EndNode.Index].numReachingPaths;
        }

        private struct TraversalNode
        {
            public TraversalNode(IDAGNode node)
            {
                this.node = node;
                numUnfinishedPredecessors = node.NumPredecessors;
                numReachingPaths = 0;
            }
            public readonly IDAGNode node;
            public int numUnfinishedPredecessors;
            public BigInteger numReachingPaths;
        }
    }
}