|
1
21 package com.db4o.inside.fieldindex;
22
23 import com.db4o.*;
24 import com.db4o.foundation.*;
25
26 public class IndexedNodeCollector {
27
28 private final Collection4 _nodes;
29
30 private final Hashtable4 _nodeCache;
31
32 public IndexedNodeCollector(QCandidates candidates) {
33 _nodes = new Collection4();
34 _nodeCache = new Hashtable4();
35 collectIndexedNodes(candidates);
36 }
37
38 public Iterator4 getNodes() {
39 return _nodes.iterator();
40 }
41
42 private void collectIndexedNodes(QCandidates candidates) {
43 collectIndexedNodes(candidates.iterateConstraints());
44 implicitlyAndJoinsOnSameField();
45 }
46
47 private void implicitlyAndJoinsOnSameField() {
48 final Object  [] nodes = _nodes.toArray();
49 for (int i = 0; i < nodes.length; i++) {
50 Object node = nodes[i];
51 if (node instanceof OrIndexedLeaf) {
52 OrIndexedLeaf current = (OrIndexedLeaf) node;
53 OrIndexedLeaf other = findJoinOnSameFieldAtSameLevel(current);
54 if (null != other) {
55 nodes[Arrays4.indexOf(nodes, other)] = null;
56 collectImplicitAnd(current.getConstraint(), current, other);
57 }
58 }
59 }
60 }
61
62 private OrIndexedLeaf findJoinOnSameFieldAtSameLevel(OrIndexedLeaf join) {
63 final Iterator4 i = _nodes.iterator();
64 while (i.moveNext()) {
65 if (i.current() == join) {
66 continue;
67 }
68 if (i.current() instanceof OrIndexedLeaf) {
69 OrIndexedLeaf current = (OrIndexedLeaf) i.current();
70 if (current.getIndex() == join.getIndex()
71 && parentConstraint(current) == parentConstraint(join)) {
72 return current;
73 }
74 }
75 }
76 return null;
77 }
78
79 private Object parentConstraint(OrIndexedLeaf node) {
80 return node.getConstraint().parent();
81 }
82
83 private void collectIndexedNodes(final Iterator4 qcons) {
84
85 while (qcons.moveNext()) {
86 QCon qcon = (QCon)qcons.current();
87 if (isCached(qcon)) {
88 continue;
89 }
90 if (isLeaf(qcon)) {
91 if (qcon.canLoadByIndex() && qcon.canBeIndexLeaf()) {
92 final QConObject conObject = (QConObject) qcon;
93 if (conObject.hasJoins()) {
94 collectJoinedNode(conObject);
95 } else {
96 collectStandaloneNode(conObject);
97 }
98 }
99 } else {
100 if (!qcon.hasJoins()) {
101 collectIndexedNodes(qcon.iterateChildren());
102 }
103 }
104 }
105 }
106
107 private boolean isCached(QCon qcon) {
108 return null != _nodeCache.get(qcon);
109 }
110
111 private void collectStandaloneNode(final QConObject conObject) {
112 IndexedLeaf existing = findLeafOnSameField(conObject);
113 if (existing != null) {
114 collectImplicitAnd(conObject, existing, new IndexedLeaf(conObject));
115 } else {
116 _nodes.add(new IndexedLeaf(conObject));
117 }
118 }
119
120 private void collectJoinedNode(QConObject constraintWithJoins) {
121 Collection4 joins = collectTopLevelJoins(constraintWithJoins);
122 if (!canJoinsBeSearchedByIndex(joins)) {
123 return;
124 }
125 if (1 == joins.size()) {
126 _nodes.add(nodeForConstraint((QCon)joins.singleElement()));
127 return;
128 }
129 collectImplicitlyAndingJoins(joins, constraintWithJoins);
130 }
131
132 private boolean allHaveSamePath(Collection4 leaves) {
133 final Iterator4 i = leaves.iterator();
134 i.moveNext();
135 QCon first = (QCon)i.current();
136 while (i.moveNext()) {
137 if (!haveSamePath(first, (QCon)i.current())) {
138 return false;
139 }
140 }
141 return true;
142 }
143
144 private boolean haveSamePath(QCon x, QCon y) {
145 if (x == y) {
146 return true;
147 }
148 if (!x.onSameFieldAs(y)) {
149 return false;
150 }
151 if (!x.hasParent()) {
152 return !y.hasParent();
153 }
154 return haveSamePath(x.parent(), y.parent());
155 }
156
157 private Collection4 collectLeaves(Collection4 joins) {
158 Collection4 leaves = new Collection4();
159 collectLeaves(leaves, joins);
160 return leaves;
161 }
162
163 private void collectLeaves(Collection4 leaves, Collection4 joins) {
164 final Iterator4 i = joins.iterator();
165 while (i.moveNext()) {
166 final QConJoin join = ((QConJoin)i.current());
167 collectLeavesFromJoin(leaves, join);
168 }
169 }
170
171 private void collectLeavesFromJoin(Collection4 leaves, QConJoin join) {
172 collectLeavesFromJoinConstraint(leaves, join.i_constraint1);
173 collectLeavesFromJoinConstraint(leaves, join.i_constraint2);
174 }
175
176 private void collectLeavesFromJoinConstraint(Collection4 leaves, QCon constraint) {
177 if (constraint instanceof QConJoin) {
178 collectLeavesFromJoin(leaves, (QConJoin) constraint);
179 } else {
180 if (!leaves.containsByIdentity(constraint)) {
181 leaves.add(constraint);
182 }
183 }
184 }
185
186 private boolean canJoinsBeSearchedByIndex(Collection4 joins) {
187 Collection4 leaves = collectLeaves(joins);
188 return allHaveSamePath(leaves)
189 && allCanBeSearchedByIndex(leaves);
190 }
191
192 private boolean allCanBeSearchedByIndex(Collection4 leaves) {
193 final Iterator4 i = leaves.iterator();
194 while (i.moveNext()) {
195 final QCon leaf = ((QCon)i.current());
196 if (!leaf.canLoadByIndex()) {
197 return false;
198 }
199 }
200 return true;
201 }
202
203 private void collectImplicitlyAndingJoins(Collection4 joins, QConObject constraintWithJoins) {
204 final Iterator4 i = joins.iterator();
205 i.moveNext();
206 IndexedNodeWithRange last = nodeForConstraint((QCon)i.current());
207 while (i.moveNext()) {
208 final IndexedNodeWithRange node = nodeForConstraint((QCon)i.current());
209 last = new AndIndexedLeaf(constraintWithJoins, node, last);
210 _nodes.add(last);
211 }
212 }
213
214 private Collection4 collectTopLevelJoins(QConObject constraintWithJoins) {
215 Collection4 joins = new Collection4();
216 collectTopLevelJoins(joins, constraintWithJoins);
217 return joins;
218 }
219
220 private void collectTopLevelJoins(Collection4 joins, QCon constraintWithJoins) {
221 final Iterator4 i = constraintWithJoins.i_joins.iterator();
222 while (i.moveNext()) {
223 QConJoin join = (QConJoin)i.current();
224 if (!join.hasJoins()) {
225 if (!joins.containsByIdentity(join)) {
226 joins.add(join);
227 }
228 } else {
229 collectTopLevelJoins(joins, join);
230 }
231 }
232 }
233
234 private IndexedNodeWithRange newNodeForConstraint(QConJoin join) {
235 final IndexedNodeWithRange c1 = nodeForConstraint(join.i_constraint1);
236 final IndexedNodeWithRange c2 = nodeForConstraint(join.i_constraint2);
237 if (join.isOr()) {
238 return new OrIndexedLeaf(join.i_constraint1, c1, c2);
239 }
240 return new AndIndexedLeaf(join.i_constraint1, c1, c2);
241 }
242
243 private IndexedNodeWithRange nodeForConstraint(QCon con) {
244 IndexedNodeWithRange node = (IndexedNodeWithRange) _nodeCache.get(con);
245 if (null != node || _nodeCache.containsKey(con)) {
246 return node;
247 }
248 node = newNodeForConstraint(con);
249 _nodeCache.put(con, node);
250 return node;
251 }
252
253 private IndexedNodeWithRange newNodeForConstraint(QCon con) {
254 if (con instanceof QConJoin) {
255 return newNodeForConstraint((QConJoin)con);
256 }
257 return new IndexedLeaf((QConObject)con);
258 }
259
260 private void collectImplicitAnd(final QCon constraint, IndexedNodeWithRange x, final IndexedNodeWithRange y) {
261 _nodes.remove(x);
262 _nodes.remove(y);
263 _nodes.add(new AndIndexedLeaf(constraint, x, y));
264 }
265
266 private IndexedLeaf findLeafOnSameField(QConObject conObject) {
267 final Iterator4 i = _nodes.iterator();
268 while (i.moveNext()) {
269 if (i.current() instanceof IndexedLeaf) {
270 IndexedLeaf leaf = (IndexedLeaf)i.current();
271 if (conObject.onSameFieldAs(leaf.constraint())) {
272 return leaf;
273 }
274 }
275 }
276 return null;
277 }
278
279 private boolean isLeaf(QCon qcon) {
280 return !qcon.hasChildren();
281 }
282 }
283 |
Popular Tags |
Java API By Example, From Geeks To Geeks.