001/*
002// This software is subject to the terms of the Eclipse Public License v1.0
003// Agreement, available at the following URL:
004// http://www.eclipse.org/legal/epl-v10.html.
005// You must accept the terms of that agreement to use this software.
006//
007// Copyright (C) 2002-2005 Julian Hyde
008// Copyright (C) 2005-2013 Pentaho and others
009// All Rights Reserved.
010*/
011package mondrian.olap.fun;
012
013import mondrian.calc.*;
014import mondrian.calc.impl.*;
015import mondrian.mdx.*;
016import mondrian.olap.*;
017import mondrian.olap.type.*;
018import mondrian.resource.MondrianResource;
019import mondrian.rolap.*;
020import mondrian.util.*;
021
022import org.apache.commons.collections.ComparatorUtils;
023import org.apache.commons.collections.comparators.ComparatorChain;
024import org.apache.log4j.Logger;
025
026import java.util.*;
027
028/**
029 * {@code FunUtil} contains a set of methods useful within the {@code
030 * mondrian.olap.fun} package.
031 *
032 * @author jhyde
033 * @since 1.0
034 */
035public class FunUtil extends Util {
036    private static final Logger LOGGER =
037        Logger.getLogger(FunUtil.class);
038    private static final String SORT_TIMING_NAME = "Sort";
039    private static final String SORT_EVAL_TIMING_NAME = "EvalForSort";
040
041    static final String[] emptyStringArray = new String[0];
042    private static final boolean debug = false;
043    public static final NullMember NullMember = new NullMember();
044
045    /**
046     * Special value which indicates that a {@code double} computation
047     * has returned the MDX null value. See {@link DoubleCalc}.
048     */
049    public static final double DoubleNull = 0.000000012345;
050
051    /**
052     * Special value which indicates that a {@code double} computation
053     * has returned the MDX EMPTY value. See {@link DoubleCalc}.
054     */
055    public static final double DoubleEmpty = -0.000000012345;
056
057    /**
058     * Special value which indicates that an {@code int} computation
059     * has returned the MDX null value. See {@link mondrian.calc.IntegerCalc}.
060     */
061    public static final int IntegerNull = Integer.MIN_VALUE + 1;
062
063    /**
064     * Null value in three-valued boolean logic.
065     * Actually, a placeholder until we actually implement 3VL.
066     */
067    public static final boolean BooleanNull = false;
068
069    /**
070     * Creates an exception which indicates that an error has occurred while
071     * executing a given function.
072     *
073     * @param funDef Function being executed
074     * @param message Explanatory message
075     * @return Exception that can be used as a cell result
076     */
077    public static RuntimeException newEvalException(
078        FunDef funDef,
079        String message)
080    {
081        Util.discard(funDef); // TODO: use this
082        return new MondrianEvaluationException(message);
083    }
084
085    /**
086     * Creates an exception which indicates that an error has occurred while
087     * executing a given function.
088     *
089     * @param throwable Exception
090     * @return Exception that can be used as a cell result
091     */
092    public static RuntimeException newEvalException(Throwable throwable) {
093        return new MondrianEvaluationException(
094            throwable.getClass().getName() + ": " + throwable.getMessage());
095    }
096
097    /**
098     * Creates an exception which indicates that an error has occurred while
099     * executing a given function.
100     *
101     * @param message Explanatory message
102     * @param throwable Exception
103     * @return Exception that can be used as a cell result
104     */
105    public static RuntimeException newEvalException(
106        String message,
107        Throwable throwable)
108    {
109        return new MondrianEvaluationException(
110            message
111            + ": " + Util.getErrorMessage(throwable));
112    }
113
114    public static void checkIterListResultStyles(Calc calc) {
115        switch (calc.getResultStyle()) {
116        case ITERABLE:
117        case LIST:
118        case MUTABLE_LIST:
119            break;
120        default:
121            throw ResultStyleException.generateBadType(
122                ResultStyle.ITERABLE_LIST_MUTABLELIST,
123                calc.getResultStyle());
124        }
125    }
126
127    public static void checkListResultStyles(Calc calc) {
128        switch (calc.getResultStyle()) {
129        case LIST:
130        case MUTABLE_LIST:
131            break;
132        default:
133            throw ResultStyleException.generateBadType(
134                ResultStyle.LIST_MUTABLELIST,
135                calc.getResultStyle());
136        }
137    }
138
139    /**
140     * Returns an argument whose value is a literal.
141     */
142    static String getLiteralArg(
143        ResolvedFunCall call,
144        int i,
145        String defaultValue,
146        String[] allowedValues)
147    {
148        if (i >= call.getArgCount()) {
149            if (defaultValue == null) {
150                throw newEvalException(
151                    call.getFunDef(),
152                    "Required argument is missing");
153            } else {
154                return defaultValue;
155            }
156        }
157        Exp arg = call.getArg(i);
158        if (!(arg instanceof Literal)
159            || arg.getCategory() != Category.Symbol)
160        {
161            throw newEvalException(
162                call.getFunDef(),
163                "Expected a symbol, found '" + arg + "'");
164        }
165        String s = (String) ((Literal) arg).getValue();
166        StringBuilder sb = new StringBuilder(64);
167        for (int j = 0; j < allowedValues.length; j++) {
168            String allowedValue = allowedValues[j];
169            if (allowedValue.equalsIgnoreCase(s)) {
170                return allowedValue;
171            }
172            if (j > 0) {
173                sb.append(", ");
174            }
175            sb.append(allowedValue);
176        }
177        throw newEvalException(
178            call.getFunDef(),
179            "Allowed values are: {" + sb + "}");
180    }
181
182    /**
183     * Returns the ordinal of a literal argument. If the argument does not
184     * belong to the supplied enumeration, returns -1.
185     */
186    static <E extends Enum<E>> E getLiteralArg(
187        ResolvedFunCall call,
188        int i,
189        E defaultValue,
190        Class<E> allowedValues)
191    {
192        if (i >= call.getArgCount()) {
193            if (defaultValue == null) {
194                throw newEvalException(
195                    call.getFunDef(),
196                    "Required argument is missing");
197            } else {
198                return defaultValue;
199            }
200        }
201        Exp arg = call.getArg(i);
202        if (!(arg instanceof Literal)
203            || arg.getCategory() != Category.Symbol)
204        {
205            throw newEvalException(
206                call.getFunDef(),
207                "Expected a symbol, found '" + arg + "'");
208        }
209        String s = (String) ((Literal) arg).getValue();
210        for (E e : allowedValues.getEnumConstants()) {
211            if (e.name().equalsIgnoreCase(s)) {
212                return e;
213            }
214        }
215        StringBuilder buf = new StringBuilder(64);
216        int k = 0;
217        for (E e : allowedValues.getEnumConstants()) {
218            if (k++ > 0) {
219                buf.append(", ");
220            }
221            buf.append(e.name());
222        }
223        throw newEvalException(
224            call.getFunDef(),
225            "Allowed values are: {" + buf + "}");
226    }
227
228    /**
229     * Throws an error if the expressions don't have the same hierarchy.
230     * @throws MondrianEvaluationException if expressions don't have the same
231     *     hierarchy
232     */
233    static void checkCompatible(Exp left, Exp right, FunDef funDef) {
234        final Type leftType = TypeUtil.stripSetType(left.getType());
235        final Type rightType = TypeUtil.stripSetType(right.getType());
236        if (!TypeUtil.isUnionCompatible(leftType, rightType)) {
237            throw newEvalException(
238                funDef, "Expressions must have the same hierarchy");
239        }
240    }
241
242    /**
243     * Adds every element of {@code right} which is not in {@code set}
244     * to both {@code set} and {@code left}.
245     */
246    static void addUnique(
247        TupleList left,
248        TupleList right,
249        Set<List<Member>> set)
250    {
251        assert left != null;
252        assert right != null;
253        if (right.isEmpty()) {
254            return;
255        }
256        for (int i = 0, n = right.size(); i < n; i++) {
257            List<Member> o = right.get(i);
258            if (set.add(o)) {
259                left.add(o);
260            }
261        }
262    }
263
264    /**
265     * Returns the default hierarchy of a dimension, or null if there is no
266     * default.
267     *
268     * @see MondrianResource#CannotImplicitlyConvertDimensionToHierarchy
269     *
270     * @param dimension Dimension
271     * @return Default hierarchy, or null
272     */
273    public static Hierarchy getDimensionDefaultHierarchy(Dimension dimension) {
274        final Hierarchy[] hierarchies = dimension.getHierarchies();
275        if (hierarchies.length == 1) {
276            return hierarchies[0];
277        }
278        if (MondrianProperties.instance().SsasCompatibleNaming.get()) {
279            // In SSAS 2005, dimensions with more than one hierarchy do not have
280            // a default hierarchy.
281            return null;
282        }
283        for (Hierarchy hierarchy : hierarchies) {
284            if (hierarchy.getName() == null
285                || hierarchy.getUniqueName().equals(dimension.getUniqueName()))
286            {
287                return hierarchy;
288            }
289        }
290        return null;
291    }
292
293    static List<Member> addMembers(
294        final SchemaReader schemaReader,
295        final List<Member> members,
296        final Hierarchy hierarchy)
297    {
298        // only add accessible levels
299        for (Level level : schemaReader.getHierarchyLevels(hierarchy)) {
300            addMembers(schemaReader, members, level);
301        }
302        return members;
303    }
304
305    static List<Member> addMembers(
306        SchemaReader schemaReader,
307        List<Member> members,
308        Level level)
309    {
310        List<Member> levelMembers = schemaReader.getLevelMembers(level, true);
311        members.addAll(levelMembers);
312        return members;
313    }
314
315    /**
316     * Removes every member from a list which is calculated.
317     * The list must not be null, and must consist only of members.
318     *
319     * @param memberList Member list
320     * @return List of non-calculated members
321     */
322    static List<Member> removeCalculatedMembers(List<Member> memberList)
323    {
324        List<Member> clone = new ArrayList<Member>();
325        for (Member member : memberList) {
326            if (member.isCalculated()) {
327                continue;
328            }
329            clone.add(member);
330        }
331        return clone;
332    }
333
334    /**
335     * Removes every tuple from a list which is calculated.
336     * The list must not be null, and must consist only of members.
337     *
338     * @param memberList Member list
339     * @return List of non-calculated members
340     */
341    static TupleList removeCalculatedMembers(TupleList memberList)
342    {
343        if (memberList.getArity() == 1) {
344            return new UnaryTupleList(
345                removeCalculatedMembers(
346                    memberList.slice(0)));
347        } else {
348            final TupleList clone = memberList.cloneList(memberList.size());
349            outer:
350            for (List<Member> members : memberList) {
351                for (Member member : members) {
352                    if (member.isCalculated()) {
353                        continue outer;
354                    }
355                }
356                clone.add(members);
357            }
358            return clone;
359        }
360    }
361
362    /**
363     * Returns whether {@code m0} is an ancestor of {@code m1}.
364     *
365     * @param strict if true, a member is not an ancestor of itself
366     */
367    static boolean isAncestorOf(Member m0, Member m1, boolean strict) {
368        if (strict) {
369            if (m1 == null) {
370                return false;
371            }
372            m1 = m1.getParentMember();
373        }
374        while (m1 != null) {
375            if (m1.equals(m0)) {
376                return true;
377            }
378            m1 = m1.getParentMember();
379        }
380        return false;
381    }
382
383    /**
384     * For each member in a list, evaluates an expression and creates a map
385     * from members to values.
386     *
387     * <p>If the list contains tuples, use
388     * {@link #evaluateTuples(mondrian.olap.Evaluator, mondrian.calc.Calc, mondrian.calc.TupleList)}.
389     *
390     * @param evaluator Evaluation context
391     * @param exp Expression to evaluate
392     * @param memberIter Iterable over the collection of members
393     * @param memberList List to be populated with members, or null
394     * @param parentsToo If true, evaluate the expression for all ancestors
395     *            of the members as well
396     *
397     * @pre exp != null
398     * @pre exp.getType() instanceof ScalarType
399     */
400    static Map<Member, Object> evaluateMembers(
401        Evaluator evaluator,
402        Calc exp,
403        Iterable<Member> memberIter,
404        List<Member> memberList,
405        boolean parentsToo)
406    {
407        final int savepoint = evaluator.savepoint();
408        try {
409            assert exp.getType() instanceof ScalarType;
410            Map<Member, Object> mapMemberToValue =
411                new HashMap<Member, Object>();
412            for (Member member : memberIter) {
413                if (memberList != null) {
414                    memberList.add(member);
415                }
416                while (true) {
417                    evaluator.setContext(member);
418                    Object result = exp.evaluate(evaluator);
419                    if (result == null) {
420                        result = Util.nullValue;
421                    }
422                    mapMemberToValue.put(member, result);
423                    if (!parentsToo) {
424                        break;
425                    }
426                    member = member.getParentMember();
427                    if (member == null) {
428                        break;
429                    }
430                    if (mapMemberToValue.containsKey(member)) {
431                        break;
432                    }
433                }
434            }
435            return mapMemberToValue;
436        } finally {
437            evaluator.restore(savepoint);
438        }
439    }
440
441    /**
442     * For each tuple in a list, evaluates an expression and creates a map
443     * from tuples to values.
444     *
445     * @param evaluator Evaluation context
446     * @param exp Expression to evaluate
447     * @param tuples List of tuples
448     *
449     * @pre exp != null
450     * @pre exp.getType() instanceof ScalarType
451     */
452    static Map<List<Member>, Object> evaluateTuples(
453        Evaluator evaluator,
454        Calc exp,
455        TupleList tuples)
456    {
457        final int savepoint = evaluator.savepoint();
458
459        try {
460            assert exp.getType() instanceof ScalarType;
461            final Map<List<Member>, Object> mapMemberToValue =
462                    new HashMap<List<Member>, Object>();
463            for (int i = 0, count = tuples.size(); i < count; i++) {
464                List<Member> tuple = tuples.get(i);
465                evaluator.setContext(tuple);
466                Object result = exp.evaluate(evaluator);
467                if (result == null) {
468                    result = Util.nullValue;
469                }
470                mapMemberToValue.put(tuple, result);
471            }
472            return mapMemberToValue;
473        } finally {
474            evaluator.restore(savepoint);
475        }
476    }
477
478    /**
479     * Helper function to sort a list of members according to an expression.
480     *
481     * <p>NOTE: This function does not preserve the contents of the validator.
482     *
483     * <p>If you do not specify {@code memberList}, the method
484     * will build its own member list as it iterates over {@code memberIter}.
485     * It is acceptable if {@code memberList} and {@code memberIter} are the
486     * same list object.
487     *
488     * <p>If you specify {@code memberList}, the list is sorted in place, and
489     * memberList is returned.
490     *
491     * @param evaluator Evaluator
492     * @param memberIter Iterable over members
493     * @param memberList List of members
494     * @param exp Expression to sort on
495     * @param desc Whether to sort descending
496     * @param brk Whether to break
497     * @return sorted list (never null)
498     */
499    static List<Member> sortMembers(
500        Evaluator evaluator,
501        Iterable<Member> memberIter,
502        List<Member> memberList,
503        Calc exp,
504        boolean desc,
505        boolean brk)
506    {
507        if ((memberList != null) && (memberList.size() <= 1)) {
508            return memberList;
509        }
510
511        evaluator.getTiming().markStart(SORT_EVAL_TIMING_NAME);
512        boolean timingEval = true;
513        boolean timingSort = false;
514        try {
515            // REVIEW mberkowitz 1/09: test whether precomputing
516            // values saves time.
517            Map<Member, Object> mapMemberToValue;
518            final boolean parentsToo = !brk;
519            if (memberList == null) {
520                memberList = new ArrayList<Member>();
521                mapMemberToValue = evaluateMembers(
522                    evaluator, exp, memberIter, memberList, parentsToo);
523            } else {
524                mapMemberToValue = evaluateMembers(
525                    evaluator, exp, memberIter, null, parentsToo);
526            }
527
528            MemberComparator comp;
529            if (brk) {
530                comp = new BreakMemberComparator(evaluator, exp, desc);
531            } else {
532                comp = new HierarchicalMemberComparator(evaluator, exp, desc);
533            }
534            comp.preloadValues(mapMemberToValue);
535            evaluator.getTiming().markEnd(SORT_EVAL_TIMING_NAME);
536            timingEval = false;
537            evaluator.getTiming().markStart(SORT_TIMING_NAME);
538            timingSort = true;
539            Collections.sort(memberList, comp.wrap());
540            return memberList;
541        } finally {
542            if (timingEval) {
543                evaluator.getTiming().markEnd(SORT_EVAL_TIMING_NAME);
544            } else if (timingSort) {
545                evaluator.getTiming().markEnd(SORT_TIMING_NAME);
546            }
547        }
548    }
549
550    /**
551     * Sorts a list of members according to a list of SortKeySpecs.
552     * An in-place, Stable sort.
553     * Helper function for MDX OrderSet function.
554     *
555     * <p>NOTE: Does not preserve the contents of the validator.
556     */
557    static List<Member> sortMembers(
558        Evaluator evaluator,
559        Iterable<Member> memberIter,
560        List<Member> memberList,
561        List<SortKeySpec> keySpecList)
562    {
563        if ((memberList != null) && (memberList.size() <= 1)) {
564            return memberList;
565        }
566        if (memberList == null) {
567            memberList = new ArrayList<Member>();
568            for (Member member : memberIter) {
569                memberList.add(member);
570            }
571            if (memberList.size() <= 1) {
572                return memberList;
573            }
574        }
575
576        ComparatorChain chain = new ComparatorChain();
577        for (SortKeySpec key : keySpecList) {
578            boolean brk = key.direction.brk;
579            MemberComparator comp;
580            if (brk) {
581                comp = new BreakMemberComparator(
582                    evaluator, key.key, key.direction.descending);
583            } else {
584                comp = new HierarchicalMemberComparator(
585                    evaluator, key.key, key.direction.descending);
586            }
587            comp.preloadValues(memberList);
588            chain.addComparator(comp.wrap(), false);
589        }
590
591        Collections.sort(memberList, chain);
592        return memberList;
593    }
594
595    /**
596     * Sorts a list of Tuples by the value of an applied expression. Stable
597     * sort.
598     *
599     * <p>Helper function for MDX functions TopCount, TopSum, TopPercent,
600     * BottomCount, BottomSum, BottomPercent, but not the MDX function Order.
601     *
602     * <p>NOTE: This function does not preserve the contents of the validator.
603     *
604     * <p>If you specify {@code tupleList}, the list is sorted in place, and
605     * tupleList is returned.
606     *
607     * @param evaluator Evaluator
608     * @param tupleIterable Iterator over tuples
609     * @param tupleList List of tuples, if known, otherwise null
610     * @param exp Expression to sort on
611     * @param desc Whether to sort descending
612     * @param brk Whether to break
613     * @param arity Number of members in each tuple
614     * @return sorted list (never null)
615     */
616    public static TupleList sortTuples(
617        Evaluator evaluator,
618        TupleIterable tupleIterable,
619        TupleList tupleList,
620        Calc exp,
621        boolean desc,
622        boolean brk,
623        int arity)
624    {
625        // NOTE: This method does not implement the iterable/list concept
626        // as fully as sortMembers. This is because sortMembers evaluates all
627        // sort expressions up front. There, it is efficient to unravel the
628        // iterator and evaluate the sort expressions at the same time.
629        List<List<Member>> tupleArrayList;
630        if (tupleList == null) {
631            tupleArrayList = new ArrayList<List<Member>>();
632            final TupleCursor cursor = tupleIterable.tupleCursor();
633            while (cursor.forward()) {
634                tupleArrayList.add(cursor.current());
635            }
636            if (tupleArrayList.size() <= 1) {
637                return new DelegatingTupleList(
638                    tupleIterable.getArity(),
639                    tupleArrayList);
640            }
641        } else {
642            if (tupleList.size() <= 1) {
643                return tupleList;
644            }
645            tupleArrayList = tupleList;
646        }
647
648        @SuppressWarnings({"unchecked"})
649        List<Member>[] tuples =
650            tupleArrayList.toArray(new List[tupleArrayList.size()]);
651        final DelegatingTupleList result =
652            new DelegatingTupleList(
653                tupleIterable.getArity(),
654                Arrays.asList(tuples));
655
656        Comparator<List<Member>> comparator;
657        if (brk) {
658            comparator =
659                new BreakTupleComparator(evaluator, exp, arity);
660            if (desc) {
661                comparator = Collections.reverseOrder(comparator);
662            }
663        } else {
664            comparator =
665                new HierarchicalTupleComparator(evaluator, exp, arity, desc);
666        }
667
668        Arrays.sort(tuples, comparator);
669
670        if (LOGGER.isDebugEnabled()) {
671            StringBuilder sb =
672                new StringBuilder("FunUtil.sortTuples returned:");
673            for (List<Member> tuple : tuples) {
674                sb.append("\n");
675                sb.append(tuple.toString());
676            }
677            LOGGER.debug(sb.toString());
678        }
679
680        return result;
681    }
682
683    /**
684     * Partially sorts a list of Members by the value of an applied expression.
685     *
686     * <p>Avoids sorting the whole list, finds only the <i>n</i>top (or bottom)
687     * valued Members, and returns them as a new List. Helper function for MDX
688     * functions TopCount and BottomCount.</p>
689     *
690     * <p>NOTE: Does not preserve the contents of the validator.</p>
691     *
692     * @param list a list of members
693     * @param exp a Calc applied to each member to find its sort-key
694     * @param evaluator Evaluator
695     * @param limit maximum count of members to return.
696     * @param desc true to sort descending (and find TopCount), false to sort
697     *   ascending (and find BottomCount).
698     * @return the top or bottom members, as a new list.
699     */
700    public static  List<Member> partiallySortMembers(
701        Evaluator evaluator,
702        List<Member> list,
703        Calc exp,
704        int limit,
705        boolean desc)
706    {
707        assert list.size() > 0;
708        assert limit <= list.size();
709        evaluator.getTiming().markStart(SORT_EVAL_TIMING_NAME);
710        boolean timingEval = true;
711        boolean timingSort = false;
712        try {
713            MemberComparator comp =
714                new BreakMemberComparator(evaluator, exp, desc);
715            Map<Member, Object> valueMap =
716                evaluateMembers(evaluator, exp, list, null, false);
717            evaluator.getTiming().markEnd(SORT_EVAL_TIMING_NAME);
718            timingEval = false;
719            evaluator.getTiming().markStart(SORT_TIMING_NAME);
720            timingSort = true;
721            comp.preloadValues(valueMap);
722            return stablePartialSort(list, comp.wrap(), limit);
723        } finally {
724            if (timingEval) {
725                evaluator.getTiming().markEnd(SORT_EVAL_TIMING_NAME);
726            } else if (timingSort) {
727                evaluator.getTiming().markEnd(SORT_TIMING_NAME);
728            }
729        }
730    }
731
732    /**
733     * Helper function to sort a list of tuples according to a list
734     * of expressions and a list of sorting flags.
735     *
736     * <p>NOTE: This function does not preserve the contents of the validator.
737     */
738    static TupleList sortTuples(
739        Evaluator evaluator,
740        TupleIterable tupleIter,
741        TupleList tupleList,
742        List<SortKeySpec> keySpecList,
743        int arity)
744    {
745        if (tupleList == null) {
746            tupleList = TupleCollections.createList(arity);
747            TupleCursor cursor = tupleIter.tupleCursor();
748            while (cursor.forward()) {
749                tupleList.addCurrent(cursor);
750            }
751        }
752        if (tupleList.size() <= 1) {
753            return tupleList;
754        }
755
756        ComparatorChain chain = new ComparatorChain();
757        for (SortKeySpec key : keySpecList) {
758            boolean brk = key.direction.brk;
759            boolean orderByKey =
760                key.key.isWrapperFor(MemberOrderKeyFunDef.CalcImpl.class);
761            if (brk) {
762                TupleExpMemoComparator comp =
763                    new BreakTupleComparator(evaluator, key.key, arity);
764                comp.preloadValues(tupleList);
765                chain.addComparator(comp, key.direction.descending);
766            } else if (orderByKey) {
767                TupleExpMemoComparator comp =
768                    new HierarchicalTupleKeyComparator(
769                        evaluator, key.key, arity);
770                comp.preloadValues(tupleList);
771                chain.addComparator(comp, key.direction.descending);
772            } else {
773                TupleExpComparator comp =
774                    new HierarchicalTupleComparator(
775                        evaluator, key.key, arity, key.direction.descending);
776                chain.addComparator(comp, false);
777            }
778        }
779
780        Collections.sort(tupleList, chain);
781
782        if (LOGGER.isDebugEnabled()) {
783            StringBuilder sb =
784                new StringBuilder("FunUtil.sortTuples returned:");
785            for (List<Member> tuple : tupleList) {
786                sb.append("\n");
787                sb.append(tuple.toString());
788            }
789            LOGGER.debug(sb.toString());
790        }
791
792        return tupleList;
793    }
794
795    /**
796     * Partially sorts a list of Tuples by the value of an applied expression.
797     *
798     * <p>Avoids sorting the whole list, finds only the <i>n</i> top (or bottom)
799     * valued Tuples, and returns them as a new List. Helper function for MDX
800     * functions TopCount and BottomCount.
801     *
802     * <p>NOTE: Does not preserve the contents of the validator. The returned
803     * list is immutable.
804     *
805     * @param evaluator Evaluator
806     * @param list a list of tuples
807     * @param exp a Calc applied to each tuple to find its sort-key
808     * @param limit maximum count of tuples to return.
809     * @param desc true to sort descending (and find TopCount),
810     *  false to sort ascending (and find BottomCount).
811     * @return the top or bottom tuples, as a new list.
812     */
813    public static List<List<Member>> partiallySortTuples(
814        Evaluator evaluator,
815        TupleList list,
816        Calc exp,
817        int limit,
818        boolean desc)
819    {
820        assert list.size() > 0;
821        assert limit <= list.size();
822        Comparator<List<Member>> comp =
823            new BreakTupleComparator(evaluator, exp, list.getArity());
824        if (desc) {
825            comp = Collections.reverseOrder(comp);
826        }
827        return stablePartialSort(list, comp, limit);
828    }
829
830    /**
831     * Sorts a list of members into hierarchical order. The members must belong
832     * to the same dimension.
833     *
834     * @param memberList List of members
835     * @param post Whether to sort in post order; if false, sorts in pre order
836     *
837     * @see #hierarchizeTupleList(mondrian.calc.TupleList, boolean)
838     */
839    public static void hierarchizeMemberList(
840        List<Member> memberList,
841        boolean post)
842    {
843        if (memberList.size() <= 1) {
844            return;
845        }
846        if (memberList.get(0).getDimension().isHighCardinality()) {
847            return;
848        }
849        Comparator<Member> comparator = new HierarchizeComparator(post);
850        Collections.sort(memberList, comparator);
851    }
852
853    /**
854     * Sorts a list of tuples into hierarchical order.
855     *
856     * @param tupleList List of tuples
857     * @param post Whether to sort in post order; if false, sorts in pre order
858     *
859     * @see #hierarchizeMemberList(java.util.List, boolean)
860     */
861    public static TupleList hierarchizeTupleList(
862        TupleList tupleList,
863        boolean post)
864    {
865        if (tupleList.isEmpty()) {
866            TupleCollections.emptyList(tupleList.getArity());
867        }
868        final TupleList fixedList = tupleList.fix();
869        if (tupleList.getArity() == 1) {
870            hierarchizeMemberList(fixedList.slice(0), post);
871            return fixedList;
872        }
873        Comparator<List<Member>> comparator =
874            new HierarchizeTupleComparator(fixedList.getArity(), post);
875
876        Collections.sort(fixedList, comparator);
877
878        if (LOGGER.isDebugEnabled()) {
879            StringBuilder sb =
880                new StringBuilder("FunUtil.hierarchizeTupleList returned:");
881            for (List<Member> tuple : fixedList) {
882                sb.append("\n");
883                sb.append(tuple.toString());
884            }
885        }
886
887        return fixedList;
888    }
889
890    /**
891     * Compares double-precision values according to MDX semantics.
892     *
893     * <p>MDX requires a total order:
894     * <blockquote>
895     *    -inf &lt; NULL &lt; ... &lt; -1 &lt; ... &lt; 0 &lt; ... &lt; NaN &lt;
896     * +inf
897     * </blockquote>
898     * but this is different than Java semantics, specifically with regard
899     * to {@link Double#NaN}.
900     */
901    public static int compareValues(double d1, double d2) {
902        if (Double.isNaN(d1)) {
903            if (d2 == Double.POSITIVE_INFINITY) {
904                return -1;
905            } else if (Double.isNaN(d2)) {
906                return 0;
907            } else {
908                return 1;
909            }
910        } else if (Double.isNaN(d2)) {
911            if (d1 == Double.POSITIVE_INFINITY) {
912                return 1;
913            } else {
914                return -1;
915            }
916        } else if (d1 == d2) {
917            return 0;
918        } else if (d1 == FunUtil.DoubleNull) {
919            if (d2 == Double.NEGATIVE_INFINITY) {
920                return 1;
921            } else {
922                return -1;
923            }
924        } else if (d2 == FunUtil.DoubleNull) {
925            if (d1 == Double.NEGATIVE_INFINITY) {
926                return -1;
927            } else {
928                return 1;
929            }
930        } else if (d1 < d2) {
931            return -1;
932        } else {
933            return 1;
934        }
935    }
936
937    /**
938     * Compares two cell values.
939     *
940     * <p>Nulls compare last, exceptions (including the
941     * object which indicates the the cell is not in the cache yet) next,
942     * then numbers and strings are compared by value.
943     *
944     * @param value0 First cell value
945     * @param value1 Second cell value
946     * @return -1, 0, or 1, depending upon whether first cell value is less
947     *   than, equal to, or greater than the second
948     */
949    public static int compareValues(Object value0, Object value1) {
950        if (value0 == value1) {
951            return 0;
952        }
953        // null is less than anything else
954        if (value0 == null) {
955            return -1;
956        }
957        if (value1 == null) {
958            return 1;
959        }
960
961        if (value0 == RolapUtil.valueNotReadyException) {
962            // the left value is not in cache; continue as best as we can
963             return -1;
964        } else if (value1 == RolapUtil.valueNotReadyException) {
965            // the right value is not in cache; continue as best as we can
966            return 1;
967        } else if (value0 == Util.nullValue) {
968            return -1; // null == -infinity
969        } else if (value1 == Util.nullValue) {
970            return 1; // null == -infinity
971        } else if (value0 instanceof String) {
972            return ((String) value0).compareToIgnoreCase((String) value1);
973        } else if (value0 instanceof Number) {
974            return FunUtil.compareValues(
975                ((Number) value0).doubleValue(),
976                ((Number) value1).doubleValue());
977        } else if (value0 instanceof Date) {
978            return ((Date) value0).compareTo((Date) value1);
979        } else if (value0 instanceof OrderKey) {
980            return ((OrderKey) value0).compareTo(value1);
981        } else {
982            throw Util.newInternal("cannot compare " + value0);
983        }
984    }
985
986    /**
987     * Turns the mapped values into relative values (percentages) for easy
988     * use by the general topOrBottom function. This might also be a useful
989     * function in itself.
990     */
991    static void toPercent(
992        TupleList members,
993        Map<List<Member>, Object> mapMemberToValue)
994    {
995        double total = 0;
996        int memberCount = members.size();
997        for (int i = 0; i < memberCount; i++) {
998            final List<Member> key = members.get(i);
999            final Object o = mapMemberToValue.get(key);
1000            if (o instanceof Number) {
1001                total += ((Number) o).doubleValue();
1002            }
1003        }
1004        for (int i = 0; i < memberCount; i++) {
1005            final List<Member> key = members.get(i);
1006            final Object o = mapMemberToValue.get(key);
1007            if (o instanceof Number) {
1008                double d = ((Number) o).doubleValue();
1009                mapMemberToValue.put(
1010                    key,
1011                    d / total * (double) 100);
1012            }
1013        }
1014    }
1015
1016
1017    /**
1018     * Decodes the syntactic type of an operator.
1019     *
1020     * @param flags A encoded string which represents an operator signature,
1021     *   as used by the {@code flags} parameter used to construct a
1022     *   {@link FunDefBase}.
1023     *
1024     * @return A {@link Syntax}
1025     */
1026    public static Syntax decodeSyntacticType(String flags) {
1027        char c = flags.charAt(0);
1028        switch (c) {
1029        case 'p':
1030            return Syntax.Property;
1031        case 'f':
1032            return Syntax.Function;
1033        case 'm':
1034            return Syntax.Method;
1035        case 'i':
1036            return Syntax.Infix;
1037        case 'P':
1038            return Syntax.Prefix;
1039        case 'Q':
1040            return Syntax.Postfix;
1041        case 'I':
1042            return Syntax.Internal;
1043        default:
1044            throw newInternal(
1045                "unknown syntax code '" + c + "' in string '" + flags + "'");
1046        }
1047    }
1048
1049    /**
1050     * Decodes the signature of a function into a category code which describes
1051     * the return type of the operator.
1052     *
1053     * <p>For example, <code>decodeReturnType("fnx")</code> returns
1054     * <code>{@link Category#Numeric}</code>, indicating this function has a
1055     * numeric return value.
1056     *
1057     * @param flags The signature of an operator,
1058     *   as used by the {@code flags} parameter used to construct a
1059     *   {@link FunDefBase}.
1060     *
1061     * @return An array {@link Category} codes.
1062     */
1063    public static int decodeReturnCategory(String flags) {
1064        final int returnCategory = decodeCategory(flags, 1);
1065        if ((returnCategory & Category.Mask) != returnCategory) {
1066            throw newInternal("bad return code flag in flags '" + flags + "'");
1067        }
1068        return returnCategory;
1069    }
1070
1071    /**
1072     * Decodes the {@code offset}th character of an encoded method
1073     * signature into a type category.
1074     *
1075     * <p>The codes are:
1076     * <table border="1">
1077     *
1078     * <tr><td>a</td><td>{@link Category#Array}</td></tr>
1079     *
1080     * <tr><td>d</td><td>{@link Category#Dimension}</td></tr>
1081     *
1082     * <tr><td>h</td><td>{@link Category#Hierarchy}</td></tr>
1083     *
1084     * <tr><td>l</td><td>{@link Category#Level}</td></tr>
1085     *
1086     * <tr><td>b</td><td>{@link Category#Logical}</td></tr>
1087     *
1088     * <tr><td>m</td><td>{@link Category#Member}</td></tr>
1089     *
1090     * <tr><td>N</td><td>Constant {@link Category#Numeric}</td></tr>
1091     *
1092     * <tr><td>n</td><td>{@link Category#Numeric}</td></tr>
1093     *
1094     * <tr><td>x</td><td>{@link Category#Set}</td></tr>
1095     *
1096     * <tr><td>#</td><td>Constant {@link Category#String}</td></tr>
1097     *
1098     * <tr><td>S</td><td>{@link Category#String}</td></tr>
1099     *
1100     * <tr><td>t</td><td>{@link Category#Tuple}</td></tr>
1101     *
1102     * <tr><td>v</td><td>{@link Category#Value}</td></tr>
1103     *
1104     * <tr><td>y</td><td>{@link Category#Symbol}</td></tr>
1105     *
1106     * </table>
1107     *
1108     * @param flags Encoded signature string
1109     * @param offset 0-based offset of character within string
1110     * @return A {@link Category}
1111     */
1112    public static int decodeCategory(String flags, int offset) {
1113        char c = flags.charAt(offset);
1114        switch (c) {
1115        case 'a':
1116            return Category.Array;
1117        case 'd':
1118            return Category.Dimension;
1119        case 'h':
1120            return Category.Hierarchy;
1121        case 'l':
1122            return Category.Level;
1123        case 'b':
1124            return Category.Logical;
1125        case 'm':
1126            return Category.Member;
1127        case 'N':
1128            return Category.Numeric | Category.Constant;
1129        case 'n':
1130            return Category.Numeric;
1131        case 'I':
1132            return Category.Numeric | Category.Integer | Category.Constant;
1133        case 'i':
1134            return Category.Numeric | Category.Integer;
1135        case 'x':
1136            return Category.Set;
1137        case '#':
1138            return Category.String | Category.Constant;
1139        case 'S':
1140            return Category.String;
1141        case 't':
1142            return Category.Tuple;
1143        case 'v':
1144            return Category.Value;
1145        case 'y':
1146            return Category.Symbol;
1147        case 'U':
1148            return Category.Null;
1149        case 'e':
1150            return Category.Empty;
1151        case 'D':
1152            return Category.DateTime;
1153        default:
1154            throw newInternal(
1155                "unknown type code '" + c + "' in string '" + flags + "'");
1156        }
1157    }
1158
1159    /**
1160     * Decodes a string of parameter types into an array of type codes.
1161     *
1162     * <p>Each character is decoded using {@link #decodeCategory(String, int)}.
1163     * For example, <code>decodeParameterTypes("nx")</code> returns
1164     * <code>{{@link Category#Numeric}, {@link Category#Set}}</code>.
1165     *
1166     * @param flags The signature of an operator,
1167     *   as used by the {@code flags} parameter used to construct a
1168     *   {@link FunDefBase}.
1169     *
1170     * @return An array {@link Category} codes.
1171     */
1172    public static int[] decodeParameterCategories(String flags) {
1173        int[] parameterCategories = new int[flags.length() - 2];
1174        for (int i = 0; i < parameterCategories.length; i++) {
1175            parameterCategories[i] = decodeCategory(flags, i + 2);
1176        }
1177        return parameterCategories;
1178    }
1179
1180    /**
1181     * Converts a double (primitive) value to a Double. {@link #DoubleNull}
1182     * becomes null.
1183     */
1184    public static Double box(double d) {
1185        return d == DoubleNull
1186            ? null
1187            : d;
1188    }
1189
1190    /**
1191     * Converts an int (primitive) value to an Integer. {@link #IntegerNull}
1192     * becomes null.
1193     */
1194    public static Integer box(int n) {
1195        return n == IntegerNull
1196            ? null
1197            : n;
1198    }
1199
1200    static double percentile(
1201        Evaluator evaluator,
1202        TupleList members,
1203        Calc exp,
1204        double p)
1205    {
1206        SetWrapper sw = evaluateSet(evaluator, members, exp);
1207        if (sw.errorCount > 0) {
1208            return Double.NaN;
1209        } else if (sw.v.size() == 0) {
1210            return FunUtil.DoubleNull;
1211        }
1212        double[] asArray = new double[sw.v.size()];
1213        for (int i = 0; i < asArray.length; i++) {
1214            asArray[i] = (Double) sw.v.get(i);
1215        }
1216        Arrays.sort(asArray);
1217
1218        // The median is defined as the value that has exactly the same
1219        // number of entries before it in the sorted list as after.
1220        // So, if the number of entries in the list is odd, the
1221        // median is the entry at (length-1)/2 (using zero-based indexes).
1222        // If the number of entries is even, the median is defined as the
1223        // arithmetic mean of the two numbers in the middle of the list, or
1224        // (entries[length/2 - 1] + entries[length/2]) / 2.
1225        int length = asArray.length;
1226        if (p <= 0.0) {
1227            return asArray[0];
1228        } else if (p >= 1.0) {
1229            return asArray[length - 1];
1230        } else if (length == 1) {
1231            return asArray[0] * p;
1232        } else if (p == 0.5) {
1233            // Special case for median.
1234            if ((length & 1) == 1) {
1235                // The length is odd. Note that length/2 is an integer
1236                // expression, and it's positive so we save ourselves a divide.
1237                return asArray[length >> 1];
1238            } else {
1239                return (asArray[(length >> 1) - 1] + asArray[length >> 1])
1240                    / 2.0;
1241            }
1242        } else {
1243            final double jD = Math.floor(length * p);
1244            int j = jD > 0 ? (int) jD - 1 : (int) jD;
1245            double alpha = (p * length) - jD;
1246            assert alpha >= 0;
1247            assert alpha <= 1;
1248            return asArray[j] + ((asArray[j + 1] - asArray[j]) * alpha);
1249        }
1250    }
1251
1252    /**
1253     * Returns the member which lies upon a particular quartile according to a
1254     * given expression.
1255     *
1256     * @param evaluator Evaluator
1257     * @param members List of members
1258     * @param exp Expression to rank members
1259     * @param range Quartile (1, 2 or 3)
1260     *
1261     * @pre range >= 1 && range <= 3
1262     */
1263    protected static double quartile(
1264        Evaluator evaluator,
1265        TupleList members,
1266        Calc exp,
1267        int range)
1268    {
1269        assert range >= 1 && range <= 3;
1270
1271        SetWrapper sw = evaluateSet(evaluator, members, exp);
1272        if (sw.errorCount > 0) {
1273            return Double.NaN;
1274        } else if (sw.v.size() == 0) {
1275            return DoubleNull;
1276        }
1277
1278        double[] asArray = new double[sw.v.size()];
1279        for (int i = 0; i < asArray.length; i++) {
1280            asArray[i] = ((Double) sw.v.get(i)).doubleValue();
1281        }
1282
1283        Arrays.sort(asArray);
1284        // get a quartile, median is a second q
1285        double dm = 0.25 * asArray.length * range;
1286        int median = (int) Math.floor(dm);
1287        return dm == median && median < asArray.length - 1
1288            ? (asArray[median] + asArray[median + 1]) / 2
1289            : asArray[median];
1290    }
1291
1292    public static Object min(
1293        Evaluator evaluator,
1294        TupleList members,
1295        Calc calc)
1296    {
1297        SetWrapper sw = evaluateSet(evaluator, members, calc);
1298        if (sw.errorCount > 0) {
1299            return Double.NaN;
1300        } else {
1301            final int size = sw.v.size();
1302            if (size == 0) {
1303                return Util.nullValue;
1304            } else {
1305                Double min = ((Number) sw.v.get(0)).doubleValue();
1306                for (int i = 1; i < size; i++) {
1307                    Double iValue = ((Number) sw.v.get(i)).doubleValue();
1308                    if (iValue < min) {
1309                        min = iValue;
1310                    }
1311                }
1312                return min;
1313            }
1314        }
1315    }
1316
1317    public static Object max(
1318        Evaluator evaluator,
1319        TupleList members,
1320        Calc exp)
1321    {
1322        SetWrapper sw = evaluateSet(evaluator, members, exp);
1323        if (sw.errorCount > 0) {
1324            return Double.NaN;
1325        } else {
1326            final int size = sw.v.size();
1327            if (size == 0) {
1328                return Util.nullValue;
1329            } else {
1330                Double max = ((Number) sw.v.get(0)).doubleValue();
1331                for (int i = 1; i < size; i++) {
1332                    Double iValue = ((Number) sw.v.get(i)).doubleValue();
1333                    if (iValue > max) {
1334                        max = iValue;
1335                    }
1336                }
1337                return max;
1338            }
1339        }
1340    }
1341
1342    static Object var(
1343        Evaluator evaluator,
1344        TupleList members,
1345        Calc exp,
1346        boolean biased)
1347    {
1348        SetWrapper sw = evaluateSet(evaluator, members, exp);
1349        return _var(sw, biased);
1350    }
1351
1352    private static Object _var(SetWrapper sw, boolean biased) {
1353        if (sw.errorCount > 0) {
1354            return new Double(Double.NaN);
1355        } else if (sw.v.size() == 0) {
1356            return Util.nullValue;
1357        } else {
1358            double stdev = 0.0;
1359            double avg = _avg(sw);
1360            for (int i = 0; i < sw.v.size(); i++) {
1361                stdev +=
1362                    Math.pow((((Number) sw.v.get(i)).doubleValue() - avg), 2);
1363            }
1364            int n = sw.v.size();
1365            if (!biased) {
1366                n--;
1367            }
1368            return new Double(stdev / (double) n);
1369        }
1370    }
1371
1372    static double correlation(
1373        Evaluator evaluator,
1374        TupleList memberList,
1375        Calc exp1,
1376        Calc exp2)
1377    {
1378        SetWrapper sw1 = evaluateSet(evaluator, memberList, exp1);
1379        SetWrapper sw2 = evaluateSet(evaluator, memberList, exp2);
1380        Object covar = _covariance(sw1, sw2, false);
1381        Object var1 = _var(sw1, false); // this should be false, yes?
1382        Object var2 = _var(sw2, false);
1383
1384        return ((Number) covar).doubleValue()
1385            / Math.sqrt(
1386                ((Number) var1).doubleValue()
1387                * ((Number) var2).doubleValue());
1388    }
1389
1390    static Object covariance(
1391        Evaluator evaluator,
1392        TupleList members,
1393        Calc exp1,
1394        Calc exp2,
1395        boolean biased)
1396    {
1397        final int savepoint = evaluator.savepoint();
1398        SetWrapper sw1;
1399        try {
1400            sw1 = evaluateSet(evaluator, members, exp1);
1401        } finally {
1402            evaluator.restore(savepoint);
1403        }
1404        SetWrapper sw2;
1405        try {
1406            sw2 = evaluateSet(evaluator, members, exp2);
1407        } finally {
1408            evaluator.restore(savepoint);
1409        }
1410        // todo: because evaluateSet does not add nulls to the SetWrapper, this
1411        // solution may lead to mismatched lists and is therefore not robust
1412        return _covariance(sw1, sw2, biased);
1413    }
1414
1415
1416    private static Object _covariance(
1417        SetWrapper sw1,
1418        SetWrapper sw2,
1419        boolean biased)
1420    {
1421        if (sw1.v.size() != sw2.v.size()) {
1422            return Util.nullValue;
1423        }
1424        double avg1 = _avg(sw1);
1425        double avg2 = _avg(sw2);
1426        double covar = 0.0;
1427        for (int i = 0; i < sw1.v.size(); i++) {
1428            // all of this casting seems inefficient - can we make SetWrapper
1429            // contain an array of double instead?
1430            double diff1 = (((Number) sw1.v.get(i)).doubleValue() - avg1);
1431            double diff2 = (((Number) sw2.v.get(i)).doubleValue() - avg2);
1432            covar += (diff1 * diff2);
1433        }
1434        int n = sw1.v.size();
1435        if (!biased) {
1436            n--;
1437        }
1438        return new Double(covar / (double) n);
1439    }
1440
1441    static Object stdev(
1442        Evaluator evaluator,
1443        TupleList members,
1444        Calc exp,
1445        boolean biased)
1446    {
1447        Object o = var(evaluator, members, exp, biased);
1448        return (o instanceof Double)
1449            ? new Double(Math.sqrt(((Number) o).doubleValue()))
1450            : o;
1451    }
1452
1453    public static Object avg(
1454        Evaluator evaluator,
1455        TupleList members,
1456        Calc calc)
1457    {
1458        SetWrapper sw = evaluateSet(evaluator, members, calc);
1459        return (sw.errorCount > 0)
1460            ? new Double(Double.NaN)
1461            : (sw.v.size() == 0)
1462            ? Util.nullValue
1463            : new Double(_avg(sw));
1464    }
1465
1466    // TODO: parameterize inclusion of nulls; also, maybe make _avg a method of
1467    // setwrapper, so we can cache the result (i.e. for correl)
1468    private static double _avg(SetWrapper sw) {
1469        double sum = 0.0;
1470        for (int i = 0; i < sw.v.size(); i++) {
1471            sum += ((Number) sw.v.get(i)).doubleValue();
1472        }
1473        // TODO: should look at context and optionally include nulls
1474        return sum / (double) sw.v.size();
1475    }
1476
1477    public static Object sum(
1478        Evaluator evaluator,
1479        TupleList members,
1480        Calc exp)
1481    {
1482        double d = sumDouble(evaluator, members, exp);
1483        return d == DoubleNull ? Util.nullValue : new Double(d);
1484    }
1485
1486    public static double sumDouble(
1487        Evaluator evaluator,
1488        TupleList members,
1489        Calc exp)
1490    {
1491        SetWrapper sw = evaluateSet(evaluator, members, exp);
1492        if (sw.errorCount > 0) {
1493            return Double.NaN;
1494        } else if (sw.v.size() == 0) {
1495            return DoubleNull;
1496        } else {
1497            double sum = 0.0;
1498            for (int i = 0; i < sw.v.size(); i++) {
1499                sum += ((Number) sw.v.get(i)).doubleValue();
1500            }
1501            return sum;
1502        }
1503    }
1504
1505    public static double sumDouble(
1506        Evaluator evaluator,
1507        TupleIterable iterable,
1508        Calc exp)
1509    {
1510        SetWrapper sw = evaluateSet(evaluator, iterable, exp);
1511        if (sw.errorCount > 0) {
1512            return Double.NaN;
1513        } else if (sw.v.size() == 0) {
1514            return DoubleNull;
1515        } else {
1516            double sum = 0.0;
1517            for (int i = 0; i < sw.v.size(); i++) {
1518                sum += ((Number) sw.v.get(i)).doubleValue();
1519            }
1520            return sum;
1521        }
1522    }
1523
1524    public static int count(
1525        Evaluator evaluator,
1526        TupleIterable iterable,
1527        boolean includeEmpty)
1528    {
1529        if (iterable == null) {
1530            return 0;
1531        }
1532        if (includeEmpty) {
1533            if (iterable instanceof TupleList) {
1534                return ((TupleList) iterable).size();
1535            } else {
1536                int retval = 0;
1537                TupleCursor cursor = iterable.tupleCursor();
1538                while (cursor.forward()) {
1539                    retval++;
1540                }
1541                return retval;
1542            }
1543        } else {
1544            int retval = 0;
1545            TupleCursor cursor = iterable.tupleCursor();
1546            while (cursor.forward()) {
1547                cursor.setContext(evaluator);
1548                if (!evaluator.currentIsEmpty()) {
1549                    retval++;
1550                }
1551            }
1552            return retval;
1553        }
1554    }
1555
1556    /**
1557     * Evaluates {@code exp} (if defined) over {@code members} to
1558     * generate a {@link List} of {@link SetWrapper} objects, which contains
1559     * a {@link Double} value and meta information, unlike
1560     * {@link #evaluateMembers}, which only produces values.
1561     *
1562     * @pre exp != null
1563     */
1564    static SetWrapper evaluateSet(
1565        Evaluator evaluator,
1566        TupleIterable members,
1567        Calc calc)
1568    {
1569        assert members != null;
1570        assert calc != null;
1571        assert calc.getType() instanceof ScalarType;
1572
1573        // todo: treat constant exps as evaluateMembers() does
1574        SetWrapper retval = new SetWrapper();
1575        final TupleCursor cursor = members.tupleCursor();
1576        while (cursor.forward()) {
1577            cursor.setContext(evaluator);
1578            Object o = calc.evaluate(evaluator);
1579            if (o == null || o == Util.nullValue) {
1580                retval.nullCount++;
1581            } else if (o == RolapUtil.valueNotReadyException) {
1582                // Carry on summing, so that if we are running in a
1583                // BatchingCellReader, we find out all the dependent cells we
1584                // need
1585                retval.errorCount++;
1586            } else if (o instanceof Number) {
1587                retval.v.add(((Number) o).doubleValue());
1588            } else {
1589                retval.v.add(o);
1590            }
1591        }
1592        return retval;
1593    }
1594
1595    /**
1596     * Evaluates one or more expressions against the member list returning
1597     * a SetWrapper array. Where this differs very significantly from the
1598     * above evaluateSet methods is how it count null values and Throwables;
1599     * this method adds nulls to the SetWrapper Vector rather than not adding
1600     * anything - as the above method does. The impact of this is that if, for
1601     * example, one was creating a list of x,y values then each list will have
1602     * the same number of values (though some might be null) - this allows
1603     * higher level code to determine how to handle the lack of data rather than
1604     * having a non-equal number (if one is plotting x,y values it helps to
1605     * have the same number and know where a potential gap is the data is.
1606     */
1607    static SetWrapper[] evaluateSet(
1608        Evaluator evaluator,
1609        TupleList list,
1610        DoubleCalc[] calcs)
1611    {
1612        Util.assertPrecondition(calcs != null, "calcs != null");
1613
1614        // todo: treat constant exps as evaluateMembers() does
1615        SetWrapper[] retvals = new SetWrapper[calcs.length];
1616        for (int i = 0; i < calcs.length; i++) {
1617            retvals[i] = new SetWrapper();
1618        }
1619        final TupleCursor cursor = list.tupleCursor();
1620        while (cursor.forward()) {
1621            cursor.setContext(evaluator);
1622            for (int i = 0; i < calcs.length; i++) {
1623                DoubleCalc calc = calcs[i];
1624                SetWrapper retval = retvals[i];
1625                double o = calc.evaluateDouble(evaluator);
1626                if (o == FunUtil.DoubleNull) {
1627                    retval.nullCount++;
1628                    retval.v.add(null);
1629                } else {
1630                    retval.v.add(o);
1631                }
1632                // TODO: If the expression yielded an error, carry on
1633                // summing, so that if we are running in a
1634                // BatchingCellReader, we find out all the dependent cells
1635                // we need
1636            }
1637        }
1638        return retvals;
1639    }
1640
1641    static List<Member> periodsToDate(
1642        Evaluator evaluator,
1643        Level level,
1644        Member member)
1645    {
1646        if (member == null) {
1647            member = evaluator.getContext(level.getHierarchy());
1648        }
1649        Member m = member;
1650        while (m != null) {
1651            if (m.getLevel() == level) {
1652                break;
1653            }
1654            m = m.getParentMember();
1655        }
1656        // If m == null, then "level" was lower than member's level.
1657        // periodsToDate([Time].[Quarter], [Time].[1997] is valid,
1658        //  but will return an empty List
1659        List<Member> members = new ArrayList<Member>();
1660        if (m != null) {
1661            // e.g. m is [Time].[1997] and member is [Time].[1997].[Q1].[3]
1662            // we now have to make m to be the first member of the range,
1663            // so m becomes [Time].[1997].[Q1].[1]
1664            SchemaReader reader = evaluator.getSchemaReader();
1665            m = Util.getFirstDescendantOnLevel(reader, m, member.getLevel());
1666            reader.getMemberRange(level, m, member, members);
1667        }
1668        return members;
1669    }
1670
1671    static List<Member> memberRange(
1672        Evaluator evaluator,
1673        Member startMember,
1674        Member endMember)
1675    {
1676        final Level level = startMember.getLevel();
1677        assertTrue(level == endMember.getLevel());
1678        List<Member> members = new ArrayList<Member>();
1679        evaluator.getSchemaReader().getMemberRange(
1680            level, startMember, endMember, members);
1681
1682        if (members.isEmpty()) {
1683            // The result is empty, so maybe the members are reversed. This is
1684            // cheaper than comparing the members before we call getMemberRange.
1685            evaluator.getSchemaReader().getMemberRange(
1686                level, endMember, startMember, members);
1687        }
1688        return members;
1689    }
1690
1691    /**
1692     * Returns the member under ancestorMember having the same relative position
1693     * under member's parent.
1694     * <p>For exmaple, cousin([Feb 2001], [Q3 2001]) is [August 2001].
1695     * @param schemaReader The reader to use
1696     * @param member The member for which we'll find the cousin.
1697     * @param ancestorMember The cousin's ancestor.
1698     *
1699     * @return The child of {@code ancestorMember} in the same position
1700     * under {@code ancestorMember} as {@code member} is under its
1701     * parent.
1702     */
1703    static Member cousin(
1704        SchemaReader schemaReader,
1705        Member member,
1706        Member ancestorMember)
1707    {
1708        if (ancestorMember.isNull()) {
1709            return ancestorMember;
1710        }
1711        if (member.getHierarchy() != ancestorMember.getHierarchy()) {
1712            throw MondrianResource.instance().CousinHierarchyMismatch.ex(
1713                member.getUniqueName(), ancestorMember.getUniqueName());
1714        }
1715        if (member.getLevel().getDepth()
1716            < ancestorMember.getLevel().getDepth())
1717        {
1718            return member.getHierarchy().getNullMember();
1719        }
1720
1721        Member cousin = cousin2(schemaReader, member, ancestorMember);
1722        if (cousin == null) {
1723            cousin = member.getHierarchy().getNullMember();
1724        }
1725
1726        return cousin;
1727    }
1728
1729    private static Member cousin2(
1730        SchemaReader schemaReader,
1731        Member member1,
1732        Member member2)
1733    {
1734        if (member1.getLevel() == member2.getLevel()) {
1735            return member2;
1736        }
1737        Member uncle =
1738            cousin2(schemaReader, member1.getParentMember(), member2);
1739        if (uncle == null) {
1740            return null;
1741        }
1742        int ordinal = Util.getMemberOrdinalInParent(schemaReader, member1);
1743        List<Member> cousins = schemaReader.getMemberChildren(uncle);
1744        if (cousins.size() <= ordinal) {
1745            return null;
1746        }
1747        return cousins.get(ordinal);
1748    }
1749
1750    /**
1751     * Returns the ancestor of {@code member} at the given level
1752     * or distance. It is assumed that any error checking required
1753     * has been done prior to calling this function.
1754     *
1755     * <p>This method takes into consideration the fact that there
1756     * may be intervening hidden members between {@code member}
1757     * and the ancestor. If {@code targetLevel} is not null, then
1758     * the method will only return a member if the level at
1759     * {@code distance} from the member is actually the
1760     * {@code targetLevel} specified.
1761     *
1762     * @param evaluator The evaluation context
1763     * @param member The member for which the ancestor is to be found
1764     * @param distance The distance up the chain the ancestor is to
1765     * be found.
1766     *
1767     * @param targetLevel The desired targetLevel of the ancestor. If
1768     * {@code null}, then the distance completely determines the desired
1769     * ancestor.
1770     *
1771     * @return The ancestor member, or {@code null} if no such
1772     * ancestor exists.
1773     */
1774    static Member ancestor(
1775        Evaluator evaluator,
1776        Member member,
1777        int distance,
1778        Level targetLevel)
1779    {
1780        if ((targetLevel != null)
1781            && (member.getHierarchy() != targetLevel.getHierarchy()))
1782        {
1783            throw MondrianResource.instance().MemberNotInLevelHierarchy.ex(
1784                member.getUniqueName(), targetLevel.getUniqueName());
1785        }
1786
1787        if (distance == 0) {
1788            // Shortcut if there's nowhere to go.
1789            return member;
1790        } else if (distance < 0) {
1791            // Can't go backwards.
1792            return member.getHierarchy().getNullMember();
1793        }
1794
1795        final List<Member> ancestors = new ArrayList<Member>();
1796        final SchemaReader schemaReader = evaluator.getSchemaReader();
1797        schemaReader.getMemberAncestors(member, ancestors);
1798
1799        Member result = member.getHierarchy().getNullMember();
1800
1801        searchLoop:
1802        for (int i = 0; i < ancestors.size(); i++) {
1803            final Member ancestorMember = ancestors.get(i);
1804
1805            if (targetLevel != null) {
1806                if (ancestorMember.getLevel() == targetLevel) {
1807                    if (schemaReader.isVisible(ancestorMember)) {
1808                        result = ancestorMember;
1809                        break;
1810                    } else {
1811                        result = member.getHierarchy().getNullMember();
1812                        break;
1813                    }
1814                }
1815            } else {
1816                if (schemaReader.isVisible(ancestorMember)) {
1817                    distance--;
1818
1819                    // Make sure that this ancestor is really on the right
1820                    // targetLevel. If a targetLevel was specified and at least
1821                    // one of the ancestors was hidden, this this algorithm goes
1822                    // too far up the ancestor list. It's not a problem, except
1823                    // that we need to check if it's happened and return the
1824                    // hierarchy's null member instead.
1825                    //
1826                    // For example, consider what happens with
1827                    // Ancestor([Store].[Israel].[Haifa], [Store].[Store
1828                    // State]).  The distance from [Haifa] to [Store State] is
1829                    // 1, but that lands us at the country targetLevel, which is
1830                    // clearly wrong.
1831                    if (distance == 0) {
1832                        result = ancestorMember;
1833                        break;
1834                    }
1835                }
1836            }
1837        }
1838
1839        return result;
1840    }
1841
1842    /**
1843     * Compares a pair of members according to their positions in a
1844     * prefix-order (or postfix-order, if {@code post} is true) walk
1845     * over a hierarchy.
1846     *
1847     * @param m1 First member
1848     * @param m2 Second member
1849     *
1850     * @param post Whether to sortMembers in postfix order. If true, a parent
1851     *   will sortMembers immediately after its last child. If false, a parent
1852     *   will sortMembers immediately before its first child.
1853     *
1854     * @return -1 if m1 collates before m2,
1855     *   0 if m1 equals m2,
1856     *   1 if m1 collates after m2
1857     */
1858    public static int compareHierarchically(
1859        Member m1,
1860        Member m2,
1861        boolean post)
1862    {
1863        // Strip away the LimitedRollupMember wrapper, if it exists. The
1864        // wrapper does not implement equals and comparisons correctly. This
1865        // is safe this method has no side-effects: it just returns an int.
1866        m1 = unwrapLimitedRollupMember(m1);
1867        m2 = unwrapLimitedRollupMember(m2);
1868
1869        if (equals(m1, m2)) {
1870            return 0;
1871        }
1872
1873        while (true) {
1874            int depth1 = m1.getDepth();
1875            int depth2 = m2.getDepth();
1876            if (depth1 < depth2) {
1877                m2 = m2.getParentMember();
1878                if (equals(m1, m2)) {
1879                    return post ? 1 : -1;
1880                }
1881            } else if (depth1 > depth2) {
1882                m1 = m1.getParentMember();
1883                if (equals(m1, m2)) {
1884                    return post ? -1 : 1;
1885                }
1886            } else {
1887                Member prev1 = m1;
1888                Member prev2 = m2;
1889                m1 = unwrapLimitedRollupMember(m1.getParentMember());
1890                m2 = unwrapLimitedRollupMember(m2.getParentMember());
1891                if (equals(m1, m2)) {
1892                    final int c = compareSiblingMembers(prev1, prev2);
1893                    // compareHierarchically needs to impose a total order;
1894                    // cannot return 0 for non-equal members
1895                    assert c != 0
1896                        : "Members " + prev1 + ", " + prev2
1897                        + " are not equal, but compare returned 0.";
1898                    return c;
1899                }
1900            }
1901        }
1902    }
1903
1904    private static Member unwrapLimitedRollupMember(Member m) {
1905        if (m instanceof RolapHierarchy.LimitedRollupMember) {
1906            return ((RolapHierarchy.LimitedRollupMember) m).member;
1907        }
1908        return m;
1909    }
1910    /**
1911     * Compares two members which are known to have the same parent.
1912     *
1913     * First, compare by ordinal.
1914     * This is only valid now we know they're siblings, because
1915     * ordinals are only unique within a parent.
1916     * If the dimension does not use ordinals, both ordinals
1917     * will be -1.
1918     *
1919     * <p>If the ordinals do not differ, compare using regular member
1920     * comparison.
1921     *
1922     * @param m1 First member
1923     * @param m2 Second member
1924     * @return -1 if m1 collates less than m2,
1925     *   1 if m1 collates after m2,
1926     *   0 if m1 == m2.
1927     */
1928    public static int compareSiblingMembers(Member m1, Member m2) {
1929        // calculated members collate after non-calculated
1930        final boolean calculated1 = m1.isCalculatedInQuery();
1931        final boolean calculated2 = m2.isCalculatedInQuery();
1932        if (calculated1) {
1933            if (!calculated2) {
1934                return 1;
1935            }
1936        } else {
1937            if (calculated2) {
1938                return -1;
1939            }
1940        }
1941        final Comparable k1 = m1.getOrderKey();
1942        final Comparable k2 = m2.getOrderKey();
1943        if ((k1 != null) && (k2 != null)) {
1944            return k1.compareTo(k2);
1945        } else {
1946            final int ordinal1 = m1.getOrdinal();
1947            final int ordinal2 = m2.getOrdinal();
1948            return (ordinal1 == ordinal2)
1949                ? m1.compareTo(m2)
1950                : (ordinal1 < ordinal2)
1951                ? -1
1952                : 1;
1953        }
1954    }
1955
1956    /**
1957     * Returns whether one of the members in a tuple is null.
1958     */
1959    public static boolean tupleContainsNullMember(Member[] tuple) {
1960        for (Member member : tuple) {
1961            if (member.isNull()) {
1962                return true;
1963            }
1964        }
1965        return false;
1966    }
1967
1968    /**
1969     * Returns whether one of the members in a tuple is null.
1970     */
1971    public static boolean tupleContainsNullMember(List<Member> tuple) {
1972        for (Member member : tuple) {
1973            if (member.isNull()) {
1974                return true;
1975            }
1976        }
1977        return false;
1978    }
1979
1980    public static Member[] makeNullTuple(final TupleType tupleType) {
1981        final Type[] elementTypes = tupleType.elementTypes;
1982        Member[] members = new Member[elementTypes.length];
1983        for (int i = 0; i < elementTypes.length; i++) {
1984            MemberType type = (MemberType) elementTypes[i];
1985            members[i] = makeNullMember(type);
1986        }
1987        return members;
1988    }
1989
1990    static Member makeNullMember(MemberType memberType) {
1991        Hierarchy hierarchy = memberType.getHierarchy();
1992        if (hierarchy == null) {
1993            return NullMember;
1994        }
1995        return hierarchy.getNullMember();
1996    }
1997
1998    /**
1999     * Validates the arguments to a function and resolves the function.
2000     *
2001     * @param validator Validator used to validate function arguments and
2002     *           resolve the function
2003     * @param funDef Function definition, or null to deduce definition from
2004     *           name, syntax and argument types
2005     * @param args    Arguments to the function
2006     * @param newArgs Output parameter for the resolved arguments
2007     * @param name    Function name
2008     * @param syntax Syntax style used to invoke function
2009     * @return resolved function definition
2010     */
2011    public static FunDef resolveFunArgs(
2012        Validator validator,
2013        FunDef funDef,
2014        Exp[] args,
2015        Exp[] newArgs,
2016        String name,
2017        Syntax syntax)
2018    {
2019        for (int i = 0; i < args.length; i++) {
2020            newArgs[i] = validator.validate(args[i], false);
2021        }
2022        if (funDef == null || validator.alwaysResolveFunDef()) {
2023            funDef = validator.getDef(newArgs, name, syntax);
2024        }
2025        checkNativeCompatible(validator, funDef, newArgs);
2026        return funDef;
2027    }
2028
2029    /**
2030     * Functions that dynamically return one or more members of the measures
2031     * dimension prevent us from using native evaluation.
2032     *
2033     * @param validator Validator used to validate function arguments and
2034     *           resolve the function
2035     * @param funDef Function definition, or null to deduce definition from
2036     *           name, syntax and argument types
2037     * @param args    Arguments to the function
2038     */
2039    private static void checkNativeCompatible(
2040        Validator validator,
2041        FunDef funDef,
2042        Exp[] args)
2043    {
2044        // If the first argument to a function is either:
2045        // 1) the measures dimension or
2046        // 2) a measures member where the function returns another member or
2047        //    a set,
2048        // then these are functions that dynamically return one or more
2049        // members of the measures dimension.  In that case, we cannot use
2050        // native cross joins because the functions need to be executed to
2051        // determine the resultant measures.
2052        //
2053        // As a result, we disallow functions like AllMembers applied on the
2054        // Measures dimension as well as functions like the range operator,
2055        // siblings, and lag, when the argument is a measure member.
2056        // However, we do allow functions like isEmpty, rank, and topPercent.
2057        //
2058        // Also, the Set and Parentheses functions are ok since they're
2059        // essentially just containers.
2060        Query query = validator.getQuery();
2061        if (!(funDef instanceof SetFunDef)
2062            && !(funDef instanceof ParenthesesFunDef)
2063            && query != null
2064            && query.nativeCrossJoinVirtualCube())
2065        {
2066            int[] paramCategories = funDef.getParameterCategories();
2067            if (paramCategories.length > 0) {
2068                final int cat0 = paramCategories[0];
2069                final Exp arg0 = args[0];
2070                switch (cat0) {
2071                case Category.Dimension:
2072                case Category.Hierarchy:
2073                    if (arg0 instanceof DimensionExpr
2074                        && ((DimensionExpr) arg0).getDimension().isMeasures()
2075                        && !(funDef instanceof HierarchyCurrentMemberFunDef))
2076                    {
2077                        query.setVirtualCubeNonNativeCrossJoin();
2078                    }
2079                    break;
2080                case Category.Member:
2081                    if (arg0 instanceof MemberExpr
2082                        && ((MemberExpr) arg0).getMember().isMeasure()
2083                        && isMemberOrSet(funDef.getReturnCategory()))
2084                    {
2085                        query.setVirtualCubeNonNativeCrossJoin();
2086                    }
2087                    break;
2088                }
2089            }
2090        }
2091    }
2092
2093    private static boolean isMemberOrSet(int category) {
2094        return category == Category.Member || category == Category.Set;
2095    }
2096
2097    static void appendTuple(StringBuilder buf, Member[] members) {
2098        buf.append("(");
2099        for (int j = 0; j < members.length; j++) {
2100            if (j > 0) {
2101                buf.append(", ");
2102            }
2103            Member member = members[j];
2104            buf.append(member.getUniqueName());
2105        }
2106        buf.append(")");
2107    }
2108
2109    /**
2110     * Returns whether two tuples are equal.
2111     *
2112     * <p>The members are allowed to be in different positions. For example,
2113     * <code>([Gender].[M], [Store].[USA]) IS ([Store].[USA],
2114     * [Gender].[M])</code> returns {@code true}.
2115     */
2116    static boolean equalTuple(Member[] members0, Member[] members1) {
2117        final int count = members0.length;
2118        if (count != members1.length) {
2119            return false;
2120        }
2121        outer:
2122        for (int i = 0; i < count; i++) {
2123            // First check the member at the corresponding ordinal. It is more
2124            // likely to be there.
2125            final Member member0 = members0[i];
2126            if (member0.equals(members1[i])) {
2127                continue;
2128            }
2129            // Look for this member in other positions.
2130            // We can assume that the members in members0 are distinct (because
2131            // they belong to different dimensions), so this test is valid.
2132            for (int j = 0; j < count; j++) {
2133                if (i != j && member0.equals(members1[j])) {
2134                    continue outer;
2135                }
2136            }
2137            // This member of members0 does not occur in any position of
2138            // members1. The tuples are not equal.
2139            return false;
2140        }
2141        return true;
2142    }
2143
2144    static FunDef createDummyFunDef(
2145        Resolver resolver,
2146        int returnCategory,
2147        Exp[] args)
2148    {
2149        final int[] argCategories = ExpBase.getTypes(args);
2150        return new FunDefBase(resolver, returnCategory, argCategories) {
2151        };
2152    }
2153
2154    public static List<Member> getNonEmptyMemberChildren(
2155        Evaluator evaluator,
2156        Member member)
2157    {
2158        SchemaReader sr = evaluator.getSchemaReader();
2159        if (evaluator.isNonEmpty()) {
2160            return sr.getMemberChildren(member, evaluator);
2161        } else {
2162            return sr.getMemberChildren(member);
2163        }
2164    }
2165
2166    public static Map<Member, Access>
2167        getNonEmptyMemberChildrenWithDetails(
2168            Evaluator evaluator, Member member)
2169    {
2170        SchemaReader sr = evaluator.getSchemaReader();
2171        if (evaluator.isNonEmpty()) {
2172            return (Map<Member, Access>)
2173                sr.getMemberChildrenWithDetails(member, evaluator);
2174        } else {
2175            return (Map<Member, Access>)
2176                sr.getMemberChildrenWithDetails(member, null);
2177        }
2178    }
2179
2180    /**
2181     * Returns members of a level which are not empty (according to the
2182     * criteria expressed by the evaluator).
2183     *
2184     * @param evaluator Evaluator, determines non-empty criteria
2185     * @param level Level
2186     * @param includeCalcMembers Whether to include calculated members
2187     */
2188    static List<Member> getNonEmptyLevelMembers(
2189        final Evaluator evaluator,
2190        final Level level,
2191        final boolean includeCalcMembers)
2192    {
2193        SchemaReader sr = evaluator.getSchemaReader();
2194        if (evaluator.isNonEmpty()) {
2195            List<Member> members = sr.getLevelMembers(level, evaluator);
2196            if (includeCalcMembers) {
2197                return addLevelCalculatedMembers(sr, level, members);
2198            }
2199            return members;
2200        }
2201        return sr.getLevelMembers(level, includeCalcMembers);
2202    }
2203
2204    static TupleList levelMembers(
2205        final Level level,
2206        final Evaluator evaluator,
2207        final boolean includeCalcMembers)
2208    {
2209        List<Member> memberList =
2210            getNonEmptyLevelMembers(evaluator, level, includeCalcMembers);
2211        TupleList tupleList;
2212        if (!includeCalcMembers) {
2213            memberList = removeCalculatedMembers(memberList);
2214        }
2215        final List<Member> memberListClone = new ArrayList<Member>(memberList);
2216        tupleList = new UnaryTupleList(memberListClone);
2217        return hierarchizeTupleList(tupleList, false);
2218    }
2219
2220    static TupleList hierarchyMembers(
2221        Hierarchy hierarchy,
2222        Evaluator evaluator,
2223        final boolean includeCalcMembers)
2224    {
2225        TupleList tupleList = new UnaryTupleList();
2226        final List<Member> memberList = tupleList.slice(0);
2227        if (evaluator.isNonEmpty()) {
2228            // Allow the SQL generator to generate optimized SQL since we know
2229            // we're only interested in non-empty members of this level.
2230            for (Level level : hierarchy.getLevels()) {
2231                List<Member> members =
2232                    getNonEmptyLevelMembers(
2233                        evaluator, level, includeCalcMembers);
2234                memberList.addAll(members);
2235            }
2236        } else {
2237            final List<Member> memberList1 = addMembers(
2238                evaluator.getSchemaReader(),
2239                new ConcatenableList<Member>(),
2240                hierarchy);
2241            if (includeCalcMembers) {
2242                memberList.addAll(memberList1);
2243            } else {
2244                // Same effect as calling removeCalculatedMembers(tupleList)
2245                // but one fewer copy of the list.
2246                for (Member member1 : memberList1) {
2247                    if (!member1.isCalculated()) {
2248                        memberList.add(member1);
2249                    }
2250                }
2251            }
2252        }
2253        return hierarchizeTupleList(tupleList, false);
2254    }
2255
2256   /**
2257    * Partial Sort: sorts in place an array of Objects using a given Comparator,
2258    * but only enough so that the N biggest (or smallest) items are at the start
2259    * of the array. Not a stable sort, unless the Comparator is so contrived.
2260    *
2261    * @param items will be partially-sorted in place
2262    * @param comp a Comparator; null means use natural comparison
2263    */
2264    static <T> void partialSort(T[] items, Comparator<T> comp, int limit)
2265    {
2266        if (comp == null) {
2267            //noinspection unchecked
2268            comp = (Comparator<T>) ComparatorUtils.naturalComparator();
2269        }
2270        new Quicksorter<T>(items, comp).partialSort(limit);
2271    }
2272
2273    /**
2274     * Stable partial sort of a list. Returns the desired head of the list.
2275     */
2276    public static <T> List<T> stablePartialSort(
2277        final List<T> list, final Comparator<T> comp, int limit)
2278    {
2279        return stablePartialSort(list, comp, limit, 0);
2280    }
2281
2282    /**
2283     * Stable partial sort of a list, using a specified algorithm.
2284     */
2285    public static <T> List<T> stablePartialSort(
2286        final List<T> list, final Comparator<T> comp, int limit, int algorithm)
2287    {
2288        assert limit <= list.size();
2289        assert list.size() > 0;
2290        for (;;) {
2291            switch (algorithm) {
2292            case 0:
2293                float ratio = (float) limit / (float) list.size();
2294                if (ratio <= .05) {
2295                    algorithm = 4; // julian's algorithm
2296                } else if (ratio <= .35) {
2297                    algorithm = 2; // marc's algorithm
2298                } else {
2299                    algorithm = 1; // array sort
2300                }
2301                break;
2302            case 1:
2303                return stablePartialSortArray(list, comp, limit);
2304            case 2:
2305                return stablePartialSortMarc(list, comp, limit);
2306            case 3:
2307                return stablePartialSortPedro(list, comp, limit);
2308            case 4:
2309                return stablePartialSortJulian(list, comp, limit);
2310            default:
2311                throw new RuntimeException();
2312            }
2313        }
2314    }
2315
2316    /**
2317     * Partial sort an array by sorting it and returning the first {@code limit}
2318     * elements. Fastest approach if limit is a significant fraction of the
2319     * list.
2320     */
2321    public static <T> List<T> stablePartialSortArray(
2322        final List<T> list, final Comparator<T> comp, int limit)
2323    {
2324        ArrayList<T> list2 = new ArrayList<T>(list);
2325        Collections.sort(list2, comp);
2326        return list2.subList(0, limit);
2327    }
2328
2329    /**
2330     * Marc's original algorithm for stable partial sort of a list.
2331     * Now superseded by {@link #stablePartialSortJulian}.
2332     */
2333    public static <T> List<T> stablePartialSortMarc(
2334        final List<T> list, final Comparator<T> comp, int limit)
2335    {
2336        assert limit >= 0;
2337
2338        // Load an array of pairs {list-item, list-index}.
2339        // List-index is a secondary sort key, to give a stable sort.
2340        // REVIEW Can we use a simple T[], with the index implied?
2341        // REVIEW When limit is big relative to list size, faster to
2342        // mergesort. Test for this.
2343        int n = list.size();            // O(n) to scan list
2344        @SuppressWarnings({"unchecked"})
2345        final ObjIntPair<T>[] pairs = new ObjIntPair[n];
2346
2347        int i = 0;
2348        for (T item : list) {           // O(n) to scan list
2349            pairs[i] = new ObjIntPair<T>(item, i);
2350            ++i;
2351        }
2352
2353        Comparator<ObjIntPair<T>> pairComp =
2354            new Comparator<ObjIntPair<T>>()
2355        {
2356            public int compare(ObjIntPair<T> x, ObjIntPair<T> y) {
2357                int val = comp.compare(x.t, y.t);
2358                if (val == 0) {
2359                    val = x.i - y.i;
2360                }
2361                return val;
2362            }
2363        };
2364
2365        final int length = Math.min(limit, n);
2366        // O(n + limit * log(limit)) to quicksort
2367        partialSort(pairs, pairComp, length);
2368
2369        // Use an abstract list to avoid doing a copy. The result is immutable.
2370        return new AbstractList<T>() {
2371            @Override
2372            public T get(int index) {
2373                return pairs[index].t;
2374            }
2375
2376            @Override
2377            public int size() {
2378                return length;
2379            }
2380        };
2381    }
2382
2383    /**
2384     * Pedro's algorithm for stably sorting the top {@code limit} items in
2385     * a list.
2386     */
2387    public static <T> List<T> stablePartialSortPedro(
2388        final List<T> list, final Comparator<T> comp, int limit)
2389    {
2390        final ObjIntPair<T>[] pairs = new ObjIntPair[limit];
2391        Comparator<ObjIntPair<T>> pairComp =
2392            new Comparator<ObjIntPair<T>>() {
2393                public int compare(ObjIntPair<T> x, ObjIntPair<T> y) {
2394                    int val = comp.compare(x.t, y.t);
2395                    if (val == 0) {
2396                        val = x.i - y.i;
2397                    }
2398                    return val;
2399                }
2400            };
2401
2402        int filled = 0;
2403        T maximum = null;
2404        int maximumIndex = 0;
2405        int originalIndex = 0;
2406        for (T item : list) { // O(n) to scan list
2407            switch (filled) {
2408            case 0:
2409                maximum = item;
2410                pairs[0] = new ObjIntPair<T>(item, originalIndex);
2411                filled++;
2412                break;
2413            default:
2414                if (filled < limit) {
2415                    pairs[filled] = new ObjIntPair<T>(item, originalIndex);
2416
2417                    if (comp.compare(item, maximum) > 0) {
2418                        maximum = item;
2419                        maximumIndex = filled;
2420                    }
2421                    filled++;
2422                } else {
2423                    if (comp.compare(item, maximum) < 0) {
2424                        pairs[maximumIndex] =
2425                            new ObjIntPair<T>(item, originalIndex);
2426                        maximum = pairs[0].t;
2427                        maximumIndex = 0;
2428                        for (int i = 0; i < filled; i++) {
2429                            if (comp.compare(pairs[i].t, maximum) > 0) {
2430                                maximum = pairs[i].t;
2431                                maximumIndex = i;
2432                            }
2433                        }
2434                    }
2435                }
2436            }
2437            originalIndex++;
2438        }
2439
2440        Arrays.sort(pairs, pairComp);
2441
2442        if (false)
2443        for (int i = 0; i < limit; i++) {
2444            T item = pairs[i].t;
2445            T originalItem = list.get(i);
2446            int itemIndex = pairs[i].i;
2447            if (itemIndex < i) {
2448                if (pairs[itemIndex].i > i) {
2449                    list.set(pairs[itemIndex].i, originalItem);
2450                }
2451            } else {
2452                list.set(itemIndex, originalItem);
2453            }
2454            list.set(i, item);
2455        }
2456
2457        List<T> result = new ArrayList<T>(limit);
2458        for (int i = 0; i < limit; i++) {
2459            result.add(list.get(pairs[i].i));
2460        }
2461        return result;
2462    }
2463
2464    /**
2465     * Julian's algorithm for stable partial sort. Improves Pedro's algorithm
2466     * by using a heap (priority queue) for the top {@code limit} items seen.
2467     * The items on the priority queue have an ordinal field, so the queue
2468     * can be used to generate a list of stably sorted items. (Heap sort is
2469     * not normally stable.)
2470     *
2471     * @param list List to sort
2472     * @param comp Comparator
2473     * @param limit Maximum number of items to return
2474     * @param <T> Element type
2475     * @return Sorted list, containing at most limit items
2476     */
2477    public static <T> List<T> stablePartialSortJulian(
2478        final List<T> list, final Comparator<T> comp, int limit)
2479    {
2480        final Comparator<ObjIntPair<T>> comp2 =
2481            new Comparator<ObjIntPair<T>>() {
2482                public int compare(ObjIntPair<T> o1, ObjIntPair<T> o2) {
2483                    int c = comp.compare(o1.t, o2.t);
2484                    if (c == 0) {
2485                        c = Util.compare(o1.i, o2.i);
2486                    }
2487                    return -c;
2488                }
2489            };
2490        int filled = 0;
2491        final PriorityQueue<ObjIntPair<T>> queue =
2492            new PriorityQueue<ObjIntPair<T>>(limit, comp2);
2493        for (T element : list) {
2494            if (filled < limit) {
2495                queue.offer(new ObjIntPair<T>(element, filled++));
2496            } else {
2497                ObjIntPair<T> head = queue.element();
2498                if (comp.compare(element, head.t) <= 0) {
2499                    ObjIntPair<T> item = new ObjIntPair<T>(element, filled++);
2500                    if (comp2.compare(item, head) >= 0) {
2501                        ObjIntPair poll = queue.remove();
2502                        Util.discard(poll);
2503                        queue.offer(item);
2504                    }
2505                }
2506            }
2507        }
2508
2509        int n = queue.size();
2510        final Object[] elements = new Object[n];
2511        while (n > 0) {
2512            elements[--n] = queue.poll().t;
2513        }
2514        assert queue.isEmpty();
2515        //noinspection unchecked
2516        return Arrays.asList((T[]) elements);
2517    }
2518
2519    static TupleList parseTupleList(
2520        Evaluator evaluator,
2521        String string,
2522        List<Hierarchy> hierarchies)
2523    {
2524        final IdentifierParser.TupleListBuilder builder =
2525            new IdentifierParser.TupleListBuilder(
2526                evaluator.getSchemaReader(),
2527                evaluator.getCube(),
2528                hierarchies);
2529        IdentifierParser.parseTupleList(builder, string);
2530        return builder.tupleList;
2531    }
2532
2533    /**
2534     * Parses a tuple, of the form '(member, member, ...)'.
2535     * There must be precisely one member for each hierarchy.
2536     *
2537     *
2538     * @param evaluator Evaluator, provides a {@link mondrian.olap.SchemaReader}
2539     *   and {@link mondrian.olap.Cube}
2540     * @param string String to parse
2541     * @param i Position to start parsing in string
2542     * @param members Output array of members
2543     * @param hierarchies Hierarchies of the members
2544     * @return Position where parsing ended in string
2545     */
2546    private static int parseTuple(
2547        final Evaluator evaluator,
2548        String string,
2549        int i,
2550        final Member[] members,
2551        List<Hierarchy> hierarchies)
2552    {
2553        final IdentifierParser.Builder builder =
2554            new IdentifierParser.TupleBuilder(
2555                evaluator.getSchemaReader(),
2556                evaluator.getCube(),
2557                hierarchies)
2558            {
2559                public void tupleComplete() {
2560                    super.tupleComplete();
2561                    memberList.toArray(members);
2562                }
2563            };
2564        return IdentifierParser.parseTuple(builder, string, i);
2565    }
2566
2567    /**
2568     * Parses a tuple, such as "([Gender].[M], [Marital Status].[S])".
2569     *
2570     * @param evaluator Evaluator, provides a {@link mondrian.olap.SchemaReader}
2571     *   and {@link mondrian.olap.Cube}
2572     * @param string String to parse
2573     * @param hierarchies Hierarchies of the members
2574     * @return Tuple represented as array of members
2575     */
2576    static Member[] parseTuple(
2577        Evaluator evaluator,
2578        String string,
2579        List<Hierarchy> hierarchies)
2580    {
2581        final Member[] members = new Member[hierarchies.size()];
2582        int i = parseTuple(evaluator, string, 0, members, hierarchies);
2583        // todo: check for garbage at end of string
2584        if (FunUtil.tupleContainsNullMember(members)) {
2585            return null;
2586        }
2587        return members;
2588    }
2589
2590    static List<Member> parseMemberList(
2591        Evaluator evaluator,
2592        String string,
2593        Hierarchy hierarchy)
2594    {
2595        IdentifierParser.MemberListBuilder builder =
2596            new IdentifierParser.MemberListBuilder(
2597                evaluator.getSchemaReader(),
2598                evaluator.getCube(),
2599                hierarchy);
2600        IdentifierParser.parseMemberList(builder, string);
2601        return builder.memberList;
2602    }
2603
2604    private static int parseMember(
2605        Evaluator evaluator,
2606        String string,
2607        int i,
2608        final Member[] members,
2609        Hierarchy hierarchy)
2610    {
2611        IdentifierParser.MemberListBuilder builder =
2612            new IdentifierParser.MemberListBuilder(
2613                evaluator.getSchemaReader(), evaluator.getCube(), hierarchy)
2614            {
2615                @Override
2616                public void memberComplete() {
2617                    members[0] = resolveMember(hierarchyList.get(0));
2618                    segmentList.clear();
2619                }
2620            };
2621        return IdentifierParser.parseMember(builder, string, i);
2622    }
2623
2624    static Member parseMember(
2625        Evaluator evaluator, String string, Hierarchy hierarchy)
2626    {
2627        Member[] members = {null};
2628        int i = parseMember(evaluator, string, 0, members, hierarchy);
2629        // todo: check for garbage at end of string
2630        final Member member = members[0];
2631        if (member == null) {
2632            throw MondrianResource.instance().MdxChildObjectNotFound.ex(
2633                string, evaluator.getCube().getQualifiedName());
2634        }
2635        return member;
2636    }
2637
2638    /**
2639     * Returns whether an expression is worth wrapping in "Cache( ... )".
2640     *
2641     * @param exp Expression
2642     * @return Whether worth caching
2643     */
2644    public static boolean worthCaching(Exp exp) {
2645        // Literal is not worth caching.
2646        if (exp instanceof Literal) {
2647            return false;
2648        }
2649        // Member, hierarchy, level, or dimension expression is not worth
2650        // caching.
2651        if (exp instanceof MemberExpr
2652            || exp instanceof LevelExpr
2653            || exp instanceof HierarchyExpr
2654            || exp instanceof DimensionExpr)
2655        {
2656            return false;
2657        }
2658        if (exp instanceof ResolvedFunCall) {
2659            ResolvedFunCall call = (ResolvedFunCall) exp;
2660
2661            // A set of literals is not worth caching.
2662            if (call.getFunDef() instanceof SetFunDef) {
2663                for (Exp setArg : call.getArgs()) {
2664                    if (worthCaching(setArg)) {
2665                        return true;
2666                    }
2667                }
2668                return false;
2669            }
2670        }
2671        return true;
2672    }
2673
2674    // ~ Inner classes ---------------------------------------------------------
2675
2676    /**
2677     * A functional for {@link FunUtil#partialSort}.
2678     * Sorts or partially sorts an array in ascending order, using a Comparator.
2679     *
2680     * <p>Algorithm: quicksort, or partial quicksort (alias
2681     * "quickselect"), Hoare/Singleton.  Partial quicksort is
2682     * quicksort that recurs only on one side, which is thus
2683     * tail-recursion.  Picks pivot as median of three; falls back on
2684     * insertion sort for small "subfiles".  Partial quicksort is O(n
2685     * + m log m), instead of O(n log n), where n is the input size,
2686     * and m is the desired output size.
2687     *
2688     * <p>See D Knuth, Art of Computer Programming, 5.2.2 (Algorithm
2689     * Q); R. Sedgewick, Algorithms in C, ch 5.  Good summary in
2690     * http://en.wikipedia.org/wiki/Selection_algorithm
2691     *
2692     * <P>TODO: What is the time-cost of this functor and of the nested
2693     * Comparators?
2694     */
2695    static class Quicksorter<T> {
2696        // size of smallest set worth a quicksort
2697        public final int TOO_SMALL = 8;
2698
2699        private static final Logger LOGGER =
2700            Logger.getLogger(Quicksorter.class);
2701        private final T[] vec;
2702        private final Comparator<T> comp;
2703        private final boolean traced;
2704        private long partitions, comparisons, exchanges; // stats
2705
2706        public Quicksorter(T[] vec, Comparator<T> comp) {
2707            this.vec = vec;
2708            this.comp = comp;
2709            partitions = comparisons = exchanges = 0;
2710            traced = LOGGER.isDebugEnabled();
2711        }
2712
2713        private void traceStats(String prefix) {
2714            StringBuilder sb = new StringBuilder(prefix);
2715            sb.append(": ");
2716            sb.append(partitions).append(" partitions, ");
2717            sb.append(comparisons).append(" comparisons, ");
2718            sb.append(exchanges).append(" exchanges.");
2719            LOGGER.debug(sb.toString());
2720        }
2721
2722        // equivalent to operator <
2723        private boolean less(T x, T y) {
2724            comparisons++;
2725            return comp.compare(x, y) < 0;
2726        }
2727
2728        // equivalent to operator >
2729        private boolean more(T x, T y) {
2730            comparisons++;
2731            return comp.compare(x, y) > 0;
2732        }
2733        // equivalent to operator >
2734        private boolean equal(T x, T y) {
2735            comparisons++;
2736            return comp.compare(x, y) == 0;
2737        }
2738
2739        // swaps two items (identified by index in vec[])
2740        private void swap(int i, int j) {
2741            exchanges++;
2742            T temp = vec[i];
2743            vec[i] = vec[j];
2744            vec[j] = temp;
2745        }
2746
2747        // puts into ascending order three items
2748        // (identified by index in vec[])
2749        // REVIEW: use only 2 comparisons??
2750        private void order3(int i, int j, int k) {
2751            if (more(vec[i], vec[j])) {
2752                swap(i, j);
2753            }
2754            if (more(vec[i], vec[k])) {
2755                swap(i, k);
2756            }
2757            if (more(vec[j], vec[k])) {
2758                swap(j, k);
2759            }
2760        }
2761
2762        // runs a selection sort on the array segment VEC[START .. END]
2763        private void selectionSort(int start, int end) {
2764            for (int i = start; i < end; ++i) {
2765                // pick the min of vec[i, end]
2766                int pmin = i;
2767                for (int j = i + 1; j <= end; ++j) {
2768                    if (less(vec[j], vec[pmin])) {
2769                        pmin = j;
2770                    }
2771                }
2772                if (pmin != i) {
2773                    swap(i, pmin);
2774                }
2775            }
2776        }
2777
2778        /**
2779         * Runs one pass of quicksort on array segment VEC[START .. END],
2780         * dividing it into two parts, the left side VEC[START .. P] none
2781         * greater than the pivot value VEC[P], and the right side VEC[P+1
2782         * .. END] none less than the pivot value. Returns P, the index of the
2783         * pivot element in VEC[].
2784         */
2785        private int partition(int start, int end) {
2786            partitions++;
2787            assert start <= end;
2788
2789            // Find median of three (both ends and the middle).
2790            // TODO: use pseudo-median of nine when array segment is big enough.
2791            int mid = (start + end) / 2;
2792            order3(start, mid, end);
2793            if (end - start <= 2) {
2794                return mid;        // sorted!
2795            }
2796
2797            // Now the left and right ends are in place (ie in the correct
2798            // partition), and will serve as sentinels for scanning. Pick middle
2799            // as pivot and set it aside, in penultimate position.
2800            final T pivot = vec[mid];
2801            swap(mid, end - 1);
2802
2803            // Scan inward from both ends, swapping misplaced items.
2804            int left = start + 1;       // vec[start] is in place
2805            int right = end - 2;        // vec[end - 1] is pivot
2806            while (left < right) {
2807                // scan past items in correct place, but stop at a pivot value
2808                // (Sedgewick's idea).
2809                while (less(vec[left], pivot)) {
2810                    ++left;
2811                }
2812                while (less(pivot, vec[right])) {
2813                    --right;
2814                }
2815                if (debug) {
2816                    assert (left <= end) && (right >= start);
2817                }
2818                if (left < right) {     // found a misplaced pair
2819                    swap(left, right);
2820                    ++left; --right;
2821                }
2822            }
2823            if ((left == right) && less(vec[left], pivot)) {
2824                ++left;
2825            }
2826
2827            // All scanned. Restore pivot to its rightful place.
2828            swap(left, end - 1);
2829
2830            if (debug) {
2831                for (int i = start; i < left; i++) {
2832                    assert !more(vec[i], pivot);
2833                }
2834                assert equal(vec[left], pivot);
2835                for (int i = left + 1;  i <= end;  i++) {
2836                    assert !less(vec[i], pivot);
2837                }
2838            }
2839            return left;
2840        }
2841
2842
2843        // Runs quicksort on VEC[START, END]. Recursive version,
2844        // TODO: exploit tail recursion
2845        private void sort(int start, int end) {
2846            if (end - start < TOO_SMALL) {
2847                selectionSort(start, end);
2848                return;
2849            }
2850
2851            // Split data, so that left side dominates the right side
2852            // (but neither is sorted):
2853            int mid = partition(start, end);
2854            sort(start, mid - 1);
2855            sort(mid + 1, end);
2856        }
2857
2858        // Runs quickselect(LIMIT) on VEC[START, END]. Recursive version,
2859        // TODO: exploit tail recursion, unfold.
2860        private void select(int limit, int start, int end) {
2861            if (limit == 0) {
2862                return;
2863            }
2864            if (end - start < TOO_SMALL) {
2865                selectionSort(start, end);
2866                return;
2867            }
2868            int mid = partition(start, end);
2869            int leftSize = mid - start + 1;
2870            if (limit < leftSize) {
2871                // work on the left side, and ignore the right side
2872                select(limit, start, mid);
2873            } else {
2874                limit -= leftSize;
2875                // work on the right side, but keep the left side
2876                select(limit, mid + 1, end);
2877            }
2878        }
2879
2880        public void sort() {
2881            int n = vec.length - 1;
2882            sort(0, n);
2883            if (traced) {
2884                traceStats("quicksort on " + n + "items");
2885            }
2886        }
2887
2888        /** puts the LIMIT biggest items at the head, not sorted */
2889        public void select(int limit) {
2890            int n = vec.length - 1;
2891            select(limit, 0, n);
2892            if (traced) {
2893                traceStats("quickselect for " + limit + " from" + n + "items");
2894            }
2895        }
2896
2897        public void partialSort(int limit) {
2898            int n = vec.length - 1;
2899            select(limit, 0, n);
2900            if (traced) {
2901                traceStats(
2902                    "partial sort: quickselect phase for "
2903                    + limit + "from " + n + "items");
2904            }
2905            sort(0, limit - 1);
2906            if (traced) {
2907                traceStats("partial sort: quicksort phase on " + n + "items");
2908            }
2909        }
2910    }
2911
2912    /**
2913     * Comparator for members.
2914     *
2915     * <p>Could genericize this to <code>class&lt;T&gt; MemorizingComparator
2916     * implements Comparator&lt;T&gt;</code>, but not if it adds a run time
2917     * cost, since the comparator is at the heart of the sort algorithms.
2918     */
2919    private static abstract class MemberComparator implements Comparator<Member>
2920    {
2921        private static final Logger LOGGER =
2922            Logger.getLogger(MemberComparator.class);
2923        final Evaluator evaluator;
2924        final Calc exp;
2925
2926        private final int descMask;
2927        private final Map<Member, Object> valueMap;
2928
2929        MemberComparator(Evaluator evaluator, Calc exp, boolean desc)
2930        {
2931            this.evaluator = evaluator;
2932            this.exp = exp;
2933            this.descMask = desc ? -1 : 1;
2934            this.valueMap = new HashMap<Member, Object>();
2935        }
2936
2937        private int maybeNegate(int c) {
2938            return descMask * c;
2939        }
2940
2941        // applies the Calc to a member, memorizing results
2942        protected Object eval(Member m)
2943        {
2944            Object val = valueMap.get(m);
2945            if (val == null) {
2946                evaluator.setContext(m);
2947                val = exp.evaluate(evaluator);
2948                if (val == null) {
2949                    val = Util.nullValue;
2950                }
2951                valueMap.put(m, val);
2952            }
2953            return val;
2954        }
2955
2956        // wraps comparison with tracing
2957        Comparator<Member> wrap() {
2958            final MemberComparator comparator = this;
2959            if (LOGGER.isDebugEnabled()) {
2960                return new Comparator<Member>() {
2961                    public int compare(Member m1, Member m2) {
2962                        final int c = comparator.compare(m1, m2);
2963                        // here guaranteed that eval(m) finds a memorized value
2964                        LOGGER.debug(
2965                            "compare "
2966                            + m1.getUniqueName() + "(" + eval(m1) + "), "
2967                            + m2.getUniqueName() + "(" + eval(m2) + ")"
2968                            + " yields " + c);
2969                        return c;
2970                    }
2971                };
2972            } else {
2973                return this;
2974            }
2975        }
2976
2977        // Preloads the value map with precomputed members (supplied as a map).
2978        void preloadValues(Map<Member, Object> map) {
2979            valueMap.putAll(map);
2980        }
2981
2982        // Preloads the value map by applying the expression to a Collection of
2983        // members.
2984        void preloadValues(Collection<Member> members) {
2985            for (Member m : members) {
2986                eval(m);
2987            }
2988        }
2989
2990        protected final int compareByValue(Member m1, Member m2) {
2991            final int c = FunUtil.compareValues(eval(m1), eval(m2));
2992            return maybeNegate(c);
2993        }
2994
2995        protected final int compareHierarchicallyButSiblingsByValue(
2996            Member m1, Member m2)
2997        {
2998            if (FunUtil.equals(m1, m2)) {
2999                return 0;
3000            }
3001            while (true) {
3002                int depth1 = m1.getDepth(),
3003                    depth2 = m2.getDepth();
3004                if (depth1 < depth2) {
3005                    m2 = m2.getParentMember();
3006                    if (Util.equals(m1, m2)) {
3007                        return -1;
3008                    }
3009                } else if (depth1 > depth2) {
3010                    m1 = m1.getParentMember();
3011                    if (Util.equals(m1, m2)) {
3012                        return 1;
3013                    }
3014                } else {
3015                    Member prev1 = m1, prev2 = m2;
3016                    m1 = m1.getParentMember();
3017                    m2 = m2.getParentMember();
3018                    if (Util.equals(m1, m2)) {
3019                        // including case where both parents are null
3020                        int c = compareByValue(prev1, prev2);
3021                        if (c != 0) {
3022                            return c;
3023                        }
3024                        // prev1 and prev2 are siblings.  Order according to
3025                        // hierarchy, if the values do not differ.  Needed to
3026                        // have a consistent sortMembers if members with equal
3027                        // (null!)  values are compared.
3028                        c = FunUtil.compareSiblingMembers(prev1, prev2);
3029
3030                        // Do not negate c, even if we are sorting descending.
3031                        // This comparison is to achieve the 'natural order'.
3032                        return c;
3033                    }
3034                }
3035            }
3036        }
3037    }
3038
3039    private static class HierarchicalMemberComparator
3040        extends MemberComparator
3041    {
3042        HierarchicalMemberComparator(
3043            Evaluator evaluator, Calc exp, boolean desc)
3044        {
3045            super(evaluator, exp, desc);
3046        }
3047
3048        public int compare(Member m1, Member m2) {
3049            return compareHierarchicallyButSiblingsByValue(m1, m2);
3050        }
3051    }
3052
3053    private static class BreakMemberComparator extends MemberComparator {
3054        BreakMemberComparator(Evaluator evaluator, Calc exp, boolean desc)
3055        {
3056            super(evaluator, exp, desc);
3057        }
3058
3059        public final int compare(Member m1, Member m2) {
3060            return compareByValue(m1, m2);
3061        }
3062    }
3063
3064    /**
3065     * Compares tuples, which are represented as lists of {@link Member}s.
3066     */
3067    private static abstract class TupleComparator
3068        implements Comparator<List<Member>>
3069    {
3070        final int arity;
3071        TupleComparator(int arity) {
3072            this.arity = arity;
3073        }
3074    }
3075
3076    /**
3077     * Extension to {@link TupleComparator} which compares tuples by evaluating
3078     * an expression.
3079     */
3080    private static abstract class TupleExpComparator extends TupleComparator {
3081        Evaluator evaluator;
3082        final Calc calc;
3083
3084        TupleExpComparator(Evaluator evaluator, Calc calc, int arity) {
3085            super(arity);
3086            this.evaluator = evaluator;
3087            this.calc = calc;
3088        }
3089    }
3090
3091    private static class HierarchicalTupleComparator
3092        extends TupleExpComparator
3093    {
3094        private final boolean desc;
3095
3096        HierarchicalTupleComparator(
3097            Evaluator evaluator, Calc calc, int arity, boolean desc)
3098        {
3099            super(evaluator, calc, arity);
3100            this.desc = desc;
3101        }
3102
3103        public int compare(List<Member> a1, List<Member> a2) {
3104            int c = 0;
3105            final int savepoint = evaluator.savepoint();
3106            try {
3107                for (int i = 0; i < arity; i++) {
3108                    Member m1 = a1.get(i), m2 = a2.get(i);
3109                    c = compareHierarchicallyButSiblingsByValue(m1, m2);
3110                    if (c != 0) {
3111                        break;
3112                    }
3113                    // compareHierarchicallyButSiblingsByValue imposes a
3114                    // total order
3115                    assert m1.equals(m2);
3116                    evaluator.setContext(m1);
3117                }
3118            } finally {
3119                evaluator.restore(savepoint);
3120            }
3121            return c;
3122        }
3123
3124        protected int compareHierarchicallyButSiblingsByValue(
3125            Member m1,
3126            Member m2)
3127        {
3128            if (FunUtil.equals(m1, m2)) {
3129                return 0;
3130            }
3131            while (true) {
3132                int depth1 = m1.getDepth(),
3133                        depth2 = m2.getDepth();
3134                if (depth1 < depth2) {
3135                    m2 = m2.getParentMember();
3136                    if (FunUtil.equals(m1, m2)) {
3137                        return -1;
3138                    }
3139                } else if (depth1 > depth2) {
3140                    m1 = m1.getParentMember();
3141                    if (FunUtil.equals(m1, m2)) {
3142                        return 1;
3143                    }
3144                } else {
3145                    Member prev1 = m1, prev2 = m2;
3146                    m1 = m1.getParentMember();
3147                    m2 = m2.getParentMember();
3148                    if (FunUtil.equals(m1, m2)) {
3149                        // including case where both parents are null
3150                        int c = compareByValue(prev1, prev2);
3151                        if (c == 0) {
3152                            c = FunUtil.compareSiblingMembers(prev1, prev2);
3153                        }
3154                        return desc ? -c : c;
3155                    }
3156                }
3157            }
3158        }
3159
3160        private int compareByValue(Member m1, Member m2) {
3161            int c;
3162            final int savepoint = evaluator.savepoint();
3163            try {
3164                evaluator.setContext(m1);
3165                Object v1 = calc.evaluate(evaluator);
3166                evaluator.setContext(m2);
3167                Object v2 = calc.evaluate(evaluator);
3168                c = FunUtil.compareValues(v1, v2);
3169                return c;
3170            } finally {
3171                // important to restore the evaluator state
3172                evaluator.restore(savepoint);
3173            }
3174        }
3175    }
3176
3177    // almost the same as MemberComparator
3178    static abstract class TupleExpMemoComparator extends TupleExpComparator {
3179        private final Map<List<Member>, Object> valueMap =
3180            new HashMap<List<Member>, Object>();
3181
3182        TupleExpMemoComparator(Evaluator e, Calc calc, int arity)
3183        {
3184            super(e, calc, arity);
3185        }
3186
3187        // applies the Calc to a tuple, memorizing results
3188        protected Object eval(List<Member> t)
3189        {
3190            Object val = valueMap.get(t);
3191            if (val != null) {
3192                return val;
3193            }
3194            return compute(t);
3195        }
3196
3197        private Object compute(List<Member> key) {
3198            evaluator.setContext(key);
3199            Object val = calc.evaluate(evaluator);
3200            if (val == null) {
3201                val = Util.nullValue;
3202            }
3203            valueMap.put(key, val);
3204            return val;
3205        }
3206
3207        // Preloads the value map by applying the expression to a Collection of
3208        // members.
3209        void preloadValues(TupleList tuples) {
3210            for (List<Member> t : tuples) {
3211                compute(t);
3212            }
3213        }
3214    }
3215
3216    private static class BreakTupleComparator extends TupleExpMemoComparator {
3217        BreakTupleComparator(Evaluator e, Calc calc, int arity) {
3218            super(e, calc, arity);
3219        }
3220
3221        public int compare(List<Member> a1, List<Member> a2) {
3222            return FunUtil.compareValues(eval(a1), eval(a2));
3223        }
3224    }
3225
3226    private static class HierarchicalTupleKeyComparator
3227        extends TupleExpMemoComparator
3228    {
3229
3230        HierarchicalTupleKeyComparator(Evaluator e, Calc calc, int arity) {
3231            super(e, calc, arity);
3232        }
3233
3234        public int compare(List<Member> a1, List<Member> a2) {
3235            OrderKey k1 = (OrderKey) eval(a1);
3236            OrderKey k2 = (OrderKey) eval(a2);
3237            return compareMemberOrderKeysHierarchically(k1, k2);
3238        }
3239
3240        private int compareMemberOrderKeysHierarchically(
3241            OrderKey k1, OrderKey k2)
3242        {
3243            // null is less than anything else
3244            if (k1 == Util.nullValue) {
3245                return -1;
3246            }
3247            if (k2 == Util.nullValue) {
3248                return 1;
3249            }
3250            Member m1 = k1.member;
3251            Member m2 = k2.member;
3252            if (FunUtil.equals(m1, m2)) {
3253                return 0;
3254            }
3255            while (true) {
3256                int depth1 = m1.getDepth(),
3257                        depth2 = m2.getDepth();
3258                if (depth1 < depth2) {
3259                    m2 = m2.getParentMember();
3260                    if (FunUtil.equals(m1, m2)) {
3261                        return -1;
3262                    }
3263                } else if (depth1 > depth2) {
3264                    m1 = m1.getParentMember();
3265                    if (FunUtil.equals(m1, m2)) {
3266                        return 1;
3267                    }
3268                } else {
3269                    Member prev1 = m1, prev2 = m2;
3270                    m1 = m1.getParentMember();
3271                    m2 = m2.getParentMember();
3272                    if (FunUtil.equals(m1, m2)) {
3273                        OrderKey pk1 = new OrderKey(prev1);
3274                        OrderKey pk2 = new OrderKey(prev2);
3275                        return FunUtil.compareValues(pk1, pk2);
3276                    }
3277                }
3278            }
3279        }
3280    }
3281
3282    /**
3283     * Compares lists of {@link Member}s so as to convert them into hierarchical
3284     * order. Applies lexicographic order to the array.
3285     */
3286    private static class HierarchizeTupleComparator extends TupleComparator {
3287        private final boolean post;
3288
3289        HierarchizeTupleComparator(int arity, boolean post) {
3290            super(arity);
3291            this.post = post;
3292        }
3293
3294        public int compare(List<Member> a1, List<Member> a2) {
3295            for (int i = 0; i < arity; i++) {
3296                Member m1 = a1.get(i), m2 = a2.get(i);
3297                int c = FunUtil.compareHierarchically(m1, m2, post);
3298                if (c != 0) {
3299                    return c;
3300                }
3301            }
3302            return 0;
3303        }
3304    }
3305
3306    /**
3307     * Compares {@link Member}s so as to arrage them in prefix or postfix
3308     * hierarchical order.
3309     */
3310    private static class HierarchizeComparator implements Comparator<Member> {
3311        private final boolean post;
3312
3313        HierarchizeComparator(boolean post) {
3314            this.post = post;
3315        }
3316        public int compare(Member m1, Member m2) {
3317            return FunUtil.compareHierarchically(m1, m2, post);
3318        }
3319    }
3320
3321    static class SetWrapper {
3322        List v = new ArrayList();
3323        public int errorCount = 0, nullCount = 0;
3324
3325        // private double avg = Double.NaN;
3326        // TODO: parameterize inclusion of nulls
3327        // by making this a method of the SetWrapper, we can cache the result
3328        // this allows its reuse in Correlation
3329        // public double getAverage() {
3330        //     if (avg == Double.NaN) {
3331        //         double sum = 0.0;
3332        //         for (int i = 0; i < resolvers.size(); i++) {
3333        //             sum += ((Number) resolvers.elementAt(i)).doubleValue();
3334        //         }
3335        //         // TODO: should look at context and optionally include nulls
3336        //         avg = sum / (double) resolvers.size();
3337        //     }
3338        //     return avg;
3339        // }
3340    }
3341
3342    /**
3343     * Compares cell values, so that larger values compare first.
3344     *
3345     * <p>Nulls compare last, exceptions (including the
3346     * object which indicates the the cell is not in the cache yet) next,
3347     * then numbers and strings are compared by value.
3348     */
3349    public static class DescendingValueComparator implements Comparator {
3350        /**
3351         * The singleton.
3352         */
3353        static final DescendingValueComparator instance =
3354                new DescendingValueComparator();
3355
3356        public int compare(Object o1, Object o2) {
3357            return - compareValues(o1, o2);
3358        }
3359    }
3360
3361    /**
3362     * Null member of unknown hierarchy.
3363     */
3364    private static class NullMember implements Member {
3365        public Member getParentMember() {
3366            throw new UnsupportedOperationException();
3367        }
3368
3369        public Level getLevel() {
3370            throw new UnsupportedOperationException();
3371        }
3372
3373        public Hierarchy getHierarchy() {
3374            throw new UnsupportedOperationException();
3375        }
3376
3377        public String getParentUniqueName() {
3378            throw new UnsupportedOperationException();
3379        }
3380
3381        public MemberType getMemberType() {
3382            throw new UnsupportedOperationException();
3383        }
3384
3385        public boolean isParentChildLeaf() {
3386            return false;
3387        }
3388
3389        public void setName(String name) {
3390            throw new UnsupportedOperationException();
3391        }
3392
3393        public boolean isAll() {
3394            return false;
3395        }
3396
3397        public boolean isMeasure() {
3398            throw new UnsupportedOperationException();
3399        }
3400
3401        public boolean isNull() {
3402            return true;
3403        }
3404
3405        public boolean isChildOrEqualTo(Member member) {
3406            throw new UnsupportedOperationException();
3407        }
3408
3409        public boolean isCalculated() {
3410            throw new UnsupportedOperationException();
3411        }
3412
3413        public boolean isEvaluated() {
3414            throw new UnsupportedOperationException();
3415        }
3416
3417        public int getSolveOrder() {
3418            throw new UnsupportedOperationException();
3419        }
3420
3421        public Exp getExpression() {
3422            throw new UnsupportedOperationException();
3423        }
3424
3425        public List<Member> getAncestorMembers() {
3426            throw new UnsupportedOperationException();
3427        }
3428
3429        public boolean isCalculatedInQuery() {
3430            throw new UnsupportedOperationException();
3431        }
3432
3433        public Object getPropertyValue(String propertyName) {
3434            throw new UnsupportedOperationException();
3435        }
3436
3437        public Object getPropertyValue(String propertyName, boolean matchCase) {
3438            throw new UnsupportedOperationException();
3439        }
3440
3441        public String getPropertyFormattedValue(String propertyName) {
3442            throw new UnsupportedOperationException();
3443        }
3444
3445        public void setProperty(String name, Object value) {
3446            throw new UnsupportedOperationException();
3447        }
3448
3449        public Property[] getProperties() {
3450            throw new UnsupportedOperationException();
3451        }
3452
3453        public int getOrdinal() {
3454            throw new UnsupportedOperationException();
3455        }
3456
3457        public Comparable getOrderKey() {
3458            throw new UnsupportedOperationException();
3459        }
3460
3461        public boolean isHidden() {
3462            throw new UnsupportedOperationException();
3463        }
3464
3465        public int getDepth() {
3466            throw new UnsupportedOperationException();
3467        }
3468
3469        public Member getDataMember() {
3470            throw new UnsupportedOperationException();
3471        }
3472
3473        public String getUniqueName() {
3474            throw new UnsupportedOperationException();
3475        }
3476
3477        public String getName() {
3478            throw new UnsupportedOperationException();
3479        }
3480
3481        public String getDescription() {
3482            throw new UnsupportedOperationException();
3483        }
3484
3485        public OlapElement lookupChild(
3486            SchemaReader schemaReader, Id.Segment s, MatchType matchType)
3487        {
3488            throw new UnsupportedOperationException();
3489        }
3490
3491        public String getQualifiedName() {
3492            throw new UnsupportedOperationException();
3493        }
3494
3495        public String getCaption() {
3496            throw new UnsupportedOperationException();
3497        }
3498
3499        public String getLocalized(LocalizedProperty prop, Locale locale) {
3500            throw new UnsupportedOperationException();
3501        }
3502
3503        public boolean isVisible() {
3504            throw new UnsupportedOperationException();
3505        }
3506
3507        public Dimension getDimension() {
3508            throw new UnsupportedOperationException();
3509        }
3510
3511        public Map<String, Annotation> getAnnotationMap() {
3512            throw new UnsupportedOperationException();
3513        }
3514
3515        public int compareTo(Object o) {
3516            throw new UnsupportedOperationException();
3517        }
3518
3519        public boolean equals(Object obj) {
3520            throw new UnsupportedOperationException();
3521        }
3522
3523        public int hashCode() {
3524            throw new UnsupportedOperationException();
3525        }
3526    }
3527
3528    /**
3529     * Enumeration of the flags allowed to the {@code ORDER} MDX function.
3530     */
3531    enum Flag {
3532        ASC(false, false),
3533        DESC(true, false),
3534        BASC(false, true),
3535        BDESC(true, true);
3536
3537        final boolean descending;
3538        final boolean brk;
3539
3540        Flag(boolean descending, boolean brk) {
3541            this.descending = descending;
3542            this.brk = brk;
3543        }
3544
3545        public static String[] getNames() {
3546            List<String> names = new ArrayList<String>();
3547            for (Flag flags : Flag.class.getEnumConstants()) {
3548                names.add(flags.name());
3549            }
3550            return names.toArray(new String[names.size()]);
3551        }
3552    }
3553
3554    static class SortKeySpec {
3555        private final Calc key;
3556        private final Flag direction;
3557
3558        SortKeySpec(Calc key, Flag dir) {
3559            this.key = key;
3560            this.direction = dir;
3561        }
3562
3563        Calc getKey() {
3564            return this.key;
3565        }
3566
3567        Flag getDirection() {
3568            return this.direction;
3569        }
3570    }
3571
3572    public static class OrderKey implements Comparable {
3573        private final Member member;
3574
3575        public OrderKey(Member member) {
3576            super();
3577            this.member = member;
3578        }
3579
3580        public int compareTo(Object o) {
3581            assert o instanceof OrderKey;
3582            Member otherMember = ((OrderKey) o).member;
3583            final boolean thisCalculated = this.member.isCalculatedInQuery();
3584            final boolean otherCalculated = otherMember.isCalculatedInQuery();
3585            if (thisCalculated) {
3586                if (!otherCalculated) {
3587                    return 1;
3588                }
3589            } else {
3590                if (otherCalculated) {
3591                    return -1;
3592                }
3593            }
3594            final Comparable thisKey = this.member.getOrderKey();
3595            final Comparable otherKey = otherMember.getOrderKey();
3596            if ((thisKey != null) && (otherKey != null)) {
3597                return thisKey.compareTo(otherKey);
3598            } else {
3599                return this.member.compareTo(otherMember);
3600            }
3601        }
3602    }
3603
3604    /**
3605     * Tuple consisting of an object and an integer.
3606     *
3607     * <p>Similar to {@link Pair}, but saves boxing overhead of converting
3608     * {@code int} to {@link Integer}.
3609     */
3610    public static class ObjIntPair<T> {
3611        final T t;
3612        final int i;
3613
3614        public ObjIntPair(T t, int i) {
3615            this.t = t;
3616            this.i = i;
3617        }
3618
3619        public int hashCode() {
3620            return Util.hash(i, t);
3621        }
3622
3623        public boolean equals(Object obj) {
3624            return this == obj
3625                || obj instanceof ObjIntPair
3626                && this.i == ((ObjIntPair) obj).i
3627                && Util.equals(this.t, ((ObjIntPair) obj).t);
3628        }
3629
3630        public String toString() {
3631            return "<" + t + ", " + i + ">";
3632        }
3633    }
3634}
3635
3636// End FunUtil.java