Make it iterative instead of recursive
MODIFY
WalletWasabi.Tests/UnitTests/WabiSabi/Client/GreedyDecomposerTests.cs
WalletWasabi.Tests/UnitTests/WabiSabi/Client/GreedyDecomposerTests.cs
@@ -29,12 +29,12 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
[InlineData(18, new long[] { 10, 5, 2, 1 })]
[InlineData(19, new long[] { 10, 5, 2, 2 })]
[InlineData(38, new long[] { 10, 10, 10, 5, 2, 1 })]
- public void Decompose1Test(int amount, long[] expected)
+ public void Decompose1Test(long amount, long[] expected)
{
- var decomposer = new GreedyDecomposer(new long[] { 1, 2, 5, 10 });
- var amounts = decomposer.Decompose(amount);
- Assert.Equal(amount, amounts.Sum());
- Assert.Equal(expected, amounts);
+ var decomposer = new GreedyDecomposer(new Money[] { new (1L), new (2L), new (5L), new (10L) });
+ var amounts = decomposer.Decompose(Money.Satoshis(amount));
+ Assert.Equal(Money.Satoshis(amount), amounts.Sum());
+ Assert.Equal(expected, amounts.Select(x => x.Satoshi));
}
[Theory]
@@ -59,12 +59,12 @@ namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
[InlineData(18, new long[] { 11, 3, 3, 1 })]
[InlineData(19, new long[] { 11, 3, 3, 1, 1 })]
[InlineData(38, new long[] { 11, 11, 11, 3, 1, 1 })]
- public void Decompose2Test(int amount, long[] expected)
+ public void Decompose2Test(long amount, long[] expected)
{
- var decomposer = new GreedyDecomposer(new long[] { 1, 3, 11 });
- var amounts = decomposer.Decompose(amount);
- Assert.Equal(amount, amounts.Sum());
- Assert.Equal(expected, amounts);
+ var decomposer = new GreedyDecomposer(new Money[] { new (1L), new (3L), new (11L) });
+ var amounts = decomposer.Decompose(Money.Satoshis(amount));
+ Assert.Equal(Money.Satoshis(amount), amounts.Sum());
+ Assert.Equal(expected, amounts.Select(x => x.Satoshi));
}
}
}

MODIFY
WalletWasabi/WabiSabi/Client/GreedyDecomposer.cs
WalletWasabi/WabiSabi/Client/GreedyDecomposer.cs
@@ -2,30 +2,42 @@ using System.Linq;
using System.Collections.Generic;
using System.Collections.Immutable;
using System;
+using NBitcoin;
namespace WalletWasabi.WabiSabi.Client
{
public class GreedyDecomposer
{
- public GreedyDecomposer(IEnumerable<long> denominations)
+ public GreedyDecomposer(IEnumerable<Money> denominations)
{
_denominations = denominations.Any()
? denominations.OrderByDescending(x => x).ToImmutableList()
: throw new ArgumentException($"Argument {nameof(denominations)} has no elements");
}
- private ImmutableList<long> _denominations;
+ private ImmutableList<Money> _denominations;
- public IEnumerable<long> Decompose(long amount) =>
- Decompose(amount, _denominations.First(), _denominations.Skip(1), Enumerable.Empty<long>());
-
- private static IEnumerable<long> Decompose(long amount, long denomination, IEnumerable<long> denominations, IEnumerable<long> acc) =>
- (amount - denomination, denominations.Any()) switch
+ public IEnumerable<Money> Decompose(Money amount)
+ {
+ var i = 0;
+ var denomination = _denominations[i];
+ while (amount > Money.Zero)
+ {
+ if (denomination <= amount)
+ {
+ yield return denomination;
+ amount -= denomination;
+ }
+ else if(++i < _denominations.Count)
{
- (0 or > 0, _) => Decompose(amount - denomination, denomination, denominations, acc.Append(denomination)),
- (< 0, true) => Decompose(amount, denominations.First(), denominations.Skip(1), acc),
- _ => acc
- };
+ denomination = _denominations[i];
+ }
+ else
+ {
+ yield return amount;
+ }
+ }
+ }
}
}

Make it iterative instead of recursive