Modify TreeSet to use Ordering instead of Order...

Modify TreeSet to use Ordering instead of Ordered to bring it inline
with TreeMap and improve performance.

7 files changed, 20 insertions, 21 deletions

diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala
index dd504e3781..edd75a617e 100644
--- a/src/compiler/scala/tools/nsc/Settings.scala
+++ b/src/compiler/scala/tools/nsc/Settings.scala
@@ -331,6 +331,7 @@ object Settings
       new OutputSetting(outputDirs, default)
   }
 
+  implicit val SettingOrdering : Ordering[Setting] = Ordering.ordered;
   /** A base class for settings of all types.
    *  Subclasses each define a `value' field of the appropriate type.
    */
diff --git a/src/compiler/scala/tools/nsc/doc/DocUtil.scala b/src/compiler/scala/tools/nsc/doc/DocUtil.scala
index 096c1b8374..ad2c4ca521 100644
--- a/src/compiler/scala/tools/nsc/doc/DocUtil.scala
+++ b/src/compiler/scala/tools/nsc/doc/DocUtil.scala
@@ -92,7 +92,7 @@ object DocUtil {
     var ts = ts0
     for (t <- ts1.iterator) {
       if (!ts.contains(t._1))
-        ts = ts.updated(t._1, new TreeSet[S]);
+        ts = ts.updated(t._1, TreeSet.empty[S](Ordering.ordered[S]));
       ts = ts.updated(t._1, merge(ts(t._1), t._2))
     }
     ts
diff --git a/src/compiler/scala/tools/nsc/doc/ModelExtractor.scala b/src/compiler/scala/tools/nsc/doc/ModelExtractor.scala
index fd954071c7..328f2713af 100644
--- a/src/compiler/scala/tools/nsc/doc/ModelExtractor.scala
+++ b/src/compiler/scala/tools/nsc/doc/ModelExtractor.scala
@@ -420,8 +420,8 @@ trait ModelExtractor {
     "[ \t]*@(exception|param|throws)[ \t]+(\\p{Graph}*)[ \t]*(.*)")
 
   def sort[E <: Entity](entities: Iterable[E]): Iterable[E] = {
-    val set = new collection.immutable.TreeSet[E]()({eA: E => new Ordered[E] {
-      def compare(eB: E): Int = {
+    val set = new collection.immutable.TreeSet[E]()(new Ordering[E] {
+      def compare(eA : E, eB: E): Int = {
         if (eA eq eB) return 0;
         (eA, eB) match {
           case (eA: ClassOrObject, eB: ClassOrObject) =>
@@ -442,10 +442,7 @@ trait ModelExtractor {
         assert(diff0 != 0)
         diff0
       }
-      override def equals(other: Any) : Boolean =
-        eA.equals(other) || (other match { case that: AnyRef => this.eq(that)
-                                           case _ => false })
-    }})
+    })
     set ++ entities
   }
 }
diff --git a/src/compiler/scala/tools/nsc/doc/ModelToXML.scala b/src/compiler/scala/tools/nsc/doc/ModelToXML.scala
index dc8f6a1771..21729b32b8 100644
--- a/src/compiler/scala/tools/nsc/doc/ModelToXML.scala
+++ b/src/compiler/scala/tools/nsc/doc/ModelToXML.scala
@@ -257,8 +257,8 @@ trait ModelToXML extends ModelExtractor {
     var seq: NodeSeq = NodeSeq.Empty
     if (xs.iterator.hasNext) {
       // alphabetic
-      val set = new scala.collection.immutable.TreeSet[entity.Member]()(mA => new Ordered[entity.Member] {
-        def compare(mB: entity.Member): Int =
+      val set = new scala.collection.immutable.TreeSet[entity.Member]()(new Ordering[entity.Member] {
+        def compare(mA : entity.Member, mB: entity.Member): Int =
           if (mA eq mB) 0
           else {
             val diff = mA.name compare mB.name
@@ -269,10 +269,6 @@ trait ModelToXML extends ModelExtractor {
               diff0
             }
           }
-        override def equals(other: Any): Boolean =
-           other match { case that: entity.Member => compare(that) == 0
-                         case that: AnyRef => this.eq(that)
-                         case _ => false }
       })++xs
       seq = seq ++ <table cellpadding="3" class="member" summary="">
       <tr><td colspan="2" class="title">{Text(category.label + " Summary")}</td></tr>
diff --git a/src/compiler/scala/tools/nsc/interactive/Positions.scala b/src/compiler/scala/tools/nsc/interactive/Positions.scala
index 141f710b88..9982e14815 100755
--- a/src/compiler/scala/tools/nsc/interactive/Positions.scala
+++ b/src/compiler/scala/tools/nsc/interactive/Positions.scala
@@ -148,6 +148,7 @@ self: Global =>
           tree setPos OffsetPosition(pos.source.get, currentPos.start)
         else {
           setChildrenPos(currentPos, children)
+          // temporary hack to work around issues with implicit resolution
           tree setPos new RangePosition(
             pos.source.get, (children map (_.pos.start)).min, pos.point, (children map (_.pos.end)).max)
         }
diff --git a/src/library/scala/Ordering.scala b/src/library/scala/Ordering.scala
index 1a30e24124..e9af2b8a94 100644
--- a/src/library/scala/Ordering.scala
+++ b/src/library/scala/Ordering.scala
@@ -94,6 +94,10 @@ object Ordering
 {
   def apply[T](implicit ord : Ordering[T]) = ord
 
+  def ordered[A <: Ordered[A]] : Ordering[A] = new Ordering[A]{
+    def compare(x : A, y : A) = x.compare(y);
+  }
+
   trait UnitOrdering extends Ordering[Unit] {
     def compare(x : Unit, y : Unit) = 0;
   }
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 151760b2c0..87d0042fdb 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -17,16 +17,16 @@ import generic._
 object TreeSet {
 
   type Coll = TreeSet[_]
-  implicit def implicitBuilder[A <% Ordered[A]]: Builder[A, TreeSet[A]] = newBuilder[A]
-  def newBuilder[A <% Ordered[A]]: Builder[A, TreeSet[A]] = new AddingBuilder(empty[A])
+  implicit def implicitBuilder[A](implicit ordering : Ordering[A]) : Builder[A, TreeSet[A]] = newBuilder[A](ordering)
+  def newBuilder[A](implicit ordering : Ordering[A]) : Builder[A, TreeSet[A]] = new AddingBuilder(empty[A](ordering))
 
   /** The empty set of this type
    */
-  def empty[A <% Ordered[A]] = new TreeSet[A]
+  def empty[A](implicit ordering : Ordering[A]) = new TreeSet[A]
 
   /** The canonical factory for this type
    */
-  def apply[A <% Ordered[A]](elems: A*) : TreeSet[A] = empty[A] ++ elems
+  def apply[A](elems: A*)(implicit ordering : Ordering[A]) : TreeSet[A] = empty[A] ++ elems
 }
 
 /** This class implements immutable sets using a tree.
@@ -36,12 +36,12 @@ object TreeSet {
  */
 
 @serializable
-class TreeSet[A <% Ordered[A]](override val size: Int, t: RedBlack[A]#Tree[Unit])
+class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit])(implicit val ordering : Ordering[A])
   extends RedBlack[A] with SortedSet[A] with SortedSetTemplate[A, TreeSet[A]] {
 
-  def isSmaller(x: A, y: A) = x < y
+  def isSmaller(x: A, y: A) = compare(x,y) < 0
 
-  def this() = this(0, null)
+  def this()(implicit ordering : Ordering[A]) = this(0, null)(ordering)
 
   protected val tree: RedBlack[A]#Tree[Unit] = if (size == 0) Empty else t
 
@@ -94,5 +94,5 @@ class TreeSet[A <% Ordered[A]](override val size: Int, t: RedBlack[A]#Tree[Unit]
   }
   override def firstKey = tree.first
   override def lastKey = tree.last
-  override def compare(a0: A, a1: A) = a0.compare(a1)
+  override def compare(a0: A, a1: A) = ordering.compare(a0, a1);
 }