// test_algorithm1.cc   not exhaustive, just some functions

#include <iostream>
#include <vector>       // need a data structure to demonstrate
#include <algorithm>    // defines functions, not data structure
using namespace std;

static int pos_nums() { static int i=1; return i++; }  // 1, 2, 3, ...

void put(int i) { cout << ' ' << i; }    // put int with a leading space


int main()
{
  vector<int> a(10);     // 'a' is a data object in memory
  bool result;
  vector<int>::iterator v_ptr;

  cout << "test_algorithms.cpp running on size";
  put(a.size());
  cout << endl;
  
  
  generate(a.begin(), a.end(), pos_nums);     // pos_mums generates values

  cout << "generate     ";
  for_each(a.begin(), a.end(), put);          // print values
  cout << endl;

  random_shuffle(a.begin(), a.end());         // shuffle

  cout << "randomized   ";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  v_ptr = max_element(a.begin(), a.end());    // find maximum element
  cout << "max = " << *v_ptr << endl;

                                              // value of minimum element
  cout << "min = " << *min_element(a.begin(), a.end()) << endl;
  sort(a.begin(), a.end());                   // sort

  cout << "sorted       ";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  reverse(a.begin(), a.end());                // reverse order

  cout << "reversed    ";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  stable_sort(a.begin(), a.end());            // another sort

  cout << "stable_sort  ";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  result = binary_search(a.begin(), a.end(), 5);

  cout << (result?"found ":"did not find ") << 5 << endl;

  next_permutation(a.begin(), a.end());       // permute vector
  cout << "permutation  ";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  next_permutation(a.begin(), a.end());       // another permute

  cout << "permutation n";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  prev_permutation(a.begin(), a.end());       // previous permute

  cout << "previous perm";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  v_ptr = find(a.begin(), a.end(), 7);        // find iterator value for 7
  cout << "found iterator to 7 is = " << v_ptr << endl;

  rotate(a.begin(), v_ptr, a.end());          // rotate about value 7

  cout << "rotate, 7 1st";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  // add a few values to the vector           // add 15 and 20 to vector
  a.push_back(15);
  a.push_back(20);

  cout << "more values  ";
  for_each(a.begin(), a.end(), put);
  cout << endl;

  v_ptr = upper_bound(a.begin(), a.end(), 11); // find upper bound of 11
  cout << "upper bound of 11 is = " << *v_ptr << " at " << v_ptr << endl;

  v_ptr = lower_bound(a.begin(), a.end(), 17); // find lower bound of 17
  cout << "lower bound of 17 is = " << *v_ptr << " at " <<v_ptr << endl;

  return 0;
}

// result of execution:
// test_algorithms.cpp running on size 10
// generate      1 2 3 4 5 6 7 8 9 10
// randomized    2 6 9 5 4 3 1 7 8 10
// max = 10
// min = 1
// sorted        1 2 3 4 5 6 7 8 9 10
// reversed     10 9 8 7 6 5 4 3 2 1
// stable_sort   1 2 3 4 5 6 7 8 9 10
// found 5
// permutation   1 2 3 4 5 6 7 8 10 9
// permutation n 1 2 3 4 5 6 7 9 8 10
// previous perm 1 2 3 4 5 6 7 8 10 9
// found iterator to 7 is = 0x10047020
// rotate, 7 1st 7 8 10 9 1 2 3 4 5 6
// more values   7 8 10 9 1 2 3 4 5 6 15 20
// upper bound of 11 is = 15 at 0x10047350
// lower bound of 17 is = 20 at 0x10047354