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