// Edge Types:

// - Function calls:
//    - On the function itself if in this module, breakable (by prototype)
//    - On any struct, non-breakable if members are accessed or passed by value

// - Variable Declarations:
//    - On any struct, non-breakable if non-pointer

// - Struct Declarations:
//    - On any struct, non-breakable if non-pointer


// An 'edge from' is a 'dependency on'
class TopoEdge : struct
{
   public LinkElement<TopoEdge> in, out;
   External from, to;
   bool breakable;
};

class External
{
   public const char * output;
   public const char * decl;
   public int id;
   External fwdDecl;

   Array<int> protoDeps;
   Array<External> protoDepsExternal;

   public LinkElement<External> link;
   LinkList<TopoEdge, link = out> outgoing { };
   LinkList<TopoEdge, link = in> incoming { };
   int nonBreakableIncoming;
}

class FunctionExternal : External
{
}

class DeclarationExternal : External
{
}

void CreateEdge(External to, External from, bool soft)
{
   TopoEdge e { from = from, to = to, breakable = soft };
   from.outgoing.Add(e);
   to.incoming.Add(e);
   if(!soft)
      to.nonBreakableIncoming++;
}

LinkList<External, link = link> externals
{ [
   // [0]
   {
      "void FunctionTakingAStruct(TheStruct s)\n"     // - -> [3]
      "{\n"
      "   s.a.a = 1;\n"                               // ---> [4], [3]
      "   OtherFunctionTakingAnotherStruct(s.a);\n"   // ---> [1]
      "}\n",

      "void FunctionTakingAStruct(TheStruct s);\n",
      protoDeps = { [ 3 ] },
      id = 0
   },

   // [1]
   {
      "void OtherFunctionTakingAnotherStruct(OtherStruct s)\n"    // - -> [4]
      "{\n"
      "   s.b->a.a = 1;\n"                                        // ---> [3], [4]
      "\n"
      "   FunctionTakingBoth(s.b, s);\n"                            // ---> [2]
      "   FunctionTakingAStruct(s.b);\n"                          // ---> [0]
      "}\n",

      "void OtherFunctionTakingAnotherStruct(OtherStruct s);\n",
      protoDeps = { [ 4 ] },
      id = 1
   },

   // [2]
   {
      "void FunctionTakingBoth(TheStruct s, OtherStruct o) { OtherFunctionTakingAnotherStruct(o); }\n",      // - -> [3]
      protoDeps = { [ 3, 4 ] },
      id = 2
   },

   // [3]
   {
      "struct TheStruct\n"
      "{\n"
      "   OtherStruct a;\n"      // ---> [4]
      "};\n",

      "struct TheStruct;\n",
      id = 3
   },

   // [4]
   {
      "struct OtherStruct\n"
      "{\n"
      "   int a;\n"
      "   TheStruct * b;\n"      // - -> [3]
      "};\n",

      "struct OtherStruct;\n",
      id = 4
   }
] };

void FindProtoDeps(External external)
{
   if(external.protoDeps)
   {
      int c = 0;
      external.protoDepsExternal = { size = external.protoDeps.GetCount() };

      for(i : external.protoDeps)
      {
         for(e : externals; e.id == i)
         {
            external.protoDepsExternal[c++] = e;
            break;
         }
      }
   }
}

#define DebugPrint   PrintLn

/*
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)
*/
void TopoSort(LinkList<External, link = link> input)
{
   LinkList<External, link = link> L { };
   LinkList<External, link = link> S { };
   LinkList<External, link = link> B { };
   External n, next;
   int nextID = 0;

   for(n = input.first; n; n = next)
   {
      next = n.link.next;
      if(n.id >= nextID) nextID = n.id + 1;
      if(!n.incoming.count)
      {
         input.Remove((IteratorPointer)n);
         S.Add(n);
      }
      else if(!n.nonBreakableIncoming)
      {
         input.Remove((IteratorPointer)n);
         B.Add(n);
      }
   }

   while(true)
   {
      TopoEdge e, ne;
      if((n = S.first))
      {
         DebugPrint("*** Free Node: [", n.id, "]\n\t", n.output);
         S.Remove((IteratorPointer)n);
         L.Add(n);
         for(e = n.outgoing.first; e; e = ne)
         {
            External m = e.to;
            LinkList<External, link = link> list;

            DebugPrint(" This Free Node has an edge to [", m.id, "] ", m.output);
            if(m.nonBreakableIncoming)
            {
               DebugPrint("... which we think is in input");
               list = input;
            }
            else
            {
               DebugPrint("... which we think is in B");
               list = B;
            }

            if(!list.count)
               PrintLn("!!! Something's wrong !!!");
            ne = e.out.next;

            if(!e.breakable)
            {
               m.nonBreakableIncoming--;
               DebugPrint("Reducing non breakable incoming, now ", m.nonBreakableIncoming);
            }

            n.outgoing.Remove((IteratorPointer)e);
            m.incoming.Remove((IteratorPointer)e);
            delete e;

            if(!m.incoming.count)
            {
               DebugPrint("Last edge to this node taken out, moving to S...");
               list.Remove((IteratorPointer)m);
               S.Add(m);
            }
            else if(!m.nonBreakableIncoming)
            {
               DebugPrint("Last non-breakable edge to this node taken out, moving to B...");
               list.Remove((IteratorPointer)m);
               B.Add(m);
            }
         }
      }
      else if((n = B.first))
      {
         DebugPrint("Breaking some of the ", n.incoming.count, " incoming edges to [", n.id, "] ", n.output);
         B.Remove((IteratorPointer)n);

         // Break the edges of this node
         for(e = n.incoming.first; e; e = ne)
         {
            TopoEdge e2, n2;
            External m = e.from;
            External f { output = m.decl, id = nextID++ };  // Forward declaration
            m.fwdDecl = f;
            ne = e.in.next;

            // Create edges to the prototype
            if(m.protoDepsExternal)
            {
               for(i : m.protoDepsExternal)
                  CreateEdge(f, i.fwdDecl ? i.fwdDecl : i, i.fwdDecl ? true : false);
            }

            DebugPrint("Breaking edge from ", e.from.id, " to ", e.to.id);
            DebugPrint("Creating a forward decl node [", f.id, "] for [", m.id, "]");

            for(e2 = m.outgoing.first; e2; e2 = n2)
            {
               n2 = e2.out.next;
               if(e2.breakable)
               {
                  External to = e2.to;

                  if(e2 == e)
                     DebugPrint("Breaking this particular connection");
                  else
                     DebugPrint("Also redirecting connection from ", m.id, " to ", to.id, " to come from ", f.id, " instead.");
                  e2.breakable = false;
                  e2.from = f;
                  m.outgoing.Remove((IteratorPointer)e2);
                  f.outgoing.Add(e2);
                  to.nonBreakableIncoming++;
                  if(e2 != e && to.nonBreakableIncoming == 1)
                  {
                     // If this node was previously in B, move it to input
                     B.Remove((IteratorPointer)to);
                     input.Add(to);
                  }

                  //DebugPrint("Node ", e2.to.id, " now has ", e2.to.nonBreakableIncoming, " non-breakable incoming edges.");
               }
            }

            if(!f.incoming.count)
               S.Add(f);
            else if(!f.nonBreakableIncoming)
               B.Add(f);
            else
               input.Add(f);

            // Avoid needless edge breaking by processing a node as soon as one shows up in S
            if(S.first)
               break;
         }

         // Put n back in input because it now has unbreakable edges
         input.Add(n);
      }
      else
      {
         if(input.count)
            PrintLn("Error: Graph has cycles!");
         else
         {
            PrintLn("\n\n*** Success! Result: ***\n\n\n");
            input.first = L.first;
            input.last = L.last;
            input.count = L.count;
            L.first = null;
            L.last = null;
            L.count = 0;
         }
         break;
      }
   }

   delete L;
   delete S;
   delete B;
}

// 1. For Function Definitions, hard struct links must be hard as they pertain to whether a struct is instantiated/dereferenced
// 2. For function prototypes, struct links are always soft (unless they refer to a forward declaration)
// 3. For function definitions, function calls are always soft for functions / hard for prototypes
// 4. For struct members, struct links are hard if they refer to a forward declaration or if the struct is insantiated

class App : Application
{
   void Main()
   {
      // Setup test

      CreateEdge(externals[0], externals[1], true);
      CreateEdge(externals[0], externals[3], false);
      CreateEdge(externals[0], externals[4], false);

      CreateEdge(externals[1], externals[0], true);
      CreateEdge(externals[1], externals[2], false);
      CreateEdge(externals[1], externals[3], false);
      CreateEdge(externals[1], externals[4], false);

      CreateEdge(externals[2], externals[1], true);
      CreateEdge(externals[2], externals[3], true);
      CreateEdge(externals[2], externals[4], true);

      // This will insert a cycle...
      CreateEdge(externals[3], externals[4], false);
      CreateEdge(externals[4], externals[3], true);

      for(e : externals)
         FindProtoDeps(e);

      // Perform Basic Topo-Sort
      TopoSort(externals);

      // Will need to handle breakable edges

      for(e : externals)
         PrintLn(e.output);

      system("pause");
   }
}