From 8bcb2ca758fccd454d0c490e4def551ac6887425 Mon Sep 17 00:00:00 2001
From: Francis Russell <francis@unchartedbackwaters.co.uk>
Date: Fri, 6 Apr 2012 19:12:14 +0100
Subject: [PATCH] Reimplement transitive closure for better reuse.

---
 src/ofc/codegen/ProducerStatement.scala | 17 +++++-----------
 src/ofc/util/Ordering.scala             | 26 +++++++------------------
 2 files changed, 12 insertions(+), 31 deletions(-)

diff --git a/src/ofc/codegen/ProducerStatement.scala b/src/ofc/codegen/ProducerStatement.scala
index 52cbba3..c79e169 100644
--- a/src/ofc/codegen/ProducerStatement.scala
+++ b/src/ofc/codegen/ProducerStatement.scala
@@ -4,19 +4,12 @@ import ofc.util.Ordering
 class ProducerStatement extends Statement {
   object Context {
     def sort(contexts: Seq[Context]) : Seq[Context] = {
-      val ordering = scala.collection.mutable.Set[(Context, Context)]()
-      for(c1 <- contexts; c2 <- contexts)
-        (c1.tryCompare(c2)) match {
-          case Some(x) => {
-            if (x<0) 
-              ordering += (c1 -> c2)
-            else if (x>0)
-              ordering += (c2 -> c1)
-          }
-          case None => ()
-        }
+      def pathFunction(c1: Context, c2: Context) = c1.tryCompare(c2) match {
+        case Some(x) if x<0 => true
+        case _ => false
+      }
 
-      val totalOrdering = Ordering.transitiveClosure(ordering.toSet)
+      val totalOrdering = Ordering.transitiveClosure(contexts, pathFunction(_: Context, _: Context))
       contexts.sortWith((a,b) => totalOrdering.contains(a,b))
     }
   }
diff --git a/src/ofc/util/Ordering.scala b/src/ofc/util/Ordering.scala
index bd6fd46..3bc1c09 100644
--- a/src/ofc/util/Ordering.scala
+++ b/src/ofc/util/Ordering.scala
@@ -1,26 +1,14 @@
 package ofc.util
-import scala.annotation.tailrec
 
 object Ordering {
-  
-  @tailrec
-  def transitiveClosure[T](ordering: Set[(T, T)]) : Set[(T, T)] = {
-    def step[T](ordering: Set[(T, T)]) = {
-      val newOrdering = scala.collection.mutable.Set[(T, T)]()
-      newOrdering ++= ordering
+  def transitiveClosure[T](nodes: Seq[T], hasPath: (T,T) => Boolean) : Set[(T,T)] = {
+    val ordering = scala.collection.mutable.Set[(T, T)]()
+    ordering ++= { for(n1 <- nodes; n2 <- nodes; if hasPath(n1, n2)) yield (n1 -> n2) }
 
-      for ((a1,a2) <- ordering; (b1, b2) <- ordering; if a2 == b1)
-        newOrdering += (a1 -> b2)
+    for(via <- nodes; start <- nodes; end <- nodes)
+      if (!ordering.contains(start -> end) && ordering.contains(start -> via) && ordering.contains(via -> end))
+        ordering += (start -> end)
 
-      assert(newOrdering.size >= ordering.size)
-      newOrdering.toSet
-    }
-
-    val stepped = step(ordering)
-
-    if (stepped.size == ordering.size)
-      ordering
-    else
-      transitiveClosure(stepped)
+    ordering.toSet
   }
 }
-- 
2.47.3