// C++ tip of the week #9
// Topic: STL iterators, part 1
// Relevance: algorithms
//            collections of data
//            data/stream sequences
//

#if defined( _MSC_VER ) && !defined( HAVE_NEW_IOSTREAMS )
#define HAVE_NEW_IOSTREAMS
#endif

#if __GNUC__ >= 3
#define HAVE_NEW_IOSTREAMS
#endif

#include <algorithm>
#include <list>
#include <map>            // STL associative container std::map<>
#include <vector>
#include <string>

#ifdef HAVE_NEW_IOSTREAMS
#include <iostream>
#else
#include <iostream.h>
#define std
#endif

#include <assert.h>

int GimeInt() {
   static int i = 0;
   return ++i;
}

const int nContainerSize = 5;
static const char* aszNumbers[] =
   { "zero", "one", "two", "three", "four", "five", "six", "seven" };
const int nNumbers = sizeof( aszNumbers ) / sizeof( const char* );

// This program exercises the requirements on bidirectional and random
// access iterators. Random access iterators have al properties of
// bidirectional iterators. (1)

int main() {
// std::list<> uses bidirectional iterators
   typedef std::list< int > MyList_t;
   MyList_t myList( nContainerSize );
   std::generate( myList.begin(), myList.end(), &GimeInt );

// create a bidirectional iterator specifically for std::list< int >
   MyList_t::iterator myListIterator = myList.end(); // (2)

// bidirectional iterators allow for looping forward:
   for ( myListIterator = myList.begin(); // initialization
         myListIterator != myList.end();  // ending condition
         ++myListIterator )               /* loop (3) */ {

   // iterators can be dereferenced
      std::cout << "Current list entry: " << *myListIterator;

   // iterators can be compared
      if ( myList.begin() != myListIterator ) {

      // bidirectional iterators allow for looping backward:
         MyList_t::const_iterator myPrevious = myListIterator; // (4)
         std::cout << ", previous list entry: " << *--myPrevious;
      }

      std::cout << '\n';
   }

// exercise (one of) the bidirectional iterator(s) of std::map<>
   typedef std::map< std::string, int > MyMap_t;
   MyMap_t myMap; // empty, nContainerSize defaults makes no sense

// copy the myList entries into myMap, use a reverse iterator for looping (5)
   typedef MyList_t::reverse_iterator LRI_t;
   for ( LRI_t idx = myList.rbegin(); idx != myList.rend(); ++idx ) { // (6)
      std::cout << "List entry: " << *idx << '\n';
      assert( *idx < nNumbers );
      myMap[ aszNumbers[ *idx ] ] = *idx; // std::map<> entries are sorted
   }

// std::map<> iterators are bidirectional, like with std::list<>, there are
// const and reverse flavors available; when dereferencing map iterators, a
// std::pair<> is returned
   typedef MyMap_t::const_iterator MCI_t;
   for ( MCI_t pairIdx = myMap.begin(); pairIdx != myMap.end(); ++pairIdx ) {
   // note in the print out that the std::map<> entries have been sorted
      std::cout << "The string: \"" << pairIdx->first
                << "\" corresponds to the int: " << pairIdx->second << '\n';
   }

// std::vector<> supports random access iterators
   typedef std::vector< int > MyVector_t;
   MyVector_t myVector( nContainerSize );

// fill myVector with the values of myList reversed
   std::copy( myList.rbegin(), myList.rend(), myVector.begin() );

// positions of elements can be calculated
   MyVector_t::iterator myVectorIterator = myVector.begin();
   std::cout << "First element:  " << *myVectorIterator << '\n';
   std::cout << "Second element: " << *( myVectorIterator + 1 ) << '\n';

// <container>::difference_type is typedeffed to Distance of the used iterator
   MyVector_t::difference_type distanceToLastElement =
                          myVector.end() - myVector.begin() - 1;
   myVectorIterator += distanceToLastElement;
   std::cout << "Last element:   " << *myVectorIterator << '\n';

// random access iterators have an order
   if ( myVectorIterator < myVector.end() ) { // (7)
      std::cout << "OK!\n";
   }
   else { // oops, very wrong...
      std::cout << "NOT OK!!\n";
   }

   return 0;
}

// (1) And bidirectional iterators have all properties of forward iterators.
// However, std::forward_iterator<>s are not so interesting as all standard
// containers support at least std::bidirectional_iterator<>s.
//
// (2) Iterators to which no value is assigned, are "singular". They are
// just as bad as dangling pointers, thus one should always directly assign
// a value to an iterator. "One past the end" is a good default.
//
// (3) In loops, or in general if the return value of the increment operator
// is not used, prefer prefix increment as this prevents the creation of
// a temporary.
//
// (4) A const_iterator points to a constant element. The iterator itself
// is not const, thus it can be modified.
//
// (5) If needed, a reverse iterator can be converted to an iterator that
// points to the same element, by calling the member function base().
// 
// (6) Always initialize a reverse iterator through assignment, never through
// copy construction as a reverse iterator can be copy constructed from an
// iterator (eg. if you forget the 'r' in front of begin()), but not
// initialized by assignment to an iterator.
//
// (7) Never use singular iterators in comparisons. The results are undefined.
// Here, "myVectorIterator" is non-singular as a result of its previous use.