lucene/highlighter/src/java/org/apache/lucene/search/vectorhighlight/FieldQuery.java - lucene-solr - Git at Google

 /*
  * 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.
  */
 package org.apache.lucene.search.vectorhighlight;
 import java.io.IOException;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;

 import org.apache.lucene.index.IndexReader;
 import org.apache.lucene.index.Term;
 import org.apache.lucene.queries.function.FunctionScoreQuery;
 import org.apache.lucene.search.BooleanClause;
 import org.apache.lucene.search.BooleanQuery;
 import org.apache.lucene.search.BoostQuery;
 import org.apache.lucene.search.ConstantScoreQuery;
 import org.apache.lucene.search.DisjunctionMaxQuery;
 import org.apache.lucene.search.MultiTermQuery;
 import org.apache.lucene.search.PhraseQuery;
 import org.apache.lucene.search.Query;
 import org.apache.lucene.search.SynonymQuery;
 import org.apache.lucene.search.TermQuery;
 import org.apache.lucene.search.vectorhighlight.FieldTermStack.TermInfo;

 /**
  * FieldQuery breaks down query object into terms/phrases and keeps
  * them in a QueryPhraseMap structure.
  */
 public class FieldQuery {

   final boolean fieldMatch;

   // fieldMatch==true,  Map<fieldName,QueryPhraseMap>
   // fieldMatch==false, Map<null,QueryPhraseMap>
   Map<String, QueryPhraseMap> rootMaps = new HashMap<>();

   // fieldMatch==true,  Map<fieldName,setOfTermsInQueries>
   // fieldMatch==false, Map<null,setOfTermsInQueries>
   Map<String, Set<String>> termSetMap = new HashMap<>();

   int termOrPhraseNumber; // used for colored tag support

   // The maximum number of different matching terms accumulated from any one MultiTermQuery
   private static final int MAX_MTQ_TERMS = 1024;

   public FieldQuery(Query query, IndexReader reader, boolean phraseHighlight, boolean fieldMatch) throws IOException {
     this.fieldMatch = fieldMatch;
     Set<Query> flatQueries = new LinkedHashSet<>();
     flatten( query, reader, flatQueries, 1f );
     saveTerms( flatQueries, reader );
     Collection<Query> expandQueries = expand( flatQueries );

     for( Query flatQuery : expandQueries ){
       QueryPhraseMap rootMap = getRootMap( flatQuery );
       rootMap.add( flatQuery, reader );
       float boost = 1f;
       while (flatQuery instanceof BoostQuery) {
         BoostQuery bq = (BoostQuery) flatQuery;
         flatQuery = bq.getQuery();
         boost *= bq.getBoost();
       }
       if( !phraseHighlight && flatQuery instanceof PhraseQuery ){
         PhraseQuery pq = (PhraseQuery)flatQuery;
         if( pq.getTerms().length > 1 ){
           for( Term term : pq.getTerms() )
             rootMap.addTerm( term, boost );
         }
       }
     }
   }

   /** For backwards compatibility you can initialize FieldQuery without
    * an IndexReader, which is only required to support MultiTermQuery
    */
   FieldQuery( Query query, boolean phraseHighlight, boolean fieldMatch ) throws IOException {
     this (query, null, phraseHighlight, fieldMatch);
   }

   protected void flatten( Query sourceQuery, IndexReader reader, Collection<Query> flatQueries, float boost ) throws IOException {
     while (sourceQuery instanceof BoostQuery) {
       BoostQuery bq = (BoostQuery) sourceQuery;
       sourceQuery = bq.getQuery();
       boost *= bq.getBoost();
     }
     if( sourceQuery instanceof BooleanQuery ){
       BooleanQuery bq = (BooleanQuery)sourceQuery;
       for( BooleanClause clause : bq ) {
         if( !clause.isProhibited() ) {
           flatten( clause.getQuery(), reader, flatQueries, boost );
         }
       }
     } else if( sourceQuery instanceof DisjunctionMaxQuery ){
       DisjunctionMaxQuery dmq = (DisjunctionMaxQuery)sourceQuery;
       for( Query query : dmq ){
         flatten( query, reader, flatQueries, boost );
       }
     }
     else if( sourceQuery instanceof TermQuery ){
       if (boost != 1f) {
         sourceQuery = new BoostQuery(sourceQuery, boost);
       }
       if( !flatQueries.contains( sourceQuery ) )
         flatQueries.add( sourceQuery );
     }
     else if ( sourceQuery instanceof SynonymQuery ){
       SynonymQuery synQuery = (SynonymQuery) sourceQuery;
       for( Term term : synQuery.getTerms()) {
         flatten( new TermQuery(term), reader, flatQueries, boost);
       }
     }
     else if( sourceQuery instanceof PhraseQuery ){
       PhraseQuery pq = (PhraseQuery)sourceQuery;
       if( pq.getTerms().length == 1 )
         sourceQuery = new TermQuery( pq.getTerms()[0] );
       if (boost != 1f) {
         sourceQuery = new BoostQuery(sourceQuery, boost);
       }
       flatQueries.add(sourceQuery);
     } else if (sourceQuery instanceof ConstantScoreQuery) {
       final Query q = ((ConstantScoreQuery) sourceQuery).getQuery();
       if (q != null) {
         flatten( q, reader, flatQueries, boost);
       }
     } else if (sourceQuery instanceof FunctionScoreQuery) {
       final Query q = ((FunctionScoreQuery) sourceQuery).getWrappedQuery();
       if (q != null) {
         flatten(q, reader, flatQueries, boost);
       }
     } else if (reader != null) {
       Query query = sourceQuery;
       Query rewritten;
       if (sourceQuery instanceof MultiTermQuery) {
         rewritten = new MultiTermQuery.TopTermsScoringBooleanQueryRewrite(MAX_MTQ_TERMS).rewrite(reader, (MultiTermQuery) query);
       } else {
         rewritten = query.rewrite(reader);
       }
       if (rewritten != query) {
         // only rewrite once and then flatten again - the rewritten query could have a speacial treatment
         // if this method is overwritten in a subclass.
         flatten(rewritten, reader, flatQueries, boost);

       }
       // if the query is already rewritten we discard it
     }
     // else discard queries
   }

   /*
    * Create expandQueries from flatQueries.
    *
    * expandQueries := flatQueries + overlapped phrase queries
    *
    * ex1) flatQueries={a,b,c}
    *      => expandQueries={a,b,c}
    * ex2) flatQueries={a,"b c","c d"}
    *      => expandQueries={a,"b c","c d","b c d"}
    */
   Collection<Query> expand( Collection<Query> flatQueries ){
     Set<Query> expandQueries = new LinkedHashSet<>();
     for( Iterator<Query> i = flatQueries.iterator(); i.hasNext(); ){
       Query query = i.next();
       i.remove();
       expandQueries.add( query );
       float queryBoost = 1f;
       while (query instanceof BoostQuery) {
         BoostQuery bq = (BoostQuery) query;
         queryBoost *= bq.getBoost();
         query = bq.getQuery();
       }
       if( !( query instanceof PhraseQuery ) ) continue;
       for( Iterator<Query> j = flatQueries.iterator(); j.hasNext(); ){
         Query qj = j.next();
         float qjBoost = 1f;
         while (qj instanceof BoostQuery) {
           BoostQuery bq = (BoostQuery) qj;
           qjBoost *= bq.getBoost();
           qj = bq.getQuery();
         }
         if( !( qj instanceof PhraseQuery ) ) continue;
         checkOverlap( expandQueries, (PhraseQuery)query, queryBoost, (PhraseQuery)qj, qjBoost );
       }
     }
     return expandQueries;
   }

   /*
    * Check if PhraseQuery A and B have overlapped part.
    *
    * ex1) A="a b", B="b c" => overlap; expandQueries={"a b c"}
    * ex2) A="b c", B="a b" => overlap; expandQueries={"a b c"}
    * ex3) A="a b", B="c d" => no overlap; expandQueries={}
    */
   private void checkOverlap( Collection<Query> expandQueries, PhraseQuery a, float aBoost, PhraseQuery b, float bBoost ){
     if( a.getSlop() != b.getSlop() ) return;
     Term[] ats = a.getTerms();
     Term[] bts = b.getTerms();
     if( fieldMatch && !ats[0].field().equals( bts[0].field() ) ) return;
     checkOverlap( expandQueries, ats, bts, a.getSlop(), aBoost);
     checkOverlap( expandQueries, bts, ats, b.getSlop(), bBoost );
   }

   /*
    * Check if src and dest have overlapped part and if it is, create PhraseQueries and add expandQueries.
    *
    * ex1) src="a b", dest="c d"       => no overlap
    * ex2) src="a b", dest="a b c"     => no overlap
    * ex3) src="a b", dest="b c"       => overlap; expandQueries={"a b c"}
    * ex4) src="a b c", dest="b c d"   => overlap; expandQueries={"a b c d"}
    * ex5) src="a b c", dest="b c"     => no overlap
    * ex6) src="a b c", dest="b"       => no overlap
    * ex7) src="a a a a", dest="a a a" => overlap;
    *                                     expandQueries={"a a a a a","a a a a a a"}
    * ex8) src="a b c d", dest="b c"   => no overlap
    */
   private void checkOverlap( Collection<Query> expandQueries, Term[] src, Term[] dest, int slop, float boost ){
     // beginning from 1 (not 0) is safe because that the PhraseQuery has multiple terms
     // is guaranteed in flatten() method (if PhraseQuery has only one term, flatten()
     // converts PhraseQuery to TermQuery)
     for( int i = 1; i < src.length; i++ ){
       boolean overlap = true;
       for( int j = i; j < src.length; j++ ){
         if( ( j - i ) < dest.length && !src[j].text().equals( dest[j-i].text() ) ){
           overlap = false;
           break;
         }
       }
       if( overlap && src.length - i < dest.length ){
         PhraseQuery.Builder pqBuilder = new PhraseQuery.Builder();
         for( Term srcTerm : src )
           pqBuilder.add( srcTerm );
         for( int k = src.length - i; k < dest.length; k++ ){
           pqBuilder.add( new Term( src[0].field(), dest[k].text() ) );
         }
         pqBuilder.setSlop( slop );
         Query pq = pqBuilder.build();
         if (boost != 1f) {
           pq = new BoostQuery(pq, 1f);
         }
         if(!expandQueries.contains( pq ) )
           expandQueries.add( pq );
       }
     }
   }

   QueryPhraseMap getRootMap( Query query ){
     String key = getKey( query );
     QueryPhraseMap map = rootMaps.get( key );
     if( map == null ){
       map = new QueryPhraseMap( this );
       rootMaps.put( key, map );
     }
     return map;
   }

   /*
    * Return 'key' string. 'key' is the field name of the Query.
    * If not fieldMatch, 'key' will be null.
    */
   private String getKey( Query query ){
     if( !fieldMatch ) return null;
     while (query instanceof BoostQuery) {
       query = ((BoostQuery) query).getQuery();
     }
     if( query instanceof TermQuery )
       return ((TermQuery)query).getTerm().field();
     else if ( query instanceof PhraseQuery ){
       PhraseQuery pq = (PhraseQuery)query;
       Term[] terms = pq.getTerms();
       return terms[0].field();
     }
     else if (query instanceof MultiTermQuery) {
       return ((MultiTermQuery)query).getField();
     }
     else
       throw new RuntimeException( "query \"" + query.toString() + "\" must be flatten first." );
   }

   /*
    * Save the set of terms in the queries to termSetMap.
    *
    * ex1) q=name:john
    *      - fieldMatch==true
    *          termSetMap=Map<"name",Set<"john">>
    *      - fieldMatch==false
    *          termSetMap=Map<null,Set<"john">>
    *
    * ex2) q=name:john title:manager
    *      - fieldMatch==true
    *          termSetMap=Map<"name",Set<"john">,
    *                         "title",Set<"manager">>
    *      - fieldMatch==false
    *          termSetMap=Map<null,Set<"john","manager">>
    *
    * ex3) q=name:"john lennon"
    *      - fieldMatch==true
    *          termSetMap=Map<"name",Set<"john","lennon">>
    *      - fieldMatch==false
    *          termSetMap=Map<null,Set<"john","lennon">>
    */
   void saveTerms( Collection<Query> flatQueries, IndexReader reader ) throws IOException{
     for( Query query : flatQueries ){
       while (query instanceof BoostQuery) {
         query = ((BoostQuery) query).getQuery();
       }
       Set<String> termSet = getTermSet( query );
       if( query instanceof TermQuery )
         termSet.add( ((TermQuery)query).getTerm().text() );
       else if( query instanceof PhraseQuery ){
         for( Term term : ((PhraseQuery)query).getTerms() )
           termSet.add( term.text() );
       }
       else if (query instanceof MultiTermQuery && reader != null) {
         BooleanQuery mtqTerms = (BooleanQuery) query.rewrite(reader);
         for (BooleanClause clause : mtqTerms) {
           termSet.add (((TermQuery) clause.getQuery()).getTerm().text());
         }
       }
       else
         throw new RuntimeException( "query \"" + query.toString() + "\" must be flatten first." );
     }
   }

   private Set<String> getTermSet( Query query ){
     String key = getKey( query );
     Set<String> set = termSetMap.get( key );
     if( set == null ){
       set = new HashSet<>();
       termSetMap.put( key, set );
     }
     return set;
   }

   Set<String> getTermSet( String field ){
     return termSetMap.get( fieldMatch ? field : null );
   }

   /**
    *
    * @return QueryPhraseMap
    */
   public QueryPhraseMap getFieldTermMap( String fieldName, String term ){
     QueryPhraseMap rootMap = getRootMap( fieldName );
     return rootMap == null ? null : rootMap.subMap.get( term );
   }

   /**
    *
    * @return QueryPhraseMap
    */
   public QueryPhraseMap searchPhrase( String fieldName, final List<TermInfo> phraseCandidate ){
     QueryPhraseMap root = getRootMap( fieldName );
     if( root == null ) return null;
     return root.searchPhrase( phraseCandidate );
   }

   private QueryPhraseMap getRootMap( String fieldName ){
     return rootMaps.get( fieldMatch ? fieldName : null );
   }

   int nextTermOrPhraseNumber(){
     return termOrPhraseNumber++;
   }

   /**
    * Internal structure of a query for highlighting: represents
    * a nested query structure
    */
   public static class QueryPhraseMap {

     boolean terminal;
     int slop;   // valid if terminal == true and phraseHighlight == true
     float boost;  // valid if terminal == true
     int termOrPhraseNumber;   // valid if terminal == true
     FieldQuery fieldQuery;
     Map<String, QueryPhraseMap> subMap = new HashMap<>();

     public QueryPhraseMap( FieldQuery fieldQuery ){
       this.fieldQuery = fieldQuery;
     }

     void addTerm( Term term, float boost ){
       QueryPhraseMap map = getOrNewMap( subMap, term.text() );
       map.markTerminal( boost );
     }

     private QueryPhraseMap getOrNewMap( Map<String, QueryPhraseMap> subMap, String term ){
       QueryPhraseMap map = subMap.get( term );
       if( map == null ){
         map = new QueryPhraseMap( fieldQuery );
         subMap.put( term, map );
       }
       return map;
     }

     void add( Query query, IndexReader reader ) {
       float boost = 1f;
       while (query instanceof BoostQuery) {
         BoostQuery bq = (BoostQuery) query;
         query = bq.getQuery();
         boost = bq.getBoost();
       }
       if( query instanceof TermQuery ){
         addTerm( ((TermQuery)query).getTerm(), boost );
       }
       else if( query instanceof PhraseQuery ){
         PhraseQuery pq = (PhraseQuery)query;
         Term[] terms = pq.getTerms();
         Map<String, QueryPhraseMap> map = subMap;
         QueryPhraseMap qpm = null;
         for( Term term : terms ){
           qpm = getOrNewMap( map, term.text() );
           map = qpm.subMap;
         }
         qpm.markTerminal( pq.getSlop(), boost );
       }
       else
         throw new RuntimeException( "query \"" + query.toString() + "\" must be flatten first." );
     }

     public QueryPhraseMap getTermMap( String term ){
       return subMap.get( term );
     }

     private void markTerminal( float boost ){
       markTerminal( 0, boost );
     }

     private void markTerminal( int slop, float boost ){
       this.terminal = true;
       this.slop = slop;
       this.boost = boost;
       this.termOrPhraseNumber = fieldQuery.nextTermOrPhraseNumber();
     }

     public boolean isTerminal(){
       return terminal;
     }

     public int getSlop(){
       return slop;
     }

     public float getBoost(){
       return boost;
     }

     public int getTermOrPhraseNumber(){
       return termOrPhraseNumber;
     }

     public QueryPhraseMap searchPhrase( final List<TermInfo> phraseCandidate ){
       QueryPhraseMap currMap = this;
       for( TermInfo ti : phraseCandidate ){
         currMap = currMap.subMap.get( ti.getText() );
         if( currMap == null ) return null;
       }
       return currMap.isValidTermOrPhrase( phraseCandidate ) ? currMap : null;
     }

     public boolean isValidTermOrPhrase( final List<TermInfo> phraseCandidate ){
       // check terminal
       if( !terminal ) return false;

       // if the candidate is a term, it is valid
       if( phraseCandidate.size() == 1 ) return true;

       // else check whether the candidate is valid phrase
       // compare position-gaps between terms to slop
       int pos = phraseCandidate.get( 0 ).getPosition();
       for( int i = 1; i < phraseCandidate.size(); i++ ){
         int nextPos = phraseCandidate.get( i ).getPosition();
         if( Math.abs( nextPos - pos - 1 ) > slop ) return false;
         pos = nextPos;
       }
       return true;
     }
   }
 }
	/*
	* 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.
	*/
	package org.apache.lucene.search.vectorhighlight;
	import java.io.IOException;
	import java.util.Collection;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.LinkedHashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;

	import org.apache.lucene.index.IndexReader;
	import org.apache.lucene.index.Term;
	import org.apache.lucene.queries.function.FunctionScoreQuery;
	import org.apache.lucene.search.BooleanClause;
	import org.apache.lucene.search.BooleanQuery;
	import org.apache.lucene.search.BoostQuery;
	import org.apache.lucene.search.ConstantScoreQuery;
	import org.apache.lucene.search.DisjunctionMaxQuery;
	import org.apache.lucene.search.MultiTermQuery;
	import org.apache.lucene.search.PhraseQuery;
	import org.apache.lucene.search.Query;
	import org.apache.lucene.search.SynonymQuery;
	import org.apache.lucene.search.TermQuery;
	import org.apache.lucene.search.vectorhighlight.FieldTermStack.TermInfo;

	/**
	* FieldQuery breaks down query object into terms/phrases and keeps
	* them in a QueryPhraseMap structure.
	*/
	public class FieldQuery {

	final boolean fieldMatch;

	// fieldMatch==true, Map<fieldName,QueryPhraseMap>
	// fieldMatch==false, Map<null,QueryPhraseMap>
	Map<String, QueryPhraseMap> rootMaps = new HashMap<>();

	// fieldMatch==true, Map<fieldName,setOfTermsInQueries>
	// fieldMatch==false, Map<null,setOfTermsInQueries>
	Map<String, Set<String>> termSetMap = new HashMap<>();

	int termOrPhraseNumber; // used for colored tag support

	// The maximum number of different matching terms accumulated from any one MultiTermQuery
	private static final int MAX_MTQ_TERMS = 1024;

	public FieldQuery(Query query, IndexReader reader, boolean phraseHighlight, boolean fieldMatch) throws IOException {
	this.fieldMatch = fieldMatch;
	Set<Query> flatQueries = new LinkedHashSet<>();
	flatten( query, reader, flatQueries, 1f );
	saveTerms( flatQueries, reader );
	Collection<Query> expandQueries = expand( flatQueries );

	for( Query flatQuery : expandQueries ){
	QueryPhraseMap rootMap = getRootMap( flatQuery );
	rootMap.add( flatQuery, reader );
	float boost = 1f;
	while (flatQuery instanceof BoostQuery) {
	BoostQuery bq = (BoostQuery) flatQuery;
	flatQuery = bq.getQuery();
	boost *= bq.getBoost();
	}
	if( !phraseHighlight && flatQuery instanceof PhraseQuery ){
	PhraseQuery pq = (PhraseQuery)flatQuery;
	if( pq.getTerms().length > 1 ){
	for( Term term : pq.getTerms() )
	rootMap.addTerm( term, boost );
	}
	}
	}
	}

	/** For backwards compatibility you can initialize FieldQuery without
	* an IndexReader, which is only required to support MultiTermQuery
	*/
	FieldQuery( Query query, boolean phraseHighlight, boolean fieldMatch ) throws IOException {
	this (query, null, phraseHighlight, fieldMatch);
	}

	protected void flatten( Query sourceQuery, IndexReader reader, Collection<Query> flatQueries, float boost ) throws IOException {
	while (sourceQuery instanceof BoostQuery) {
	BoostQuery bq = (BoostQuery) sourceQuery;
	sourceQuery = bq.getQuery();
	boost *= bq.getBoost();
	}
	if( sourceQuery instanceof BooleanQuery ){
	BooleanQuery bq = (BooleanQuery)sourceQuery;
	for( BooleanClause clause : bq ) {
	if( !clause.isProhibited() ) {
	flatten( clause.getQuery(), reader, flatQueries, boost );
	}
	}
	} else if( sourceQuery instanceof DisjunctionMaxQuery ){
	DisjunctionMaxQuery dmq = (DisjunctionMaxQuery)sourceQuery;
	for( Query query : dmq ){
	flatten( query, reader, flatQueries, boost );
	}
	}
	else if( sourceQuery instanceof TermQuery ){
	if (boost != 1f) {
	sourceQuery = new BoostQuery(sourceQuery, boost);
	}
	if( !flatQueries.contains( sourceQuery ) )
	flatQueries.add( sourceQuery );
	}
	else if ( sourceQuery instanceof SynonymQuery ){
	SynonymQuery synQuery = (SynonymQuery) sourceQuery;
	for( Term term : synQuery.getTerms()) {
	flatten( new TermQuery(term), reader, flatQueries, boost);
	}
	}
	else if( sourceQuery instanceof PhraseQuery ){
	PhraseQuery pq = (PhraseQuery)sourceQuery;
	if( pq.getTerms().length == 1 )
	sourceQuery = new TermQuery( pq.getTerms()[0] );
	if (boost != 1f) {
	sourceQuery = new BoostQuery(sourceQuery, boost);
	}
	flatQueries.add(sourceQuery);
	} else if (sourceQuery instanceof ConstantScoreQuery) {
	final Query q = ((ConstantScoreQuery) sourceQuery).getQuery();
	if (q != null) {
	flatten( q, reader, flatQueries, boost);
	}
	} else if (sourceQuery instanceof FunctionScoreQuery) {
	final Query q = ((FunctionScoreQuery) sourceQuery).getWrappedQuery();
	if (q != null) {
	flatten(q, reader, flatQueries, boost);
	}
	} else if (reader != null) {
	Query query = sourceQuery;
	Query rewritten;
	if (sourceQuery instanceof MultiTermQuery) {
	rewritten = new MultiTermQuery.TopTermsScoringBooleanQueryRewrite(MAX_MTQ_TERMS).rewrite(reader, (MultiTermQuery) query);
	} else {
	rewritten = query.rewrite(reader);
	}
	if (rewritten != query) {
	// only rewrite once and then flatten again - the rewritten query could have a speacial treatment
	// if this method is overwritten in a subclass.
	flatten(rewritten, reader, flatQueries, boost);

	}
	// if the query is already rewritten we discard it
	}
	// else discard queries
	}

	/*
	* Create expandQueries from flatQueries.
	*
	* expandQueries := flatQueries + overlapped phrase queries
	*
	* ex1) flatQueries={a,b,c}
	* => expandQueries={a,b,c}
	* ex2) flatQueries={a,"b c","c d"}
	* => expandQueries={a,"b c","c d","b c d"}
	*/
	Collection<Query> expand( Collection<Query> flatQueries ){
	Set<Query> expandQueries = new LinkedHashSet<>();
	for( Iterator<Query> i = flatQueries.iterator(); i.hasNext(); ){
	Query query = i.next();
	i.remove();
	expandQueries.add( query );
	float queryBoost = 1f;
	while (query instanceof BoostQuery) {
	BoostQuery bq = (BoostQuery) query;
	queryBoost *= bq.getBoost();
	query = bq.getQuery();
	}
	if( !( query instanceof PhraseQuery ) ) continue;
	for( Iterator<Query> j = flatQueries.iterator(); j.hasNext(); ){
	Query qj = j.next();
	float qjBoost = 1f;
	while (qj instanceof BoostQuery) {
	BoostQuery bq = (BoostQuery) qj;
	qjBoost *= bq.getBoost();
	qj = bq.getQuery();
	}
	if( !( qj instanceof PhraseQuery ) ) continue;
	checkOverlap( expandQueries, (PhraseQuery)query, queryBoost, (PhraseQuery)qj, qjBoost );
	}
	}
	return expandQueries;
	}

	/*
	* Check if PhraseQuery A and B have overlapped part.
	*
	* ex1) A="a b", B="b c" => overlap; expandQueries={"a b c"}
	* ex2) A="b c", B="a b" => overlap; expandQueries={"a b c"}
	* ex3) A="a b", B="c d" => no overlap; expandQueries={}
	*/
	private void checkOverlap( Collection<Query> expandQueries, PhraseQuery a, float aBoost, PhraseQuery b, float bBoost ){
	if( a.getSlop() != b.getSlop() ) return;
	Term[] ats = a.getTerms();
	Term[] bts = b.getTerms();
	if( fieldMatch && !ats[0].field().equals( bts[0].field() ) ) return;
	checkOverlap( expandQueries, ats, bts, a.getSlop(), aBoost);
	checkOverlap( expandQueries, bts, ats, b.getSlop(), bBoost );
	}

	/*
	* Check if src and dest have overlapped part and if it is, create PhraseQueries and add expandQueries.
	*
	* ex1) src="a b", dest="c d" => no overlap
	* ex2) src="a b", dest="a b c" => no overlap
	* ex3) src="a b", dest="b c" => overlap; expandQueries={"a b c"}
	* ex4) src="a b c", dest="b c d" => overlap; expandQueries={"a b c d"}
	* ex5) src="a b c", dest="b c" => no overlap
	* ex6) src="a b c", dest="b" => no overlap
	* ex7) src="a a a a", dest="a a a" => overlap;
	* expandQueries={"a a a a a","a a a a a a"}
	* ex8) src="a b c d", dest="b c" => no overlap
	*/
	private void checkOverlap( Collection<Query> expandQueries, Term[] src, Term[] dest, int slop, float boost ){
	// beginning from 1 (not 0) is safe because that the PhraseQuery has multiple terms
	// is guaranteed in flatten() method (if PhraseQuery has only one term, flatten()
	// converts PhraseQuery to TermQuery)
	for( int i = 1; i < src.length; i++ ){
	boolean overlap = true;
	for( int j = i; j < src.length; j++ ){
	if( ( j - i ) < dest.length && !src[j].text().equals( dest[j-i].text() ) ){
	overlap = false;
	break;
	}
	}
	if( overlap && src.length - i < dest.length ){
	PhraseQuery.Builder pqBuilder = new PhraseQuery.Builder();
	for( Term srcTerm : src )
	pqBuilder.add( srcTerm );
	for( int k = src.length - i; k < dest.length; k++ ){
	pqBuilder.add( new Term( src[0].field(), dest[k].text() ) );
	}
	pqBuilder.setSlop( slop );
	Query pq = pqBuilder.build();
	if (boost != 1f) {
	pq = new BoostQuery(pq, 1f);
	}
	if(!expandQueries.contains( pq ) )
	expandQueries.add( pq );
	}
	}
	}

	QueryPhraseMap getRootMap( Query query ){
	String key = getKey( query );
	QueryPhraseMap map = rootMaps.get( key );
	if( map == null ){
	map = new QueryPhraseMap( this );
	rootMaps.put( key, map );
	}
	return map;
	}

	/*
	* Return 'key' string. 'key' is the field name of the Query.
	* If not fieldMatch, 'key' will be null.
	*/
	private String getKey( Query query ){
	if( !fieldMatch ) return null;
	while (query instanceof BoostQuery) {
	query = ((BoostQuery) query).getQuery();
	}
	if( query instanceof TermQuery )
	return ((TermQuery)query).getTerm().field();
	else if ( query instanceof PhraseQuery ){
	PhraseQuery pq = (PhraseQuery)query;
	Term[] terms = pq.getTerms();
	return terms[0].field();
	}
	else if (query instanceof MultiTermQuery) {
	return ((MultiTermQuery)query).getField();
	}
	else
	throw new RuntimeException( "query \"" + query.toString() + "\" must be flatten first." );
	}

	/*
	* Save the set of terms in the queries to termSetMap.
	*
	* ex1) q=name:john
	* - fieldMatch==true
	* termSetMap=Map<"name",Set<"john">>
	* - fieldMatch==false
	* termSetMap=Map<null,Set<"john">>
	*
	* ex2) q=name:john title:manager
	* - fieldMatch==true
	* termSetMap=Map<"name",Set<"john">,
	* "title",Set<"manager">>
	* - fieldMatch==false
	* termSetMap=Map<null,Set<"john","manager">>
	*
	* ex3) q=name:"john lennon"
	* - fieldMatch==true
	* termSetMap=Map<"name",Set<"john","lennon">>
	* - fieldMatch==false
	* termSetMap=Map<null,Set<"john","lennon">>
	*/
	void saveTerms( Collection<Query> flatQueries, IndexReader reader ) throws IOException{
	for( Query query : flatQueries ){
	while (query instanceof BoostQuery) {
	query = ((BoostQuery) query).getQuery();
	}
	Set<String> termSet = getTermSet( query );
	if( query instanceof TermQuery )
	termSet.add( ((TermQuery)query).getTerm().text() );
	else if( query instanceof PhraseQuery ){
	for( Term term : ((PhraseQuery)query).getTerms() )
	termSet.add( term.text() );
	}
	else if (query instanceof MultiTermQuery && reader != null) {
	BooleanQuery mtqTerms = (BooleanQuery) query.rewrite(reader);
	for (BooleanClause clause : mtqTerms) {
	termSet.add (((TermQuery) clause.getQuery()).getTerm().text());
	}
	}
	else
	throw new RuntimeException( "query \"" + query.toString() + "\" must be flatten first." );
	}
	}

	private Set<String> getTermSet( Query query ){
	String key = getKey( query );
	Set<String> set = termSetMap.get( key );
	if( set == null ){
	set = new HashSet<>();
	termSetMap.put( key, set );
	}
	return set;
	}

	Set<String> getTermSet( String field ){
	return termSetMap.get( fieldMatch ? field : null );
	}

	/**
	*
	* @return QueryPhraseMap
	*/
	public QueryPhraseMap getFieldTermMap( String fieldName, String term ){
	QueryPhraseMap rootMap = getRootMap( fieldName );
	return rootMap == null ? null : rootMap.subMap.get( term );
	}

	/**
	*
	* @return QueryPhraseMap
	*/
	public QueryPhraseMap searchPhrase( String fieldName, final List<TermInfo> phraseCandidate ){
	QueryPhraseMap root = getRootMap( fieldName );
	if( root == null ) return null;
	return root.searchPhrase( phraseCandidate );
	}

	private QueryPhraseMap getRootMap( String fieldName ){
	return rootMaps.get( fieldMatch ? fieldName : null );
	}

	int nextTermOrPhraseNumber(){
	return termOrPhraseNumber++;
	}

	/**
	* Internal structure of a query for highlighting: represents
	* a nested query structure
	*/
	public static class QueryPhraseMap {

	boolean terminal;
	int slop; // valid if terminal == true and phraseHighlight == true
	float boost; // valid if terminal == true
	int termOrPhraseNumber; // valid if terminal == true
	FieldQuery fieldQuery;
	Map<String, QueryPhraseMap> subMap = new HashMap<>();

	public QueryPhraseMap( FieldQuery fieldQuery ){
	this.fieldQuery = fieldQuery;
	}

	void addTerm( Term term, float boost ){
	QueryPhraseMap map = getOrNewMap( subMap, term.text() );
	map.markTerminal( boost );
	}

	private QueryPhraseMap getOrNewMap( Map<String, QueryPhraseMap> subMap, String term ){
	QueryPhraseMap map = subMap.get( term );
	if( map == null ){
	map = new QueryPhraseMap( fieldQuery );
	subMap.put( term, map );
	}
	return map;
	}

	void add( Query query, IndexReader reader ) {
	float boost = 1f;
	while (query instanceof BoostQuery) {
	BoostQuery bq = (BoostQuery) query;
	query = bq.getQuery();
	boost = bq.getBoost();
	}
	if( query instanceof TermQuery ){
	addTerm( ((TermQuery)query).getTerm(), boost );
	}
	else if( query instanceof PhraseQuery ){
	PhraseQuery pq = (PhraseQuery)query;
	Term[] terms = pq.getTerms();
	Map<String, QueryPhraseMap> map = subMap;
	QueryPhraseMap qpm = null;
	for( Term term : terms ){
	qpm = getOrNewMap( map, term.text() );
	map = qpm.subMap;
	}
	qpm.markTerminal( pq.getSlop(), boost );
	}
	else
	throw new RuntimeException( "query \"" + query.toString() + "\" must be flatten first." );
	}

	public QueryPhraseMap getTermMap( String term ){
	return subMap.get( term );
	}

	private void markTerminal( float boost ){
	markTerminal( 0, boost );
	}

	private void markTerminal( int slop, float boost ){
	this.terminal = true;
	this.slop = slop;
	this.boost = boost;
	this.termOrPhraseNumber = fieldQuery.nextTermOrPhraseNumber();
	}

	public boolean isTerminal(){
	return terminal;
	}

	public int getSlop(){
	return slop;
	}

	public float getBoost(){
	return boost;
	}

	public int getTermOrPhraseNumber(){
	return termOrPhraseNumber;
	}

	public QueryPhraseMap searchPhrase( final List<TermInfo> phraseCandidate ){
	QueryPhraseMap currMap = this;
	for( TermInfo ti : phraseCandidate ){
	currMap = currMap.subMap.get( ti.getText() );
	if( currMap == null ) return null;
	}
	return currMap.isValidTermOrPhrase( phraseCandidate ) ? currMap : null;
	}

	public boolean isValidTermOrPhrase( final List<TermInfo> phraseCandidate ){
	// check terminal
	if( !terminal ) return false;

	// if the candidate is a term, it is valid
	if( phraseCandidate.size() == 1 ) return true;

	// else check whether the candidate is valid phrase
	// compare position-gaps between terms to slop
	int pos = phraseCandidate.get( 0 ).getPosition();
	for( int i = 1; i < phraseCandidate.size(); i++ ){
	int nextPos = phraseCandidate.get( i ).getPosition();
	if( Math.abs( nextPos - pos - 1 ) > slop ) return false;
	pos = nextPos;
	}
	return true;
	}
	}
	}