001: /*
002: * Copyright Aduna (http://www.aduna-software.com/) (c) 1997-2007.
003: *
004: * Licensed under the Aduna BSD-style license.
005: */
006: package org.openrdf.query.algebra.evaluation.iterator;
007:
008: import java.util.ArrayList;
009: import java.util.Collection;
010: import java.util.HashMap;
011: import java.util.HashSet;
012: import java.util.Iterator;
013: import java.util.List;
014: import java.util.Map;
015: import java.util.Set;
016:
017: import info.aduna.iteration.CloseableIteration;
018: import info.aduna.iteration.CloseableIteratorIteration;
019: import info.aduna.lang.ObjectUtil;
020:
021: import org.openrdf.model.Literal;
022: import org.openrdf.model.Value;
023: import org.openrdf.model.impl.LiteralImpl;
024: import org.openrdf.model.vocabulary.XMLSchema;
025: import org.openrdf.query.BindingSet;
026: import org.openrdf.query.QueryEvaluationException;
027: import org.openrdf.query.algebra.AggregateOperator;
028: import org.openrdf.query.algebra.Count;
029: import org.openrdf.query.algebra.Group;
030: import org.openrdf.query.algebra.GroupElem;
031: import org.openrdf.query.algebra.Max;
032: import org.openrdf.query.algebra.Min;
033: import org.openrdf.query.algebra.ValueExpr;
034: import org.openrdf.query.algebra.evaluation.EvaluationStrategy;
035: import org.openrdf.query.algebra.evaluation.QueryBindingSet;
036:
037: /**
038: * @author David Huynh
039: * @author Arjohn Kampman
040: */
041: public class GroupIterator
042: extends
043: CloseableIteratorIteration<BindingSet, QueryEvaluationException> {
044:
045: /*-----------*
046: * Constants *
047: *-----------*/
048:
049: private final EvaluationStrategy strategy;
050:
051: private final BindingSet parentBindings;
052:
053: private final Group group;
054:
055: /*-----------*
056: * Variables *
057: *-----------*/
058:
059: private boolean ordered = false;
060:
061: /*--------------*
062: * Constructors *
063: *--------------*/
064:
065: public GroupIterator(EvaluationStrategy strategy, Group group,
066: BindingSet parentBindings) throws QueryEvaluationException {
067: this .strategy = strategy;
068: this .group = group;
069: this .parentBindings = parentBindings;
070:
071: super .setIterator(createIterator());
072: }
073:
074: /*---------*
075: * Methods *
076: *---------*/
077:
078: private Iterator<BindingSet> createIterator()
079: throws QueryEvaluationException {
080: Collection<BindingSet> bindingSets;
081: Collection<Entry> entries;
082:
083: if (ordered) {
084: bindingSets = new ArrayList<BindingSet>();
085: entries = buildOrderedEntries();
086: } else {
087: bindingSets = new HashSet<BindingSet>();
088: entries = buildUnorderedEntries();
089: }
090:
091: for (Entry entry : entries) {
092: QueryBindingSet sol = new QueryBindingSet(parentBindings);
093:
094: for (String name : group.getGroupBindingNames()) {
095: Value value = entry.getPrototype().getValue(name);
096: if (value != null) {
097: // Potentially overwrites bindings from super
098: sol.setBinding(name, value);
099: }
100: }
101:
102: for (GroupElem ge : group.getGroupElements()) {
103: Value value = processAggregate(entry.getSolutions(), ge
104: .getOperator());
105: if (value != null) {
106: // Potentially overwrites bindings from super
107: sol.setBinding(ge.getName(), value);
108: }
109: }
110:
111: bindingSets.add(sol);
112: }
113:
114: return bindingSets.iterator();
115: }
116:
117: private Collection<Entry> buildOrderedEntries()
118: throws QueryEvaluationException {
119: CloseableIteration<BindingSet, QueryEvaluationException> iter = strategy
120: .evaluate(group.getArg(), parentBindings);
121:
122: try {
123: List<Entry> orderedEntries = new ArrayList<Entry>();
124: Map<Key, Entry> entries = new HashMap<Key, Entry>();
125:
126: while (iter.hasNext()) {
127: BindingSet bindingSet = iter.next();
128: Key key = new Key(bindingSet);
129: Entry entry = entries.get(key);
130:
131: if (entry == null) {
132: entry = new Entry(bindingSet);
133: entries.put(key, entry);
134: orderedEntries.add(entry);
135: }
136:
137: entry.addSolution(bindingSet);
138: }
139:
140: return orderedEntries;
141: } finally {
142: iter.close();
143: }
144: }
145:
146: private Collection<Entry> buildUnorderedEntries()
147: throws QueryEvaluationException {
148: CloseableIteration<BindingSet, QueryEvaluationException> iter = strategy
149: .evaluate(group.getArg(), parentBindings);
150:
151: try {
152: Map<Key, Entry> entries = new HashMap<Key, Entry>();
153:
154: while (iter.hasNext()) {
155: BindingSet sol = iter.next();
156: Key key = new Key(sol);
157: Entry entry = entries.get(key);
158:
159: if (entry == null) {
160: entry = new Entry(sol);
161: entries.put(key, entry);
162: }
163:
164: entry.addSolution(sol);
165: }
166:
167: return entries.values();
168: } finally {
169: iter.close();
170: }
171:
172: }
173:
174: private Value processAggregate(Set<BindingSet> bindingSets,
175: AggregateOperator operator) throws QueryEvaluationException {
176: if (operator instanceof Count) {
177: Count countOp = (Count) operator;
178:
179: ValueExpr arg = countOp.getArg();
180:
181: if (arg != null) {
182: Set<Value> values = makeValueSet(arg, bindingSets);
183: return new LiteralImpl(Integer.toString(values.size()),
184: XMLSchema.INTEGER);
185: } else {
186: return new LiteralImpl(Integer.toString(bindingSets
187: .size()), XMLSchema.INTEGER);
188: }
189: } else if (operator instanceof Min) {
190: Min minOp = (Min) operator;
191:
192: Set<Value> values = makeValueSet(minOp.getArg(),
193: bindingSets);
194:
195: // FIXME: handle case where 'values' is empty
196: double min = Double.POSITIVE_INFINITY;
197: for (Value v : values) {
198: if (v instanceof Literal) {
199: Literal l = (Literal) v;
200: try {
201: min = Math.min(min, Double.parseDouble(l
202: .getLabel()));
203: } catch (NumberFormatException e) {
204: // ignore
205: }
206: }
207: }
208:
209: return new LiteralImpl(Double.toString(min),
210: XMLSchema.DOUBLE);
211: } else if (operator instanceof Max) {
212: Max maxOp = (Max) operator;
213:
214: Set<Value> values = makeValueSet(maxOp.getArg(),
215: bindingSets);
216:
217: // FIXME: handle case where 'values' is empty
218: double max = Double.NEGATIVE_INFINITY;
219: for (Value v : values) {
220: if (v instanceof Literal) {
221: Literal l = (Literal) v;
222: try {
223: max = Math.max(max, Double.parseDouble(l
224: .getLabel()));
225: } catch (NumberFormatException e) {
226: // ignore
227: }
228: }
229: }
230:
231: return new LiteralImpl(Double.toString(max),
232: XMLSchema.DOUBLE);
233: }
234:
235: return null;
236: }
237:
238: private Set<Value> makeValueSet(ValueExpr arg,
239: Set<BindingSet> bindingSets)
240: throws QueryEvaluationException {
241: Set<Value> valueSet = new HashSet<Value>();
242:
243: for (BindingSet s : bindingSets) {
244: Value value = strategy.evaluate(arg, s);
245: if (value != null) {
246: valueSet.add(value);
247: }
248: }
249:
250: return valueSet;
251: }
252:
253: /**
254: * A unique key for a set of existing bindings.
255: *
256: * @author David Huynh
257: */
258: protected class Key {
259:
260: private BindingSet bindingSet;
261:
262: private int hash;
263:
264: public Key(BindingSet bindingSet) {
265: this .bindingSet = bindingSet;
266:
267: for (String name : group.getGroupBindingNames()) {
268: Value value = bindingSet.getValue(name);
269: if (value != null) {
270: this .hash ^= value.hashCode();
271: }
272: }
273: }
274:
275: @Override
276: public int hashCode() {
277: return hash;
278: }
279:
280: @Override
281: public boolean equals(Object other) {
282: if (other instanceof Key && other.hashCode() == hash) {
283: BindingSet otherSolution = ((Key) other).bindingSet;
284:
285: for (String name : group.getGroupBindingNames()) {
286: Value v1 = bindingSet.getValue(name);
287: Value v2 = otherSolution.getValue(name);
288:
289: if (!ObjectUtil.nullEquals(v1, v2)) {
290: return false;
291: }
292: }
293:
294: return true;
295: }
296:
297: return false;
298: }
299: }
300:
301: protected static class Entry {
302:
303: private BindingSet prototype;
304:
305: private Set<BindingSet> bindingSets;
306:
307: public Entry(BindingSet prototype) {
308: this .prototype = prototype;
309: this .bindingSets = new HashSet<BindingSet>();
310: }
311:
312: public BindingSet getPrototype() {
313: return prototype;
314: }
315:
316: public void addSolution(BindingSet bindingSet) {
317: bindingSets.add(bindingSet);
318: }
319:
320: public Set<BindingSet> getSolutions() {
321: return bindingSets;
322: }
323: }
324: }
|