/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */

#if 0

////////// algo/foreach1.cpp    p334

/********* #include "algostuff.hpp" *********/
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>

/* PRINT_ELEMENTS()
 * - prints optional C-string optcstr followed by
 * - all elements of the collection coll
 * - separated by spaces
 */
template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
    typename T::const_iterator pos;

    std::cout << optcstr;
    for (pos=coll.begin(); pos!=coll.end(); ++pos) {
        std::cout << *pos << ' ';
    }
    std::cout << std::endl;
}

/* INSERT_ELEMENTS (collection, first, last)
 * - fill values from first to last into the collection
 * - NOTE: NO half-open range
 */
template <class T>
inline void INSERT_ELEMENTS (T& coll, int first, int last)
{
    for (int i=first; i<=last; ++i) {
        coll.insert(coll.end(),i);
    }
}
/********* #include "algostuff.hpp" *********/
using namespace std;

// function called for each element
void print (int elem)
{
    cout << elem << ' ';
}

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,9);

    // call print() for each element
    for_each (coll.begin(), coll.end(),  // range
              print);                    // operation
    cout << endl;
    return 0;
}

// 1 2 3 4 5 6 7 8 9




////////// algo/foreach2.cpp    p335

#include "algostuff.hpp"
using namespace std;

// function object that adds the value with which it is initialized
template <class T>
class AddValue {
  private:
    T theValue;    // value to add
  public:
    // constructor initializes the value to add
    AddValue (const T& v) : theValue(v) {
    }

    // the function call for the element adds the value
    void operator() (T& elem) const {
        elem += theValue;
    }
};

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,9);

    // add ten to each element
    for_each (coll.begin(), coll.end(),       // range
              AddValue<int>(10));             // operation
    PRINT_ELEMENTS(coll);

    // add value of first element to each element
    for_each (coll.begin(), coll.end(),       // range
              AddValue<int>(*coll.begin()));  // operation
    PRINT_ELEMENTS(coll);
    return 0;
}

// 11 12 13 14 15 16 17 18 19
// 22 23 24 25 26 27 28 29 30




////////// algo/foreach3.cpp    p336

#include "algostuff.hpp"
using namespace std;

// function object to process the mean value
class MeanValue {
  private:
    long num;    // number of elements
    long sum;    // sum of all element values
  public:
    // constructor
    MeanValue () : num(0), sum(0) {
    }

    // function call
    // - process one more element of the sequence
    void operator() (int elem) {
        num++;          // increment count
        sum += elem;    // add value
    }

    // return mean value (implicit type conversion)
    operator double() {
        return static_cast<double>(sum) / static_cast<double>(num);
    }
};

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,8);

    // process and print mean value
    double mv = for_each (coll.begin(), coll.end(),  // range
                          MeanValue());              // operation
    cout << "mean value: " << mv << endl;
    return 0;
}

// mean value: 4.5




////////// algo/count1.cpp    p338

#include "algostuff.hpp"
using namespace std;

bool isEven (int elem)
{
    return elem % 2 == 0;
}

int main()
{
    vector<int> coll;
    int num;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll,"coll: ");

    // count and print elements with value 4
    num = count (coll.begin(), coll.end(),       // range
                 4);                             // value
    cout << "number of elements equal to 4:      " << num << endl;

    // count elements with even value
    num = count_if (coll.begin(), coll.end(),    // range
                    isEven);                     // criterion
    cout << "number of elements with even value: " << num << endl;

    // count elements that are greater than value 4
    num = count_if (coll.begin(), coll.end(),    // range
                    bind2nd(greater<int>(),4));  // criterion
    cout << "number of elements greater than 4:  " << num << endl;
    return 0;
}

// coll: 1 2 3 4 5 6 7 8 9
// number of elements equal to 4:      1
// number of elements with even value: 4
// number of elements greater than 4:  5




////////// algo/minmax1.cpp    p340

#include <cstdlib>
#include "algostuff.hpp"
using namespace std;

bool absLess (int elem1, int elem2)
{
    return abs(elem1) < abs(elem2);
}

int main()
{
    deque<int> coll;

    INSERT_ELEMENTS(coll,2,8);
    INSERT_ELEMENTS(coll,-3,5);

    PRINT_ELEMENTS(coll);

    // process and print minimum and maximum
    cout << "minimum: "
         << *min_element(coll.begin(),coll.end())
         << endl;
    cout << "maximum: "
         << *max_element(coll.begin(),coll.end())
         << endl;

    // process and print minimum and maximum of absolute values
    cout << "minimum of absolute values: "
         << *min_element(coll.begin(),coll.end(),
                         absLess)
         << endl;
    cout << "maximum of absolute values: "
         << *max_element(coll.begin(),coll.end(),
                         absLess)
         << endl;
    return 0;
}

// 2 3 4 5 6 7 8 -3 -2 -1 0 1 2 3 4 5
// minimum: -3
// maximum: 8
// minimum of absolute values: 0
// maximum of absolute values: 8




////////// algo/find1.cpp    p342

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    INSERT_ELEMENTS(coll,1,9);

    PRINT_ELEMENTS(coll,"coll: ");

    // find first element with value 4
    list<int>::iterator pos1;
    pos1 = find (coll.begin(), coll.end(),    // range
                 4);                          // value

    /* find second element with value 4
     * - note: continue the search behind the first 4 (if any)
     */
    list<int>::iterator pos2;
    if (pos1 != coll.end()) {
        pos2 = find (++pos1, coll.end(),      // range
                     4);                      // value
    }

    /* print all elements from first to second 4 (both included)
     * - note: now we need the position of the first 4 again (if any)
     * - note: we have to pass the position behind the second 4 (if any)
     */
    if (pos1!=coll.end() && pos2!=coll.end()) {
        copy (--pos1, ++pos2,
              ostream_iterator<int>(cout," "));
        cout << endl;
    }
    return 0;
}

// coll: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
// 4 5 6 7 8 9 1 2 3 4




////////// algo/find2.cpp    p343

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;
    vector<int>::iterator pos;

    INSERT_ELEMENTS(coll,1,9);

    PRINT_ELEMENTS(coll,"coll: ");

    // find first element greater than 3
    pos = find_if (coll.begin(), coll.end(),    // range
                   bind2nd(greater<int>(),3));  // criterion

    // print its position
    cout << "the "
         << distance(coll.begin(),pos) + 1
         << ". element is the first greater than 3" << endl;

    // find first element divisible by 3
    pos = find_if (coll.begin(), coll.end(),
                   not1(bind2nd(modulus<int>(),3)));

    // print its position
    cout << "the "
         << distance(coll.begin(),pos) + 1
         << ". element is the first divisible by 3" << endl;
    return 0;
}

// coll: 1 2 3 4 5 6 7 8 9
// the 4. element is the first greater than 3
// the 3. element is the first divisible by 3




////////// algo/searchn1.cpp    p345

#include "algostuff.hpp"
using namespace std;

int main()
{
   deque<int> coll;

   INSERT_ELEMENTS(coll,1,9);
   PRINT_ELEMENTS(coll);

   // find four consecutive elements with value 3
   deque<int>::iterator pos;
   pos = search_n (coll.begin(), coll.end(),    // range
                   4,                           // count
                   3);                          // value

   // print result
   if (pos != coll.end()) {
       cout << "four consecutive elements with value 3 "
            << "start with " << distance(coll.begin(),pos) +1
            << ". element" << endl;
   }
   else {
       cout << "no four consecutive elements with value 3 found"
            << endl;
   }

   // find four consecutive elements with value greater than 3
   pos = search_n (coll.begin(), coll.end(),    // range
                   4,                           // count
                   3,                           // value
                   greater<int>());             // criterion

   // print result
   if (pos != coll.end()) {
       cout << "four consecutive elements with value > 3 "
            << "start with " << distance(coll.begin(),pos) +1
            << ". element" << endl;
   }
   else {
       cout << "no four consecutive elements with value > 3 found"
            << endl;
   }
   return 0;
}

// 1 2 3 4 5 6 7 8 9
// no four consecutive elements with value 3 found
// four consecutive elements with value > 3 start with 4. element




////////// algo/search1.cpp    p348

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> coll;
    list<int> subcoll;

    INSERT_ELEMENTS(coll,1,7);
    INSERT_ELEMENTS(coll,1,7);

    INSERT_ELEMENTS(subcoll,3,6);

    PRINT_ELEMENTS(coll,   "coll:    ");
    PRINT_ELEMENTS(subcoll,"subcoll: ");

    // search first occurrence of subcoll in coll
    deque<int>::iterator pos;
    pos = search (coll.begin(), coll.end(),         // range
                  subcoll.begin(), subcoll.end());  // subrange

    // loop while subcoll found as subrange of coll
    while (pos != coll.end()) { 
        // print position of first element
        cout << "subcoll found starting with element "
             << distance(coll.begin(),pos) + 1
             << endl;

        // search next occurrence of subcoll
        ++pos;
        pos = search (pos, coll.end(),                  // range
                      subcoll.begin(), subcoll.end());  // subrange
    }
    return 0;
}

// coll:    1 2 3 4 5 6 7 1 2 3 4 5 6 7
// subcoll: 3 4 5 6
// subcoll found starting with element 3
// subcoll found starting with element 10




////////// algo/search2.cpp    p349

#include "algostuff.hpp"
using namespace std;

// checks whether an element is even or odd
bool checkEven (int elem, bool even)
{
    if (even) {
        return elem % 2 == 0;
    }
    else {
        return elem % 2 == 1;
    }
}

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll,"coll: ");

    /* arguments for checkEven()
     * - check for: "even odd even"
     */
    bool checkEvenArgs[3] = { true, false, true };

    // search first subrange in coll
    vector<int>::iterator pos;
    pos = search (coll.begin(), coll.end(),       // range
                  checkEvenArgs, checkEvenArgs+3, // subrange values
                  checkEven);                     // subrange criterion

    // loop while subrange found
    while (pos != coll.end()) {
        // print position of first element
        cout << "subrange found starting with element "
             << distance(coll.begin(),pos) + 1
             << endl;

        // search next subrange in coll
        pos = search (++pos, coll.end(),              // range
                      checkEvenArgs, checkEvenArgs+3, // subr. values
                      checkEven);                     // subr. criterion
    }
    return 0;
}

// coll: 1 2 3 4 5 6 7 8 9
// subrange found starting with element 2
// subrange found starting with element 4
// subrange found starting with element 6




////////// algo/findend1.cpp    p351

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> coll;
    list<int> subcoll;

    INSERT_ELEMENTS(coll,1,7);
    INSERT_ELEMENTS(coll,1,7);

    INSERT_ELEMENTS(subcoll,3,6);

    PRINT_ELEMENTS(coll,   "coll:    ");
    PRINT_ELEMENTS(subcoll,"subcoll: ");

    // search last occurrence of subcoll in coll
    deque<int>::iterator pos;
    pos = find_end (coll.begin(), coll.end(),         // range
                    subcoll.begin(), subcoll.end());  // subrange

    // loop while subcoll found as subrange of coll
    deque<int>::iterator end(coll.end());
    while (pos != end) { 
        // print position of first element
        cout << "subcoll found starting with element "
             << distance(coll.begin(),pos) + 1
             << endl;

        // search next occurrence of subcoll
        end = pos;
        pos = find_end (coll.begin(), end,               // range
                        subcoll.begin(), subcoll.end()); // subrange
    }
    return 0;
}

// coll:    1 2 3 4 5 6 7 1 2 3 4 5 6 7
// subcoll: 3 4 5 6
// subcoll found starting with element 10
// subcoll found starting with element 3




////////// algo/findof1.cpp    p353

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;
    list<int> searchcoll;

    INSERT_ELEMENTS(coll,1,11);
    INSERT_ELEMENTS(searchcoll,3,5);

    PRINT_ELEMENTS(coll,      "coll:       ");
    PRINT_ELEMENTS(searchcoll,"searchcoll: ");

    // search first occurrence of an element of searchcoll in coll
    vector<int>::iterator pos;
    pos = find_first_of (coll.begin(), coll.end(),     // range
                         searchcoll.begin(),   // beginning of search set
                         searchcoll.end());    // end of search set
    cout << "first element of searchcoll in coll is element "
         << distance(coll.begin(),pos) + 1
         << endl;

    // search last occurrence of an element of searchcoll in coll
    vector<int>::reverse_iterator rpos;
    rpos = find_first_of (coll.rbegin(), coll.rend(),  // range
                          searchcoll.begin(),  // beginning of search set
                          searchcoll.end());   // end of search set
    cout << "last element of searchcoll in coll is element "
         << distance(coll.begin(),rpos.base())
         << endl;
    return 0;
}

// coll:       1 2 3 4 5 6 7 8 9 10 11
// searchcoll: 3 4 5
// first element of searchcoll in coll is element 3
// last element of searchcoll in coll is element 5




////////// algo/adjfind1.cpp    p354

#include "algostuff.hpp"
using namespace std;

// return whether the second object has double the value of the first
bool doubled (int elem1, int elem2)
{
   return elem1 * 2 == elem2;
}

int main()
{
   vector<int> coll;

   coll.push_back(1);
   coll.push_back(3);
   coll.push_back(2);
   coll.push_back(4);
   coll.push_back(5);
   coll.push_back(5);
   coll.push_back(0);

   PRINT_ELEMENTS(coll,"coll: ");

   // search first two elements with equal value
   vector<int>::iterator pos;
   pos = adjacent_find (coll.begin(), coll.end());

   if (pos != coll.end()) {
       cout << "first two elements with equal value have position "
            << distance(coll.begin(),pos) + 1
            << endl;
   }

   // search first two elements for which the second has double the value of the first
   pos = adjacent_find (coll.begin(), coll.end(),   // range
                        doubled);                   // criterion

   if (pos != coll.end()) {
       cout << "first two elements with second value twice the "
            << "first have pos. "
            << distance(coll.begin(),pos) + 1
            << endl;
   }
   return 0;
}

// coll: 1 3 2 4 5 5 0
// first two elements with equal value have position 5
// first two elements with second value twice the first have pos. 3




////////// algo/equal1.cpp    p356

#include "algostuff.hpp"
using namespace std;

bool bothEvenOrOdd (int elem1, int elem2)
{
    return elem1 % 2 == elem2 % 2;
}

int main()
{
    vector<int> coll1;
    list<int> coll2;

    INSERT_ELEMENTS(coll1,1,7);
    INSERT_ELEMENTS(coll2,3,9);

    PRINT_ELEMENTS(coll1,"coll1: ");
    PRINT_ELEMENTS(coll2,"coll2: ");

    // check whether both collections are equal
    if (equal (coll1.begin(), coll1.end(),  // first range
               coll2.begin())) {            // second range
        cout << "coll1 == coll2" << endl;
    }
    else {
        cout << "coll1 != coll2" << endl;
    }

    // check for corresponding even and odd elements
    if (equal (coll1.begin(), coll1.end(),  // first range
               coll2.begin(),               // second range
               bothEvenOrOdd)) {            // comparison criterion
        cout << "even and odd elements correspond" << endl;
    }
    else {
        cout << "even and odd elements do not correspond" << endl;
    }
    return 0;
}

// coll1: 1 2 3 4 5 6 7
// coll2: 3 4 5 6 7 8 9
// coll1 != coll2
// even and odd elements correspond




////////// algo/misma1.cpp    p358

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll1;
    list<int> coll2;

    INSERT_ELEMENTS(coll1,1,6);

    for (int i=1; i<=16; i*=2) {
        coll2.push_back(i);
    }
    coll2.push_back(3);

    PRINT_ELEMENTS(coll1,"coll1: ");
    PRINT_ELEMENTS(coll2,"coll2: ");

    // find first mismatch
    pair<vector<int>::iterator,list<int>::iterator> values;
    values = mismatch (coll1.begin(), coll1.end(),  // first range
                       coll2.begin());              // second range
    if (values.first == coll1.end()) {
        cout << "no mismatch" << endl;
    }
    else {
        cout << "first mismatch: "
             << *values.first  << " and "
             << *values.second << endl;
    }

    /* find first position where the element of coll1 is not
     * less than the corresponding element of coll2
     */
    values = mismatch (coll1.begin(), coll1.end(),  // first range
                       coll2.begin(),               // second range
                       less_equal<int>());          // criterion
    if (values.first == coll1.end()) {
        cout << "always less-or-equal" << endl;
    }
    else {
        cout << "not less-or-equal: "
             << *values.first << " and "
             << *values.second << endl;
    }
    return 0;
}

// coll1: 1 2 3 4 5 6
// coll2: 1 2 4 8 16 3
// first mismatch: 3 and 4
// not less-or-equal: 6 and 3




////////// algo/lexico1.cpp    p360

#include "algostuff.hpp"
using namespace std;

void printCollection (const list<int>& l)
{
    PRINT_ELEMENTS(l);
}

bool lessForCollection (const list<int>& l1, const list<int>& l2)
{
    return lexicographical_compare
                (l1.begin(), l1.end(),   // first range
                 l2.begin(), l2.end());  // second range
}

int main()
{
    list<int> c1, c2, c3, c4;

    // fill all collections with the same starting values
    INSERT_ELEMENTS(c1,1,5);
    c4 = c3 = c2 = c1;

    // and now some differences
    c1.push_back(7);
    c3.push_back(2);
    c3.push_back(0);
    c4.push_back(2);

    // create collection of collections
    vector<list<int> > cc;

    cc.push_back(c1);
    cc.push_back(c2);
    cc.push_back(c3);
    cc.push_back(c4);
    cc.push_back(c3);
    cc.push_back(c1);
    cc.push_back(c4);
    cc.push_back(c2);

    // print all collections
    for_each (cc.begin(), cc.end(),
              printCollection);
    cout << endl;

    // sort collection lexicographically
    sort (cc.begin(), cc.end(),    // range
          lessForCollection);      // sorting criterion

    // print all collections again
    for_each (cc.begin(), cc.end(),
              printCollection);
    return 0;
}

// 1 2 3 4 5 7
// 1 2 3 4 5
// 1 2 3 4 5 2 0
// 1 2 3 4 5 2
// 1 2 3 4 5 2 0
// 1 2 3 4 5 7
// 1 2 3 4 5 2
// 1 2 3 4 5
//
// 1 2 3 4 5
// 1 2 3 4 5
// 1 2 3 4 5 2
// 1 2 3 4 5 2
// 1 2 3 4 5 2 0
// 1 2 3 4 5 2 0
// 1 2 3 4 5 7
// 1 2 3 4 5 7




////////// algo/copy1.cpp    p364

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll1;
    list<int> coll2;

    INSERT_ELEMENTS(coll1,1,9);

    /* copy elements of coll1 into coll2
     * - use back inserter to insert instead of overwrite
     */
    copy (coll1.begin(), coll1.end(),         // source range
          back_inserter(coll2));              // destination range

    /* print elements of coll2
     * - copy elements to cout using an ostream iterator
     */
    copy (coll2.begin(), coll2.end(),         // source range
          ostream_iterator<int>(cout," "));   // destination range
    cout << endl;

    /* copy elements of coll1 into coll2 in reverse order
     * - now overwriting
     */
    copy (coll1.rbegin(), coll1.rend(),       // source range
          coll2.begin());                     // destination range

    // print elements of coll2 again
    copy (coll2.begin(), coll2.end(),         // source range
          ostream_iterator<int>(cout," "));   // destination range
    cout << endl;
    return 0;
}

// 1 2 3 4 5 6 7 8 9
// 9 8 7 6 5 4 3 2 1




////////// algo/copy2.cpp    p365

#include "algostuff.hpp"
using namespace std;

int main()
{
    /* initialize source collection with "..........abcdef.........."
     */
    vector<char> source(10,'.');
    for (int c='a'; c<='f'; c++) {
        source.push_back(c);
    }
    source.insert(source.end(),10,'.');
    PRINT_ELEMENTS(source,"source: ");

    // copy all letters three elements in front of the 'a'
    vector<char> c1(source.begin(),source.end());
    copy (c1.begin()+10, c1.begin()+16,  // source range
          c1.begin()+7);                 // destination range
    PRINT_ELEMENTS(c1,"c1:     ");

    // copy all letters three elements behind the 'f'
    vector<char> c2(source.begin(),source.end());
    copy_backward (c2.begin()+10, c2.begin()+16,  // source range
                   c2.begin()+19);                // destination range
    PRINT_ELEMENTS(c2,"c2:     ");
    return 0;
}

// source: . . . . . . . . . . a b c d e f . . . . . . . . . .
// c1:     . . . . . . . a b c d e f d e f . . . . . . . . . .
// c2:     . . . . . . . . . . a b c a b c d e f . . . . . . .




////////// algo/copy3.cpp    p???

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
    copy (istream_iterator<string>(cin),         // beginning of source
          istream_iterator<string>(),            // end of source
          ostream_iterator<string>(cout,"\n"));  // destination
    return 0;
}

// the quick brown fox
// the
// quick
// brown
// fox
// the lazy dog
// the
// lazy
// dog
// ^Z




////////// algo/transf1.cpp    p367

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll1;
    list<int> coll2;

    INSERT_ELEMENTS(coll1,1,9);
    PRINT_ELEMENTS(coll1,"coll1:   ");

    // negate all elements in coll1
    transform (coll1.begin(), coll1.end(),      // source range
               coll1.begin(),                   // destination range
               negate<int>());                  // operation
    PRINT_ELEMENTS(coll1,"negated: ");

    // transform elements of coll1 into coll2 with ten times their value
    transform (coll1.begin(), coll1.end(),      // source range
               back_inserter(coll2),            // destination range
               bind2nd(multiplies<int>(),10));  // operation
    PRINT_ELEMENTS(coll2,"coll2:   ");

    // print coll2 negatively and in reverse order
    transform (coll2.rbegin(), coll2.rend(),    // source range
               ostream_iterator<int>(cout," "), // destination range
               negate<int>());                  // operation
    cout << endl;
    return 0;
}

// coll1:   1 2 3 4 5 6 7 8 9
// negated: -1 -2 -3 -4 -5 -6 -7 -8 -9
// coll2:   -10 -20 -30 -40 -50 -60 -70 -80 -90
// 90 80 70 60 50 40 30 20 10




////////// algo/transf2.cpp    p369

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll1;
    list<int> coll2;

    INSERT_ELEMENTS(coll1,1,9);
    PRINT_ELEMENTS(coll1,"coll1:   ");

    // square each element
    transform (coll1.begin(), coll1.end(),       // first source range
               coll1.begin(),                    // second source range
               coll1.begin(),                    // destination range
               multiplies<int>());               // operation
    PRINT_ELEMENTS(coll1,"squared: ");

    /* add each element traversed forward with each element traversed backward
     * and insert result into coll2
     */
    transform (coll1.begin(), coll1.end(),       // first source range
               coll1.rbegin(),                   // second source range
               back_inserter(coll2),             // destination range
               plus<int>());                     // operation
    PRINT_ELEMENTS(coll2,"coll2:   ");

    // print differences of two corresponding elements
    cout << "diff:    ";
    transform (coll1.begin(), coll1.end(),       // first source range
               coll2.begin(),                    // second source range
               ostream_iterator<int>(cout, " "), // destination range
               minus<int>());                    // operation
    cout << endl;
    return 0;
}

// coll1:   1 2 3 4 5 6 7 8 9
// squared: 1 4 9 16 25 36 49 64 81
// coll2:   82 68 58 52 50 52 58 68 82
// diff:    -81 -64 -49 -36 -25 -16 -9 -4 -1




////////// algo/swap1.cpp    p370

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll1;
    deque<int> coll2;

    INSERT_ELEMENTS(coll1,1,9);
    INSERT_ELEMENTS(coll2,11,23);

    PRINT_ELEMENTS(coll1,"coll1: ");
    PRINT_ELEMENTS(coll2,"coll2: ");

    // swap elements of coll1 with corresponding elements of coll2
    deque<int>::iterator pos;
    pos = swap_ranges (coll1.begin(), coll1.end(),  // first range
                       coll2.begin());              // second range

    PRINT_ELEMENTS(coll1,"\ncoll1: ");
    PRINT_ELEMENTS(coll2,"coll2: ");
    if (pos != coll2.end()) {
        cout << "first element not modified: "
             << *pos << endl;
    }

    // mirror first three with last three elements in coll2
    swap_ranges (coll2.begin(), coll2.begin()+3,    // first range
                 coll2.rbegin());                   // second range

    PRINT_ELEMENTS(coll2,"\ncoll2: ");
    return 0;
}

// coll1: 1 2 3 4 5 6 7 8 9
// coll2: 11 12 13 14 15 16 17 18 19 20 21 22 23
//
// coll1: 11 12 13 14 15 16 17 18 19
// coll2: 1 2 3 4 5 6 7 8 9 20 21 22 23
// first element not modified: 20
//
// coll2: 23 22 21 4 5 6 7 8 9 20 3 2 1




////////// algo/fill1.cpp    p372

// assign "newValue" to each element in the range
// fill( begin, end, newValue )
// fill( begin, num, newValue )

#pragma warning( disable : 4786 )
#include "algostuff.hpp"
using namespace std;

int main()
{
    // print ten times 7.7
    fill_n(ostream_iterator<float>(cout, " "), // beginning of destination
           10,                                 // count
           7.7);                               // new value
    cout << endl;

    list<string> coll;

    // insert "hello" nine times
    fill_n(back_inserter(coll),       // beginning of destination
           9,                         // count
           "hello");                  // new value
    PRINT_ELEMENTS(coll,"coll: ");

    // overwrite all elements with "again"
    fill(coll.begin(), coll.end(),    // destination
         "again");                    // new value
    PRINT_ELEMENTS(coll,"coll: ");

    // replace all but two elements with "hi"
    fill_n(coll.begin(),              // beginning of destination
           coll.size()-2,             // count
           "hi");                     // new value
    PRINT_ELEMENTS(coll,"coll: ");

    // replace the second and up to the last element but one with "hmmm"
    list<string>::iterator pos1, pos2;
    pos1 = coll.begin();
    pos2 = coll.end();
    fill (++pos1, --pos2,              // destination
          "hmmm");                     // new value
    PRINT_ELEMENTS(coll,"coll: ");
    return 0;
}

// 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7 7.7
// coll: hello hello hello hello hello hello hello hello hello
// coll: again again again again again again again again again
// coll: hi hi hi hi hi hi hi again again
// coll: hi hmmm hmmm hmmm hmmm hmmm hmmm hmmm again




////////// algo/generate.cpp    p374

#include <cstdlib>
#include <ctime>
#include "algostuff.hpp"
using namespace std;

int main()
{
    srand( time(0) );
    list<int> coll;

    // insert five random numbers
    generate_n (back_inserter(coll),      // beginning of destination range
                5,                        // count
                rand);                    // new value generator
    PRINT_ELEMENTS(coll);

    // overwrite with five new random numbers
    generate (coll.begin(), coll.end(),   // destination range
              rand);                      // new value generator
    PRINT_ELEMENTS(coll);
    return 0;
}

// 25911 2560 11497 22350 2540
// 23324 28961 1094 13673 25531




////////// algo/replace1.cpp    p375

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;

    INSERT_ELEMENTS(coll,2,7);
    INSERT_ELEMENTS(coll,4,9);
    PRINT_ELEMENTS(coll,"coll: ");

    // replace all elements with value 6 with 42
    replace (coll.begin(), coll.end(),     // range
             6,                            // old value
             42);                          // new value
    PRINT_ELEMENTS(coll,"coll: ");

    // replace all elements with value less than 5 with 0
    replace_if (coll.begin(), coll.end(),  // range
                bind2nd(less<int>(),5),    // criterion for replacement
                0);                        // new value
    PRINT_ELEMENTS(coll,"coll: ");
    return 0;
}

// coll: 2 3 4 5 6 7 4 5 6 7 8 9
// coll: 2 3 4 5 42 7 4 5 42 7 8 9
// coll: 0 0 0 5 42 7 0 5 42 7 8 9




////////// algo/replace2.cpp    p377

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;

    INSERT_ELEMENTS(coll,2,6);
    INSERT_ELEMENTS(coll,4,9);
    PRINT_ELEMENTS(coll);

    // print all elements with value 5 replaced with 55
    replace_copy(coll.begin(), coll.end(),           // source
                 ostream_iterator<int>(cout," "),    // destination
                 5,                                  // old value
                 55);                                // new value
    cout << endl;

    // print all elements with a value less than 5 replaced with 42
    replace_copy_if(coll.begin(), coll.end(),        // source
                    ostream_iterator<int>(cout," "), // destination
                    bind2nd(less<int>(),5),     // replacement criterion
                    42);                        // new value
    cout << endl;

    // print each element while each odd element is replaced with 0
    replace_copy_if(coll.begin(), coll.end(),        // source
                    ostream_iterator<int>(cout," "), // destination
                    bind2nd(modulus<int>(),2),  // replacement criterion
                    0);                         // new value
    cout << endl;
    return 0;
}

// 2 3 4 5 6 4 5 6 7 8 9
// 2 3 4 55 6 4 55 6 7 8 9
// 42 42 42 5 6 42 5 6 7 8 9
// 2 0 4 0 6 4 0 6 0 8 0




////////// algo/remove1.cpp    p379

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,2,6);
    INSERT_ELEMENTS(coll,4,9);
    INSERT_ELEMENTS(coll,1,7);
    PRINT_ELEMENTS(coll,"coll:               ");

    // remove all elements with value 5
    vector<int>::iterator pos;
    pos = remove(coll.begin(), coll.end(),   // range
                 5);                         // value to remove

    PRINT_ELEMENTS(coll,"size not changed:   ");

    // erase the ``removed'' elements in the container
    coll.erase(pos, coll.end());
    PRINT_ELEMENTS(coll,"size changed:       ");

    // remove all elements less than 4
    coll.erase(remove_if(coll.begin(), coll.end(),  // range
                         bind2nd(less<int>(),4)),   // remove criterion
               coll.end());
    PRINT_ELEMENTS(coll,"<4 removed:         ");
    return 0;
}

// coll:               2 3 4 5 6 4 5 6 7 8 9 1 2 3 4 5 6 7
// size not changed:   2 3 4 6 4 6 7 8 9 1 2 3 4 6 7 5 6 7
// size changed:       2 3 4 6 4 6 7 8 9 1 2 3 4 6 7
// <4 removed:         4 6 4 6 7 8 9 4 6 7




////////// algo/remove2.cpp    p380

#pragma warning( disable : 4786 )
#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll1;

    INSERT_ELEMENTS(coll1,1,6);
    INSERT_ELEMENTS(coll1,1,9);
    PRINT_ELEMENTS(coll1);

    // print elements without those having the value 3
    remove_copy(coll1.begin(), coll1.end(),       // source
                ostream_iterator<int>(cout," "),  // destination
                3);                               // removed value
    cout << endl;

    // print elements without those having a value greater than 4
    remove_copy_if(coll1.begin(), coll1.end(),      // source
                   ostream_iterator<int>(cout," "), // destination
                   bind2nd(greater<int>(),4));      // removed elements
    cout << endl;

    // copy all elements greater than 3 into a multiset
    multiset<int> coll2;
    remove_copy_if(coll1.begin(), coll1.end(),    // source
                   inserter(coll2,coll2.end()),   // destination
                   bind2nd(less<int>(),4));       // elements not copied
    PRINT_ELEMENTS(coll2);
    return 0;
}

// 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9
// 1 2 4 5 6 1 2 4 5 6 7 8 9
// 1 2 3 4 1 2 3 4
// 4 4 5 5 6 6 7 8 9




////////// algo/unique1.cpp    p382

#include "algostuff.hpp"
using namespace std;

int main()
{
    // source data
    int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7,
                      5, 4, 4 };
    int sourceNum = sizeof(source)/sizeof(source[0]);

    list<int> coll;

    // initialize coll with elements from source
    copy (source, source+sourceNum,           // source
          back_inserter(coll));               // destination
    PRINT_ELEMENTS(coll);

    // remove consecutive duplicates
    list<int>::iterator pos;
    pos = unique (coll.begin(), coll.end());

    /* print elements not removed
     * - use new logical end
     */
    copy (coll.begin(), pos,                  // source
          ostream_iterator<int>(cout," "));   // destination
    cout << "\n\n";

    // reinitialize coll with elements from source
    copy (source, source+sourceNum,           // source
          coll.begin());                      // destination
    PRINT_ELEMENTS(coll);

    // remove elements if there was a previous greater element
    coll.erase (unique (coll.begin(), coll.end(),
                        greater<int>()),
                coll.end());
    PRINT_ELEMENTS(coll);
    return 0;
}

// 1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4
// 1 4 6 1 2 3 1 6 5 7 5 4
//
// 1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4
// 1 4 4 6 6 6 6 7




////////// algo/unique2.cpp    p384

#include "algostuff.hpp"
using namespace std;

bool differenceOne (int elem1, int elem2)
{
    return elem1 + 1 == elem2 || elem1 - 1 == elem2;
}

int main()
{
    // source data
    int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7,
                      5, 4, 4 };
    int sourceNum = sizeof(source)/sizeof(source[0]);

    // initialize coll with elements from source
    list<int> coll;
    copy(source, source+sourceNum,      // source
         back_inserter(coll));          // destination
    PRINT_ELEMENTS(coll);

    // print element with consecutive duplicates removed
    unique_copy(coll.begin(), coll.end(),          // source
                ostream_iterator<int>(cout," "));  // destination
    cout << endl;

    // print element without consecutive duplicates that differ by one
    unique_copy(coll.begin(), coll.end(),         // source
                ostream_iterator<int>(cout," "),  // destination
                differenceOne);                   // duplicates criterion
    cout << endl;
    return 0;
}

// 1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4
// 1 4 6 1 2 3 1 6 5 7 5 4
// 1 4 4 6 1 3 1 6 6 6 4 4




////////// algo/unique3.cpp    p385

#include <iostream>
#include <algorithm>
using namespace std;

bool bothSpaces (char elem1, char elem2)
{
    return elem1 == ' ' && elem2 == ' ';
}

int main()
{
    // don't skip leading whitespaces by default
    cin.unsetf(ios::skipws);

    /* copy standard input to standard output
     * - while compressing spaces
     */
    unique_copy(istream_iterator<char>(cin),  // beginning of source: cin
                istream_iterator<char>(),     // end of source: end-of-file
                ostream_iterator<char>(cout), // destination: cout
                bothSpaces);                  // duplicate criterion
    return 0;
}

// 2 spaces  3 spaces   done
// 2 spaces 3 spaces done
// 4    5     6      done
// 4 5 6 done
// ^Z




////////// algo/reverse1.cpp    p387

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll,"coll: ");

    // reverse order of elements
    reverse (coll.begin(), coll.end());
    PRINT_ELEMENTS(coll,"coll: ");

    // reverse order from second to last element but one
    reverse (coll.begin()+1, coll.end()-1);
    PRINT_ELEMENTS(coll,"coll: ");

    // print all of them in reverse order
    reverse_copy (coll.begin(), coll.end(),           // source
                  ostream_iterator<int>(cout," "));   // destination
    cout << endl;
    return 0;
}

// coll: 1 2 3 4 5 6 7 8 9
// coll: 9 8 7 6 5 4 3 2 1
// coll: 9 2 3 4 5 6 7 8 1
// 1 8 7 6 5 4 3 2 9




////////// algo/rotate1.cpp    p388

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll,"coll:      ");

    // rotate one element to the left
    rotate (coll.begin(),      // beginning of range
            coll.begin() + 1,  // new first element
            coll.end());       // end of range
    PRINT_ELEMENTS(coll,"one left:  ");

    // rotate two elements to the right
    rotate (coll.begin(),      // beginning of range
            coll.end() - 2,    // new first element
            coll.end());       // end of range
    PRINT_ELEMENTS(coll,"two right: ");

    // rotate so that element with value 4 is the beginning
    rotate (coll.begin(),                     // beginning of range
            find(coll.begin(),coll.end(),4),  // new first element
            coll.end());                      // end of range
    PRINT_ELEMENTS(coll,"4 first:   ");
    return 0;
}

// coll:      1 2 3 4 5 6 7 8 9
// one left:  2 3 4 5 6 7 8 9 1
// two right: 9 1 2 3 4 5 6 7 8
// 4 first:   4 5 6 7 8 9 1 2 3




////////// algo/rotate2.cpp    p389

#pragma warning( disable : 4786 )
#include "algostuff.hpp"
using namespace std;

int main()
{
    set<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll);

    // print elements rotated one element to the left
    set<int>::iterator pos = coll.begin();
    advance(pos,1);
    rotate_copy(coll.begin(),                     // beginning of source
                pos,                              // new first element
                coll.end(),                       // end of source
                ostream_iterator<int>(cout," ")); // destination
    cout << endl;

    // print elements rotated two elements to the right
    pos = coll.end();
    advance(pos,-2);
    rotate_copy(coll.begin(),                     // beginning of source
                pos,                              // new first element
                coll.end(),                       // end of source
                ostream_iterator<int>(cout," ")); // destination
    cout << endl;

    // print elements rotated so that element with value 4 is the beginning
    rotate_copy(coll.begin(),                     // beginning of source
                coll.find(4),                     // new first element
                coll.end(),                       // end of source
                ostream_iterator<int>(cout," ")); // destination
    cout << endl;
    return 0;
}

// 1 2 3 4 5 6 7 8 9
// 2 3 4 5 6 7 8 9 1
// 8 9 1 2 3 4 5 6 7
// 4 5 6 7 8 9 1 2 3




////////// algo/perm1.cpp    p391

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,3);
    PRINT_ELEMENTS(coll,"on entry:  ");

    /* permute elements until they are sorted
     * - runs through all permutations because the elements are sorted now
     */
    while (next_permutation(coll.begin(),coll.end())) {
        PRINT_ELEMENTS(coll," ");
    }
    PRINT_ELEMENTS(coll,"afterward: ");

    /* permute until descending sorted
     * - this is the next permutation after ascending sorting
     * - so the loop ends immediately
     */
    while (prev_permutation(coll.begin(),coll.end())) {
        PRINT_ELEMENTS(coll," ");
    }
    PRINT_ELEMENTS(coll,"now:       ");

    /* permute elements until they are sorted in descending order
     * - runs through all permutations because the elements are sorted
     *    in descending order now
     */
    while (prev_permutation(coll.begin(),coll.end())) {
        PRINT_ELEMENTS(coll," ");
    }
    PRINT_ELEMENTS(coll,"afterward: ");
    return 0;
}

// on entry:  1 2 3
//  1 3 2
//  2 1 3
//  2 3 1
//  3 1 2
//  3 2 1
// afterward: 1 2 3
// now:       3 2 1
//  3 1 2
//  2 3 1
//  2 1 3
//  1 3 2
//  1 2 3
// afterward: 3 2 1




////////// algo/random1.cpp    p393

#include <cstdlib>
#include "algostuff.hpp"
using namespace std;

class MyRandom {
  public:
    ptrdiff_t operator() (ptrdiff_t max) {
        double tmp;
        tmp = static_cast<double>(rand())
                / static_cast<double>(RAND_MAX);
        return static_cast<ptrdiff_t>(tmp * max);
    }
};

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll,"coll:     ");

    // shuffle all elements randomly
    random_shuffle (coll.begin(), coll.end());

    PRINT_ELEMENTS(coll,"shuffled: ");

    // sort them again
    sort (coll.begin(), coll.end());
    PRINT_ELEMENTS(coll,"sorted:   ");

    /* shuffle elements with self-written random number generator
     * - to pass an lvalue we have to use a temporary object
     */
    MyRandom rd;
    random_shuffle (coll.begin(), coll.end(),    // range
                    rd);                 // random number generator

    PRINT_ELEMENTS(coll,"shuffled: ");
    return 0;
}

// coll:     1 2 3 4 5 6 7 8 9
// shuffled: 5 4 1 3 7 8 9 2 6
// sorted:   1 2 3 4 5 6 7 8 9
// shuffled: 9 3 8 7 2 5 6 1 4




////////// algo/part1.cpp    p395

// partition() and stable_partition() move all elements in the range
// [begin,end) to the front for which the unary predicate op(elem)
// yields true.  stable_partition() preserves the relative order of
// elements that match the criteria and those that do not

#include "algostuff.hpp"
using namespace std;

int main()
{
   vector<int> coll1;
   vector<int> coll2;

   INSERT_ELEMENTS(coll1,1,9);
   INSERT_ELEMENTS(coll2,1,9);
   PRINT_ELEMENTS(coll1,"coll1: ");
   PRINT_ELEMENTS(coll2,"coll2: ");
   cout << endl;

   // move all even elements to the front
   vector<int>::iterator pos1, pos2;
   pos1 = partition(coll1.begin(), coll1.end(),         // range
                    not1(bind2nd(modulus<int>(),2)));   // criterion
   pos2 = stable_partition(coll2.begin(), coll2.end(),       // range
                           not1(bind2nd(modulus<int>(),2))); // crit.

   // print collections and first odd element
   PRINT_ELEMENTS(coll1,"coll1: ");
   cout << "first odd element: " << *pos1 << endl;
   PRINT_ELEMENTS(coll2,"coll2: ");
   cout << "first odd element: " << *pos2 << endl;
   return 0;
}

// coll1: 1 2 3 4 5 6 7 8 9
// coll2: 1 2 3 4 5 6 7 8 9
//
// coll1: 8 2 6 4 5 3 7 1 9
// first odd element: 5
// coll2: 2 4 6 8 1 3 5 7 9
// first odd element: 1




////////// algo/sort1.cpp    p398

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    INSERT_ELEMENTS(coll,1,9);

    PRINT_ELEMENTS(coll,"on entry: ");

    // sort elements
    sort (coll.begin(), coll.end());

    PRINT_ELEMENTS(coll,"sorted:   ");

    // sorted reverse
    sort (coll.begin(), coll.end(),    // range
          greater<int>());             // sorting criterion

    PRINT_ELEMENTS(coll,"sorted >: ");
    return 0;
}

// on entry: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
// sorted:   1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
// sorted >: 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1




////////// algo/sort2.cpp    p399

// stable_sort() guarantees that the order of equal elements remains
// stable

#pragma warning( disable : 4786 )
#include "algostuff.hpp"
using namespace std;

bool lessLength (const string& s1, const string& s2)
{
    return s1.length() < s2.length();
}

int main()
{
    vector<string> coll1;
    vector<string> coll2;

    // fill both collections with the same elements
    coll1.push_back ("1xxx");
    coll1.push_back ("2x");
    coll1.push_back ("3x");
    coll1.push_back ("4x");
    coll1.push_back ("5xx");
    coll1.push_back ("6xxxx");
    coll1.push_back ("7xx");
    coll1.push_back ("8xxx");
    coll1.push_back ("9xx");
    coll1.push_back ("10xxx");
    coll1.push_back ("11");
    coll1.push_back ("12");
    coll1.push_back ("13");
    coll1.push_back ("14xx");
    coll1.push_back ("15");
    coll1.push_back ("16");
    coll1.push_back ("17");
    coll2 = coll1;

    PRINT_ELEMENTS(coll1,"on entry:\n ");

    // sort (according to the length of the strings)
    sort (coll1.begin(), coll1.end(),           // range
          lessLength);                          // criterion
    stable_sort (coll2.begin(), coll2.end(),    // range
                 lessLength);                   // criterion

    PRINT_ELEMENTS(coll1,"\nwith sort():\n ");
    PRINT_ELEMENTS(coll2,"\nwith stable_sort():\n ");
    return 0;
}

// on entry:
//  1xxx 2x 3x 4x 5xx 6xxxx 7xx 8xxx 9xx 10xxx 11 12 13 14xx 15 16 17
//
// with sort():
//  17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx
//
// with stable_sort():
//  2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx 10xxx




////////// algo/psort1.cpp    p401

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> coll;

    INSERT_ELEMENTS(coll,3,7);
    INSERT_ELEMENTS(coll,2,6);
    INSERT_ELEMENTS(coll,1,5);
    PRINT_ELEMENTS(coll);

    // sort until the first five elements are sorted
    partial_sort (coll.begin(),      // beginning of the range
                  coll.begin()+5,    // end of sorted range
                  coll.end());       // end of full range
    PRINT_ELEMENTS(coll);

    // sort inversely until the first five elements are sorted
    partial_sort (coll.begin(),      // beginning of the range
                  coll.begin()+5,    // end of sorted range
                  coll.end(),        // end of full range
                  greater<int>());   // sorting criterion
    PRINT_ELEMENTS(coll);

    // sort all elements
    partial_sort (coll.begin(),      // beginning of the range
                  coll.end(),        // end of sorted range
                  coll.end());       // end of full range
    PRINT_ELEMENTS(coll);
    return 0;
}

// 3 4 5 6 7 2 3 4 5 6 1 2 3 4 5
// 1 2 2 3 3 7 6 5 5 6 4 4 3 4 5
// 7 6 6 5 5 1 2 2 3 3 4 4 3 4 5
// 1 2 2 3 3 3 4 4 4 5 5 5 6 6 7




////////// algo/psort2.cpp    p402

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> coll1;
    vector<int> coll6(6);      // initialize with 6 elements
    vector<int> coll30(30);    // initialize with 30 elements

    INSERT_ELEMENTS(coll1,3,7);
    INSERT_ELEMENTS(coll1,2,6);
    INSERT_ELEMENTS(coll1,1,5);
    PRINT_ELEMENTS(coll1);

    // copy elements of coll1 sorted into coll6
    vector<int>::iterator pos6;
    pos6 = partial_sort_copy (coll1.begin(), coll1.end(),
                              coll6.begin(), coll6.end());

    // print all copied elements
    copy (coll6.begin(), pos6,
          ostream_iterator<int>(cout," "));
    cout << endl;

    // copy elements of coll1 sorted into coll30
    vector<int>::iterator pos30;
    pos30 = partial_sort_copy (coll1.begin(), coll1.end(),
                               coll30.begin(), coll30.end(),
                               greater<int>());

    // print all copied elements
    copy (coll30.begin(), pos30,
          ostream_iterator<int>(cout," "));
    cout << endl;
    return 0;
}

// 3 4 5 6 7 2 3 4 5 6 1 2 3 4 5
// 1 2 2 3 3 3
// 7 6 6 5 5 5 4 4 4 3 3 3 2 2 1




////////// algo/nth1.cpp    p404

// nth_element() - if you need only the set of the n lowest or highest
// elements without having all the elements sorted

#include "algostuff.hpp"
using namespace std;

int main()
{
    deque<int> coll;

    INSERT_ELEMENTS(coll,3,7);
    INSERT_ELEMENTS(coll,2,6);
    INSERT_ELEMENTS(coll,1,5);
    PRINT_ELEMENTS(coll);

    // extract the four lowest elements
    nth_element (coll.begin(),     // beginning of range
                 coll.begin()+3,   // element that should be sorted correctly
                 coll.end());      // end of range

    // print them
    cout << "the four lowest elements are:  ";
    copy (coll.begin(), coll.begin()+4,
          ostream_iterator<int>(cout," "));
    cout << endl;

    // extract the four highest elements
    nth_element (coll.begin(),     // beginning of range
                 coll.end()-4,     // element that should be sorted correctly
                 coll.end());      // end of range

    // print them
    cout << "the four highest elements are: ";
    copy (coll.end()-4, coll.end(),
          ostream_iterator<int>(cout," "));
    cout << endl;

    // extract the four highest elements (second version)
    nth_element (coll.begin(),     // beginning of range
                 coll.begin()+3,   // element that should be sorted correctly
                 coll.end(),       // end of range
                 greater<int>());  // sorting criterion

    // print them
    cout << "the four highest elements are: ";
    copy (coll.begin(), coll.begin()+4,
          ostream_iterator<int>(cout," "));
    cout << endl;
    return 0;
}

// 3 4 5 6 7 2 3 4 5 6 1 2 3 4 5
// the four lowest elements are:  1 2 2 3
// the four highest elements are: 5 6 6 7
// the four highest elements are: 7 6 6 5




////////// algo/heap1.cpp    p407

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,3,7);
    INSERT_ELEMENTS(coll,5,9);
    INSERT_ELEMENTS(coll,1,4);

    PRINT_ELEMENTS (coll, "on entry:           ");

    // convert collection into a heap
    make_heap (coll.begin(), coll.end());

    PRINT_ELEMENTS (coll, "after make_heap():  ");

    // pop next element out of the heap
    pop_heap (coll.begin(), coll.end());
    coll.pop_back();

    PRINT_ELEMENTS (coll, "after pop_heap():   ");

    // push new element into the heap
    coll.push_back (17);
    push_heap (coll.begin(), coll.end());

    PRINT_ELEMENTS (coll, "after push_heap():  ");

    /* convert heap into a sorted collection
     * - NOTE: after the call it is no longer a heap
     */
    sort_heap (coll.begin(), coll.end());

    PRINT_ELEMENTS (coll, "after sort_heap():  ");
    return 0;
}

// on entry:           3 4 5 6 7 5 6 7 8 9 1 2 3 4
// after make_heap():  9 8 6 7 7 5 5 3 6 4 1 2 3 4
// after pop_heap():   8 7 6 7 4 5 5 3 6 4 1 2 3
// after push_heap():  17 7 8 7 4 5 6 3 6 4 1 2 3 5
// after sort_heap():  1 2 3 3 4 4 5 5 6 6 7 7 8 17




////////// algo/bsearch1.cpp    p410

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll);

    // check existence of element with value 5
    if (binary_search(coll.begin(), coll.end(), 5)) {
        cout << "5 is present" << endl;
    }
    else {
        cout << "5 is not present" << endl;
    }

    // check existence of element with value 42
    if (binary_search(coll.begin(), coll.end(), 42)) {
        cout << "42 is present" << endl;
    }
    else {
        cout << "42 is not present" << endl;
    }
    return 0;
}

// 1 2 3 4 5 6 7 8 9
// 5 is present
// 42 is not present




////////// algo/includes.cpp    p412

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;
    vector<int> search;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll,"coll:   ");

    search.push_back(3);
    search.push_back(4);
    search.push_back(7);
    PRINT_ELEMENTS(search,"search: ");

    // check whether all elements in search are also in coll
    if (includes (coll.begin(), coll.end(),
                  search.begin(), search.end())) {
        cout << "all elements of search are also in coll"
             << endl;
    }
    else {
        cout << "not all elements of search are also in coll"
             << endl;
    }
    return 0;
}

// coll:   1 2 3 4 5 6 7 8 9
// search: 3 4 7
// all elements of search are also in coll




////////// algo/bounds1.cpp    p413

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    INSERT_ELEMENTS(coll,1,9);
    coll.sort ();
    PRINT_ELEMENTS(coll);

    // print first and last position 5 could get inserted
    list<int>::iterator pos1, pos2;

    pos1 = lower_bound (coll.begin(), coll.end(),
                        5);
    pos2 = upper_bound (coll.begin(), coll.end(),
                        5);

    cout << "5 could get position "
         << distance(coll.begin(),pos1) + 1
         << " up to "
         << distance(coll.begin(),pos2) + 1
         << " without breaking the sorting" << endl;

    // insert 3 at the first possible position without breaking the sorting
    coll.insert (lower_bound(coll.begin(),coll.end(),
                             3),
                 3);

    // insert 7 at the last possible position without breaking the sorting
    coll.insert (upper_bound(coll.begin(),coll.end(),
                             7),
                 7);

    PRINT_ELEMENTS(coll);
    return 0;
}

// 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
// 5 could get position 9 up to 11 without breaking the sorting
// 1 1 2 2 3 3 3 4 4 5 5 6 6 7 7 7 8 8 9 9




////////// algo/eqrange1.cpp    p415

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    INSERT_ELEMENTS(coll,1,9);
    coll.sort ();
    PRINT_ELEMENTS(coll);

    // print first and last position 5 could get inserted
    pair<list<int>::iterator,list<int>::iterator> range;

    range = equal_range (coll.begin(), coll.end(),
                         5);

    cout << "5 could get position "
         << distance(coll.begin(),range.first) + 1
         << " up to "
         << distance(coll.begin(),range.second) + 1
         << " without breaking the sorting" << endl;
    return 0;
}

// 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
// 5 could get position 9 up to 11 without breaking the sorting




////////// algo/merge1.cpp    p417

#pragma warning( disable : 4786 )
#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll1;
    set<int> coll2;

    // fill both collections with some sorted elements
    INSERT_ELEMENTS(coll1,1,6);
    INSERT_ELEMENTS(coll2,3,8);

    PRINT_ELEMENTS(coll1,"coll1:  ");
    PRINT_ELEMENTS(coll2,"coll2:  ");

    // print merged sequence
    cout << "merged: ";
    merge (coll1.begin(), coll1.end(),
           coll2.begin(), coll2.end(),
           ostream_iterator<int>(cout," "));
    cout << endl;
    return 0;
}

// coll1:  1 2 3 4 5 6
// coll2:  3 4 5 6 7 8
// merged: 1 2 3 3 4 4 5 5 6 6 7 8




////////// algo/setalgos.cpp    p421

#include "algostuff.hpp"
using namespace std;

int main()
{
    int c1[] = { 1, 2, 2, 4, 6, 7, 7, 9 };
    int num1 = sizeof(c1) / sizeof(int);

    int c2[] = { 2, 2, 2, 3, 6, 6, 8, 9 };
    int num2 = sizeof(c2) / sizeof(int);

    // print source ranges
    cout << "c1:                         " ;
    copy (c1, c1+num1,
          ostream_iterator<int>(cout," "));
    cout << endl;
    cout << "c2:                         " ;
    copy (c2, c2+num2,
          ostream_iterator<int>(cout," "));
    cout << '\n' << endl;

    // sum the ranges by using merge()
    cout << "merge():                    ";
    merge (c1, c1+num1,
           c2, c2+num2,
           ostream_iterator<int>(cout," "));
    cout << endl;

    // unite the ranges by using set_union()
    cout << "set_union():                ";
    set_union (c1, c1+num1,
               c2, c2+num2,
               ostream_iterator<int>(cout," "));
    cout << endl;

    // intersect the ranges by using set_intersection()
    cout << "set_intersection():         ";
    set_intersection (c1, c1+num1,
                      c2, c2+num2,
                      ostream_iterator<int>(cout," "));
    cout << endl;

    // determine elements of first range without elements of second range
    // by using set_difference()
    cout << "set_difference():           ";
    set_difference (c1, c1+num1,
                    c2, c2+num2,
                    ostream_iterator<int>(cout," "));
    cout << endl;

    // determine difference the ranges with set_symmetric_difference()
    cout << "set_symmetric_difference(): ";
    set_symmetric_difference (c1, c1+num1,
                              c2, c2+num2,
                              ostream_iterator<int>(cout," "));
    cout << endl;
    return 0;
}

// c1:                         1 2 2 4 6 7 7 9
// c2:                         2 2 2 3 6 6 8 9
//
// merge():                    1 2 2 2 2 2 3 4 6 6 6 7 7 8 9 9
// set_union():                1 2 2 2 3 4 6 6 7 7 8 9
// set_intersection():         2 2 6 9
// set_difference():           1 4 7 7
// set_symmetric_difference(): 1 2 3 4 6 7 7 8




////////// algo/imerge1.cpp    p424

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;

    // insert two sorted sequences
    INSERT_ELEMENTS(coll,1,7);
    INSERT_ELEMENTS(coll,1,8);
    PRINT_ELEMENTS(coll);

    // find beginning of second part (element after 7)
    list<int>::iterator pos;
    pos = find (coll.begin(), coll.end(),    // range
                7);                          // value
    ++pos;

    // merge into one sorted range
    inplace_merge (coll.begin(), pos, coll.end());

    PRINT_ELEMENTS(coll);
    return 0;
}

// 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8
// 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8




////////// algo/accu1.cpp    p426

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll);

    // process sum of elements
    cout << "sum: "
         << accumulate (coll.begin(), coll.end(),    // range
                        0)                           // initial value
         << endl;

    // process sum of elements less 100
    cout << "sum: "
         << accumulate (coll.begin(), coll.end(),    // range
                        -100)                        // initial value
         << endl;

    // process product of elements
    cout << "product: "
         << accumulate (coll.begin(), coll.end(),    // range
                        1,                           // initial value
                        multiplies<int>())           // operation
         << endl;

    // process product of elements (use 0 as initial value)
    cout << "product: "
         << accumulate (coll.begin(), coll.end(),    // range
                        0,                           // initial value
                        multiplies<int>())           // operation
         << endl;
    return 0;
}

// 1 2 3 4 5 6 7 8 9
// sum: 45
// sum: -55
// product: 362880
// product: 0




////////// algo/inner1.cpp    p428

#include "algostuff.hpp"
using namespace std;

int main()
{
    list<int> coll;

    INSERT_ELEMENTS(coll,1,6);
    PRINT_ELEMENTS(coll);

    /* process sum of all products
     * (0 + 1*1 + 2*2 + 3*3 + 4*4 + 5*5 + 6*6)
     */
    cout << "inner product: "
         << inner_product (coll.begin(), coll.end(),  // first range
                           coll.begin(),              // second range
                           0)                         // initial value
         << endl;

    /* process sum of 1*6 ... 6*1
     * (0 + 1*6 + 2*5 + 3*4 + 4*3 + 5*2 + 6*1)
     */
    cout << "inner reverse product: "
         << inner_product (coll.begin(), coll.end(),  // first range
                           coll.rbegin(),             // second range
                           0)                         // initial value
         << endl;

    /* process product of all sums
     * (1 * 1+1 * 2+2 * 3+3 * 4+4 * 5+5 * 6+6)
     */
    cout << "product of sums: "
         << inner_product (coll.begin(), coll.end(),  // first range
                           coll.begin(),              // second range
                           1,                         // initial value
                           multiplies<int>(),       // inner operation
                           plus<int>())             // outer operation
         << endl;
    return 0;
}

// 1 2 3 4 5 6
// inner product: 91
// inner reverse product: 56
// product of sums: 46080




////////// algo/partsum1.cpp    p430

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    INSERT_ELEMENTS(coll,1,6);
    PRINT_ELEMENTS(coll);

    // print all partial sums
    partial_sum (coll.begin(), coll.end(),          // source range
                 ostream_iterator<int>(cout," "));  // destination
    cout << endl;

    // print all partial products
    partial_sum (coll.begin(), coll.end(),          // source range
                 ostream_iterator<int>(cout," "),   // destination
                 multiplies<int>());                // operation
    cout << endl;
    return 0;
}

// 1 2 3 4 5 6
// 1 3 6 10 15 21
// 1 2 6 24 120 720




////////// algo/adjdiff1.cpp    p431

#include "algostuff.hpp"
using namespace std;

int main()
{
   deque<int> coll;

   INSERT_ELEMENTS(coll,1,6);
   PRINT_ELEMENTS(coll);

   // print all differences between elements
   adjacent_difference (coll.begin(), coll.end(),         // source
                        ostream_iterator<int>(cout," ")); // dest.
   cout << endl;

   // print all sums with the predecessors
   adjacent_difference (coll.begin(), coll.end(),         // source
                        ostream_iterator<int>(cout," "),  // dest.
                        plus<int>());                     // operation
   cout << endl;

   // print all products between elements
   adjacent_difference (coll.begin(), coll.end(),         // source
                        ostream_iterator<int>(cout," "),  // dest.
                        multiplies<int>());               // operation
   cout << endl;
   return 0;
}

// 1 2 3 4 5 6
// 1 1 1 1 1 1
// 1 3 5 7 9 11
// 1 2 6 12 20 30




////////// algo/relabs.cpp    p432

#include "algostuff.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    coll.push_back(17);
    coll.push_back(-3);
    coll.push_back(22);
    coll.push_back(13);
    coll.push_back(13);
    coll.push_back(-9);
    PRINT_ELEMENTS(coll,"coll:     ");

    // convert into relative values
    adjacent_difference (coll.begin(), coll.end(),   // source
                         coll.begin());              // destination
    PRINT_ELEMENTS(coll,"relative: ");
     
    // convert into absolute values
    partial_sum (coll.begin(), coll.end(),           // source
                 coll.begin());                      // destination
    PRINT_ELEMENTS(coll,"absolute: ");
    return 0;
}

// coll:     17 -3 22 13 13 -9
// relative: 17 -20 25 -9 0 -22
// absolute: 17 -3 22 13 13 -9

#endif