Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

New feature: Iterators.interleave() [or Iterators.zip()] #677

Open
gissuebot opened this issue Oct 31, 2014 · 31 comments
Open

New feature: Iterators.interleave() [or Iterators.zip()] #677

gissuebot opened this issue Oct 31, 2014 · 31 comments

Comments

@gissuebot
Copy link

Original issue created by chris.winters on 2011-08-05 at 07:24 PM


First reported in guava-discuss list: http://groups.google.com/group/guava-discuss/browse_frm/thread/da433e0b7db8c8ae

Be able to combine iterators but instead of moving through elements one at a time, pull from each iterator in turn until all are exhausted. Iterators should not have to be the same size. Sample code + output of how it might work:

Code:

List<String> a = [ "one", "two", "three", "four" ];
List<String> b = [ "fee", "fi" ];
List<String> c = [ "broccoli", "tomato", "potato" ];
List<String> d = [ "purple" ];

Iterator<String> interleaved = Iterators.interleave(
    a.iterator(), b.iterator(),
    c.iterator(), d.iterator() );
int count = 1;
while ( interleaved.hasNext() ) {
   System.out.println( count++ + ": " + interleaved.next() );
}

Output:

1: one
2: fee
3: broccoli
4: purple
5: two
6: fi
7: tomato
8: three
9: potato
10: four

@gissuebot
Copy link
Author

Original comment posted by amertum on 2011-08-05 at 09:58 PM


We can also see this like that :

Iterator<List<String>> interleaved = Iterators.interleave(
    a.iterator(), b.iterator(),
    c.iterator(), d.iterator());

Output:

["one", "fee", "broccoli", "purple"]
["two", "fi", "tomato"]
["three", "potato"]
["four"]

and maybe padded with null as well ? Like partition but with multiple inputs iterator.

@gissuebot
Copy link
Author

Original comment posted by chris.winters on 2011-08-06 at 04:16 PM


I think that output would be fine since it can be sent to a separate Iterators.concat() method to flatten it to a single list.

@gissuebot
Copy link
Author

gissuebot commented Oct 31, 2014

Original comment posted by j...@nwsnet.de on 2011-08-16 at 08:04 AM


Looks interesting to me. Can you supply a use case or two?

However, the name "zip" seems to be generally understood as something else (namely pulling a single element from all iterators at once and returning a tuple whose length equals the number of iterators). [I see this has already been pointed out on the mailing list.] "Interleave" is fine, though.

@gissuebot
Copy link
Author

Original comment posted by amertum on 2011-08-16 at 12:06 PM


A use case is when you retrieve some data from a third party which come in many list of single element which are related to each other. And then you need to process these data and you find yourself iterate over many collection which is not very logic and readable. The thing you really need is to interleave these data to have them close to each other.

Example :

names = ["robert", "paul", "mike"]
ages = [25, 32, 45]

interleave(names, ages) produces :
[
["robert", 25],
["paul", 32],
["mike", 45]
]

so now you can use a predicate to filter people which age is under 30.

@gissuebot
Copy link
Author

gissuebot commented Oct 31, 2014

Original comment posted by j...@nwsnet.de on 2011-08-16 at 01:20 PM


A use case is when you retrieve some data from a third party
which come in many list of single element which are related to each other.
An iterable of single-element iterables is easily pre-processed via Itera[tor|ble]s.concat.

names = ["robert", "paul", "mike"]
ages = [25, 32, 45]
interleave(names, ages) produces :
[
["robert", 25],
["paul", 32],
["mike", 45]
]
This is exactly what zip commonly does.

I agree that the output example in comment #1 is a useful intermediate step to return before serializing the elements of all result tuples.

Also, what is the preferred result type? Guava still has no implementation of a n-tuple or even pair and triple concept. Immutable lists would be ok, but they'd work only for immutable elements. Iterators might also work (like returned by itertools.groupby in Python), but are not that comfortable to work with for direct/indexed element access.

BTW, this seems quite similar to partition, but somewhat the other way round.

@gissuebot
Copy link
Author

Original comment posted by gscerbak on 2011-08-16 at 01:44 PM


@amer: names and ages have to have compatible type, in your case it would be just Object. The way interleave is proposed to work won't enable you to filter people easily. For your use case it is more reasonable to either create a Person class and create an iterable of people by iterating over names and ages and instantiating Person objects from them. Other choice is to do the same without a new class, by using a Map.

This is classic example of Java failing at tuples. Interleave makes sense only for compatible types - e.g. same type as in the example with String above. I am not sure a reasonable use case for this exists. If Iterables contain related data, you should combine them in an entity. If the interleaved order is important, that should be handled by Ordering, but I cannot imagine when such an Ordering would be useful.

@gissuebot
Copy link
Author

Original comment posted by gscerbak on 2011-08-16 at 02:12 PM


@yo.gi: Look at this:

Pair in JDK 1.6 - java.util.AbstractMap.SimpleEntry<K,V> and java.util.AbstractMap.SimpleImmutableEntry<K,V>

Pair in Guava r09 - com.google.common.collect.Maps#immutableEntry

Triple in Guava r09 - com.google.common.collect.Tables#immutableCell

@gissuebot
Copy link
Author

gissuebot commented Oct 31, 2014

Original comment posted by j...@nwsnet.de on 2011-08-16 at 03:32 PM


Those are specializations of a tuple (as suggested by literature), but they have different semantics than what we need here (no maps, no tables). Reusing them would violate the principle of least surprise, IMHO.

@gissuebot
Copy link
Author

Original comment posted by gscerbak on 2011-08-16 at 05:29 PM


@yo.gi: You are right, they can be pragmatically used as tuples and triples, but they were not intended to be, their semantics - meaning - is different. The problem is, that in Java, it is probably not possible to do anything more sensible.

@gissuebot
Copy link
Author

Original comment posted by amertum on 2011-08-16 at 05:41 PM


@gscerbak : OK, this is not very pretty to mix types but right now, I'm doing presentation using JSP with expression language which does not really care about type.
But I like the way you see it with Ordering. I'll think about it.

@gissuebot
Copy link
Author

Original comment posted by kevinb9n on 2011-09-01 at 05:43 PM


(No comment entered for this change.)


Status: Triaged
Labels: Type-Enhancement

@gissuebot
Copy link
Author

gissuebot commented Oct 31, 2014

Original comment posted by han...@eyealike.com on 2011-10-28 at 07:07 PM


May I suggest these signatures:

class Iterators {
    public static <T> Iterator<T> interleave( Iterable<Iterator<T> ) { ... }
    public static <T> Iterator<Iterator<T>> transpose( Iterable<Iterator<T> ) { ... }
}

I think 'transpose' would be a better name for the functionality originally asked for in this issue. An Iterable<Iterator<T> can be seen as a jagged, sparse matrix and the name 'transpose' suggests that the result is another matrix, just with rows and columns swapped.

That leaves the name 'interleave' free for the equivalent of Iterators.concat( Iterators.transpose( x ) ). Note that I am not sure that interleave should be implemented that way (I have an implementation and think that it shouldn't) it just illustrates the relationship between the two methods.

@gissuebot
Copy link
Author

gissuebot commented Oct 31, 2014

Original comment posted by j...@nwsnet.de on 2011-10-29 at 06:40 PM


For the record: "jagged, sparse matrix" makes me totally think of Guava's table implementation.

@gissuebot
Copy link
Author

Original comment posted by fry@google.com on 2011-12-10 at 04:14 PM


(No comment entered for this change.)


Labels: Package-Collect

@gissuebot
Copy link
Author

Original comment posted by wasserman.louis on 2012-02-12 at 05:39 PM


Related: http://stackoverflow.com/q/9200080/869736 .

@gissuebot
Copy link
Author

Original comment posted by fry@google.com on 2012-02-16 at 07:17 PM


(No comment entered for this change.)


Status: Acknowledged

@gissuebot
Copy link
Author

Original comment posted by wasserman.louis on 2012-02-23 at 07:27 PM


Do I understand correctly that this issue is now basically about transpose? Issue 203 pretty conclusively eliminated the possibility of Pair.

@gissuebot
Copy link
Author

Original comment posted by wasserman.louis on 2012-03-07 at 12:17 AM


How do we feel about interleave? I'm not sure how I feel about transpose, but interleave is simple and has broader utility.

@gissuebot
Copy link
Author

Original comment posted by kevinb@google.com on 2012-05-30 at 07:43 PM


(No comment entered for this change.)


Labels: -Type-Enhancement, Type-Addition

@gissuebot
Copy link
Author

Original comment posted by kevinb@google.com on 2012-06-22 at 06:16 PM


(No comment entered for this change.)


Status: Research

@gissuebot
Copy link
Author

gissuebot commented Nov 1, 2014

Original comment posted by car...@medallia.com on 2012-12-26 at 08:55 PM


We needed this functionality for creating test data

@gissuebot
Copy link
Author

Original comment posted by kgilmer on 2014-01-26 at 01:28 AM


I have an implementation of this. I wonder if submitting the code for review is worthwhile given the age of this issue...? Is the feature considered too esoteric for inclusion into Guava?

@gissuebot
Copy link
Author

Original comment posted by kgilmer on 2014-03-06 at 10:32 PM


FWIW my implementation is available here under the MIT-style license: https://github.com/iheartradio/interleaver

@rafalmag
Copy link

I am also looking forward for java util functionality like one from groovy List#transpose or scala List#zip .

@kevinb9n
Copy link
Contributor

Note that it's possible to get this functionality using ArrayTable and Tables.transpose() (and then filtering out nulls); it's just a little awkward as you may need to invent row and column keys you don't care about.

@smaudet
Copy link

smaudet commented Aug 14, 2015

Would still be nice to have this...

At the moment, this may be possible, but very clunky/awkward to implement, especially if you really only needed it as a one-off.

@mattnathan
Copy link

While this issue is old I wanted to add my use case for this feature - request/response pairing.

I have a batch function that takes a collection of requests and returns a collection of responses, in order. I want to be able to do something taking both the request and response together as a pair (not a Pair) and this seems to satisfy that use case for me.

Iterable<Request> requests = ...
Iterable<Response> responses = batchRequest(requests);
Iterables.forEachPair(requests, responses, (req, res) -> doSomething(req, res));

@cpovirk
Copy link
Member

cpovirk commented Mar 22, 2017

I think we had gotten about 70% of the way through discussing forEachPair. Maybe @kevinb9n remembers the status.

@kevinb9n
Copy link
Contributor

kevinb9n commented Mar 24, 2017

Thanks for the reminder on forEachPair... it should be coming soon.

Did I close this issue? It's not clear why I would have done that. Must have been accidental.

@kevinb9n kevinb9n reopened this Mar 24, 2017
@cpovirk
Copy link
Member

cpovirk commented Apr 3, 2017

This issue is covering ~3 different things now:

  • interleave
  • zip (coming in 22.0)
  • forEachPair (also coming in 22.0)

@davidklebanoff
Copy link

davidklebanoff commented Apr 3, 2017

@cpovirk
For the interleave component, I have written a custom Iterator that I've been using for my own personal use that can interleave 2-N iterators of varying sizes. I'm not sure if this is something that would be desired in the core library - if so I could do a pull request. Also if that's the case, it would probably need some style/name changes to better fit the Guava code base.

/**
 * An Iterator implementation which interleaves elements from the given iterators.
 *
 * Iterators do not need to be the same length.
 */
public class InterleavingIterator<T> extends AbstractIterator<T> {

    private final Queue<Iterator<T>> queue;

    public static <T> InterleavingIterator<T> ofIterators(final List<Iterator<T>> iterators) {
        return new InterleavingIterator<>(iterators);
    }

    public static <T> InterleavingIterator<T> ofIterables(final List<Iterable<T>> iterables) {
        final LinkedList<Iterator<T>> iterators = new LinkedList<>();
        for (final Iterable<T> iterable : iterables) {
            iterators.add(iterable.iterator());
        }
        return new InterleavingIterator<>(iterators);
    }

    private InterleavingIterator(final List<Iterator<T>> iterators) {
        this.queue = new LinkedList<>(iterators);
    }

    @Override
    protected T computeNext() {
        while (!queue.isEmpty()) {
            final Iterator<T> head = queue.poll();
            if (head.hasNext()) {
                final T result = head.next();
                queue.offer(head);
                return result;
            }
        }
        return endOfData();
    }

}

@netdpb netdpb added the P3 label Aug 7, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

9 participants