diff options
author | Paul Phillips <paulp@improving.org> | 2010-02-02 19:43:07 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2010-02-02 19:43:07 +0000 |
commit | 4aeae5f9c7aea8874965539f730e9abaa077729d (patch) | |
tree | fbc62a7100cd4f143011d0deaec2880efe5a760a /src | |
parent | c8203f123f44057233cca331ceb2b823a1b67e6f (diff) | |
download | scala-4aeae5f9c7aea8874965539f730e9abaa077729d.tar.gz scala-4aeae5f9c7aea8874965539f730e9abaa077729d.tar.bz2 scala-4aeae5f9c7aea8874965539f730e9abaa077729d.zip |
Took a swing at sorting out sorting.
rewriting the Sorting methods to accept Orderings and adding a sorted
method to SeqLike, because we should all be pretty tired of writing
".sortWith(_ < _)" by now. I think it should be called "sort", not
"sorted", but that refuses to coexist gracefully with the deprecated
sort in List.
Review by moors (chosen pretty arbitrarily, someone at epfl should
review it but I don't know who deserves the nomination.)
Diffstat (limited to 'src')
14 files changed, 48 insertions, 36 deletions
diff --git a/src/compiler/scala/tools/nsc/Interpreter.scala b/src/compiler/scala/tools/nsc/Interpreter.scala index 406761eddb..34a82b987b 100644 --- a/src/compiler/scala/tools/nsc/Interpreter.scala +++ b/src/compiler/scala/tools/nsc/Interpreter.scala @@ -1129,7 +1129,7 @@ class Interpreter(val settings: Settings, out: PrintWriter) { } filterNot isSynthVarName /** Another entry point for tab-completion, ids in scope */ - def unqualifiedIds() = (unqualifiedIdNames() map (_.toString)).removeDuplicates sortWith (_ < _) + def unqualifiedIds() = (unqualifiedIdNames() map (_.toString)).removeDuplicates.sorted /** For static/object method completion */ def getClassObject(path: String): Option[Class[_]] = classLoader tryToLoadClass path diff --git a/src/compiler/scala/tools/nsc/PhaseAssembly.scala b/src/compiler/scala/tools/nsc/PhaseAssembly.scala index edced3ad56..95ccee6b9d 100644 --- a/src/compiler/scala/tools/nsc/PhaseAssembly.scala +++ b/src/compiler/scala/tools/nsc/PhaseAssembly.scala @@ -102,7 +102,7 @@ trait PhaseAssembly { self: Global => var lvl = 1 var nds = nodes.valuesIterator.filter(_.level == lvl).toList while(nds.size > 0) { - nds = nds.sortWith((n1,n2) => (n1.phasename compareTo n2.phasename) < 0) + nds = nds sortBy (_.phasename) for (n <- nds) { chain = chain ::: n.phaseobj.get } @@ -167,7 +167,7 @@ trait PhaseAssembly { self: Global => } else if (sanity.length > 1) { var msg = "Multiple phases want to run right after the phase " + sanity.head.to.phasename + "\n" msg += "Phases: " - sanity = sanity.sortWith((e1,e2) => (e1.frm.phasename compareTo e2.frm.phasename) < 0) + sanity = sanity sortBy (_.frm.phasename) for (edge <- sanity) { msg += edge.frm.phasename + ", " } diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala index 951f165f36..edfae44a1f 100644 --- a/src/compiler/scala/tools/nsc/Settings.scala +++ b/src/compiler/scala/tools/nsc/Settings.scala @@ -514,8 +514,7 @@ object Settings { // Ordered (so we can use TreeSet) def compare(that: Setting): Int = name compare that.name - def compareLists[T <% Ordered[T]](xs: List[T], ys: List[T]): Boolean = - xs.sortWith(_ < _) == ys.sortWith(_ < _) + def compareLists[T: Ordering](xs: List[T], ys: List[T]) = xs.sorted == ys.sorted // Equality def eqValues: List[Any] = List(name, value) diff --git a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala index 22d7ce90b7..8ec4464dde 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala @@ -238,7 +238,7 @@ trait Linearizers { self: ICodes => covered.size + (hs :\ 0)((h, s) => h.blocks.length + s) } - val tryBlocks = handlersByCovered.keysIterator.toList.sortWith(size(_) > size(_)) + val tryBlocks = handlersByCovered.keysIterator.toList sortBy size var result = normalLinearizer.linearize(m) diff --git a/src/compiler/scala/tools/nsc/doc/html/page/Index.scala b/src/compiler/scala/tools/nsc/doc/html/page/Index.scala index 9b8a30fa62..adc74c272f 100644 --- a/src/compiler/scala/tools/nsc/doc/html/page/Index.scala +++ b/src/compiler/scala/tools/nsc/doc/html/page/Index.scala @@ -49,7 +49,7 @@ class Index(modelRoot: Package) extends HtmlPage { <ol class="templates">{ val tpls: Map[String, Seq[DocTemplateEntity]] = (pack.templates filter (t => !t.isPackage && !isExcluded(t) )) groupBy (_.name) - for (tn <- tpls.keySet.toSeq sortWith (_.toLowerCase < _.toLowerCase)) yield { + for (tn <- tpls.keySet.toSeq sortBy (_.toLowerCase)) yield { val entries = tpls(tn) sortWith { (less, more) => less.isTrait || more.isObject } def doEntry(ety: DocTemplateEntity, firstEty: Boolean): NodeSeq = { val etyTpe = @@ -65,7 +65,7 @@ class Index(modelRoot: Package) extends HtmlPage { } }</ol> <ol class="packages"> { - for (sp <- pack.packages sortWith (_.name.toLowerCase < _.name.toLowerCase)) yield + for (sp <- pack.packages sortBy (_.name.toLowerCase)) yield <li>{ packageElem(sp) }</li> }</ol> </xml:group> diff --git a/src/compiler/scala/tools/nsc/doc/html/page/Template.scala b/src/compiler/scala/tools/nsc/doc/html/page/Template.scala index a314109b25..185288ace8 100644 --- a/src/compiler/scala/tools/nsc/doc/html/page/Template.scala +++ b/src/compiler/scala/tools/nsc/doc/html/page/Template.scala @@ -29,15 +29,15 @@ class Template(tpl: DocTemplateEntity) extends HtmlPage { </xml:group> val valueMembers = - (tpl.methods ::: tpl.values ::: (tpl.templates filter { tpl => tpl.isObject || tpl.isPackage })) sortWith (_.name < _.name) + (tpl.methods ::: tpl.values ::: (tpl.templates filter { tpl => tpl.isObject || tpl.isPackage })) sortBy (_.name) val typeMembers = - (tpl.abstractTypes ::: tpl.aliasTypes ::: (tpl.templates filter { tpl => tpl.isTrait || tpl.isClass })) sortWith (_.name < _.name) + (tpl.abstractTypes ::: tpl.aliasTypes ::: (tpl.templates filter { tpl => tpl.isTrait || tpl.isClass })) sortBy (_.name) val constructors = (tpl match { case cls: Class => cls.constructors case _ => Nil - }) sortWith (_.name < _.name) + }) sortBy (_.name) val body = <body class={ if (tpl.isTrait || tpl.isClass) "type" else "value" }> diff --git a/src/compiler/scala/tools/nsc/interactive/RefinedBuildManager.scala b/src/compiler/scala/tools/nsc/interactive/RefinedBuildManager.scala index 10bb55d5c6..10993b42fd 100644 --- a/src/compiler/scala/tools/nsc/interactive/RefinedBuildManager.scala +++ b/src/compiler/scala/tools/nsc/interactive/RefinedBuildManager.scala @@ -134,9 +134,9 @@ class RefinedBuildManager(val settings: Settings) extends Changes with BuildMana val changesOrdered = toList.map(e => { e._1.toString + " -> " + - e._2.sortWith(_.toString < _.toString).mkString("List(", ", ", ")") + e._2.sortBy(_.toString).mkString("List(", ", ", ")") }) - changesOrdered.sortWith(_ < _).mkString("Map(", ", ", ")") + changesOrdered.sorted.mkString("Map(", ", ", ")") } } val additionalDefs: mutable.HashSet[AbstractFile] = mutable.HashSet.empty diff --git a/src/compiler/scala/tools/nsc/interpreter/XMLCompletion.scala b/src/compiler/scala/tools/nsc/interpreter/XMLCompletion.scala index 18bc136ce7..67063192bd 100644 --- a/src/compiler/scala/tools/nsc/interpreter/XMLCompletion.scala +++ b/src/compiler/scala/tools/nsc/interpreter/XMLCompletion.scala @@ -31,7 +31,7 @@ class XMLCompletion(root: Node) extends CompletionAware { nodeCache(s) = node s :: res - }).sortWith (_ < _) + }).sorted } override def execute(id: String) = getNode(id) diff --git a/src/compiler/scala/tools/nsc/plugins/Plugin.scala b/src/compiler/scala/tools/nsc/plugins/Plugin.scala index d3b5c0a22d..92dcd6c534 100644 --- a/src/compiler/scala/tools/nsc/plugins/Plugin.scala +++ b/src/compiler/scala/tools/nsc/plugins/Plugin.scala @@ -133,8 +133,8 @@ object Plugin { { val alljars = jars ::: (for { dir <- dirs if dir.isDirectory - entry <- dir.toDirectory.files.toList sortWith (_.name <= _.name) - if entry.name.toLowerCase endsWith ".jar" + entry <- dir.toDirectory.files.toList sortBy (_.name) + if entry.extension == "jar" pdesc <- loadDescription(entry) if !(ignoring contains pdesc.name) } yield entry) diff --git a/src/compiler/scala/tools/nsc/symtab/classfile/Pickler.scala b/src/compiler/scala/tools/nsc/symtab/classfile/Pickler.scala index a9a9aa4397..5233868a3f 100644 --- a/src/compiler/scala/tools/nsc/symtab/classfile/Pickler.scala +++ b/src/compiler/scala/tools/nsc/symtab/classfile/Pickler.scala @@ -145,7 +145,7 @@ abstract class Pickler extends SubComponent { localChildDummy.setInfo(ClassInfoType(List(sym.tpe), EmptyScope, localChildDummy)) localChildDummy :: globals } - putChildren(sym, children.sortWith((x, y) => x isLess y)) + putChildren(sym, children sortWith (_ isLess _)) } for (annot <- staticAnnotations(sym.annotations.reverse)) putAnnotation(sym, annot) diff --git a/src/compiler/scala/tools/nsc/transform/SpecializeTypes.scala b/src/compiler/scala/tools/nsc/transform/SpecializeTypes.scala index cc607bca26..77e3757092 100644 --- a/src/compiler/scala/tools/nsc/transform/SpecializeTypes.scala +++ b/src/compiler/scala/tools/nsc/transform/SpecializeTypes.scala @@ -198,8 +198,8 @@ abstract class SpecializeTypes extends InfoTransform with TypingTransformers { val tvars = if (sym.isClass) env.keySet else specializedTypeVars(sym.info).intersect(env.keySet) val (methparams, others) = tvars.toList.partition(_.owner.isMethod) - val tvars1 = methparams.sortWith(_.name.toString < _.name.toString) - val tvars2 = others.sortWith(_.name.toString < _.name.toString) + val tvars1 = methparams sortBy (_.name.toString) + val tvars2 = others sortBy (_.name.toString) log("specName(" + sym + ") env " + env) specializedName(sym.name, tvars1 map env, tvars2 map env) } diff --git a/src/compiler/scala/tools/nsc/util/ClassPath.scala b/src/compiler/scala/tools/nsc/util/ClassPath.scala index 5b20362880..a5e62ff542 100644 --- a/src/compiler/scala/tools/nsc/util/ClassPath.scala +++ b/src/compiler/scala/tools/nsc/util/ClassPath.scala @@ -69,7 +69,7 @@ object ClassPath { val assem = Assembly.LoadFrom(assemFile.path) if (assem != null) { // DeclaringType == null: true for non-inner classes - res = assem.GetTypes().filter((typ: MSILType) => typ.DeclaringType == null) + res = assem.GetTypes() filter (_.DeclaringType == null) Sorting.stableSort(res, (t1: MSILType, t2: MSILType) => (t1.FullName compareTo t2.FullName) < 0) } res diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala index 9aa3141395..dde7b49175 100644 --- a/src/library/scala/collection/SeqLike.scala +++ b/src/library/scala/collection/SeqLike.scala @@ -814,6 +814,19 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self => */ def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sortWith(ord on f) + /** Sorts this $Coll according to the implicitly given Ordering ord. + * For a $Coll[A] coll, it is equivalent to either of: + * + * coll.sortBy(identity[A]) + * coll.sortWith(_ < _) + * + * @param ord the ordering assumed on domain `B`. + * @return a $coll consisting of the elements of this $coll + * sorted according to the ordering where `x < y` if + * `ord.lt(f(x), f(y))`. + */ + def sorted[B >: A](implicit ord: Ordering[B]): Repr = sortWith(ord) + /** Converts this $coll to a sequence. * $willNotTerminateInf * diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala index 5585457f07..c79f5d2fd2 100644 --- a/src/library/scala/util/Sorting.scala +++ b/src/library/scala/util/Sorting.scala @@ -31,24 +31,24 @@ object Sorting { * items. This doesn't quite work the way that I want yet -- K should be * bounded as viewable, but the compiler rejects that. */ - implicit def seq2RichSort[K <: Ordered[K] : ClassManifest](s: Seq[K]) = new RichSorting[K](s) + // implicit def seq2RichSort[K <: Ordered[K] : ClassManifest](s: Seq[K]) = new RichSorting[K](s) /** Quickly sort an array of Doubles. */ - def quickSort(a: Array[Double]) = sort1(a, 0, a.length) + def quickSort(a: Array[Double]) { sort1(a, 0, a.length) } - /** Quickly sort an array of items that are viewable as ordered. */ - def quickSort[K <% Ordered[K]](a: Array[K]) = sort1(a, 0, a.length) + /** Quickly sort an array of items with an implicit Ordering. */ + def quickSort[K](a: Array[K])(implicit ord: Ordering[K]) { sort1(a, 0, a.length) } /** Quickly sort an array of Ints. */ - def quickSort(a: Array[Int]) = sort1(a, 0, a.length) + def quickSort(a: Array[Int]) { sort1(a, 0, a.length) } /** Quickly sort an array of Floats. */ - def quickSort(a: Array[Float]) = sort1(a, 0, a.length) + def quickSort(a: Array[Float]) { sort1(a, 0, a.length) } /** Sort an array of K where K is Ordered, preserving the existing order * where the values are equal. */ - def stableSort[K <% Ordered[K] : ClassManifest](a: Array[K]) { - stableSort(a, 0, a.length-1, new Array[K](a.length), (a:K, b:K) => a < b) + def stableSort[K](a: Array[K])(implicit m: ClassManifest[K], ord: Ordering[K]) { + stableSort(a, 0, a.length-1, new Array[K](a.length), ord.lt _) } /** Sorts an array of <code>K</code> given an ordering function @@ -74,8 +74,8 @@ object Sorting { } /** Sorts an arbitrary sequence of items that are viewable as ordered. */ - def stableSort[K <% Ordered[K] : ClassManifest](a: Seq[K]): Array[K] = - stableSort(a, (a:K, b:K) => a < b) + def stableSort[K](a: Seq[K])(implicit m: ClassManifest[K], ord: Ordering[K]): Array[K] = + stableSort(a, ord.lt _) /** Stably sorts a sequence of items given an extraction function that will * return an ordered key from an item. @@ -84,10 +84,11 @@ object Sorting { * @param f the comparison function. * @return the sorted sequence of items. */ - def stableSort[K : ClassManifest, M <% Ordered[M]](a: Seq[K], f: K => M): Array[K] = - stableSort(a, (a: K, b: K) => f(a) < f(b)) + def stableSort[K, M](a: Seq[K], f: K => M)(implicit m: ClassManifest[K], ord: Ordering[M]): Array[K] = + stableSort(a)(m, ord on f) - private def sort1[K <% Ordered[K]](x: Array[K], off: Int, len: Int) { + private def sort1[K](x: Array[K], off: Int, len: Int)(implicit ord: Ordering[K]) { + import ord._ def swap(a: Int, b: Int) { val t = x(a) x(a) = x(b) @@ -562,7 +563,7 @@ object Sorting { 3.724737288678125E10f // 0.0f/0.0f ) - Sorting quickSort tuples + Sorting.quickSort(tuples) println(tuples.toList) Sorting quickSort integers @@ -582,8 +583,7 @@ object Sorting { * the items are ordered. * </p> */ -class RichSorting[K <: Ordered[K] : ClassManifest](s: Seq[K]) { - +class RichSorting[K](s: Seq[K])(implicit m: ClassManifest[K], ord: Ordering[K]) { /** Returns an array with a sorted copy of the RichSorting's sequence. */ def sort = Sorting.stableSort(s) |