1

I need some code sample or algorithm to resize List<List<Integer>> that should work in next way:

Let's imagine that we have next newSize and incomingList (pseudocode):

    int newSize = 4;
    List<List<Integer>> incomingList = List(List(1,2,3),List(4,5,6),List(7,8,9);

    List<List<Integer>> result = resizeListOfNestedList(newSize, incomingList)

newSize integer sets new size of incomingList and resizeListOfNestedList should return next result for non odd numbers (eg. 4):

    List(List(1,2),List(3,4),List(5,6),List(7,8)

and next if newSize is odd number (e.g 3):

    List(List(1,2),List(3,4,5),List(6,7,8)

newSize is always greater than incomingList.size()

I would appreciate any advice.

Update

With help of google.common.Lists, I have finished draft code (yeah, it smells), I hope it will help somebody.

In my case method receives different incomingList.size()s and newSize params and it's obvious that incomingList.size()/newSize will return double value (e.g incoming list.size() = 1000, but we need to "compress" it to 600 elements) so I am not able to use Lists.partition all the time. expandList is better to call after next code: 

int maxSplitValue = (int) Math.ceil((double) incomingList.size() / newSize);

List<List<Integer>> firstPortionValues = Lists.partition(
      incomingList, maxSplitValue
);//size can be less than required after double to int upper round

if (firstPortionValues.size() < maxSplitValue) {
   List<List<Integer>> expandedList = expandList(firstPortionValues, maxSplitValue)
}

Results: 

Incoming list:[[0, 1], [2, 3]] 
New size value: 3
Outcoming list:[[0], [1], [2, 3]]

Incoming list:[[0.0, 1.0, 2.0], [3.0, 4.0, 5.0], [6.0, 7.0, 8.0]]
New size value: 4
Outcoming list:[[0.0], [1.0], [2.0], [3.0, 4.0, 5.0], [6.0, 7.0, 8.0]]

Code:

public List<List<Integer>> expandList(List<List<Integer>> incomingList, int newSize) {

        List<List<Integer>> resultList = new ArrayList<>();

        for (int index = 0; index < incomingList.size(); index++) {

            List<Integer> nodeList = incomingList.get(index);

            final int minPortionValue = getMinPortionValue(
                incomingList.size(), resultList.size(), nodeList.size(), index, newSize
            );

            List<List<Integer>> portionResult = splitNodeList(new ArrayList<>(nodeList), minPortionValue);

            resultList.addAll(portionResult);
        }

        return resultList;
    }

    private int getMinPortionValue(int listSize, int resultListSize, int listElementSize, int index, int newSize) {

        if (listElementSize > 1) {

            int maxPortionValue = listElementSize % 2 == 0 ? listElementSize / 2 : --listElementSize;
            boolean isOkUseMaxPortionValue = maxPortionValue + listSize - index + resultListSize <= newSize;

            if (isOkUseMaxPortionValue) {
                return maxPortionValue;
            } else {
                return getMinPortionValue(listSize, resultListSize, listElementSize - 1, index, newSize);
            }
        } else {
            return 0;
        }
    }

    private List<List<Integer>> splitNodeList(List<Integer> nodeList, int minSplitValue) {

        List<List<Integer>> result = new ArrayList<>();

        if (minSplitValue > 0) {

            result.addAll(Lists.partition(nodeList, minSplitValue));

            return result;
        } else {

            result.add(nodeList);

            return result;
        }
    }
  • Please show us what you have tried so far. – eltabo May 11 '16 at 09:34
  • @eltabo If I had some useful code-drafts, I would have posted it with question. Please note that I didn't ask for complete solution. Also, I suppose that there should be some java libs that can help. –  May 11 '16 at 09:49
  • task is not clear enough, didn't you lost value 9 in example ? – light_keeper May 11 '16 at 15:11
  • When you talk about handling a list of lists... this is basically a [tree](http://stackoverflow.com/questions/3522454/java-tree-data-structure), you might want to implement your datastructure accordingly. It can save you alot of headache. Then this becomes a more common tree traversal/rebalancing problem. – SME_Dev May 11 '16 at 15:31
  • @unpc you should post an answer and mark your question as resolved – Federico Piazza May 18 '16 at 17:49

3 Answers3

0

Why you not use ListUtils.union(list1,list2); from Apache Commons and

Java: how can I split an ArrayList in multiple small ArrayLists?

Community
  • 1
  • 1
Matthias Wegner
  • 303
  • 4
  • 18
  • Thank you for response. In my case I don't know chunk size. e.g method receives array size 1000 and requirement that nested list size should be 600 elements. If you try to calc chunks you will get double `1,66` which can not be passed to `partition(List list, int size)`. That is why I rounded chunks to upper value, divided, and then expanded to the size required. –  May 11 '16 at 14:47
0

Reading your question, I can come up with the algorithm idea of doing 2 steps:

  1. Combine all the sublist into one list (using Guava Iterables)
  2. Partition the result of step 1 (using Guava partition)

Guava helps focusing more in what we need than how to do it, therefore is easy to translate your pseudo code and working code.

So, you can have something like this:

@Test
public void test(){
    // Init lists
    List<Integer> a = Lists.newArrayList(1,2,3);
    List<Integer> b = Lists.newArrayList(4,5,6);
    List<Integer> c = Lists.newArrayList(7,8,9);

    List<List<Integer>> incomingList = Lists.newArrayList(a,b,c);
    System.out.println(incomingList);

    // Create combined list
    Iterable<Integer> tempList = Iterables.concat(incomingList);

    // Re-Partition list 
    Iterable<List<Integer>> result = Iterables.partition(tempList, 2); // New size: 2

    // Convert from Iterables to List
    List<List<Integer>> finalList = Lists.newArrayList(result);
    System.out.println(finalList);
}

The output is:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]      // Incoming list
[[1, 2], [3, 4], [5, 6], [7, 8], [9]]  // Final list

Above code is to debug easily, you can reduce the code in less lines and also leverage import static to make it more readable and having this:

import static com.google.common.collect.Iterables.*;
import static com.google.common.collect.Lists.*;

public void test(){
    List<Integer> a = newArrayList(1,2,3);
    List<Integer> b = newArrayList(4,5,6);
    List<Integer> c = newArrayList(7,8,9);

    List<List<Integer>> incomingList = newArrayList(a,b,c);
    System.out.println(incomingList);

    // Repartition
    List<List<Integer>> finalList = newArrayList(partition(concat(incomingList), 2));
    System.out.println(finalList);
}

As a note on the result list, partition method create multiple lists of N values but the last list can have less values. For what you stated seems you want the less values at the beginning. I leave that to you to search partition methods and guava usages.

Federico Piazza
  • 30,085
  • 15
  • 87
  • 123
0

You can just code it, pure Java7. This code keeps new list of lists balanced, adding extra elements in the end.

public List<List<Integer>> resizeListOfNestedList(int newSize, List<List<Integer>> data) {

    ArrayList<Integer> allElements = new ArrayList<>();

    for (List<Integer> integers : data) {
        allElements.addAll(integers);
    }

    int elementsPerItem = allElements.size() / newSize;
    int extraElements  = allElements.size() % newSize;
    int indexToStartAddExtraElement = newSize - extraElements;

    ArrayList<List<Integer>> result = new ArrayList<>(newSize);
    Iterator<Integer> iterator = allElements.iterator();

    for (int i = 0; i < newSize; i++){

        int currentItemElementsCount = elementsPerItem;

        if (i >= indexToStartAddExtraElement)
            currentItemElementsCount++;

        ArrayList<Integer> current = new ArrayList<>(currentItemElementsCount);

        for (int j = 0; j < currentItemElementsCount; j++){
            current.add(iterator.next());
        }

        result.add(current);
    }

    return result;
}
light_keeper
  • 627
  • 5
  • 15