NearSpansOrdered.cs

Go to the documentation of this file.

/* 
 * 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 System.Collections.Generic;
using IndexReader = Lucene.Net.Index.IndexReader;

namespace Lucene.Net.Search.Spans
{
    
    /// <summary>A Spans that is formed from the ordered subspans of a SpanNearQuery
    /// where the subspans do not overlap and have a maximum slop between them.
    /// <p/>
    /// The formed spans only contains minimum slop matches.<br/>
    /// The matching slop is computed from the distance(s) between
    /// the non overlapping matching Spans.<br/>
    /// Successive matches are always formed from the successive Spans
    /// of the SpanNearQuery.
    /// <p/>
    /// The formed spans may contain overlaps when the slop is at least 1.
    /// For example, when querying using
    /// <c>t1 t2 t3</c>
    /// with slop at least 1, the fragment:
    /// <c>t1 t2 t1 t3 t2 t3</c>
    /// matches twice:
    /// <c>t1 t2 .. t3      </c>
    /// <c>      t1 .. t2 t3</c>
    /// 
    /// 
    /// Expert:
    /// Only public for subclassing.  Most implementations should not need this class
    /// </summary>
    public class NearSpansOrdered:Spans
    {
        internal class AnonymousClassComparator : System.Collections.IComparer
        {
            public AnonymousClassComparator(NearSpansOrdered enclosingInstance)
            {
                InitBlock(enclosingInstance);
            }
            private void  InitBlock(NearSpansOrdered enclosingInstance)
            {
                this.enclosingInstance = enclosingInstance;
            }
            private NearSpansOrdered enclosingInstance;
            public NearSpansOrdered Enclosing_Instance
            {
                get
                {
                    return enclosingInstance;
                }
                
            }
            public virtual int Compare(System.Object o1, System.Object o2)
            {
                return ((Spans) o1).Doc() - ((Spans) o2).Doc();
            }
        }
        private void  InitBlock()
        {
            spanDocComparator = new AnonymousClassComparator(this);
        }
        private int allowedSlop;
        private bool firstTime = true;
        private bool more = false;
        
        /// <summary>The spans in the same order as the SpanNearQuery </summary>
        private Spans[] subSpans;
        
        /// <summary>Indicates that all subSpans have same doc() </summary>
        private bool inSameDoc = false;
        
        private int matchDoc = - 1;
        private int matchStart = - 1;
        private int matchEnd = - 1;
        private System.Collections.Generic.List<byte[]> matchPayload;
        
        private Spans[] subSpansByDoc;
        private System.Collections.IComparer spanDocComparator;
        
        private SpanNearQuery query;
        private bool collectPayloads = true;
        
        public NearSpansOrdered(SpanNearQuery spanNearQuery, IndexReader reader):this(spanNearQuery, reader, true)
        {
        }
        
        public NearSpansOrdered(SpanNearQuery spanNearQuery, IndexReader reader, bool collectPayloads)
        {
            InitBlock();
            if (spanNearQuery.GetClauses().Length < 2)
            {
                throw new System.ArgumentException("Less than 2 clauses: " + spanNearQuery);
            }
            this.collectPayloads = collectPayloads;
            allowedSlop = spanNearQuery.Slop;
            SpanQuery[] clauses = spanNearQuery.GetClauses();
            subSpans = new Spans[clauses.Length];
            matchPayload = new System.Collections.Generic.List<byte[]>();
            subSpansByDoc = new Spans[clauses.Length];
            for (int i = 0; i < clauses.Length; i++)
            {
                subSpans[i] = clauses[i].GetSpans(reader);
                subSpansByDoc[i] = subSpans[i]; // used in toSameDoc()
            }
            query = spanNearQuery; // kept for toString() only.
        }
        
        // inherit javadocs
        public override int Doc()
        {
            return matchDoc;
        }
        
        // inherit javadocs
        public override int Start()
        {
            return matchStart;
        }
        
        // inherit javadocs
        public override int End()
        {
            return matchEnd;
        }
        
        public virtual Spans[] GetSubSpans()
        {
            return subSpans;
        }
        
        // TODO: Remove warning after API has been finalized
        // TODO: Would be nice to be able to lazy load payloads

        public override ICollection<byte[]> GetPayload()
        {
            return matchPayload;
        }

        // TODO: Remove warning after API has been finalized

        public override bool IsPayloadAvailable()
        {
            return (matchPayload.Count == 0) == false;
        }

        // inherit javadocs
        public override bool Next()
        {
            if (firstTime)
            {
                firstTime = false;
                for (int i = 0; i < subSpans.Length; i++)
                {
                    if (!subSpans[i].Next())
                    {
                        more = false;
                        return false;
                    }
                }
                more = true;
            }
            if (collectPayloads)
            {
                matchPayload.Clear();
            }
            return AdvanceAfterOrdered();
        }
        
        // inherit javadocs
        public override bool SkipTo(int target)
        {
            if (firstTime)
            {
                firstTime = false;
                for (int i = 0; i < subSpans.Length; i++)
                {
                    if (!subSpans[i].SkipTo(target))
                    {
                        more = false;
                        return false;
                    }
                }
                more = true;
            }
            else if (more && (subSpans[0].Doc() < target))
            {
                if (subSpans[0].SkipTo(target))
                {
                    inSameDoc = false;
                }
                else
                {
                    more = false;
                    return false;
                }
            }
            if (collectPayloads)
            {
                matchPayload.Clear();
            }
            return AdvanceAfterOrdered();
        }
        
        /// <summary>Advances the subSpans to just after an ordered match with a minimum slop
        /// that is smaller than the slop allowed by the SpanNearQuery.
        /// </summary>
        /// <returns> true iff there is such a match.
        /// </returns>
        private bool AdvanceAfterOrdered()
        {
            while (more && (inSameDoc || ToSameDoc()))
            {
                if (StretchToOrder() && ShrinkToAfterShortestMatch())
                {
                    return true;
                }
            }
            return false; // no more matches
        }
        
        
        /// <summary>Advance the subSpans to the same document </summary>
        private bool ToSameDoc()
        {
            System.Array.Sort(subSpansByDoc, spanDocComparator);
            int firstIndex = 0;
            int maxDoc = subSpansByDoc[subSpansByDoc.Length - 1].Doc();
            while (subSpansByDoc[firstIndex].Doc() != maxDoc)
            {
                if (!subSpansByDoc[firstIndex].SkipTo(maxDoc))
                {
                    more = false;
                    inSameDoc = false;
                    return false;
                }
                maxDoc = subSpansByDoc[firstIndex].Doc();
                if (++firstIndex == subSpansByDoc.Length)
                {
                    firstIndex = 0;
                }
            }
            for (int i = 0; i < subSpansByDoc.Length; i++)
            {
                System.Diagnostics.Debug.Assert((subSpansByDoc [i].Doc() == maxDoc)
                    , "NearSpansOrdered.toSameDoc() spans " + subSpansByDoc [0] 
                    + "\n at doc " + subSpansByDoc [i].Doc() 
                    + ", but should be at " + maxDoc);
            }
            inSameDoc = true;
            return true;
        }
        
        /// <summary>Check whether two Spans in the same document are ordered.</summary>
        /// <param name="spans1">
        /// </param>
        /// <param name="spans2">
        /// </param>
        /// <returns> true iff spans1 starts before spans2
        /// or the spans start at the same position,
        /// and spans1 ends before spans2.
        /// </returns>
        internal static bool DocSpansOrdered(Spans spans1, Spans spans2)
        {
            System.Diagnostics.Debug.Assert(spans1.Doc() == spans2.Doc(), "doc1 " + spans1.Doc() + " != doc2 " + spans2.Doc());
            int start1 = spans1.Start();
            int start2 = spans2.Start();
            /* Do not call docSpansOrdered(int,int,int,int) to avoid invoking .end() : */
            return (start1 == start2)?(spans1.End() < spans2.End()):(start1 < start2);
        }
        
        /// <summary>Like <see cref="DocSpansOrdered(Spans,Spans)" />, but use the spans
        /// starts and ends as parameters.
        /// </summary>
        private static bool DocSpansOrdered(int start1, int end1, int start2, int end2)
        {
            return (start1 == start2)?(end1 < end2):(start1 < start2);
        }
        
        /// <summary>Order the subSpans within the same document by advancing all later spans
        /// after the previous one.
        /// </summary>
        private bool StretchToOrder()
        {
            matchDoc = subSpans[0].Doc();
            for (int i = 1; inSameDoc && (i < subSpans.Length); i++)
            {
                while (!DocSpansOrdered(subSpans[i - 1], subSpans[i]))
                {
                    if (!subSpans[i].Next())
                    {
                        inSameDoc = false;
                        more = false;
                        break;
                    }
                    else if (matchDoc != subSpans[i].Doc())
                    {
                        inSameDoc = false;
                        break;
                    }
                }
            }
            return inSameDoc;
        }
        
        /// <summary>The subSpans are ordered in the same doc, so there is a possible match.
        /// Compute the slop while making the match as short as possible by advancing
        /// all subSpans except the last one in reverse order.
        /// </summary>
        private bool ShrinkToAfterShortestMatch()
        {
            matchStart = subSpans[subSpans.Length - 1].Start();
            matchEnd = subSpans[subSpans.Length - 1].End();
            System.Collections.Generic.Dictionary<byte[], byte[]> possibleMatchPayloads = new System.Collections.Generic.Dictionary<byte[], byte[]>();
            if (subSpans[subSpans.Length - 1].IsPayloadAvailable())
            {
                System.Collections.Generic.ICollection<byte[]> payload = subSpans[subSpans.Length - 1].GetPayload();
                foreach(byte[] pl in payload)
                {
                    if (!possibleMatchPayloads.ContainsKey(pl))
                    {
                        possibleMatchPayloads.Add(pl, pl);
                    }
                }
            }
            
            System.Collections.Generic.List<byte[]> possiblePayload = null;
            
            int matchSlop = 0;
            int lastStart = matchStart;
            int lastEnd = matchEnd;
            for (int i = subSpans.Length - 2; i >= 0; i--)
            {
                Spans prevSpans = subSpans[i];
                if (collectPayloads && prevSpans.IsPayloadAvailable())
                {
                    System.Collections.Generic.ICollection<byte[]> payload = prevSpans.GetPayload();
                    possiblePayload = new System.Collections.Generic.List<byte[]>(payload.Count);
                    possiblePayload.AddRange(payload);
                }
                
                int prevStart = prevSpans.Start();
                int prevEnd = prevSpans.End();
                while (true)
                {
                    // Advance prevSpans until after (lastStart, lastEnd)
                    if (!prevSpans.Next())
                    {
                        inSameDoc = false;
                        more = false;
                        break; // Check remaining subSpans for final match.
                    }
                    else if (matchDoc != prevSpans.Doc())
                    {
                        inSameDoc = false; // The last subSpans is not advanced here.
                        break; // Check remaining subSpans for last match in this document.
                    }
                    else
                    {
                        int ppStart = prevSpans.Start();
                        int ppEnd = prevSpans.End(); // Cannot avoid invoking .end()
                        if (!DocSpansOrdered(ppStart, ppEnd, lastStart, lastEnd))
                        {
                            break; // Check remaining subSpans.
                        }
                        else
                        {
                            // prevSpans still before (lastStart, lastEnd)
                            prevStart = ppStart;
                            prevEnd = ppEnd;
                            if (collectPayloads && prevSpans.IsPayloadAvailable())
                            {
                                System.Collections.Generic.ICollection<byte[]> payload = prevSpans.GetPayload();
                                possiblePayload = new System.Collections.Generic.List<byte[]>(payload.Count);
                                possiblePayload.AddRange(payload);
                            }
                        }
                    }
                }
                
                if (collectPayloads && possiblePayload != null)
                {
                    foreach (byte[] pl in possiblePayload)
                    {
                        if (!possibleMatchPayloads.ContainsKey(pl))
                        {
                            possibleMatchPayloads.Add(pl, pl);
                        }
                    }
                }
                
                System.Diagnostics.Debug.Assert(prevStart <= matchStart);
                if (matchStart > prevEnd)
                {
                    // Only non overlapping spans add to slop.
                    matchSlop += (matchStart - prevEnd);
                }
                
                /* Do not break on (matchSlop > allowedSlop) here to make sure
                * that subSpans[0] is advanced after the match, if any.
                */
                matchStart = prevStart;
                lastStart = prevStart;
                lastEnd = prevEnd;
            }
            
            bool match = matchSlop <= allowedSlop;
            
            if (collectPayloads && match && possibleMatchPayloads.Count > 0)
            {
                matchPayload.AddRange(possibleMatchPayloads.Keys);
            }
            
            return match; // ordered and allowed slop
        }
        
        public override System.String ToString()
        {
            return GetType().FullName + "(" + query.ToString() + ")@" + (firstTime?"START":(more?(Doc() + ":" + Start() + "-" + End()):"END"));
        }
    }
}