mondrian.olap.fun.sort

Class Sorter

java.lang.Object

mondrian.olap.fun.sort.Sorter

public class Sorter
extends Object

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Sorter.Flag Enumeration of the flags allowed to the ORDER MDX function.
static class	Sorter.ObjIntPair<T> Tuple consisting of an object and an integer.

Constructor Summary

Constructors

Constructor and Description
Sorter()

Method Summary

Modifier and Type	Method and Description
static Double	box(double d) Converts a double (primitive) value to a Double.
static Integer	box(int n) Converts an int (primitive) value to an Integer.
static int	compareHierarchically(Member m1, Member m2, boolean post) Compares a pair of members according to their positions in a prefix-order (or postfix-order, if post is true) walk over a hierarchy.
static int	compareSiblingMembers(Member m1, Member m2) Compares two members which are known to have the same parent.
static int	compareValues(double d1, double d2) Compares double-precision values according to MDX semantics.
static int	compareValues(Object value0, Object value1) Compares two cell values.
static Map<List<Member>,Object>	evaluateTuples(Evaluator evaluator, Calc exp, TupleList tuples) For each tuple in a list, evaluates an expression and creates a map from tuples to values.
static void	hierarchizeMemberList(List<Member> memberList, boolean post) Sorts a list of members into hierarchical order.
static TupleList	hierarchizeTupleList(TupleList tupleList, boolean post) Sorts a list of tuples into hierarchical order.
static boolean	listEquals(List<Member> a1, List<Member> a2)
static List<Member>	partiallySortMembers(Evaluator evaluator, List<Member> list, Calc exp, int limit, boolean desc) Partially sorts a list of Members by the value of an applied expression.
static List<List<Member>>	partiallySortTuples(Evaluator evaluator, TupleList list, Calc exp, int limit, boolean desc) Partially sorts a list of Tuples by the value of an applied expression.
static List<Member>	sortMembers(Evaluator evaluator, Iterable<Member> memberIter, List<Member> memberList, Calc exp, boolean desc, boolean brk) Helper function to sort a list of members according to an expression.
static List<Member>	sortMembers(Evaluator evaluator, Iterable<Member> memberIter, List<Member> memberList, List<SortKeySpec> keySpecList) Sorts a list of members according to a list of SortKeySpecs.
static TupleList	sortTuples(Evaluator evaluator, TupleIterable tupleIterable, TupleList tupleList, Calc exp, boolean desc, boolean brk, int arity) Sorts a list of Tuples by the value of an applied expression.
static TupleList	sortTuples(Evaluator evaluator, TupleIterable tupleIter, TupleList tupleList, List<SortKeySpec> keySpecList, int arity) Helper function to sort a list of tuples according to a list of expressions and a list of sorting flags.
static <T> List<T>	stablePartialSort(List<T> list, Comparator<T> comp, int limit) Stable partial sort of a list.
static <T> List<T>	stablePartialSort(List<T> list, Comparator<T> comp, int limit, int algorithm) Stable partial sort of a list, using a specified algorithm.
static <T> List<T>	stablePartialSortArray(List<T> list, Comparator<T> comp, int limit) Partial sort an array by sorting it and returning the first limit elements.
static <T> List<T>	stablePartialSortJulian(List<T> list, Comparator<T> comp, int limit) Julian's algorithm for stable partial sort.
static <T> List<T>	stablePartialSortMarc(List<T> list, Comparator<T> comp, int limit) Marc's original algorithm for stable partial sort of a list.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Sorter

public Sorter()

Method Detail

evaluateTuples

public static Map<List<Member>,Object> evaluateTuples(Evaluator evaluator,
                                                      Calc exp,
                                                      TupleList tuples)

For each tuple in a list, evaluates an expression and creates a map from tuples to values.

Parameters:

evaluator - Evaluation context

exp - Expression to evaluate

tuples - List of tuples exp != null exp.getType() instanceof ScalarType

sortMembers

public static List<Member> sortMembers(Evaluator evaluator,
                                       Iterable<Member> memberIter,
                                       List<Member> memberList,
                                       Calc exp,
                                       boolean desc,
                                       boolean brk)

Helper function to sort a list of members according to an expression.

NOTE: This function does not preserve the contents of the validator.

If you do not specify memberList, the method will build its own member list as it iterates over memberIter. It is acceptable if memberList and memberIter are the same list object.

If you specify memberList, the list is sorted in place, and memberList is returned.

Parameters:

evaluator - Evaluator

memberIter - Iterable over members

memberList - List of members

exp - Expression to sort on

desc - Whether to sort descending

brk - Whether to break

Returns:

sorted list (never null)

listEquals

public static boolean listEquals(List<Member> a1,
                                 List<Member> a2)

sortMembers

public static List<Member> sortMembers(Evaluator evaluator,
                                       Iterable<Member> memberIter,
                                       List<Member> memberList,
                                       List<SortKeySpec> keySpecList)

Sorts a list of members according to a list of SortKeySpecs. An in-place, Stable sort. Helper function for MDX OrderSet function.

NOTE: Does not preserve the contents of the validator.

sortTuples

public static TupleList sortTuples(Evaluator evaluator,
                                   TupleIterable tupleIterable,
                                   TupleList tupleList,
                                   Calc exp,
                                   boolean desc,
                                   boolean brk,
                                   int arity)

Sorts a list of Tuples by the value of an applied expression. Stable sort.

Helper function for MDX functions TopCount, TopSum, TopPercent, BottomCount, BottomSum, BottomPercent, but not the MDX function Order.

NOTE: This function does not preserve the contents of the validator.

If you specify tupleList, the list is sorted in place, and tupleList is returned.

Parameters:

evaluator - Evaluator

tupleIterable - Iterator over tuples

tupleList - List of tuples, if known, otherwise null

exp - Expression to sort on

desc - Whether to sort descending

brk - Whether to break

arity - Number of members in each tuple

Returns:

sorted list (never null)

partiallySortMembers

public static List<Member> partiallySortMembers(Evaluator evaluator,
                                                List<Member> list,
                                                Calc exp,
                                                int limit,
                                                boolean desc)

Partially sorts a list of Members by the value of an applied expression.

Avoids sorting the whole list, finds only the ntop (or bottom) valued Members, and returns them as a new List. Helper function for MDX functions TopCount and BottomCount.

NOTE: Does not preserve the contents of the validator.

Parameters:

list - a list of members

exp - a Calc applied to each member to find its sort-key

evaluator - Evaluator

limit - maximum count of members to return.

desc - true to sort descending (and find TopCount), false to sort ascending (and find BottomCount).

Returns:

the top or bottom members, as a new list.

sortTuples

public static TupleList sortTuples(Evaluator evaluator,
                                   TupleIterable tupleIter,
                                   TupleList tupleList,
                                   List<SortKeySpec> keySpecList,
                                   int arity)

Helper function to sort a list of tuples according to a list of expressions and a list of sorting flags.

NOTE: This function does not preserve the contents of the validator.

partiallySortTuples

public static List<List<Member>> partiallySortTuples(Evaluator evaluator,
                                                     TupleList list,
                                                     Calc exp,
                                                     int limit,
                                                     boolean desc)

Partially sorts a list of Tuples by the value of an applied expression.

Avoids sorting the whole list, finds only the n top (or bottom) valued Tuples, and returns them as a new List. Helper function for MDX functions TopCount and BottomCount.

NOTE: Does not preserve the contents of the validator. The returned list is immutable.

Parameters:

evaluator - Evaluator

list - a list of tuples

exp - a Calc applied to each tuple to find its sort-key

limit - maximum count of tuples to return.

desc - true to sort descending (and find TopCount), false to sort ascending (and find BottomCount).

Returns:

the top or bottom tuples, as a new list.

hierarchizeMemberList

public static void hierarchizeMemberList(List<Member> memberList,
                                         boolean post)

Sorts a list of members into hierarchical order. The members must belong to the same dimension.

Parameters:

memberList - List of members

post - Whether to sort in post order; if false, sorts in pre order

See Also:

hierarchizeTupleList(mondrian.calc.TupleList, boolean)

hierarchizeTupleList

public static TupleList hierarchizeTupleList(TupleList tupleList,
                                             boolean post)

Sorts a list of tuples into hierarchical order.

Parameters:

tupleList - List of tuples

post - Whether to sort in post order; if false, sorts in pre order

See Also:

hierarchizeMemberList(java.util.List, boolean)

compareValues

public static int compareValues(double d1,
                                double d2)

Compares double-precision values according to MDX semantics.

MDX requires a total order:

-inf < NULL < ... < -1 < ... < 0 < ... < NaN < +inf

but this is different than Java semantics, specifically with regard to Double.NaN.

compareValues

public static int compareValues(Object value0,
                                Object value1)

Compares two cell values.

Nulls compare last, exceptions (including the object which indicates the the cell is not in the cache yet) next, then numbers and strings are compared by value.

Parameters:

value0 - First cell value

value1 - Second cell value

Returns:

-1, 0, or 1, depending upon whether first cell value is less than, equal to, or greater than the second

box

public static Double box(double d)

Converts a double (primitive) value to a Double. DoubleNull becomes null.

box

public static Integer box(int n)

Converts an int (primitive) value to an Integer. IntegerNull becomes null.

compareHierarchically

public static int compareHierarchically(Member m1,
                                        Member m2,
                                        boolean post)

Compares a pair of members according to their positions in a prefix-order (or postfix-order, if post is true) walk over a hierarchy.

Parameters:

m1 - First member

m2 - Second member

post - Whether to sortMembers in postfix order. If true, a parent will sortMembers immediately after its last child. If false, a parent will sortMembers immediately before its first child.

Returns:

-1 if m1 collates before m2, 0 if m1 equals m2, 1 if m1 collates after m2

compareSiblingMembers

public static int compareSiblingMembers(Member m1,
                                        Member m2)

Compares two members which are known to have the same parent.

First, compare by ordinal. This is only valid now we know they're siblings, because ordinals are only unique within a parent. If the dimension does not use ordinals, both ordinals will be -1.

If the ordinals do not differ, compare using regular member comparison.

Parameters:

m1 - First member

m2 - Second member

Returns:

-1 if m1 collates less than m2, 1 if m1 collates after m2, 0 if m1 == m2.

stablePartialSort

public static <T> List<T> stablePartialSort(List<T> list,
                                            Comparator<T> comp,
                                            int limit)

Stable partial sort of a list. Returns the desired head of the list.

stablePartialSort

public static <T> List<T> stablePartialSort(List<T> list,
                                            Comparator<T> comp,
                                            int limit,
                                            int algorithm)

Stable partial sort of a list, using a specified algorithm.

stablePartialSortArray

public static <T> List<T> stablePartialSortArray(List<T> list,
                                                 Comparator<T> comp,
                                                 int limit)

Partial sort an array by sorting it and returning the first limit elements. Fastest approach if limit is a significant fraction of the list.

stablePartialSortMarc

public static <T> List<T> stablePartialSortMarc(List<T> list,
                                                Comparator<T> comp,
                                                int limit)

Marc's original algorithm for stable partial sort of a list. Now superseded by stablePartialSortJulian(java.util.List<T>, java.util.Comparator<T>, int).

stablePartialSortJulian

public static <T> List<T> stablePartialSortJulian(List<T> list,
                                                  Comparator<T> comp,
                                                  int limit)

Julian's algorithm for stable partial sort. Improves Pedro's algorithm by using a heap (priority queue) for the top limit items seen. The items on the priority queue have an ordinal field, so the queue can be used to generate a list of stably sorted items. (Heap sort is not normally stable.)

Type Parameters:

T - Element type

Parameters:

list - List to sort

comp - Comparator

limit - Maximum number of items to return

Returns:

Sorted list, containing at most limit items