stream/test_loop.cpp

Go to the documentation of this file.

/***************************************************************************
 *  stream/test_loop.cpp
 *
 *  example for building a loop of stream operations
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright © 2011 Jaroslaw Fedorowicz <fedorow@cs.uni-frankfurt.de>
 *  Copyright © 2011 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
 *
 *  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)
 **************************************************************************/

//! \example stream/test_loop.cpp
//! This is an example of how to use some basic algorithms from the
//! stream package to form a loop iterating over the data.
//! Some input is generated, sorted, some elements are filtered out.
//! The remaining elements are transformed, sorted and processed in the
//! next pass. The loop will terminate if at most one element remains.
//! A split sorter is used to cut the data flow (and type dependency) cycle.

#include <iostream>
#include <limits>

#include <stxxl/mng>
#include <stxxl/vector>
#include <stxxl/stream>

using std::cout;
using std::endl;

const stxxl::uint64 memory_to_use = 3ul * 1024 * 1024 * 1024;

bool verbose;

struct random_generator
{
    typedef stxxl::random_number32::value_type value_type;
    typedef stxxl::uint64 size_type;
    value_type current;
    size_type count;
    stxxl::random_number32 rnd;

    random_generator(size_type _count) : count(_count)
    {
        if (verbose) cout << "Random Stream: ";
        current = rnd();
    }

    value_type operator * () const
    {
        return current;
    }
    random_generator & operator ++ ()
    {
        count--;
        if (verbose) {
            cout << current << ", ";
            if (empty()) cout << endl;
        }
        current = rnd();
        return *this;
    }
    bool empty() const
    {
        return (count == 0);
    }
};

template <typename value_type>
struct Cmp : std::binary_function<value_type, value_type, bool>
{
    bool operator () (const value_type & a, const value_type & b) const
    {
        return a < b;
    }
    static value_type min_value()
    {
        return value_type((std::numeric_limits<value_type>::min)());
    }
    static value_type max_value()
    {
        return value_type((std::numeric_limits<value_type>::max)());
    }
};

template <typename Input>
struct filter
{
    typedef typename Input::value_type value_type;
    typedef stxxl::uint64 size_type;
    Input & input;
    value_type filter_value;
    size_type & counter;

    void apply_filter()
    {
        while (!input.empty() && *input == filter_value) {
            ++input;
            counter++;
        }
    }

    filter(Input & _input, value_type _filter_value, size_type & _counter) : input(_input), filter_value(_filter_value), counter(_counter)
    {
        apply_filter();
    }

    const value_type operator * () const
    {
        return *input;
    }

    filter & operator ++ ()
    {
        ++input;
        apply_filter();
        return *this;
    }

    bool empty() const
    {
        return input.empty();
    }
};

template <typename Input>
struct output
{
    typedef typename Input::value_type value_type;
    Input & input;

    output(Input & _input) : input(_input) { }

    const value_type operator * () const
    {
        return *input;
    }

    output & operator ++ ()
    {
        if (verbose) cout << *input << ", ";
        ++input;
        if (empty() && verbose)
            cout << endl;
        return *this;
    }

    bool empty() const
    {
        return input.empty();
    }
};

template <typename Input>
struct shuffle
{
    typedef typename Input::value_type value_type;
    Input & input;
    value_type current, next;
    bool even, is_empty;

    // from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
    int count_bits(stxxl::uint64 v)
    {
        int c;
        for (c = 0; v; c++) {
            v &= v - 1;
        }
        return c;
    }

    void apply_shuffle()
    {
        is_empty = input.empty();
        if (!is_empty) {
            current = *input;
            ++input;
            if (!input.empty()) {
                STXXL_STATIC_ASSERT(sizeof(value_type) == 4);
                stxxl::uint64 combined = current;
                combined = combined << 32 | *input;
                combined = (1ul << count_bits(combined)) - 1;
                current = combined >> 32;
                next = combined;
            }
        }
    }

    shuffle(Input & _input) : input(_input), current(0), next(0), even(true), is_empty(false)
    {
        apply_shuffle();
    }

    value_type operator * () const
    {
        return current;
    }

    shuffle & operator ++ ()
    {
        even = !even;
        is_empty = input.empty();
        if (even) {
            ++input;
            apply_shuffle();
        } else {
            current = next;
        }
        return *this;
    }

    bool empty() const
    {
        return is_empty;
    }
};

typedef random_generator input_generator_type;
typedef Cmp<input_generator_type::value_type> cmp;
typedef stxxl::stream::runs_creator<input_generator_type, cmp> runs_creator_type0;
typedef runs_creator_type0::sorted_runs_type sorted_runs_type;
typedef stxxl::stream::runs_merger<sorted_runs_type, cmp> runs_merger_type;
typedef output<runs_merger_type> output_type;
typedef filter<output_type> filter_type0;
typedef filter<filter_type0> filter_type1;
typedef shuffle<filter_type1> shuffle_type;
typedef stxxl::stream::runs_creator<shuffle_type, cmp> runs_creator_type1;

int main(int argc, char ** argv)
{
    if (argc < 2) {
        cout << "Usage: " << argv[0] << " count [Options]\nOptions: -v \t prints elements of each iteration\n";
        return EXIT_FAILURE;
    }

    stxxl::block_manager::get_instance();

    verbose = (argc == 3) && !strcmp(argv[2], "-v");

    stxxl::uint64 total = atoi(argv[1]);

    input_generator_type input_stream(total);

    runs_creator_type0 runs_creator(input_stream, cmp(), memory_to_use);

    sorted_runs_type& sorted_runs = runs_creator.result();

    stxxl::uint64 counter = 0;
    int i;

    for (i = 0; counter < total - 1; ++i) {
        if (verbose) cout << "Iteration " << i << ": ";

        runs_merger_type runs_merger(sorted_runs, cmp(), memory_to_use);

        output_type output_stream(runs_merger);

        filter_type0 filter0(output_stream, 0, counter);

        filter_type1 filter1(filter0, filter_type1::value_type(-1), counter);

        shuffle_type shuffled_stream(filter1);

        runs_creator_type1 runs_creator(shuffled_stream, cmp(), memory_to_use);

        sorted_runs.swap( runs_creator.result() );
    }

    runs_merger_type runs_merger(sorted_runs, cmp(), memory_to_use);

    while (!runs_merger.empty()) {
        if (verbose) cout << "Iteration " << i << ": " << *runs_merger << endl;
        ++runs_merger;
    }
    cout << "\nIteration needed: " << i << endl;

    return 0;
}

// vim: et:ts=4:sw=4