/*
* 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
{
/// Similar to , but for the unordered case.
///
/// Expert:
/// Only public for subclassing. Most implementations should not need this class
///
public class NearSpansUnordered : Spans
{
private SpanNearQuery query;
private System.Collections.Generic.IList ordered = new System.Collections.Generic.List(); // 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
{
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();
}
}
}
/// Wraps a Spans, and can be used to form a linked list.
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 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
/// WARNING: The List is not necessarily in order of the the positions
/// Collection of <c>byte[]</c> payloads
/// IOException
public override ICollection GetPayload()
{
System.Collections.Generic.ISet matchPayload = Lucene.Net.Support.Compatibility.SetFactory.CreateHashSet();
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);
}
}
}