#include <iostream>
#include <algorithm>            // most of the algorithms are in the algorithms header
#include <numeric>              // this header contains some of the numeric algorithms
#include <vector>
#include <string>
#include <list>
#include <deque>
#include <iterator>             // this header contains the stream iterators
#include <fstream>

using std::cout;
using std::endl;
using std::cin;
using std::vector;
using std::string;
using std::list;
using std::deque;
using std::istream_iterator;
using std::ostream_iterator;
using std::ifstream;
using std::ofstream;

bool isShorter(const string &s1, const string &s2) {
  return s1.size() < s2.size();
}

bool isBig(const string &s1) {
  return s1.size() >= 5;
}

/*
  Instead of defining several algorithms for each container the library provides a set of algorithms that are 
  independent to any particular container. These algorithms are called generics and operate on different kinds 
  of containers and on elements of various types. The generic algorithms never execute container operations such
  as adding or removing elements. Algorithms utilize iterators to traverse the container but they never change
  the size of the container itself. However, they may change the value of the elements stored in the container
  or change the order of the elements. 
*/

int main() {
  /* 
    Most algorithms operate over a range of elements, which is sometimes referred to as the input range.
    The first two parameters of algorithms that operate over an input range are the iterators that define the input range.
    The first parameter defines the first element belonging to the input range and the second parameter defines the 
    the element that is one-past the last element belonging to the input range. 
  */
  
  // read only algorithms
  vector<int> nums = {23, 28, 12, 4, 89, 45, 37};
  int val = 12;
  auto result = find(nums.cbegin(), nums.cend(), val);                  // the find algorithm searches the input range for the value given as the third argument and returns an iterator to its location if it exists, otherwise it returns the one-past the end iterator
  cout << "The value " << val << (result == nums.cend() ? " does not exist " : " does exist") << " in the nums list." << endl;
  
  int sum = accumulate(nums.cbegin(), nums.cend(), 0);                  // the accumulate algorithm is from the numeric header, it adds together all elements in the input range with the initial value of the summation given by the third argument (in this case 0)
  cout << "The sum of all values in nums is " << sum << endl;
  
  /*
    the equal algorithm compares two sequences to determine whether the elements are matching
    the first two parameters defines the range of the first sequence
    the third parameter defines the start of the second sequence 
    any algorithm that compares two sequences assumes the second sequence is just as long or longer than the first
  */ 
  vector<string> animals1 = {"Chicken", "Elephant", "Camel", "Zebra"};
  vector<string> animals2 = {"Chicken", "Elephant", "Camel", "Zebra"};
  vector<string> animals3 = {"Chicken", "Elephant", "Camel", "Giraffe"};
  bool isEqual = equal(animals1.cbegin(), animals1.cend(), animals2.cbegin());
  cout << "animals1 is equalt to animals2: " << (isEqual ? "True" : "False") << endl;
  isEqual = equal(animals1.cbegin(), animals1.cend(), animals3.cbegin());
  cout << "animals1 is equalt to animals3: " << (isEqual ? "True" : "False") << endl;
  
  // algorithms that write container elements
  fill(nums.begin(), nums.begin() + nums.size()/2, 0);                  // the fill algorithm assigns the value given as the third argument to every element of the container belonging to the input range specified by the first two arguments
  cout << "nums after using fill algorithm: ";
  for (int i = 0; i < nums.size(); ++i) cout << nums[i] << " ";
  cout << endl;
  
  vector<int> vals(7, 0);
  auto valsIter = copy(nums.begin(), nums.end(), vals.begin());                         // the copy algorithm copies the elements from the input range specified by the first two arguments to the destination sequence specified by the third argument
  // similar to the equal algorithm, the copy algorithm assumes the destination sequence is just as long, if not longer, than the source sequence 
  // copy returns an iterator to the element in the destination sequence just after all the elements that were copied from the source sequence
  cout << "vals after using the copy algorithm: ";
  for (int i = 0; i < vals.size(); ++i) cout << vals[i] << " ";
  cout << endl;
  
  replace(nums.begin(), nums.end(), 0, -1);                             // the replace algorithm finds all elements in the input range that match the third argument and replaces them with the value given as the fourth argument
  cout << "nums after using the replace algorithm: ";
  for (int i = 0; i < nums.size(); ++i) cout << nums[i] << " ";
  cout << endl;
  
  // algorithms that reorder container elements
  vector<string> story = {"the", "quick", "red", "fox", "jumps", "over", "the", "slow", "red", "turtle"};
  cout << "story before sort: ";
  for (int i = 0; i < story.size(); ++i) cout << story[i] << " ";
  cout << endl;
  // sort the words in the story so the duplicate words will be together
  sort(story.begin(), story.end());                                     // the sort algorithm orders the sequence of strings alphabetically
  cout << "story after sort: ";
  for (int i = 0; i < story.size(); ++i) cout << story[i] << " ";
  cout << endl;
  auto uniqueIter = unique(story.begin(), story.end());                 // the unique algorithm reorders the sequence such that unique elements are at the front of the sequence, it returns an iterator one-past the unique elements
  story.erase(uniqueIter, story.end());                                 // erase all duplicates using the iterator returned by the unique algorithm
  cout << "story after unique and erase: ";
  for (int i = 0; i < story.size(); ++i) cout << story[i] << " ";
  cout << endl;
  
  /*
    many algorithms require operators such as < or ==, they will use the operator corresponding to the type of the elements in the sequence
    sometimes it is beneficial to define the operation that the algorithm uses because some elements may not have operators such as > or ==
    we can use predicates to define operations that the algorithms will use to perform comparisons
    predicates are expressions that can be called and return a value that can be used as a condition (usually we have to define a function to use as a predicate)
    library algorithms use either unary predicates (requires one parameter) or binary predicates (requires two parameters)
    algorithms that can use predicates will call the predicates on the elements of the sequence within the input range
    therefore, the types of the sequence elements must be compatible with the types of the parameters used in the predicate
  */
  sort(story.begin(), story.end(), isShorter);                          // using the isShorter function as a predicate to the sort algorithm will sort the strings in the sequence by length instead of alphabetically
  cout << "story after sorting by word length: ";
  for (int i = 0; i < story.size(); ++i) cout << story[i] << " ";
  cout << endl;
  
  // print the strings in the story sequence that have 5 or more letters
  auto partitionIter = partition(story.begin(), story.end(), isBig);   // the partition algorithm reorders the sequence by placing the elements for which the predicate is true at the beginning of the sequence and placing the elements for which the predicate is false after
  // the partition algorithm returns an iterator to the element one-after the last element that the predicate evaluated as true
  story.erase(partitionIter, story.end());
  cout << "story after using partition: ";
  for (int i = 0; i < story.size(); ++i) cout << story[i] << " ";
  cout << endl;
  
  // we would like to print all the strings in the sequence that are longer than some arbitrary value
  vector<string> newStory = {"how", "much", "wood", "would", "a", "woodchuck", "chuck", "if", "a", "woodchuck", "could", "chuck", "wood"};
  sort(newStory.begin(), newStory.end());
  auto newUniqueIter = unique(newStory.begin(), newStory.end());
  newStory.erase(newUniqueIter, newStory.end());
  stable_sort(newStory.begin(), newStory.end(), isShorter);                 // the stable_sort algorithm is similar to sort but it will maintain the alphabetically ordered sequence for strings that have the same length
  cout << "new story after sorting and removing duplicates: ";
  for (int i = 0; i < newStory.size(); ++i) cout << newStory[i] << " ";
  cout << endl;
  /*
    we can use the find_if algorithm to find the first string in the sequence that has a certain length
    however, find_if only accepts unary predicates which means we cannot find strings that are an arbitrary length because any function we pass to find_if can only have one parameter 
  */
  /*
    an algorithm will accept any kind of callable object including: function, function pointer, classes that overload the function call operator and lambda expression
    an object is callable if we can apply the call operator () to it 
    a lambda expression represents a callable piece of code, it can be thought of as an unamed, inline function
    like any function, a lambda expression has a return type, parameter list and a function body
    unlike functions, a lambda expression can be placed inside the scope of a function
    a lambda expression has the form [capture list] (parameter list) -> return type {function body}
    >> the capture list is a list of local variables defined in the enclosing function, it is usually left empty
    >> the parameter list and return type can be omitted, however the capture list and function body must be present 
    a lambda can use local variables from the surrounding function only if it specifies which variables it intends to use in the capture list
  */
  auto f = [] {return 42;};                                                 // define a lambda expression that takes no arguments and returns 42
  cout << "calling f: " << f() << endl;                                     // a lambda expression can be called, just like any other fuction 
  /*
    we want to pass a callable function to the find_if algorithm that will compare the length of each string in the sequence to a local variable
    therefore, we need to write a lambda expression that accepts a string argument and compares the length of the string to a local variable specified in the capture list
    the find_if algorithm returns an iterator to the first element in the sequence such that the predicate returns true
  */
  vector<string>::size_type targetLen = 4;
  auto findIter = find_if(newStory.begin(), newStory.end(), [targetLen] (const string &s1) {return s1.size() >= targetLen;});
  /*
    we would also like to print all the strings in the sequence that are a certain length specified by the targetLen variable
    this can be accomplished by using the for_each algorithm
    the for_each algorithm takes a callable object (in this case a lamda expression) and calls that object on every element of the input range
  */
  for_each(findIter, newStory.end(), [] (const string &s) {cout << s << " ";});
  cout << endl;
  
  /*
    the library defines several types of iterators on top of the iterators defined for each type of container: insert iterators, stream iterators, reverse iterators, move iterators
    insert iterators:
      >> iterators that are bound to a container and can be used to insert elements into the container
      >> an iterator adaptor that takes a container and yields an iterator that can add elements to the container
      >> there are three main functions which can return an insert iterator: inserter, front_inserter and back_inserter
      >> front_inserter will insert the element at the front of the container sequence using the push_front function of the container (only available for containers that support push_front)
      >> back_inserter will insert the element at the back of the container sequence using the push_back function of the container (only available for containers that support push_back)
      >> inserter requires two arguments including the container and an iterator pointing to where the new element should be inserted, uses the insert function of the given container and the element is inserted infront of the location provided by the given iterator
  */
  
  // copying a container using a container iterator for the destination
  deque<int> dest1 = {12, 13, 14, 15, 16, 17};
  deque<int> copyVals = {-5, -6, -7};
  copy(copyVals.begin(), copyVals.end(), dest1.begin());
  for (int i = 0; i < dest1.size(); ++i) cout << dest1[i] << ", ";
  cout << endl;
  
  // copying a container using a front_inserter iterator for the destination
  deque<int> dest2 = {12, 13, 14, 15, 16, 17};
  auto frontIter = front_inserter(dest2);
  copy(copyVals.begin(), copyVals.end(), frontIter);
  for (int i = 0; i < dest2.size(); ++i) cout << dest2[i] << ", ";
  cout << endl;
  
  // copying a container using a back_inserter iterator for the destination
  deque<int> dest3 = {12, 13, 14, 15, 16, 17};
  auto backIter = back_inserter(dest3);
  copy(copyVals.begin(), copyVals.end(), backIter);
  for (int i = 0; i < dest3.size(); ++i) cout << dest3[i] << ", ";
  cout << endl;
  
  // copying a container using an inserter iterator for the destination
  deque<int> dest4 = {12, 13, 14, 15, 16, 17};
  auto midIter = inserter(dest4, dest4.begin() + 3);
  copy(copyVals.begin(), copyVals.end(), midIter);
  for (int i = 0; i < dest4.size(); ++i) cout << dest4[i] << ", ";
  cout << endl;
  
  /*
    stream iterators:
      >> iterators that can be used with objects of IO type
      >> these iterators treat their corresponding stream as a sequence of elements of a specified type
      >> there are two functions that return stream iterators: istream_iterator and ostream_iterator
  */
  /*
    istream_iterator:
      >> when creating a stream iterator the type of objects it will read or write must be specified
      >> creating the stream iterator requires binding it to a stream, otherwise it is default initialized and is equivalent to an off-the-end iterator
      >> an iterator bound to a stream is equal to an off-the-end iterator if the associated stream hits the EOF or if it encounters an IO error
  */
  
  vector<int> vec;
  istream_iterator<int> cinIter(cin);             // cinIter is an iterator that reads int's from the input stream cin
  istream_iterator<int> eof;                      // default initialization of the iterator will create an off-the-end iterator, it can be used to determine the end of file when reading from a stream
  while (cinIter != eof) {                        // checks if there is valid input to read and the input is of type int
    vec.push_back(*cinIter++);                    // increment the iterator to get the next input from the stream and dereference the previous input and store in the vector
  }
  for (int i = 0; i < vec.size(); ++i) {
    cout << vec[i] << ", ";
  }
  cout << endl;
  
  // using stream iterators with algorithms (uncomment the code)
  // istream_iterator<int> cinIter2(cin), eof2;
  // cout << accumulate(cinIter2, eof2, 0) << endl;
  
  /*
    ostream_iterator:
      >> when creating an ostream_iterator we must bind it to a specific stream
      >> it is not possible to default initialize ostream_iterator's unlike the istream_iterator's that are default initialized as off-the-end iterators if not bound to a stream
      >> can provide an optional second argument that specifies a character string to print after every element read from the stream
      >> the dereference (*) and increment (++) operators have no effect on ostream_iterator's
  */
  ostream_iterator<int> coutIter(cout, " ");
  // assigning a value to the ostream_iterator will write to the output stream associated with the iterator 
  // the dereference and increment operators have no impact on the code, they are included in order to be consistent with other stream iterators
  for (auto e: vec) *coutIter++ = e;     
  //for (auto e: vec) coutIter = e;                 // this code is equivalent to the line above
  cout << endl;
  
  
  /*
    reverse iterators:
    >> are iterators that traverse a container from the last element to the first element
    >> incrementing (++) a reverse iterator goes to the previous element in the container while decrementing (--) a reverse iterator goes to the next element
    >> all containers, beside forward_list, support the reverse iterator
    >> you can obtain a reverse iterator by calling the functions rbegin(), rend(), rcbegin() or rcend()
    >> remember that in this case rbegin() will return an iterator pointing to the last element in the container while the iterator from rend() will point to 1 position before the first element in the container
  */
  vector<int> listof_nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  cout << "listof_nums print out using reverse iterators: " << endl;
  for (auto rIter = listof_nums.rbegin(); rIter < listof_nums.rend(); ++rIter) {
    cout << *rIter << ", ";
  }
  cout << endl;
  
  /*
    structure of generic algorithms:
    >> generic algorithms require certain operations to be performed on iterators, for example accessing a container element through an iterator, incrementing the iterator, comparing two iterators etc. 
    >> the iterator operations required by the algorithms are grouped into 5 iterator categories
      >> input iterator: read, no write, single-pass, increment only 
      >> output iterator: write, no read, single-pass, increment only 
      >> forward iterator: read and write, multi-pass, increment only
      >> bidirectional iterator:  read and write, multi-pass, increment and decrement
      >> random-access iterator:  read and write, multi-pass, full iterator arithmetic
  */
  
  /*
    create a small program that can read a text file containing the names, grades and sections of students in CSV format and generate the following data:
    >> How many students are in each section?
    >> What is the highest grade in each section? and who has it?
    >> What is the lowest grade in each section? and who has it?
    >> What is the average grade in each section?
  */
  ifstream readStrm("input.txt");
  string line;
  vector<string> names;
  vector<int> grades;
  vector<char> sections;
  int linesRead = 0;
  while (readStrm >> line) {
    if (linesRead % 3 == 0) {                   // read the name of the student
      line.erase(line.end() - 1);
      names.push_back(line);
    }
    else if (linesRead % 3 == 1) {              // read the grade they acheived
      grades.push_back(stoi(line));             // converts a string to an integer value, string must start with an integer and stoi will stop reading when it gets to the first non-integer character in the string 
    }
    else if (linesRead % 3 == 2) {              // read the student's section 
      sections.push_back(*(line.begin()));
    }
    ++linesRead;
  }
  auto highest_grade = max_element(grades.begin(), grades.end());
  auto lowest_grade = min_element(grades.begin(), grades.end());
  float average_grade = accumulate(grades.begin(), grades.end(), 0.0) / grades.size();
  
  cout << endl;
  cout << "Student data: " << endl;
  cout << "the highest grade is: " << *highest_grade << endl;
  cout << "the lowest grade is: " << *lowest_grade << endl;
  cout << "the average grade is: " << average_grade << endl;
  
  return 0;
}