You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucenenet.apache.org by ni...@apache.org on 2023/04/14 20:24:03 UTC
[lucenenet] branch master updated: BREAKING: Lucene.Net.Util: Added ValuePriorityQueue to utilize stack allocations where possible (#826)
This is an automated email from the ASF dual-hosted git repository.
nightowl888 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucenenet.git
The following commit(s) were added to refs/heads/master by this push:
new 4b8ef7948 BREAKING: Lucene.Net.Util: Added ValuePriorityQueue<T> to utilize stack allocations where possible (#826)
4b8ef7948 is described below
commit 4b8ef7948e240e1c724d94a18e36bf2dc2903139
Author: Shad Storhaug <sh...@shadstorhaug.com>
AuthorDate: Sat Apr 15 03:23:58 2023 +0700
BREAKING: Lucene.Net.Util: Added ValuePriorityQueue<T> to utilize stack allocations where possible (#826)
* Lucene.Net.Util: Added ValuePriorityQueue ref struct so we can eliminate the per-request PriorityQueue<T> allocation in certain instances.
* BREAKING: Lucene.Net.Facet (FloatTaxonomyFacets + IntTaxonomyFacets + TopOrdAndSingleQueue + TopOrdAndInt32Queue): Converted OrdAndValue<T> into a struct. Modified to stack allocate both the priority queue instance and the buffer that backs it, the latter falling back to using an array pool if the number of bytes to allocate exceeds Constants.MaxStackByteLimit. Closes #774.
* Lucene.Net.Search.TopDocs: Refactored merge to use ValuePriorityQueue and allocate the buffer on the stack if it fits within Constants.MaxStackByteLimit.
* Lucene.Net.Util.Fst: Refactored pack to use ValuePriorityQueue and allocate the buffer on the stack if it fits within Constants.MaxStackByteLimit.
* Lucene.Net.Facet.OrdAndValue<T>: Fixed nullable warnings
* Lucene.Net.Util.ValuePriorityQueue<T>: Refactored the constructor to accept IComparer<T> instead of IPriorityComparer<T>. This will save allocations of adapter classes for IComparer<T>. Replaced IPriorityComparer<T> with an abstract class PriorityComparer<T> that implements IComparer<T> and makes a crude conversion that ignores equal to (0) and assumes either greater than (1) or less than (-1) when LessThan() returns false or true respectively.
---
.../Taxonomy/FloatTaxonomyFacets.cs | 104 ++--
src/Lucene.Net.Facet/Taxonomy/IntTaxonomyFacets.cs | 105 ++--
src/Lucene.Net.Facet/TopOrdAndFloatQueue.cs | 55 +-
src/Lucene.Net.Facet/TopOrdAndIntQueue.cs | 34 +-
.../Support/TestApiConsistency.cs | 2 +-
src/Lucene.Net.Tests/Support/TestApiConsistency.cs | 2 +-
src/Lucene.Net.Tests/Util/TestPriorityQueue.cs | 559 ++++++++++++++++++++-
src/Lucene.Net/Search/HitQueue.cs | 4 +-
src/Lucene.Net/Search/TopDocs.cs | 217 ++++----
src/Lucene.Net/Util/Fst/FST.cs | 121 +++--
src/Lucene.Net/Util/PriorityQueue.cs | 504 +++++++++++++++----
11 files changed, 1364 insertions(+), 343 deletions(-)
diff --git a/src/Lucene.Net.Facet/Taxonomy/FloatTaxonomyFacets.cs b/src/Lucene.Net.Facet/Taxonomy/FloatTaxonomyFacets.cs
index 56ed487f9..588245d38 100644
--- a/src/Lucene.Net.Facet/Taxonomy/FloatTaxonomyFacets.cs
+++ b/src/Lucene.Net.Facet/Taxonomy/FloatTaxonomyFacets.cs
@@ -1,6 +1,8 @@
// Lucene version compatibility level 4.8.1
using Lucene.Net.Diagnostics;
+using Lucene.Net.Util;
using System;
+using System.Buffers;
using System.Collections.Generic;
using System.Diagnostics;
@@ -33,6 +35,8 @@ namespace Lucene.Net.Facet.Taxonomy
/// </summary>
public abstract class SingleTaxonomyFacets : TaxonomyFacets
{
+ private const int OrdAndSingleByteSize = sizeof(int) + sizeof(float); // LUCENENET specific - so we can calculate stack size
+
/// <summary>
/// Per-ordinal value. </summary>
protected readonly float[] m_values;
@@ -104,7 +108,8 @@ namespace Lucene.Net.Facet.Taxonomy
return m_values[ord];
}
- public override FacetResult GetTopChildren(int topN, string dim, params string[] path)
+#nullable enable
+ public override FacetResult? GetTopChildren(int topN, string dim, params string[] path)
{
if (topN <= 0)
{
@@ -118,64 +123,81 @@ namespace Lucene.Net.Facet.Taxonomy
return null;
}
- TopOrdAndSingleQueue q = new TopOrdAndSingleQueue(Math.Min(m_taxoReader.Count, topN));
- float bottomValue = 0;
+ // LUCENENET: Refactored PriorityQueue<T> subclass into PriorityComparer<T>
+ // implementation, which can be passed into ValuePriorityQueue. ValuePriorityQueue
+ // lives on the stack, and if the array size is small enough, we also allocate the
+ // array on the stack. Fallback to the array pool if it is beyond MaxStackByteLimit.
+ int bufferSize = PriorityQueue.GetArrayHeapSize(Math.Min(m_taxoReader.Count, topN));
+ bool usePool = OrdAndSingleByteSize * bufferSize > Constants.MaxStackByteLimit;
+ OrdAndValue<float>[]? arrayToReturnToPool = usePool ? ArrayPool<OrdAndValue<float>>.Shared.Rent(bufferSize) : null;
+ try
+ {
+ Span<OrdAndValue<float>> buffer = usePool ? arrayToReturnToPool : stackalloc OrdAndValue<float>[bufferSize];
+ var q = new ValuePriorityQueue<OrdAndValue<float>>(buffer, TopOrdAndSingleComparer.Default);
- int ord = m_children[dimOrd];
- float sumValues = 0;
- int childCount = 0;
+ float bottomValue = 0;
- while (ord != TaxonomyReader.INVALID_ORDINAL)
- {
- if (m_values[ord] > 0)
+ int ord = m_children[dimOrd];
+ float sumValues = 0;
+ int childCount = 0;
+
+ while (ord != TaxonomyReader.INVALID_ORDINAL)
{
- sumValues += m_values[ord];
- childCount++;
- if (m_values[ord] > bottomValue)
+ if (m_values[ord] > 0)
{
- // LUCENENET specific - use struct instead of reusing class instance for better performance
- q.Insert(new OrdAndValue<float>(ord, m_values[ord]));
- if (q.Count == topN)
+ sumValues += m_values[ord];
+ childCount++;
+ if (m_values[ord] > bottomValue)
{
- bottomValue = q.Top.Value;
+ // LUCENENET specific - use struct instead of reusing class instance for better performance
+ q.Insert(new OrdAndValue<float>(ord, m_values[ord]));
+ if (q.Count == topN)
+ {
+ bottomValue = q.Top.Value;
+ }
}
}
- }
- ord = m_siblings[ord];
- }
+ ord = m_siblings[ord];
+ }
- if (sumValues == 0)
- {
- return null;
- }
+ if (sumValues == 0)
+ {
+ return null;
+ }
- if (dimConfig.IsMultiValued)
- {
- if (dimConfig.RequireDimCount)
+ if (dimConfig.IsMultiValued)
{
- sumValues = m_values[dimOrd];
+ if (dimConfig.RequireDimCount)
+ {
+ sumValues = m_values[dimOrd];
+ }
+ else
+ {
+ // Our sum'd count is not correct, in general:
+ sumValues = -1;
+ }
}
else
{
- // Our sum'd count is not correct, in general:
- sumValues = -1;
+ // Our sum'd dim count is accurate, so we keep it
+ }
+
+ LabelAndValue[] labelValues = new LabelAndValue[q.Count];
+ for (int i = labelValues.Length - 1; i >= 0; i--)
+ {
+ var ordAndValue = q.Pop();
+ FacetLabel child = m_taxoReader.GetPath(ordAndValue.Ord);
+ labelValues[i] = new LabelAndValue(child.Components[cp.Length], ordAndValue.Value);
}
- }
- else
- {
- // Our sum'd dim count is accurate, so we keep it
- }
- LabelAndValue[] labelValues = new LabelAndValue[q.Count];
- for (int i = labelValues.Length - 1; i >= 0; i--)
+ return new FacetResult(dim, path, sumValues, labelValues, childCount);
+ }
+ finally
{
- var ordAndValue = q.Pop();
- FacetLabel child = m_taxoReader.GetPath(ordAndValue.Ord);
- labelValues[i] = new LabelAndValue(child.Components[cp.Length], ordAndValue.Value);
+ if (arrayToReturnToPool is not null)
+ ArrayPool<OrdAndValue<float>>.Shared.Return(arrayToReturnToPool);
}
-
- return new FacetResult(dim, path, sumValues, labelValues, childCount);
}
}
}
\ No newline at end of file
diff --git a/src/Lucene.Net.Facet/Taxonomy/IntTaxonomyFacets.cs b/src/Lucene.Net.Facet/Taxonomy/IntTaxonomyFacets.cs
index 3980f3530..6eb53844c 100644
--- a/src/Lucene.Net.Facet/Taxonomy/IntTaxonomyFacets.cs
+++ b/src/Lucene.Net.Facet/Taxonomy/IntTaxonomyFacets.cs
@@ -1,6 +1,9 @@
// Lucene version compatibility level 4.8.1
+using Lucene.Net.Util;
using System;
+using System.Buffers;
using System.Collections.Generic;
+using System.Runtime.InteropServices;
namespace Lucene.Net.Facet.Taxonomy
{
@@ -31,6 +34,8 @@ namespace Lucene.Net.Facet.Taxonomy
/// </summary>
public abstract class Int32TaxonomyFacets : TaxonomyFacets
{
+ private const int OrdAndInt32ByteSize = sizeof(int) + sizeof(int); // LUCENENET specific - so we can calculate stack size
+
/// <summary>
/// Per-ordinal value. </summary>
protected readonly int[] m_values;
@@ -106,7 +111,9 @@ namespace Lucene.Net.Facet.Taxonomy
return m_values[ord];
}
- public override FacetResult GetTopChildren(int topN, string dim, params string[] path)
+#nullable enable
+
+ public override FacetResult? GetTopChildren(int topN, string dim, params string[] path)
{
if (topN <= 0)
{
@@ -120,65 +127,81 @@ namespace Lucene.Net.Facet.Taxonomy
return null;
}
- TopOrdAndInt32Queue q = new TopOrdAndInt32Queue(Math.Min(m_taxoReader.Count, topN));
+ // LUCENENET: Refactored PriorityQueue<T> subclass into PriorityComparer<T>
+ // implementation, which can be passed into ValuePriorityQueue. ValuePriorityQueue
+ // lives on the stack, and if the array size is small enough, we also allocate the
+ // array on the stack. Fallback to the array pool if it is beyond MaxStackByteLimit.
+ int bufferSize = PriorityQueue.GetArrayHeapSize(Math.Min(m_taxoReader.Count, topN));
+ bool usePool = OrdAndInt32ByteSize * bufferSize > Constants.MaxStackByteLimit;
+ OrdAndValue<int>[]? arrayToReturnToPool = usePool ? ArrayPool<OrdAndValue<int>>.Shared.Rent(bufferSize) : null;
+ try
+ {
+ Span<OrdAndValue<int>> buffer = usePool ? arrayToReturnToPool : stackalloc OrdAndValue<int>[bufferSize];
+ var q = new ValuePriorityQueue<OrdAndValue<int>>(buffer, TopOrdAndInt32Comparer.Default);
- int bottomValue = 0;
+ int bottomValue = 0;
- int ord = m_children[dimOrd];
- int totValue = 0;
- int childCount = 0;
+ int ord = m_children[dimOrd];
+ int totValue = 0;
+ int childCount = 0;
- while (ord != TaxonomyReader.INVALID_ORDINAL)
- {
- if (m_values[ord] > 0)
+ while (ord != TaxonomyReader.INVALID_ORDINAL)
{
- totValue += m_values[ord];
- childCount++;
- if (m_values[ord] > bottomValue)
+ if (m_values[ord] > 0)
{
- // LUCENENET specific - use struct instead of reusing class instance for better performance
- q.Insert(new OrdAndValue<int>(ord, m_values[ord]));
- if (q.Count == topN)
+ totValue += m_values[ord];
+ childCount++;
+ if (m_values[ord] > bottomValue)
{
- bottomValue = q.Top.Value;
+ // LUCENENET specific - use struct instead of reusing class instance for better performance
+ q.Insert(new OrdAndValue<int>(ord, m_values[ord]));
+ if (q.Count == topN)
+ {
+ bottomValue = q.Top.Value;
+ }
}
}
- }
- ord = m_siblings[ord];
- }
+ ord = m_siblings[ord];
+ }
- if (totValue == 0)
- {
- return null;
- }
+ if (totValue == 0)
+ {
+ return null;
+ }
- if (dimConfig.IsMultiValued)
- {
- if (dimConfig.RequireDimCount)
+ if (dimConfig.IsMultiValued)
{
- totValue = m_values[dimOrd];
+ if (dimConfig.RequireDimCount)
+ {
+ totValue = m_values[dimOrd];
+ }
+ else
+ {
+ // Our sum'd value is not correct, in general:
+ totValue = -1;
+ }
}
else
{
- // Our sum'd value is not correct, in general:
- totValue = -1;
+ // Our sum'd dim value is accurate, so we keep it
+ }
+
+ LabelAndValue[] labelValues = new LabelAndValue[q.Count];
+ for (int i = labelValues.Length - 1; i >= 0; i--)
+ {
+ var ordAndValue = q.Pop();
+ FacetLabel child = m_taxoReader.GetPath(ordAndValue.Ord);
+ labelValues[i] = new LabelAndValue(child.Components[cp.Length], ordAndValue.Value);
}
- }
- else
- {
- // Our sum'd dim value is accurate, so we keep it
- }
- LabelAndValue[] labelValues = new LabelAndValue[q.Count];
- for (int i = labelValues.Length - 1; i >= 0; i--)
+ return new FacetResult(dim, path, totValue, labelValues, childCount);
+ }
+ finally
{
- var ordAndValue = q.Pop();
- FacetLabel child = m_taxoReader.GetPath(ordAndValue.Ord);
- labelValues[i] = new LabelAndValue(child.Components[cp.Length], ordAndValue.Value);
+ if (arrayToReturnToPool is not null)
+ ArrayPool<OrdAndValue<int>>.Shared.Return(arrayToReturnToPool);
}
-
- return new FacetResult(dim, path, totValue, labelValues, childCount);
}
}
}
\ No newline at end of file
diff --git a/src/Lucene.Net.Facet/TopOrdAndFloatQueue.cs b/src/Lucene.Net.Facet/TopOrdAndFloatQueue.cs
index d5da14cb9..b936193bc 100644
--- a/src/Lucene.Net.Facet/TopOrdAndFloatQueue.cs
+++ b/src/Lucene.Net.Facet/TopOrdAndFloatQueue.cs
@@ -2,6 +2,7 @@
using Lucene.Net.Util;
using System;
using System.Runtime.InteropServices;
+#nullable enable
namespace Lucene.Net.Facet
{
@@ -28,13 +29,15 @@ namespace Lucene.Net.Facet
/// <para/>
/// NOTE: This was TopOrdAndFloatQueue in Lucene
/// </summary>
+
+ // LUCENENET NOTE: Keeping this around because it is public. Although,
+ // we don't use it internally anymore, we use TopOrdAndSingleComparer
+ // with ValuePriorityQueue instead.
public class TopOrdAndSingleQueue : PriorityQueue<OrdAndValue<float>>
{
// LUCENENET specific - de-nested OrdAndValue and made it into a generic struct
// so it can be used with this class and TopOrdAndInt32Queue
-#nullable enable
-
/// <summary>
/// Initializes a new instance of <see cref="TopOrdAndSingleQueue"/> with the
/// specified <paramref name="topN"/> size.
@@ -43,16 +46,29 @@ namespace Lucene.Net.Facet
{
}
-#nullable restore
+ protected internal override bool LessThan(OrdAndValue<float> a, OrdAndValue<float> b)
+ => TopOrdAndSingleComparer.Default.LessThan(a, b);
+ }
+
+ /// <summary>
+ /// Keeps highest results, first by largest <see cref="float"/> value,
+ /// then tie break by smallest ord.
+ /// <para/>
+ /// NOTE: This is a refactoring of TopOrdAndFloatQueue in Lucene
+ /// </summary>
+ // LUCENENET: Refactored PriorityQueue<T> subclass into PriorityComparer<T>
+ // implementation, which can be passed into ValuePriorityQueue.
+ public sealed class TopOrdAndSingleComparer : PriorityComparer<OrdAndValue<float>>
+ {
+ /// <summary>
+ /// Returns a default sort order comparer for <see cref="OrdAndValue{Single}"/>.
+ /// Keeps highest results, first by largest <see cref="float"/> value,
+ /// then tie break by smallest ord.
+ /// </summary>
+ public static TopOrdAndSingleComparer Default { get; } = new TopOrdAndSingleComparer();
protected internal override bool LessThan(OrdAndValue<float> a, OrdAndValue<float> b)
{
- // LUCENENET specific - added guard clauses
- if (a is null)
- throw new ArgumentNullException(nameof(a));
- if (b is null)
- throw new ArgumentNullException(nameof(b));
-
if (a.Value < b.Value)
{
return true;
@@ -72,40 +88,45 @@ namespace Lucene.Net.Facet
/// Holds a single entry.
/// </summary>
// LUCENENET specific - de-nested this and made it into a struct so it can be shared
+ // and stack allocated.
[StructLayout(LayoutKind.Sequential)]
- public sealed class OrdAndValue<T> : IEquatable<OrdAndValue<T>>
+ public struct OrdAndValue<T> : IEquatable<OrdAndValue<T>>
+ where T : struct
{
+ private int ord;
+ private T value;
+
/// <summary>
/// Ordinal of the entry. </summary>
- public int Ord;
+ public int Ord => ord;
/// <summary>
/// Value associated with the ordinal. </summary>
- public T Value;
+ public T Value => value;
/// <summary>
/// Default constructor.
/// </summary>
public OrdAndValue(int ord, T value)
{
- Ord = ord;
- Value = value;
+ this.ord = ord;
+ this.value = value;
}
#region Added for better .NET support
- public override bool Equals(object obj)
+ public override bool Equals(object? obj)
{
return obj is OrdAndValue<T> other && Equals(other);
}
public bool Equals(OrdAndValue<T> other)
{
- return this.Ord == other.Ord && this.Value.Equals(other.Value);
+ return this.ord == other.ord && this.value.Equals(other.value);
}
public override int GetHashCode()
{
- return this.Ord.GetHashCode() ^ this.Value.GetHashCode();
+ return this.ord.GetHashCode() ^ this.value.GetHashCode();
}
public static bool operator ==(OrdAndValue<T> left, OrdAndValue<T> right)
diff --git a/src/Lucene.Net.Facet/TopOrdAndIntQueue.cs b/src/Lucene.Net.Facet/TopOrdAndIntQueue.cs
index 13300bf49..597485e9e 100644
--- a/src/Lucene.Net.Facet/TopOrdAndIntQueue.cs
+++ b/src/Lucene.Net.Facet/TopOrdAndIntQueue.cs
@@ -1,6 +1,7 @@
// Lucene version compatibility level 4.8.1
using Lucene.Net.Util;
using System;
+#nullable enable
namespace Lucene.Net.Facet
{
@@ -27,13 +28,15 @@ namespace Lucene.Net.Facet
/// <para/>
/// NOTE: This was TopOrdAndIntQueue in Lucene
/// </summary>
+
+ // LUCENENET NOTE: Keeping this around because it is public. Although,
+ // we don't use it internally anymore, we use TopOrdAndInt32Comparer
+ // with ValuePriorityQueue instead.
public class TopOrdAndInt32Queue : PriorityQueue<OrdAndValue<int>>
{
// LUCENENET specific - de-nested OrdAndValue and made it into a generic struct
// so it can be used with this class and TopOrdAndSingleQueue
-#nullable enable
-
/// <summary>
/// Initializes a new instance of <see cref="TopOrdAndInt32Queue"/> with the specified
/// <paramref name="topN"/> size.
@@ -43,16 +46,29 @@ namespace Lucene.Net.Facet
{
}
-#nullable restore
+ protected internal override bool LessThan(OrdAndValue<int> a, OrdAndValue<int> b)
+ => TopOrdAndInt32Comparer.Default.LessThan(a, b);
+ }
+
+ /// <summary>
+ /// Keeps highest results, first by largest <see cref="int"/> value,
+ /// then tie break by smallest ord.
+ /// <para/>
+ /// NOTE: This is a refactoring of TopOrdAndIntQueue in Lucene
+ /// </summary>
+ // LUCENENET: Refactored PriorityQueue<T> subclass into PriorityComparer<T>
+ // implementation, which can be passed into ValuePriorityQueue.
+ public sealed class TopOrdAndInt32Comparer : PriorityComparer<OrdAndValue<int>>
+ {
+ /// <summary>
+ /// Returns a default sort order comparer for <see cref="OrdAndValue{Int32}"/>.
+ /// Keeps highest results, first by largest <see cref="int"/> value,
+ /// then tie break by smallest ord.
+ /// </summary>
+ public static TopOrdAndInt32Comparer Default { get; } = new TopOrdAndInt32Comparer();
protected internal override bool LessThan(OrdAndValue<int> a, OrdAndValue<int> b)
{
- // LUCENENET specific - added guard clauses
- if (a is null)
- throw new ArgumentNullException(nameof(a));
- if (b is null)
- throw new ArgumentNullException(nameof(b));
-
if (a.Value < b.Value)
{
return true;
diff --git a/src/Lucene.Net.Tests.Facet/Support/TestApiConsistency.cs b/src/Lucene.Net.Tests.Facet/Support/TestApiConsistency.cs
index 989ccbbe8..f786275f0 100644
--- a/src/Lucene.Net.Tests.Facet/Support/TestApiConsistency.cs
+++ b/src/Lucene.Net.Tests.Facet/Support/TestApiConsistency.cs
@@ -38,7 +38,7 @@ namespace Lucene.Net.Tests.Facet
[TestCase(typeof(Lucene.Net.Facet.Facets))]
public override void TestPrivateFieldNames(Type typeFromTargetAssembly)
{
- base.TestPrivateFieldNames(typeFromTargetAssembly);
+ base.TestPrivateFieldNames(typeFromTargetAssembly, @"^Lucene\.Net\.Facet\.Taxonomy\.(?:Single|Int32)TaxonomyFacets\.OrdAnd(?:Single|Int32)ByteSize");
}
[Test, LuceneNetSpecific]
diff --git a/src/Lucene.Net.Tests/Support/TestApiConsistency.cs b/src/Lucene.Net.Tests/Support/TestApiConsistency.cs
index 76fc665f8..75f8a15f4 100644
--- a/src/Lucene.Net.Tests/Support/TestApiConsistency.cs
+++ b/src/Lucene.Net.Tests/Support/TestApiConsistency.cs
@@ -38,7 +38,7 @@ namespace Lucene.Net
[TestCase(typeof(Lucene.Net.Analysis.Analyzer))]
public override void TestPrivateFieldNames(Type typeFromTargetAssembly)
{
- base.TestPrivateFieldNames(typeFromTargetAssembly, @"^Lucene\.Net\.Support\.(?:ConcurrentHashSet|PlatformHelper|DateTimeOffsetUtil|Arrays|IO\.FileSupport)|^Lucene\.ExceptionExtensions|^Lucene\.Net\.Util\.Constants\.MaxStackByteLimit");
+ base.TestPrivateFieldNames(typeFromTargetAssembly, @"^Lucene\.Net\.Support\.(?:ConcurrentHashSet|PlatformHelper|DateTimeOffsetUtil|Arrays|IO\.FileSupport)|^Lucene\.ExceptionExtensions|^Lucene\.Net\.Util\.Constants\.MaxStackByteLimit|^Lucene\.Net\.Search\.TopDocs\.ShardByteSize");
}
[Test, LuceneNetSpecific]
diff --git a/src/Lucene.Net.Tests/Util/TestPriorityQueue.cs b/src/Lucene.Net.Tests/Util/TestPriorityQueue.cs
index a99156fc9..4b789a5a0 100644
--- a/src/Lucene.Net.Tests/Util/TestPriorityQueue.cs
+++ b/src/Lucene.Net.Tests/Util/TestPriorityQueue.cs
@@ -2,6 +2,7 @@
using NUnit.Framework;
using System;
using System.Collections.Generic;
+using System.Drawing;
using System.IO;
#if FEATURE_SERIALIZABLE
using System.Runtime.Serialization;
@@ -34,6 +35,16 @@ namespace Lucene.Net.Util
{
private static readonly int MAX_PQ_SIZE = ArrayUtil.MAX_ARRAY_LENGTH - 1;
+ private class IntegerComparer : PriorityComparer<int?>
+ {
+ public static IntegerComparer Default { get; } = new IntegerComparer();
+
+ protected internal override bool LessThan(int? a, int? b)
+ {
+ return (a < b);
+ }
+ }
+
#if FEATURE_SERIALIZABLE
[Serializable]
#endif
@@ -51,11 +62,11 @@ namespace Lucene.Net.Util
// LUCENENET specific - "prepopulate" is now controlled by whether
// or not SentinelFactory is null.
- private class SentinelFactory : SentinelFactory<int?, IntegerQueue>
+ internal class SentinelFactory : ISentinelFactory<int?>
{
public static SentinelFactory Default { get; } = new SentinelFactory();
- public override int? Create(IntegerQueue integerQueue) => int.MaxValue;
+ public int? Create() => int.MaxValue;
}
protected internal override bool LessThan(int? a, int? b)
@@ -64,6 +75,7 @@ namespace Lucene.Net.Util
}
}
+ [Test]
public void TestPQ()
{
TestPQ(AtLeast(10000), Random);
@@ -104,6 +116,48 @@ namespace Lucene.Net.Util
// System.out.println(" microseconds/pop");
}
+ [Test]
+ public void ValuePriorityQueue_TestPQ()
+ {
+ ValuePriorityQueue_TestPQ(AtLeast(10000), Random);
+ }
+
+ public static void ValuePriorityQueue_TestPQ(int count, Random gen)
+ {
+ Span<int?> buffer = new int?[GetArrayHeapSize(count)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ int sum = 0, sum2 = 0;
+
+ for (int i = 0; i < count; i++)
+ {
+ int next = gen.Next();
+ sum += next;
+ pq.Add(next);
+ }
+
+ // Date end = new Date();
+
+ // System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
+ // System.out.println(" microseconds/put");
+
+ // start = new Date();
+
+ int last = int.MinValue;
+ for (int i = 0; i < count; i++)
+ {
+ var next = pq.Pop();
+ assertTrue(next.Value >= last);
+ last = next.Value;
+ sum2 += last;
+ }
+
+ assertEquals(sum, sum2);
+ // end = new Date();
+
+ // System.out.print(((float)(end.getTime()-start.getTime()) / count) * 1000);
+ // System.out.println(" microseconds/pop");
+ }
+
[Test]
public virtual void TestClear()
{
@@ -116,6 +170,19 @@ namespace Lucene.Net.Util
Assert.AreEqual(0, pq.Count);
}
+ [Test]
+ public virtual void ValuePriorityQueue_TestClear()
+ {
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(3)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ pq.Add(2);
+ pq.Add(3);
+ pq.Add(1);
+ Assert.AreEqual(3, pq.Count);
+ pq.Clear();
+ Assert.AreEqual(0, pq.Count);
+ }
+
[Test]
public void TestFixedSize()
{
@@ -130,6 +197,21 @@ namespace Lucene.Net.Util
assertEquals((int?)3, pq.Top);
}
+ [Test]
+ public void ValuePriorityQueue_TestFixedSize()
+ {
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(3)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ pq.InsertWithOverflow(2);
+ pq.InsertWithOverflow(3);
+ pq.InsertWithOverflow(1);
+ pq.InsertWithOverflow(5);
+ pq.InsertWithOverflow(7);
+ pq.InsertWithOverflow(1);
+ assertEquals(3, pq.Count);
+ assertEquals((int?)3, pq.Top);
+ }
+
[Test]
public virtual void TestInsertWithOverflow()
{
@@ -163,6 +245,40 @@ namespace Lucene.Net.Util
Assert.AreEqual((int?)7, pq.Top);
}
+ [Test]
+ public virtual void ValuePriorityQueue_TestInsertWithOverflow()
+ {
+ // Tests that InsertWithOverflow discards the correct value,
+ // and the resulting PQ preserves its structure
+
+ int size = 4;
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(size)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ int? i1 = 2;
+ int? i2 = 3;
+ int? i3 = 1;
+ int? i4 = 5;
+ int? i5 = 7;
+ int? i6 = 1;
+
+ Assert.IsNull(pq.InsertWithOverflow(i1));
+ Assert.IsNull(pq.InsertWithOverflow(i2));
+ Assert.IsNull(pq.InsertWithOverflow(i3));
+ Assert.IsNull(pq.InsertWithOverflow(i4));
+ Assert.IsTrue(pq.InsertWithOverflow(i5) == i3); // i3 should have been dropped
+ Assert.IsTrue(pq.InsertWithOverflow(i6) == i6); // i6 should not have been inserted
+ Assert.AreEqual(size, pq.Count);
+ Assert.AreEqual((int?)2, pq.Top);
+
+ // LUCENENET SPECIFIC
+ pq.Pop();
+ Assert.AreEqual((int?)3, pq.Top);
+ pq.Pop();
+ Assert.AreEqual((int?)5, pq.Top);
+ pq.Pop();
+ Assert.AreEqual((int?)7, pq.Top);
+ }
+
#region LUCENENET SPECIFIC TESTS
@@ -188,6 +304,15 @@ namespace Lucene.Net.Util
}
}
+ private class MyComparer : PriorityComparer<MyType>
+ {
+ public static MyComparer Default { get; } = new MyComparer();
+ protected internal override bool LessThan(MyType a, MyType b)
+ {
+ return a.Field < b.Field;
+ }
+ }
+
private class Less : IComparer<int?>
{
public static IComparer<int?> Default { get; } = new Less();
@@ -278,6 +403,23 @@ namespace Lucene.Net.Util
Assert.AreEqual(pq.Count, 0);
}
+ [Test, LuceneNetSpecific]
+ public static void ValuePriorityQueue_TestPrepopulation()
+ {
+ int maxSize = 10;
+ // Populates the internal array
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default, IntegerQueue.SentinelFactory.Default);
+ Assert.AreEqual(pq.Top, int.MaxValue);
+ Assert.AreEqual(pq.Count, 10);
+
+ // Does not populate it
+ buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default, sentinelFactory: null);
+ Assert.AreEqual(pq.Top, default);
+ Assert.AreEqual(pq.Count, 0);
+ }
+
private static void AddAndTest<T>(PriorityQueue<T> pq, T element, T expectedTop, int expectedSize)
{
pq.Add(element);
@@ -285,19 +427,26 @@ namespace Lucene.Net.Util
Assert.AreEqual(pq.Count, expectedSize);
}
+ private static void AddAndTest<T>(ref ValuePriorityQueue<T> pq, T element, T expectedTop, int expectedSize)
+ {
+ pq.Add(element);
+ Assert.AreEqual(pq.Top, expectedTop);
+ Assert.AreEqual(pq.Count, expectedSize);
+ }
+
[Test, LuceneNetSpecific]
public static void TestAdd()
{
int maxSize = 10;
PriorityQueue<int?> pq = new IntegerQueue(maxSize);
-
+
// Add mixed elements
AddAndTest(pq, 5, 5, 1);
AddAndTest(pq, 1, 1, 2);
AddAndTest(pq, 3, 1, 3);
AddAndTest(pq, -1, -1, 4);
AddAndTest(pq, -111111, -111111, 5);
-
+
// Add a sorted list of elements
pq = new IntegerQueue(maxSize);
AddAndTest(pq, -111111, -111111, 1);
@@ -315,6 +464,41 @@ namespace Lucene.Net.Util
AddAndTest(pq, -111111, -111111, 5);
}
+
+ [Test, LuceneNetSpecific]
+ public static void ValuePriorityQueue_TestAdd()
+ {
+ int maxSize = 10;
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+
+ // Add mixed elements
+ AddAndTest(ref pq, 5, 5, 1);
+ AddAndTest(ref pq, 1, 1, 2);
+ AddAndTest(ref pq, 3, 1, 3);
+ AddAndTest(ref pq, -1, -1, 4);
+ AddAndTest(ref pq, -111111, -111111, 5);
+
+ // Add a sorted list of elements
+ buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ AddAndTest(ref pq, -111111, -111111, 1);
+ AddAndTest(ref pq, -1, -111111, 2);
+ AddAndTest(ref pq, 1, -111111, 3);
+ AddAndTest(ref pq, 3, -111111, 4);
+ AddAndTest(ref pq, 5, -111111, 5);
+
+ // Add a reversed sorted list of elements
+ buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ AddAndTest(ref pq, 5, 5, 1);
+ AddAndTest(ref pq, 3, 3, 2);
+ AddAndTest(ref pq, 1, 1, 3);
+ AddAndTest(ref pq, -1, -1, 4);
+ AddAndTest(ref pq, -111111, -111111, 5);
+ }
+
+
[Test, LuceneNetSpecific]
public static void TestDuplicates()
{
@@ -336,6 +520,28 @@ namespace Lucene.Net.Util
Assert.AreEqual(pq.Count, 7);
}
+ [Test, LuceneNetSpecific]
+ public static void ValuePriorityQueue_TestDuplicates()
+ {
+ // Tests that the queue doesn't absorb elements with duplicate keys
+ int maxSize = 10;
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+
+ pq.Add(3);
+ pq.Add(3);
+ Assert.AreEqual(pq.Count, 2);
+
+ pq.Add(3);
+ Assert.AreEqual(pq.Count, 3);
+
+ pq.Add(17);
+ pq.Add(17);
+ pq.Add(17);
+ pq.Add(17);
+ Assert.AreEqual(pq.Count, 7);
+ }
+
[Test, LuceneNetSpecific]
public static void TestPop()
{
@@ -394,6 +600,66 @@ namespace Lucene.Net.Util
pq.Pop();
}
+ [Test, LuceneNetSpecific]
+ public static void ValuePriorityQueue_TestPop()
+ {
+ int maxSize = 10;
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+
+ // Add one element and pop it
+ pq.Add(7);
+ pq.Pop();
+ Assert.AreEqual(pq.Count, 0);
+
+ // Add a bunch of elements, pop them all
+ pq.Add(1);
+ pq.Add(20);
+ pq.Add(1);
+ pq.Add(15);
+ pq.Add(4);
+ pq.Add(12);
+ pq.Add(1000);
+ pq.Add(-3);
+ pq.Pop();
+ Assert.AreEqual(pq.Count, 7);
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ Assert.AreEqual(pq.Count, 0);
+
+ // Interleaved adds and pops
+ pq.Add(1);
+ pq.Add(20);
+ pq.Pop();
+ Assert.AreEqual(pq.Count, 1);
+ pq.Add(1);
+ pq.Add(15);
+ pq.Add(4);
+ pq.Pop();
+ pq.Pop();
+ Assert.AreEqual(pq.Count, 2);
+ pq.Add(12);
+ pq.Add(1000);
+ pq.Add(-3);
+ pq.Pop();
+ pq.Pop();
+ Assert.AreEqual(pq.Count, 3);
+
+ // Pop an empty PQ
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ pq.Pop();
+ }
+
+
[Test, LuceneNetSpecific]
public static void TestUpdateTop()
{
@@ -423,6 +689,36 @@ namespace Lucene.Net.Util
Assert.AreEqual(pq.Top.Field, 1);
}
+ [Test, LuceneNetSpecific]
+ public static void ValuePriorityQueue_TestUpdateTop()
+ {
+ // Mostly to reflect the usage of UpdateTop
+ int maxSize = 10;
+ Span<MyType> buffer = new MyType[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<MyType> pq = new ValuePriorityQueue<MyType>(buffer, MyComparer.Default);
+
+ pq.Add(new MyType(1));
+ pq.Add(new MyType(20));
+ pq.Add(new MyType(1));
+ pq.Add(new MyType(15));
+ pq.Add(new MyType(4));
+ pq.Add(new MyType(12));
+ pq.Add(new MyType(1000));
+ pq.Add(new MyType(-300));
+
+ Assert.AreEqual(pq.Top.Field, -300);
+ MyType topElement = pq.Top;
+ topElement.Field = 25; // Now this should no longer be at the top of the queue
+ pq.UpdateTop(); // Hence we need to update the top queue
+ Assert.AreEqual(pq.Top.Field, 1);
+
+ // The less eficient way to do this is the following
+ topElement = pq.Pop();
+ topElement.Field = 678;
+ pq.Add(topElement);
+ Assert.AreEqual(pq.Top.Field, 1);
+ }
+
[Test, LuceneNetSpecific]
public static void TestOverflow()
{
@@ -460,6 +756,45 @@ namespace Lucene.Net.Util
}
}
+ [Test, LuceneNetSpecific]
+ public static void ValuePriorityQueue_TestOverflow()
+ {
+ // Tests adding elements to full queues
+ // Add's documentation claims throwing an IndexOutOfRangeException in this situation
+
+ // Add an element to a prepopulated queue
+ int maxSize = 10;
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default, IntegerQueue.SentinelFactory.Default);
+
+ try
+ {
+ pq.Add(3);
+ Assert.Fail();
+ }
+ catch (Exception e) when (e.IsIndexOutOfBoundsException())
+ {
+ }
+
+ // Populate manually
+ maxSize = 5;
+ buffer = stackalloc int?[GetArrayHeapSize(maxSize)];
+ pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ pq.Add(1);
+ pq.Add(4);
+ pq.Add(-1);
+ pq.Add(0);
+ pq.Add(10);
+
+ try
+ {
+ pq.Add(666);
+ }
+ catch (Exception e) when (e.IsIndexOutOfBoundsException())
+ {
+ }
+ }
+
[Test, LuceneNetSpecific]
public virtual void TestInsertWithOverflowDoesNotOverflow()
{
@@ -476,9 +811,26 @@ namespace Lucene.Net.Util
Assert.AreEqual((int?)3, pq.Top);
}
+ [Test, LuceneNetSpecific]
+ public virtual void ValuePriorityQueue_TestInsertWithOverflowDoesNotOverflow()
+ {
+ // Tests that InsertWithOverflow does not cause overflow
+
+ Span<int?> buffer = stackalloc int?[GetArrayHeapSize(3)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ pq.InsertWithOverflow(2);
+ pq.InsertWithOverflow(3);
+ pq.InsertWithOverflow(1);
+ pq.InsertWithOverflow(5);
+ pq.InsertWithOverflow(7);
+ pq.InsertWithOverflow(1);
+ Assert.AreEqual(3, pq.Count);
+ Assert.AreEqual((int?)3, pq.Top);
+ }
+
private static void AddElements<T>(PriorityQueue<T> pq, T[] elements)
{
- int size = (int)elements.size();
+ int size = elements.Length;
for (int i = 0; i < size; i++)
{
@@ -521,7 +873,7 @@ namespace Lucene.Net.Util
private static void TimedAddAndPop<T>(PriorityQueue<T> pq, T[] elements)
{
- int size = (int)elements.size();
+ int size = elements.Length;
DateTime start, end;
TimeSpan total;
@@ -546,6 +898,83 @@ namespace Lucene.Net.Util
Console.WriteLine("Average time per pop: {0} ticks", total.Ticks / size);
}
+
+ #region ValuePriorityQueue
+
+ private static void AddElements<T>(ref ValuePriorityQueue<T> pq, T[] elements)
+ {
+ int size = elements.Length;
+
+ for (int i = 0; i < size; i++)
+ {
+ pq.Add(elements[i]);
+ }
+ }
+
+ private static void PopElements<T>(ref ValuePriorityQueue<T> pq)
+ {
+ int size = pq.Count;
+
+ for (int i = 0; i < size; i++)
+ {
+ pq.Pop();
+ }
+ }
+
+ private static void PopAndTestElements<T>(ref ValuePriorityQueue<T> pq, T[] elements)
+ {
+ int size = pq.Count;
+
+ for (int i = 0; i < size; i++)
+ {
+ Assert.AreEqual(pq.Pop(), elements[i]);
+ }
+ }
+
+ private static void PopAndTestElements<T>(ref ValuePriorityQueue<T> pq)
+ {
+ int size = pq.Count;
+ T last = pq.Pop();
+
+ for (int i = 1; i < size; i++)
+ {
+ T next = pq.Pop();
+ Assert.IsTrue(pq.Comparer.Compare(last, next) < 0 || last.Equals(next));
+ last = next;
+ }
+ }
+
+ private static void TimedAddAndPop<T>(ref ValuePriorityQueue<T> pq, T[] elements)
+ {
+ int size = elements.Length;
+ DateTime start, end;
+ TimeSpan total;
+
+ start = DateTime.Now;
+
+ AddElements(ref pq, elements);
+
+ end = DateTime.Now;
+ total = end - start;
+
+ Console.WriteLine("Total adding time: {0} ticks or {1}ms", total.Ticks, total.Milliseconds);
+ Console.WriteLine("Average time per add: {0} ticks", total.Ticks / size);
+
+ start = DateTime.Now;
+
+ PopElements(ref pq);
+
+ end = DateTime.Now;
+ total = end - start;
+
+ Console.WriteLine("Total popping time: {0} ticks or {1}ms", total.Ticks, total.Milliseconds);
+ Console.WriteLine("Average time per pop: {0} ticks", total.Ticks / size);
+ }
+
+ #endregion ValuePriorityQueue
+
+
+
[Test, LuceneNetSpecific]
public static void TestPersistence()
{
@@ -568,6 +997,29 @@ namespace Lucene.Net.Util
PopAndTestElements(pq, elements);
}
+ [Test, LuceneNetSpecific]
+ public static void ValuePriorityQueue_TestPersistence()
+ {
+ // Tests that a big number of elements are added and popped (in the correct order)
+ // without losing any information
+
+ int maxSize = AtLeast(100000);
+ Span<int?> buffer = new int?[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+
+ int?[] elements = new int?[maxSize];
+ for (int i = 0; i < maxSize; i++)
+ {
+ elements[i] = Random.Next();
+ }
+
+ AddElements(ref pq, elements);
+
+ ArrayUtil.IntroSort(elements, Less.Default);
+
+ PopAndTestElements(ref pq, elements);
+ }
+
[Test, LuceneNetSpecific]
public static void TestStress()
{
@@ -617,11 +1069,62 @@ namespace Lucene.Net.Util
Assert.AreEqual(pq.Count, 0);
}
+ [Test, LuceneNetSpecific]
+ public static void ValuePriorityQueue_TestStress()
+ {
+ int atLeast = 1000000;
+ int maxSize = AtLeast(atLeast);
+ //PriorityQueue<int?> pq = new IntegerQueue(maxSize);
+ Span<int?> buffer = new int?[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+
+ // Add a lot of elements
+ for (int i = 0; i < maxSize; i++)
+ {
+ pq.Add(Random.Next());
+ }
+
+ // Pop some of them
+ while (pq.Count > atLeast / 2)
+ {
+ pq.Pop();
+ }
+
+ // Add some more
+ while (pq.Count < (atLeast * 3) / 4)
+ {
+ pq.Add(Random.Next());
+ }
+
+ PopAndTestElements(ref pq);
+
+ Assert.AreEqual(pq.Count, 0);
+
+ // We fill it again
+ for (int i = 0; 2 * i < maxSize; i++)
+ {
+ pq.Add(Random.Next());
+ }
+
+ Assert.AreEqual(pq.Count, (maxSize + 1) / 2);
+ pq.Clear();
+ Assert.AreEqual(pq.Count, 0);
+
+ // One last time
+ for (int i = 0; 2 * i < maxSize; i++)
+ {
+ pq.Add(Random.Next());
+ }
+
+ PopAndTestElements(ref pq);
+ Assert.AreEqual(pq.Count, 0);
+ }
+
[Test, Explicit, LuceneNetSpecific]
public static void Benchmarks()
{
AssumeTrue("Turn VERBOSE on or otherwise you won't see the results.", Verbose);
-
+
int maxSize = AtLeast(100000);
PriorityQueue<int?> pq = new IntegerQueue(maxSize);
int?[] elements = new int?[maxSize];
@@ -651,6 +1154,43 @@ namespace Lucene.Net.Util
pq.Clear();
}
+ [Test, Explicit, LuceneNetSpecific]
+ public static void ValuePriorityQueue_Benchmarks()
+ {
+ AssumeTrue("Turn VERBOSE on or otherwise you won't see the results.", Verbose);
+
+ int maxSize = AtLeast(100000);
+ Span<int?> buffer = new int?[GetArrayHeapSize(maxSize)];
+ ValuePriorityQueue<int?> pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ int?[] elements = new int?[maxSize];
+
+ for (int i = 0; i < maxSize; i++)
+ {
+ elements[i] = Random.Next();
+ }
+
+ Console.WriteLine("Random list of elements...");
+
+ TimedAddAndPop(ref pq, elements);
+ pq.Clear();
+
+ Console.WriteLine("\nSorted list of elements...");
+
+ buffer = new int?[GetArrayHeapSize(maxSize)];
+ pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ ArrayUtil.IntroSort(elements, Less.Default);
+ TimedAddAndPop(ref pq, elements);
+ pq.Clear();
+
+ Console.WriteLine("\nReverse sorted list of elements...");
+
+ buffer = new int?[GetArrayHeapSize(maxSize)];
+ pq = new ValuePriorityQueue<int?>(buffer, IntegerComparer.Default);
+ ArrayUtil.IntroSort(elements, Greater.Default);
+ TimedAddAndPop(ref pq, elements);
+ pq.Clear();
+ }
+
#if FEATURE_SERIALIZABLE
[Test, LuceneNetSpecific]
@@ -677,6 +1217,11 @@ namespace Lucene.Net.Util
}
#endif
+ private static int GetArrayHeapSize(int maxSize)
+ {
+ return PriorityQueue.GetArrayHeapSize(maxSize);
+ }
+
#endregion
}
}
\ No newline at end of file
diff --git a/src/Lucene.Net/Search/HitQueue.cs b/src/Lucene.Net/Search/HitQueue.cs
index 5f4c4d046..67b00ec45 100644
--- a/src/Lucene.Net/Search/HitQueue.cs
+++ b/src/Lucene.Net/Search/HitQueue.cs
@@ -72,11 +72,11 @@ namespace Lucene.Net.Search
// and a "prePopulate" boolean value, population is controlled by whether ISentinelFactory<T>
// has an instance or is null. This is the singleton instance that is injected when "prePopulate"
// is true.
- internal sealed class SentinelFactory : SentinelFactory<ScoreDoc, HitQueue>
+ internal sealed class SentinelFactory : ISentinelFactory<ScoreDoc>
{
public static SentinelFactory Default { get; } = new SentinelFactory();
- public override ScoreDoc Create(HitQueue priorityQueue)
+ public ScoreDoc Create()
{
// Always set the doc Id to MAX_VALUE so that it won't be favored by
// lessThan. this generally should not happen since if score is not NEG_INF,
diff --git a/src/Lucene.Net/Search/TopDocs.cs b/src/Lucene.Net/Search/TopDocs.cs
index 7930ef355..297dfbbd4 100644
--- a/src/Lucene.Net/Search/TopDocs.cs
+++ b/src/Lucene.Net/Search/TopDocs.cs
@@ -2,8 +2,11 @@
using Lucene.Net.Support;
using Lucene.Net.Util;
using System;
+using System.Buffers;
+using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
namespace Lucene.Net.Search
{
@@ -69,36 +72,76 @@ namespace Lucene.Net.Search
this.maxScore = maxScore;
}
+#nullable enable
+
+ private static readonly int ShardByteSize = Marshal.SizeOf(typeof(Shard)); // LUCENENET specific so we can calculate stack size
+
+ // LUCENENET specific - Renamed ShardRef to Shard and made it into a struct
+ // so we can allocate arrays of them on the stack.
// Refers to one hit:
- private class ShardRef
+ [StructLayout(LayoutKind.Sequential)]
+ private struct Shard : IEquatable<Shard>
{
+ [SuppressMessage("CodeQuality", "IDE0079:Remove unnecessary suppression", Justification = "This is a SonarCloud issue")]
+ [SuppressMessage("Major Code Smell", "S2933:Fields that are only assigned in the constructor should be \"readonly\"", Justification = "Structs are known to have performance issues with readonly fields")]
+ [SuppressMessage("Style", "IDE0044:Add readonly modifier", Justification = "Structs are known to have performance issues with readonly fields")]
+ private int shardIndex;
+ private int hitIndex;
+
// Which shard (index into shardHits[]):
- internal int ShardIndex { get; private set; }
+ internal int ShardIndex => shardIndex;
// Which hit within the shard:
- internal int HitIndex { get; set; }
+ internal int HitIndex
+ {
+ get => hitIndex;
+ set => hitIndex = value;
+ }
+
+ public Shard(int shardIndex)
+ {
+ this.shardIndex = shardIndex;
+ this.hitIndex = 0;
+ }
- public ShardRef(int shardIndex)
+ public bool Equals(Shard other)
{
- this.ShardIndex = shardIndex;
+ return shardIndex == other.shardIndex && hitIndex == other.hitIndex;
}
+ public override bool Equals(object? obj)
+ {
+ if (obj is Shard shard)
+ return Equals(shard);
+ return false;
+ }
+
+ public override int GetHashCode()
+ => shardIndex.GetHashCode() ^ hitIndex.GetHashCode();
+
public override string ToString()
{
- return "ShardRef(shardIndex=" + ShardIndex + " hitIndex=" + HitIndex + ")";
+ return $"{nameof(Shard)}({nameof(shardIndex)}={shardIndex} {nameof(hitIndex)}={hitIndex})";
+ }
+
+ public static bool operator ==(Shard shard1, Shard shard2)
+ {
+ return shard1.Equals(shard2);
}
+
+ public static bool operator !=(Shard shard1, Shard shard2)
+ => !(shard1 == shard2);
}
-#nullable enable
+ // LUCENENET specific - refactored ScoreMergeSortQueue into ScoreMergeSortComparer so it can be passed into a ValuePriorityQueue
- // Specialized MergeSortQueue that just merges by
+ // Specialized MergeSortComparer that just merges by
// relevance score, descending:
- private sealed class ScoreMergeSortQueue : PriorityQueue<ShardRef> // LUCENENET specific - marked sealed
+ private sealed class ScoreMergeSortComparer : PriorityComparer<Shard> // LUCENENET specific - marked sealed
{
internal readonly ScoreDoc[][] shardHits;
- public ScoreMergeSortQueue(TopDocs[] shardHits)
- : base(shardHits?.Length ?? 0)
+ public ScoreMergeSortComparer(TopDocs[] shardHits)
{
if (shardHits is null)
throw new ArgumentNullException(nameof(shardHits));
@@ -111,14 +154,8 @@ namespace Lucene.Net.Search
}
// Returns true if first is < second
- protected internal override bool LessThan(ShardRef first, ShardRef second)
+ protected internal override bool LessThan(Shard first, Shard second)
{
- // LUCENENET specific - added guard clauses
- if (first is null)
- throw new ArgumentNullException(nameof(first));
- if (second is null)
- throw new ArgumentNullException(nameof(second));
-
if (Debugging.AssertsEnabled) Debugging.Assert(first != second);
float firstScore = shardHits[first.ShardIndex][first.HitIndex].Score;
float secondScore = shardHits[second.ShardIndex][second.HitIndex].Score;
@@ -154,7 +191,8 @@ namespace Lucene.Net.Search
}
}
- private sealed class MergeSortQueue : PriorityQueue<ShardRef> // LUCENENET specific - marked sealed
+ // LUCENENET specific - refactored MergeSortQueue into MergeSortComparer so it can be passed into a ValuePriorityQueue
+ private sealed class MergeSortComparer : PriorityComparer<Shard> // LUCENENET specific - marked sealed
{
// These are really FieldDoc instances:
internal readonly ScoreDoc[][] shardHits;
@@ -162,8 +200,7 @@ namespace Lucene.Net.Search
internal readonly FieldComparer[] comparers;
internal readonly int[] reverseMul;
- public MergeSortQueue(Sort sort, TopDocs[] shardHits)
- : base(shardHits?.Length ?? 0)
+ public MergeSortComparer(Sort sort, TopDocs[] shardHits)
{
if (shardHits is null)
throw new ArgumentNullException(nameof(shardHits));
@@ -204,17 +241,9 @@ namespace Lucene.Net.Search
}
}
-
-
// Returns true if first is < second
- protected internal override bool LessThan(ShardRef first, ShardRef second)
+ protected internal override bool LessThan(Shard first, Shard second)
{
- // LUCENENET specific - added guard clauses
- if (first is null)
- throw new ArgumentNullException(nameof(first));
- if (second is null)
- throw new ArgumentNullException(nameof(second));
-
if (Debugging.AssertsEnabled) Debugging.Assert(first != second);
FieldDoc firstFD = (FieldDoc)shardHits[first.ShardIndex][first.HitIndex];
FieldDoc secondFD = (FieldDoc)shardHits[second.ShardIndex][second.HitIndex];
@@ -289,82 +318,102 @@ namespace Lucene.Net.Search
if (shardHits is null)
throw new ArgumentNullException(nameof(shardHits));
- PriorityQueue<ShardRef> queue;
+ // LUCENENET: Refactored PriorityQueue<T> subclasses into PriorityComparer<T>
+ // implementations, which can be passed into ValuePriorityQueue. ValuePriorityQueue
+ // lives on the stack, and if the array size is small enough, we also allocate the
+ // array on the stack. Fallback to the array pool if it is beyond MaxStackByteLimit.
+ IComparer<Shard> comparer;
if (sort is null)
{
- queue = new ScoreMergeSortQueue(shardHits);
+ comparer = new ScoreMergeSortComparer(shardHits);
}
else
{
- queue = new MergeSortQueue(sort, shardHits);
+ comparer = new MergeSortComparer(sort, shardHits);
}
-
- int totalHitCount = 0;
- int availHitCount = 0;
- float maxScore = float.Epsilon; // LUCENENET: Epsilon in .NET is the same as MIN_VALUE in Java
- for (int shardIDX = 0; shardIDX < shardHits.Length; shardIDX++)
+ int bufferSize = PriorityQueue.GetArrayHeapSize(shardHits.Length);
+ bool usePool = ShardByteSize * bufferSize > Constants.MaxStackByteLimit;
+ Shard[]? arrayToReturnToPool = usePool ? ArrayPool<Shard>.Shared.Rent(bufferSize) : null;
+ try
{
- TopDocs shard = shardHits[shardIDX];
- // totalHits can be non-zero even if no hits were
- // collected, when searchAfter was used:
- totalHitCount += shard.TotalHits;
- if (shard.ScoreDocs != null && shard.ScoreDocs.Length > 0)
+ Span<Shard> buffer = usePool ? arrayToReturnToPool : stackalloc Shard[bufferSize];
+ var queue = new ValuePriorityQueue<Shard>(buffer, comparer);
+
+ int totalHitCount = 0;
+ int availHitCount = 0;
+ float maxScore = float.Epsilon; // LUCENENET: Epsilon in .NET is the same as MIN_VALUE in Java
+ for (int shardIDX = 0; shardIDX < shardHits.Length; shardIDX++)
{
- availHitCount += shard.ScoreDocs.Length;
- queue.Add(new ShardRef(shardIDX));
- maxScore = Math.Max(maxScore, shard.MaxScore);
- //System.out.println(" maxScore now " + maxScore + " vs " + shard.getMaxScore());
+ TopDocs shard = shardHits[shardIDX];
+ // totalHits can be non-zero even if no hits were
+ // collected, when searchAfter was used:
+ totalHitCount += shard.TotalHits;
+ if (shard.ScoreDocs != null && shard.ScoreDocs.Length > 0)
+ {
+ availHitCount += shard.ScoreDocs.Length;
+ queue.Add(new Shard(shardIDX));
+ maxScore = Math.Max(maxScore, shard.MaxScore);
+ //System.out.println(" maxScore now " + maxScore + " vs " + shard.getMaxScore());
+ }
}
- }
- if (availHitCount == 0)
- {
- maxScore = float.NaN;
- }
+ if (availHitCount == 0)
+ {
+ maxScore = float.NaN;
+ }
- ScoreDoc[] hits;
- if (availHitCount <= start)
- {
- hits = Arrays.Empty<ScoreDoc>();
- }
- else
- {
- hits = new ScoreDoc[Math.Min(size, availHitCount - start)];
- int requestedResultWindow = start + size;
- int numIterOnHits = Math.Min(availHitCount, requestedResultWindow);
- int hitUpto = 0;
- while (hitUpto < numIterOnHits)
+ ScoreDoc[] hits;
+ if (availHitCount <= start)
+ {
+ hits = Arrays.Empty<ScoreDoc>();
+ }
+ else
{
- if (Debugging.AssertsEnabled) Debugging.Assert(queue.Count > 0);
- ShardRef @ref = queue.Pop();
- ScoreDoc hit = shardHits[@ref.ShardIndex].ScoreDocs[@ref.HitIndex++];
- hit.ShardIndex = @ref.ShardIndex;
- if (hitUpto >= start)
+ hits = new ScoreDoc[Math.Min(size, availHitCount - start)];
+ int requestedResultWindow = start + size;
+ int numIterOnHits = Math.Min(availHitCount, requestedResultWindow);
+ int hitUpto = 0;
+ while (hitUpto < numIterOnHits)
{
- hits[hitUpto - start] = hit;
- }
+ if (Debugging.AssertsEnabled) Debugging.Assert(queue.Count > 0);
+ // LUCENENET NOTE: Since we are popping this from the queue and then
+ // adding it back, we properly get our updated HitIndex into the queue.
+ Shard @ref = queue.Pop();
+ ScoreDoc hit = shardHits[@ref.ShardIndex].ScoreDocs[@ref.HitIndex++];
+ hit.ShardIndex = @ref.ShardIndex;
+ if (hitUpto >= start)
+ {
+ hits[hitUpto - start] = hit;
+ }
- //System.out.println(" hitUpto=" + hitUpto);
- //System.out.println(" doc=" + hits[hitUpto].doc + " score=" + hits[hitUpto].score);
+ //System.out.println(" hitUpto=" + hitUpto);
+ //System.out.println(" doc=" + hits[hitUpto].doc + " score=" + hits[hitUpto].score);
- hitUpto++;
+ hitUpto++;
- if (@ref.HitIndex < shardHits[@ref.ShardIndex].ScoreDocs.Length)
- {
- // Not done with this these TopDocs yet:
- queue.Add(@ref);
+ if (@ref.HitIndex < shardHits[@ref.ShardIndex].ScoreDocs.Length)
+ {
+ // Not done with this these TopDocs yet:
+ queue.Add(@ref);
+ }
}
}
- }
- if (sort is null)
- {
- return new TopDocs(totalHitCount, hits, maxScore);
+ if (sort is null)
+ {
+ return new TopDocs(totalHitCount, hits, maxScore);
+ }
+ else
+ {
+ return new TopFieldDocs(totalHitCount, hits, sort.GetSort(), maxScore);
+ }
}
- else
+ finally
{
- return new TopFieldDocs(totalHitCount, hits, sort.GetSort(), maxScore);
+ if (arrayToReturnToPool is not null)
+ ArrayPool<Shard>.Shared.Return(arrayToReturnToPool);
}
+
}
}
}
\ No newline at end of file
diff --git a/src/Lucene.Net/Util/Fst/FST.cs b/src/Lucene.Net/Util/Fst/FST.cs
index 4807a2211..4197a4bb1 100644
--- a/src/Lucene.Net/Util/Fst/FST.cs
+++ b/src/Lucene.Net/Util/Fst/FST.cs
@@ -3,9 +3,12 @@ using J2N.Numerics;
using Lucene.Net.Diagnostics;
using Lucene.Net.Support;
using System;
+using System.Buffers;
using System.Collections.Generic;
+using System.Diagnostics.CodeAnalysis;
using System.IO;
using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
using System.Text;
using JCG = J2N.Collections.Generic;
@@ -1681,38 +1684,60 @@ namespace Lucene.Net.Util.Fst
int topN = Math.Min(maxDerefNodes, inCounts.Count);
// Find top nodes with highest number of incoming arcs:
- FST.NodeQueue q = new FST.NodeQueue(topN);
+ IDictionary<int, int> topNodeMap = null;
- // TODO: we could use more RAM efficient selection algo here...
- FST.NodeAndInCount bottom = null;
- for (int node = 0; node < inCounts.Count; node++)
+#nullable enable
+
+ // LUCENENET: Refactored PriorityQueue<T> subclass into PriorityComparer<T>
+ // implementation, which can be passed into ValuePriorityQueue. ValuePriorityQueue
+ // lives on the stack, and if the array size is small enough, we also allocate the
+ // array on the stack. Fallback to the array pool if it is beyond MaxStackByteLimit.
+ int bufferSize = PriorityQueue.GetArrayHeapSize(topN);
+ bool usePool = FST.NodeAndInCount.ByteSize * bufferSize > Constants.MaxStackByteLimit;
+ FST.NodeAndInCount?[]? arrayToReturnToPool = usePool ? ArrayPool<FST.NodeAndInCount?>.Shared.Rent(bufferSize) : null;
+ try
{
- if (inCounts.Get(node) >= minInCountDeref)
+ Span<FST.NodeAndInCount?> buffer = usePool ? arrayToReturnToPool : stackalloc FST.NodeAndInCount?[bufferSize];
+ var q = new ValuePriorityQueue<FST.NodeAndInCount?>(buffer, FST.NodeComparer.Default);
+#nullable restore
+
+ // TODO: we could use more RAM efficient selection algo here...
+ FST.NodeAndInCount? bottom = null;
+
+ for (int node = 0; node < inCounts.Count; node++)
{
- if (bottom is null)
+ if (inCounts.Get(node) >= minInCountDeref)
{
- q.Add(new FST.NodeAndInCount(node, (int)inCounts.Get(node)));
- if (q.Count == topN)
+ if (!bottom.HasValue)
{
- bottom = q.Top;
+ q.Add(new FST.NodeAndInCount(node, (int)inCounts.Get(node)));
+ if (q.Count == topN)
+ {
+ bottom = q.Top;
+ }
+ }
+ else if (inCounts.Get(node) > bottom.Value.Count)
+ {
+ q.InsertWithOverflow(new FST.NodeAndInCount(node, (int)inCounts.Get(node)));
}
- }
- else if (inCounts.Get(node) > bottom.Count)
- {
- q.InsertWithOverflow(new FST.NodeAndInCount(node, (int)inCounts.Get(node)));
}
}
- }
- // Free up RAM:
- inCounts = null;
+ // Free up RAM:
+ inCounts = null;
- IDictionary<int, int> topNodeMap = new Dictionary<int, int>();
- for (int downTo = q.Count - 1; downTo >= 0; downTo--)
+ topNodeMap = new Dictionary<int, int>(q.Count); // LUCENENET: Allocate the dictionary prior to the loop
+ for (int downTo = q.Count - 1; downTo >= 0; downTo--)
+ {
+ FST.NodeAndInCount? n = q.Pop();
+ topNodeMap[n.Value.Node] = downTo; // LUCENENET: we are bound in the loop by Count, so we won't go past the end and get null here.
+ //System.out.println("map node=" + n.Node + " inCount=" + n.count + " to newID=" + downTo);
+ }
+ }
+ finally
{
- FST.NodeAndInCount n = q.Pop();
- topNodeMap[n.Node] = downTo;
- //System.out.println("map node=" + n.Node + " inCount=" + n.count + " to newID=" + downTo);
+ if (arrayToReturnToPool is not null)
+ ArrayPool<FST.NodeAndInCount?>.Shared.Return(arrayToReturnToPool);
}
// +1 because node ords start at 1 (0 is reserved as stop node):
@@ -2321,53 +2346,63 @@ namespace Lucene.Net.Util.Fst
}
}
- internal class NodeAndInCount : IComparable<NodeAndInCount> // LUCENENET TODO: This is a candidate for a struct
+ [StructLayout(LayoutKind.Sequential)]
+ internal struct NodeAndInCount : IComparable<NodeAndInCount> // LUCENENET specific - made into a struct
{
- internal int Node { get; private set; }
- internal int Count { get; private set; }
+ public const int ByteSize = sizeof(int) + sizeof(int);
+
+ [SuppressMessage("CodeQuality", "IDE0079:Remove unnecessary suppression", Justification = "This is a SonarCloud issue")]
+ [SuppressMessage("Major Code Smell", "S2933:Fields that are only assigned in the constructor should be \"readonly\"", Justification = "Structs are known to have performance issues with readonly fields")]
+ [SuppressMessage("Style", "IDE0044:Add readonly modifier", Justification = "Structs are known to have performance issues with readonly fields")]
+ private int node;
+ [SuppressMessage("CodeQuality", "IDE0079:Remove unnecessary suppression", Justification = "This is a SonarCloud issue")]
+ [SuppressMessage("Major Code Smell", "S2933:Fields that are only assigned in the constructor should be \"readonly\"", Justification = "Structs are known to have performance issues with readonly fields")]
+ [SuppressMessage("Style", "IDE0044:Add readonly modifier", Justification = "Structs are known to have performance issues with readonly fields")]
+ private int count;
+
+ internal int Node => node;
+ internal int Count => count;
public NodeAndInCount(int node, int count)
{
- this.Node = node;
- this.Count = count;
+ this.node = node;
+ this.count = count;
}
- public virtual int CompareTo(NodeAndInCount other)
+ public int CompareTo(NodeAndInCount other)
{
- if (Count > other.Count)
+ if (count > other.count)
{
return 1;
}
- else if (Count < other.Count)
+ else if (count < other.count)
{
return -1;
}
else
{
// Tie-break: smaller node compares as greater than
- return other.Node - Node;
+ return other.node - node;
}
}
}
#nullable enable
- internal class NodeQueue : PriorityQueue<NodeAndInCount>
+ // LUCENENET: Refactored NodeQueue into NodeComparer
+ // implementation, which can be passed into ValuePriorityQueue.
+ internal class NodeComparer : PriorityComparer<NodeAndInCount?>
{
- public NodeQueue(int topN)
- : base(topN) // LUCENENET NOTE: Doesn't pre-populate because sentinelFactory is null
- {
- }
+ public static NodeComparer Default { get; } = new NodeComparer();
- [MethodImpl(MethodImplOptions.AggressiveInlining)]
- protected internal override bool LessThan(NodeAndInCount a, NodeAndInCount b)
+ protected internal override bool LessThan(NodeAndInCount? a, NodeAndInCount? b)
{
- // LUCENENET specific - added guard clauses
- if (a is null)
- throw new ArgumentNullException(nameof(a));
- if (b is null)
- throw new ArgumentNullException(nameof(b));
+ // LUCENENET specific - added guard clauses
+ if (a is null)
+ throw new ArgumentNullException(nameof(a));
+ if (b is null)
+ throw new ArgumentNullException(nameof(b));
- int cmp = a.CompareTo(b);
+ int cmp = a.Value.CompareTo(b.Value);
if (Debugging.AssertsEnabled) Debugging.Assert(cmp != 0);
return cmp < 0;
}
diff --git a/src/Lucene.Net/Util/PriorityQueue.cs b/src/Lucene.Net/Util/PriorityQueue.cs
index 7ae0bc590..9ab1f2f4e 100644
--- a/src/Lucene.Net/Util/PriorityQueue.cs
+++ b/src/Lucene.Net/Util/PriorityQueue.cs
@@ -1,6 +1,8 @@
using J2N.Numerics;
using Lucene.Net.Support;
using System;
+using System.Collections;
+using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
#nullable enable
@@ -31,14 +33,16 @@ namespace Lucene.Net.Util
/// <remarks>
/// This interface can be implemented to provide sentinel
/// instances. The implementation of this interface can be passed to
- /// a constructor of <see cref="PriorityQueue{T}"/>. If an instance
- /// is provided, the <see cref="PriorityQueue{T}"/> constructor will use
- /// the <see cref="Create{TQueue}(TQueue)"/> method to fill the queue,
+ /// a constructor of <see cref="PriorityQueue{T}"/> or <see cref="ValuePriorityQueue{T}"/>.
+ /// If an instance is provided, the either constructor will use
+ /// the <see cref="Create()"/> method to fill the queue,
/// so that code which uses the queue can always assume it is full and only
/// change the top without attempting to insert any new items.
/// <para/>
/// Those sentinel values should always compare worse than any non-sentinel
- /// value (i.e., <see cref="PriorityQueue{T}.LessThan(T, T)"/> should always favor the
+ /// value (i.e., <see cref="PriorityQueue{T}.LessThan(T, T)"/>,
+ /// <see cref="PriorityComparer{T}.LessThan(T, T)"/>, or
+ /// <see cref="IComparer{T}.Compare(T, T)"/> should always favor the
/// non-sentinel values).
/// <para/>
/// When using a <see cref="ISentinelFactory{T}"/>, the following usage pattern
@@ -55,17 +59,14 @@ namespace Lucene.Net.Util
/// pqTop.Change();
/// pqTop = pq.UpdateTop();
/// </code>
- /// <b>NOTE:</b> <see cref="Create{TQueue}(TQueue)"/> will be called by the
- /// <see cref="PriorityQueue{T}"/> constructor <see cref="PriorityQueue{T}.Count"/>
+ /// <b>NOTE:</b> <see cref="Create()"/> will be called by the
+ /// <see cref="PriorityQueue{T}"/> or <see cref="ValuePriorityQueue{T}"/> constructor
+ /// <see cref="PriorityQueue{T}.Count"/> or <see cref="ValuePriorityQueue{T}.Count"/>
/// times, relying on a new instance to be returned. Therefore you should ensure any call to this
- /// <see cref="Create{TQueue}(TQueue)"/> creates a new instance and behaves consistently, e.g., it cannot
+ /// <see cref="Create()"/> creates a new instance and behaves consistently, e.g., it cannot
/// return <c>null</c> if it previously returned non-<c>null</c>.
- /// <para/>
- /// To make implementing this interface easier, it is recommended to use the
- /// <see cref="SentinelFactory{T, TPriorityQueue}"/> abstract class.
/// </remarks>
/// <typeparam name="T">The type of sentinel instance to create.</typeparam>
- /// <seealso cref="SentinelFactory{T, TPriorityQueue}"/>
// LUCENENET specific interface to eliminate the virtual method call in the PriorityQueue<T> constructor.
public interface ISentinelFactory<T>
{
@@ -73,121 +74,365 @@ namespace Lucene.Net.Util
/// Creates a sentinel instance of <typeparamref name="T"/> to fill an element
/// of a <see cref="PriorityQueue{T}"/>.
/// </summary>
- /// <typeparam name="TQueue">The type of priority queue that is calling this method.</typeparam>
- /// <param name="priorityQueue">The <see cref="PriorityQueue{T}"/> instance that is calling this method.
- /// <para/>
- /// <b>NOTE:</b> The call to this method happens in the constructor, so it occurs prior to any
- /// subclass construtor state being set. If you need to access state from your subclass, you should
- /// pass that state into the constructor of the implementation of this interface.</param>
/// <returns>A newly created sentinel instance for use in a single element of <see cref="PriorityQueue{T}"/>.</returns>
- T Create<TQueue>(TQueue priorityQueue) where TQueue : PriorityQueue<T>;
+ T Create();
}
/// <summary>
- /// Provides the sentinel instances of <typeparamref name="T"/> to a
- /// <see cref="PriorityQueue{T}"/>.
- /// </summary>
- /// <remarks>
- /// This class can be extended to provide sentinel
- /// instances. The concrete class instance can be passed to
- /// a constructor of <see cref="PriorityQueue{T}"/>. If an instance
- /// is provided, the <see cref="PriorityQueue{T}"/> constructor will use
- /// the <see cref="Create(TPriorityQueue)"/> method to fill the queue,
- /// so that code which uses the queue can always assume it is full and only
- /// change the top without attempting to insert any new items.
+ /// An adapter comparer for use with <see cref="ValuePriorityQueue{T}"/>.
/// <para/>
- /// Those sentinel values should always compare worse than any non-sentinel
- /// value (i.e., <see cref="PriorityQueue{T}.LessThan(T, T)"/> should always favor the
- /// non-sentinel values).
+ /// This comparer makes it easy to convert <see cref="PriorityQueue{T}"/>-derived
+ /// subclasses into comparers that can be used with <see cref="ValuePriorityQueue{T}"/>.
/// <para/>
- /// When using a <see cref="ISentinelFactory{T}"/>, the following usage pattern
- /// is recommended:
- /// <code>
- /// // Implements ISentinelFactory<T>.Create(PriorityQueue<T>)
- /// var sentinelFactory = new MySentinelFactory<MyObject>();
- /// PriorityQueue<MyObject> pq = new MyQueue<MyObject>(sentinelFactory);
- /// // save the 'top' element, which is guaranteed to not be <c>default</c>.
- /// MyObject pqTop = pq.Top;
- /// <...>
- /// // now in order to add a new element, which is 'better' than top (after
- /// // you've verified it is better), it is as simple as:
- /// pqTop.Change();
- /// pqTop = pq.UpdateTop();
- /// </code>
- /// <b>NOTE:</b> <see cref="Create(TPriorityQueue)"/> will be called by the
- /// <see cref="PriorityQueue{T}"/> constructor <see cref="PriorityQueue{T}.Count"/>
- /// times, relying on a new instance to be returned. Therefore you should ensure any call to this
- /// <see cref="Create(TPriorityQueue)"/> creates a new instance and behaves consistently, e.g., it cannot
- /// return <c>null</c> if it previously returned non-<c>null</c>.
- /// </remarks>
- /// <typeparam name="T">The type of sentinel instance to create.</typeparam>
- /// <typeparam name="TPriorityQueue"></typeparam>
- // LUCENENET specific class to eliminate the virtual method call in the PriorityQueue<T> constructor.
- public abstract class SentinelFactory<T, TPriorityQueue> : ISentinelFactory<T>
- where TPriorityQueue : PriorityQueue<T>
+ /// <b>NOTE:</b> This adapter converts the 2-state <see cref="LessThan(T, T)"/>
+ /// method to the 3-state <see cref="IComparer{T}.Compare(T, T)"/> by always assuming if
+ /// <see cref="LessThan(T, T)"/> returns <c>false</c> that the left node is greater than
+ /// the right node. This means nodes will never compare equal, even if they actually are.
+ /// Therefore, it may not work correctly for most applications of <see cref="IComparer{T}"/>,
+ /// but will work correctly with <see cref="ValuePriorityQueue{T}"/>.
+ /// </summary>
+ /// <typeparam name="T">The type of item to compare. This may be either a value type or a reference type.</typeparam>
+ public abstract class PriorityComparer<T> : IComparer<T>
{
/// <summary>
- /// Creates a sentinel instance of <typeparamref name="T"/> to fill an element
- /// of a <see cref="PriorityQueue{T}"/>.
+ /// Determines the ordering of objects in this priority queue. Subclasses
+ /// must define this one method.
/// </summary>
- /// <param name="priorityQueue">The <see cref="PriorityQueue{T}"/> instance that is calling this method.
- /// <para/>
- /// <b>NOTE:</b> The call to this method happens in the constructor, so it occurs prior to any
- /// subclass construtor state being set. If you need to access state from your subclass, you should
- /// pass that state into the constructor of the implementation of this interface.</param>
- /// <returns></returns>
- public abstract T Create(TPriorityQueue priorityQueue);
- T ISentinelFactory<T>.Create<TQueue>(TQueue priorityQueue)
- => Create((TPriorityQueue)(object)priorityQueue);
+ /// <param name="a">The left value to compare.</param>
+ /// <param name="b">The right value to compare.</param>
+ /// <returns> <c>true</c> if parameter <paramref name="a"/> is less than parameter <paramref name="b"/>; otherwise <c>false</c>. </returns>
+ protected internal abstract bool LessThan(T a, T b);
+
+ int IComparer<T>.Compare(T? a, T? b) => LessThan(a!, b!) ? -1 : 1;
}
/// <summary>
- /// A <see cref="PriorityQueue{T}"/> maintains a partial ordering of its elements such that the
+ /// A <see cref="ValuePriorityQueue{T}"/> maintains a partial ordering of its elements such that the
/// element with least priority can always be found in constant time. Put()'s and Pop()'s
/// require log(size) time.
+ /// <para/>
+ /// This ref struct has the same behavior as <see cref="PriorityQueue{T}"/>, but can be
+ /// used to reduce allocations in scenarios where ref structs are allowed. If the type of
+ /// <typeparamref name="T"/> is a struct the passed in <see cref="Span{T}"/> buffer
+ /// may also be allocated on the stack, as allowed.
///
- /// <para/><b>NOTE</b>: this class will pre-allocate a full array of
- /// length <c>maxSize+1</c> if instantiated with a constructor that
- /// accepts a <see cref="ISentinelFactory{T}"/>. That maximum size can
- /// grow as we insert elements over time.
+ /// <para/><b>NOTE</b>: The allocation size of the supplied <see cref="Span{T}"/> buffer
+ /// must be <c>maxSize+1</c>. The <see cref="PriorityQueue.GetArrayHeapSize(int)"/> method
+ /// can be used to get the correct calculation and to validate bounds of maxSize.
/// <para/>
- /// <b>NOTE</b>: The type of <typeparamref name="T"/> must be either a class
- /// or a nullable value type. Non-nullable value types are not supported and may
- /// produce undefined behavior.
+ /// If instantiated with a constructor that accepts a <see cref="ISentinelFactory{T}"/>,
+ /// that factory will be used to populate the elements of the array.
+ /// <para/>
+ /// <b>NOTE</b>: The type of <typeparamref name="T"/> may be either a class
+ /// or a value type. But do note that it was specifically designed with
+ /// nullable types in mind, so there may be cases where you need to use a
+ /// nullable value type to get it to behave correctly.
/// <para/>
/// @lucene.internal
/// </summary>
-#if FEATURE_SERIALIZABLE
- [Serializable]
-#endif
- public abstract class PriorityQueue<T>
+ public ref struct ValuePriorityQueue<T>
{
- private int size = 0;
- internal readonly int maxSize; // LUCENENET: Internal for testing
- internal T?[] heap; // LUCENENET: Internal for testing
+ private int size;
+ internal int maxSize; // LUCENENET: Internal for testing
+ [SuppressMessage("CodeQuality", "IDE0079:Remove unnecessary suppression", Justification = "This is a SonarCloud issue")]
+ [SuppressMessage("Major Code Smell", "S2933:Fields that are only assigned in the constructor should be \"readonly\"", Justification = "Structs are known to have performance issues with readonly fields")]
+ [SuppressMessage("Style", "IDE0044:Add readonly modifier", Justification = "Structs are known to have performance issues with readonly fields")]
+ private Span<T> heap;
+ [SuppressMessage("CodeQuality", "IDE0079:Remove unnecessary suppression", Justification = "This is a SonarCloud issue")]
+ [SuppressMessage("Major Code Smell", "S2933:Fields that are only assigned in the constructor should be \"readonly\"", Justification = "Structs are known to have performance issues with readonly fields")]
+ [SuppressMessage("Style", "IDE0044:Add readonly modifier", Justification = "Structs are known to have performance issues with readonly fields")]
+ private IComparer<T> comparer;
/// <summary>
- /// Initializes a new instance of <see cref="PriorityQueue{T}"/> with the
- /// specified <paramref name="maxSize"/>.
+ /// Initializes a new instance of <see cref="ValuePriorityQueue{T}"/> with the specified
+ /// <paramref name="buffer"/> and <paramref name="comparer"/>.
/// </summary>
- /// <param name="maxSize">The maximum number of elements this queue can hold.</param>
- protected PriorityQueue(int maxSize) // LUCENENET specific - made protected instead of public
- : this(maxSize, sentinelFactory: null)
+ /// <param name="buffer">The buffer to use for priority queue operations.
+ /// <para/>
+ /// To determine the correct size of buffer to allocate, use the
+ /// <see cref="PriorityQueue.GetArrayHeapSize(int)"/> method.
+ /// </param>
+ /// <param name="comparer">An <see cref="IComparer{T}"/> implementation that is
+ /// used to determine the order of items in the priority queue.
+ /// Note that if the comparer returns 0, the value is treated no differently than
+ /// if it were 1 (greater than).</param>
+ /// <exception cref="ArgumentNullException"><paramref name="comparer"/> is <c>null</c>.</exception>
+ public ValuePriorityQueue(Span<T> buffer, IComparer<T> comparer)
+ : this(buffer, comparer, sentinelFactory: null)
{
}
/// <summary>
- /// Initializes a new instance of <see cref="PriorityQueue{T}"/> with the
- /// specified <paramref name="maxSize"/> and <paramref name="sentinelFactory"/>.
+ /// Initializes a new instance of <see cref="ValuePriorityQueue{T}"/> with the specified
+ /// <paramref name="buffer"/> and <paramref name="comparer"/>.
/// </summary>
- /// <param name="maxSize">The maximum number of elements this queue can hold.</param>
+ /// <param name="buffer">The buffer to use for priority queue operations.
+ /// <para/>
+ /// To determine the correct size of buffer to allocate, use the
+ /// <see cref="PriorityQueue.GetArrayHeapSize(int)"/> method.
+ /// </param>
+ /// <param name="comparer">An <see cref="IComparer{T}"/> implementation that is
+ /// used to determine the order of items in the priority queue.
+ /// Note that if the comparer returns 0, the value is treated no differently than
+ /// if it were 1 (greater than).</param>
/// <param name="sentinelFactory">If not <c>null</c>, the queue will be pre-populated.
- /// This factory will be called <paramref name="maxSize"/> times to get an instance
- /// to provide to each element in the queue.</param>
+ /// This factory will be called <paramref name="buffer"/>.Length - 1 times to get an instance
+ /// to provide to each element in the queue. <paramref name="sentinelFactory"/> should
+ /// return a new instance on each call, but each sentinel instance should consistently
+ /// represent the same value.</param>
+ /// <exception cref="ArgumentNullException"><paramref name="comparer"/> is <c>null</c>.</exception>
/// <seealso cref="ISentinelFactory{T}"/>
- /// <seealso cref="SentinelFactory{T, TPriorityQueue}"/>
- protected PriorityQueue(int maxSize, ISentinelFactory<T>? sentinelFactory)
+ public ValuePriorityQueue(Span<T> buffer, IComparer<T> comparer, ISentinelFactory<T>? sentinelFactory)
+ {
+ this.comparer = comparer ?? throw new ArgumentNullException(nameof(comparer));
+ heap = buffer;
+ // NOTE: we subtract 1 because all access to heap is
+ // 1-based not 0-based. heap[0] is unused.
+ maxSize = buffer.Length - 1;
+ size = 0;
+ // LUCENENET: If we have a sentinel factory, it means we should pre-populate the array
+ // with sentinel values.
+ if (sentinelFactory is not null)
+ {
+ for (int i = 1; i < heap.Length; i++)
+ {
+ heap[i] = sentinelFactory.Create();
+ }
+ size = maxSize;
+ }
+ }
+
+ /// <summary>Returns the underlying storage of the queue.</summary>
+ public Span<T> RawHeap => heap;
+
+ /// <summary>
+ /// Gets the comparer used to determine the order of objects in this priority queue.
+ /// </summary>
+ public IComparer<T> Comparer => comparer;
+
+ /// <summary>
+ /// Determines the ordering of objects in this priority queue.
+ /// </summary>
+ /// <returns><c>true</c> if parameter <paramref name="a"/> is less than parameter
+ /// <paramref name="b"/>; othewise, <c>false</c>.</returns>
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
+ private bool LessThan(T a, T b)
+ => comparer.Compare(a, b) < 0;
+
+#nullable restore
+
+ /// <summary>
+ /// Adds an Object to a <see cref="PriorityQueue{T}"/> in log(size) time. If one tries to add
+ /// more objects than <see cref="maxSize"/> from initialize and it is not possible to resize
+ /// the heap, an <see cref="IndexOutOfRangeException"/> is thrown.
+ /// </summary>
+ /// <returns> The new 'top' element in the queue. </returns>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with PriorityQueue<T>
+ public T Add(T element) // LUCENENET TODO: Factor out the IndexOutOfRangeException here and make a TryAdd() method.
+ {
+ size++;
+ heap[size] = element;
+ UpHeap();
+ return heap[1];
+ }
+
+ /// <summary>
+ /// Adds an Object to a <see cref="PriorityQueue{T}"/> in log(size) time.
+ /// If the given <paramref name="element"/> is smaller than then full
+ /// heap's minimum, it won't be added.
+ /// </summary>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with PriorityQueue<T>
+ public void Insert(T element) // LUCENENET specific - added as a more efficient way to insert value types without reuse
+ {
+ if (size < maxSize)
+ {
+ Add(element);
+ }
+ else if (size > 0 && !LessThan(element, heap[1]))
+ {
+ heap[1] = element;
+ UpdateTop();
+ }
+ }
+
+ /// <summary>
+ /// Adds an Object to a <see cref="PriorityQueue{T}"/> in log(size) time.
+ /// It returns the object (if any) that was
+ /// dropped off the heap because it was full. This can be
+ /// the given parameter (in case it is smaller than the
+ /// full heap's minimum, and couldn't be added), or another
+ /// object that was previously the smallest value in the
+ /// heap and now has been replaced by a larger one, or <c>null</c>
+ /// if the queue wasn't yet full with <see cref="maxSize"/> elements.
+ /// </summary>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with PriorityQueue<T>
+ public T InsertWithOverflow(T element)
+ {
+ if (size < maxSize)
+ {
+ Add(element);
+ return default;
+ }
+ else if (size > 0 && !LessThan(element, heap[1]))
+ {
+ T ret = heap[1];
+ heap[1] = element;
+ UpdateTop();
+ return ret;
+ }
+ else
+ {
+ return element;
+ }
+ }
+
+ /// <summary>
+ /// Returns the least element of the <see cref="PriorityQueue{T}"/> in constant time.
+ /// Returns <c>null</c> if the queue is empty. </summary>
+ public T Top =>
+ // We don't need to check size here: if maxSize is 0,
+ // then heap is length 2 array with both entries null.
+ // If size is 0 then heap[1] is already null.
+ heap[1];
+
+ /// <summary>
+ /// Removes and returns the least element of the <see cref="PriorityQueue{T}"/> in log(size)
+ /// time.
+ /// </summary>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with PriorityQueue<T>
+ public T Pop()
+ {
+ if (size > 0)
+ {
+ T result = heap[1]; // save first value
+ heap[1] = heap[size]; // move last to first
+ heap[size] = default; // permit GC of objects
+ size--;
+ DownHeap(); // adjust heap
+ return result;
+ }
+ else
+ {
+ return default;
+ }
+ }
+
+ /// <summary>
+ /// Should be called when the Object at top changes values. Still log(n) worst
+ /// case, but it's at least twice as fast to
+ ///
+ /// <code>
+ /// pq.Top.Change();
+ /// pq.UpdateTop();
+ /// </code>
+ ///
+ /// instead of
+ ///
+ /// <code>
+ /// o = pq.Pop();
+ /// o.Change();
+ /// pq.Push(o);
+ /// </code>
+ /// </summary>
+ /// <returns> The new 'top' element. </returns>
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with PriorityQueue<T>
+ public T UpdateTop()
{
+ DownHeap();
+ return heap[1];
+ }
+
+ /// <summary>
+ /// Returns the number of elements currently stored in the <see cref="PriorityQueue{T}"/>.
+ /// NOTE: This was size() in Lucene.
+ /// </summary>
+ public int Count => size;
+
+ /// <summary>
+ /// Removes all entries from the <see cref="PriorityQueue{T}"/>. </summary>
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with PriorityQueue<T>
+ public void Clear()
+ {
+ for (int i = 0; i <= size; i++)
+ {
+ heap[i] = default;
+ }
+ size = 0;
+ }
+
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with PriorityQueue<T>
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
+ private void UpHeap()
+ {
+ int i = size;
+ T node = heap[i]; // save bottom node
+ int j = i.TripleShift(1);
+ while (j > 0 && LessThan(node, heap[j]))
+ {
+ heap[i] = heap[j]; // shift parents down
+ i = j;
+ j = j.TripleShift(1);
+ }
+ heap[i] = node; // install saved node
+ }
+
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with PriorityQueue<T>
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
+ private void DownHeap()
+ {
+ int i = 1;
+ T node = heap[i]; // save top node
+ int j = i << 1; // find smaller child
+ int k = j + 1;
+ if (k <= size && LessThan(heap[k], heap[j]))
+ {
+ j = k;
+ }
+ while (j <= size && LessThan(heap[j], node))
+ {
+ heap[i] = heap[j]; // shift up child
+ i = j;
+ j = i << 1;
+ k = j + 1;
+ if (k <= size && LessThan(heap[k], heap[j]))
+ {
+ j = k;
+ }
+ }
+ heap[i] = node; // install saved node
+ }
+ }
+
+#nullable enable
+
+ /// <summary>
+ /// LUCENENET specific static methods for managing priority queues.
+ /// </summary>
+ public static class PriorityQueue
+ {
+ /// <summary>
+ /// Gets the heap size for the specified <paramref name="maxSize"/> of
+ /// a priority queue and checks to ensure it is within bounds.
+ /// <para/>
+ /// Heap size is 1 greater than <paramref name="maxSize"/>, since priority
+ /// queue is 1-based rather than 0-based.
+ /// </summary>
+ /// <param name="maxSize">The maximum length of the priority queue.</param>
+ /// <returns>The heap size to allocate for the priority queue.</returns>
+ /// <exception cref="ArgumentOutOfRangeException">
+ /// <paramref name="maxSize"/> is less than 0.
+ /// <para/>
+ /// -or-
+ /// <para/>
+ /// <paramref name="maxSize"/> is greater than <see cref="ArrayUtil.MAX_ARRAY_LENGTH"/>.
+ /// </exception>
+ public static int GetArrayHeapSize(int maxSize)
+ {
+ if (maxSize < 0)
+ throw new ArgumentOutOfRangeException(nameof(maxSize), "Non-negative number required.");
+
int heapSize;
if (0 == maxSize)
{
@@ -216,6 +461,60 @@ namespace Lucene.Net.Util
heapSize = maxSize + 1;
}
}
+ return heapSize;
+ }
+ }
+
+ /// <summary>
+ /// A <see cref="PriorityQueue{T}"/> maintains a partial ordering of its elements such that the
+ /// element with least priority can always be found in constant time. Put()'s and Pop()'s
+ /// require log(size) time.
+ ///
+ /// <para/><b>NOTE</b>: this class will pre-allocate a full array of
+ /// length <c>maxSize+1</c> if instantiated with a constructor that
+ /// accepts a <see cref="ISentinelFactory{T}"/>. That maximum size can
+ /// grow as we insert elements over time.
+ /// <para/>
+ /// <b>NOTE</b>: The type of <typeparamref name="T"/> may be either a class
+ /// or a value type. But do note that it was specifically designed with
+ /// nullable types in mind, so there may be cases where you need to use a
+ /// nullable value type to get it to behave correctly.
+ /// <para/>
+ /// @lucene.internal
+ /// </summary>
+#if FEATURE_SERIALIZABLE
+ [Serializable]
+#endif
+ public abstract class PriorityQueue<T>
+ {
+ private int size = 0;
+ internal readonly int maxSize; // LUCENENET: Internal for testing
+ internal T?[] heap; // LUCENENET: Internal for testing
+
+ /// <summary>
+ /// Initializes a new instance of <see cref="PriorityQueue{T}"/> with the
+ /// specified <paramref name="maxSize"/>.
+ /// </summary>
+ /// <param name="maxSize">The maximum number of elements this queue can hold.</param>
+ protected PriorityQueue(int maxSize) // LUCENENET specific - made protected instead of public
+ : this(maxSize, sentinelFactory: null)
+ {
+ }
+
+ /// <summary>
+ /// Initializes a new instance of <see cref="PriorityQueue{T}"/> with the
+ /// specified <paramref name="maxSize"/> and <paramref name="sentinelFactory"/>.
+ /// </summary>
+ /// <param name="maxSize">The maximum number of elements this queue can hold.</param>
+ /// <param name="sentinelFactory">If not <c>null</c>, the queue will be pre-populated.
+ /// This factory will be called <paramref name="maxSize"/> times to get an instance
+ /// to provide to each element in the queue. <paramref name="sentinelFactory"/> should
+ /// return a new instance on each call, but each sentinel instance should consistently
+ /// represent the same value.</param>
+ /// <seealso cref="ISentinelFactory{T}"/>
+ protected PriorityQueue(int maxSize, ISentinelFactory<T>? sentinelFactory)
+ {
+ int heapSize = PriorityQueue.GetArrayHeapSize(maxSize);
this.maxSize = maxSize;
this.heap = new T[heapSize];
// LUCENENET: If we have a sentinel factory, it means we should pre-populate the array
@@ -224,7 +523,7 @@ namespace Lucene.Net.Util
{
for (int i = 1; i < heap.Length; i++)
{
- heap[i] = sentinelFactory.Create(this);
+ heap[i] = sentinelFactory.Create();
}
size = maxSize;
}
@@ -233,7 +532,8 @@ namespace Lucene.Net.Util
/// <summary>
/// Determines the ordering of objects in this priority queue. Subclasses
/// must define this one method. </summary>
- /// <returns> <c>true</c> if parameter <paramref name="a"/> is less than parameter <paramref name="b"/>. </returns>
+ /// <returns><c>true</c> if parameter <paramref name="a"/> is less than parameter
+ /// <paramref name="b"/>; othewise, <c>false</c>.</returns>
protected internal abstract bool LessThan(T a, T b); // LUCENENET: Internal for testing
// LUCENENET specific - refactored getSentinelObject() method into ISentinelFactory<T> and
@@ -247,6 +547,7 @@ namespace Lucene.Net.Util
/// the heap, an <see cref="IndexOutOfRangeException"/> is thrown.
/// </summary>
/// <returns> The new 'top' element in the queue. </returns>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with ValuePriorityQueue<T>
public T Add(T element)
{
size++;
@@ -260,6 +561,7 @@ namespace Lucene.Net.Util
/// If the given <paramref name="element"/> is smaller than then full
/// heap's minimum, it won't be added.
/// </summary>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with ValuePriorityQueue<T>
public virtual void Insert(T element) // LUCENENET specific - added as a more efficient way to insert value types without reuse
{
if (size < maxSize)
@@ -283,6 +585,7 @@ namespace Lucene.Net.Util
/// heap and now has been replaced by a larger one, or <c>null</c>
/// if the queue wasn't yet full with <see cref="maxSize"/> elements.
/// </summary>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with ValuePriorityQueue<T>
public virtual T InsertWithOverflow(T element)
{
if (size < maxSize)
@@ -306,6 +609,7 @@ namespace Lucene.Net.Util
/// <summary>
/// Returns the least element of the <see cref="PriorityQueue{T}"/> in constant time.
/// Returns <c>null</c> if the queue is empty. </summary>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with ValuePriorityQueue<T>
public T Top =>
// We don't need to check size here: if maxSize is 0,
// then heap is length 2 array with both entries null.
@@ -316,6 +620,7 @@ namespace Lucene.Net.Util
/// Removes and returns the least element of the <see cref="PriorityQueue{T}"/> in log(size)
/// time.
/// </summary>
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with ValuePriorityQueue<T>
public T Pop()
{
if (size > 0)
@@ -352,6 +657,7 @@ namespace Lucene.Net.Util
/// </summary>
/// <returns> The new 'top' element. </returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with ValuePriorityQueue<T>
public T UpdateTop()
{
DownHeap();
@@ -376,6 +682,8 @@ namespace Lucene.Net.Util
size = 0;
}
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with ValuePriorityQueue<T>
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
private void UpHeap()
{
int i = size;
@@ -390,6 +698,8 @@ namespace Lucene.Net.Util
heap[i] = node; // install saved node
}
+ // LUCENENET: IMPORTANT - this implementation should remain in sync with ValuePriorityQueue<T>
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
private void DownHeap()
{
int i = 1;