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.ArrayList;
27 import java.util.Comparator;
28 import java.util.Iterator;
29 import java.util.List;
30 import net.jcip.annotations.Immutable;
31 import org.modeshape.graph.Location;
32 import org.modeshape.graph.query.QueryContext;
33 import org.modeshape.graph.query.QueryResults.Columns;
34 import org.modeshape.graph.query.model.ChildNodeJoinCondition;
35 import org.modeshape.graph.query.model.EquiJoinCondition;
36 import org.modeshape.graph.query.model.JoinType;
37 import org.modeshape.graph.query.model.SameNodeJoinCondition;
38
39 /**
40 * Create a processing component that performs a merge-join algorithm. This algorithm only makes sense for
41 * {@link EquiJoinCondition equi-joins}, {@link ChildNodeJoinCondition child-node joins}, and {@link SameNodeJoinCondition
42 * same-node joins}.
43 * <p>
44 * <b> Note that it is required that the left and right processing components (where this component gets its results) must already
45 * be properly sorted and have had duplicates removed. </b>
46 * </p>
47 */
48 @Immutable
49 public class MergeJoinComponent extends JoinComponent {
50
51 public MergeJoinComponent( QueryContext context,
52 ProcessingComponent left,
53 ProcessingComponent right,
54 EquiJoinCondition condition,
55 JoinType joinType ) {
56 super(context, left, right, condition, joinType);
57 }
58
59 public MergeJoinComponent( QueryContext context,
60 ProcessingComponent left,
61 ProcessingComponent right,
62 ChildNodeJoinCondition condition,
63 JoinType joinType ) {
64 super(context, left, right, condition, joinType);
65 }
66
67 public MergeJoinComponent( QueryContext context,
68 ProcessingComponent left,
69 ProcessingComponent right,
70 SameNodeJoinCondition condition,
71 JoinType joinType ) {
72 super(context, left, right, condition, joinType);
73 }
74
75 /**
76 * {@inheritDoc}
77 *
78 * @see org.modeshape.graph.query.process.ProcessingComponent#execute()
79 */
80 @Override
81 public List<Object[]> execute() {
82 // Construct the necessary components ...
83 final Columns leftColumns = left().getColumns();
84 final Columns rightColumns = right().getColumns();
85 final ValueSelector leftSelector = valueSelectorFor(left(), getJoinCondition());
86 final ValueSelector rightSelector = valueSelectorFor(right(), getJoinCondition());
87 final Comparator<Object> comparator = comparatorFor(getContext(), left(), right(), getJoinCondition());
88 final TupleMerger merger = createMerger(getColumns(), leftColumns, rightColumns);
89
90 // Walk through the left and right results ...
91 List<Object[]> leftTuples = left().execute();
92 List<Object[]> rightTuples = right().execute();
93 List<Object[]> tuples = new ArrayList<Object[]>(leftTuples.size() * rightTuples.size());
94 Iterator<Object[]> leftIter = leftTuples.iterator();
95 Iterator<Object[]> rightIter = rightTuples.iterator();
96 Object[] leftTuple = leftIter.next();
97 Object[] rightTuple = rightIter.next();
98 Object[] nextLeftTuple = null;
99 Object[] nextRightTuple = null;
100 while (true) {
101 // Get the value from the left and right side ...
102 Object leftValue = leftSelector.evaluate(leftTuple);
103 Object rightValue = rightSelector.evaluate(rightTuple);
104 // Determine if the tuples should be joined ...
105 int compare = comparator.compare(leftValue, rightValue);
106 while (compare == 0) {
107 Object[] result = merger.merge(leftTuple, rightTuple);
108 tuples.add(result);
109
110 // Peek at the next right tuple, but skip any duplicates ...
111 if (nextRightTuple == null) {
112 nextRightTuple = rightIter.next();
113 while (isSameTuple(rightColumns, nextRightTuple, rightTuple)) {
114 nextRightTuple = rightIter.next();
115 }
116 }
117
118 // Compare the leftTuple with the nextRightTuple ...
119 leftValue = leftSelector.evaluate(leftTuple);
120 rightValue = rightSelector.evaluate(nextRightTuple);
121 compare = comparator.compare(leftValue, rightValue);
122 if (compare == 0) {
123 // This is a good match, update the variables and repeat ...
124 rightTuple = nextRightTuple;
125 nextRightTuple = null;
126 continue;
127 }
128 if (compare > 0) {
129 // The rightTuple is smaller than the left, so we need to increment the right again ...
130 rightTuple = nextRightTuple;
131 nextRightTuple = null;
132 compare = 0; // to prevent iteration below ...
133 break;
134 }
135
136 // Otherwise, the leftTuple didn't work with the nextRightTuple,
137 // so try the nextLeftTuple with the rightTuple ...
138 nextLeftTuple = leftIter.next();
139 while (isSameTuple(leftColumns, nextLeftTuple, leftTuple)) {
140 nextLeftTuple = leftIter.next();
141 }
142 leftValue = leftSelector.evaluate(nextLeftTuple);
143 rightValue = rightSelector.evaluate(rightTuple);
144 compare = comparator.compare(leftValue, rightValue);
145 if (compare == 0) {
146 // This is a good match, so update the variables and repeat ...
147 leftTuple = nextLeftTuple;
148 nextLeftTuple = null;
149 continue;
150 }
151
152 // Otherwise, neither was a good match, so advance both ...
153 leftTuple = nextLeftTuple;
154 rightTuple = nextRightTuple;
155 nextLeftTuple = null;
156 nextRightTuple = null;
157 compare = 0; // to prevent iteration below ...
158 break;
159 }
160 // There wasn't a match ...
161 if (compare < 0) {
162 // The leftValue is smaller than the right, so we need to increment the left ...
163 if (!leftIter.hasNext()) break;
164 leftTuple = leftIter.next();
165 }
166 if (compare > 0) {
167 // The rightValue is smaller than the left, so we need to increment the right ...
168 if (!rightIter.hasNext()) break;
169 rightTuple = rightIter.next();
170 }
171 }
172 return tuples;
173 }
174
175 protected final boolean isSameTuple( Columns columns,
176 Object[] tuple1,
177 Object[] tuple2 ) {
178 for (int i = columns.getColumnCount(); i != columns.getLocationCount(); ++i) {
179 Location location = (Location)tuple1[i];
180 Location location2 = (Location)tuple2[i];
181 if (!location.isSame(location2)) return false;
182 }
183 return true;
184 }
185 }