#include<iostream>
#include<algorithm>
#include<vector>
#include<limits>
#include<numeric>
using namespace std;


// output stream for vectors
template < class T >
ostream & operator << ( ostream & ost, const vector<T> & v )
{
    typename vector<T>::const_iterator i = v.begin();
    for ( ; i != v.end() ; ++i )
        ost << *i << " ";
    return ost;
}

// sequence unary
template < class T >
class Sequence
{
    public:
        int num;
        Sequence( const int n = 0 ) : num(n) {}
        void operator () ( T & foo ) { foo = ++num; }
};

// random generator and unary
template < class T >
class Random
{
    public:
        int mod;
        Random( const int n = 0 ) : mod(n) { seed(); }
        T operator () ( void ) { return rand(); }
        void operator () ( T & foo ) { foo = rand() % mod; }
        static bool seeded;
        static void seed ( void )
        {
            if ( !seeded )
            {
                seeded = true;
                srand(time(0));
            }
        }
};
template < class T > bool Random<T>::seeded = false;

// mod unary
template<class T>
class Mod
{
    public:
        int num;
        Mod( const int n = static_cast<int>(INFINITY) ) : num(n) {}
        void operator() (T & x) { x %= num; }
};

// print unary
template<class T>
class Print
{
    public:
        ostream& os;
        int count;
        Print(ostream& out) : os(out), count(0) {}
        void operator() (T & x) { os << x << ' '; ++count; }
};

template < class T >
bool mod2 ( const T & foo )
{
    return ( foo % 2 );
}

int main()
{
    vector<int> v(5);

    // set each element to the return from rand
    srand(time(0));
    generate( v.begin(), v.end(), rand );
    Print<int> P = for_each(v.begin(), v.end(), Print<int>(cout));
    cout << endl << P.count << " objects printed." << endl;
    // now mod each value by 10
    for_each(v.begin(), v.end(), Mod<int>(10));
    cout << "mod those by 10" << endl;
    cout << v << endl;
    generate(v.begin(), v.end(), Random<int>() );
    cout << "random" << endl;
    cout << v << endl;
    for_each(v.begin(), v.end(), Random<int>(20) );
    cout << "random mod 20" << endl;
    cout << v << endl;

    // resize and sequence them
    // note: iota does the same thing buf it is
    // depricated but may be in the old headers
    v.resize(10);
    for_each( v.begin(), v.end(), Sequence<int>() );
    cout << "v = " << v << endl;
    // swap two elements
    swap ( v[7], v[9] );
    cout << "swap positions 7 and 9" << endl;
    iter_swap ( v.begin()+6, v.begin()+8 );
    cout << "swap iterators 6 and 8" << endl;
    cout << "v = " << v << endl;

    vector<int> x(10);
    for_each( x.begin(), x.end(), Sequence<int>() );
    // shuffle the elements
    srand48(time(0));   // random_shuffle typically uses rand48, not rand
    random_shuffle( x.begin(), x.end() );
    cout << "x = " << x << endl;

    cout << "swap the first 5 elements" << endl;
    swap_ranges ( v.begin(), v.begin() + 5, x.begin() );
    cout << "v = " << v << endl;
    cout << "x = " << x << endl;

    sort( v.begin(), v.end() );
    cout << "sorted v = " << v << endl;
    vector<int>::iterator new_end = unique( v.begin(), v.end() );
    vector<int> y ( v.begin(), new_end );
    cout << "v = " << v << endl;
    cout << "y = " << y << endl;

    // built in binary search
    for ( int i = 0 ; i < 8 ; ++i )
        cout << "searching for " << i << " - "
            << (binary_search(y.begin(), y.end(), i) ? "yes" : "no")
            << endl;

    sort( x.begin(), x.end() );
    cout << "sorted x = " << x << endl;
    // the partition treats need something castable to bool
    new_end = partition( x.begin(), x.end(), mod2<int> );
    y.assign ( x.begin(), new_end );
    cout << "mod2 partition x = " << x << endl;
    cout << "y = " << y << endl;

    // we need to insure the vectors are the same size for these
    x.resize( y.size() );
    for_each( x.begin(), x.end(), Sequence<int>() );
    cout << "x = " << x << endl;
    // play with transform
    v.resize( y.size() );
    cout << "transform y + x" << endl;
    transform( y.begin(), y.end(), x.begin(), v.begin(), plus<int>());
    cout << "result = " << v << endl;
    cout << "transform y - x" << endl;
    transform( y.begin(), y.end(), x.begin(), v.begin(), minus<int>());
    cout << "result = " << v << endl;
    transform( y.begin(), y.end(), v.begin(), negate<int>());
    // some numeric stuff
    cout << "v = negation of y = " << v << endl;
    cout << "the sum = "
        << accumulate(v.begin(), v.end(), 0) << endl;
    cout << "the product = "
        << accumulate(v.begin(), v.end(), 1, multiplies<int>() ) << endl;
    vector<int> z( v.size() );
    adjacent_difference(v.begin(), v.end(), z.begin() );
    cout << "adjacent differences of v = " << z << endl;

    v.resize(3);
    for_each( v.begin(), v.end(), Sequence<int>() );
    cout << "v = " << v << endl;
    // now lets play the permutation game
    cout << "permutations of v" << endl;
    cout << v << endl;
    while ( next_permutation ( v.begin(), v.end() ) )
        cout << v << endl;

    return 0;
}