RankFunDef


1   /*
2   // $Id: //open/mondrian/src/main/mondrian/olap/fun/RankFunDef.java#14 $
3   // This software is subject to the terms of the Common Public License
4   // Agreement, available at the following URL:
5   // http://www.opensource.org/licenses/cpl.html.
6   // Copyright (C) 2005-2006 Julian Hyde
7   // All Rights Reserved.
8   // You must accept the terms of that agreement to use this software.
9   */
10  
11  package mondrian.olap.fun;
12  
13  import mondrian.olap.*;
14  import mondrian.olap.type.*;
15  import mondrian.calc.*;
16  import mondrian.calc.impl.*;
17  import mondrian.rolap.RolapUtil;
18  import mondrian.mdx.ResolvedFunCall;
19  
20  import java.util.*;
21  import java.io.PrintWriter  ;
22  
23  /**
24   * Definition of the <code>RANK</code> MDX function.
25   *
26   * @author Richard Emberson
27   * @since 17 January, 2005
28   * @version $Id: //open/mondrian/src/main/mondrian/olap/fun/RankFunDef.java#14 $
29   */
30  public class RankFunDef extends FunDefBase {
31      static final boolean debug = false;
32      static final ReflectiveMultiResolver Resolver = new ReflectiveMultiResolver(
33              "Rank",
34              "Rank(<Tuple>, <Set> [, <Calc Expression>])",
35              "Returns the one-based rank of a tuple in a set.",
36              new String  []{"fitx", "fitxn", "fimx", "fimxn"},
37              RankFunDef.class);
38  
39      public RankFunDef(FunDef dummyFunDef) {
40          super(dummyFunDef);
41      }
42  
43      public Calc compileCall(ResolvedFunCall call, ExpCompiler compiler) {
44          switch (call.getArgCount()) {
45          case 2:
46              return compileCall2(call, compiler);
47          case 3:
48              return compileCall3(call, compiler);
49          default:
50              throw Util.newInternal("invalid arg count " + call.getArgCount());
51          }
52      }
53  
54      public Calc compileCall3(ResolvedFunCall call, ExpCompiler compiler) {
55          final Type type0 = call.getArg(0).getType();
56          if (type0 instanceof TupleType) {
57              final TupleCalc tupleCalc =
58                      compiler.compileTuple(call.getArg(0));
59              final ListCalc listCalc =
60                      compiler.compileList(call.getArg(1));
61              final Calc sortCalc =
62                      compiler.compileScalar(call.getArg(2), true);
63              Calc sortedListCalc =
64                      new SortCalc(call, listCalc, sortCalc);
65              final ExpCacheDescriptor cacheDescriptor =
66                      new ExpCacheDescriptor(
67                              call, sortedListCalc, compiler.getEvaluator());
68              return new Rank3TupleCalc(call, tupleCalc, sortCalc, cacheDescriptor);
69          } else {
70              final MemberCalc memberCalc =
71                      compiler.compileMember(call.getArg(0));
72              final ListCalc listCalc = compiler.compileList(call.getArg(1));
73              final Calc sortCalc = compiler.compileScalar(call.getArg(2), true);
74              Calc sortedListCalc =
75                      new SortCalc(call, listCalc, sortCalc);
76              final ExpCacheDescriptor cacheDescriptor =
77                      new ExpCacheDescriptor(
78                              call, sortedListCalc, compiler.getEvaluator());
79              return new Rank3MemberCalc(call, memberCalc, sortCalc, cacheDescriptor);
80          }
81      }
82  
83      public Calc compileCall2(ResolvedFunCall call, ExpCompiler compiler) {
84          final Exp listExp = call.getArg(1);
85          ListCalc listCalc0 = compiler.compileList(listExp);
86          Calc listCalc1 = new RankedListCalc(listCalc0);
87          final Calc listCalc;
88          if (MondrianProperties.instance().EnableExpCache.get()) {
89              final ExpCacheDescriptor key = new ExpCacheDescriptor(
90                      listExp, listCalc1, compiler.getEvaluator());
91              listCalc = new CacheCalc(listExp, key);
92          } else {
93              listCalc = listCalc1;
94          }
95          if (call.getArg(0).getType() instanceof TupleType) {
96              final TupleCalc tupleCalc =
97                      compiler.compileTuple(call.getArg(0));
98              return new Rank2TupleCalc(call, tupleCalc, listCalc);
99          } else {
100             final MemberCalc memberCalc =
101                     compiler.compileMember(call.getArg(0));
102             return new Rank2MemberCalc(call, memberCalc, listCalc);
103         }
104     }
105 
106     private static class Rank2TupleCalc extends AbstractDoubleCalc {
107         private final TupleCalc tupleCalc;
108         private final Calc listCalc;
109 
110         public Rank2TupleCalc(ResolvedFunCall call, TupleCalc tupleCalc, Calc listCalc) {
111             super(call, new Calc[] {tupleCalc, listCalc});
112             this.tupleCalc = tupleCalc;
113             this.listCalc = listCalc;
114         }
115 
116         public double evaluateDouble(Evaluator evaluator) {
117             // Get member or tuple.
118             // If the member is null (or the tuple contains a null member)
119             // the result is null (even if the list is null).
120             final Member[] members = tupleCalc.evaluateTuple(evaluator);
121             if (members == null) {
122                 return DoubleNull;
123             }
124             assert !tupleContainsNullMember(members);
125 
126             // Get the set of members/tuples.
127             // If the list is empty, MSAS cannot figure out the type of the
128             // list, so returns an error "Formula error - dimension count is
129             // not valid - in the Rank function". We will naturally return 0,
130             // which I think is better.
131             RankedList rankedList = (RankedList) listCalc.evaluate(evaluator);
132             if (rankedList == null) {
133                 return 0;
134             }
135 
136             // Find position of member in list. -1 signifies not found.
137             final int i = rankedList.indexOf(members);
138             // Return 1-based rank. 0 signifies not found.
139             return i + 1;
140         }
141     }
142 
143     private static class Rank2MemberCalc extends AbstractDoubleCalc {
144         private final MemberCalc memberCalc;
145         private final Calc listCalc;
146 
147         public Rank2MemberCalc(ResolvedFunCall call, MemberCalc memberCalc, Calc listCalc) {
148             super(call, new Calc[] {memberCalc, listCalc});
149             this.memberCalc = memberCalc;
150             this.listCalc = listCalc;
151         }
152 
153         public double evaluateDouble(Evaluator evaluator) {
154             // Get member or tuple.
155             // If the member is null (or the tuple contains a null member)
156             // the result is null (even if the list is null).
157             final Member member = memberCalc.evaluateMember(evaluator);
158             if (member == null ||
159                     member.isNull()) {
160                 return DoubleNull;
161             }
162             // Get the set of members/tuples.
163             // If the list is empty, MSAS cannot figure out the type of the
164             // list, so returns an error "Formula error - dimension count is
165             // not valid - in the Rank function". We will naturally return 0,
166             // which I think is better.
167             RankedList rankedList = (RankedList) listCalc.evaluate(evaluator);
168             if (rankedList == null) {
169                 return 0;
170             }
171 
172             // Find position of member in list. -1 signifies not found.
173             final int i = rankedList.indexOf(member);
174             // Return 1-based rank. 0 signifies not found.
175             return i + 1;
176         }
177     }
178 
179     private static class Rank3TupleCalc extends AbstractDoubleCalc {
180         private final TupleCalc tupleCalc;
181         private final Calc sortCalc;
182         private final ExpCacheDescriptor cacheDescriptor;
183 
184         public Rank3TupleCalc(
185                 ResolvedFunCall call,
186                 TupleCalc tupleCalc,
187                 Calc sortCalc,
188                 ExpCacheDescriptor cacheDescriptor) {
189             super(call, new Calc[] {tupleCalc, sortCalc});
190             this.tupleCalc = tupleCalc;
191             this.sortCalc = sortCalc;
192             this.cacheDescriptor = cacheDescriptor;
193         }
194 
195         public double evaluateDouble(Evaluator evaluator) {
196             Member[] members = tupleCalc.evaluateTuple(evaluator);
197             if (members == null) {
198                 return DoubleNull;
199             }
200             assert !tupleContainsNullMember(members);
201 
202             // Compute the value of the tuple.
203             final Evaluator evaluator2 = evaluator.push(members);
204             Object   value = sortCalc.evaluate(evaluator2);
205             if (value instanceof RuntimeException  ) {
206                 // The value wasn't ready, so quit now... we'll be back.
207                 return 0;
208             }
209 
210             // Evaluate the list (or retrieve from cache).
211             // If there was an exception while calculating the
212             // list, propagate it up.
213             final SortResult sortResult = (SortResult)
214                     evaluator.getCachedResult(cacheDescriptor);
215             if (debug) {
216                 sortResult.print(new PrintWriter  (System.out));
217             }
218             if (sortResult.empty) {
219                 // If list is empty, the rank is null.
220                 return DoubleNull;
221             }
222 
223             // If value is null, it won't be in the values array.
224             if (value == Util.nullValue) {
225                 return sortResult.values.length + 1;
226             }
227             // Look for the ranked value in the array.
228             int j = FunUtil.searchValuesDesc(sortResult.values, value);
229             if (j < 0) {
230                 // Value not found. Flip the result to find the
231                 // insertion point.
232                 j = -(j + 1);
233                 return j + 1; // 1-based
234             }
235             if (j <= sortResult.values.length) {
236                 // If the values preceding are equal, increase the rank.
237                 while (j > 0 && sortResult.values[j - 1].equals(value)) {
238                     --j;
239                 }
240             }
241             return j + 1; // 1-based
242         }
243     }
244 
245     private static class Rank3MemberCalc extends AbstractDoubleCalc {
246         private final MemberCalc memberCalc;
247         private final Calc sortCalc;
248         private final ExpCacheDescriptor cacheDescriptor;
249 
250         public Rank3MemberCalc(
251                 ResolvedFunCall call,
252                 MemberCalc memberCalc,
253                 Calc sortCalc,
254                 ExpCacheDescriptor cacheDescriptor) {
255             super(call, new Calc[] {memberCalc, sortCalc});
256             this.memberCalc = memberCalc;
257             this.sortCalc = sortCalc;
258             this.cacheDescriptor = cacheDescriptor;
259         }
260 
261         public double evaluateDouble(Evaluator evaluator) {
262             Member member = memberCalc.evaluateMember(evaluator);
263             if (member == null || member.isNull()) {
264                 return DoubleNull;
265             }
266             // Compute the value of the tuple.
267             final Evaluator evaluator2 = evaluator.push(member);
268             Object   value = sortCalc.evaluate(evaluator2);
269             if (value == RolapUtil.valueNotReadyException) {
270                 // The value wasn't ready, so quit now... we'll be back.
271                 return 0;
272             }
273 
274             // Evaluate the list (or retrieve from cache).
275             // If there was an exception while calculating the
276             // list, propagate it up.
277             final SortResult sortResult = (SortResult)
278                     evaluator.getCachedResult(cacheDescriptor);
279             if (debug) {
280                 sortResult.print(new PrintWriter  (System.out));
281             }
282             if (sortResult.empty) {
283                 // If list is empty, the rank is null.
284                 return DoubleNull;
285             }
286 
287             // If value is null, it won't be in the values array.
288             if (value == Util.nullValue) {
289                 return sortResult.values.length + 1;
290             }
291             // Look for the ranked value in the array.
292             int j = FunUtil.searchValuesDesc(sortResult.values, value);
293             if (j < 0) {
294                 // Value not found. Flip the result to find the
295                 // insertion point.
296                 j = -(j + 1);
297                 return j + 1; // 1-based
298             }
299             if (j <= sortResult.values.length) {
300                 // If the values preceding are equal, increase the rank.
301                 while (j > 0 && sortResult.values[j - 1].equals(value)) {
302                     --j;
303                 }
304             }
305             return j + 1; // 1-based
306         }
307     }
308 
309     /**
310      * Expression which evaluates an expression to form a list of tuples,
311      * evaluates a scalar expression at each tuple, then sorts the list of
312      * values. The result is a value of type {@link SortResult}, and can be
313      * used to implement the <code>Rank</code> function efficiently.
314      */
315     private static class SortCalc extends AbstractCalc {
316         private final ListCalc listCalc;
317         private final Calc sortCalc;
318 
319         public SortCalc(Exp exp, ListCalc listExp, Calc sortExp) {
320             super(exp);
321             this.listCalc = listExp;
322             this.sortCalc = sortExp;
323         }
324 
325         public Calc[] getCalcs() {
326             return new Calc[] {listCalc, sortCalc};
327         }
328 
329         public boolean dependsOn(Dimension dimension) {
330             return anyDependsButFirst(getCalcs(), dimension);
331         }
332 
333         public Object   evaluate(Evaluator evaluator) {
334             // Create a new evaluator so we don't corrupt the given one.
335             final Evaluator evaluator2 = evaluator.push();
336             // Construct an array containing the value of the expression
337             // for each member.
338             List members = (List) listCalc.evaluate(evaluator2);
339             assert members != null;
340             if (members.isEmpty()) {
341                 return new SortResult(true, new Object  [0]);
342             }
343             RuntimeException   exception = null;
344             Object  [] values = new Object  [members.size()];
345             int j = 0;
346             for (Object   member1 : members) {
347                 final Object   o = member1;
348                 if (o instanceof Member) {
349                     Member member = (Member) o;
350                     evaluator2.setContext(member);
351                 } else {
352                     evaluator2.setContext((Member[]) o);
353                 }
354                 final Object   value = sortCalc.evaluate(evaluator2);
355                 if (value instanceof RuntimeException  ) {
356                     if (exception == null) {
357                         exception = (RuntimeException  ) value;
358                     }
359                 } else if (Util.isNull(value)) {
360                     ;
361                 } else {
362                     values[j++] = value;
363                 }
364             }
365             // If there were exceptions, quit now... we'll be back.
366             if (exception != null) {
367                 return exception;
368             }
369             // If the array is shorter than we expected (because of null
370             // values) truncate it.
371             if (j < members.size()) {
372                 final Object  [] oldValues = values;
373                 values = new Object  [j];
374                 System.arraycopy(oldValues, 0, values, 0, j);
375             }
376             // Sort the array.
377             FunUtil.sortValuesDesc(values);
378             return new SortResult(false, values);
379         }
380     }
381 
382     /**
383      * Holder for the result of sorting a set of values.
384      *
385      * <p>todo: More optimal representation if a lot of the values are the
386      * same.
387      */
388     private static class SortResult {
389         /**
390          * Whether the list of tuples was empty.
391          * If this is the case, the rank will always be null.
392          *
393          * <p>It's possible for there to be a positive number of tuples, all
394          * of whose values are null, in which case, empty will be false but
395          * values will be empty.
396          */
397         final boolean empty;
398         /**
399          * Values in sorted order. Null values are not present: they would
400          * be at the end, anyway.
401          */
402         final Object  [] values;
403 
404         public SortResult(boolean empty, Object  [] values) {
405             this.empty = empty;
406             this.values = values;
407             assert values != null;
408             assert !empty || values.length == 0;
409         }
410 
411         public void print(PrintWriter   pw) {
412             if (empty) {
413                 pw.println("SortResult: empty");
414             } else {
415                 pw.println("SortResult {");
416                 for (int i = 0; i < values.length; i++) {
417                     if (i > 0) {
418                         pw.println(",");
419                     }
420                     Object   value = values[i];
421                     pw.print(value);
422                 }
423                 pw.println("}");
424             }
425             pw.flush();
426         }
427     }
428 
429     /**
430      * Expression which evaluates an expression to form a list of tuples.
431      * The result is a value of type {@link RankedList}, or null if the list
432      * is empty.
433      */
434     private static class RankedListCalc extends AbstractCalc {
435         private final ListCalc listCalc;
436 
437         public RankedListCalc(ListCalc listCalc) {
438             super(new DummyExp(listCalc.getType()));
439             this.listCalc = listCalc;
440         }
441 
442         public Calc[] getCalcs() {
443             return new Calc[] {listCalc};
444         }
445 
446         public Object   evaluate(Evaluator evaluator) {
447             // Construct an array containing the value of the expression
448             // for each member.
449             List members = listCalc.evaluateList(evaluator);
450             if (members == null) {
451                 return null;
452             }
453             return new RankedList(members);
454         }
455     }
456 
457     /**
458      * Data structure which contains a list and can return the position of an
459      * element in the list in O(log N).
460      */
461     static class RankedList {
462         Map<Object  , Integer  > map = new HashMap<Object  , Integer  >();
463 
464         RankedList(List members) {
465             for (int i = 0; i < members.size(); i++) {
466                 Object   o = members.get(i);
467                 final Object   key;
468                 if (o instanceof Member) {
469                     key = o;
470                 } else if (o instanceof Member[]) {
471                     key = Arrays.asList((Member []) o);
472                 } else {
473                     throw Util.newInternal("bad member/tuple " + o);
474                 }
475                 final Integer   value = map.put(key, i);
476                 if (value != null) {
477                     // The list already contained a value for this key -- put
478                     // it back.
479                     map.put(key, value);
480                 }
481             }
482         }
483 
484         int indexOf(Member m) {
485             return indexOf((Object  ) m);
486         }
487 
488         int indexOf(Member[] tuple) {
489             return indexOf(Arrays.asList(tuple));
490         }
491 
492         private int indexOf(Object   o) {
493             Integer   integer = map.get(o);
494             if (integer == null) {
495                 return -1;
496             } else {
497                 return integer;
498             }
499         }
500     }
501 }
502 
503 // End RankFunDef.java
504
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags