//
// STL.cpp
// Sample code to explain some advanced STL concepts. This is a shameless
// copy of online materials in order to create a simple example program to
// explain the basics of STL.
//
// Topics covered:
// ostream_iterator, copy, deque, insert_iterator, front_inserter,
// back_inserter, accumulate, count, count_if, find, find_if, generate,
// generate_n, fill, fill_n, transform, negate, mismatch, search, equal,
// for_each, swap, sort, merge, binary_search, includes, ptr_fun, set_union,
// set_intersection, set_difference.
//
// Prerequisite:
// Basic STL concepts: vectors, maps, sets, iterators, algorithms
//
// Author:
// Priyank Bolia (priyank.co.in)
//
// License:
// Priyank Bolia does not hold any copyrights for this work
// and the rights still remains with the original authors, who had done all
// the hard work.
//
// References:
// sgi.com/tech/stl/swap.html, msdn.microsoft.com
//

#define _SECURE_SCL 0  // Disable visual Studio 2005 warnings

#include <iterator>
#include <deque>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>

using namespace std;

// Creation of a user-defined function object
// that inherits from the unary_function base class
class greaterthan : unary_function<int, bool>
{
  int num;

public:
  greaterthan(int n) : num(n) {}

  result_type operator()(argument_type i)
  {
    return (result_type)(i > num);
  }
};

// return the next Fibonacci number in the Fibonacci series.
int Fibonacci(void)
{
  static int r;
  static int f1 = 0;
  static int f2 = 1;
  r = f1 + f2 ;
  f1 = f2 ;
  f2 = r ;
  return f1 ;
}

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

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main ()
{
  int arr[4] = { 3,4,7,8 };  // Initialize a deque using an array.

  // A deque is very much like a vector: like vector, it is a sequence that
  // supports random access to elements, const time insertion and
  // removal of elements at the end of the sequence, and linear time
  // insertion and removal of elements in the middle. The main way in which
  // deque differs from vector is that deque also supports constant
  // time insertion and removal of elements at the beginning of the sequence.
  // Additionally, deque does not have any member functions analogous to
  // vector's capacity() and reserve(), and does not provide any of the
  // guarantees on iterator validity that are associated with those member
  // functions.
  deque<int> d(arr+0, arr+4);

  cout << "Start with a deque: ";  // Output the original deque.

  // An ostream_iterator is an Output Iterator that performs formatted
  // output of objects of type T to a particular ostream. Note that all
  // of the restrictions of an Output Iterator must be obeyed, including
  // the restrictions on the ordering of operator* and operator++
  // operations.
  copy(d.begin(), d.end(), ostream_iterator<int>(cout," "));
  // OUTPUT: Start with a deque: 3 4 7 8

  // Insert into the middle.
  // Insert_iterator is an iterator adaptor that functions as an Output
  // Iterator: assignment through an insert_iterator inserts an object
  // into a Container. Specifically, if ii is an insert_iterator, then
  // ii keeps track of a Container c and an insertion point p; the
  // expression *ii = x performs the insertion c.insert(p, x).
  insert_iterator<deque<int> > ins(d, d.begin()+2);
  *ins = 5; *ins = 6;

  // Output the new deque.
  cout << endl << endl;
  cout << "Use an insert_iterator: ";

  // Copies elements from range [first, last) to the range
  // [result, result + (last - first)).  That is, it performs the
  // assignments *result = *first, *(result + 1) = *(first + 1), and so on.
  // Generally, for every integer n from 0 to last - first, copy performs
  // the assignment *(result + n) = *(first + n). Assignments are
  // performed in forward order, i.e. in order of increasing n.
  // The return value is result + (last - first)
  copy(d.begin(), d.end(), ostream_iterator<int>(cout," "));
  // OUTPUT: Use an insert_iterator: 3 4 5 6 7 8

  // A deque of four 1s.
  deque<int> d2(4, 1);

  // Insert d2 at front of d.
  // Front_insert_iterator is an iterator adaptor that functions as an
  // Output Iterator: assignment through a front_insert_iterator inserts
  // an object before the first element of a Front Insertion Sequence.
  copy(d2.begin(), d2.end(), front_inserter(d));

  // Output the new deque.
  cout << endl << endl;
  cout << "Use a front_inserter: ";
  copy(d.begin(), d.end(), ostream_iterator<int>(cout," "));
  // OUTPUT: Use a front_inserter: 1 1 1 1 3 4 5 6 7 8

  // Insert d2 at back of d.
  // Back_insert_iterator is an iterator adaptor that functions as an
  // Output Iterator: assignment through a back_insert_iterator inserts
  // an object after the last element of a Back Insertion Sequence.
  copy(d2.begin(), d2.end(), back_inserter(d));

  // Output the new deque.
  cout << endl << endl;
  cout << "Use a back_inserter: ";
  copy(d.begin(), d.end(), ostream_iterator<int>(cout," "));
  cout << endl << endl;
  // OUTPUT: Use a back_inserter: 1 1 1 1 3 4 5 6 7 8 1 1 1 1

  // Accumulate example
  int A[] = {1, 2, 3, 4, 5};
  const int N = sizeof(A) / sizeof(int);
  deque<int> a(A+0, A+N);

  // Adding the numbers
  // Accumulate is a generalization of summation: it computes the sum
  // (or some other binary operation) of init and all of the elements in
  // the range [first, last).
  cout << "The sum of ";
  copy(a.begin(), a.end()-1, ostream_iterator<int>(cout, " + "));
  cout << *(a.end()-1) << " is "
    << accumulate(a.begin(), a.end(), 0)
    << endl << endl;
  // OUTPUT: The sum of 1 + 2 + 3 + 4 + 5 is 15

  // Multiplying the numbers
  // Multiplies<T> is a function object. Specifically, it is an Adaptable
  // Binary Function. If f is an object of class multiplies<T> and x and y
  // are objects of class T, then f(x,y) returns x*y. Similarly, there is:
  // plus<T> (+), minus<T> (-), divides<T> (/), modulus<T> (%).
  cout << "The product of ";
  copy(a.begin(), a.end()-1, ostream_iterator<int>(cout, " + "));
  cout << *(a.end()-1) << " is "
    << accumulate(a.begin(), a.end(), 1, multiplies<int>())
    << endl << endl;
  // OUTPUT: The product of 1 * 2 * 3 * 4 * 5 is 120

  // Count finds the number of elements in [first, last) that are
  // equal to value.
  cout << "Number of ones: "
    << (int)count(A, A + N, 1)
    << endl << endl;
  // OUTPUT: Number of ones: 1

  // Count_if finds the number of elements in [first, last) that satisfy
  // the predicate pred.
  cout << "Number of elements greater than 3: "
    << (int)count_if(A, A + N, greaterthan(3))
    << endl << endl;
  // OUTPUT: Number of elements greater than 3: 2

  // find returns the first iterator i in the range [first, last) such
  // that *i == value.
  // Returns last if no such iterator exists.
  deque<int>::iterator find_result = find(a.begin(), a.end(), 2);
  cout << "Find whether 2 is present in A: " << *(find_result)
    << endl << endl;
  // OUTPUT: Find whether 2 is present in A: 2

  // find_if returns the first iterator i in the range [first, last)
  // such that pred(*i) is true.
  // Returns last if no such iterator exists.
  deque<int>::iterator find_if_result = find_if(a.begin(), a.end(),
    bind2nd(greater<int>(), 3));
  // Binder2nd is a function object adaptor: it is used to transform an
  // adaptable binary function into an adaptable unary function.
  // Specifically, if f is an object of class
  // binder2nd<AdaptableBinaryFunction>, then f(x) returns F(x, c),
  // where F is an object of class AdaptableBinaryFunction and where
  // c is a const. Both F and c are passed as arguments to
  // binder2nd's constructor.

  cout << "Find number greater than 3 in A: " << *(find_if_result)
    << " " << *(find_if_result++) << endl << endl;
  // OUTPUT: Find number greater than 3 in A: 5 4

  cout << "Fibonacci series: ";
  // The generate_n algorithm traverses the range [First, First + n),
  // assigning to each element the value returned by Gen.
  // The return value is first + n.
  generate_n(ostream_iterator<int>(cout, " "), 10, Fibonacci);
  cout << endl << endl;
  // OUTPUT: Fibonacci series: 1 1 2 3 5 8 13 21 34 55

  const int NUM = 10;
  vector<int> V1(NUM);
  vector<int> V2(NUM);

  // Generate assigns the result of invoking gen, a function object that
  // takes no arguments, to each element in the range [first, last).
  generate(V1.begin(), V1.end(), rand);

  // Fill assigns the value to every element in the range
  // [first, last). That is, for every iterator i in [first, last),
  // it performs the assignment *i = value.
  fill(V2.begin(), V2.end(), 0);

  // Fill_n assigns the value to every element in the range
  // [first, first+n). That is, for every iterator i in [first, first+n),
  // it performs the assignment *i = value.
  // The return value is first + n.
  fill_n(back_inserter(V2), 5, 42);

  // Transform performs an operation on objects.
  // It performs the operation op(*i1, *i2) for each iterator i1 in the
  // range [first1, last1) and assigns the result to *o, where i2 is the
  // corresponding iterator in the second input range and where o is the
  // corresponding output iterator. That is, for each n such that
  // 0 <= n < last1 - first1, it performs the assignment
  // *(result + n) = op(*(first1 + n), *(first2 + n). The return value is
  // result + (last1 - first1).
  transform(V1.begin(), V1.end(), V2.begin(), negate<int>());
  // If f is an object of class negate<T> and x is an object of class T,
  // then f(x) returns -x.

  cout << "Result of negate on randomly generated values: ";
  copy(V2.begin(), V2.end(), ostream_iterator<int>(cout, " "));
  cout << "\nThe last 42 were filled with fill_n function."
     << endl << endl;
  // OUTPUT: Result of negate on randomly generated values: -41 -18467
  // -6334 -26500 -19169 -1 5724 -11478 -29358 -26962 -24464 42 42 42 42 42
  // The last 42 were filled with fill_n function.

  // mismatch
  int A1[] = { 3, 1, 4, 1, 5, 9, 3 };
  int A2[] = { 3, 1, 4, 2, 8, 5, 7 };
  const int NMIS = sizeof(A1) / sizeof(int);

  // Mismatch finds the first position where the two ranges [first1, last1)
  // and [first2, first2 + (last1 - first1)) differ.
  pair<int*, int*> result = mismatch(A1, A1 + NMIS, A2);
  // Pair<T1,T2> is a heterogeneous pair: it holds one object of type T1
  // and one of type T2. A pair is much like a Container, in that it "owns"
  // its elements. It is not actually a model of Container, though, because
  // it does not support the sDarkorangedard methods (such as iterators)
  // for accessing the elements of a Container.
  cout << "The first mismatch is in position " << (int)(result.first - A1)
    << endl;
  cout << "Values are: " << *(result.first) << ", " << *(result.second)
    << endl << endl;
  // OUTPUT: The first mismatch is in position 3
  // Values are: 1, 2

  // search
  const char S1[] = "Hello, world!";
  const char S2[] = "world";
  const int N1 = sizeof(S1) - 1;
  const int N2 = sizeof(S2) - 1;

  // Search finds a subsequence within the range [first1, last1) that is
  // identical to [first2, last2) when compared element-by-element. It
  // returns an iterator pointing to the beginning of that subsequence,
  // or else last1 if no such subsequence exists
  const char* p = search(S1, S1 + N1, S2, S2 + N2);
  cout << "Found subsequence \"" << S2 << "\" at character " << (int)(p - S1)
    << " of sequence \"" << S1 << "\"." << endl << endl;
  // OUTPUT: Found subsequence "world" at character 7 of sequence
  // "Hello, world!".

  // equal
  int AE1[] = { 3, 1, 4, 1, 5, 9, 3 };
  int AE2[] = { 3, 1, 4, 2, 8, 5, 7 };
  const int NEQU = sizeof(AE1) / sizeof(int);

  // Equal returns true if the two ranges [first1, last1) and
  // [first2, first2 + (last1 - first1)) are identical when compared
  // element-by-element, and otherwise returns false.
  cout << "Result of comparison: " << equal(AE1, AE1 + NEQU, AE2)
    << endl << endl;
  // OUTPUT: Result of comparison: 0

  // for_each
  int AFOREACH[] = {1, 4, 2, 8, 5, 7};
  const int NFOREACH = sizeof(A) / sizeof(int);

  // For_each applies the function object f to each element in the range
  // [first, last); f's return value, if any, is ignored. Applications are
  // performed in forward order,  i.e. from first to last. For_each returns
  // the function object after it has been applied to each element.
  print<int> P = for_each(AFOREACH, AFOREACH + NFOREACH, print<int>(cout));
  cout << endl << P.count << " objects printed." << endl << endl;
  // OUTPUT: 1 4 2 8 5
  // 5 objects printed.

  cout << "Swapping contents of vector V2 to V1: ";
  // Swap Assigns the contents of a to b and the contents of b to a. This
  // is used as a primitive operation by many other algorithms.
  swap(V1, V2);
  copy(V1.begin(), V1.end(), ostream_iterator<int>(cout, " "));
  cout << endl << endl;
  // OUTPUT: Swapping contents of vector V2 to V1: -41 -18467 -6334 -26500
  // -19169 -15724 -1147 8 -29358 -26962 -24464 42 42 42 42 42

  // Sort sorts the elements in [first, last) into ascending order,
  // meaning that if i and j are any two valid iterators in [first, last)
  // such that i precedes j, then *j is not less than *i. Note: sort is
  // not guaranteed to be stable. That is, suppose that *i and *j are
  // equivalent: neither one is less than the other. It is not guaranteed
  // that the relative order of these two elements will be preserved by sort.
  cout << "Sorted array 1: ";
  sort(AE1, AE1 + NEQU);
  copy(AE1, AE1 + NEQU, ostream_iterator<int>(cout, " "));
  cout << endl << endl;
  // OUTPUT: Sorted array 1: 1 1 3 3 4 5 9
  cout << "Sorted array 2: ";
  sort(AE2, AE2 + NEQU);
  copy(AE2, AE2 + NEQU, ostream_iterator<int>(cout, " "));
  cout << endl << endl;
  // OUTPUT: Sorted array 2: 1 2 3 4 5 7 8

  // Merge combines two sorted ranges [first1, last1) and [first2, last2)
  // into a single sorted range. That is, it copies elements from
  // [first1, last1) and [first2, last2) into
  // [result, result + (last1 - first1) + (last2 - first2)) such that the
  // resulting range is in ascending order. Merge is stable, meaning both
  // that the relative order f elements within each input range is
  // preserved, and that for equivalent elements in both input ranges the
  // element from the first range precedes the element from the second.
  // The return value is result + (last1 - first1) + (last2 - first2).
  cout << "Merged sorted array: ";
  merge(AE1, AE1 + NEQU, AE2, AE2 + NEQU,
    ostream_iterator<int>(cout, " "));
  cout << endl << endl;
  // OUTPUT: Merged sorted array: 1 1 1 2 3 3 3 4 4 5 5 7 8 9

  // Binary_search is a version of binary search: it attempts to find the
  // element value in an ordered range [first, last) It returns true if
  // an element that is equivalent to value is present in [first, last)
  // and false if no such element exists.
  cout << "Searching for 7 in AE1: "
    << (binary_search(AE1, AE1 + NEQU, 7) ? "present" : "not present")
    << endl << endl;
  // OUTPUT: Searching for 7 in AE1: not present

  int AI1[] = { 1, 2, 3, 4, 5, 6, 7 };
  int AI2[] = { 1, 4, 7 };

  const int NI1 = sizeof(AI1) / sizeof(int);
  const int NI2 = sizeof(AI2) / sizeof(int);

  // Includes tests whether one sorted range includes another sorted
  // range. That is, it returns true if and only if, for every element
  // in [first2, last2), an equivalent element is also present
  // in [first1, last1). Both [first1, last1) and [first2, last2)
  // must be sorted in ascending order.
  cout << "AI2 contained in AI1: "
    << (includes(AI1, AI1 + NI1, AI2, AI2 + NI2) ? "true" : "false")
    << endl << endl;
  // OUTPUT: AI2 contained in AI1: true

  // Ptr_fun takes a function pointer as its argument and returns a
  // function pointer adaptor, a type of function object. It is actually
  // two different functions, not one (that is, the name ptr_fun is
  // overloaded). If its argument is of type Result (*)(Arg) then ptr_fun
  // creates a pointer_to_unary_function, and if its argument is of type
  // Result (*)(Arg1, Arg2) then ptr_fun creates a
  // pointer_to_binary_function.
  vector <char*> vec1;
  vector <char*>::iterator Iter1, RIter;

  vec1.push_back ( "Open" );
  vec1.push_back ( "up" );
  vec1.push_back ( "the" );
  vec1.push_back ( "pearly" );
  vec1.push_back ( "gates" );

  cout << "Original sequence contains: " ;
  for ( Iter1 = vec1.begin( ) ; Iter1 != vec1.end( ) ; Iter1++ )
    cout << *Iter1 << " ";
  cout << endl;
  // OUTPUT: Original sequence contains: Open up the pearly gates

  // To search the sequence for "pearly"
  // use a pointer_to_function conversion
  // find_if returns the first iterator i in the range [first, last)
  // such that pred(*i) is true.
  // Returns last if no such iterator exists.
  RIter = find_if( vec1.begin( ), vec1.end( ),
    not1 ( bind2nd (ptr_fun ( strcmp ), "pearly" ) ) );

  if ( RIter != vec1.end( ) )  
  {
    cout << "The search for 'pearly' was successful.\n";
    cout << "The next character string is: "
      << *++RIter << "." << endl << endl;
  }
  // OUTPUT: The search for 'pearly' was successful.
  // The next character string is: gates.

  // Set_union constructs a sorted range that is the union of the sorted
  // ranges [first1, last1) and [first2, last2). The return value is the
  // end of the output range.
  int AS1[] = {1, 3, 5, 7, 9, 11};
  int AS2[] = {1, 1, 2, 3, 5, 8, 13};  

  const int SN1 = sizeof(AS1) / sizeof(int);
  const int SN2 = sizeof(AS2) / sizeof(int);

  cout << "Union of AS1 and AS2: ";
  set_union(AS1, AS1 + SN1, AS2, AS2 + SN2,
    ostream_iterator<int>(cout, " "));
  cout << endl << endl;
  // OUTPUT: Union of AS1 and AS2: 1 1 2 3 5 7 8 9 11 13

  // Set_intersection constructs a sorted range that is the intersection
  // of the sorted ranges [first1, last1) and [first2, last2). The return
  // value is the end of the output range.
  char AS3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'h', 'H'};
  char AS4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
  const int SN3 = sizeof(AS3);
  const int SN4 = sizeof(AS4);

  cout << "Intersection of AS3 and AS4: ";
  set_intersection(AS3, AS3 + SN3, AS4, AS4 + SN4,
    ostream_iterator<char>(cout, " "), lt_nocase);
  cout << endl << endl;
  // OUTPUT: Intersection of AS3 and AS4: a b b f h

  // Set_difference constructs a sorted range that is the set difference
  // of the sorted ranges [first1, last1) and [first2, last2). The return
  // value is the end of the output range.
  cout << "Difference of AS3 and AS4: ";
  set_difference(AS3, AS3 + SN3, AS4, AS4 + SN4,
    ostream_iterator<char>(cout, " "), lt_nocase);
  cout << endl << endl;
  // OUTPUT: Difference of AS3 and AS4: B B H

  return 0;
}