Java: Implementing "repeat until no change" collection

Question

I'm trying to implement an algorithm that repeatedly applies operations on a Collection (currently a List). In each step Elements can be added, removed and changed (using getters and setters) within the collection. The algorithm is repeated until no changes were made to the collection in the previous step.

The order of elements is not relevant. However a modified or created Element should not be accessed until the next loop.

My approach was to have a large mainloop, and an inner loop that applies the algorithm and copies modified, created and unchanged elements to a second List. After the inner loop finished, the original list is emptied and replaced by the new one. The main loop is terminated if the new and the old list contain the same elements.

What is the best way to do this? Is there a collection that supports this out of the box? 3rd party is also ok.

Any help would really be appreciated!

Answer 1

I would just use a boolean variable that is set to false at the beginning of the main loop. When a change is made to the list in the inner loop this could be set to true, if no change is made it remains false. The main loop can then continue looping if this is true or finish looping otherwise

Answer 2

Since you say that order is not relevant, use an implementation of the Set interface, for example HashSet. You can compare sets for equality simply with the equals method.

Answer 3

Your approach sounds reasonable to me, but has lots of collection copying. I think you can feed the same collection into the inner loop that updates the collection in place and signals whether any changes were made, e.g. while (collectionUpdated).

If the collection is not too big or you don't expect many changes to it, recursion works well. e.g.

runAlgo(Collection c) {
  // do work

  if (collectionUpdated)
    return runAlgo(c); // potential stackoverflow with huge collection or too many calls from lots of collection updates
  else
    return c;
}