KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > ldap > server > db > ExpressionEnumerator


1 /*
2  * Copyright 2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  *
16  */
17 package org.apache.ldap.server.db;
18
19
20 import org.apache.ldap.common.NotImplementedException;
21 import org.apache.ldap.common.filter.*;
22 import org.apache.ldap.server.schema.AttributeTypeRegistry;
23
24 import javax.naming.NamingEnumeration JavaDoc;
25 import javax.naming.NamingException JavaDoc;
26 import java.math.BigInteger JavaDoc;
27 import java.util.ArrayList JavaDoc;
28
29
30 /**
31  * Enumerates over candidates that satisfy a filter expression.
32  *
33  * @author <a HREF="mailto:dev@directory.apache.org">Apache Directory Project</a>
34  * @version $Rev: 169198 $
35  */
36 public class ExpressionEnumerator implements Enumerator
37 {
38     /** The database used by this enumerator */
39     private Database db = null;
40     /** Enumerator flyweight for evaulating filter scope assertions */
41     private ScopeEnumerator scopeEnumerator;
42     /** Enumerator flyweight for evaulating filter substring assertions */
43     private SubstringEnumerator substringEnumerator;
44     /** Evaluator dependency on a ExpressionEvaluator */
45     private ExpressionEvaluator evaluator;
46
47
48     /**
49      * Creates an expression tree enumerator.
50      *
51      * @param db database used by this enumerator
52      * @param evaluator
53      */
54     public ExpressionEnumerator( Database db,
55                                  AttributeTypeRegistry attributeTypeRegistry,
56                                  ExpressionEvaluator evaluator )
57     {
58         this.db = db;
59         this.evaluator = evaluator;
60
61         LeafEvaluator leafEvaluator = evaluator.getLeafEvaluator();
62         scopeEnumerator = new ScopeEnumerator( db, leafEvaluator.getScopeEvaluator() );
63         substringEnumerator = new SubstringEnumerator( db, attributeTypeRegistry,
64                 leafEvaluator.getSubstringEvaluator() );
65     }
66
67
68     /**
69      * Creates an enumeration to enumerate through the set of candidates
70      * satisfying a filter expression.
71      *
72      * @param node a filter expression root
73      * @return an enumeration over the
74      * @throws NamingException if database access fails
75      */
76     public NamingEnumeration JavaDoc enumerate( ExprNode node ) throws NamingException JavaDoc
77     {
78         NamingEnumeration JavaDoc list = null;
79
80         if ( node instanceof ScopeNode )
81         {
82             list = scopeEnumerator.enumerate( node );
83         }
84         else if ( node instanceof AssertionNode )
85         {
86             throw new IllegalArgumentException JavaDoc( "Cannot produce enumeration "
87                 + "on an AssertionNode" );
88         }
89         else if ( node.isLeaf() )
90         {
91             LeafNode leaf = ( LeafNode ) node;
92
93             switch( leaf.getAssertionType() )
94             {
95             case( LeafNode.APPROXIMATE ):
96                 list = enumEquality( ( SimpleNode ) node );
97                 break;
98             case( LeafNode.EQUALITY ):
99                 list = enumEquality( ( SimpleNode ) node );
100                 break;
101             case( LeafNode.EXTENSIBLE ):
102                 // N O T I M P L E M E N T E D Y E T !
103 throw new NotImplementedException();
104             case( LeafNode.GREATEREQ ):
105                 list = enumGreater( ( SimpleNode ) node, true );
106                 break;
107             case( LeafNode.LESSEQ ):
108                 list = enumGreater( ( SimpleNode ) node, false );
109                 break;
110             case( LeafNode.PRESENCE ):
111                 list = enumPresence( ( PresenceNode ) node );
112                 break;
113             case( LeafNode.SUBSTRING ):
114                 list = substringEnumerator.enumerate( leaf );
115                 break;
116             default:
117                 throw new IllegalArgumentException JavaDoc( "Unknown leaf assertion" );
118             }
119         }
120         else
121         {
122             BranchNode branch = ( BranchNode ) node;
123             
124             switch( branch.getOperator() )
125             {
126             case( BranchNode.AND ):
127                 list = enumConj( branch );
128                 break;
129             case( BranchNode.NOT ):
130                 list = enumNeg( branch );
131                 break;
132             case( BranchNode.OR ):
133                 list = enumDisj( branch );
134                 break;
135             default:
136                 throw new IllegalArgumentException JavaDoc(
137                     "Unknown branch logical operator" );
138             }
139         }
140
141         return list;
142     }
143
144
145     /**
146      * Creates an enumeration over a disjunction expression branch node.
147      *
148      * @param node the disjunction expression branch node
149      */
150     private NamingEnumeration JavaDoc enumDisj( BranchNode node ) throws NamingException JavaDoc
151     {
152         ArrayList JavaDoc children = node.getChildren();
153         NamingEnumeration JavaDoc[] childEnumerations = new NamingEnumeration JavaDoc [children.size()];
154
155         // Recursively create NamingEnumerations for each child expression node
156 for ( int ii = 0; ii < childEnumerations.length; ii++ )
157         {
158             childEnumerations[ii] = enumerate( ( ExprNode ) children.get( ii ) );
159         }
160
161         return new DisjunctionEnumeration( childEnumerations );
162     }
163
164
165     /**
166      * Creates an enumeration over a negation expression branch node.
167      *
168      * @param node a negation expression branch node
169      */
170     private NamingEnumeration JavaDoc enumNeg( final BranchNode node ) throws NamingException JavaDoc
171     {
172         Index idx = null;
173         NamingEnumeration JavaDoc childEnumeration = null;
174         NamingEnumeration JavaDoc enumeration = null;
175
176         // Iterates over entire set of index values
177 if ( node.getChild().isLeaf() )
178         {
179             LeafNode child = ( LeafNode ) node.getChild();
180             idx = db.getUserIndex( child.getAttribute() );
181             childEnumeration = idx.listIndices();
182         }
183         // Iterates over the entire set of entries
184 else
185         {
186             idx = db.getNdnIndex();
187             childEnumeration = idx.listIndices();
188         }
189
190
191         IndexAssertion assertion = new IndexAssertion()
192         {
193             public boolean assertCandidate( IndexRecord rec ) throws NamingException JavaDoc
194             {
195                 // NOTICE THE ! HERE
196 // The candidate is valid if it does not pass assertion. A
197 // candidate that passes assertion is therefore invalid.
198 return ! evaluator.evaluate( node.getChild(), rec );
199             }
200         };
201
202         enumeration = new IndexAssertionEnumeration( childEnumeration, assertion, true );
203         return enumeration;
204     }
205
206
207     /**
208      * Creates an enumeration over a conjunction expression branch node.
209      *
210      * @param node a conjunction expression branch node
211      */
212     private NamingEnumeration JavaDoc enumConj( final BranchNode node ) throws NamingException JavaDoc
213     {
214         int minIndex = 0;
215         int minValue = Integer.MAX_VALUE;
216         int value = Integer.MAX_VALUE;
217
218         /*
219          * We scan the child nodes of a branch node searching for the child
220          * expression node with the smallest scan count. This is the child
221          * we will use for iteration by creating a NamingEnumeration over its
222          * expression.
223          */
224         final ArrayList JavaDoc children = node.getChildren();
225         for ( int ii = 0; ii < children.size(); ii++ )
226         {
227             ExprNode child = ( ExprNode ) children.get( ii );
228             value = ( ( BigInteger JavaDoc ) child.get( "count" ) ).intValue();
229             minValue = Math.min( minValue, value );
230
231             if ( minValue == value )
232             {
233                 minIndex = ii;
234             }
235         }
236
237         // Once found we build the child enumeration & the wrapping enum
238 final ExprNode minChild = ( ExprNode ) children.get( minIndex );
239         IndexAssertion assertion = new IndexAssertion()
240         {
241             public boolean assertCandidate( IndexRecord rec ) throws NamingException JavaDoc
242             {
243                 for ( int ii = 0; ii < children.size(); ii++ )
244                 {
245                     ExprNode child = ( ExprNode ) children.get( ii );
246
247                     // Skip the child (with min scan count) chosen for enum
248 if ( child == minChild )
249                     {
250                         continue;
251                     }
252                     else if ( ! evaluator.evaluate( child, rec ) )
253                     {
254                         return false;
255                     }
256                 }
257
258                 return true;
259             }
260         };
261
262         // Do recursive call to build child enumeration then wrap and return
263 NamingEnumeration JavaDoc underlying = enumerate( minChild );
264         IndexAssertionEnumeration iae;
265         iae = new IndexAssertionEnumeration( underlying, assertion );
266         return iae;
267     }
268
269
270     /**
271      * Returns an enumeration over candidates that satisfy a presence attribute
272      * value assertion.
273      *
274      * @param node the presence AVA node
275      * @return an enumeration over the index records matching the AVA
276      * @throws NamingException if there is a failure while accessing the db
277      */
278     private NamingEnumeration JavaDoc enumPresence( final PresenceNode node )
279         throws NamingException JavaDoc
280     {
281         if ( db.hasUserIndexOn( node.getAttribute() ) )
282         {
283             Index idx = db.getExistanceIndex();
284             return idx.listIndices( node.getAttribute() );
285         }
286         
287         return nonIndexedScan( node );
288     }
289     
290
291     /**
292      * Returns an enumeration over candidates that satisfy a simple greater than
293      * or less than or equal to attribute value assertion.
294      *
295      * @param node the AVA node
296      * @param isGreater true if >= false if <= is used
297      * @return an enumeration over the index records matching the AVA
298      * @throws NamingException if there is a failure while accessing the db
299      */
300     private NamingEnumeration JavaDoc enumGreater( final SimpleNode node,
301         final boolean isGreater ) throws NamingException JavaDoc
302     {
303         if ( db.hasUserIndexOn( node.getAttribute() ) )
304         {
305             Index idx = db.getUserIndex( node.getAttribute() );
306             
307             if ( isGreater )
308             {
309                 return idx.listIndices( node.getValue(), true );
310             }
311             else
312             {
313                 return idx.listIndices( node.getValue(), false );
314             }
315         }
316
317         return nonIndexedScan( node );
318     }
319     
320     
321     /**
322      * Returns an enumeration over candidates that satisfy a simple equality
323      * attribute value assertion.
324      *
325      * @param node the equality AVA node
326      * @return an enumeration over the index records matching the AVA
327      * @throws NamingException if there is a failure while accessing the db
328      */
329     private NamingEnumeration JavaDoc enumEquality( final SimpleNode node )
330         throws NamingException JavaDoc
331     {
332         if ( db.hasUserIndexOn( node.getAttribute() ) )
333         {
334             Index idx = db.getUserIndex( node.getAttribute() );
335             return idx.listIndices( node.getValue() );
336         }
337
338         return nonIndexedScan( node );
339     }
340     
341     
342     /**
343      * Creates a scan over all entries in the database with an assertion to test
344      * for the correct evaluation of a filter expression on a LeafNode.
345      *
346      * @param node the leaf node to produce a scan over
347      * @return the enumeration over all perspective candidates satisfying expr
348      * @throws NamingException if db access failures result
349      */
350     private NamingEnumeration JavaDoc nonIndexedScan( final LeafNode node )
351         throws NamingException JavaDoc
352     {
353         NamingEnumeration JavaDoc underlying = db.getNdnIndex().listIndices();
354         IndexAssertion assertion = new IndexAssertion()
355         {
356             public boolean assertCandidate( IndexRecord record )
357                 throws NamingException JavaDoc
358             {
359                 return evaluator.getLeafEvaluator().evaluate( node, record );
360             }
361         };
362         
363         return new IndexAssertionEnumeration( underlying, assertion );
364     }
365 }
366
Popular Tags