Re-implement "remaining amounts" handling
MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/CheapestSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/CheapestSelectionStrategy.cs
@@ -9,10 +9,6 @@ namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
/// </summary>
public class CheapestSelectionStrategy
{
- private long _currentInputCosts = 0;
- private long _bestTargetSoFar = long.MaxValue;
- private long[]? _bestSelectionSoFar;
-
/// <param name="target">Value in satoshis.</param>
/// <param name="inputCosts">Costs of spending coins in satoshis.</param>
public CheapestSelectionStrategy(long target, long[] inputValues, long[] inputCosts)
@@ -20,6 +16,16 @@ public class CheapestSelectionStrategy
InputCosts = inputCosts;
InputValues = inputValues;
Target = target;
+ BestTargetSoFar = long.MaxValue;
+
+ RemainingAmounts = new long[inputValues.Length];
+ long accumulator = InputValues.Sum();
+
+ for (int i = 0; i < inputValues.Length; i++)
+ {
+ accumulator -= inputValues[i];
+ RemainingAmounts[i] = accumulator;
+ }
}
/// <summary>Costs corresponding to <see cref="InputValues"/> values.</summary>
@@ -32,7 +38,19 @@ public class CheapestSelectionStrategy
public long[] InputValues { get; }
/// <summary>Gives lowest found value selection whose sum is larger than or equal to <see cref="Target"/>.</summary>
- public long[]? GetBestSelectionFound() => _bestSelectionSoFar?.Where(x => x > 0).ToArray();
+ public long[]? GetBestSelectionFound() => BestSelectionSoFar?.Where(x => x > 0).ToArray();
+
+ /// <summary>Input cost(s) of the current selection.</summary>
+ private long CurrentInputCosts { get; set; } = 0;
+
+ /// <summary>Sum of the selectable/remaining coins.</summary>
+ private long[] RemainingAmounts { get; set; }
+
+ /// <summary>Sum of the best found selection.</summary>
+ private long BestTargetSoFar { get; set; }
+
+ /// <summary>Best coin selection so far.</summary>
+ private long[]? BestSelectionSoFar { get; set; }
/// <summary>
/// Modifies selection sum so that we don't need to recompute it.
@@ -50,7 +68,7 @@ public class CheapestSelectionStrategy
{
if (selection[depth] == 0)
{
- _currentInputCosts += InputCosts[depth];
+ CurrentInputCosts += InputCosts[depth];
}
selection[depth] = InputValues[depth];
@@ -60,7 +78,7 @@ public class CheapestSelectionStrategy
{
if (selection[depth] > 0)
{
- _currentInputCosts -= InputCosts[depth];
+ CurrentInputCosts -= InputCosts[depth];
}
newSum = oldSum - selection[depth];
@@ -79,26 +97,34 @@ public class CheapestSelectionStrategy
/// <param name="sum">Sum of first <paramref name="depth"/> elements of <paramref name="selection"/>.</param>
public EvaluationResult Evaluate(long[] selection, int depth, long sum)
{
- long totalCost = sum + _currentInputCosts;
+ long totalCost = sum + CurrentInputCosts;
- if (totalCost > _bestTargetSoFar)
+ if (totalCost > BestTargetSoFar)
{
// Our solution is already better than what we might get here.
return EvaluationResult.SkipBranch;
}
- else if (sum >= Target)
+
+ if (sum >= Target)
{
- if (_bestTargetSoFar > totalCost)
+ if (BestTargetSoFar > totalCost)
{
- _bestSelectionSoFar = selection[0..depth];
- _bestTargetSoFar = totalCost;
+ BestSelectionSoFar = selection[0..depth];
+ BestTargetSoFar = totalCost;
}
// Even if a match occurred we cannot be sure that there isn't
// a better selection thanks to input costs.
return EvaluationResult.SkipBranch;
}
- else if (depth == selection.Length)
+
+ if (sum + RemainingAmounts[depth - 1] < Target)
+ {
+ // The remaining coins cannot sum up to required target, cut the branch.
+ return EvaluationResult.SkipBranch;
+ }
+
+ if (depth == selection.Length)
{
// Leaf reached, no match
return EvaluationResult.SkipBranch;

Re-implement "remaining amounts" handling

Co-authored-by: adamPetho <45069029+adamPetho@users.noreply.github.com>