# Package net.sf.saxon.expr.sort

This package provides utility routines for sorting and grouping. Specifically, it contains a QuickSort implementation, and some `AtomicComparer` objects that handle character and numeric comparisons, together with the important `DocumentOrderIterator` which iterates over a set of nodes in document order.

The package also contains the classes to support the implementation of the XSLT 2.0 instruction `xsl:for-each-group`, and some utilities for maintaining sets and maps whose keys are unboxed integer values.

- Interface Summary
  Interface | Description
  --- | ---
  AtomicComparer | Interface representing an object that can be used to compare two XPath atomic values for equality or for ordering.
  AtomicMatchKey | Marker interface to identify an object that acts as a surrogate for an atomic value, with the property that if two atomic values are equal under the XPath 'eq' operator, then their corresponding surrogates are equal under the Java equals() comparison (and by implication, they have equal hash codes).
  GroupIterator | A GroupIterator is an iterator that iterates over a sequence of groups.
  ItemOrderComparer | A Comparer used for comparing nodes in document order, or items in merge order
  SortKeyEvaluator | Callback interface used to evaluate sort keys.

- Class Summary
  Class | Description
  --- | ---
  AlphanumericCollator | A Comparer that treats strings as an alternating sequence of alpha parts and numeric parts.
  AtomicSortComparer | An AtomicComparer used for comparing atomic values of arbitrary item types.
  CalendarValueComparer | A comparer specifically for comparing two date, time, or dateTime values
  CaseFirstCollator | A StringCollator that sorts lowercase before uppercase, or vice versa.
  CodepointCollatingComparer | An AtomicComparer used for comparing strings, untypedAtomic values, and URIs using the Unicode codepoint collation.
  CodepointCollator | A collating sequence that uses Unicode codepoint ordering
  CollatingAtomicComparer | An AtomicComparer used for comparing strings, untypedAtomic values, and URIs using a collation.
  CollationMatchKey | A match key for comparing strings under a collation.
  ComparableAtomicValueComparer | A comparer for comparing two "ordinary" atomic values, where the values implement the Comparable interface and the equals() method with the appropriate XPath semantics.
  ConditionalSorter | An expression that sorts an underlying sequence into document order if some condition is true, or that returns the sequence "as is" (knowing that it doesn't need sorting) if the condition is false.
  DecimalSortComparer | An AtomicComparer used for sorting values that are known to be instances of xs:decimal (including xs:integer), It also supports a separate method for getting a collation key to test equality of items
  DescendingComparer | A Comparer used for comparing descending keys.
  DocumentOrderIterator | DocumentOrderIterator takes as input an iteration of nodes in any order, and returns as output an iteration of the same nodes in document order, eliminating any duplicates.
  DocumentSorter | A DocumentSorter is an expression that sorts a sequence of nodes into document order.
  DoubleSortComparer | An AtomicComparer used for sorting values that are known to be numeric.
  EmptyGreatestComparer | A Comparer that modifies a base comparer by sorting empty key values and NaN values last (greatest), as opposed to the default which sorts them first.
  EmptyIntIterator | An iterator over a zero-length sequence of integers
  EqualityComparer | A comparer for comparing two atomic values where (a) equals is defined, and is implemented using the Java equals() method, and (b) ordering is not defined, and results in a dynamic error.
  GenericAtomicComparer | An AtomicComparer used for comparing atomic values of arbitrary item types.
  GlobalOrderComparer | A Comparer used for comparing nodes in document order.
  GroupAdjacentIterator | A GroupAdjacentIterator iterates over a sequence of groups defined by xsl:for-each-group group-adjacent="x".
  GroupByIterator | A GroupByIterator iterates over a sequence of groups defined by xsl:for-each-group group-by="x".
  GroupEndingIterator | A GroupEndingIterator iterates over a sequence of groups defined by xsl:for-each-group group-ending-with="x".
  GroupMatchingIterator | A GroupMatchingIterator contains code shared between GroupStartingIterator and GroupEndingIterator
  GroupStartingIterator | A GroupStartingIterator iterates over a sequence of groups defined by xsl:for-each-group group-starting-with="x".
  GroupToBeSorted | This class is a specialization of ObjectToBeSorted for use when the sequence being sorted is a sequence of groups.
  HTML5CaseBlindCollator | A collating sequence that compares strings according to the HTML5 rules for case-blind matching.
  ItemToBeSorted | This class is a specialization of class ObjectToBeSorted for use when the sequence being sorted is a sequence of items (including tuples, which are represented as items).
  ItemWithMergeKeys | A class representing an item together with its merge keys and the name of the merge source object from which it derived, suitable for encapsulation as an ObjectValue.
  LocalOrderComparer | A Comparer used for comparing nodes in document order.
  LRUCache<K,​V> | An LRU cache, based on `LinkedHashMap`.
  MergeGroupingIterator | An iterator that groups the result of merging several xsl:merge input streams, identifying groups of adjacent items having the same merge key value
  MergeInstr |
  MergeInstr.MergeKeyMappingFunction | Mapping function for items encountered during the merge; the mapping function wraps the merged item and its merge keys into a single composite object
  MergeInstr.MergeSource | Inner class representing one merge source
  MergeIterator | An iterator representing the sorted merge of two merge inputs, retaining all duplicates.
  NumericComparer | A Comparer used for comparing sort keys when data-type="number".
  NumericComparer11 | A Comparer used for comparing sort keys when data-type="number".
  ObjectToBeSorted<T> | This class represents a member of a sequence that is being sorted.
  RuleBasedSubstringMatcher | This class wraps a RuleBasedCollator to provide a SubstringMatcher.
  SimpleCollation | A simple collation that just wraps a supplied Comparator
  SortedGroupIterator | A SortedGroupIterator is a modified SortedIterator.
  SortedIterator | Class to do a sorted iteration
  SortExpression | Expression equivalent to the imaginary syntax expr sortby (sort-key)+
  SortKeyDefinition | A SortKeyDefinition defines one component of a sort key.
  SortKeyDefinitionList | The class represents a list of sort key definitions in major-to-minor sort key order.
  TextComparer | A Comparer used for comparing sort keys when data-type="text".
  UcaCollatorUsingJava | This class implements (an approximation to) the UCA Collation Algorithm relying solely on the built-in Java support (that is, without using the ICU library).
  UntypedNumericComparer | A specialist comparer that implements the rules for comparing an untypedAtomic value (always the first operand) to a numeric value (always the second operand)

- Exception Summary
  Exception | Description
  --- | ---
  ComparisonException | A `ComparisonException` is a `ClassCastException` that encapsulates an `XPathException`.