001 /*
002 // $Id: //open/mondrian/src/main/mondrian/olap/fun/DescendantsFunDef.java#20 $
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) 2004-2002 Kana Software, Inc.
007 // Copyright (C) 2004-2008 Julian Hyde and others
008 // All Rights Reserved.
009 // You must accept the terms of that agreement to use this software.
010 */
011 package mondrian.olap.fun;
012
013 import java.util.*;
014
015 import mondrian.olap.*;
016 import mondrian.olap.type.NumericType;
017 import mondrian.olap.type.NullType;
018 import mondrian.calc.*;
019 import mondrian.calc.impl.AbstractListCalc;
020 import mondrian.mdx.ResolvedFunCall;
021
022 /**
023 * Definition of the <code>Descendants</code> MDX function.
024 *
025 * @author jhyde
026 * @version $Id: //open/mondrian/src/main/mondrian/olap/fun/DescendantsFunDef.java#20 $
027 * @since Mar 23, 2006
028 */
029 class DescendantsFunDef extends FunDefBase {
030
031 static final ReflectiveMultiResolver Resolver = new ReflectiveMultiResolver(
032 "Descendants",
033 "Descendants(<Member>[, <Level>[, <Desc_flag>]])",
034 "Returns the set of descendants of a member at a specified level, optionally including or excluding descendants in other levels.",
035 new String[]{"fxm", "fxml", "fxmly", "fxmn", "fxmny", "fxmey"},
036 DescendantsFunDef.class,
037 Flag.getNames());
038
039 public DescendantsFunDef(FunDef dummyFunDef) {
040 super(dummyFunDef);
041
042 }
043
044 public Calc compileCall(ResolvedFunCall call, ExpCompiler compiler) {
045 final MemberCalc memberCalc = compiler.compileMember(call.getArg(0));
046 Flag flag = Flag.SELF;
047 if (call.getArgCount() == 1) {
048 flag = Flag.SELF_BEFORE_AFTER;
049 }
050 final boolean depthSpecified = call.getArgCount() >= 2 &&
051 call.getArg(1).getType() instanceof NumericType;
052 final boolean depthEmpty = call.getArgCount() >= 2 &&
053 call.getArg(1).getType() instanceof NullType;
054 if (call.getArgCount() >= 3) {
055 flag = FunUtil.getLiteralArg(call, 2, Flag.SELF, Flag.class);
056 }
057
058 if (call.getArgCount() >= 2 && depthEmpty) {
059 if (flag != Flag.LEAVES) {
060 throw Util.newError(
061 "depth must be specified unless DESC_FLAG is LEAVES");
062 }
063 }
064 if ((depthSpecified || depthEmpty) && flag.leaves) {
065 final IntegerCalc depthCalc = depthSpecified ?
066 compiler.compileInteger(call.getArg(1)) :
067 null;
068 return new AbstractListCalc(call, new Calc[] {memberCalc, depthCalc}) {
069 public List evaluateList(Evaluator evaluator) {
070 final Member member = memberCalc.evaluateMember(evaluator);
071 List<Member> result = new ArrayList<Member>();
072 int depth = -1;
073 if (depthCalc != null) {
074 depth = depthCalc.evaluateInteger(evaluator);
075 if (depth < 0) {
076 depth = -1; // no limit
077 }
078 }
079 final SchemaReader schemaReader =
080 evaluator.getSchemaReader();
081 descendantsLeavesByDepth(
082 member, result, schemaReader, depth);
083 hierarchize(result, false);
084 return result;
085 }
086 };
087 } else if (depthSpecified) {
088 final IntegerCalc depthCalc = call.getArgCount() > 1 ?
089 compiler.compileInteger(call.getArg(1)) :
090 null;
091 final Flag flag1 = flag;
092 return new AbstractListCalc(call, new Calc[] {memberCalc, depthCalc}) {
093 public List evaluateList(Evaluator evaluator) {
094 final Member member = memberCalc.evaluateMember(evaluator);
095 List<Member> result = new ArrayList<Member>();
096 final int depth = depthCalc.evaluateInteger(evaluator);
097 final SchemaReader schemaReader = evaluator.getSchemaReader();
098 descendantsByDepth(
099 member, result, schemaReader,
100 depth, flag1.before, flag1.self, flag1.after,
101 evaluator);
102 hierarchize(result, false);
103 return result;
104 }
105 };
106 } else {
107 final LevelCalc levelCalc = call.getArgCount() > 1 ?
108 compiler.compileLevel(call.getArg(1)) :
109 null;
110 final Flag flag2 = flag;
111 return new AbstractListCalc(call, new Calc[] {memberCalc, levelCalc}) {
112 public List evaluateList(Evaluator evaluator) {
113 final Evaluator context =
114 evaluator.isNonEmpty() ? evaluator : null;
115 final Member member = memberCalc.evaluateMember(evaluator);
116 List<Member> result = new ArrayList<Member>();
117 final SchemaReader schemaReader = evaluator.getSchemaReader();
118 final Level level = levelCalc != null ?
119 levelCalc.evaluateLevel(evaluator) :
120 member.getLevel();
121 descendantsByLevel(
122 schemaReader, member, level, result,
123 flag2.before, flag2.self,
124 flag2.after, flag2.leaves, context);
125 hierarchize(result, false);
126 return result;
127 }
128 };
129 }
130 }
131
132 private static void descendantsByDepth(
133 Member member,
134 List<Member> result,
135 final SchemaReader schemaReader,
136 final int depthLimitFinal,
137 final boolean before,
138 final boolean self,
139 final boolean after,
140 final Evaluator context)
141 {
142 List<Member> children = new ArrayList<Member>();
143 children.add(member);
144 for (int depth = 0;; ++depth) {
145 if (depth == depthLimitFinal) {
146 if (self) {
147 result.addAll(children);
148 }
149 if (!after) {
150 break; // no more results after this level
151 }
152 } else if (depth < depthLimitFinal) {
153 if (before) {
154 result.addAll(children);
155 }
156 } else {
157 if (after) {
158 result.addAll(children);
159 } else {
160 break; // no more results after this level
161 }
162 }
163
164 children = schemaReader.getMemberChildren(children, context);
165 if (children.size() == 0) {
166 break;
167 }
168 }
169 }
170
171 /**
172 * Populates 'result' with the descendants at the leaf level at depth
173 * 'depthLimit' or less. If 'depthLimit' is -1, does not apply a depth
174 * constraint.
175 */
176 private static void descendantsLeavesByDepth(
177 final Member member,
178 final List<Member> result,
179 final SchemaReader schemaReader,
180 final int depthLimit) {
181 if (!schemaReader.isDrillable(member)) {
182 if (depthLimit >= 0) {
183 result.add(member);
184 }
185 return;
186 }
187 List<Member> children = new ArrayList<Member>();
188 children.add(member);
189 for (int depth = 0; depthLimit == -1 || depth <= depthLimit; ++depth) {
190 children = schemaReader.getMemberChildren(children);
191 if (children.size() == 0) {
192 throw Util.newInternal("drillable member must have children");
193 }
194 List<Member> nextChildren = new ArrayList<Member>();
195 for (Member child : children) {
196 // TODO: Implement this more efficiently. The current
197 // implementation of isDrillable for a parent-child hierarchy
198 // simply retrieves the children sees whether there are any,
199 // so we end up fetching each member's children twice.
200 if (schemaReader.isDrillable(child)) {
201 nextChildren.add(child);
202 } else {
203 result.add(child);
204 }
205 }
206 if (nextChildren.isEmpty()) {
207 return;
208 }
209 children = nextChildren;
210 }
211 }
212
213 /**
214 * Finds all descendants of a member which are before/at/after a level,
215 * and/or are leaves (have no descendants) and adds them to a result list.
216 *
217 * @param schemaReader Member reader
218 * @param ancestor Member to find descendants of
219 * @param level Level relative to which to filter, must not be null
220 * @param result Result list
221 * @param before Whether to output members above <code>level</code>
222 * @param self Whether to output members at <code>level</code>
223 * @param after Whether to output members below <code>level</code>
224 * @param leaves Whether to output members which are leaves
225 * @param context Evaluation context; determines criteria by which the
226 * result set should be filtered
227 */
228 static void descendantsByLevel(
229 SchemaReader schemaReader,
230 Member ancestor,
231 Level level,
232 List<Member> result,
233 boolean before,
234 boolean self,
235 boolean after,
236 boolean leaves,
237 Evaluator context) {
238 // We find the descendants of a member by making breadth-first passes
239 // down the hierarchy. Initially the list just contains the ancestor.
240 // Then we find its children. We add those children to the result if
241 // they fulfill the before/self/after conditions relative to the level.
242 //
243 // We add a child to the "fertileMembers" list if some of its children
244 // might be in the result. Again, this depends upon the
245 // before/self/after conditions.
246 //
247 // Note that for some member readers -- notably the
248 // RestrictedMemberReader, when it is reading a ragged hierarchy -- the
249 // children of a member do not always belong to the same level. For
250 // example, the children of USA include WA (a state) and Washington
251 // (a city). This is why we repeat the before/self/after logic for
252 // each member.
253 final int levelDepth = level.getDepth();
254 List<Member> members = Collections.singletonList(ancestor);
255 // Each pass, "fertileMembers" has the same contents as "members",
256 // except that we omit members whose children we are not interested
257 // in. We allocate it once, and clear it each pass, to save a little
258 // memory allocation.
259 if (leaves) {
260 assert !before && !self && !after;
261 do {
262 List<Member> nextMembers = new ArrayList<Member>();
263 for (Member member : members) {
264 final int currentDepth = member.getLevel().getDepth();
265 List<Member> childMembers =
266 schemaReader.getMemberChildren(member, context);
267 if (childMembers.size() == 0) {
268 // this member is a leaf -- add it
269 if (currentDepth == levelDepth) {
270 result.add(member);
271 }
272 } else {
273 // this member is not a leaf -- add its children
274 // to the list to be considered next iteration
275 if (currentDepth <= levelDepth) {
276 nextMembers.addAll(childMembers);
277 }
278 }
279 }
280 members = nextMembers;
281 }
282 while (members.size() > 0);
283 } else {
284 List<Member> fertileMembers = new ArrayList<Member>();
285 do {
286 fertileMembers.clear();
287 for (Member member : members) {
288 final int currentDepth = member.getLevel().getDepth();
289 if (currentDepth == levelDepth) {
290 if (self) {
291 result.add(member);
292 }
293 if (after) {
294 // we are interested in member's children
295 fertileMembers.add(member);
296 }
297 } else if (currentDepth < levelDepth) {
298 if (before) {
299 result.add(member);
300 }
301 fertileMembers.add(member);
302 } else {
303 if (after) {
304 result.add(member);
305 fertileMembers.add(member);
306 }
307 }
308 }
309 members =
310 schemaReader.getMemberChildren(fertileMembers, context);
311 }
312 while (members.size() > 0);
313 }
314 }
315
316 /**
317 * Enumeration of the flags allowed to the <code>DESCENDANTS</code>
318 * function.
319 */
320 enum Flag {
321 SELF(true, false, false, false),
322 AFTER(false, true, false, false),
323 BEFORE(false, false, true, false),
324 BEFORE_AND_AFTER(false, true, true, false),
325 SELF_AND_AFTER(true, true, false, false),
326 SELF_AND_BEFORE(true, false, true, false),
327 SELF_BEFORE_AFTER(true, true, true, false),
328 LEAVES(false, false, false, true);
329
330 private final boolean self;
331 private final boolean after;
332 private final boolean before;
333 private final boolean leaves;
334
335 Flag(boolean self, boolean after, boolean before, boolean leaves) {
336 this.self = self;
337 this.after = after;
338 this.before = before;
339 this.leaves = leaves;
340 }
341
342 public static String[] getNames() {
343 List<String> names = new ArrayList<String>();
344 for (Flag flags : Flag.class.getEnumConstants()) {
345 names.add(flags.name());
346 }
347 return names.toArray(new String[names.size()]);
348 }
349 }
350 }
351
352 // End DescendantsFunDef.java