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