# Let's Break Down the Party by Breaking the Party Down Recursively

This is a an overdue alternative implementation on my previous question: Let's Break Down the Party

This alternative uses the int internal representation suggested by @janos and recursion to arrive at the same results. For starters, here are the changes in Denomination enum to support the internal representation:

public enum Denomination {
// values;

static final int MULTIPLIER = 100;

private final BigDecimal value;
private final int centValue; // internal representation
private String description;

private Denomination(double value, final String description) {
this.value = BigDecimal.valueOf(value);
this.centValue = (int) (MULTIPLIER * value);
this.description = Objects.requireNonNull(description);
}

/**
* @return the value in cents
*/
public int getCentValue() {
return centValue;
}

...

}


(I've kept the original BigDecimal value parts of code intact since I am treating the new internal representation as an addition rather than a replacement to the original)

MULTIPLIER_VALUE uses the default (package) access modifier as it is only meant to be visible within the same package, i.e. the Calculator:

public class Calculator {

/**
* Break down the input into {@link Denomination} values by recursion.
*
* @param input the value to break down
* @return an unmodifiable {@link Map} with the {@link Denomination} as keys and a
*         positive integer, the multiplier, as values
*/
public static Map<Denomination, Integer> getBreakdownRecursively(double input) {
return Collections.unmodifiableMap(
recurse(Stream.of(Denomination.values()).iterator(),
(int) (input * Denomination.MULTIPLIER),
new EnumMap<>(Denomination.class)));
}

private static Map<Denomination, Integer> recurse(Iterator<Denomination> iterator,
int input, Map<Denomination, Integer> result) {
if (input == 0 || !iterator.hasNext()) {
return result;
}
Denomination current = iterator.next();
int nextInput = input;
int units = input / current.getCentValue();
if (units != 0) {
result.put(current, Integer.valueOf(units));
nextInput = input % current.getCentValue();
}
return recurse(iterator, nextInput, result);
}

...

}


Rather than continuing encumbering my Denomination enum with the logic to do the 'break down', I have put the very simple calculations within the recurse() method. To showcase the results with the recursion method in the unit test, I have the following changes inside CalculatorTest:

public class CalculatorTest {

@DataProvider(name = "test-cases")
public Iterator<Object[]> getTestCases() {
// return test cases as new Object[] { Double, CaseBuilder }
}

@Test(dataProvider = "test-cases")
public void test(final Double testValue, final CaseBuilder builder) {
doTest(testValue, builder, Calculator::getBreakdown);
}

@Test(dataProvider = "test-cases")
public void testRecursion(final Double testValue, final CaseBuilder builder) {
doTest(testValue, builder, Calculator::getBreakdownRecursively);
}

private void doTest(final Double testValue, final CaseBuilder builder,
final DoubleFunction<Map<Denomination, Integer>> function) {
Stream.of(testValue, builder).forEach(Objects::requireNonNull);
final Map<Denomination, Integer> expected = builder.getExpected();
assertThat(function.apply(testValue.doubleValue()), equalTo(expected));
assertThat(Double.valueOf(Calculator.compute(expected)), equalTo(testValue));
}

...

}


Question

Are there any other improvements for this implementation?

• Your BigDecimal is imprecise since you're creating it from double, rather than from something exact (String or int). Isn't the value of your NICKEL something like 0.050000000000000003? – maaartinus Apr 29 '15 at 3:03
• @maaartinus to be frank that would be a nice comment on the linked question :) For the purposes of this question however, I deal with those minor inconsistencies by sweeping them under the metaphorical MULTIPLIER rug, as @janos did address this in the linked question. TL;DR: the BigDecimal usage is not part of this review. – h.j.k. Apr 29 '15 at 3:34

A small remark.

You made the MULTIPLIER package private for a reason. The problem is when other people will look at your code, they will think it's wrong, and that you forgot to put private there.

It is better to make MULTIPLIER as private and create a getter and setter for it. With the getter/setter you could make the package private, and you can even add into the JavaDoc the reason for the package private.

Getters and setters are normally generated; so if there is no modifier before a getter/setter, then most people will understand that it is needed to be so.

• Wells, we're roughly on the same page when I added my quantize() method... let's cut to the chase and award the bounty! :D – h.j.k. May 6 '15 at 14:43
• @h.j.k. thx for the bounty, even more that I'm surprised to receive it cause the answer was pretty short on a minor thing. – chillworld May 6 '15 at 15:47
• Wells I started the bounty to drive attention towards this... and it worked. :) – h.j.k. May 6 '15 at 15:54

I decided to introduce a quantize() method on Denomination to do the multiplication:

public static int quantize(double input) {
return (int) (input * MULTIPLIER);
}


This changes the Denomination's constructor:

this.centValue = quantize(value);


And the helper method itself:

public static Map<Denomination, Integer> getBreakdownRecursively(double input) {
return recurse(Stream.of(Denomination.values()).iterator(),
Denomination.quantize(input), new EnumMap<>(Denomination.class));
}


As hinted from above, I moved the Collections.unmodifiableMap() call to the last recursion within the recurse() method:

private static Map<Denomination, Integer> recurse(Iterator<Denomination> iterator,
int input, Map<Denomination, Integer> result) {
if (input == 0 || !iterator.hasNext()) {
return Collections.unmodifiableMap(result);
}
Denomination current = iterator.next();
...
}


Now, the original approach described in the question works well and looks simple enough, but what if I went a little deeper with Java 8 features? Looks like a nice place to introduce Map.computeIfAbsent()...

private static Map<Denomination, Integer> recurse(Iterator<Denomination> iterator,
int input, Map<Denomination, Integer> result) {
if (input == 0 || !iterator.hasNext()) {
return Collections.unmodifiableMap(result);
}
Denomination current = iterator.next();
return recurse(iterator, result.computeIfAbsent(current, key ->
Optional.of(Integer.valueOf(input / key.getCentValue()))
.filter(i -> i.intValue() != 0).orElse(null)) == null ?
input : input % current.getCentValue(), result);
}


Sure, readability is sacrificed, but hey, just one return statement! By taking advantage of computeIfAbsent() and its return type, I can optionally store the output of the current iteration's breakdown (when the quotient is not zero), and determine what should be the next value to recuse with (the original input, or the modulus).

edit

I suppose I can improve the readability somewhat by this...

private static Integer getValue(int input) {
// return Optional.of(Integer.valueOf(input))
//                 .filter(i -> i.intValue() != 0).orElse(null);
return input == 0 ? null : Integer.valueOf(input);
}


(fixed that)

The return statement will then read:

private static Map<Denomination, Integer> recurse(Iterator<Denomination> iterator,
int input, Map<Denomination, Integer> result) {
if (input == 0 || !iterator.hasNext()) {
return Collections.unmodifiableMap(result);
}
Denomination current = iterator.next();
return recurse(iterator, result.computeIfAbsent(current, key ->
getValue(input / key.getCentValue())) == null ?
input : input % current.getCentValue(), result);
}