In an earlier post we introduced the Collections package, which includes several ways of keeping track of objects in your application. The Collections package includes a number of very powerful features, such as search using the specification pattern and many ways of sorting your data. The latter will be elaborated upon in this article.
Comparator functions
Sorting a list always revolves around a comparator function. Such functions take two parameters, execute their logic, and return which of the parameters should be placed higher than the other. There are a number of comparator functions readily available in our package, and their usage is fairly straight forward. Take a look at some code:
//create a new list, and fill it with some integers var integers:List = new ArrayList(); integers.add(3); integers.add(1); integers.add(4); integers.add(5); integers.add(2); //now sort it integers.sort(Comparators.compareIntegers); trace(integers.toArray().toString()); //traces 1,2,3,4,5
The predefined comparator functions in the Comparators class only work on numbers and strings, but any criteria can be used for sorting if you write your own, custom comparator. In the example below, we will sort a list containing MovieClips based on their x property.
//create a new list var dots:List = new ArrayList(); //now fill it with movieclips, placed at random x values var dot:MovieClip; for(var i:int = 0; i < 10; i++) { dot = new MovieClip(); dot.x = Math.random() * 500; addChild(dot); dots.add(dot); } //then sort the list with our custom comparator function dots.sort(compareDotsX); //the custom sorting function we've written private function compareDotsX(dot1:*, dot2:*):int { var position1:Number = dot1.x; var position2:Number = dot2.x; if(position1 >; position2) { return SortOrder.LARGER; } if(position1 == position2) { return SortOrder.EQUAL; } return SortOrder.LESS; }
The sorting function in the example above uses simple conditional logic to compare the x properties of two items in a list, and returns LESS, EQUAL, or LARGER depending on the outcome. The three constants in the SortOrder class are simple integers (-1 for less, 0 for equal and 1 for larger), but their use will improve readability, as well as add another layer of abstraction to your code.
Moreover, comparator functions can be expanded with any logic you might need. Sticking to the MovieClip example, you may sort based not only the x property, but y, z, alpha, rotation, width, height or any other combination of properties. Sample implementations can be found in the Comparators class in the nl.dpdk.collections.sorting package, but any function can be used as long as it returns one of the three constants inside the SortOrder class.
Sorting methods
Other than the comparator function, there is one other major component to sorting: the sort type. For small collections such as the ones above, which sort type you choose is not very important. This will change however, when your collection grows in size and/or you search it frequency.
We have implemented a number of sorting methods in our collections package, which are represented by the constants inside the SortTypes class in nl.dpdk.collections.sorting package. The methods themselves are defined inside concrete collections classes. These are industry standard algorithms, documented both online and inside the package itself. Examples are: merge sort, shell sort, bubble sort, selection sort, insertion sort, binary insertion sort and the native sorting method used by Flash. Which sorting method you choose is dependant of a number of conditions, which are also outlined in the documentation.
These implementations itself are a nice way to get introduced to the details involved in sorting datastructures.
Changing the sort type used in the example above is done by adding a second parameter to the sort method on the ArrayList:
dots.sort(compareDotsX, SortTypes.NATIVE);
Many collection types have different concrete implementation of these search algorithms, and the default is set to a method that will deliver best performance in most use cases. Because ArrayList decorates the native array for example, the default is set to Native sort, since it is highly optimised for use by the Flash player.
One final note on this subject however is to keep in mind which algorithm you specify. The implemented sorting methods vary for each collection type, so specifying an unimplemented method will only cause it to use it’s default.
The OrderedList
One final noteworthy implementation of sorting in the Collections package is the OrderedList. This is a List adapter which applies a sorting function passed to the constructor every time a new item is added to the List. This means that each addition will take longer to process, but it being an ArrayList implementation makes it applicable to a number of use cases.
One such case could be displaying a list of high-scores in a game, as outlined in the example below.
//a list of high scores from a database var highScores:ArrayList = new ArrayList(); //500, 300, 340, 740, 150 //a new ordered list is created by passing an existing collection to the the constructor along with the comparator function //the high scores are now sorted automatically var orderedScores:OrderedList = new OrderedList(Comparators.compareIntegersDescending, highScores); //740, 500, 340, 300, 150 //now a new score is added to the ordered list //because the new score is higher than any other, it is placed at the front of the list orderedScores.add(player.getScore()); //9000 //iterate over the ordered list var iterator:IIterator = orderedScores.iterator(); while(iterator.hasNext()) { //adds each score to a list of scores, in a descending order addScoreToHighScoreDisplay(iterator.next()); // 9000, 740, 500, 340, 300, 150 }
The particulars of this list implementation, as well as the algorithms responsible for sorting, tread beyond the scope of this article, but are documented inside the package itself. In addition, the references below might offer further insight.
0 Responses to “Sorting and custom sorting”
Leave a Reply