001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one
003     *  or more contributor license agreements.  See the NOTICE file
004     *  distributed with this work for additional information
005     *  regarding copyright ownership.  The ASF licenses this file
006     *  to you under the Apache License, Version 2.0 (the
007     *  "License"); you may not use this file except in compliance
008     *  with the License.  You may obtain a copy of the License at
009     *  
010     *    http://www.apache.org/licenses/LICENSE-2.0
011     *  
012     *  Unless required by applicable law or agreed to in writing,
013     *  software distributed under the License is distributed on an
014     *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015     *  KIND, either express or implied.  See the License for the
016     *  specific language governing permissions and limitations
017     *  under the License. 
018     *  
019     */
020    package org.apache.directory.server.xdbm.search.impl;
021    
022    
023    import java.util.ArrayList;
024    import java.util.List;
025    
026    import org.apache.directory.server.i18n.I18n;
027    import org.apache.directory.server.xdbm.IndexCursor;
028    import org.apache.directory.server.xdbm.Store;
029    import org.apache.directory.server.xdbm.search.Evaluator;
030    import org.apache.directory.shared.ldap.NotImplementedException;
031    import org.apache.directory.shared.ldap.entry.ServerEntry;
032    import org.apache.directory.shared.ldap.filter.AndNode;
033    import org.apache.directory.shared.ldap.filter.ExprNode;
034    import org.apache.directory.shared.ldap.filter.NotNode;
035    import org.apache.directory.shared.ldap.filter.OrNode;
036    import org.apache.directory.shared.ldap.filter.ScopeNode;
037    import org.apache.directory.shared.ldap.filter.SearchScope;
038    
039    
040    /**
041     * Builds Cursors over candidates that satisfy a filter expression.
042     * 
043     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
044     * @version $Rev: 927146 $
045     */
046    public class CursorBuilder<ID>
047    {
048        /** The database used by this builder */
049        private Store<ServerEntry, ID> db = null;
050    
051        /** Evaluator dependency on a EvaluatorBuilder */
052        private EvaluatorBuilder<ID> evaluatorBuilder;
053    
054    
055        /**
056         * Creates an expression tree enumerator.
057         *
058         * @param db database used by this enumerator
059         * @param evaluatorBuilder the evaluator builder
060         */
061        public CursorBuilder( Store<ServerEntry, ID> db, EvaluatorBuilder<ID> evaluatorBuilder )
062        {
063            this.db = db;
064            this.evaluatorBuilder = evaluatorBuilder;
065        }
066    
067    
068        public <T> IndexCursor<?, ServerEntry, ID> build( ExprNode node ) throws Exception
069        {
070            switch ( node.getAssertionType() )
071            {
072                /* ---------- LEAF NODE HANDLING ---------- */
073    
074                case APPROXIMATE:
075                    return new ApproximateCursor<T, ID>( db, ( ApproximateEvaluator<T, ID> ) evaluatorBuilder.build( node ) );
076    
077                case EQUALITY:
078                    return new EqualityCursor<T, ID>( db, ( EqualityEvaluator<T, ID> ) evaluatorBuilder.build( node ) );
079    
080                case GREATEREQ:
081                    return new GreaterEqCursor<T, ID>( db, ( GreaterEqEvaluator<T, ID> ) evaluatorBuilder.build( node ) );
082    
083                case LESSEQ:
084                    return new LessEqCursor<T, ID>( db, ( LessEqEvaluator<T, ID> ) evaluatorBuilder.build( node ) );
085    
086                case PRESENCE:
087                    return new PresenceCursor<ID>( db, ( PresenceEvaluator<ID> ) evaluatorBuilder.build( node ) );
088    
089                case SCOPE:
090                    if ( ( ( ScopeNode ) node ).getScope() == SearchScope.ONELEVEL )
091                    {
092                        return new OneLevelScopeCursor<ID>( db,
093                            ( OneLevelScopeEvaluator<ServerEntry, ID> ) evaluatorBuilder.build( node ) );
094                    }
095                    else
096                    {
097                        return new SubtreeScopeCursor<ID>( db, ( SubtreeScopeEvaluator<ServerEntry, ID> ) evaluatorBuilder
098                            .build( node ) );
099                    }
100    
101                case SUBSTRING:
102                    return new SubstringCursor<ID>( db, ( SubstringEvaluator<ID> ) evaluatorBuilder.build( node ) );
103    
104                    /* ---------- LOGICAL OPERATORS ---------- */
105    
106                case AND:
107                    return buildAndCursor( ( AndNode ) node );
108    
109                case NOT:
110                    return new NotCursor<ID, ID>( db, evaluatorBuilder.build( ( ( NotNode ) node ).getFirstChild() ) );
111    
112                case OR:
113                    return buildOrCursor( ( OrNode ) node );
114    
115                    /* ----------  NOT IMPLEMENTED  ---------- */
116    
117                case ASSERTION:
118                case EXTENSIBLE:
119                    throw new NotImplementedException();
120    
121                default:
122                    throw new IllegalStateException( I18n.err( I18n.ERR_260, node.getAssertionType() ) );
123            }
124        }
125    
126    
127        /**
128         * Creates a OrCursor over a disjunction expression branch node.
129         *
130         * @param node the disjunction expression branch node
131         * @return Cursor over candidates satisfying disjunction expression
132         * @throws Exception on db access failures
133         */
134        private IndexCursor<?, ServerEntry, ID> buildOrCursor( OrNode node ) throws Exception
135        {
136            List<ExprNode> children = node.getChildren();
137            List<IndexCursor<? extends Object, ServerEntry, ID>> childCursors = new ArrayList<IndexCursor<?, ServerEntry, ID>>(
138                children.size() );
139            List<Evaluator<? extends ExprNode, ServerEntry, ID>> childEvaluators = new ArrayList<Evaluator<? extends ExprNode, ServerEntry, ID>>(
140                children.size() );
141    
142            // Recursively create Cursors and Evaluators for each child expression node
143            for ( ExprNode child : children )
144            {
145                childCursors.add( build( child ) );
146                childEvaluators.add( evaluatorBuilder.build( child ) );
147            }
148    
149            return new OrCursor( childCursors, childEvaluators );
150        }
151    
152    
153        /**
154         * Creates an AndCursor over a conjunction expression branch node.
155         *
156         * @param node a conjunction expression branch node
157         * @return Cursor over the conjunction expression
158         * @throws Exception on db access failures
159         */
160        private IndexCursor<?, ServerEntry, ID> buildAndCursor( AndNode node ) throws Exception
161        {
162            int minIndex = 0;
163            long minValue = Long.MAX_VALUE;
164            //noinspection UnusedAssignment
165            long value = Long.MAX_VALUE;
166    
167            /*
168             * We scan the child nodes of a branch node searching for the child
169             * expression node with the smallest scan count.  This is the child
170             * we will use for iteration by creating a Cursor over its expression.
171             */
172            final List<ExprNode> children = node.getChildren();
173    
174            for ( int ii = 0; ii < children.size(); ii++ )
175            {
176                ExprNode child = children.get( ii );
177                Object count = child.get( "count" );
178                if ( count == null )
179                {
180                    continue;
181                }
182                value = ( Long ) count;
183                minValue = Math.min( minValue, value );
184    
185                if ( minValue == value )
186                {
187                    minIndex = ii;
188                }
189            }
190    
191            // Once found we build the child Evaluators minus the one for the minChild
192            ExprNode minChild = children.get( minIndex );
193            List<Evaluator<? extends ExprNode, ServerEntry, ID>> childEvaluators = new ArrayList<Evaluator<? extends ExprNode, ServerEntry, ID>>(
194                children.size() - 1 );
195            for ( ExprNode child : children )
196            {
197                if ( child == minChild )
198                {
199                    continue;
200                }
201    
202                childEvaluators.add( evaluatorBuilder.build( child ) );
203            }
204    
205            // Do recursive call to build min child Cursor then create AndCursor
206            IndexCursor<?, ServerEntry, ID> childCursor = build( minChild );
207            return new AndCursor( childCursor, childEvaluators );
208        }
209    }