1 /*
2 * ModeShape (http://www.modeshape.org)
3 * See the COPYRIGHT.txt file distributed with this work for information
4 * regarding copyright ownership. Some portions may be licensed
5 * to Red Hat, Inc. under one or more contributor license agreements.
6 * See the AUTHORS.txt file in the distribution for a full listing of
7 * individual contributors.
8 *
9 * ModeShape is free software. Unless otherwise indicated, all code in ModeShape
10 * is licensed to you under the terms of the GNU Lesser General Public License as
11 * published by the Free Software Foundation; either version 2.1 of
12 * the License, or (at your option) any later version.
13 *
14 * ModeShape is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
18 *
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this software; if not, write to the Free
21 * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
22 * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
23 */
24 package org.modeshape.graph.query.process;
25
26 import java.util.Collections;
27 import java.util.Comparator;
28 import java.util.Iterator;
29 import java.util.LinkedList;
30 import java.util.List;
31 import org.modeshape.graph.query.QueryContext;
32 import org.modeshape.graph.query.QueryResults.Columns;
33
34 /**
35 */
36 public class ExceptComponent extends SetOperationComponent {
37
38 private final Comparator<Object[]> comparator;
39
40 public ExceptComponent( QueryContext context,
41 Columns columns,
42 Iterable<ProcessingComponent> sources,
43 boolean alreadySorted,
44 boolean all ) {
45 super(context, columns, sources, alreadySorted, all);
46 this.comparator = createSortComparator(context, columns);
47 }
48
49 /**
50 * {@inheritDoc}
51 *
52 * @see org.modeshape.graph.query.process.ProcessingComponent#execute()
53 */
54 @Override
55 public List<Object[]> execute() {
56 Iterator<ProcessingComponent> sources = sources().iterator();
57 if (!sources.hasNext()) return emptyTuples();
58
59 // Execute all of the source components (so we can sort the results from the smallest to the largest) ...
60 // TODO: Parallelize this ???
61 List<List<Object[]>> allTuples = new LinkedList<List<Object[]>>();
62 while (sources.hasNext()) {
63 List<Object[]> tuples = sources.next().execute();
64 if (tuples == null) continue;
65 if (tuples.isEmpty()) return emptyTuples();
66 allTuples.add(tuples);
67 }
68 if (allTuples.isEmpty()) return emptyTuples();
69 if (allTuples.size() == 1) return allTuples.get(0); // just one source
70 // Sort the tuples by size, starting with the smallest ...
71 Collections.sort(allTuples, new Comparator<List<Object[]>>() {
72 public int compare( List<Object[]> tuples1,
73 List<Object[]> tuples2 ) {
74 return tuples1.size() - tuples2.size();
75 }
76 });
77
78 // Do the sources 2 at a time ...
79 Iterator<List<Object[]>> iter = allTuples.iterator();
80 List<Object[]> tuples = iter.next(); // already sorted ...
81 assert iter.hasNext();
82 // Process the next source with the previous ...
83 while (iter.hasNext()) {
84 List<Object[]> next = iter.next(); // already sorted ...
85 // Walk through the first and second results ...
86 Iterator<Object[]> tupleIter = tuples.iterator();
87 Iterator<Object[]> nextIter = next.iterator();
88 // There is at least one tuple in each ...
89 Object[] tuple1 = tupleIter.next();
90 Object[] tuple2 = nextIter.next();
91 while (true) {
92 int comparison = comparator.compare(tuple1, tuple2);
93 if (comparison == 0) {
94 // Both match, so remove the tuple from 'tuples' and go on ...
95 tupleIter.remove();
96 continue;
97 }
98 // No match, so leave tuple1 in 'tuples'
99 if (comparison < 0) {
100 // tuple1 is less than tuple2, so advance tupleIter ...
101 if (!tupleIter.hasNext()) {
102 // The intersection results ('tuples') has no more tuples, so go to the next source ...
103 break;
104 }
105 tuple1 = tupleIter.next();
106 continue;
107 }
108 assert comparison > 0;
109 // tuple1 is greater than tuple2, so advance nextIter ...
110 if (!nextIter.hasNext()) {
111 // The next source has no more tuples, so leave all remaining tuples, and go to the next source ...
112 break;
113 }
114 tuple2 = nextIter.next();
115 continue;
116 }
117 }
118 // Remove duplicates if requested to ...
119 removeDuplicatesIfRequested(tuples);
120 // Return all of the common tuples that were in all sources ...
121 return tuples;
122 }
123 }