11
\$\begingroup\$

I was working on representing a large List of information on a number of different pages, and a colleague of mine suggested that I try to make a generic method for the task I was trying to perform:

private <T> List<List<T>> listSplitter(List<T> originalList, int splitCount) {
    List<List<T>> listOfLists= new ArrayList<>();
    listOfLists.add(new ArrayList<>());

    int originalListSize = originalList.size();     
    int index = 0;
    int pageNumber = 0;
    int numItemsAdded = 0;

    while (index < originalListSize) {
        if (numItemsAdded > splitCount - 1) {
            numItemsAdded = 0;
            pageNumber ++;
            listOfLists.add(new ArrayList<>());
        }
        List activeList = listOfLists.get(pageNumber);
        activeList.add(originalList.get(index));
        numItemsAdded++;
        index++;
    }

    return listOfLists;
}

This correctly splits a list of objects into any number of lists based on the desired number of objects per list. I would love to get feedback on this method, as I am new to Java generics.

\$\endgroup\$
11
\$\begingroup\$

Compiler Warning

This line gives you a compiler warning because it's not using generics:

List activeList = listOfLists.get(pageNumber);

it should be

List<T> activeList = listOfLists.get(pageNumber);

Empty list input

If the input is an empty list, then the output will be a list containing one empty list. I think it would be more reasonable if the output itself was an empty list.

This can be solved by only adding a list if the number of items added is more than zero.


splitCount <= 0

If I give the method a zero or negative value for splitCount, then the output will look like this:

[[], [0], [1], [2], [3], [4], [5]]

The proper response would be to throw an Exception. That value just shouldn't be zero or less.


Iterator

As your code is iterating through a list, it could use the Iterator for the list instead of using the indexes. For a LinkedList, the performance of get is very slow, so always using Iterator would give a significantly faster performance for such lists, and is a good practice even on ArrayList.


activeList

Currently you keep track of a 'pageNumber' and for each item you add, you get the list with that page number. It would be better to declare the activeList on the function-scope instead of inside the scope of the for-loop. Then you can change the activeList variable when needed, i.e. inside your if statement.


if (numItemsAdded > splitCount - 1) {

This if-statement would be a lot easier to grasp if it was

if (numItemsAdded >= splitCount) {

There is no need to introduce the - 1 when you can just change the operator.


My final code:

With the above in mind, here's what I ended up with:

private static <T> List<List<T>> listSplitter(List<T> originalList, int resultsPerList) {
    if (resultsPerList <= 0) {
        throw new IllegalArgumentException("resultsPerList must be positive");
    }
    List<List<T>> listOfLists = new ArrayList<>();
    List<T> latestList = new ArrayList<>();
    Iterator<T> iterator = originalList.iterator();

    while (iterator.hasNext()) {
        T next = iterator.next();
        if (latestList.size() >= resultsPerList) {
            listOfLists.add(latestList);
            latestList = new ArrayList<T>();
        } 
        latestList.add(next);
    }

    if (!latestList.isEmpty()) {
        listOfLists.add(latestList);
    }

    return listOfLists;
}
\$\endgroup\$
8
\$\begingroup\$

There have been a number of answers, and they all provide very good input. Both Simon and Janos suggest answers that are similar, you have a list-of-lists, and you have a 'current' list that you will with values.

The concept is good, but, if you reverse the logic slightly, you can neaten up the code and remove the 'terminal' if-condition. Consider this code:

private <T> List<List<T>> listSplitter(List<T> originalList, int splitCount) {
    List<List<T>> listOfLists = new ArrayList<>();
    List<T> current = new ArrayList<>(splitCount);
    listOfLists.add(current);

    for (T item : originalList) {
        if (current.size() == splitCount) {
            current = new ArrayList<>(splitCount);
            listOfLists.add(current);
        }
        current.add(item);
    }

    return listOfLists;
}

By pre-adding the current in this way to the listOfLists you caan be guaranteed it is never empty, and thus there is no need for the check.

It just 'works'.

\$\endgroup\$
  • \$\begingroup\$ Good point! +1 Btw, in the meantime I changed my answer to use .subList instead of walking over all elements, which naturally eliminated that redundant check. (though, I have another redundancy now, which I'm sure you will spot ;-) \$\endgroup\$ – janos Oct 10 '14 at 5:13
  • \$\begingroup\$ Isn't this pretty much how the original code worked? I added the last if check to avoid returning an empty list containing an empty list. \$\endgroup\$ – Simon Forsberg Oct 10 '14 at 7:21
  • \$\begingroup\$ @SimonAndréForsberg - in terms of algorithm, it is close, except it does not use any index, counter, or page number variables. The part that makes the difference is the 'current' variable which only holds the most recently used page. Additionally, doing it the way I do it means there is no need for the empty-list-check because the last page will never be empty (unless the input data is empty). \$\endgroup\$ – rolfl Oct 10 '14 at 10:29
  • \$\begingroup\$ So your answer and mine is pretty much the same, except how we handle empty input data. \$\endgroup\$ – Simon Forsberg Oct 10 '14 at 10:38
  • \$\begingroup\$ @Simon - no, the key difference is that you only add a list if it has data, whereas I always add the list. I add the list before the loop, and I always add the list inside the loop on the page-change. That reversal is the key to my answer \$\endgroup\$ – rolfl Oct 10 '14 at 10:50
8
\$\begingroup\$

Naming

A better name for this functionality would be partition, like it is in Guava's Lists.partition.

Handling invalid / strange arguments

There are several possible invalid / strange inputs to consider:

  • size < 1: invalid input, the natural response is to throw IllegalArgumentException
  • original list is empty or null: strange input, you might even consider invalid. However, returning an empty collection with no partitions inside should be safe enough, whether to raise an exception or not is less obvious in this case
  • original list is smaller than target partition size: a bit strange input, it might be good to return early with the original list wrapped in another list, rather than walking over all elements, or mistakenly allocating an oversized segment

Other optimizations

When building the partitions, it would be more efficient to specify the expected size for the partition, to avoid dynamic resizing of the ArrayList while building it.

Similarly, it can be a good idea to specify the expected size of the outer List too that will contain the partitions.

Instead of walking over all items to create the partitions, it would be more efficient to use .subList to add the segments directly.

Suggested implementation

Putting the above tips together:

public static <T> List<List<T>> partition(List<T> orig, int size) {
    if (size < 1) {
        throw new IllegalArgumentException("The target partition size must be at least 1");
    }
    if (orig == null) {
        return Collections.emptyList();
    }
    int origSize = orig.size();
    List<List<T>> result = new ArrayList<>(origSize / size + 1);
    for (int i = 0; i < origSize; i += size) {
        result.add(orig.subList(i, Math.min(i + size, origSize)));
    }
    return result;
}

As @skiwi pointed out:

subList() only takes a view of the list, meaning that things can break in strange ways if the original list is operated on later. You could solve this by forcing a copy at the start for example.

If, in your use case it's important to protect against mutation of the original list, then you could change the line using .subList to force a copy like this:

result.add(new ArrayList<T>(orig.subList(i, Math.min(i + size, origSize))));

Or using an unmodifiable list can be an interesting option too:

result.add(Collections.unmodifiableList(orig.subList(i, Math.min(i + size, origSize))));

However, don't do this if it's not necessary, and benefit from the good performance of sub-lists.

Unit tests

A task of this complexity definitely deserves some unit tests:

@Test
public void testPartitionEmpty() {
    assertEquals(Collections.EMPTY_LIST, partition(Arrays.asList(), 3));
}

@Test
public void testPartitionNull() {
    assertEquals(Collections.EMPTY_LIST, partition(null, 3));
}

@Test(expected = IllegalArgumentException.class)
public void testPartitionZeroSize() {
    partition(Arrays.asList(1, 2, 3), 0);
}

@Test(expected = IllegalArgumentException.class)
public void testPartitionNegativeSize() {
    partition(Arrays.asList(1, 2, 3), -3);
}

@Test
public void testPartitionInts() {
    assertEquals(
            Arrays.asList(
                    Arrays.asList(1, 2),
                    Arrays.asList(3, 4),
                    Arrays.asList(5)),
            partition(Arrays.asList(1, 2, 3, 4, 5), 2));
}

@Test
public void testPartitionStrings() {
    assertEquals(
            Arrays.asList(
                    Arrays.asList("1", "2"),
                    Arrays.asList("3", "4"),
                    Arrays.asList("5")),
            partition(Arrays.asList("1", "2", "3", "4", "5"), 2));
}

@Test
public void testPartition_MultipleOfSize() {
    assertEquals(
            Arrays.asList(
                    Arrays.asList(1, 2),
                    Arrays.asList(3, 4)),
            partition(Arrays.asList(1, 2, 3, 4), 2));
}

@Test
public void testPartition_Size1() {
    assertEquals(
            Arrays.asList(
                    Arrays.asList(1),
                    Arrays.asList(2),
                    Arrays.asList(3),
                    Arrays.asList(4)),
            partition(Arrays.asList(1, 2, 3, 4), 1));
}

@Test
public void testPartition_BiggerSize() {
    List<Integer> orig = Arrays.asList(1, 2, 3, 4);
    assertEquals(
            Arrays.asList(orig),
            partition(orig, orig.size() + 11));
}

Consider using Iterable<T> instead of List<T>

The goal of the method is to split a large collection to multiple smaller collections. The concept makes sense for anything that's Iterable<T>, which is a super-interface of List<T>. Depending on your use case, it might be useful to consider this alternative, and make the method more general by rewriting to make it work with this signature:

public static <T> List<List<T>> partition(Iterable<T> iterable, int size) {
\$\endgroup\$
  • 1
    \$\begingroup\$ I really appreciate you including the example tests for this. Tests are something I am still struggling with, but I am very aware of the need for them. It is nice to have some examples to look at. \$\endgroup\$ – bazola Oct 10 '14 at 10:56
7
\$\begingroup\$

while loop

Your while loop would work much better as a for loop, as you are iterating over index anyways (you would get rid of two extra lines of code, and the code would be clearer as well).

raw list

It's always a bit ugly to have raw types, so List activeList could be List<T> activeList.

Naming

  • pageNumber isn't very generic, listNumber or listIndex might be better.
  • splitCount should better be itemsPerList (that way, I know what it is, as it could also be the number of lists).

remove numItemsAdded

You don't really need numItemsAdded. Without it, the code would look like this:

private static <T> List<List<T>> listSplitter(List<T> originalList, int itemsPerList) {
    List<List<T>> listOfLists = new ArrayList<>();
    int originalListSize = originalList.size();
    int listIndex = -1;

    for (int index = 0; index < originalListSize; index++) {
        if (index % itemsPerList == 0) {
            listIndex++;
            listOfLists.add(new ArrayList<>());
        }
        List<T> activeList = listOfLists.get(listIndex);
        activeList.add(originalList.get(index));
    }

    return listOfLists;
}

You have to decide if it is more or less readable. I think that it is clearer, as there are less variables the reader has to keep track of.

\$\endgroup\$
  • \$\begingroup\$ Ah, modulo, smart solution. It even 'supports' negative list sizes (not that the lists actually get negative size though...). Not sizes of 0 though as that is DivisionByZero. \$\endgroup\$ – Simon Forsberg Oct 9 '14 at 21:56
  • 1
    \$\begingroup\$ @SimonAndréForsberg that is true, if the desired list size is <= 0 it should really thrown an IllegalArgumentException as you suggested in your answer. \$\endgroup\$ – tim Oct 10 '14 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.