Sordid Details, of a sort

The following post from Sheridan Rawlins, Yahoo! Small Business engineer, outlines two often misunderstood RTML operators, SORT, and INDEXED-SORT. The post is intended for Yahoo! Store Developers or merchants with an advanced understanding of RTML. Learn more about RTML.

Some time ago we released the SORT operator in response to the difficulty and tedium of writing a sorting template directly in the RTML language. I would like to shed some light on how it works, describe the differences in the two flavors of sort (SORT & INDEXED-SORT), and describe more advanced sorting, such as sorting on a secondary property when the first property is equivalent.

Both the SORT and INDEXED-SORT operators expect 2 variable names (var1 & var2), a sequence, and a body. The elements of sequence are examined 2 elements at a time by setting the two variables and evaluating the body to determine whether var1 is less than the var2. A copy of the sequence in sorted order is returned.

The body allows full customization of the sort order subject to some conventions which should be followed: return-style consistency, and comparison consistency.

Return-style consistency

We support two styles of body’s return value – one of the following styles should be chosen and stay consistent for a given instance of SORT or INDEXED-SORT:

1. strcmp-like: a number, which is
   1. -1 if var1 < var2
   2. 0 if var1 = var2
   3. +1 if var1 > var2
2. Binary Predicate: a symbol which is
   1. T if A < B
   2. NIL if A >= B

Comparison Consistency

The comparison must obey the following “StrictWeakOrdering” properties:

• Irreflexive: when (var1=A, var2=A), body must return 0 or NIL
• Antisemetric: when (var1=A, var2=B) returns -1 or T, then (var1=B, var2=A) must return +1 or NIL
• Transitive: when (var1=A, var2=B) returns -1 or T, and (var1=B, var2=C) returns -1 or T, then (var1=A, var2=C) must return -1 or T as well.

When to use SORT vs. INDEXED-SORT

SORT is useful when sequence directly describes the elements to be sorted.

INDEXED-SORT is useful when “expensive” lookups must be performed against each element in sequence to determine the index to sort on. The best example of this is when you have a sequence of ids (i.e. @contents) and you wish to sort on the @name property of each element.

INDEXED-SORT’s extra parameter: getindex

INDEXED-SORT first iterates across sequence setting var1 for each element and evaluating getindex. Then, it evaluates body much like sort but sets var1, and var2 to these indices. A copy of the sorted sequence is returned (indices are discarded).

I hope this helps describe the basic principles of the sort and comparison operators. I’ll provide examples and other sorting tidbits in a companion post.

Sheridan Rawlins
Yahoo! Small Business

Edit 01/11/07

In order to reverse the sort order you need to tweak the body of the INDEXED-SORT.

The current implementation of sort-item-by-price has something like the following:

sort-items-by-price (items nilgreater)

INDEXED-SORT var1 var1
             var2 var2
             getindex WITH-OBJECT var1
                        ELEMENT position 0
                                sequence @price
             sequence items
  CALL :<=>-nil.
    var1
    var2
    nilgreater

To reverse the sort you would would switch the arguments and the boolean in the call to <=>-nil. — Something like:

sort-items-by-price (items nilgreater)

INDEXED-SORT var1 var1
             var2 var2
             getindex WITH-OBJECT var1
                        ELEMENT position 0
                                sequence @price
             sequence items
  CALL :<=>-nil.
    var2
    var1
    NOT nilgreater

I hope this helps!–SCR