Split List<String[]> into List<List<String[]>>

Question

We have a list of string arrays i.e. List<String[]> (which we got from a csv) which follows the hierarchy:

0000

3000
   5000
   5000
   5000
    .
    . 
    .
3900

3000
   5000
   5000
   5000
    .
    .
    .
3900

.
.
.

9999

As you can see, it will always start with 0000 and end with 9999 (think of them as header and footer respectively)

Furthermore, it has equal numbers of 3000 and 3900, with zero to many 5000 records in between.

Input Example:

{
    ["0000","entry A", entry B", "entry C"....], 
    ["3000","entry1", entry2", "entry3"....],            ---
    ["5000", "entry4", entry 5", "entry 6"...],            |
    ["5000", "entry 7", entry 8", "entry 9"...],           |
    ["5000", "entry 10", entry 11", "entry 12"...],        | -> This is one group
    ["5000", "entry 13", entry 14", "entry 15".....],      |
    ["3900", "entry 16", entry 17", "entry 18"....],     ---
    ["3000","entry19", entry20", "entry 21"....],
    ["5000", "entry 22", entry 23", "entry 24"...],
    ["3900", "entry 25", entry 26", "entry 27"...],
    ["3000","entry 28", entry 29", "entry 30"...],
    ["3900", "entry 31", entry 32", "entry 33"...],
    ["9999", "entry X", entry Y", "entry Z"...]
}

The first and last row (i.e. 0000 and 9999) are useless and will not be used.

we have to split this List<String[]> into List<List<String[]>> such that it contains rows from 3000 to 3900

Output:

{
    {
        ["3000","entry1", entry2", "entry3", ...],
        ["5000", "entry4", entry 5", "entry 6", ...],
        ["5000", "entry 7", entry 8", "entry 9", ...],
        ["5000", "entry 10", entry 11", "entry 12", ...],
        ["5000", "entry 13", entry 14", "entry 15", ...],
        ["3900", "entry 16", entry 17", "entry 18", ...],
    },
    {
        ["3000","entry19", entry20", "entry 21", ...],
        ["5000", "entry 22", entry 23", "entry 24", ...],
        ["3900", "entry 25", entry 26", "entry 27", ...],
    },
    {
        ["3000","entry 28", entry 29", "entry 30", ...],
        ["3900", "entry 31", entry 32", "entry 33", ...],
    }
}

This is my code so far:

 private List<List<String[]>> splitIntoBlocks(List<String[]> rows) {

        //get all position of 3000
        List<Integer> l1 = IntStream.range(0,rows.size())
                .filter(i->rows.get(i)[0].equals("3000"))
                .boxed()
                .collect(Collectors.toList());

        //get all position of 3900
        List<Integer> l2 = IntStream.range(0,rows.size())
                .filter(i->rows.get(i)[0].equals("3900"))
                .boxed()
                .collect(Collectors.toList());

         List<List<String[]>> res=null;

        //split list<string[]> rows into blocks that start with 3000 and end with 3900 and store it in a list
        if(l1.size() == l2.size()) {
            res = IntStream.range(0, l1.size())
                    .mapToObj(i->rows.subList(l1.get(i),l2.get(i)+1))
                    .collect(Collectors.toList());
        }
        return res;
    }

As you can see, I have solved it using streams in roughly 3 stream statements, but I'm not very good at java 8 features. I'm looking for someone to solve this in perhaps 1 or 2 statements. I feel that it is very much possible

P.S. - This is not an interview question, but something I will be using at work.

Answer 1

Motivations for improvement

I think "solving in 1 or 2 statements" is not a good target. Aiming for Java 8 features for the sake of using Java 8 features is also not a good target. A better target would be a combination of:

• correct and reasonably robust
• easy to understand
• reasonably efficient

Here's a bit shorter and more efficient, but pretty bad solution:

private List<List<String[]>> splitIntoBlocks(List<String[]> rows) {
    List<List<String[]>> blocks = new ArrayList<>();

    int start = 0;
    for (int index = 0; index < rows.size(); index++) {
        String marker = rows.get(index)[0];
        if (marker.equals("3000")) {
            start = index;
        } else if (marker.equals("3900")) {
            int end = index + 1;
            blocks.add(rows.subList(start, end));
        }
    }

    return blocks;
}

This is bad (as bad as the original code), because it doesn't validate the input. It will only work correctly with input in the assumed format, which it doesn't verify, and it doesn't detect or signal when something is wrong, which could lead to nasty bugs.

Validating inputs

The posted code assumes the input follows a certain format. It should at least document the assumptions, and state if the caller can be trusted to enforce those assumptions.

As you mentioned, the input comes from CSV files. Since the expected format is not captured by the List<String[]> type, I would be very cautious. A verification is needed somewhere to avoid bugs or undefined behavior, for example the following checks come to mind:

• There are the same number of START and END markers (you already did this one)
• The START and END markers don't overlap
• (optional?) There are no garbage records after an END and before the next START
• The rows are not empty (avoid crashing due to index out of bounds exceptions)

When any of these assumptions fail, I would either raise a custom exception that the caller can handle, or else throw IllegalArgumentException to fail fast.

So in fact, instead of making the posted code shorter, I'm suggesting to actually make it longer, by adding more validation logic.

Making the code easier to understand

Another answer already mentioned to improve the variable names. (I suggest following Java conventions with camelCase names, so startIndices and endIndices.)

The values "3000" and "3900" are magic strings. It would be better to use private static final constants for such values, so that they stand out, and with a descriptive name.

Building the lists of startIndices and endIndices use the same logic, duplicated. It would be good to extract to a helper method.

When returning a container type, it's usually more practical to return an empty container instead of null.

Answer 2

Low hanging fruit

l1 and l2 are very opaque variable names. start_indices and end_indices would be much more descriptive.

---

        //get all position of 3000
        List<Integer> l1 = IntStream.range(0,rows.size())
                .filter(i->rows.get(i)[0].equals("3000"))
                .boxed()
                .collect(Collectors.toList());

This code takes int indices, boxes them into Integer indices, and collects them into a List<Integer>. This results in many small objects in memory.

We can avoid the boxing, by replacing .boxed().collect(Collectors.toList()) with .toArray() and changing the variable type to int[].

        // get positions of all "3000"'s
        int[] start_indices = IntStream.range(0,rows.size())
                .filter(i->rows.get(i)[0].equals("3000"))
                .toArray();

Apply similar change to the group end indices, and corresponding changes to the final res construction.

Single Pass

The above is still passing over the rows input 3 times; the first to collect the starting indices, the second to collect the ending indices, and the third time to assemble the result. Three passes means you cannot apply this grouping operation on an ephemeral stream; it requires a concrete collection that can be repeatedly iterated over.

Moreover, an IntStream is being used to generate indices into the rows list -- a hack -- which requires an ArrayList or similar \$O(1)\$-indexable collection to avoid quadratic time complexity.

It would be much better to perform a single pass over the stream of data, and collecting the required groups along the way:

private List<List<String[]>> splitIntoBlocks(List<String[]> rows) {
   return rows.stream().collect(Block.collector());
}

Well, the above clearly solves the "looking for someone to solve this in perhaps 1 or 2 statements" request, but clearly additional work is still required. The Block.collector() class is required, writing of which (to handle possible splitting & parallel stream handling) is a non-trivial exercise. See Collector.of(...)

Answer 3

• The input data seems to me to naturally fit a sequential process, and all the processing can be achieved in a single pass, so I fail to see how using streams and making 3 passes is a sensible approach, especially with the amount of boxing used
• The approach taken assumes, rather than checks, that the input data is well-formed, which seems a little optimistic. Defensive programming principles suggest that you should check the data meets expectations.
• The naming issues have already been addressed. There's little restriction on variable names, and the typing saved in naming a variable "l1" is a poor exchange for readability against "subListStartOffsets" or something similar.

For this sort of processing, I'd often write a little Finite State Machine, but this exercise doesn't seem quite to warrant it. The natural processing pattern seems to me to be this.

For the first array, check that it starts with "0000". If not, throw an Exception as the input is badly-formed.

Assign a List<List<String[]>> for the result. Let's call this outputList.

Also allocate an int to hold the start of the current subList. Let's just call this subListStart. Initialise it to a "flag" value, say -1. (This probably should be a constant).

Now process a row at a time.

• If it starts with "3000" it marks the start of a subList. Check subListStart, if it is -1 then store the current offset in it, if not the input data is badly formed, and you should throw an Exception.
• If it starts with "3900" it marks the end of a subList. Extract the subList from subListStart to the current offset, and add it to your outputList. Set subListStart to -1 again, to indicate we're looking for a new start...
• If it starts with "5000" it's just data, but you should check that you've seen a start of list marker, so if subListStart is -1 you should throw an Exception.
• If it starts with "9999" it marks the end of the input data. You should check that the last subList was closed, by checking subListStart is -1.

Here's an example of how I might implement this (far from fully tested, I must point out).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class SubListProcessor {

  private static final String HEADER = "0000";
  private static final String START_OF_SUBLIST = "3000";
  private static final String END_OF_SUBLIST = "3900";
  private static final String FOOTER = "9999";
  private static final String PLAIN_DATA = "5000";

  public class BadlyFormedListException extends IllegalArgumentException {

    public BadlyFormedListException(String message) {
      super(message);
    }
  }

  public List<List<String[]>> processList(List<String[]> inputList) {
    List<List<String[]>> outputList = new ArrayList<>();

    int subListStart = -1; // Magic number, could/should make this a constant
    int currentOffset = 0;
    boolean seenFooter = false;
    Iterator<String[]> inputListIterator = inputList.iterator();

    String[] firstLine = inputListIterator.next();
    if (firstLine == null) {
      throw new BadlyFormedListException("Input List is empty");
    }
    if (firstLine.length == 0) {
      throw new BadlyFormedListException("Empty line at offset " + currentOffset);
    }
    if (!firstLine[0].equals(HEADER)) {
      throw new BadlyFormedListException("No header in input List");
    }

    while (inputListIterator.hasNext()) {
      String[] inputLine = inputListIterator.next();
      currentOffset += 1;
      if (inputLine.length == 0) {
        throw new BadlyFormedListException("Empty line at offset " + currentOffset);
      }
      switch (inputLine[0]) {
        case (START_OF_SUBLIST) : {
          if (subListStart == -1) {
            subListStart = currentOffset;
          }
          else {
            throw new BadlyFormedListException("Unclosed sub-list at offset " + currentOffset);
          }
          break;
        }
        case (PLAIN_DATA) : {
          if (subListStart == -1) {
            throw new BadlyFormedListException("Unopened sub-list at offset " + currentOffset);
          }
          break;
        }
        case (END_OF_SUBLIST) : {
          if (subListStart == -1) {
            throw new BadlyFormedListException("Unopened sub-list at offset " + currentOffset);
          }
          outputList.add(inputList.subList(subListStart, currentOffset + 1));
          subListStart = -1;
          break;
        }
        case (FOOTER) : {
          if (subListStart != -1) {
            throw new BadlyFormedListException("Unclosed sub-list at offset " + currentOffset);
          }
          seenFooter = true;
          break;
        }
        default :
          throw new BadlyFormedListException("Unrecognised line at offset " + currentOffset);

      }
    }

    if (!seenFooter) {
      throw new BadlyFormedListException("No footer in input list");
    }

    return outputList;
  }

  public static void main(String[] args) {
    List<String[]> inputList = Arrays.asList(
        new String[]{"0000", "entry A", "entry B", "entry C"},
        new String[]{"3000", "entry1", "entry2", "entry3"},
        new String[]{"5000", "entry4", "entry 5", "entry 6"},
        new String[]{"5000", "entry 7", "entry 8", "entry 9"},
        new String[]{"5000", "entry 10", "entry 11", "entry 12"},
        new String[]{"5000", "entry 13", "entry 14", "entry 15"},
        new String[]{"3900", "entry 16", "entry 17", "entry 18"},
        new String[]{"3000", "entry19", "entry20", "entry 21"},
        new String[]{"5000", "entry 22", "entry 23", "entry 24"},
        new String[]{"3900", "entry 25", "entry 26", "entry 27"},
        new String[]{"3000", "entry 28", "entry 29", "entry 30"},
        new String[]{"3900", "entry 31", "entry 32", "entry 33"},
        new String[]{"9999", "entry X", "entry Y", "entry Z"});

    List<List<String[]>> result = new SubListProcessor().processList(inputList);

    for (List<String[]> subList : result) {
      System.out.println("<");
      for (String[] value : subList) {
        System.out.format("\t%s%n", Arrays.toString(value));
      }
      System.out.println(">");
    }
  }
}