Bell Triangle computation in Java

Question

In mathematics, the Bell triangle is a triangle of numbers analogous to Pascal's triangle, whose values count partitions of a set in which a given element is the largest singleton. It is named for its close connection to the Bell numbers, which may be found on both sides of the triangle, and which are in turn named after Eric Temple Bell.

(Wikipedia article)

I have a model class for a Bell Triangle together with a test class below. Similar to my previous question, I have chosen the less conventional method of representing my standard and exception test cases using Enums, only this time my test methods specify the exact inputs for testing.

I would also like to explain first the following line in my compute() method and ask a follow-up question about it:

result[i][j + 1] = result[--i][j] + result[++i][j];

i represents the current row, and j the current field. The original form is probably easier to understand:

result[i][j + 1] = result[i - 1][j] + result[i][j];

To compute the next field of the current row, we need to sum up the current field of the current row and the same field of the previous row. The only reason I ended up with the final version is to arguably make the formula look more symmetric. Have I taken things a little too far, and perhaps stick with the original form?

I also have a second question with regards to my displayTriangle() method in my BellTriangleTest class. I am using Java 8 streams to map each triangle row, with each row of long values (the triangle is a long[][] array after all) being streamed as a LongStream to be in turn collected into a String via Collectors.joining(", "). The String output for each triangle row is then consumed by log::debug. Is there a more fluent way to do this?

Please review the Javadocs and the overall readability of code+test too, as I will like to know if I am being too verbose in these departments.

BellTriangle

/**
 * Computes a Bell Triangle.
 * <p>
 * A Bell Triangle is a triangle of numbers, which count partitions of a set in which a given
 * element is the largest singleton. It is named for its close connection to the Bell numbers, which
 * may be found on both sides of the triangle.
 */
public class BellTriangle implements Cloneable {

    public static final int LIMIT = 24;
    private static final long[] ROW_ZERO = new long[] { 1 };
    private final long[][] triangle;

    /**
     * Computes a triangle up to the number of rows, <code>n</code>.
     *
     * @param n the number of rows, excluding <code>row 0</code>, to compute.
     * @see #compute(int)
     */
    public BellTriangle(int n) {
        triangle = compute(n);
    }

    /**
     * Compute the triangle up to the number of rows, <code>n</code>.
     * <p>
     * The smallest Bell Triangle contains a single-field row, <code>row 0</code>, with the value 1
     * representing the number of partitions for an <em>empty</em> set. Therefore, in computing the
     * triangle for a set of <code>n</code> elements, the resulting array has <code>n + 1</code>
     * rows. Row indices run from 0 to <code>n</code>, inclusive. Field indices also run in the same
     * range. The Bell Number of the triangle is simply the first array value of the
     * <code>n-th</code> row.
     * <p>
     * Due to maximum value of the <code>long</code> datatype, <code>n</code> must not be greater
     * than {@link BellTriangle#LIMIT}.
     *
     * @param n the number of rows, excluding <code>row 0</code>, to compute.
     * @return a two-dimension jagged array representing the computed triangle.
     * @see BellTriangle#LIMIT
     */
    private long[][] compute(int n) {
        if (n < 0 || n > LIMIT) {
            throw new IllegalArgumentException("Input must be between 0 and " + LIMIT
                    + ", inclusive.");
        }
        final long[][] result = new long[++n][];
        result[0] = ROW_ZERO;
        for (int i = 1; i < n; i++) {
            result[i] = new long[i + 1];
            result[i][0] = result[i - 1][i - 1];
            for (int j = 0; j < i; j++) {
                result[i][j + 1] = result[--i][j] + result[++i][j];
            }
        }
        return result;
    }

    /**
     * Gets the size of the triangle, i.e. the value of <code>n</code> used in the constructor.
     *
     * @return the triangle's size.
     */
    public final int getSize() {
        return triangle.length - 1;
    }

    /**
     * Gets the Bell Number for the triangle's size.
     *
     * @return the Bell Number.
     */
    public final long getBellNumber() {
        return triangle[getSize()][0];
    }

    /**
     * Given a positive <code>row</code> and <code>field</code>, return the value within the
     * triangle. Both indices start from zero.
     * <p>
     * <code>row</code> must be equal to or less than the triangle's size, and <code>field</code>
     * must also be equal to or less than <code>row</code>.
     *
     * @param row the row to seek.
     * @param field the field to return.
     * @return the value for the specified <code>row</code> and <code>field</code>.
     */
    public final long getValue(int row, int field) {
        if (row < 0 || field < 0) {
            throw new IllegalArgumentException("Both indices must be greater than 0.");
        }
        if (row > getSize()) {
            throw new IllegalArgumentException("Row index must be " + getSize() + " or less.");
        }
        if (row < field) {
            throw new IllegalArgumentException("Field index must not be greater than row index.");
        }
        return triangle[row][field];
    }

    /**
     * Copies the <code>triangle</code>.
     *
     * @return a copy of the <code>triangle</code>.
     */
    public final long[][] getTriangle() {
        long[][] result = new long[triangle.length][];
        int i = 0;
        for (long[] row : triangle) {
            long[] newRow = new long[row.length];
            System.arraycopy(row, 0, newRow, 0, row.length);
            result[i++] = newRow;
        }
        return result;
    }

    @Override
    public final BellTriangle clone() {
        return new BellTriangle(getSize());
    }

    @Override
    public final boolean equals(Object o) {
        return o instanceof BellTriangle && ((BellTriangle) o).getSize() == getSize();
    }

    @Override
    public final int hashCode() {
        return getSize();
    }

}

BellTriangleTest

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.equalTo;

import java.util.Arrays;
import java.util.Iterator;
import java.util.Objects;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

/**
 * Unit testing for {@link BellTriangle}.
 */
public class BellTriangleTest {

    private static final int SIZE = 5;
    private static final BellTriangle TEST = new BellTriangle(SIZE);
    private static final Logger log = LoggerFactory.getLogger(BellTriangleTest.class);
    private static final String STANDARD = "test-cases";
    private static final String EXCEPTIONS = "exception-test-cases";

    private static enum TestCase {
        ZERO(0, 1), ONE(1, 1), TWO(2, 2), THREE(3, 5), FOUR(4, 15), FIVE(5, 52), SIX(6, 203);

        private final Integer index;
        private final Long result;

        TestCase(int index, long result) {
            this.index = Integer.valueOf(index);
            this.result = Long.valueOf(result);
        }
    }

    private static enum ExceptionTestCase {
        NEG_ROW(-1, 0), NEG_FIELD(0, -1), BAD_ROW(SIZE + 1, 0), BAD_FIELD(0, SIZE + 1);

        private final Integer row;
        private final Integer field;

        ExceptionTestCase(int row, int field) {
            this.row = Integer.valueOf(row);
            this.field = Integer.valueOf(field);
        }
    }

    /**
     * Displays a {@link BellTriangle} using a left-aligned format.
     *
     * @param bellTriangle the {@link BellTriangle} to display.
     */
    private static final void displayTriangle(final BellTriangle bellTriangle) {
        Arrays.stream(bellTriangle.getTriangle())
                .map((row) -> Arrays.stream(row).boxed().map(Object::toString)
                        .collect(Collectors.joining(", "))).forEach(log::debug);
    }

    @DataProvider(name = STANDARD)
    public Iterator<Object[]> getTestCases() {
        return Stream.of(TestCase.values())
                .map((current) -> new Object[] { current.index, current.result }).iterator();
    }

    @Test(dataProvider = STANDARD)
    public void testGetSizeResultAndValue(Integer index, Long expected) {
        final BellTriangle bellTriangle = new BellTriangle(index.intValue());
        assertThat(Integer.valueOf(bellTriangle.getSize()), equalTo(index));
        assertThat(Long.valueOf(bellTriangle.getBellNumber()), equalTo(expected));
        assertThat(Long.valueOf(bellTriangle.getValue(index.intValue(), 0)), equalTo(expected));
        displayTriangle(bellTriangle);
    }

    @DataProvider(name = EXCEPTIONS)
    public Iterator<Object[]> getExceptionTestCases() {
        return Stream.of(ExceptionTestCase.values())
                .map((current) -> new Object[] { current.row, current.field }).iterator();
    }

    @Test(dataProvider = EXCEPTIONS, expectedExceptions = IllegalArgumentException.class)
    public void testExceptions(Integer row, Integer field) {
        TEST.getValue(row.intValue(), field.intValue());
    }

    @Test
    public void testGetTriangle() {
        assertThat("Matching triangles", Arrays.deepEquals(TEST.getTriangle(), TEST.getTriangle()));
        assertThat("Different triangles' references", TEST.getTriangle() != TEST.getTriangle());
    }

    @Test
    public void testTriangles() {
        assertThat("Matching objects", Objects.equals(TEST, TEST.clone()));
        assertThat("Matching objects' hash codes", TEST.hashCode() == TEST.clone().hashCode());
        assertThat("Different objects' references", TEST != TEST.clone());
    }

    public static void main(String[] args) {
        System.out.println("Enter integers between 0 and " + BellTriangle.LIMIT
                + " inclusive, any other inputs to exit.");
        try (Scanner scanner = new Scanner(System.in)) {
            int input = -1;
            while (scanner.hasNextInt() && (input = scanner.nextInt()) >= 0) {
                displayTriangle(new BellTriangle(input));
            }
        }
    }

}

Answer 1

• result[i][j + 1] = result[--i][j] + result[++i][j]; Don't ever use something like that.

  1. You can get into very serious trouble if you modify the code slightly and your -- are not well "aligned" with your ++.
  2. It's less efficient because you are making two useless assignments.

• final long[][] result = new long[++n][]; Same thing as above. That's very dangerous. Just use n + 1.

• You should probably be more verbose on the LIMIT variable name.

• Don't implement Cloneable. That interface was just a big mistake. It is deprecated. If you need that functionality just define a copy constructor.

• In getTriangle(), instead of defining i and looping over the rows, it would be simpler to just loop over i.

• Maybe you should not have the method compute, but just do that work in the constructor. But that's arguable. If you keep it as a separate method, you should make it static.

• I don't really see the need for ROW_ZERO. I think it would be simpler to just define that in compute.

• You should move the code that outputs to console and the main method outside of the test file.

Answer 2

(choosing to provide this as an answer since this may be construed as a 'significant change').

I just noticed I can replace the index of my TestCase enum with ordinal():

private static enum TestCase {
    ZERO(1), ONE(1), TWO(2), THREE(5), FOUR(15), FIVE(52), SIX(203), SEVEN(877), EIGHT(4140);

    private final Integer index;
    private final Long result;

    TestCase(long result) {
        this.index = Integer.valueOf(ordinal());
        this.result = Long.valueOf(result);
    }
}

I also thought of testing two more properties of the Bell Triangle with the enhancement below:

public void testGetSizeResultAndValue(Integer index, Long expected) {
    final int size = index.intValue();
    final BellTriangle bellTriangle = new BellTriangle(size);
    assertThat(Integer.valueOf(bellTriangle.getSize()), equalTo(index));
    assertThat(Long.valueOf(bellTriangle.getBellNumber()), equalTo(expected));
    assertThat(Long.valueOf(bellTriangle.getValue(size, 0)), equalTo(expected));
    if (size == 0) {
        displayTriangle(bellTriangle);
        return;
    }
    assertThat(Long.valueOf(bellTriangle.getValue(size - 1, size - 1)), equalTo(expected));
    final long nextValue = (bellTriangle.getValue(size - 1, 0) + bellTriangle.getBellNumber());
    assertThat(Long.valueOf(bellTriangle.getValue(size, 1)), equalTo(Long.valueOf(nextValue)));
    displayTriangle(bellTriangle);
}

• The last field of the last row is also the Bell Number of the triangle's size.
• The next value is the sum of the current value and the corresponding field of the previous row.

Answer 3

I disagree with some points toto2 stated.

result[i][j + 1] = result[--i][j] + result[++i][j];

This is indeed a terrible idea. Most probably JIT will optimize it away, but some colleague of yours might be tempted to "fix the obvious nonsense" by incrementing j instead. Or you may come to the idea that the operands should be ordered differently.

Or you rewrite it in a different language and it will work sometimes and sometimes not as it's undefined behaviour and the compiler is allowed to do anything it wants, including draining your bank account and formatting your harddisk.

Whenever a variable occurs more than once in a statement, don't change its value.

final long[][] result = new long[++n][];

That's fine for me, though I was prefer move the increment to a more visible place.

Don't implement Cloneable.

It's indeed broken by design, but sometimes handy (I usually override it to return the right type and declare no stupid exception). However, think twice if you make a non-final class Cloneable.

However, you class is immutable (+100 points!), so there's nothing to gain by cloning it.

if (row < 0 || field < 0) {
    throw new IllegalArgumentException("Both indices must be greater than 0.")
}

Your text doesn't match the condition. Use Guava:

checkElementIndex(row, getSize(), "row");
checkArgument(field >= 0, "Field (%s) must be non-negative.", field);
checkArgument(field <= row, "Field (%s) must be less or equal to row (%s).", field, row);

I'm not claiming that my formulation is better than yours. I'd suggest to use formulations similar to the expression, i.e., don't write < and "greater".