content: package org.apache.lucene.search;
  
  /**
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to You under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  import org.apache.lucene.index.IndexReader;
  import org.apache.lucene.index.Term;
  import org.apache.lucene.util.ToStringUtils;
  import org.apache.lucene.search.BooleanClause.Occur;
  
  import java.io.IOException;
  import java.util.*;
  
  /** A Query that matches documents matching boolean combinations of other
    * queries, e.g. {@link TermQuery}s, {@link PhraseQuery}s or other
    * BooleanQuerys.
    */
  public class BooleanQuery extends Query implements Iterable<BooleanClause> {
  
    private static int maxClauseCount = 1024;
  
    /** Thrown when an attempt is made to add more than {@link
     * #getMaxClauseCount()} clauses. This typically happens if
     * a PrefixQuery, FuzzyQuery, WildcardQuery, or TermRangeQuery 
     * is expanded to many terms during search. 
     */
    public static class TooManyClauses extends RuntimeException {
      public TooManyClauses() {
        super("maxClauseCount is set to " + maxClauseCount);
      }
    }
  
    /** Return the maximum number of clauses permitted, 1024 by default.
     * Attempts to add more than the permitted number of clauses cause {@link
     * TooManyClauses} to be thrown.
     * @see #setMaxClauseCount(int)
     */
    public static int getMaxClauseCount() { return maxClauseCount; }
  
    /** 
     * Set the maximum number of clauses permitted per BooleanQuery.
     * Default value is 1024.
     */
    public static void setMaxClauseCount(int maxClauseCount) {
      if (maxClauseCount < 1)
        throw new IllegalArgumentException("maxClauseCount must be >= 1");
      BooleanQuery.maxClauseCount = maxClauseCount;
    }
  
    private ArrayList<BooleanClause> clauses = new ArrayList<BooleanClause>();
    private final boolean disableCoord;
  
    /** Constructs an empty boolean query. */
    public BooleanQuery() {
      disableCoord = false;
    }
  
    /** Constructs an empty boolean query.
     *
     * {@link Similarity#coord(int,int)} may be disabled in scoring, as
     * appropriate. For example, this score factor does not make sense for most
     * automatically generated queries, like {@link WildcardQuery} and {@link
     * FuzzyQuery}.
     *
     * @param disableCoord disables {@link Similarity#coord(int,int)} in scoring.
     */
    public BooleanQuery(boolean disableCoord) {
      this.disableCoord = disableCoord;
    }
  
    /** Returns true iff {@link Similarity#coord(int,int)} is disabled in
     * scoring for this query instance.
     * @see #BooleanQuery(boolean)
     */
    public boolean isCoordDisabled() { return disableCoord; }
  
    /**
     * Specifies a minimum number of the optional BooleanClauses
     * which must be satisfied.
     *
     * <p>
     * By default no optional clauses are necessary for a match
     * (unless there are no required clauses).  If this method is used,
     * then the specified number of clauses is required.
     * </p>
     * <p>
     * Use of this method is totally independent of specifying that
     * any specific clauses are required (or prohibited).  This number will
     * only be compared against the number of matching optional clauses.
     * </p>
     *
     * @param min the number of optional clauses that must match
     */
    public void setMinimumNumberShouldMatch(int min) {
      this.minNrShouldMatch = min;
    }
    protected int minNrShouldMatch = 0;
  
    /**
     * Gets the minimum number of the optional BooleanClauses
     * which must be satisfied.
     */
    public int getMinimumNumberShouldMatch() {
      return minNrShouldMatch;
    }
  
    /** Adds a clause to a boolean query.
     *
     * @throws TooManyClauses if the new number of clauses exceeds the maximum clause number
     * @see #getMaxClauseCount()
     */
    public void add(Query query, BooleanClause.Occur occur) {
      add(new BooleanClause(query, occur));
    }
  
    /** Adds a clause to a boolean query.
     * @throws TooManyClauses if the new number of clauses exceeds the maximum clause number
     * @see #getMaxClauseCount()
     */
    public void add(BooleanClause clause) {
      if (clauses.size() >= maxClauseCount)
        throw new TooManyClauses();
  
      clauses.add(clause);
    }
  
    /** Returns the set of clauses in this query. */
    public BooleanClause[] getClauses() {
      return clauses.toArray(new BooleanClause[clauses.size()]);
    }
  
    /** Returns the list of clauses in this query. */
    public List<BooleanClause> clauses() { return clauses; }
  
    /** Returns an iterator on the clauses in this query. It implements the {@link Iterable} interface to
     * make it possible to do:
     * <pre>for (BooleanClause clause : booleanQuery) {}</pre>
     */
    public final Iterator<BooleanClause> iterator() { return clauses().iterator(); }
  
    /**
     * Expert: the Weight for BooleanQuery, used to
     * normalize, score and explain these queries.
     *
     * <p>NOTE: this API and implementation is subject to
     * change suddenly in the next release.</p>
     */
    protected class BooleanWeight extends Weight {
      /** The Similarity implementation. */
      protected Similarity similarity;
      protected ArrayList<Weight> weights;
      protected int maxCoord;  // num optional + num required
      private final boolean disableCoord;
  
      public BooleanWeight(Searcher searcher, boolean disableCoord)
        throws IOException {
        this.similarity = getSimilarity(searcher);
        this.disableCoord = disableCoord;
        weights = new ArrayList<Weight>(clauses.size());
        for (int i = 0 ; i < clauses.size(); i++) {
          BooleanClause c = clauses.get(i);
          weights.add(c.getQuery().createWeight(searcher));
          if (!c.isProhibited()) maxCoord++;
        }
      }
  
      @Override
      public Query getQuery() { return BooleanQuery.this; }
  
      @Override
      public float getValue() { return getBoost(); }
  
      @Override
      public float sumOfSquaredWeights() throws IOException {
        float sum = 0.0f;
        for (int i = 0 ; i < weights.size(); i++) {
          // call sumOfSquaredWeights for all clauses in case of side effects
          float s = weights.get(i).sumOfSquaredWeights();         // sum sub weights
          if (!clauses.get(i).isProhibited())
            // only add to sum for non-prohibited clauses
            sum += s;
        }
  
        sum *= getBoost() * getBoost();             // boost each sub-weight
  
        return sum ;
      }
  
  
      @Override
      public void normalize(float norm) {
        norm *= getBoost();                         // incorporate boost
        for (Weight w : weights) {
          // normalize all clauses, (even if prohibited in case of side affects)
          w.normalize(norm);
        }
      }
  
      @Override
      public Explanation explain(IndexReader reader, int doc)
        throws IOException {
        final int minShouldMatch =
          BooleanQuery.this.getMinimumNumberShouldMatch();
        ComplexExplanation sumExpl = new ComplexExplanation();
        sumExpl.setDescription("sum of:");
        int coord = 0;
        float sum = 0.0f;
        boolean fail = false;
        int shouldMatchCount = 0;
        Iterator<BooleanClause> cIter = clauses.iterator();
        for (Iterator<Weight> wIter = weights.iterator(); wIter.hasNext();) {
          Weight w = wIter.next();
          BooleanClause c = cIter.next();
          if (w.scorer(reader, true, true) == null) {
            if (c.isRequired()) {
              fail = true;
              Explanation r = new Explanation(0.0f, "no match on required clause (" + c.getQuery().toString() + ")");
              sumExpl.addDetail(r);
            }
            continue;
          }
          Explanation e = w.explain(reader, doc);
          if (e.isMatch()) {
            if (!c.isProhibited()) {
              sumExpl.addDetail(e);
              sum += e.getValue();
              coord++;
            } else {
              Explanation r =
                new Explanation(0.0f, "match on prohibited clause (" + c.getQuery().toString() + ")");
              r.addDetail(e);
              sumExpl.addDetail(r);
              fail = true;
            }
            if (c.getOccur() == Occur.SHOULD)
              shouldMatchCount++;
          } else if (c.isRequired()) {
            Explanation r = new Explanation(0.0f, "no match on required clause (" + c.getQuery().toString() + ")");
            r.addDetail(e);
            sumExpl.addDetail(r);
            fail = true;
          }
        }
        if (fail) {
          sumExpl.setMatch(Boolean.FALSE);
          sumExpl.setValue(0.0f);
          sumExpl.setDescription
            ("Failure to meet condition(s) of required/prohibited clause(s)");
          return sumExpl;
        } else if (shouldMatchCount < minShouldMatch) {
          sumExpl.setMatch(Boolean.FALSE);
          sumExpl.setValue(0.0f);
          sumExpl.setDescription("Failure to match minimum number "+
                                 "of optional clauses: " + minShouldMatch);
          return sumExpl;
        }
        
        sumExpl.setMatch(0 < coord ? Boolean.TRUE : Boolean.FALSE);
        sumExpl.setValue(sum);
        
        final float coordFactor = disableCoord ? 1.0f : similarity.coord(coord, maxCoord);
        if (coordFactor == 1.0f) {
          return sumExpl;                             // eliminate wrapper
        } else {
          ComplexExplanation result = new ComplexExplanation(sumExpl.isMatch(),
                                                             sum*coordFactor,
                                                             "product of:");
          result.addDetail(sumExpl);
          result.addDetail(new Explanation(coordFactor,
                                           "coord("+coord+"/"+maxCoord+")"));
          return result;
        }
      }
  
      @Override
      public Scorer scorer(IndexReader reader, boolean scoreDocsInOrder, boolean topScorer)
          throws IOException {
        List<Scorer> required = new ArrayList<Scorer>();
        List<Scorer> prohibited = new ArrayList<Scorer>();
        List<Scorer> optional = new ArrayList<Scorer>();
        Iterator<BooleanClause> cIter = clauses.iterator();
        for (Weight w  : weights) {
          BooleanClause c =  cIter.next();
          Scorer subScorer = w.scorer(reader, true, false);
          if (subScorer == null) {
            if (c.isRequired()) {
              return null;
            }
          } else if (c.isRequired()) {
            required.add(subScorer);
          } else if (c.isProhibited()) {
            prohibited.add(subScorer);
          } else {
            optional.add(subScorer);
          }
        }
        
        // Check if we can return a BooleanScorer
        if (!scoreDocsInOrder && topScorer && required.size() == 0) {
          return new BooleanScorer(this, disableCoord, similarity, minNrShouldMatch, optional, prohibited, maxCoord);
        }
        
        if (required.size() == 0 && optional.size() == 0) {
          // no required and optional clauses.
          return null;
        } else if (optional.size() < minNrShouldMatch) {
          // either >1 req scorer, or there are 0 req scorers and at least 1
          // optional scorer. Therefore if there are not enough optional scorers
          // no documents will be matched by the query
          return null;
        }
        
        // Return a BooleanScorer2
        return new BooleanScorer2(this, disableCoord, similarity, minNrShouldMatch, required, prohibited, optional, maxCoord);
      }
      
      @Override
      public boolean scoresDocsOutOfOrder() {
        for (BooleanClause c : clauses) {
          if (c.isRequired()) {
            return false; // BS2 (in-order) will be used by scorer()
          }
        }
        
        // scorer() will return an out-of-order scorer if requested.
        return true;
      }
      
    }
  
    @Override
    public Weight createWeight(Searcher searcher) throws IOException {
      return new BooleanWeight(searcher, disableCoord);
    }
  
    @Override
    public Query rewrite(IndexReader reader) throws IOException {
      if (minNrShouldMatch == 0 && clauses.size() == 1) {                    // optimize 1-clause queries
        BooleanClause c = clauses.get(0);
        if (!c.isProhibited()) {			  // just return clause
  
          Query query = c.getQuery().rewrite(reader);    // rewrite first
  
          if (getBoost() != 1.0f) {                 // incorporate boost
            if (query == c.getQuery())                   // if rewrite was no-op
              query = (Query)query.clone();         // then clone before boost
            query.setBoost(getBoost() * query.getBoost());
          }
  
          return query;
        }
      }
  
      BooleanQuery clone = null;                    // recursively rewrite
      for (int i = 0 ; i < clauses.size(); i++) {
        BooleanClause c = clauses.get(i);
        Query query = c.getQuery().rewrite(reader);
        if (query != c.getQuery()) {                     // clause rewrote: must clone
          if (clone == null)
            clone = (BooleanQuery)this.clone();
          clone.clauses.set(i, new BooleanClause(query, c.getOccur()));
        }
      }
      if (clone != null) {
        return clone;                               // some clauses rewrote
      } else
        return this;                                // no clauses rewrote
    }
  
    // inherit javadoc
    @Override
    public void extractTerms(Set<Term> terms) {
        for (BooleanClause clause : clauses) {
            clause.getQuery().extractTerms(terms);
          }
    }
  
    @Override @SuppressWarnings("unchecked")
    public Object clone() {
      BooleanQuery clone = (BooleanQuery)super.clone();
      clone.clauses = (ArrayList<BooleanClause>) this.clauses.clone();
      return clone;
    }
  
    /** Prints a user-readable version of this query. */
    @Override
    public String toString(String field) {
      StringBuilder buffer = new StringBuilder();
      boolean needParens=(getBoost() != 1.0) || (getMinimumNumberShouldMatch()>0) ;
      if (needParens) {
        buffer.append("(");
      }
  
      for (int i = 0 ; i < clauses.size(); i++) {
        BooleanClause c = clauses.get(i);
        if (c.isProhibited())
          buffer.append("-");
        else if (c.isRequired())
          buffer.append("+");
  
        Query subQuery = c.getQuery();
        if (subQuery != null) {
          if (subQuery instanceof BooleanQuery) {	  // wrap sub-bools in parens
            buffer.append("(");
            buffer.append(subQuery.toString(field));
            buffer.append(")");
          } else {
            buffer.append(subQuery.toString(field));
          }
        } else {
          buffer.append("null");
        }
  
        if (i != clauses.size()-1)
          buffer.append(" ");
      }
  
      if (needParens) {
        buffer.append(")");
      }
  
      if (getMinimumNumberShouldMatch()>0) {
        buffer.append('~');
        buffer.append(getMinimumNumberShouldMatch());
      }
  
      if (getBoost() != 1.0f)
      {
        buffer.append(ToStringUtils.boost(getBoost()));
      }
  
      return buffer.toString();
    }
  
    /** Returns true iff <code>o</code> is equal to this. */
    @Override
    public boolean equals(Object o) {
      if (!(o instanceof BooleanQuery))
        return false;
      BooleanQuery other = (BooleanQuery)o;
      return (this.getBoost() == other.getBoost())
          && this.clauses.equals(other.clauses)
          && this.getMinimumNumberShouldMatch() == other.getMinimumNumberShouldMatch()
          && this.disableCoord == other.disableCoord;
    }
  
    /** Returns a hash code value for this object.*/
    @Override
    public int hashCode() {
      return Float.floatToIntBits(getBoost()) ^ clauses.hashCode()
        + getMinimumNumberShouldMatch() + (disableCoord ? 17:0);
    }
    
  }
  