Improving Sort?

2 views
Skip to first unread message

Landei

unread,
Dec 31, 2010, 5:25:18 AM12/31/10
to sgine-dev
Hi!

I suggest to introduce a little bit more abstraction in Sort by using
a trait encapsulating a sort algorithm, e.g.

trait Sort {
def apply[A](array: ResizableArray[A], sortFunction: (A, A) =>
Boolean): ResizableArray[A]

def apply[A](array: ResizableArray[A])(implicit ord : Ordering[A]):
ResizableArray[A] =
apply(array, ord.lteq)
}

As you can see, this would allow to share some behavior (as shown here
by providing an alternative implementation using Orderings) between
instances. Of course we don't want to break any existing code, but we
don't have to:

object Sort {
val bubbleSort = new Sort {

@scala.annotation.tailrec
def apply[A](array: ResizableArray[A], sortFunction: (A, A) =>
Boolean): ResizableArray[A] = {
//the existing sort code goes here
}
}
}

With this solution, all existing code will work as before, but it's
easier to share functionality between different sort algorithms, and
to pass a certain Sort implementation around. Of course this change
makes only sense if other algorithms will be implemented as well, but
the comments in Sort suggest that this is the plan. I'd translate an
in-place mergesort, which seems to be the most promising choice here.

What do you think?

Happy New Year!
Daniel

Hicks, Matt

unread,
Dec 31, 2010, 8:57:12 AM12/31/10
to sgin...@googlegroups.com
That's a great idea. At the moment I don't think anything is still using the sorting system though.  I modified Sgine to use Array sorting so in Java 7 I can take advantage of timsort:

http://code.google.com/p/sgine/source/browse/src/main/scala/org/sgine/scene/view/NodeView.scala?r=2ac1f1528dc299f1b98f95a1de7644c7ffe59128#84

I've been working on a completely new replacement renderer that provides a few layers of abstraction, but the biggest feature is that it fully supports Android as well.  I'm currently in the process of changing jobs (going to work for Overstock.com at the beginning of February) and haven't had much time to work on Sgine lately though.
Reply all
Reply to author
Forward
0 new messages