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.
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 Enum
s, 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));
}
}
}
}
--i;++i
on my local copy based on both of your feedback too. Will think about an answer to accept if there isn't any more some time tomorrow... \$\endgroup\$