The <xsl:sort> element is used to define a sort key which specifies the order in which nodes selected by either <xsl:apply-templates> or <xsl:for-each> are processed. The nodes can be sorted either in numerical or alphabetic order, and the alphabetic order may vary depeinding on the language in use. The nodes can be sorted either in ascending or descending order.

Static methods of the Sort class is responsible for generating the necessary code for invoking SortingIterators under <xsl:apply-templates> and <xsl:for-each> elements. Both these elements can have several <xsl:sort> child nodes defining primary, secondary, teriary, etc. keys. The code for <xsl:apply-templates> and <xsl:for-each> create vectors containg a Sort object for each sort key. The object methods of the Sort object encapsulate a container for key-specific data (such as the sort key itself, sort order, sort type, and such) while the static methods take a vector of Sort objects and generate the actual code.

The translate() method of the Sort object is never called. The vectors containing the Sort objects for a <xsl:apply-templates> or <xsl:for-each> element are instead passed to the static translateSortIterator() method. This method compiles code that instanciates a SortingIterator object that will pass on a node-set in a specific order to the code handling the <xsl:apply-templates> or <xsl:for-each> element.

The SortingIterator class is responsible for sorting nodes encapsulated in sort obects. These sort objects must be of a class inheriting from NodeSortRecord, a the SortingIterator object needs a factory object providing it with the correct type of objects:

Figure 1: SortingIterator

The SortingIterator class is fairly dumb and leaves much of the work to the NodeSortRecord class. The iterator gets the NodeSortRecords from the factory object and sorts them using quicksort and calling compareTo() on pairs of NodeSortRecord objects.

The static methods in the Sort class generates a class inheriting from NodeSortRecord, with the following overloaded methods:

• Class Constructor
• The class constructor is overloaded to create sort-key global tables, such as an array containing the sort order for all the sort keys and another array containg all the sort types. Different sort order/types can be specified for the different levels of sort keys, but we assume that the same language is used for all levels.
• extractValueFromDOM(int level)
• This method is called by the SortingIterator object to extract the value for a specific sort key for a node. The SortingIterator will only use this method once and will cache the returned value for later use. The method will only be called if absultely necessary.
• compareType(int level)
• This method returns the sort type for one sort key level. Returns either COMPARE_STRING or COMPARE_NUMERIC.
• sortOrder(int level)
• This method returns the sort order for one sort key level. Returns either COMPARE_ASCENDING or COMPARE_DESCENDING
• getCollator(int level)
• This method returns a Collator object for language-specific string comparisons. The same Collator is used for all levels of the key.

The compareTo() method of the NodeSortRecord base class deserves a bit of attention. It takes its own node (from the this pointer) and another node and compares, if necessary, the values for all sort keys:

	/** * Compare this sort element to another. The first level is checked first, * and we proceed to the next level only if the first level keys are * identical (and so the key values may not even be extracted from the DOM) */ public int compareTo(NodeSortRecord other) { int cmp; for (int level=0; level<_levels; level++) { // Compare the two nodes either as numeric or text values if (compareType(level) == COMPARE_NUMERIC) { final Double our = numericValue(level); final Double their = other.numericValue(level); if (our == null) return(-1); if (their == null) return(1); cmp = our.compareTo(their); } else { String our = stringValue(level); String their = other.stringValue(level); if (our == null) return(-1); if (their == null) return(1); cmp = getCollator().compare(our,their); } // Return inverse compare value if inverse sort order if (cmp != 0) { if (sortOrder(level) == COMPARE_DESCENDING) return(0 - cmp); else return(cmp); } } return(0); }

The two methods stringValue(int level) and numericValue(int level) return values for one level of the sort key of a node. These methods cache these values after they are first read so that the DOM.getNodeValue() is only called once. Also, the algorithm used for these two methods assure that DOM.getNodeValue() is only called when needed. The value for a node's secondary sort key is never retrieved if the node can be uniquely identified by its primary key.

After the static methods of the Sort class has generated the new class for sort objects it generates code that instanciates a new NodeSortRecordFactory object. This object is passed as a parameter to SortingIterators constructor and is used by the iterator to generate the necessary sort objects.