#include <iostream>
using std::cin;
using std::cout;
#include <vector>
using std::vector;
#include <cstdlib>
#include <ctime>

/*Write the function ExtractStrand() that extracts a sorted strand from a non-empty
vector of integers. The strand is extracted as follows:
--> The first element of the vector is removed and becomes the first element of the strand.
--> The remaining vector elements are considered in order. Each element that can be added to the strand while preserving
sorted order is removed from the vector and added to the strand.
--> The function returns a new vector containing the sorted strand. The input vector, which  was passed by reference,
has been modified to remove the extracted numbers, the remaining numbers are preserved in their original order.
Your solution can use vectors and primitive variables but no other data structures (no arrays, etc.)
*/


void print(const vector<int>& v) {
	for (int i : v) cout << i << " ";
}

vector<int> ExtractStrand(vector<int>& v) {
	vector<int> strand;
	vector<int>::iterator itv = v.begin();
	strand.push_back(*itv);
	vector<int>::iterator its = strand.begin();
	//v.erase(itv) returns the next valid iterator, if you erase the last element it will point to .end()
	itv = v.erase(itv);
	while (itv != v.end()) 	{
		its = strand.end() - 1;
		if (*itv >= *its) 		{
			cout << "*itv = " << *itv << ", *its = " << *its << '\n';
			strand.push_back(*itv);
			//++its;
			itv = v.erase(itv);
		}
		else ++itv;
	}
	return strand;
}

int main() {
	srand(time(0));
	vector<int> v;
	for (int i = 0; i < 10; ++i) v.push_back(rand() % 100);
	cout << "Before ExtractStrand(), v = ";
	print(v);
	cout << '\n';
	vector<int> strand = ExtractStrand(v);
	cout << "After ExtractStrand(), v = ";
	print(v);
	cout << '\n';
	cout << "strand = ";
	print(strand);
	cin.get();
}