separate the strategys
MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
@@ -13,14 +13,14 @@ public class BranchAndBoundTests
{
/// <summary>Tests that a best found selection is found when an exact solution does not exist.</summary>
[Fact]
- public void CheapestSelection_NoInputCosts()
+ public void MoreSelection_NoInputCosts()
{
long[] inputValues = new long[] { 11, 7, 5, 3, 2 }; // Sum is 28.
long[] inputCosts = new long[] { 0, 0, 0, 0, 0 }; // No input costs. Idealized.
long target = 27; // Target that we cannot get as a sum of input values.
BranchAndBound algorithm = new();
- CheapestSelectionStrategy strategy = new(SuggestionType.More, target, inputValues, inputCosts);
+ MoreSelectionStrategy strategy = new(target, inputValues, inputCosts);
bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.False(wasSuccessful);
@@ -29,7 +29,7 @@ public class BranchAndBoundTests
}
[Fact]
- public void CheapestSelection_ExactMatchIsAlsoCheapest()
+ public void MoreSelection_ExactMatchIsAlsoCheapest()
{
long[] inputValues = new long[] { 35, 17, 10, 5, 3, 2 };
long[] inputCosts = new long[] { 1, 5, 1, 1, 1, 1 };
@@ -37,7 +37,7 @@ public class BranchAndBoundTests
long target = 27;
BranchAndBound algorithm = new();
- CheapestSelectionStrategy strategy = new(SuggestionType.More, target, inputValues, inputCosts);
+ MoreSelectionStrategy strategy = new(target, inputValues, inputCosts);
bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.False(wasSuccessful);
@@ -50,7 +50,7 @@ public class BranchAndBoundTests
}
[Fact]
- public void CheapestSelection_ExactMatchIsExpensive()
+ public void MoreSelection_ExactMatchIsExpensive()
{
long[] inputValues = new long[] { 35, 17, 10, 5, 3, 2 };
@@ -60,7 +60,7 @@ public class BranchAndBoundTests
long target = 27; // Target that we cannot get as a sum of input values.
BranchAndBound algorithm = new();
- CheapestSelectionStrategy strategy = new(SuggestionType.More, target, inputValues, inputCosts);
+ MoreSelectionStrategy strategy = new(target, inputValues, inputCosts);
bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.False(wasSuccessful);
@@ -83,7 +83,7 @@ public class BranchAndBoundTests
long target = 26;
BranchAndBound algorithm = new();
- CheapestSelectionStrategy strategy = new(SuggestionType.Less, target, inputValues, inputCosts);
+ LessSelectionStrategy strategy = new(target, inputValues, inputCosts);
bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.False(wasSuccessful);
@@ -105,7 +105,7 @@ public class BranchAndBoundTests
long target = 32;
BranchAndBound algorithm = new();
- CheapestSelectionStrategy strategy = new(SuggestionType.Less, target, inputValues, inputCosts);
+ LessSelectionStrategy strategy = new(target, inputValues, inputCosts);
bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.False(wasSuccessful);

ADD
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
+namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
+
+public class LessSelectionStrategy : SelectionStrategy
+{
+ public LessSelectionStrategy(long target, long[] inputValues, long[] inputCosts) : base(target, inputValues, inputCosts)
+ {
+ _bestTargetSoFar = long.MinValue;
+ }
+
+ public override EvaluationResult Evaluate(long[] selection, int depth, long sum)
+ {
+ long totalCost = sum + _currentInputCosts;
+
+ if (totalCost > Target)
+ {
+ // Excessive funds, cut the branch.
+ return EvaluationResult.SkipBranch;
+ }
+
+ if (sum + _remainingAmount < _bestTargetSoFar)
+ {
+ // The remaining coins cannot sum up to our solution, so cut the branch.
+ return EvaluationResult.SkipBranch;
+ }
+
+ if (_bestTargetSoFar < totalCost)
+ {
+ _bestSelectionSoFar = selection[0..depth];
+ _bestTargetSoFar = totalCost;
+ }
+
+ if (depth == selection.Length)
+ {
+ // Leaf reached, no match
+ return EvaluationResult.SkipBranch;
+ }
+
+ return EvaluationResult.Continue;
+ }
+}

ADD
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
+namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
+
+public class MoreSelectionStrategy : SelectionStrategy
+{
+ /// <param name="target">Value in satoshis.</param>
+ /// <param name="inputCosts">Costs of spending coins in satoshis.</param>
+ public MoreSelectionStrategy(long target, long[] inputValues, long[] inputCosts) : base(target, inputValues, inputCosts)
+ {
+ _bestTargetSoFar = long.MaxValue;
+ }
+
+ public override EvaluationResult Evaluate(long[] selection, int depth, long sum)
+ {
+ long totalCost = sum + _currentInputCosts;
+
+ if (totalCost > _bestTargetSoFar)
+ {
+ // Our solution is already better than what we might get here.
+ return EvaluationResult.SkipBranch;
+ }
+ else if (sum + _remainingAmount < Target)
+ {
+ // The remaining coins cannot sum up to required target, cut the branch.
+ return EvaluationResult.SkipBranch;
+ }
+ else if (sum >= Target)
+ {
+ if (_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)
+ {
+ // Leaf reached, no match
+ return EvaluationResult.SkipBranch;
+ }
+
+ return EvaluationResult.Continue;
+ }
+}

RENAME
WalletWasabi/Blockchain/TransactionBuilding/BnB/CheapestSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/SelectionStrategy.cs
@@ -7,22 +7,18 @@ 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
+public abstract class SelectionStrategy
{
- private long _currentInputCosts = 0;
- private long _bestTargetSoFar;
- private long[]? _bestSelectionSoFar;
- private long _remainingAmount;
+ public long _currentInputCosts = 0;
+ public long _bestTargetSoFar;
+ public long _remainingAmount;
+ public long[]? _bestSelectionSoFar;
- /// <param name="target">Value in satoshis.</param>
- /// <param name="inputCosts">Costs of spending coins in satoshis.</param>
- public CheapestSelectionStrategy(SuggestionType suggestionType, long target, long[] inputValues, long[] inputCosts)
+ public SelectionStrategy(long target, long[] inputValues, long[] inputCosts)
{
InputCosts = inputCosts;
InputValues = inputValues;
Target = target;
- SuggestionType = suggestionType;
- _bestTargetSoFar = suggestionType == SuggestionType.More ? long.MaxValue : long.MinValue;
_remainingAmount = InputValues.Sum();
}
@@ -38,9 +34,6 @@ public class CheapestSelectionStrategy
/// <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();
- // <summary>Suggestion type affecting whether selection sums to a larger or a smaller sum than the target.</summary>
- private SuggestionType SuggestionType { get; }
-
/// <summary>
/// Modifies selection sum so that we don't need to recompute it.
/// </summary>
@@ -49,7 +42,7 @@ public class CheapestSelectionStrategy
/// <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)
+ public virtual long ProcessAction(NextAction action, long[] selection, int depth, long oldSum)
{
long newSum;
@@ -86,73 +79,5 @@ public class CheapestSelectionStrategy
/// <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;
-
- if (SuggestionType is SuggestionType.More)
- {
- if (totalCost > _bestTargetSoFar)
- {
- // Our solution is already better than what we might get here.
- return EvaluationResult.SkipBranch;
- }
- else if (sum + _remainingAmount < Target)
- {
- // The remaining coins cannot sum up to required target, cut the branch.
- return EvaluationResult.SkipBranch;
- }
- else if (sum >= Target)
- {
- if (_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)
- {
- // Leaf reached, no match
- return EvaluationResult.SkipBranch;
- }
-
- return EvaluationResult.Continue;
- }
- else if (SuggestionType is SuggestionType.Less)
- {
- if (totalCost > Target)
- {
- // Excessive funds, cut the branch.
- return EvaluationResult.SkipBranch;
- }
-
- if (sum + _remainingAmount < _bestTargetSoFar)
- {
- // The remaining coins cannot sum up to our solution, so cut the branch.
- return EvaluationResult.SkipBranch;
- }
-
- if (_bestTargetSoFar < totalCost)
- {
- _bestSelectionSoFar = selection[0..depth];
- _bestTargetSoFar = totalCost;
- }
-
- if (depth == selection.Length)
- {
- // Leaf reached, no match
- return EvaluationResult.SkipBranch;
- }
-
- return EvaluationResult.Continue;
- }
- else
- {
- throw new NotImplementedException($"{SuggestionType} suggestion type is not supported.");
- }
- }
+ public abstract EvaluationResult Evaluate(long[] selection, int depth, long sum);
}

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(CheapestSelectionStrategy searchStrategy, [NotNullWhen(true)] out List<long>? selectedValues, CancellationToken cancellationToken = default)
+ public bool TryGetMatch(SelectionStrategy searchStrategy, [NotNullWhen(true)] out List<long>? selectedValues, CancellationToken cancellationToken = default)
{
selectedValues = null;
@@ -45,7 +45,7 @@ public class BranchAndBound
return false;
}
- private bool TryFindSolution(CheapestSelectionStrategy searchStrategy, [NotNullWhen(true)] out long[]? selection, CancellationToken cancellationToken = default)
+ private bool TryFindSolution(SelectionStrategy searchStrategy, [NotNullWhen(true)] out long[]? selection, CancellationToken cancellationToken = default)
{
// Current selection sum.
long sum = 0L;

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
@@ -44,7 +44,7 @@ public static class ChangelessTransactionCoinSelector
long[] inputValues = inputEffectiveValues.Values.ToArray();
BranchAndBound branchAndBound = new();
- CheapestSelectionStrategy strategy = new(suggestionType, target, inputValues, inputCosts);
+ SelectionStrategy strategy = suggestionType == SuggestionType.More ? new MoreSelectionStrategy(target, inputValues, inputCosts) : new LessSelectionStrategy(target, inputValues, inputCosts);
var foundExactMatch = branchAndBound.TryGetMatch(strategy, out List<long>? solution, cancellationToken);

separate the strategys