Trademark Logo XSLTC Design
Apache Foundation Xalan Project Xerces Project Web Consortium Oasis Open




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.


The Sort class

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

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 NodeSortRecord class

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

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);

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.


The NodeSortRecordFactory class

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.