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.Collections;
025    import java.util.Comparator;
026    import java.util.List;
027    
028    import org.apache.directory.server.xdbm.IndexEntry;
029    import org.apache.directory.server.xdbm.AbstractIndexCursor;
030    import org.apache.directory.server.xdbm.IndexCursor;
031    import org.apache.directory.server.xdbm.search.Evaluator;
032    import org.apache.directory.server.i18n.I18n;
033    import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException;
034    import org.apache.directory.shared.ldap.entry.ServerEntry;
035    import org.apache.directory.shared.ldap.filter.ExprNode;
036    
037    
038    /**
039     * A Cursor returning candidates satisfying a logical conjunction expression.
040     *
041     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
042     * @version $Rev$
043     */
044    public class AndCursor<V, ID> extends AbstractIndexCursor<V, ServerEntry, ID>
045    {
046        private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_707 );
047        private final IndexCursor<V, ServerEntry, ID> wrapped;
048        private final List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators;
049        private boolean available = false;
050    
051    
052        public AndCursor( IndexCursor<V, ServerEntry, ID> wrapped,
053            List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators )
054        {
055            this.wrapped = wrapped;
056            this.evaluators = optimize( evaluators );
057        }
058    
059    
060        public boolean available()
061        {
062            return available;
063        }
064    
065    
066        public void beforeValue( ID id, V value )
067        {
068            throw new UnsupportedOperationException( UNSUPPORTED_MSG );
069        }
070    
071    
072        public void afterValue( ID id, V value )
073        {
074            throw new UnsupportedOperationException( UNSUPPORTED_MSG );
075        }
076    
077    
078        public void before( IndexEntry<V, ServerEntry, ID> element ) throws Exception
079        {
080            throw new UnsupportedOperationException( UNSUPPORTED_MSG );
081        }
082    
083    
084        public void after( IndexEntry<V, ServerEntry, ID> element ) throws Exception
085        {
086            throw new UnsupportedOperationException( UNSUPPORTED_MSG );
087        }
088    
089    
090        public void beforeFirst() throws Exception
091        {
092            checkNotClosed( "beforeFirst()" );
093            wrapped.beforeFirst();
094            available = false;
095        }
096    
097    
098        public void afterLast() throws Exception
099        {
100            checkNotClosed( "afterLast()" );
101            wrapped.afterLast();
102            available = false;
103        }
104    
105    
106        public boolean first() throws Exception
107        {
108            beforeFirst();
109            return next();
110        }
111    
112    
113        public boolean last() throws Exception
114        {
115            afterLast();
116            return previous();
117        }
118    
119    
120        public boolean previous() throws Exception
121        {
122            while ( wrapped.previous() )
123            {
124                checkNotClosed( "previous()" );
125    
126                IndexEntry<?, ServerEntry, ID> candidate = wrapped.get();
127                if ( matches( candidate ) )
128                {
129                    return available = true;
130                }
131            }
132    
133            return available = false;
134        }
135    
136    
137        public boolean next() throws Exception
138        {
139            while ( wrapped.next() )
140            {
141                checkNotClosed( "next()" );
142                IndexEntry<?, ServerEntry, ID> candidate = wrapped.get();
143                if ( matches( candidate ) )
144                {
145                    return available = true;
146                }
147            }
148    
149            return available = false;
150        }
151    
152    
153        public IndexEntry<V, ServerEntry, ID> get() throws Exception
154        {
155            checkNotClosed( "get()" );
156            if ( available )
157            {
158                return wrapped.get();
159            }
160    
161            throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
162        }
163    
164    
165        public boolean isElementReused()
166        {
167            return wrapped.isElementReused();
168        }
169    
170    
171        public void close() throws Exception
172        {
173            super.close();
174            wrapped.close();
175        }
176    
177    
178        /**
179         * TODO - duplicate code from AndEvaluator just make utility for this and
180         * for the same code in the OrEvaluator once done.
181         *
182         * Takes a set of Evaluators and copies then sorts them in a new list with
183         * increasing scan counts on their expression nodes.  This is done to have
184         * the Evaluators with the least scan count which have the highest
185         * probability of rejecting a candidate first.  That will increase the
186         * chance of shorting the checks on evaluators early so extra lookups and
187         * comparisons are avoided.
188         *
189         * @param unoptimized the unoptimized list of Evaluators
190         * @return optimized Evaluator list with increasing scan count ordering
191         */
192        private List<Evaluator<? extends ExprNode, ServerEntry, ID>> optimize(
193            List<Evaluator<? extends ExprNode, ServerEntry, ID>> unoptimized )
194        {
195            List<Evaluator<? extends ExprNode, ServerEntry, ID>> optimized = new ArrayList<Evaluator<? extends ExprNode, ServerEntry, ID>>(
196                unoptimized.size() );
197            optimized.addAll( unoptimized );
198    
199            Collections.sort( optimized, new Comparator<Evaluator<?, ServerEntry, ID>>()
200            {
201                public int compare( Evaluator<?, ServerEntry, ID> e1, Evaluator<?, ServerEntry, ID> e2 )
202                {
203                    long scanCount1 = ( Long ) e1.getExpression().get( "count" );
204                    long scanCount2 = ( Long ) e2.getExpression().get( "count" );
205    
206                    if ( scanCount1 == scanCount2 )
207                    {
208                        return 0;
209                    }
210    
211                    /*
212                     * We want the Evaluator with the smallest scan count first
213                     * since this node has the highest probability of failing, or
214                     * rather the least probability of succeeding.  That way we
215                     * can short the sub-expression evaluation process.
216                     */
217                    if ( scanCount1 < scanCount2 )
218                    {
219                        return -1;
220                    }
221    
222                    return 1;
223                }
224            } );
225    
226            return optimized;
227        }
228    
229    
230        private boolean matches( IndexEntry<?, ServerEntry, ID> indexEntry ) throws Exception
231        {
232            for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators )
233            {
234                if ( !evaluator.evaluate( indexEntry ) )
235                {
236                    return false;
237                }
238            }
239    
240            return true;
241        }
242    }