From c9248e3893580ca364c53c007ca2810954fbb274 Mon Sep 17 00:00:00 2001
From: Francis Russell <francis@unchartedbackwaters.co.uk>
Date: Fri, 3 Feb 2012 17:47:53 +0000
Subject: [PATCH] Construct sorted and fused loop hierarchy.

---
 src/ofc/generators/onetep/LoopTree.scala | 13 ++++++++++---
 src/ofc/generators/onetep/Tree.scala     |  4 ++++
 2 files changed, 14 insertions(+), 3 deletions(-)

diff --git a/src/ofc/generators/onetep/LoopTree.scala b/src/ofc/generators/onetep/LoopTree.scala
index 8ef2094..a7eee75 100644
--- a/src/ofc/generators/onetep/LoopTree.scala
+++ b/src/ofc/generators/onetep/LoopTree.scala
@@ -148,7 +148,7 @@ class LoopTree private[onetep](localIndex: Option[Index]) {
 
     for (item <- subItems)
       item match {
-        case Left(space) => dependencies ++= IterationSpace.flattenPostorder(space)
+        case Left(space) => dependencies ++= space.getDependencies
         case Right(tree) => dependencies ++= tree.getDependencies
       }
 
@@ -167,7 +167,6 @@ class LoopTree private[onetep](localIndex: Option[Index]) {
     spaces.toSet
   }
 
-
   def addIterationSpace(indices: List[Index], space: IterationSpace) {
     indices match {
       case Nil => subItems += Left(space)
@@ -207,7 +206,15 @@ class LoopTree private[onetep](localIndex: Option[Index]) {
   }
 
   def sort() {
-    //TODO: Implement me!
+    def compareItems(before: Either[IterationSpace, LoopTree], after: Either[IterationSpace, LoopTree]) : Boolean =
+      (before, after) match {
+        case (Left(space1), Left(space2)) => space2.getDependencies.contains(space1)
+        case (Right(tree1), Right(tree2)) => (tree2.getDependencies & tree1.getSpaces).nonEmpty
+        case (Left(space),  Right(tree))  => tree.getDependencies.contains(space)
+        case (Right(tree),  Left(space))  => (space.getDependencies & tree.getSpaces).nonEmpty 
+      }
+
+    subItems = subItems.sortWith(compareItems(_, _))
   }
 
   def getLocalIndex = localIndex
diff --git a/src/ofc/generators/onetep/Tree.scala b/src/ofc/generators/onetep/Tree.scala
index 0b7d3ab..218fc66 100644
--- a/src/ofc/generators/onetep/Tree.scala
+++ b/src/ofc/generators/onetep/Tree.scala
@@ -54,6 +54,10 @@ trait IterationSpace {
   def getExternalIndices : Set[Index]
   def getInternalIndices : Set[Index] = (getSpatialIndices ++ getDiscreteIndices).toSet
   def getIndices : Set[Index] = getInternalIndices ++ getExternalIndices
+  def getDependencies : Set[IterationSpace] = {
+    val operands = getOperands
+    operands.toSet ++ operands.flatMap(_.getDependencies)
+  }
 }
 
 trait DataSpace extends IterationSpace {
-- 
2.47.3