Remove abstraction, we only have one strategy
DELETE
WalletWasabi/Blockchain/TransactionBuilding/BnB/BaseStrategy.cs
-using System.Linq;
-
-namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
-
-public abstract class BaseStrategy : ISearchStrategy
-{
- /// <param name="inputValues">All values must be strictly positive and in descending order.</param>
- public BaseStrategy(long target, long[] inputValues)
- {
- Target = target;
-
- if (inputValues.Length == 0)
- {
- throw new ArgumentException("List is empty.");
- }
-
- if (inputValues.Any(x => x <= 0))
- {
- throw new ArgumentException("Only strictly positive values are supported.");
- }
-
- InputValues = inputValues.OrderByDescending(x => x).ToArray();
-
- if (!inputValues.SequenceEqual(InputValues))
- {
- throw new ArgumentException("Input values must be sorted in descending order.");
- }
- }
-
- /// <summary>Target value we want to, ideally, sum up from the input values.</summary>
- public long Target { get; }
-
- /// <summary>Input values sorted in descending orders.</summary>
- public long[] InputValues { get; }
-
- /// <inheritdoc/>
- public virtual long ProcessAction(NextAction action, long[] selection, int depth, long oldSum)
- {
- long newSum;
-
- if (action == NextAction.IncludeFirstThenOmit || action == NextAction.Include)
- {
- selection[depth] = InputValues[depth];
- newSum = oldSum + selection[depth];
- }
- else if (action == NextAction.OmitFirstThenInclude || action == NextAction.Omit)
- {
- newSum = oldSum - selection[depth];
- selection[depth] = 0;
- }
- else
- {
- newSum = oldSum - selection[depth];
- selection[depth] = 0;
- }
-
- return newSum;
- }
-
- /// <inheritdoc/>
- public abstract EvaluationResult Evaluate(long[] selection, int count, long sum);
-}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/CheapestSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/CheapestSelectionStrategy.cs
@@ -7,7 +7,7 @@ namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
/// waste of user's fund by looking for a selection that minimizes inputs' spending costs
/// and extra cost of paying more than specified target.
/// </summary>
-public class CheapestSelectionStrategy : BaseStrategy
+public class CheapestSelectionStrategy
{
private long _currentInputCosts = 0;
private long _bestTargetSoFar = long.MaxValue;
@@ -16,19 +16,33 @@ public class CheapestSelectionStrategy : BaseStrategy
/// <param name="target">Value in satoshis.</param>
/// <param name="inputSpendingCosts">Costs of spending coins in satoshis.</param>
public CheapestSelectionStrategy(long target, long[] inputValues, long[] inputSpendingCosts)
- : base(target, inputValues)
{
InputCosts = inputSpendingCosts;
+ InputValues = inputValues;
+ Target = target;
}
/// <summary>Costs corresponding to <see cref="ISearchStrategy.InputValues"/> values.</summary>
public long[] InputCosts { get; }
+ /// <summary>Target value we want to, ideally, sum up from the input values.</summary>
+ public long Target { get; }
+
+ /// <summary>Input values sorted in descending orders.</summary>
+ public long[] InputValues { get; }
+
/// <summary>Gives lowest found value selection whose sum is larger than or equal to <see cref="ISearchStrategy.Target"/>.</summary>
public long[]? GetBestSelectionFound() => _bestSelectionSoFar?.Where(x => x > 0).ToArray();
- /// <inheritdoc/>
- public override long ProcessAction(NextAction action, long[] selection, int depth, long oldSum)
+ /// <summary>
+ /// Modifies selection sum so that we don't need to recompute it.
+ /// </summary>
+ /// <param name="action">Current action of the BnB algorithm.</param>
+ /// <param name="selection">Currently selected values. <c>0</c> when the corresponding value is not selected.</param>
+ /// <param name="depth">Index of a <paramref name="selection"/> value that is currently being included / omitted.</param>
+ /// <param name="oldSum">Previous sum value.</param>
+ /// <returns>New selection sum.</returns>
+ public long ProcessAction(NextAction action, long[] selection, int depth, long oldSum)
{
long newSum;
@@ -66,8 +80,14 @@ public class CheapestSelectionStrategy : BaseStrategy
return newSum;
}
- /// <inheritdoc/>
- public override EvaluationResult Evaluate(long[] selection, int depth, long sum)
+ /// <summary>
+ /// Evaluation function that evaluates each step of the Branch and Bound algorithm and
+ /// tells the algorithm what to do next.
+ /// </summary>
+ /// <param name="selection">Currently selected values. <c>0</c> when the corresponding value is not selected.</param>
+ /// <param name="depth">Number of <paramref name="selection"/> elements that contains the current solution.</param>
+ /// <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;

ADD
WalletWasabi/Blockchain/TransactionBuilding/BnB/EvaluationResult.cs
+namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
+
+public enum EvaluationResult
+{
+ /// <summary>Select a value to the selection and continue on.</summary>
+ Continue,
+
+ /// <summary>Omit a value from the selection.</summary>
+ SkipBranch,
+
+ /// <summary>Match was found!</summary>
+ Match
+}

DELETE
WalletWasabi/Blockchain/TransactionBuilding/BnB/ISearchStrategy.cs
-namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
-
-/// <summary>
-/// Search strategy for Branch and Bound algorithm.
-/// </summary>
-public interface ISearchStrategy
-{
- /// <summary>Target value we want to, ideally, sum up from the input values.</summary>
- long Target { get; }
-
- long[] InputValues { get; }
-
- /// <summary>
- /// Modifies selection sum so that we don't need to recompute it.
- /// </summary>
- /// <param name="action">Current action of the BnB algorithm.</param>
- /// <param name="selection">Currently selected values. <c>0</c> when the corresponding value is not selected.</param>
- /// <param name="depth">Index of a <paramref name="selection"/> value that is currently being included / omitted.</param>
- /// <param name="oldSum">Previous sum value.</param>
- /// <returns>New selection sum.</returns>
- long ProcessAction(NextAction action, long[] selection, int depth, long oldSum);
-
- /// <summary>
- /// Evaluation function that evaluates each step of the Branch and Bound algorithm and
- /// tells the algorithm what to do next.
- /// </summary>
- /// <param name="selection">Currently selected values. <c>0</c> when the corresponding value is not selected.</param>
- /// <param name="count">Number of <paramref name="selection"/> elements that contains the current solution.</param>
- /// <param name="sum">Sum of first <paramref name="count"/> elements of <paramref name="selection"/>.</param>
- EvaluationResult Evaluate(long[] selection, int count, long sum);
-}
-
-public enum EvaluationResult
-{
- /// <summary>Select a value to the selection and continue on.</summary>
- Continue,
-
- /// <summary>Omit a value from the selection.</summary>
- SkipBranch,
-
- /// <summary>Match was found!</summary>
- Match
-}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
@@ -18,7 +18,7 @@ public class BranchAndBound
/// <param name="searchStrategy">Search strategy that affects how the algorithm searches through the options.</param>
/// <param name="selectedValues">Solution of the search algorithm based on <paramref name="searchStrategy"/> sorted in descending order.</param>
/// <returns><c>true</c> when a match is found, <c>false</c> otherwise.</returns>
- public bool TryGetMatch(ISearchStrategy searchStrategy, [NotNullWhen(true)] out List<long>? selectedValues, CancellationToken cancellationToken = default)
+ public bool TryGetMatch(CheapestSelectionStrategy searchStrategy, [NotNullWhen(true)] out List<long>? selectedValues, CancellationToken cancellationToken = default)
{
selectedValues = null;
@@ -45,7 +45,7 @@ public class BranchAndBound
return false;
}
- private bool TryFindSolution(ISearchStrategy searchStrategy, [NotNullWhen(true)] out long[]? selection, CancellationToken cancellationToken = default)
+ private bool TryFindSolution(CheapestSelectionStrategy searchStrategy, [NotNullWhen(true)] out long[]? selection, CancellationToken cancellationToken = default)
{
// Current selection sum.
long sum = 0L;

Remove abstraction, we only have one strategy