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 org.apache.directory.shared.ldap.entry.ServerEntry;
024    import org.apache.directory.shared.ldap.filter.OrNode;
025    import org.apache.directory.shared.ldap.filter.ExprNode;
026    import org.apache.directory.server.xdbm.IndexEntry;
027    import org.apache.directory.server.xdbm.search.Evaluator;
028    
029    import java.util.List;
030    import java.util.ArrayList;
031    import java.util.Collections;
032    import java.util.Comparator;
033    
034    
035    /**
036     * An Evaluator for logical disjunction (OR) expressions.
037     *
038     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
039     * @version $$Rev$$
040     */
041    public class OrEvaluator<ID> implements Evaluator<OrNode, ServerEntry, ID>
042    {
043        private final List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators;
044    
045        private final OrNode node;
046    
047    
048        public OrEvaluator( OrNode node, List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators )
049        {
050            this.node = node;
051            this.evaluators = optimize( evaluators );
052        }
053    
054    
055        /**
056         * Takes a set of Evaluators and copies then sorts them in a new list with
057         * decreasing scan counts on their expression nodes.  This is done to have
058         * the Evaluators with the greatest scan counts which have the highest
059         * probability of accepting a candidate first.  That will increase the
060         * chance of shorting the checks on evaluators early so extra lookups and
061         * comparisons are avoided.
062         *
063         * @param unoptimized the unoptimized list of Evaluators
064         * @return optimized Evaluator list with decreasing scan count ordering
065         */
066        private List<Evaluator<? extends ExprNode, ServerEntry, ID>> optimize(
067            List<Evaluator<? extends ExprNode, ServerEntry, ID>> unoptimized )
068        {
069            List<Evaluator<? extends ExprNode, ServerEntry, ID>> optimized = new ArrayList<Evaluator<? extends ExprNode, ServerEntry, ID>>(
070                unoptimized.size() );
071            optimized.addAll( unoptimized );
072            Collections.sort( optimized, new Comparator<Evaluator<? extends ExprNode, ServerEntry, ID>>()
073            {
074                public int compare( Evaluator<? extends ExprNode, ServerEntry, ID> e1,
075                    Evaluator<? extends ExprNode, ServerEntry, ID> e2 )
076                {
077                    long scanCount1 = ( Long ) e1.getExpression().get( "count" );
078                    long scanCount2 = ( Long ) e2.getExpression().get( "count" );
079    
080                    if ( scanCount1 == scanCount2 )
081                    {
082                        return 0;
083                    }
084    
085                    /*
086                     * We want the Evaluator with the largest scan count first
087                     * since this node has the highest probability of accepting,
088                     * or rather the least probability of failing.  That way we
089                     * can short the sub-expression evaluation process.
090                     */
091                    if ( scanCount1 < scanCount2 )
092                    {
093                        return 1;
094                    }
095    
096                    return -1;
097                }
098            } );
099    
100            return optimized;
101        }
102    
103    
104        public boolean evaluate( IndexEntry<?, ServerEntry, ID> indexEntry ) throws Exception
105        {
106            for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators )
107            {
108                if ( evaluator.evaluate( indexEntry ) )
109                {
110                    return true;
111                }
112            }
113    
114            return false;
115        }
116    
117    
118        public boolean evaluateId( ID id ) throws Exception
119        {
120            for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators )
121            {
122                if ( evaluator.evaluateId( id ) )
123                {
124                    return true;
125                }
126            }
127    
128            return false;
129        }
130    
131    
132        public boolean evaluateEntry( ServerEntry entry ) throws Exception
133        {
134            for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators )
135            {
136                if ( evaluator.evaluateEntry( entry ) )
137                {
138                    return true;
139                }
140            }
141    
142            return false;
143        }
144    
145    
146        public OrNode getExpression()
147        {
148            return node;
149        }
150    }