I get input strings from the console like this:
while ((currentLine = bufferedReader.readLine()) != null ) {
StringTokenizer string = new StringTokenizer(currentLine, " ");
while (string.hasMoreTokens()) {
// Create a new LinkedHashSet for every token and then add it to the ArrayList.
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<String>();
linkedHashSet.add(string.nextToken());
setOfStrings.add(linkedHashSet);
}
}
I'm always getting different strings from input, never the same. After finishing filling in the data structures I have this situation:
- An
ArrayList<LinkedHashSet<String>>
which contains one LinkedHashSet for each string split. Inside each
LinkedHashSet
I have a string that is different from any other string present in the other LinkedHashSets - in other words, its unique. For example, I can't have this inside the ArrayList:Set x : [foo] ... Set y : [foo]
After doing that, I call the function below many times to make different merges.
public void mergeSets(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> setOfStrings) {
String toMerge = operations.get(1);
String fromMerge = operations.get(2);
boolean enteredFirstToMerge = false;
boolean enteredFirstFromMerge = false;
// Temporary LinkedHashSet reference used to merge two sets.
LinkedHashSet<String> subSetToMerge = null;
LinkedHashSet<String> subSetFromMerge = null;
for (Iterator<LinkedHashSet<String>> iterator = setOfStrings.iterator();
iterator.hasNext(); ) {
LinkedHashSet<String> subSet = iterator.next();
if (subSet.contains(toMerge) && subSet.contains(fromMerge))
break;
else {
if (subSet.contains(toMerge) && !enteredFirstToMerge) {
enteredFirstToMerge = true;
subSetToMerge = subSet;
iterator.remove();
} else if (subSet.contains(fromMerge) && !enteredFirstFromMerge) {
enteredFirstFromMerge = true;
subSetFromMerge = subSet;
}
}
if (enteredFirstFromMerge && enteredFirstToMerge)
break;
}
if (enteredFirstFromMerge && enteredFirstToMerge) {
subSetFromMerge.addAll(subSetToMerge);
}
}
Explanation:
For example, if I have as operation merge foo bar
, I have to do these steps:
First of all, I have to find where
foo
andbar
are located:Inside
setOfStrings
, I can have this situation:position x : [bar, tree, hotel] ... position y : [foo, lemon, coffee]
When I find them, I have to combine the set which contains foo with the set that contains bar
this way:
position x : {bar tree hotel foo lemon coffee}
...
position y : {} -> deleted from the arrayList
This function takes as parameters an arrayList
of operations and an arrayList<LinkedHashSet<String>>
:
For the ArrayList
of operations
, I always get a specific position:
operations.get(1)
refers to the set to merge (foo in this example)operations.get(2)
refers to the set where to add the foo set (bar in this example)
With this for loop, I iterate the ArrayList to search the to sets,for (Iterator<LinkedHashSet<String>> iterator = setOfStrings.iterator(); iterator.hasNext(); )
This if
statement checks if the iterator is in the specific set:
if (subSet.contains(toMerge) && !enteredFirstToMerge) {
enteredFirstToMerge = true;
subSetToMerge = subSet;
iterator.remove();
} else if (subSet.contains(fromMerge) && !enteredFirstFromMerge) {
enteredFirstFromMerge = true;
subSetFromMerge = subSet;
}
My question is: Could I have collisions with this type of algorithm that I implemented?
If not the time complexity is only O(n) -> the size of the arrayList.
setOfStrings
to an entirely newArrayList<LinkedHashSet<String>>
every time a new line is read, thereby losing the results from the previous input. Am I missing something?hello hello hello programmers!