Merging key-value sets as specified by a command

Question

private void merge(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> setOfStrings) {
 String toMerge = operations.get(1);
 String fromMerge = operations.get(2);
 boolean enteredFirstToMerge = false;
 boolean enteredFirstForMerge = false;
 // references that points one on toMerge and the other on fromMerge
 LinkedHashSet<String> toMergeAndAfterDelete = null;
 LinkedHashSet<String> addOnFromMerge = null;
 for (LinkedHashSet<String> subSet : setOfStrings) {
 if (subSet.contains(toMerge) && subSet.contains(fromMerge))
 break;
 else {
 if (subSet.contains(toMerge) && !enteredFirstToMerge) {
 toMergeAndAfterDelete = subSet;
 enteredFirstToMerge = true;
 }
 if (subSet.contains(fromMerge) && !enteredFirstForMerge) {
 addOnFromMerge = subSet;
 enteredFirstForMerge = true;
 }
 if ((enteredFirstForMerge && enteredFirstToMerge)) {
 break;
 }
 }
 }
 /***********************************************/
 //outside Loop i call the remove on the arraylist
 //that are very expensive 
 /*************************************************/ 
 if (enteredFirstForMerge && enteredFirstToMerge) {
 // first i delete from the array the linkedHashSet toMerge and
 // fromMerge and after i add a 
 // new linkedHashSet with the subSets merged
 setOfStrings.remove(toMergeAndAfterDelete); 
 setOfStrings.remove(addToMergeOnFromMerge); 
 addOnFromMerge.addAll(toMergeAndAfterDelete);
 setOfStrings.add(addOnFromMerge);
 }
}

This function takes as parameter an arrayList of operations, and an ArrayList<LinkedHashSet<String>>:

For the arrayList of operations, I always get a specific position, so I don't iterate. It is always \$O(1)\$.

For example, if I have as operation move foo bar, I have to do these steps:

• First of all, I have to find where are located foo and bar:

  • Inside setOfStrings, I can have this situation:

     position x : {bar tree hotel}
     ...
     position y : {foo lemon coffee} 
    

When I find them, I have to concat the foo string into bar string in this way:

 position x : {bar tree hotel foo lemon coffee}
 ...
 position y : {} 

How can I improve the efficiency of this function?

• AJMansfield: The number one problem with your code is the formatting. Fix that and you're half done.

Answer 1

• Abstract as much as possible over type: List instead of ArrayList.

• Use OO where appropriate: List<String> operations should clearly be some class MoveOperation(String to, String from).

• It's not clear why you are using LinkedHashSet instead of List.

• The algorithm is ill-defined: what happens if there are numerous foo's or bar's.

I implemented something below, but it is in functional style, so it might be hard to read. There are three implicit loops: two for the filters and one for the map. You might also notice that I never modify a collection, but always create a new one. Again, this is the functional style. In your algorithm, you can actually shoot yourself in the foot if you modify some collections at the wrong moment.

private List<List<String>> merge2(List<String> operations, List<List<String>> listOfSentences) {
 Stream<List<String>> sentencesWithTo = listOfSentences.stream()
 .filter(sentence -> sentence.contains(toMerge));
 Stream<List<String>> sentencesWithFrom = listOfSentences.stream()
 .filter(sentence -> sentence.contains(fromMerge));
 long nTo = sentencesWithTo.count();
 long nFrom = sentencesWithFrom.count();
 if (nTo == 0 || nFrom == 0) {
 return listOfSentences;
 } else if (nTo > 1 || nFrom > 1) {
 // what to do here??
 } else {
 List<String> sentenceTo = sentencesWithTo.collect(Collectors.toList()).get(0); // should only be one element ?
 List<String> sentenceFrom = sentencesWithFrom.collect(Collectors.toList()).get(0); // should only be one element ?
 Stream<List<String>> updatedSentences = listOfSentences.stream().map(sentence -> {
 if (sentence.equals(sentenceTo))
 return Stream.concat(sentenceTo.stream(), sentenceFrom.stream()).collect(Collectors.toList());
 else if (sentence.equals(sentenceFrom))
 return new ArrayList<>();
 else 
 return sentence;
 });
 return updatedSentences.collect(Collectors.toList());
 }
}

Answer 2

Another thing to point out, this code snippet does not demonstrate what you have asked:

 // first i delete from the array the linkedHashSet toMerge and
 // fromMerge and after i add a 
 // new linkedHashSet with the subSets merged
 setOfStrings.remove(toMergeAndAfterDelete); 
 setOfStrings.remove(addToMergeOnFromMerge); 
 addOnFromMerge.addAll(toMergeAndAfterDelete);
 setOfStrings.add(addOnFromMerge);

• First of all, I have to find where are located foo and bar:

  • Inside setOfStrings, I can have this situation:

     position x : {bar tree hotel}
     ...
     position y : {foo lemon coffee} 
    

When I find them, I have to concat the foo string into bar string in this way:

 position x : {bar tree hotel foo lemon coffee}
 ...
 position y : {} 

Your code is doing more like:

position z : {bar tree hotel foo lemon coffee}

Other minor points to highlight too:

• ArrayList<LinkedHashSet<String>> setOfStrings isn't exactly a set of Strings, more like a list of set of Strings... in other words, perhaps you can think of a better variable name.
• Same for the other names e.g. toMerge and fromMerge, I don't think they are easily understandable when reading the code.
• Program to interfaces, not the implementations. I.e. instead of merge(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> setOfStrings) the method signature can be merge(List<String> operations, List<Set<String>> setOfStrings).