[/
          Copyright Oliver Kowalke 2009.
 Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at
          http://www.boost.org/LICENSE_1_0.txt
]

[section:motivation Motivation]

In order to support a broad range of execution control behaviour __push_coro__ and
__pull_coro__ can be used to ['escape-and-reenter] loops, to ['escape-and-reenter]
recursive computations and for ['cooperative] multitasking
helping to solve problems in a much simpler and more elegant way than with only
a single flow of control.


[heading 'same fringe' problem]

The advantages can be seen particularly clearly with the use of a recursive
function, such as traversal of trees.
If traversing two different trees in the same deterministic order produces the
same list of leaf nodes, then both trees have the same fringe.

[$../../../../libs/coroutine/doc/images/fringe.png [align center]]

Both trees in the picture have the same fringe even though the structure of the
trees is different.

The same fringe problem could be solved using coroutines by iterating over the
leaf nodes and comparing this sequence via \cpp{std::equal()}. The range of data
values is generated by function ['traverse()] which recursively traverses the
tree and passes each node's data value to its __push_coro__.
__push_coro__ suspends the recursive computation and transfers the data value to
the main execution context.
__pull_coro_it__, created from __pull_coro__, steps over those data values and
delivers them to  ['std::equal()] for comparison. Each increment of __pull_coro_it__
resumes ['traverse()]. Upon return from ['iterator::operator++()], either
a new data value is available, or tree traversal is finished (iterator is
invalidated).

        struct node{
            typedef boost::shared_ptr<node> ptr_t;

            // Each tree node has an optional left subtree,
            // an optional right subtree and a value of its own.
            // The value is considered to be between the left
            // subtree and the right.
            ptr_t       left,right;
            std::string value;

            // construct leaf
            node(const std::string& v):
                left(),right(),value(v)
            {}
            // construct nonleaf
            node(ptr_t l,const std::string& v,ptr_t r):
                left(l),right(r),value(v)
            {}

            static ptr_t create(const std::string& v){
                return ptr_t(new node(v));
            }

            static ptr_t create(ptr_t l,const std::string& v,ptr_t r){
                return ptr_t(new node(l,v,r));
            }
        };

        node::ptr_t create_left_tree_from(const std::string& root){
            /* --------
                 root
                 / \
                b   e
               / \
              a   c
             -------- */
            return node::create(
                    node::create(
                        node::create("a"),
                        "b",
                        node::create("c")),
                    root,
                    node::create("e"));
        }

        node::ptr_t create_right_tree_from(const std::string& root){
            /* --------
                 root
                 / \
                a   d
                   / \
                  c   e
               -------- */
            return node::create(
                    node::create("a"),
                    root,
                    node::create(
                        node::create("c"),
                        "d",
                        node::create("e")));
        }

        // recursively walk the tree, delivering values in order
        void traverse(node::ptr_t n,
                      boost::coroutines::coroutine<std::string>::push_type& out){
            if(n->left) traverse(n->left,out);
            out(n->value);
            if(n->right) traverse(n->right,out);
        }

        // evaluation
        {
            node::ptr_t left_d(create_left_tree_from("d"));
            boost::coroutines::coroutine<std::string>::pull_type left_d_reader(
                [&]( boost::coroutines::coroutine<std::string>::push_type & out){
                    traverse(left_d,out);
                });

            node::ptr_t right_b(create_right_tree_from("b"));
            boost::coroutines::coroutine<std::string>::pull_type right_b_reader(
                [&]( boost::coroutines::coroutine<std::string>::push_type & out){
                    traverse(right_b,out);
                });

            std::cout << "left tree from d == right tree from b? "
                      << std::boolalpha
                      << std::equal(boost::begin(left_d_reader),
                                    boost::end(left_d_reader),
                                    boost::begin(right_b_reader))
                      << std::endl;
        }
        {
            node::ptr_t left_d(create_left_tree_from("d"));
            boost::coroutines::coroutine<std::string>::pull_type left_d_reader(
                [&]( boost::coroutines::coroutine<std::string>::push_type & out){
                    traverse(left_d,out);
                });

            node::ptr_t right_x(create_right_tree_from("x"));
            boost::coroutines::coroutine<std::string>::pull_type right_x_reader(
                [&]( boost::coroutines::coroutine<std::string>::push_type & out){
                    traverse(right_x,out);
                });

            std::cout << "left tree from d == right tree from x? "
                      << std::boolalpha
                      << std::equal(boost::begin(left_d_reader),
                                    boost::end(left_d_reader),
                                    boost::begin(right_x_reader))
                      << std::endl;
        }
        std::cout << "Done" << std::endl;

        output:
        left tree from d == right tree from b? true
        left tree from d == right tree from x? false
        Done


[heading chaining coroutines]

The following example demonstrates how coroutines could be chained.

        typedef boost::coroutines::coroutine<std::string> coro_t;

        // deliver each line of input stream to sink as a separate string
        void readlines(coro_t::push_type& sink, std::istream& in){
            std::string line;
            while(std::getline(in,line))
                sink(line);
        }

        void tokenize(coro_t::push_type& sink, coro_t::pull_type& source){
            // This tokenizer doesn't happen to be stateful: you could reasonably
            // implement it with a single call to push each new token downstream. But
            // I've worked with stateful tokenizers, in which the meaning of input
            // characters depends in part on their position within the input line.
            BOOST_FOREACH(std::string line, source){
                std::string::size_type pos = 0;
                while(pos < line.length()){
                    if (line[pos] == '"'){
                        std::string token;
                        ++pos;              // skip open quote
                        while (pos < line.length() && line[pos] != '"')
                            token += line[pos++];
                        ++pos;              // skip close quote
                        sink(token);        // pass token downstream
                    } else if (std::isspace(line[pos])){
                        ++pos;              // outside quotes, ignore whitespace
                    } else if (std::isalpha(line[pos])){
                        std::string token;
                        while (pos < line.length() && std::isalpha(line[pos]))
                            token += line[pos++];
                        sink(token);        // pass token downstream
                    } else {                // punctuation
                        sink(std::string(1,line[pos++]));
                    }
                }
            }
        }

        void only_words(coro_t::push_type& sink,coro_t::pull_type& source){
            BOOST_FOREACH(std::string token,source){
                if (!token.empty() && std::isalpha(token[0]))
                    sink(token);
            }
        }

        void trace(coro_t::push_type& sink, coro_t::pull_type& source){
            BOOST_FOREACH(std::string token,source){
                std::cout << "trace: '" << token << "'\n";
                sink(token);
            }
        }

        struct FinalEOL{
            ~FinalEOL(){
                std::cout << std::endl;
            }
        };

        void layout(coro_t::pull_type& source,int num,int width){
            // Finish the last line when we leave by whatever means
            FinalEOL eol;

            // Pull values from upstream, lay them out 'num' to a line
            for (;;){
                for (int i = 0; i < num; ++i){
                    // when we exhaust the input, stop
                    if (!source) return;

                    std::cout << std::setw(width) << source.get();
                    // now that we've handled this item, advance to next
                    source();
                }
                // after 'num' items, line break
                std::cout << std::endl;
            }
        }

        // For example purposes, instead of having a separate text file in the
        // local filesystem, construct an istringstream to read.
        std::string data(
            "This is the first line.\n"
            "This, the second.\n"
            "The third has \"a phrase\"!\n"
            );

        {
            std::cout << "\nfilter:\n";
            std::istringstream infile(data);
            coro_t::pull_type reader(boost::bind(readlines, _1, boost::ref(infile)));
            coro_t::pull_type tokenizer(boost::bind(tokenize, _1, boost::ref(reader)));
            coro_t::pull_type filter(boost::bind(only_words, _1, boost::ref(tokenizer)));
            coro_t::pull_type tracer(boost::bind(trace, _1, boost::ref(filter)));
            BOOST_FOREACH(std::string token,tracer){
                // just iterate, we're already pulling through tracer
            }
        }

        {
            std::cout << "\nlayout() as coroutine::push_type:\n";
            std::istringstream infile(data);
            coro_t::pull_type reader(boost::bind(readlines, _1, boost::ref(infile)));
            coro_t::pull_type tokenizer(boost::bind(tokenize, _1, boost::ref(reader)));
            coro_t::pull_type filter(boost::bind(only_words, _1, boost::ref(tokenizer)));
            coro_t::push_type writer(boost::bind(layout, _1, 5, 15));
            BOOST_FOREACH(std::string token,filter){
                writer(token);
            }
        }

        {
            std::cout << "\nfiltering output:\n";
            std::istringstream infile(data);
            coro_t::pull_type reader(boost::bind(readlines,_1,boost::ref(infile)));
            coro_t::pull_type tokenizer(boost::bind(tokenize,_1,boost::ref(reader)));
            coro_t::push_type writer(boost::bind(layout,_1,5,15));
            // Because of the symmetry of the API, we can use any of these
            // chaining functions in a push_type coroutine chain as well.
            coro_t::push_type filter(boost::bind(only_words,boost::ref(writer),_1));
            BOOST_FOREACH(std::string token,tokenizer){
                filter(token);
            }
        }



[heading asynchronous operations with boost.asio]

In the past the code using asio's ['asynchronous operations] was scattered by callbacks.
__boost_asio__ provides with its new ['asynchronous result] feature a new way to simplify the
code and make it easier to read.
__yield_context__ uses internally __boost_coroutine__:

        void echo(boost::asio::ip::tcp::socket& socket,boost::asio::yield_context yield){
            char data[128];
            // read asynchronous data from socket
            // execution context will be suspended until
            // some bytes are read from socket
            std::size_t n=socket.async_read_some(boost::asio::buffer(data),yield);
            // write some bytes asynchronously
            boost::asio::async_write(socket,boost::asio::buffer(data,n),yield);
        }

[endsect]
