/* 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

////////// iter/itercat.cpp    p256

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

int main()
{
   vector<int> coll;

   // insert elements from -3 to 9
   for (int i=-3; i<=9; ++i) {
       coll.push_back (i);
   }

   /* print number of elements by processing the distance between beginning and end
    * - NOTE: uses operator - for iterators
    */
   cout << "number/distance: " << coll.end()-coll.begin() << endl;

   /* print all elements
    * - NOTE: uses operator < instead of operator !=
    */
   vector<int>::iterator pos;
   for (pos=coll.begin(); pos<coll.end(); ++pos) {
       cout << *pos << ' ';
   }
   cout << endl;

   /* print all elements
    * - NOTE: uses operator [] instead of operator *
    */
   for (i=0; i<coll.size(); ++i) {
       cout << coll.begin()[i] << ' ';
   }
   cout << endl;

   /* print every second element
    * - NOTE: uses operator +=
    */
   for (pos = coll.begin(); pos < coll.end()-1; pos += 2) {
       cout << *pos << ' ';
   }
   cout << endl;
   return 0;
}

// number/distance: 13
// -3 -2 -1 0 1 2 3 4 5 6 7 8 9
// -3 -2 -1 0 1 2 3 4 5 6 7 8 9
// -3 -1 1 3 5 7




////////// iter/advance1.cpp    p260

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

int main()
{
    list<int> coll;

    // insert elements from 1 to 9
    for (int i=1; i<=9; ++i) {
        coll.push_back(i);
    }

    list<int>::iterator pos = coll.begin();

    // print actual element
    cout << *pos << endl;

    // step three elements forward
    advance (pos, 3);

    // print actual element
    cout << *pos << endl;

    // step one element backward
    advance (pos, -1);

    // print actual element
    cout << *pos << endl;
    return 0;
}

// 1
// 4
// 3




////////// iter/distance.cpp    p261

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

int main()
{
    list<int> coll;

    // insert elements from -3 to 9
    for (int i=-3; i<=9; ++i) {
        coll.push_back(i);
    }

    // search element with value 5
    list<int>::iterator pos;
    pos = find (coll.begin(), coll.end(),    // range
                5);                          // value

    if (pos != coll.end()) {
        // process and print difference from the beginning
        cout << "difference between beginning and 5: "
             << distance(coll.begin(),pos) << endl;
    }
    else {
        cout << "5 not found" << endl;
    }
    return 0;
}

// difference between beginning and 5: 8




////////// iter/swap1.cpp    p263

#include <iostream>
#include <list>
#include <algorithm>
/********* #include "print.hpp" *********/
#include <iostream>

/* 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;
}
/********* #include "print.hpp" *********/
using namespace std;

int main()
{
    list<int> coll;

    // insert elements from 1 to 9
    for (int i=1; i<=9; ++i) {
        coll.push_back(i);
    }

    PRINT_ELEMENTS(coll);

    // swap first and second value
    iter_swap (coll.begin(), ++coll.begin());

    PRINT_ELEMENTS(coll);

    // swap first and last value
    iter_swap (coll.begin(), --coll.end());

    PRINT_ELEMENTS(coll);
    return 0;
}

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




////////// iter/reviter1.cpp    p264

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

void print (int elem)
{
    cout << elem << ' ';
}

int main()
{
    list<int> coll;

    // insert elements from 1 to 9
    for (int i=1; i<=9; ++i) {
        coll.push_back(i);
    }

    // print all elements in normal order
    for_each (coll.begin(), coll.end(),      // range
              print);                        // operation
    cout << endl;

    // print all elements in reverse order
    for_each (coll.rbegin(), coll.rend(),    // range
              print);                        // operations
    cout << endl;
    return 0;
}

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




////////// iter/reviter2.cpp    p266

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

int main()
{
    vector<int> coll;

    // insert elements from 1 to 9
    for (int i=1; i<=9; ++i) {
        coll.push_back(i);
    }

    // find position of element with value 5
    vector<int>::iterator pos;
    pos = find (coll.begin(), coll.end(),
                5);

    // print value to which iterator pos refers
    cout << "pos:  " << *pos << endl;

    // convert iterator to reverse iterator rpos
    vector<int>::reverse_iterator rpos(pos);

    // print value to which reverse iterator rpos refers
    cout << "rpos: " << *rpos << endl;
    return 0;
}

// pos:  5
// rpos: 4




////////// iter/reviter3.cpp    p268

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

void print (int elem)
{
    cout << elem << ' ';
}

int main()
{
    deque<int> coll;

    // insert elements from 1 to 9
    for (int i=1; i<=9; ++i) {
        coll.push_back(i);
    }

    // find position of element with value 2
    deque<int>::iterator pos1;
    pos1 = find (coll.begin(), coll.end(),    // range
                 2);                          // value

    // find position of element with value 7
    deque<int>::iterator pos2;
    pos2 = find (coll.begin(), coll.end(),    // range
                 7);                          // value

    // print all elements in range [pos1,pos2)
    for_each (pos1, pos2,     // range
              print);         // operation
    cout << endl;

    // convert iterators to reverse iterators
    deque<int>::reverse_iterator rpos1(pos1);
    deque<int>::reverse_iterator rpos2(pos2);

    // print all elements in range [pos1,pos2) in reverse order
    for_each (rpos2, rpos1,   // range
              print);         // operation
    cout << endl;
    return 0;
}

// 2 3 4 5 6
// 6 5 4 3 2




////////// iter/reviter4.cpp    p269

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

int main()
{
    list<int> coll;

    // insert elements from 1 to 9
    for (int i=1; i<=9; ++i) {
        coll.push_back(i);
    }

    // find position of element with value 5
    list<int>::iterator pos;
    pos = find (coll.begin(), coll.end(),    // range
                5);                          // value

    // print value of the element
    cout << "pos:   " << *pos << endl;

    // convert iterator to reverse iterator
    list<int>::reverse_iterator rpos(pos);

    // print value of the element to which the reverse iterator refers
    cout << "rpos:  " << *rpos << endl;

    // convert reverse iterator back to normal iterator
    list<int>::iterator rrpos;
    rrpos = rpos.base();

    // print value of the element to which the normal iterator refers
    cout << "rrpos: " << *rrpos << endl;
    return 0;
}

// pos:   5
// rpos:  4
// rrpos: 5




////////// iter/backins.cpp    p273

#include <iostream>
#include <vector>
#include <algorithm>
#include "print.hpp"
using namespace std;

int main()
{
    vector<int> coll;

    // create back inserter for coll
    // - inconvenient way
    back_insert_iterator<vector<int> > iter(coll);

    // insert elements with the usual iterator interface
    *iter = 1;
    iter++;
    *iter = 2;
    iter++;
    *iter = 3;

    PRINT_ELEMENTS(coll);

    // create back inserter and insert elements
    // - convenient way
    back_inserter(coll) = 44;
    back_inserter(coll) = 55;

    PRINT_ELEMENTS(coll);

    // use back inserter to append all elements again
    // - reserve enough memory to avoid reallocation
    coll.reserve(2*coll.size());
    copy (coll.begin(), coll.end(),    // source
          back_inserter(coll));        // destination

    PRINT_ELEMENTS(coll);
    return 0;
}

// 1 2 3
// 1 2 3 44 55
// 1 2 3 44 55 1 2 3 44 55




////////// iter/frontins.cpp    p274

#include <iostream>
#include <list>
#include <algorithm>
#include "print.hpp"
using namespace std;

int main()
{
    list<int> coll;

    // create front inserter for coll
    // - inconvenient way
    front_insert_iterator<list<int> > iter(coll);

    // insert elements with the usual iterator interface
    *iter = 1;
    iter++;
    *iter = 2;
    iter++;
    *iter = 3;

    PRINT_ELEMENTS(coll);

    // create front inserter and insert elements
    // - convenient way
    front_inserter(coll) = 44;
    front_inserter(coll) = 55;

    PRINT_ELEMENTS(coll);

    // use front inserter to insert all elements again
    copy (coll.begin(), coll.end(),    // source
          front_inserter(coll));       // destination

    PRINT_ELEMENTS(coll);
    return 0;
}

// 3 2 1
// 55 44 3 2 1
// 1 2 3 44 55 55 44 3 2 1




////////// iter/inserter.cpp    p276

#pragma warning( disable : 4786 )
#include <iostream>
#include <set>
#include <list>
#include <algorithm>
#include "print.hpp"
using namespace std;

int main()
{
    set<int> coll;

    // create insert iterator for coll
    // - inconvenient way
    insert_iterator<set<int> > iter(coll,coll.begin());

    // insert elements with the usual iterator interface
    *iter = 1;
    iter++;
    *iter = 2;
    iter++;
    *iter = 3;

    PRINT_ELEMENTS(coll,"set:  ");

    // create inserter and insert elements
    // - convenient way
    inserter(coll,coll.end()) = 44;
    inserter(coll,coll.end()) = 55;

    PRINT_ELEMENTS(coll,"set:  ");

    // use inserter to insert all elements into a list
    list<int> coll2;
    copy (coll.begin(), coll.end(),           // source
          inserter(coll2,coll2.begin()));     // destination

    PRINT_ELEMENTS(coll2,"list: ");

    // use inserter to reinsert all elements into the list before the second element
    copy (coll.begin(), coll.end(),           // source
          inserter(coll2,++coll2.begin()));   // destination

    PRINT_ELEMENTS(coll2,"list: ");
    return 0;
}

// set:  1 2 3
// set:  1 2 3 44 55
// list: 1 2 3 44 55
// list: 1 1 2 3 44 55 2 3 44 55




////////// iter/ostriter.cpp    p279

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

int main()
{
    // create ostream iterator for stream cout
    // - values are separated by a newline character
    ostream_iterator<int> intWriter(cout,"\n");

    // write elements with the usual iterator interface
    *intWriter = 42;
    intWriter++;
    *intWriter = 77;
    intWriter++;
    *intWriter = -5;

    // create collection with elements from 1 to 9
    vector<int> coll;
    for (int i=1; i<=9; ++i) {
        coll.push_back(i);
    }

    // write all elements without any delimiter
    copy (coll.begin(), coll.end(),
          ostream_iterator<int>(cout));
    cout << endl;

    // write all elements with " < " as delimiter
    copy (coll.begin(), coll.end(),
          ostream_iterator<int>(cout," < "));
    cout << endl;
    return 0;
}

// 42
// 77
// -5
// 123456789
// 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 <




////////// iter/istriter.cpp    p281

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

int main()
{
    // create istream iterator that reads integers from cin
    istream_iterator<int> intReader(cin);

    // create end-of-stream iterator
    istream_iterator<int> intReaderEOF;

    /* while able to read tokens with istream iterator
     * - write them twice
     */
    while (intReader != intReaderEOF) {
        cout << "once:       " << *intReader << endl;
        cout << "once again: " << *intReader << endl;
        ++intReader;
    }
    return 0;
}

// 123 234
// once:       123
// once again: 123
// once:       234
// once again: 234
// 345
// once:       345
// once again: 345
// ^Z<Enter>
// <Enter>




////////// iter/advance2.cpp    p282

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

int main()
{
    istream_iterator<string> cinPos(cin);
    ostream_iterator<string> coutPos(cout," ");

    /* while input is not at the end of the file
     * - write every third string
     */
    while (cinPos != istream_iterator<string>()) {
        // ignore the following two strings
        advance (cinPos, 2);

        // read and write the third string
        if (cinPos != istream_iterator<string>()) {
            *coutPos++ = *cinPos++;
        }
    }
    cout << endl;
    return 0;
}

// 1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 3 6 9 12 ^Z
// 




////////// iter/assoiter.cpp    p290

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
#include "print.hpp"
/********* #include "assoiter.hpp" *********/
#include <iterator>

/* template class for insert iterator for associative containers
 */
template <class Container>
class asso_insert_iterator
 : public std::iterator <std::output_iterator_tag,
                         void, void>
{
  protected:
    Container& container;    // container in which elements are inserted

  public:
    // constructor
    explicit asso_insert_iterator (Container& c) : container(c) {
    }

    // assignment operator
    // - inserts a value into the container
    asso_insert_iterator<Container>&
    operator= (const typename Container::value_type& value) { 
        container.insert(value);
        return *this;
    }

    // dereferencing is a no-op that returns the iterator itself
    asso_insert_iterator<Container>& operator* () {
        return *this;
    }

    // increment operation is a no-op that returns the iterator itself
    asso_insert_iterator<Container>& operator++ () {
        return *this;
    }
    asso_insert_iterator<Container>& operator++ (int) {
        return *this;
    }
};

/* convenience function to create the inserter
 */
template <class Container>
inline asso_insert_iterator<Container> asso_inserter (Container& c)
{
    return asso_insert_iterator<Container>(c);
}
/********* #include "assoiter.hpp" *********/

int main()
{
    set<int> coll;   

    // create inserter for coll
    // - inconvenient way
    asso_insert_iterator<set<int> > iter(coll);

    // insert elements with the usual iterator interface
    *iter = 1;
    iter++;
    *iter = 2;
    iter++;
    *iter = 3;

    PRINT_ELEMENTS(coll);

    // create inserter for coll and insert elements
    // - convenient way
    asso_inserter(coll) = 44;
    asso_inserter(coll) = 55;

    PRINT_ELEMENTS(coll);

    // use inserter with an algorithm
    int vals[] = { 33, 67, -4, 13, 5, 2 };
    copy (vals, vals+(sizeof(vals)/sizeof(vals[0])),  // source
          asso_inserter(coll));                       // destination

    PRINT_ELEMENTS(coll);
    return 0;
}

// 1 2 3
// 1 2 3 44 55
// -4 1 2 3 5 13 33 44 55 67

#endif