NearSpansUnordered.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 System.Linq;
using Lucene.Net.Util;
using IndexReader = Lucene.Net.Index.IndexReader;

namespace Lucene.Net.Search.Spans
{
    
    /// <summary> Similar to <see cref="NearSpansOrdered" />, but for the unordered case.
    /// 
    /// Expert:
    /// Only public for subclassing.  Most implementations should not need this class
    /// </summary>
    public class NearSpansUnordered : Spans
    {
        private SpanNearQuery query;
        
        private System.Collections.Generic.IList<SpansCell> ordered = new System.Collections.Generic.List<SpansCell>(); // spans in query order
        private Spans[] subSpans;
        private int slop; // from query
        
        private SpansCell first; // linked list of spans
        private SpansCell last; // sorted by doc only
        
        private int totalLength; // sum of current lengths
        
        private CellQueue queue; // sorted queue of spans
        private SpansCell max; // max element in queue
        
        private bool more = true; // true iff not done
        private bool firstTime = true; // true before first next()
        
        private class CellQueue : PriorityQueue<SpansCell>
        {
            private void  InitBlock(NearSpansUnordered enclosingInstance)
            {
                this.enclosingInstance = enclosingInstance;
            }
            private NearSpansUnordered enclosingInstance;
            public NearSpansUnordered Enclosing_Instance
            {
                get
                {
                    return enclosingInstance;
                }
                
            }
            public CellQueue(NearSpansUnordered enclosingInstance, int size)
            {
                InitBlock(enclosingInstance);
                Initialize(size);
            }

            public override bool LessThan(SpansCell spans1, SpansCell spans2)
            {
                if (spans1.Doc() == spans2.Doc())
                {
                    return NearSpansOrdered.DocSpansOrdered(spans1, spans2);
                }
                else
                {
                    return spans1.Doc() < spans2.Doc();
                }
            }
        }
        
        
        /// <summary>Wraps a Spans, and can be used to form a linked list. </summary>
        private class SpansCell:Spans
        {
            private void  InitBlock(NearSpansUnordered enclosingInstance)
            {
                this.enclosingInstance = enclosingInstance;
            }
            private NearSpansUnordered enclosingInstance;
            public NearSpansUnordered Enclosing_Instance
            {
                get
                {
                    return enclosingInstance;
                }
                
            }
            internal /*private*/ Spans spans;
            internal /*private*/ SpansCell next;
            private int length = - 1;
            private int index;
            
            public SpansCell(NearSpansUnordered enclosingInstance, Spans spans, int index)
            {
                InitBlock(enclosingInstance);
                this.spans = spans;
                this.index = index;
            }
            
            public override bool Next()
            {
                return Adjust(spans.Next());
            }
            
            public override bool SkipTo(int target)
            {
                return Adjust(spans.SkipTo(target));
            }
            
            private bool Adjust(bool condition)
            {
                if (length != - 1)
                {
                    Enclosing_Instance.totalLength -= length; // subtract old length
                }
                if (condition)
                {
                    length = End() - Start();
                    Enclosing_Instance.totalLength += length; // add new length
                    
                    if (Enclosing_Instance.max == null || Doc() > Enclosing_Instance.max.Doc() || (Doc() == Enclosing_Instance.max.Doc()) && (End() > Enclosing_Instance.max.End()))
                    {
                        Enclosing_Instance.max = this;
                    }
                }
                Enclosing_Instance.more = condition;
                return condition;
            }
            
            public override int Doc()
            {
                return spans.Doc();
            }
            public override int Start()
            {
                return spans.Start();
            }
            public override int End()
            {
                return spans.End();
            }
            // TODO: Remove warning after API has been finalized

            public override ICollection<byte[]> GetPayload()
            {
                return spans.GetPayload().ToArray();
            }

            // TODO: Remove warning after API has been finalized

            public override bool IsPayloadAvailable()
            {
                return spans.IsPayloadAvailable();
            }

            public override System.String ToString()
            {
                return spans.ToString() + "#" + index;
            }
        }
        
        
        public NearSpansUnordered(SpanNearQuery query, IndexReader reader)
        {
            this.query = query;
            this.slop = query.Slop;
            
            SpanQuery[] clauses = query.GetClauses();
            queue = new CellQueue(this, clauses.Length);
            subSpans = new Spans[clauses.Length];
            for (int i = 0; i < clauses.Length; i++)
            {
                SpansCell cell = new SpansCell(this, clauses[i].GetSpans(reader), i);
                ordered.Add(cell);
                subSpans[i] = cell.spans;
            }
        }
        public virtual Spans[] GetSubSpans()
        {
            return subSpans;
        }
        public override bool Next()
        {
            if (firstTime)
            {
                InitList(true);
                ListToQueue(); // initialize queue
                firstTime = false;
            }
            else if (more)
            {
                if (Min().Next())
                {
                    // trigger further scanning
                    queue.UpdateTop(); // maintain queue
                }
                else
                {
                    more = false;
                }
            }
            
            while (more)
            {
                
                bool queueStale = false;
                
                if (Min().Doc() != max.Doc())
                {
                    // maintain list
                    QueueToList();
                    queueStale = true;
                }
                
                // skip to doc w/ all clauses
                
                while (more && first.Doc() < last.Doc())
                {
                    more = first.SkipTo(last.Doc()); // skip first upto last
                    FirstToLast(); // and move it to the end
                    queueStale = true;
                }
                
                if (!more)
                    return false;
                
                // found doc w/ all clauses
                
                if (queueStale)
                {
                    // maintain the queue
                    ListToQueue();
                    queueStale = false;
                }
                
                if (AtMatch())
                {
                    return true;
                }
                
                more = Min().Next();
                if (more)
                {
                    queue.UpdateTop(); // maintain queue
                }
            }
            return false; // no more matches
        }
        
        public override bool SkipTo(int target)
        {
            if (firstTime)
            {
                // initialize
                InitList(false);
                for (SpansCell cell = first; more && cell != null; cell = cell.next)
                {
                    more = cell.SkipTo(target); // skip all
                }
                if (more)
                {
                    ListToQueue();
                }
                firstTime = false;
            }
            else
            {
                // normal case
                while (more && Min().Doc() < target)
                {
                    // skip as needed
                    if (Min().SkipTo(target))
                    {
                        queue.UpdateTop();
                    }
                    else
                    {
                        more = false;
                    }
                }
            }
            return more && (AtMatch() || Next());
        }
        
        private SpansCell Min()
        {
            return queue.Top();
        }
        
        public override int Doc()
        {
            return Min().Doc();
        }
        public override int Start()
        {
            return Min().Start();
        }
        public override int End()
        {
            return max.End();
        }
        
        // TODO: Remove warning after API has been finalized

        /// <summary> WARNING: The List is not necessarily in order of the the positions</summary>
        /// <returns> Collection of &amp;lt;c&amp;gt;byte[]&amp;lt;/c&amp;gt; payloads </returns>
        /// <throws>  IOException </throws>
        public override ICollection<byte[]> GetPayload()
        {
            System.Collections.Generic.ISet<byte[]> matchPayload = Lucene.Net.Support.Compatibility.SetFactory.CreateHashSet<byte[]>();
            for (SpansCell cell = first; cell != null; cell = cell.next)
            {
                if (cell.IsPayloadAvailable())
                {
                    matchPayload.UnionWith(cell.GetPayload());
                }
            }
            return matchPayload;
        }

        // TODO: Remove warning after API has been finalized

        public override bool IsPayloadAvailable()
        {
            SpansCell pointer = Min();
            while (pointer != null)
            {
                if (pointer.IsPayloadAvailable())
                {
                    return true;
                }
                pointer = pointer.next;
            }

            return false;
        }

        public override System.String ToString()
        {
            return GetType().FullName + "(" + query.ToString() + ")@" + (firstTime?"START":(more?(Doc() + ":" + Start() + "-" + End()):"END"));
        }
        
        private void  InitList(bool next)
        {
            for (int i = 0; more && i < ordered.Count; i++)
            {
                SpansCell cell = ordered[i];
                if (next)
                    more = cell.Next(); // move to first entry
                if (more)
                {
                    AddToList(cell); // add to list
                }
            }
        }
        
        private void  AddToList(SpansCell cell)
        {
            if (last != null)
            {
                // add next to end of list
                last.next = cell;
            }
            else
                first = cell;
            last = cell;
            cell.next = null;
        }
        
        private void  FirstToLast()
        {
            last.next = first; // move first to end of list
            last = first;
            first = first.next;
            last.next = null;
        }
        
        private void  QueueToList()
        {
            last = first = null;
            while (queue.Top() != null)
            {
                AddToList(queue.Pop());
            }
        }
        
        private void  ListToQueue()
        {
            queue.Clear(); // rebuild queue
            for (SpansCell cell = first; cell != null; cell = cell.next)
            {
                queue.Add(cell); // add to queue from list
            }
        }
        
        private bool AtMatch()
        {
            return (Min().Doc() == max.Doc()) && ((max.End() - Min().Start() - totalLength) <= slop);
        }
    }
}