#include <iostream>
#include <vector>
#include <algorithm>	// find, reverse, count, max_element
#include <numeric>	// accumulate, 

using namespace std;
void printIntVector1(vector<int> v);
	
// ARRAYS AND VECTORS
int main()
{
	// STACK (automatic variables, static allocation)
	// Fixed length	
	
	int v1[10];
	
	// STACK (automatic variables, static allocation)
	// Variable Length Array, C99, inherited by some C++ compilers	
	
	int n;
	
	n = 10;
	
	// or
	// cin >> n;
	
	int v2[n];
				
	// HEAP (dynamic allocation)
	
	int k = 10;
	int *v3 = new int[k];
	int *v3a = new int [4] {1, 2, 4, 5};  // C++0x, the vector size is compulsory
	   // use the arrays vith v3[3], *v3, *(v3+2)...
	delete[] v3a;
	delete[] v3;
	
	// Various notes
		
	cout << sizeof(v2)/sizeof(int) << endl;  // to calculate the length of an array (statically allocated)
	
	int vv1[] = {1, 2, 3, 6, 5, 4, 1};  // Initialization
	int vv2[10] = {1, 2, 3, 6, 5, 4, 1};  // Partial initialization
	
	
	for (int j(0); j < n; j++)   // <-- direct initialization of j, C++
		v1[j] = j;
	for (int j = 0; j < n; j++)  // <-- copy initialization 
		cout << *(v1+j) << endl;

	cout << endl;

	// Use vectors from Standard Template Library!
	
	// Standard Template Library (STL).  Iterators, Containers and Algorithms.
	
	// STL It is a library of template-based container classes, 
	// including vectors, lists, queues, and stacks. 
	// The STL also includes a number of common algorithms, including sorting and searching.
	// The goal of the STL is to give you an alternative to reinventing the wheel for these 
	// common requirements. 
	// Containers
	// A container is an object that holds other objects. 
	// The standard C++ library provides a series of container classes that are powerful 
	// tools that help C++ developers handle common programming tasks. Two types of 
	// Standard Template Library (STL) container classes are sequence and associative. 
	// Sequence containers are designed to provide sequential and random access to their elements
	// The Standard Template Library sequence containers provide efficient sequential 
	// access to a list of objects. The standard C++ library provides 
	// three sequence containers: vector, list, and deque (”dek”, double ended queue, nbgdn).
	// (Sams, Teach Yourself C++ For Linux in 21 days)

	// STL is not object-oriented. To achieve its versatility, the STL relies
	// more heavily on templates than on encapsulation, inheritance, and virtual functions
	// (polymorphism) - OOP's three main anchors - and you won't find any 
	// significant class hierarchies in the STL.
	// (Tom Swans GNU_C++ for Linux)
		
	vector<int> array_int;                  //array of type int, empty
	vector<double> array_double;        //array of type double, empty (size is 0)
	vector<double> array_double_2(10);  //array of 10 elements of type double, initialized with 0.0
	vector<double> array_double_2a(10, 2.5);  // array of 10 elements of type double, initialized with 2.5

	vector<int> v {1, 2, 3, 4, 5, 6};
	vector<int> vv = {1, 2, 3, 4, 5, 6};  // used later in this code!
	
	cout << "v was defined as { 1, 2, 3 , 4, 5, 6}" << endl;	
	cout << "v.size() is " << v.size() << endl;          // "dot" operator, Object Oriented syntax 
	cout << "v.capacity() is " << v.capacity() << endl;  // allocated storage in terms of elements
// https://www.tutorialspoint.com/cpp_standard_library/cpp_vector_capacity.htm
	
	v.push_back(100);
	cout << "after v.push_back(100)" << endl;
	
	cout << "v.size() is " << v.size() << endl;
	cout << "v.capacity() is " << v.capacity() << endl;

	v.push_back(100);
	cout << "after v.push_back(100)" << endl;

	cout << "v.size() is " << v.size() << endl;
	cout << "v.capacity() is " << v.capacity() << endl;
	cout << endl;
	
	// empty()
	cout << "is v empty?" << endl;
	cout << v.empty() << endl;
	
	// pop_back
	v.pop_back();  // removes the last element
	
	// Use indexing to access vector elements
	
	cout << "Use indexing to access vector elements" << endl;
	for (int j = 0; j < v.size(); j++)
		cout << v[j] << " ";
	cout << endl << endl;

	// Copying a vector to another
	cout << "Copying a vector to another" << endl;
	
	vector<int> vvv = vv;   //  !!!!! Great! Try and do this with C arrays....
	cout << vvv[5] << endl;
	cout << endl;
	
	// Accessing past v limits
	// The standard-library vector does not guarantee range checking while indexing!!!!!
	cout << "Access past v limits, using indexing" << endl;
	v[125] = 125;
	
	// Use v.at()
	
	// The at() operation is a vector subscript operation that throws an exception of type
	// out_of_range if its argument is out of the vector's range
	
	cout << "Access past v limits, using at()" << endl;
	v.at(5) = 125;  // OK
	// v.at(225) = 225;  // AHW!
		
	
	// ITERATORS
	
	// In a loop such as 
	// for (int j = 0; j < v.size(); j++) cout << v[j] << endl;
	// j is used to access v's elements sequentially, but the compiler cannot know 
//                              (so at each iteration &v[j] must be calculated).
	//
	// Iterators make this situation explicit, so optimizing it.
	// They are similar to pointers.
	
	// An iterator is a value that
	// - Identifies a container and an element in the container
	// - Lets us examine the value stored in that element
	// - Provides operations for moving between elements in the container
	// - Restricts the available operations in ways that correspond to what the container 
// can handle efficiently
	// (Accelerated C++ Practical Programming by Example (C++ in Depth))
	
	// A few iterators referring 
	// to useful elements of a container can be obtained;
	// begin() and end() are the best examples of this. 
	// In addition, many algorithms return iterators.
	
	printIntVector1(v);
	
	// Every standard container, such as vector, defines two associated iterator types:
	//   container-type::const_iterator   ("::" is the Scope Resolution Operator)
	//   container-type::iterator
	// When we want to use an iterator to change the values stored
	// in the container, we use the iterator type. 
	// If we need only read access, then we use the const_iterator type.
	
	// v.begin() and v.end()  return iterators, which are automatically converted to const_iterator
	// They return a value that denotes the beginning or (one past) the end of a container.
	
	// Dereference operator, *


	// Erasing a vector element
	cout << "ERASING" << endl;
	v.erase(v.begin() + 2);
	cout << "After erasing element #2, v.size() is " << v.size() << endl;

	printIntVector1(v);
	
	// IMPORTANT! erase returns an iterator that is positioned on the element that follows the one
	// that we just erased. The iterator used for deletion is invalidated: we know that iter can no
	// longer refer to the same element because that element is gone. In fact, calling erase on a
	// vector invalidates all iterators that refer to elements after the one that was just erased.
	
	// Example: erase all the elements of a vector, greater than 100
	
	// I MUST USE a while loop in this example, no for loop, because iter will not always be incremented....
	cout << "Define a new vector" << endl;
	
	vector<int> vx { 10, 200, 30, 400, 5, 600 };

	printIntVector1(vx);
	
	cout << "Now erase elements > 100" << endl;
	vector<int>::const_iterator iter = vx.begin(); 
	while (iter != vx.end())   // remark that vx.end() MUST be evaluated at each loop! Use no temp variable
	{
		if (*iter > 100)  // Only erase elements > 100
			iter = vx.erase(iter);   // iter now points to the element AFTER the erased one
		else
			iter++;
	}

	printIntVector1(vx);

	// Inserting vector elements http://www.cplusplus.com/reference/vector/vector/insert/
	// The vector is extended by inserting new elements before the element at the specified position
	cout << "INSERTING the v vector at the end of the vx vector" << endl;
	vx.insert(vx.end(), v.begin(), v.end());   	// position in vx were to copy the v vector, range 
												//       to be copied: start and end (end excluded)
	printIntVector1(vx);
	
	cout << "INSERTING a new value into vx" << endl;
	vx.insert(vx.begin()+1, 999);  // position were to copy, value 
	
	printIntVector1(vx);

	// Dereferencing as a means to address and change data
	cout << "Dereferencing as a means to address and change data (pay attention to vector limits!!)\n";
	vector<int>::iterator itx = vx.begin()+3;
	*itx++ = 765;
	*itx = 766;
	
	printIntVector1(vx);

	// GENERIC ALGORITHMS
	cout << "GENERIC ALGORITHMS" << endl;
	
	// Find an element by the find() algorithm (remember to #include <algorithm>)
	// Is there an element equal to 30?
	// find is an algorithm. 
	// find(b, e, c) looks for a given value c in the sequence [b, e)
	// It looks for the specific value given as its third argument. 
	// If the value that we want is present, the function returns an iterator denoting the first
	// occurrence of the value in the given sequence. If the value is not found, then find returns its
	// second argument e.
	
	cout << "FIND (number 5 in vx)\n";
	
	vector<int>::const_iterator it = find(vx.begin(), vx.end(), 5);  // find element 5
	if (it != vx.end())
		cout << "element found! It is at index " << it - vx.begin() << endl;

	// Now use find and insert, to insert a vector of three numbers {997 998 999} 
	// after the first occurrence of value 125
	
	cout << "insert a vector of three numbers {997 998 999} after the first occurrence of value 125\n";
	vector<int> vi = {997, 998, 999};
	vector<int>::const_iterator it1 = find(vx.begin(), vx.end(), 125);  // find element 125
	if (it1 != vx.end()) {
		cout << "element found! It is at index " << it1 - vx.begin() << endl;
		cout << "Now insert the vi vector\n";
		vx.insert(it1+1, vi.begin(), vi.end());  // it1 + 1 points to the element after 125 in vx!
	}

	printIntVector1(vx);

	// 
	// Other algorithms: 

	// reverse the elements (in place!)
	cout << "REVERSE (in place)" << endl;
  	reverse(vx.begin(), vx.end());
	printIntVector1(vx);
	
  	// count the number of elements that have the value 5
	cout << "COUNT (how many numbers = 5?)" << endl;
  	int num=count(vx.begin(), vx.end(), 5);
  	cout << num << endl;
	
	// max vector value    (c++11/c++0x)
	cout << "MAX" << endl;
	vector<int>::const_iterator maxit = max_element(vx.begin(), vx.end()); 
 	//auto maxit = max_element(vx.begin(), vx.end()); 
  	cout << *maxit << endl;
		
	// accumulate vector values (summing them up)
	cout << "ACCUMULATE" << endl;
	int sum = accumulate(vx.begin(), vx.end(), 0); // 0 is the initial value
  	cout << sum << endl;
	
	// Multidimensional vectors
	vector <vector <int> > v2d(3);
	
	return 0;
}


void printIntVector1(vector<int> v)
{
// remember that the end() iterator points PAST the end of the vector
// an iterator is defined as container-type::const_iterator or container-type::iterator   
	// cout the vector
	//cout << sizeof(v) << endl;
	for (vector<int>::const_iterator iter = v.begin(); iter != v.end(); iter++)
		cout << *iter << " ";
	cout << endl;
}