开发者

Yield Return In Java

I've created a linked list in java using generics, and now I want to be able to iterate over all the elements in the list. In C# I would use yield return inside the linked list while going over the list of elements contained in the list.

How would I go about creating a java version of the above where I can iterate over all the items contained in the linked list?

I'm 开发者_运维知识库looking to be able to write code ala

LinkedList<something> authors = new LinkedList<something>();
for (Iterator<something> i = authors.Values ; i.HasNext())
      doSomethingWith(i.Value);

And was thinking that the Value 'property'/method would consist of code resembling

LinkedListObject<something> current = first;
While (current != null){
 yield return current.getValue();
 current = current.getNext()
}

Edit: Notice that I'm not interested in using any 3rd party APIs. Built-in java functionality only.


You can return an anonymous implementation of Iterable. The effects are pretty pretty similar, just that this is a lot more verbose.

public Iterable<String> getStuff() {
    return new Iterable<String>() {

        @Override
        public Iterator<String> iterator() {
            return new Iterator<String>() {

                @Override
                public boolean hasNext() {
                    // TODO code to check next
                }

                @Override
                public String next() {
                    // TODO code to go to next
                }

                @Override
                public void remove() {
                    // TODO code to remove item or throw exception
                }

            };
        }
    };
}


"yield return" is a very sophisticated compiler trick. It basically lets you declaratively implement IEnumerable without any of the annoying details of "figuring out" how to build your iterator. The unfortunate thing is that it does not translate into other languages well because very few compilers have such a capability. In some ways "yield return" is as damning as revolutionary.

Basically in C#, the compiler will generate two implementations of IEnumerable and IEnumerator (of T). It does this by basically realizing your "method"'s local variables as instance fields in generated implementation classes as well as examining the frames containing a "yield return" artifact. Once you know this, it should be possible for a well rounded developer to accomplish the same thing explicitly... although not as concisely. To demonstrate, I will CONCAT!

public static <T> Iterable<T> concat(Iterable<T> x, Iterable<T> y)
{
    for(T e: x)
    {
        yield return e;
    }

    for(T e: y)
    {
        yield return e;
    }
}

// becomes ....

public static <E> Iterator<E> concat_(Iterable<E> x, Iterator<E> y)
{
    T e1, e2;
    Iterator<E> i1, i2;

    Iterator<E> s;
    Iterator<E> s4 = new Iterator<E>()
    {
        public bool hasNext()
        {
            return false;
        }

        public E next()
        {
            throw ... ;
        }

        public void remove()
        {
            throw ... ;
        }
    }

    Iterator<E> s3 = new Iterator<E>()
    {
        Iterator<E> act()
        {
            if(i2.hasNext())
            {
                return i2;
            }

            i2 = y.iterator();
            return (s = s4);
        }

        public bool hasNext()
        {
            return act().hasNext();
        }

        public E next()
        {
            return act().next();
        }

        public void remove()
        {
            return i2.remove();
        }
    }

    Iterator<E> s2 = new Iterator<E>()
    {
        Iterator<E> act()
        {
            if(i1.hasNext())
            {
                return i1;
            }

            i2 = y.iterator();
            return (s = s3);
        }

        public bool hasNext()
        {
            return act().hasNext();
        }

        public E next()
        {
            return act().next();
        }

        public void remove()
        {
            return i1.remove();
        }
    };

    Iterator<E> s1 = new Iterator<E>()
    {
        Iterator<E> act()
        {
            i1 = x.iterator();
            return s = s2;
        }

        public bool hasNext()
        {
            return act().hasNext();
        }

        public E next()
        {
            return act().next();
        }

        public void remove()
        {
            return act().remove();
        }
    };

    s = s1;
    return new Iterator<T>()
    {
        public bool hasNext()
        {
            return s.hasNext();
        }

        public E next()
        {
            return s.next();
        }

        public void remove()
        {
            return s.remove();
        }
    };
}

public static <T> Iterable<T> concat(Iterable<T> x, Iterable<T> y)
{
    return new Iterable<T>()
    {
        public Iterator<T> iterator()
        {
            return concat_(x, y)
        }
    };
}

// tada!

If you all will pardon my 3AM pseudo java...


try this

  • com.infomancers.collections.yield

check this article for a sample implementation as well:

  • Implementation details for Java Yielder


I don't understand why people are talking about threads... is there something I don't know about yield return?

To my understanding yield return just saves the method stack and restores it at a later time. To implement yield return you just have to save the state manually. See the Java iterator classes for details, though for a linked list you can just get away with saving the current item. For an array you'd just need the index.


Just to help readers understand the small details.

If you create a new list containing all the resulting elements and return the list, then this is a good implementation, simple enough to code. You can have as interesting data structure as you need, and when scanning it for the right entries, just return a list of all the matches, and your client will iterate on the list.

If you want to save a state, it may be more complicated. You'll need to get to where you've been every time your function is called. Not to mention re-entrant issues, etc.

The solution with threads does not create a new list. And it is as simple as the first solution. The only issue is that you involve a thread synchronization which is a bit more hard to code, and has its performance penalties.

So, yes, yield return is great and is missing from Java. Yet there are workarounds.


a yield return operation can be regarded as

  1. put some checkpoint there
  2. write a value in somewhere
  3. when resume is acquired, jump to instruction next to it.

therefore I implement it as a state machine alike class, coroutine. within this mechanism, each instruction has its instruction pointer, index, and instruction may has a label along with it, so we can use jmp(label) to jump to the label.

  1. add some mechanism to achieve a goto syntax: addInstruction(..) and jmp()
  2. and store status/variable in somewhere: setVariable(name,value), yield(value)
  3. a way to temporarily suspend / resume: exec()

for example:

    public class FibbonaciCoroutine implements Iterator<BigInteger> {
        BigInteger[] bucket = { new BigInteger("1"), new BigInteger("1"), new BigInteger("0") };
        int idx = 2;
        Coroutine coroutine = new Coroutine((pthis) -> {
    
            pthis.addInstruction("_label1", (me) -> {
                int p1 = idx - 2;
                int p2 = idx - 1;
                if (p1 < 0)
                    p1 += 3;
                if (p2 < 0)
                    p2 += 3;
                bucket[idx] = bucket[p1].add(bucket[p2]);
                idx = (idx + 1) % bucket.length;
    
                me.yield(bucket[idx]);
    
            });
            // goto
            pthis.addInstruction((me) -> {
                me.jmp("_label1");
            });
            pthis.start();
        });
    
        @Override
        public boolean hasNext() {
            return !coroutine.isStopped();
        }
    
        @Override
        public BigInteger next() {
            while (coroutine.exec())
                ;
            return coroutine.getYieldValue();
        }
    
        public static void main(String[] argv) {
            FibbonaciCoroutine cor = new FibbonaciCoroutine();
            for (int i = 0; i < 100 && cor.hasNext(); ++i) {
                System.out.printf("%d ", cor.next());
            }
        }
    
    }

see FibonacciCoroutine.java

Back to your question...

    LinkedListObject<something> current = first;
    While (current != null){
       yield return current.getValue();
       current = current.getNext()
    }

is able to convert to following code

   //some where in class, or use Var<> to wrap it.
   Var<LinkedListObject<something> > current = new Var<>(first);
   Coroutine cor = new Coroutine();
   cor.While((ins)->current.get() != null).run((ins)->{
       ins.addInstruction((c)->c.yield(current.get().getValue()) );
       // wrap it with lambda for being a checkpoint
       ins.addInstruction( (c)->current.set(current.get().getNext()) );
   });

so we can use its getYieldValue() to retrive result, or simply call coroutine.iterator to convert coroutine into an iterator


It's been ages since this question was posted, and I'm quite unsure about writing an answer to such an old question, but another way of achieving this has occurred to me and I want to present it here in case it helps anyone searching for this, given the fact that this SO thread was one of the very first hits in Google.

The code shown below has been compiled in my head. There's absolutely no guarantee it's correct, but the idea behind it is.

Use callbacks

Yes, I know, it is not the same as a yield return. But I don't think OP wanted specifically a replacement that could be (with the appropriate amount of sugar) dropped into a for (var x : <some_iterator>). My approach instead does something more akin to C#'s linq (or Java's stream()), not the yielded return.

@FunctionalInterface
public interface Looper<T> {
    void each(T item);
}



public interface Loopable<T> {
    void forEach(Looper<? super T> looper);
}

Then you would implement Loopable<T> in your code, creating this pseudo-iterator. Which is really not, it's just making use of @FunctionalInterfaces, which is Java's way of doing callbacks (sorta)

public class WhatEvs implements Loopable<WhatEvs> {
    // ...
    @Override
    public void forEach(Looper<? super T> looper) {
        while(your_condition) {
            WhatEvs nextItem = getNextItem();
            looper.each(nextItem);
        }
    }
}


I think the best way Java can offer is Stream.generate() method. Your case would look like this.

static <something> Stream<something> someMethod() {
        LinkedListObject<something> someObject = ...;
        var current = new AtomicReference<>(someObject);
        Supplier<something> getElement = () -> {
            if (current.get() != null) {
                var currentObject = current.get();
                /// ... some code ...
                current.set(current.get().getNext());
                return currentObject.getValue();
            }
            
            return null;
        };

        return Stream.generate(getElement).takeWhile(Objects::nonNull);
}

Note that using AtomicReference is neccesary since code within any lambda cannot change values/references in variables declared outside of this lambda.

Considering that you wish to stop yielding as soon as you meet null, we can write that in a much simplier way.

static <something> Stream<something> someMethod() {
        LinkedListObject<something> someObject = ...;
        return Stream.iterate(someObject, something::getNext)
                     .takeWhile(Objects::nonNull)
                     .peek(current -> {/* some code */})
                     .map(something::getValue);
}


If you want the full functionality of yield return, you probably need to set this up in two threads-- one for the first method, and one for the second. Then the first thread should wait until the second thread puts its value somewhere accessible and notifys it that it's ready. Then the first thread would process that value, wait for the next value, etc.


use my java library to realize yield return without using threads or byte code manipulation

http://www.heinerkuecker.de/YieldReturnForNested.html

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜