001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.internal.fieldindex;
022:
023: import com.db4o.foundation.*;
024: import com.db4o.internal.query.processor.*;
025:
026: public class IndexedNodeCollector {
027:
028: private final Collection4 _nodes;
029:
030: private final Hashtable4 _nodeCache;
031:
032: public IndexedNodeCollector(QCandidates candidates) {
033: _nodes = new Collection4();
034: _nodeCache = new Hashtable4();
035: collectIndexedNodes(candidates);
036: }
037:
038: public Iterator4 getNodes() {
039: return _nodes.iterator();
040: }
041:
042: private void collectIndexedNodes(QCandidates candidates) {
043: collectIndexedNodes(candidates.iterateConstraints());
044: implicitlyAndJoinsOnSameField();
045: }
046:
047: private void implicitlyAndJoinsOnSameField() {
048: final Object[] nodes = _nodes.toArray();
049: for (int i = 0; i < nodes.length; i++) {
050: Object node = nodes[i];
051: if (node instanceof OrIndexedLeaf) {
052: OrIndexedLeaf current = (OrIndexedLeaf) node;
053: OrIndexedLeaf other = findJoinOnSameFieldAtSameLevel(current);
054: if (null != other) {
055: nodes[Arrays4.indexOf(nodes, other)] = null;
056: collectImplicitAnd(current.getConstraint(),
057: current, other);
058: }
059: }
060: }
061: }
062:
063: private OrIndexedLeaf findJoinOnSameFieldAtSameLevel(
064: OrIndexedLeaf join) {
065: final Iterator4 i = _nodes.iterator();
066: while (i.moveNext()) {
067: if (i.current() == join) {
068: continue;
069: }
070: if (i.current() instanceof OrIndexedLeaf) {
071: OrIndexedLeaf current = (OrIndexedLeaf) i.current();
072: if (current.getIndex() == join.getIndex()
073: && parentConstraint(current) == parentConstraint(join)) {
074: return current;
075: }
076: }
077: }
078: return null;
079: }
080:
081: private Object parentConstraint(OrIndexedLeaf node) {
082: return node.getConstraint().parent();
083: }
084:
085: private void collectIndexedNodes(final Iterator4 qcons) {
086:
087: while (qcons.moveNext()) {
088: QCon qcon = (QCon) qcons.current();
089: if (isCached(qcon)) {
090: continue;
091: }
092: if (isLeaf(qcon)) {
093: if (qcon.canLoadByIndex() && qcon.canBeIndexLeaf()) {
094: final QConObject conObject = (QConObject) qcon;
095: if (conObject.hasJoins()) {
096: collectJoinedNode(conObject);
097: } else {
098: collectStandaloneNode(conObject);
099: }
100: }
101: } else {
102: if (!qcon.hasJoins()) {
103: collectIndexedNodes(qcon.iterateChildren());
104: }
105: }
106: }
107: }
108:
109: private boolean isCached(QCon qcon) {
110: return null != _nodeCache.get(qcon);
111: }
112:
113: private void collectStandaloneNode(final QConObject conObject) {
114: IndexedLeaf existing = findLeafOnSameField(conObject);
115: if (existing != null) {
116: collectImplicitAnd(conObject, existing, new IndexedLeaf(
117: conObject));
118: } else {
119: _nodes.add(new IndexedLeaf(conObject));
120: }
121: }
122:
123: private void collectJoinedNode(QConObject constraintWithJoins) {
124: Collection4 joins = collectTopLevelJoins(constraintWithJoins);
125: if (!canJoinsBeSearchedByIndex(joins)) {
126: return;
127: }
128: if (1 == joins.size()) {
129: _nodes.add(nodeForConstraint((QCon) joins.singleElement()));
130: return;
131: }
132: collectImplicitlyAndingJoins(joins, constraintWithJoins);
133: }
134:
135: private boolean allHaveSamePath(Collection4 leaves) {
136: final Iterator4 i = leaves.iterator();
137: i.moveNext();
138: QCon first = (QCon) i.current();
139: while (i.moveNext()) {
140: if (!haveSamePath(first, (QCon) i.current())) {
141: return false;
142: }
143: }
144: return true;
145: }
146:
147: private boolean haveSamePath(QCon x, QCon y) {
148: if (x == y) {
149: return true;
150: }
151: if (!x.onSameFieldAs(y)) {
152: return false;
153: }
154: if (!x.hasParent()) {
155: return !y.hasParent();
156: }
157: return haveSamePath(x.parent(), y.parent());
158: }
159:
160: private Collection4 collectLeaves(Collection4 joins) {
161: Collection4 leaves = new Collection4();
162: collectLeaves(leaves, joins);
163: return leaves;
164: }
165:
166: private void collectLeaves(Collection4 leaves, Collection4 joins) {
167: final Iterator4 i = joins.iterator();
168: while (i.moveNext()) {
169: final QConJoin join = ((QConJoin) i.current());
170: collectLeavesFromJoin(leaves, join);
171: }
172: }
173:
174: private void collectLeavesFromJoin(Collection4 leaves, QConJoin join) {
175: collectLeavesFromJoinConstraint(leaves, join.i_constraint1);
176: collectLeavesFromJoinConstraint(leaves, join.i_constraint2);
177: }
178:
179: private void collectLeavesFromJoinConstraint(Collection4 leaves,
180: QCon constraint) {
181: if (constraint instanceof QConJoin) {
182: collectLeavesFromJoin(leaves, (QConJoin) constraint);
183: } else {
184: if (!leaves.containsByIdentity(constraint)) {
185: leaves.add(constraint);
186: }
187: }
188: }
189:
190: private boolean canJoinsBeSearchedByIndex(Collection4 joins) {
191: Collection4 leaves = collectLeaves(joins);
192: return allHaveSamePath(leaves)
193: && allCanBeSearchedByIndex(leaves);
194: }
195:
196: private boolean allCanBeSearchedByIndex(Collection4 leaves) {
197: final Iterator4 i = leaves.iterator();
198: while (i.moveNext()) {
199: final QCon leaf = ((QCon) i.current());
200: if (!leaf.canLoadByIndex()) {
201: return false;
202: }
203: }
204: return true;
205: }
206:
207: private void collectImplicitlyAndingJoins(Collection4 joins,
208: QConObject constraintWithJoins) {
209: final Iterator4 i = joins.iterator();
210: i.moveNext();
211: IndexedNodeWithRange last = nodeForConstraint((QCon) i
212: .current());
213: while (i.moveNext()) {
214: final IndexedNodeWithRange node = nodeForConstraint((QCon) i
215: .current());
216: last = new AndIndexedLeaf(constraintWithJoins, node, last);
217: _nodes.add(last);
218: }
219: }
220:
221: private Collection4 collectTopLevelJoins(
222: QConObject constraintWithJoins) {
223: Collection4 joins = new Collection4();
224: collectTopLevelJoins(joins, constraintWithJoins);
225: return joins;
226: }
227:
228: private void collectTopLevelJoins(Collection4 joins,
229: QCon constraintWithJoins) {
230: final Iterator4 i = constraintWithJoins.i_joins.iterator();
231: while (i.moveNext()) {
232: QConJoin join = (QConJoin) i.current();
233: if (!join.hasJoins()) {
234: if (!joins.containsByIdentity(join)) {
235: joins.add(join);
236: }
237: } else {
238: collectTopLevelJoins(joins, join);
239: }
240: }
241: }
242:
243: private IndexedNodeWithRange newNodeForConstraint(QConJoin join) {
244: final IndexedNodeWithRange c1 = nodeForConstraint(join.i_constraint1);
245: final IndexedNodeWithRange c2 = nodeForConstraint(join.i_constraint2);
246: if (join.isOr()) {
247: return new OrIndexedLeaf(findLeafForJoin(join), c1, c2);
248: }
249: return new AndIndexedLeaf(join.i_constraint1, c1, c2);
250: }
251:
252: private QCon findLeafForJoin(QConJoin join) {
253: if (join.i_constraint1 instanceof QConObject) {
254: return join.i_constraint1;
255: }
256: QCon con = join.i_constraint2;
257: if (con instanceof QConObject) {
258: return con;
259: }
260: return findLeafForJoin((QConJoin) con);
261: }
262:
263: private IndexedNodeWithRange nodeForConstraint(QCon con) {
264: IndexedNodeWithRange node = (IndexedNodeWithRange) _nodeCache
265: .get(con);
266: if (null != node || _nodeCache.containsKey(con)) {
267: return node;
268: }
269: node = newNodeForConstraint(con);
270: _nodeCache.put(con, node);
271: return node;
272: }
273:
274: private IndexedNodeWithRange newNodeForConstraint(QCon con) {
275: if (con instanceof QConJoin) {
276: return newNodeForConstraint((QConJoin) con);
277: }
278: return new IndexedLeaf((QConObject) con);
279: }
280:
281: private void collectImplicitAnd(final QCon constraint,
282: IndexedNodeWithRange x, final IndexedNodeWithRange y) {
283: _nodes.remove(x);
284: _nodes.remove(y);
285: _nodes.add(new AndIndexedLeaf(constraint, x, y));
286: }
287:
288: private IndexedLeaf findLeafOnSameField(QConObject conObject) {
289: final Iterator4 i = _nodes.iterator();
290: while (i.moveNext()) {
291: if (i.current() instanceof IndexedLeaf) {
292: IndexedLeaf leaf = (IndexedLeaf) i.current();
293: if (conObject.onSameFieldAs(leaf.constraint())) {
294: return leaf;
295: }
296: }
297: }
298: return null;
299: }
300:
301: private boolean isLeaf(QCon qcon) {
302: return !qcon.hasChildren();
303: }
304: }
|