September 5, 2010

Sorting Apex classes Sobject using apex-lang code share project !

You must be stuck up with Apex, when sorting is required on instances of user defined classes and pre-loaded Sobjects. Unfortunately standard Apex API just gives a method List.sort(), that just works with primitive data types.

So to get the job done, developers can implement their own sorting either using standard and simple bubble sort or some other complex sorting algorithm. But this approach is not good because

  • Apex governor just gives handful of script statements and limited stack depth for your biz logic.
  • Bubble sort is never a preffered sorting algo, for performance reasons(complexity) and number of high iterations. 
  • Implementing some complex sorting algo is
    • difficult
    • error prone
    • mostly suited to one user defined type or sobject

So, what’s the solution ?

We can’t do anything about governor, best would be to let developer focus on biz logic only and let sorting taken care of by some other lib, like apex-lang.

In brief apex-lang is port of very popular Java “Apache common Lang” project to Apex. More details about apex-lang are available in my previous blog post and this google code project.

apex-lang offers many Apex utility classes. One of them is ArrayUtils, it offers APIs to quick sort instances of SObject and Object(User defined types/classes). The sorting API is very similar to Java’s Collections.sort(list, comparator), where you can pass in a Comparator to compare fields of two instances for a Class.

Sorting using Apex-Lang

First prerequisite for sorting using apex-lang is implementing Comparator. Those who are from Java background, for sure know about Comparators and their importance in sorting. Those who are not, don’t need to be panic. Comparator has just a single method

Integer compare(Object o1, Object o2)

Implementations of this method, should just “compare its two arguments for order. And return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

How to write create a Comparator ?

For sake of explanation lets assume we have a user defined class called “Word”, that encapsulates a single English word. As shown below

  public class Word {
    // the real word string
    public String val {get; set;}
    public Word(String theWord) {
      if (theWord == null) theWord = '';
      val = theWord;
    }
  }

Next, we will create two comparators implementations

  1. One, that sorts the words alphabetically
  2. Second, that sorts  the words based on their length.

To start we just need to extend ObjectComparator Apex class available in apex-lang library. Below is Comparator that sorts the instances of above Word class, alphabetically !, its so simple just 3 lines of code

 
  global class WordComparator implements ObjectComparator {
    global Integer compare(Object o1, Object o2) {
      // Note we used Apex String.compareTo(String1, String2) method here
      // as it does the same i.e. return Integer based on
      // String comparision
      return ((Word)o1).val.compareTo(((Word)o2).val);
    }
  }  

Next, is the comparator implementation that will be used to sort the words by length. Again a 3 liner code :)

 
  global class WordSizeComparator implements ObjectComparator {
    global Integer compare(Object o1, Object o2) {
      // Note: we can just subtract length of two Strings 
      // to compare them
      return (((Word)o1).val.length()) - (((Word)o2).val.length());
    }
  }
  

NOTE : The above comparator implementations are good for user defined apex classes only. If you want to sort instances of SObject, then instead of implementing ObjectComparator, just implement ISObjectComparator. Everything else goes same. We need two different comparators here, because unlike java in Apex List<SObject> doesn’t gels well with List<Object>.

Here is a sample Sobject comparator for Contact, that sorts it on LastName. You must be thinking we can load the Contact’s right by just querying using ORDER BY in SOQL, but trust me its not always possible :) (Governor limits !)

  global class ContactLastNameComparator implements ISObjectComparator {
    global Integer compare(SObject o1, SObject o2) {
      // Note we used Apex String.compareTo(String1, String2) method here
      // as it does the same i.e. return Integer based on
      // String comparision
      return ((Contact)o1).LastName.compareTo(((Contact)o2).LastName);
    }
  }

 

How to sort using the Comparator ?

Once Comparator is implemented, one can start sorting using apex-lang’s

  • ArrayUtils.qsort(List<Object> theList, ObjectComparator comparator), to sort ascending
  • or, ArrayUtils.qsort(List<Object> theList, ObjectComparator comparator, Boolean sortAsc), to sort descending too.

OR, to sort instances of Sobject, use

  • ArrayUtils.qsort(List<Sobject> theList, ISObjectComparator comparator), to sort ascending
  • or, ArrayUtils.qsort(List<Sobject> theList, ISObjectComparator comparator, Boolean sortAsc), to sort descending too.
Sorting Word class or User defined type/classes

for ex. to sort instances of Word class created above, all we need to do is

List<Word> wordObjects =  // Initalize list as required;
// Sort words alphabetically 
ArrayUtils.qsort(wordObjects,new WordComparator());
// Use in this manner to sort on
// the word size/length
ArrayUtils.qsort(wordObjects,new WordSizeComparator());

Note, we created WordComparator & WordSizeComparator classes above. We just instantiated it and passed it to ArrayUtils.qsort() api.

Sorting SObjects like Contact
Contact [] cons = [select Id, LastName from Contact ];
// Note we used ContactLastNameComparator
// created above
ArrayUtils.qsort(cons, new ContactLastNameComparator());

 

How to implement Comparators for Date, Number and other primitives.

apex-lang comes with a good sample Comparator called PrimitiveComparator, this class shows how to compare each primitive data type. I suggest using this class as a learning stand point, rather using it. Because this class is meant to be too generic and it does a lot of checks, instance of etc, so you might end up in giving too much share of your governor limits like script statements to it.

Many other pre-build and example Comparator implementations available as apex classes in apex-lang project. For ex. DecimalRangeComparator,  SelectOptionComparator,  SObjectSortByNameComparator. You can use these as starting point to learn how to code different comparators. In case of any issues, feel free to comment on this post. I will for sure help you in writing the correct comparator.

When apex-lang can kill you ?

Its pretty popular saying that “with great power comes great responsibility”. Same applies very well here with apex-lang, developers get a really handy way to sort almost any object(Object/SObject). But not to forget, apex-lang is not part of standard apex api, its collection of standard apex classes. So any governor limit that applies to your Apex code, is equally applicable on apex-lang. Most important of these governor limits are

  • Number of script statements used
  • Maximum stack depth allowed.

As we all know operations like sorting involve many iterations/recursions and comparisons. So its very likely, when sorting a big data set you end up hitting any of these governor limits.

So before relying super heavily on apex-lang sorting a developer needs to check following

  1. How much script statements and other governor limits quota is required to process rest of the business logic.
  2. How big will be the collection to sort via apex-lang. This is important because, the bigger the collection will be more will the governor limits used.
  3. Sorting 1000 objects roughly takes atleast 50,000+ script statements. This figure will vary hugely, depending on Comparator implementation. In above sample comparators with 1000 words
    • WordComparator consumes 51792 script statements
    • WordSizeComparator consumes 110654 script statements. With 1091 words crash occurs with reason : “System.LimitException: Maximum stack depth reached: 173

So, based on above two points. Here is the basic rule for developer to best avoid breaking governor limits in production/UAT.

  • Match the governor limits consumed by biz-logic to the sorting logic. If business logic is already consuming too governor quota like script lines + stack depth. Then one needs to limit the amount of data sorted using apex-lang (or pick some other alternate). Developer has to know, what can be the maximum collection size to be sorted. Based on this max count the biz logic should be executed, to see if we are any where close to breaking governor limits.

To see how close you are into limits you can use Limits class provided by Apex standard library. It gives pretty handy methods like getScriptStatements(), that you can use before after costly calls as shown below.

Integer scriptsBefore = Limits.getScriptStatements();
ArrayUtils.qsort(wordObjects,new WordComparator());
Integer scriptsAfter = Limits.getScriptStatements();
System.debug(LoggingLevel.info, ' ##SCRIPT STATEMENTS USED ' + (scriptsAfter - scriptsBefore));

 

How did I benchmarked “apex-lang” with big real data set.

Creating a big data set with real random words is pretty hard to achieve programmatically, unless you apply some randomization logic to generate it. For my benchmarking purposes. I did a simple trick, i.e.

  1. Hit any blog or news portal, like http://www.nytimes.com/
  2. Copy the text of a blog post or article to some text editor. This will give you many random words, easily in thousands.
  3. Split those words on whitespace, to get a Apex String array of size equal to the number of words.

I used that String array of words to create Instances of “Word” class explained above, and that big random collection was used on different sizes to bench mark apex-lang. Hope it helps.

Why Apex-Lang should be matured to standard Apex API

Because of all this governor nightmare, how cool would it be, if some of these super helpful apex-lang classes become part of Standard Apex API. So for this reason, I am posting this as an idea on Salesforce Idea Exchange.

Please promote it, if you want to see apex-lang maturing to standard apex-api. (link to idea)

References