/* 
 * 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.
 */

using System;

using IndexReader = Lucene.Net.Index.IndexReader;

namespace Lucene.Net.Search
{
	
	/* Description from Doug Cutting (excerpted from
	* LUCENE-1483):
	*
	* BooleanScorer uses a ~16k array to score windows of
	* docs. So it scores docs 0-16k first, then docs 16-32k,
	* etc. For each window it iterates through all query terms
	* and accumulates a score in table[doc%16k]. It also stores
	* in the table a bitmask representing which terms
	* contributed to the score. Non-zero scores are chained in
	* a linked list. At the end of scoring each window it then
	* iterates through the linked list and, if the bitmask
	* matches the boolean constraints, collects a hit. For
	* boolean queries with lots of frequent terms this can be
	* much faster, since it does not need to update a priority
	* queue for each posting, instead performing constant-time
	* operations per posting. The only downside is that it
	* results in hits being delivered out-of-order within the
	* window, which means it cannot be nested within other
	* scorers. But it works well as a top-level scorer.
	*
	* The new BooleanScorer2 implementation instead works by
	* merging priority queues of postings, albeit with some
	* clever tricks. For example, a pure conjunction (all terms
	* required) does not require a priority queue. Instead it
	* sorts the posting streams at the start, then repeatedly
	* skips the first to to the last. If the first ever equals
	* the last, then there's a hit. When some terms are
	* required and some terms are optional, the conjunction can
	* be evaluated first, then the optional terms can all skip
	* to the match and be added to the score. Thus the
	* conjunction can reduce the number of priority queue
	* updates for the optional terms. */
	
	public sealed class BooleanScorer:Scorer
	{
		private void  InitBlock()
		{
			bucketTable = new BucketTable();
		}
		
		private sealed class BooleanScorerCollector:Collector
		{
			private BucketTable bucketTable;
			private int mask;
			private Scorer scorer;
			
			public BooleanScorerCollector(int mask, BucketTable bucketTable)
			{
				this.mask = mask;
				this.bucketTable = bucketTable;
			}
			public override void  Collect(int doc)
			{
				BucketTable table = bucketTable;
				int i = doc & Lucene.Net.Search.BooleanScorer.BucketTable.MASK;
				Bucket bucket = table.buckets[i];
				if (bucket == null)
					table.buckets[i] = bucket = new Bucket();
				
				if (bucket.doc != doc)
				{
					// invalid bucket
					bucket.doc = doc; // set doc
					bucket.score = scorer.Score(); // initialize score
					bucket.bits = mask; // initialize mask
					bucket.coord = 1; // initialize coord
					
					bucket.next = table.first; // push onto valid list
					table.first = bucket;
				}
				else
				{
					// valid bucket
					bucket.score += scorer.Score(); // increment score
					bucket.bits |= mask; // add bits in mask
					bucket.coord++; // increment coord
				}
			}
			
			public override void  SetNextReader(IndexReader reader, int docBase)
			{
				// not needed by this implementation
			}
			
			public override void  SetScorer(Scorer scorer)
			{
				this.scorer = scorer;
			}

		    public override bool AcceptsDocsOutOfOrder
		    {
		        get { return true; }
		    }
		}
		
		// An internal class which is used in score(Collector, int) for setting the
		// current score. This is required since Collector exposes a setScorer method
		// and implementations that need the score will call scorer.score().
		// Therefore the only methods that are implemented are score() and doc().
		private sealed class BucketScorer:Scorer
		{
			
			internal float score;
			internal int doc = NO_MORE_DOCS;
			
			public BucketScorer():base(null)
			{
			}
			
			public override int Advance(int target)
			{
				return NO_MORE_DOCS;
			}
			
			public override int DocID()
			{
				return doc;
			}
			
			public override int NextDoc()
			{
				return NO_MORE_DOCS;
			}
			
			public override float Score()
			{
				return score;
			}
		}
		
		internal sealed class Bucket
		{
			internal int doc = - 1; // tells if bucket is valid
			internal float score; // incremental score
			internal int bits; // used for bool constraints
			internal int coord; // count of terms in score
			internal Bucket next; // next valid bucket
		}
		
		/// <summary>A simple hash table of document scores within a range. </summary>
		internal sealed class BucketTable
		{
			private void  InitBlock()
			{
				buckets = new Bucket[SIZE];
			}
			public const int SIZE = 1 << 11;
			public static readonly int MASK;
			
			internal Bucket[] buckets;
			internal Bucket first = null; // head of valid list
			
			public BucketTable()
			{
                InitBlock();
			}
			
			public Collector NewCollector(int mask)
			{
				return new BooleanScorerCollector(mask, this);
			}
			
			public int Size()
			{
				return SIZE;
			}
			static BucketTable()
			{
				MASK = SIZE - 1;
			}
		}
		
		internal sealed class SubScorer
		{
			public Scorer scorer;
			public bool required = false;
			public bool prohibited = false;
			public Collector collector;
			public SubScorer next;
			
			public SubScorer(Scorer scorer, bool required, bool prohibited, Collector collector, SubScorer next)
			{
				this.scorer = scorer;
				this.required = required;
				this.prohibited = prohibited;
				this.collector = collector;
				this.next = next;
			}
		}
		
		private SubScorer scorers = null;
		private BucketTable bucketTable;
		private int maxCoord = 1;
		private float[] coordFactors;
		private int requiredMask = 0;
		private int prohibitedMask = 0;
		private int nextMask = 1;
		private int minNrShouldMatch;
		private int end;
		private Bucket current;
		private int doc = - 1;
		
		public /*internal*/ BooleanScorer(Similarity similarity, int minNrShouldMatch,
            System.Collections.Generic.List<Scorer> optionalScorers, System.Collections.Generic.List<Scorer> prohibitedScorers)
            : base(similarity)
		{
			InitBlock();
			this.minNrShouldMatch = minNrShouldMatch;
			
			if (optionalScorers != null && optionalScorers.Count > 0)
			{
				foreach (Scorer scorer in optionalScorers)
				{
					maxCoord++;
					if (scorer.NextDoc() != NO_MORE_DOCS)
					{
						scorers = new SubScorer(scorer, false, false, bucketTable.NewCollector(0), scorers);
					}
				}
			}
			
			if (prohibitedScorers != null && prohibitedScorers.Count > 0)
			{
				foreach(Scorer scorer in prohibitedScorers)
				{
					int mask = nextMask;
					nextMask = nextMask << 1;
					prohibitedMask |= mask; // update prohibited mask
					if (scorer.NextDoc() != NO_MORE_DOCS)
					{
						scorers = new SubScorer(scorer, false, true, bucketTable.NewCollector(mask), scorers);
					}
				}
			}
			
			coordFactors = new float[maxCoord];
			Similarity sim = Similarity;
			for (int i = 0; i < maxCoord; i++)
			{
				coordFactors[i] = sim.Coord(i, maxCoord - 1);
			}
		}
		
		// firstDocID is ignored since nextDoc() initializes 'current'
		public /*protected internal*/ override bool Score(Collector collector, int max, int firstDocID)
		{
			bool more;
			Bucket tmp;
			BucketScorer bs = new BucketScorer();
			// The internal loop will set the score and doc before calling collect.
			collector.SetScorer(bs);
			do 
			{
				bucketTable.first = null;
				
				while (current != null)
				{
					// more queued 
					
					// check prohibited & required
					if ((current.bits & prohibitedMask) == 0 && (current.bits & requiredMask) == requiredMask)
					{
						
						if (current.doc >= max)
						{
							tmp = current;
							current = current.next;
							tmp.next = bucketTable.first;
							bucketTable.first = tmp;
							continue;
						}
						
						if (current.coord >= minNrShouldMatch)
						{
							bs.score = current.score * coordFactors[current.coord];
							bs.doc = current.doc;
							collector.Collect(current.doc);
						}
					}
					
					current = current.next; // pop the queue
				}
				
				if (bucketTable.first != null)
				{
					current = bucketTable.first;
					bucketTable.first = current.next;
					return true;
				}
				
				// refill the queue
				more = false;
				end += BucketTable.SIZE;
				for (SubScorer sub = scorers; sub != null; sub = sub.next)
				{
					int subScorerDocID = sub.scorer.DocID();
					if (subScorerDocID != NO_MORE_DOCS)
					{
						more |= sub.scorer.Score(sub.collector, end, subScorerDocID);
					}
				}
				current = bucketTable.first;
			}
			while (current != null || more);
			
			return false;
		}
		
		public override int Advance(int target)
		{
			throw new System.NotSupportedException();
		}
		
		public override int DocID()
		{
			return doc;
		}

		public override int NextDoc()
		{
			bool more;
			do 
			{
				while (bucketTable.first != null)
				{
					// more queued
					current = bucketTable.first;
					bucketTable.first = current.next; // pop the queue
					
					// check prohibited & required, and minNrShouldMatch
					if ((current.bits & prohibitedMask) == 0 && (current.bits & requiredMask) == requiredMask && current.coord >= minNrShouldMatch)
					{
						return doc = current.doc;
					}
				}
				
				// refill the queue
				more = false;
				end += BucketTable.SIZE;
				for (SubScorer sub = scorers; sub != null; sub = sub.next)
				{
					Scorer scorer = sub.scorer;
					sub.collector.SetScorer(scorer);
					int doc = scorer.DocID();
					while (doc < end)
					{
						sub.collector.Collect(doc);
						doc = scorer.NextDoc();
					}
					more |= (doc != NO_MORE_DOCS);
				}
			}
			while (bucketTable.first != null || more);
			
			return this.doc = NO_MORE_DOCS;
		}
		
		public override float Score()
		{
			return current.score * coordFactors[current.coord];
		}
		
		public override void  Score(Collector collector)
		{
			Score(collector, System.Int32.MaxValue, NextDoc());
		}
		
		public override System.String ToString()
		{
			System.Text.StringBuilder buffer = new System.Text.StringBuilder();
			buffer.Append("boolean(");
			for (SubScorer sub = scorers; sub != null; sub = sub.next)
			{
				buffer.Append(sub.scorer.ToString());
				buffer.Append(" ");
			}
			buffer.Append(")");
			return buffer.ToString();
		}
	}
}