# Fwd: Make iterators cloneable?

Jonathan Bluett-Duncan jbluettduncan at gmail.com
Sun Sep 11 17:12:34 UTC 2016

```I think O(N^2)-like performance is unavoidable here Dave. However, although
Peter's algorithm is indeed O(N^2), it should be faster than Tagir's and
reasonable(-ish) in practice.

This is because the inner loop starts off not executing at all in the outer
loop's first iteration; and each time the outer loop iterates, the inner
loop's number of iterations increases by 1, eventually reaching N
iterations when the outer loop itself hits iteration N.

So although Peter's algorithm is O(N^2) in theory, in practice it shouldn't
or isn't as bad as most O(N^2) algos, since the number of steps it takes is
less than some ratio of N^2 for sufficiently large N.

On 11 September 2016 at 17:55, Dave Brosius <dbrosius at mebigfatguy.com>
wrote:

> Sure, but both of those algorithms are n^2, which is a bit painful,
> especially given all the pointer chasing that occurs with iterators.
>
>
>
> On 09/11/2016 08:20 AM, Peter Levart wrote:
>
>> Hi,
>>
>> Even if the elements are not comparable, you could rely on the fact that
>> Collection(s) usually create iterators with stable iteration order, so you
>> could do the following:
>>
>>
>>         Set<Integer> set = Set.of(1, 2, 3, 4);
>>
>>         Iterator<Integer> it1 = set.iterator();
>>         for (int n1 = 0; it1.hasNext(); n1++) {
>>             Integer e1 = it1.next();
>>             Iterator<Integer> it2 = set.iterator();
>>             for (int n2 = 0; n2 < n1; n2++) {
>>                 Integer e2 = it2.next();
>>                 System.out.println(e1 + " <-> " + e2);
>>             }
>>         }
>>
>>
>> Regards, Peter
>>
>> On 09/11/2016 02:02 PM, Tagir F. Valeev wrote:
>>
>>> Hello!
>>>
>>> As your keys are comparable, you can create normal iterators and
>>> filter the results like this:
>>>
>>> for(String v1 : s) {
>>>    for(String v2 : s) {
>>>      if(v1.compareTo(v2) < 0) {
>>>        System.out.println(v1 + " <-->" + v2);
>>>      }
>>>    }
>>> }
>>>
>>> Or using Stream API:
>>>
>>> s.stream().flatMap(v1 -> s.stream()
>>>      .filter(v2 -> v1.compareTo(v2) < 0).map(v2 -> v1 + " <-->" + v2))
>>>   .forEach(System.out::println);
>>>
>>> With best regards,
>>> Tagir Valeev.
>>>
>>>
>>> DB> It would be nice to be able to associate each element in a collection
>>> DB> with another element in the collection, which is something very
>>> easily
>>> DB> done with index based collections, but with sets, etc this isn't so
>>> DB> easy... unless i'm having a brainfart.
>>>
>>> DB> So i'd like to do this, but Iterator doesn't implement Cloneable...
>>> Any
>>> DB> reason not to? or is there another way that's missing me?
>>>
>>> DB> public class ItClone {
>>>
>>> DB>      public static void main(String[] args) {
>>> DB>          Set<String> s = Collections.newSetFromMap(new
>>> DB> ConcurrentHashMap<String, Boolean>());
>>>
>>>
>>> DB>          Iterator<String> it1 = s.iterator();
>>> DB>          while (it1.hasNext()) {
>>> DB>              String v1 = it1.next();
>>>
>>> DB>              Iterator<String> it2 = (Iterator<String>) it1.*clone*();
>>> DB>              while (it2.hasNext()) {
>>> DB>                  String v2 = it2.next();
>>>
>>> DB>                  System.out.println(v1 + " <-->" + v2);
>>> DB>              }
>>> DB>          }
>>> DB>      }
>>> DB> }
>>>
>>>
>>
>
```