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 */
020package org.apache.directory.server.xdbm.search.evaluator;
021
022
023import java.util.ArrayList;
024import java.util.Collections;
025import java.util.List;
026
027import org.apache.directory.api.ldap.model.entry.Entry;
028import org.apache.directory.api.ldap.model.exception.LdapException;
029import org.apache.directory.api.ldap.model.filter.ExprNode;
030import org.apache.directory.api.ldap.model.filter.OrNode;
031import org.apache.directory.server.core.api.partition.PartitionTxn;
032import org.apache.directory.server.xdbm.IndexEntry;
033import org.apache.directory.server.xdbm.search.Evaluator;
034import org.apache.directory.server.xdbm.search.impl.ScanCountComparator;
035
036
037/**
038 * An Evaluator for logical disjunction (OR) expressions.
039 *
040 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
041 */
042public class OrEvaluator implements Evaluator<OrNode>
043{
044    /** The list of evaluators associated with each of the children */
045    private final List<Evaluator<? extends ExprNode>> evaluators;
046
047    /** The OrNode */
048    private final OrNode node;
049
050
051    /**
052     * Creates a new OrEvaluator
053     * 
054     * @param node The OrNode
055     * @param evaluators The inner evaluators
056     */
057    public OrEvaluator( OrNode node, List<Evaluator<? extends ExprNode>> evaluators )
058    {
059        this.node = node;
060        this.evaluators = optimize( evaluators );
061    }
062
063
064    /**
065     * Takes a set of Evaluators and copies then sorts them in a new list with
066     * decreasing scan counts on their expression nodes.  This is done to have
067     * the Evaluators with the greatest scan counts which have the highest
068     * probability of accepting a candidate first.  That will increase the
069     * chance of shorting the checks on evaluators early so extra lookups and
070     * comparisons are avoided.
071     *
072     * @param unoptimized the unoptimized list of Evaluators
073     * @return optimized Evaluator list with decreasing scan count ordering
074     */
075    private List<Evaluator<? extends ExprNode>> optimize(
076        List<Evaluator<? extends ExprNode>> unoptimized )
077    {
078        List<Evaluator<? extends ExprNode>> optimized = new ArrayList<>(
079            unoptimized.size() );
080        optimized.addAll( unoptimized );
081
082        Collections.sort( optimized, new ScanCountComparator() );
083
084        return optimized;
085    }
086
087
088    /**
089     * {@inheritDoc}
090     */
091    @Override
092    public boolean evaluate( PartitionTxn partitionTxn, IndexEntry<?, String> indexEntry ) throws LdapException
093    {
094        for ( Evaluator<?> evaluator : evaluators )
095        {
096            if ( evaluator.evaluate( partitionTxn, indexEntry ) )
097            {
098                return true;
099            }
100        }
101
102        return false;
103    }
104
105
106    /**
107     * {@inheritDoc}
108     */
109    @Override
110    public boolean evaluate( Entry entry ) throws LdapException
111    {
112        for ( Evaluator<?> evaluator : evaluators )
113        {
114            if ( evaluator.evaluate( entry ) )
115            {
116                return true;
117            }
118        }
119
120        return false;
121    }
122
123
124    /**
125     * {@inheritDoc}
126     */
127    @Override
128    public OrNode getExpression()
129    {
130        return node;
131    }
132
133
134    /**
135     * Dumps the evaluators
136     */
137    private String dumpEvaluators( String tabs )
138    {
139        StringBuilder sb = new StringBuilder();
140
141        for ( Evaluator<? extends ExprNode> evaluator : evaluators )
142        {
143            sb.append( evaluator.toString( tabs + "  " ) );
144        }
145
146        return sb.toString();
147    }
148
149
150    /**
151     * @see Object#toString()
152     */
153    public String toString( String tabs )
154    {
155        StringBuilder sb = new StringBuilder();
156
157        sb.append( tabs ).append( "OrEvaluator : " ).append( node ).append( "\n" );
158
159        if ( ( evaluators != null ) && !evaluators.isEmpty() )
160        {
161            sb.append( dumpEvaluators( tabs ) );
162        }
163
164        return sb.toString();
165    }
166
167
168    /**
169     * @see Object#toString()
170     */
171    public String toString()
172    {
173        return toString( "" );
174    }
175}