From 0433209838b941d3d8e91c8aa8175641a81c8983 Mon Sep 17 00:00:00 2001
From: Francis Russell <francis@unchartedbackwaters.co.uk>
Date: Sat, 7 Apr 2012 20:55:13 +0100
Subject: [PATCH] Enable topological sorting with priority function.

---
 src/ofc/util/DirectedGraph.scala | 10 +++++++---
 src/ofc/util/Queue.scala         | 31 +++++++++++++++++++++++++------
 2 files changed, 32 insertions(+), 9 deletions(-)

diff --git a/src/ofc/util/DirectedGraph.scala b/src/ofc/util/DirectedGraph.scala
index 56f8146..6c060d0 100644
--- a/src/ofc/util/DirectedGraph.scala
+++ b/src/ofc/util/DirectedGraph.scala
@@ -2,12 +2,10 @@ package ofc.util
 import ofc.LogicError
 
 object DirectedGraph {
-
-  def topoSort(graph: DirectedGraph) : Seq[DirectedGraph#Vertex] = {
+  private def topoSort(graph: DirectedGraph, queue: Queue[DirectedGraph#Vertex]) = {
     type Vertex = DirectedGraph#Vertex
     val degrees = scala.collection.mutable.Map[Vertex, Int]()
     val result = scala.collection.mutable.ArrayBuffer[Vertex]()
-    val queue = new StackQueue[Vertex]()
 
     degrees ++= { for (v <- graph.vertices) yield (v, graph.inDegree(v)) }
     queue ++= { for (v <- graph.vertices; if graph.inDegree(v) == 0) yield v }
@@ -33,6 +31,12 @@ object DirectedGraph {
     if (degrees.values.filter(x => x>0).nonEmpty) throw new LogicError("Cycle in graph.")
     result.toSeq
   }
+
+  def topoSort(graph: DirectedGraph) : Seq[DirectedGraph#Vertex] = 
+    topoSort(graph, new StackQueue[DirectedGraph#Vertex]())
+
+  def topoSort(graph: DirectedGraph, priority: DirectedGraph#Vertex => Int) : Seq[DirectedGraph#Vertex] = 
+    topoSort(graph, new PriorityQueue[DirectedGraph#Vertex](priority))
 }
 
 class DirectedGraph extends GraphBase {
diff --git a/src/ofc/util/Queue.scala b/src/ofc/util/Queue.scala
index fea4559..e93a608 100644
--- a/src/ofc/util/Queue.scala
+++ b/src/ofc/util/Queue.scala
@@ -1,12 +1,12 @@
 package ofc.util
 import scala.collection.generic.Growable
 
-private trait Queue[A] extends Growable[A] {
+trait Queue[A] extends Growable[A] {
   def pop() : A
   def nonEmpty : Boolean
 }
 
-private class StackQueue[A] extends Queue[A] {
+class StackQueue[A] extends Queue[A] {
   private var stack = List[A]()
 
   def nonEmpty = stack.nonEmpty
@@ -27,15 +27,34 @@ private class StackQueue[A] extends Queue[A] {
   }
 }
 
-private class PriorityQueue[A](ordering: Ordering[A]) extends Queue[A] {
-  val queue = new scala.collection.mutable.PriorityQueue[A]()(ordering)
+// Nodes with smaller priorities are popped first
+class PriorityQueue[A](priority: A => Int) extends Queue[A] {
+  // This class helps create an artificial total ordering by comparing
+  // unique integers if the compare function is non-total. This is
+  // probably unnecessary since priority queues permit duplicates.
+  private class UniqueOrdering(priority: A => Int)  extends scala.math.Ordering[(A, Int)] {
+    def compare(x: (A, Int), y: (A, Int)) = {
+      val xPri = priority(x._1)
+      val yPri = priority(y._1)
+      val comparison = -xPri.compareTo(yPri)
+      
+      if (comparison != 0)
+        comparison
+      else
+        x._2.compareTo(y._2)
+    }
+  }
+
+  var uniqueID = 0
+  val queue = new scala.collection.mutable.PriorityQueue[(A, Int)]()(new UniqueOrdering(priority))
 
   def nonEmpty = queue.nonEmpty
-  def pop() = queue.dequeue()
+  def pop() = queue.dequeue()._1
   def clear() = queue.clear()
 
   def +=(e: A) = {
-    queue += e
+    queue += (e -> uniqueID)
+    uniqueID += 1
     this
   }
 }
-- 
2.47.3