001 /*
002 // $Id: //open/mondrian/src/main/mondrian/olap/fun/RankFunDef.java#16 $
003 // This software is subject to the terms of the Common Public License
004 // Agreement, available at the following URL:
005 // http://www.opensource.org/licenses/cpl.html.
006 // Copyright (C) 2005-2008 Julian Hyde
007 // All Rights Reserved.
008 // You must accept the terms of that agreement to use this software.
009 */
010
011 package mondrian.olap.fun;
012
013 import mondrian.olap.*;
014 import mondrian.olap.type.*;
015 import mondrian.calc.*;
016 import mondrian.calc.impl.*;
017 import mondrian.rolap.RolapUtil;
018 import mondrian.mdx.ResolvedFunCall;
019
020 import java.util.*;
021 import java.io.PrintWriter;
022
023 /**
024 * Definition of the <code>RANK</code> MDX function.
025 *
026 * @author Richard Emberson
027 * @since 17 January, 2005
028 * @version $Id: //open/mondrian/src/main/mondrian/olap/fun/RankFunDef.java#16 $
029 */
030 public class RankFunDef extends FunDefBase {
031 static final boolean debug = false;
032 static final ReflectiveMultiResolver Resolver = new ReflectiveMultiResolver(
033 "Rank",
034 "Rank(<Tuple>, <Set> [, <Calc Expression>])",
035 "Returns the one-based rank of a tuple in a set.",
036 new String[]{"fitx", "fitxn", "fimx", "fimxn"},
037 RankFunDef.class);
038
039 public RankFunDef(FunDef dummyFunDef) {
040 super(dummyFunDef);
041 }
042
043 public Calc compileCall(ResolvedFunCall call, ExpCompiler compiler) {
044 switch (call.getArgCount()) {
045 case 2:
046 return compileCall2(call, compiler);
047 case 3:
048 return compileCall3(call, compiler);
049 default:
050 throw Util.newInternal("invalid arg count " + call.getArgCount());
051 }
052 }
053
054 public Calc compileCall3(ResolvedFunCall call, ExpCompiler compiler) {
055 final Type type0 = call.getArg(0).getType();
056 if (type0 instanceof TupleType) {
057 final TupleCalc tupleCalc =
058 compiler.compileTuple(call.getArg(0));
059 final ListCalc listCalc =
060 compiler.compileList(call.getArg(1));
061 final Calc sortCalc =
062 compiler.compileScalar(call.getArg(2), true);
063 Calc sortedListCalc =
064 new SortCalc(call, listCalc, sortCalc);
065 final ExpCacheDescriptor cacheDescriptor =
066 new ExpCacheDescriptor(
067 call, sortedListCalc, compiler.getEvaluator());
068 return new Rank3TupleCalc(call, tupleCalc, sortCalc, cacheDescriptor);
069 } else {
070 final MemberCalc memberCalc =
071 compiler.compileMember(call.getArg(0));
072 final ListCalc listCalc = compiler.compileList(call.getArg(1));
073 final Calc sortCalc = compiler.compileScalar(call.getArg(2), true);
074 Calc sortedListCalc =
075 new SortCalc(call, listCalc, sortCalc);
076 final ExpCacheDescriptor cacheDescriptor =
077 new ExpCacheDescriptor(
078 call, sortedListCalc, compiler.getEvaluator());
079 return new Rank3MemberCalc(call, memberCalc, sortCalc, cacheDescriptor);
080 }
081 }
082
083 public Calc compileCall2(ResolvedFunCall call, ExpCompiler compiler) {
084 final boolean tuple = call.getArg(0).getType() instanceof TupleType;
085 final Exp listExp = call.getArg(1);
086 ListCalc listCalc0 = compiler.compileList(listExp);
087 Calc listCalc1 = new RankedListCalc(listCalc0, tuple);
088 final Calc listCalc;
089 if (MondrianProperties.instance().EnableExpCache.get()) {
090 final ExpCacheDescriptor key = new ExpCacheDescriptor(
091 listExp, listCalc1, compiler.getEvaluator());
092 listCalc = new CacheCalc(listExp, key);
093 } else {
094 listCalc = listCalc1;
095 }
096 if (tuple) {
097 final TupleCalc tupleCalc =
098 compiler.compileTuple(call.getArg(0));
099 return new Rank2TupleCalc(call, tupleCalc, listCalc);
100 } else {
101 final MemberCalc memberCalc =
102 compiler.compileMember(call.getArg(0));
103 return new Rank2MemberCalc(call, memberCalc, listCalc);
104 }
105 }
106
107 private static class Rank2TupleCalc extends AbstractIntegerCalc {
108 private final TupleCalc tupleCalc;
109 private final Calc listCalc;
110
111 public Rank2TupleCalc(ResolvedFunCall call, TupleCalc tupleCalc, Calc listCalc) {
112 super(call, new Calc[] {tupleCalc, listCalc});
113 this.tupleCalc = tupleCalc;
114 this.listCalc = listCalc;
115 }
116
117 public int evaluateInteger(Evaluator evaluator) {
118 // Get member or tuple.
119 // If the member is null (or the tuple contains a null member)
120 // the result is null (even if the list is null).
121 final Member[] members = tupleCalc.evaluateTuple(evaluator);
122 if (members == null) {
123 return IntegerNull;
124 }
125 assert !tupleContainsNullMember(members);
126
127 // Get the set of members/tuples.
128 // If the list is empty, MSAS cannot figure out the type of the
129 // list, so returns an error "Formula error - dimension count is
130 // not valid - in the Rank function". We will naturally return 0,
131 // which I think is better.
132 RankedTupleList rankedList = (RankedTupleList) listCalc.evaluate(evaluator);
133 if (rankedList == null) {
134 return 0;
135 }
136
137 // Find position of member in list. -1 signifies not found.
138 final int i = rankedList.indexOf(members);
139 // Return 1-based rank. 0 signifies not found.
140 return i + 1;
141 }
142 }
143
144 private static class Rank2MemberCalc extends AbstractIntegerCalc {
145 private final MemberCalc memberCalc;
146 private final Calc listCalc;
147
148 public Rank2MemberCalc(
149 ResolvedFunCall call, MemberCalc memberCalc, Calc listCalc)
150 {
151 super(call, new Calc[] {memberCalc, listCalc});
152 this.memberCalc = memberCalc;
153 this.listCalc = listCalc;
154 }
155
156 public int evaluateInteger(Evaluator evaluator) {
157 // Get member or tuple.
158 // If the member is null (or the tuple contains a null member)
159 // the result is null (even if the list is null).
160 final Member member = memberCalc.evaluateMember(evaluator);
161 if (member == null ||
162 member.isNull())
163 {
164 return IntegerNull;
165 }
166 // Get the set of members/tuples.
167 // If the list is empty, MSAS cannot figure out the type of the
168 // list, so returns an error "Formula error - dimension count is
169 // not valid - in the Rank function". We will naturally return 0,
170 // which I think is better.
171 RankedMemberList rankedList = (RankedMemberList) listCalc.evaluate(evaluator);
172 if (rankedList == null) {
173 return 0;
174 }
175
176 // Find position of member in list. -1 signifies not found.
177 final int i = rankedList.indexOf(member);
178 // Return 1-based rank. 0 signifies not found.
179 return i + 1;
180 }
181 }
182
183 private static class Rank3TupleCalc extends AbstractIntegerCalc {
184 private final TupleCalc tupleCalc;
185 private final Calc sortCalc;
186 private final ExpCacheDescriptor cacheDescriptor;
187
188 public Rank3TupleCalc(
189 ResolvedFunCall call,
190 TupleCalc tupleCalc,
191 Calc sortCalc,
192 ExpCacheDescriptor cacheDescriptor)
193 {
194 super(call, new Calc[] {tupleCalc, sortCalc});
195 this.tupleCalc = tupleCalc;
196 this.sortCalc = sortCalc;
197 this.cacheDescriptor = cacheDescriptor;
198 }
199
200 public int evaluateInteger(Evaluator evaluator) {
201 Member[] members = tupleCalc.evaluateTuple(evaluator);
202 if (members == null) {
203 return IntegerNull;
204 }
205 assert !tupleContainsNullMember(members);
206
207 // Compute the value of the tuple.
208 final Evaluator evaluator2 = evaluator.push(members);
209 Object value = sortCalc.evaluate(evaluator2);
210 if (value instanceof RuntimeException) {
211 // The value wasn't ready, so quit now... we'll be back.
212 return 0;
213 }
214
215 // Evaluate the list (or retrieve from cache).
216 // If there was an exception while calculating the
217 // list, propagate it up.
218 final SortResult sortResult = (SortResult)
219 evaluator.getCachedResult(cacheDescriptor);
220 if (debug) {
221 sortResult.print(new PrintWriter(System.out));
222 }
223 if (sortResult.empty) {
224 // If list is empty, the rank is null.
225 return IntegerNull;
226 }
227
228 // If value is null, it won't be in the values array.
229 if (value == Util.nullValue) {
230 return sortResult.values.length + 1;
231 }
232 // Look for the ranked value in the array.
233 int j = FunUtil.searchValuesDesc(sortResult.values, value);
234 if (j < 0) {
235 // Value not found. Flip the result to find the
236 // insertion point.
237 j = -(j + 1);
238 return j + 1; // 1-based
239 }
240 if (j <= sortResult.values.length) {
241 // If the values preceding are equal, increase the rank.
242 while (j > 0 && sortResult.values[j - 1].equals(value)) {
243 --j;
244 }
245 }
246 return j + 1; // 1-based
247 }
248 }
249
250 private static class Rank3MemberCalc extends AbstractDoubleCalc {
251 private final MemberCalc memberCalc;
252 private final Calc sortCalc;
253 private final ExpCacheDescriptor cacheDescriptor;
254
255 public Rank3MemberCalc(
256 ResolvedFunCall call,
257 MemberCalc memberCalc,
258 Calc sortCalc,
259 ExpCacheDescriptor cacheDescriptor) {
260 super(call, new Calc[] {memberCalc, sortCalc});
261 this.memberCalc = memberCalc;
262 this.sortCalc = sortCalc;
263 this.cacheDescriptor = cacheDescriptor;
264 }
265
266 public double evaluateDouble(Evaluator evaluator) {
267 Member member = memberCalc.evaluateMember(evaluator);
268 if (member == null || member.isNull()) {
269 return DoubleNull;
270 }
271 // Compute the value of the tuple.
272 final Evaluator evaluator2 = evaluator.push(member);
273 Object value = sortCalc.evaluate(evaluator2);
274 if (value == RolapUtil.valueNotReadyException) {
275 // The value wasn't ready, so quit now... we'll be back.
276 return 0;
277 }
278
279 // Evaluate the list (or retrieve from cache).
280 // If there was an exception while calculating the
281 // list, propagate it up.
282 final SortResult sortResult = (SortResult)
283 evaluator.getCachedResult(cacheDescriptor);
284 if (debug) {
285 sortResult.print(new PrintWriter(System.out));
286 }
287 if (sortResult.empty) {
288 // If list is empty, the rank is null.
289 return DoubleNull;
290 }
291
292 // If value is null, it won't be in the values array.
293 if (value == Util.nullValue) {
294 return sortResult.values.length + 1;
295 }
296 // Look for the ranked value in the array.
297 int j = FunUtil.searchValuesDesc(sortResult.values, value);
298 if (j < 0) {
299 // Value not found. Flip the result to find the
300 // insertion point.
301 j = -(j + 1);
302 return j + 1; // 1-based
303 }
304 if (j <= sortResult.values.length) {
305 // If the values preceding are equal, increase the rank.
306 while (j > 0 && sortResult.values[j - 1].equals(value)) {
307 --j;
308 }
309 }
310 return j + 1; // 1-based
311 }
312 }
313
314 /**
315 * Expression which evaluates an expression to form a list of tuples,
316 * evaluates a scalar expression at each tuple, then sorts the list of
317 * values. The result is a value of type {@link SortResult}, and can be
318 * used to implement the <code>Rank</code> function efficiently.
319 */
320 private static class SortCalc extends AbstractCalc {
321 private final ListCalc listCalc;
322 private final Calc sortCalc;
323
324 public SortCalc(Exp exp, ListCalc listExp, Calc sortExp) {
325 super(exp);
326 this.listCalc = listExp;
327 this.sortCalc = sortExp;
328 }
329
330 public Calc[] getCalcs() {
331 return new Calc[] {listCalc, sortCalc};
332 }
333
334 public boolean dependsOn(Dimension dimension) {
335 return anyDependsButFirst(getCalcs(), dimension);
336 }
337
338 public Object evaluate(Evaluator evaluator) {
339 // Create a new evaluator so we don't corrupt the given one.
340 final Evaluator evaluator2 = evaluator.push();
341 // Construct an array containing the value of the expression
342 // for each member.
343 List members = (List) listCalc.evaluate(evaluator2);
344 assert members != null;
345 if (members.isEmpty()) {
346 return new SortResult(true, new Object[0]);
347 }
348 RuntimeException exception = null;
349 Object[] values = new Object[members.size()];
350 int j = 0;
351 for (Object o : members) {
352 if (o instanceof Member) {
353 Member member = (Member) o;
354 evaluator2.setContext(member);
355 } else {
356 evaluator2.setContext((Member[]) o);
357 }
358 final Object value = sortCalc.evaluate(evaluator2);
359 if (value instanceof RuntimeException) {
360 if (exception == null) {
361 exception = (RuntimeException) value;
362 }
363 } else if (Util.isNull(value)) {
364 // nothing to do
365 } else {
366 values[j++] = value;
367 }
368 }
369 // If there were exceptions, quit now... we'll be back.
370 if (exception != null) {
371 return exception;
372 }
373 // If the array is shorter than we expected (because of null
374 // values) truncate it.
375 if (j < members.size()) {
376 final Object[] oldValues = values;
377 values = new Object[j];
378 System.arraycopy(oldValues, 0, values, 0, j);
379 }
380 // Sort the array.
381 FunUtil.sortValuesDesc(values);
382 return new SortResult(false, values);
383 }
384 }
385
386 /**
387 * Holder for the result of sorting a set of values.
388 *
389 * <p>todo: More optimal representation if a lot of the values are the
390 * same.
391 */
392 private static class SortResult {
393 /**
394 * Whether the list of tuples was empty.
395 * If this is the case, the rank will always be null.
396 *
397 * <p>It's possible for there to be a positive number of tuples, all
398 * of whose values are null, in which case, empty will be false but
399 * values will be empty.
400 */
401 final boolean empty;
402 /**
403 * Values in sorted order. Null values are not present: they would
404 * be at the end, anyway.
405 */
406 final Object[] values;
407
408 public SortResult(boolean empty, Object[] values) {
409 this.empty = empty;
410 this.values = values;
411 assert values != null;
412 assert !empty || values.length == 0;
413 }
414
415 public void print(PrintWriter pw) {
416 if (empty) {
417 pw.println("SortResult: empty");
418 } else {
419 pw.println("SortResult {");
420 for (int i = 0; i < values.length; i++) {
421 if (i > 0) {
422 pw.println(",");
423 }
424 Object value = values[i];
425 pw.print(value);
426 }
427 pw.println("}");
428 }
429 pw.flush();
430 }
431 }
432
433 /**
434 * Expression which evaluates an expression to form a list of tuples.
435 * The result is a value of type
436 * {@link mondrian.olap.fun.RankFunDef.RankedMemberList} or
437 * {@link mondrian.olap.fun.RankFunDef.RankedTupleList}, or
438 * null if the list is empty.
439 */
440 private static class RankedListCalc extends AbstractCalc {
441 private final ListCalc listCalc;
442 private final boolean tuple;
443
444 public RankedListCalc(ListCalc listCalc, boolean tuple) {
445 super(new DummyExp(listCalc.getType()));
446 this.listCalc = listCalc;
447 this.tuple = tuple;
448 }
449
450 public Calc[] getCalcs() {
451 return new Calc[] {listCalc};
452 }
453
454 public Object evaluate(Evaluator evaluator) {
455 // Construct an array containing the value of the expression
456 // for each member.
457 if (tuple) {
458 List<Member[]> tupleList =
459 ((TupleListCalc) listCalc).evaluateTupleList(evaluator);
460 assert tupleList != null;
461 return new RankedTupleList(tupleList);
462 } else {
463 List<Member> memberList =
464 ((MemberListCalc) listCalc).evaluateMemberList(evaluator);
465 assert memberList != null;
466 return new RankedMemberList(memberList);
467 }
468 }
469 }
470
471 /**
472 * Data structure which contains a list and can return the position of an
473 * element in the list in O(log N).
474 */
475 static class RankedMemberList {
476 Map<Member, Integer> map = new HashMap<Member, Integer>();
477
478 RankedMemberList(List<Member> members) {
479 int i = -1;
480 for (final Member member : members) {
481 ++i;
482 final Integer value = map.put(member, i);
483 if (value != null) {
484 // The list already contained a value for this key -- put
485 // it back.
486 map.put(member, value);
487 }
488 }
489 }
490
491 int indexOf(Member m) {
492 Integer integer = map.get(m);
493 if (integer == null) {
494 return -1;
495 } else {
496 return integer;
497 }
498 }
499 }
500 /**
501 * Data structure which contains a list and can return the position of an
502 * element in the list in O(log N).
503 */
504 static class RankedTupleList {
505 final Map<List<Member>, Integer> map =
506 new HashMap<List<Member>, Integer>();
507
508 RankedTupleList(List<Member[]> tupleList) {
509 int i = -1;
510 for (final Member[] tupleMembers : tupleList) {
511 ++i;
512 final List<Member> key = Arrays.asList(tupleMembers);
513 final Integer value = map.put(key, i);
514 if (value != null) {
515 // The list already contained a value for this key -- put
516 // it back.
517 map.put(key, value);
518 }
519 }
520 }
521
522 int indexOf(Member[] tupleMembers) {
523 final List<Member> key = Arrays.asList(tupleMembers);
524 Integer integer = map.get(key);
525 if (integer == null) {
526 return -1;
527 } else {
528 return integer;
529 }
530 }
531 }
532 }
533
534 // End RankFunDef.java