forward_list<int> LinkedListsExpert::partition(forward_list<int> list, int x){
    forward_list<int> lessThanX, greaterThanX, equalX;
    forward_list<int>::iterator it = list.begin();
    while (it!=list.end()) {
        if (*it < x) {
            lessThanX.push_front(*it);
        } else if (*it > x){
            greaterThanX.push_front(*it);
        } else{
            equalX.push_front(*it);
        }
        it++;
    }
    //merge lists
    it = equalX.begin();
    while (it != equalX.end()) {
        greaterThanX.push_front(*it);
        it++;
    }
    it = lessThanX.begin();
    while (it != lessThanX.end()) {
        greaterThanX.push_front(*it);
        it++;
    }
    return greaterThanX;
}

void LinkedListsExpert::printList(forward_list<int> list){
    std::forward_list<int>::iterator it;
    for (it = list.begin(); it != list.end(); it++) {
        cout << *it << "  ";
    }
    cout << "\n";
}

int primeCount(forward_list<int> lst)
{
    int total;
    
    if(lst.empty())
    {
        return 0;
    }
    
    else
    {
        bool prime = isPrime(lst.front());
        lst.pop_front();
        
        if(prime == true)
        {
            total = 1 + primeCount(lst);
        }
        
        if(prime == false)
        {
            total = primeCount(lst);
        }
    }
    
    return total;
}

void listCopy(forward_list<T> L, forward_list<T> &P) // reverse L and put it into P
{
    for(typename forward_list<T>::iterator start = L.begin() ; start != L.end() ; ++start)
    {
        P.push_front(*start);
    }
}

void display(forward_list<T> lst)
{
    
    for(typename forward_list<T>::iterator start = lst.begin(); start != lst.end() ; ++start)
    {
        cout << *start << " ";
    }
    
    cout << endl;
}

template <typename T> void printList(const forward_list<T> &listRef)
{
	if (listRef.empty())
		cout<<"List is empty";
	else
	{
		ostream_iterator<T> output(cout, " ");
		copy(listRef.begin(), listRef.end(), output);
	}
}

void remove_evens_and_double_odds(forward_list<int>& data) {
    for (auto cur = data.begin(), prev = data.before_begin(); cur != data.end(); ) {
        if (*cur & 0x1)
            cur = data.insert_after(prev, *cur),
            advance(prev, 2),
            advance(cur, 2);
        else
            cur = data.erase_after(prev);
    }
}

void insertWord(forward_list<string> &forList,
                                           const string &str1,const string &str2)
{
    auto prev = forList.before_begin();
    for(auto i=forList.begin();i != forList.end();prev=i,++i)
        if(*i == str1){
            forList.insert_after(i,str2);
            return ;
        }
   forList.insert_after(prev,str2);
}

int primeCount(forward_list<int> lst){
	if(lst.empty()){
		return 0;
	}else{ 
		bool prime = isPrime(lst.front());
		lst.pop_front();
		if(prime){
			return 1 + primeCount(lst);
		}else{
			return primeCount(lst);
		}
	}
}

void find_and_insert(forward_list<string> &list, string const& to_find, string const& to_add)
{
    auto prev = list.before_begin();
    for (auto curr = list.begin(); curr != list.end(); prev = curr++)
    {
        if (*curr == to_find)
        {
            list.insert_after(curr, to_add);
            return;
        }
    }
    list.insert_after(prev, to_add);
}

// Merge a connected compontent of lines to a new line with width.
void merge(const forward_list<LineSeg*>& component, LineSegW& out) {
	// TODO: in principle no loop/collection is necessary
	// Note: profiling indicates this is not even close to a bottleneck, so ok for now
	forward_list<Point*> component2i;
	for (auto vec = component.begin(); vec != component.end(); ++vec) {
		component2i.push_front(&(*vec)->s);
		component2i.push_front(&(*vec)->e);
		//component2i.push_front((Vec2i*)&(*vec)->val[0]);
		//component2i.push_front((Vec2i*)&(*vec)->val[2]);
	}

	line_fit(component2i, out);
}

int primeCount( forward_list<int> lst ){
    
    static int counter = 0;
    if( lst.empty() ) { return 0; }// If lst is empty, then counter = 0.
    else
    {
        if ( isPrime( lst.front() ) ){ ++counter;}
}
    
    lst.pop_front();
    primeCount(lst); 
    
    return counter;
} // Function that returns number of Primes in a forward_list

void func(forward_list<string> &flist, const string s1, const string s2)
{
	auto before = flist.before_begin();
	auto curr = flist.begin();
	while(curr!=flist.end()) {
		if(*curr == s1){
			flist.insert_after(curr, s2);
			return;
		}else{
			curr++;
		}
	}
	flist.insert_after(curr, s2);
}

int primeCount(forward_list<int> lst){
    if(lst.empty()){ //base case
        return 0; //empty list has no (prime) numbers
    }
    if(isPrime(lst.front())){ //check if first item is prime
        cout << lst.front() << endl;
        lst.pop_front(); //can do this bc lst is passed by value
        return 1 + primeCount(lst); //recursive call
    }
    else{ //first number isnt prime
        lst.pop_front(); //dont output, just delete it
        return primeCount(lst); //dont add 1 to primecount
    }
}

void Insert(forward_list<string> &lst, const string &str1, const string &str2) {
	auto prev = lst.cbefore_begin();
	auto curr = lst.cbegin();
	while (curr != lst.cend()) {
		if (*curr != str1) {
			prev = curr;
			++curr;
		}
		else {
			lst.insert_after(curr, str2);
			return;
		}
	}
	lst.insert_after(prev, str2);
}

void printLots(forward_list<T> L, forward_list<int> P){
    int temp = 0;
    while(!P.empty()){
        int pos = P.front() - temp;
        temp = pos;
        for(; pos > 0; --pos){
            L.pop_front();
        }
        cout << L.front() << " ";
        P.pop_front();
    }
    //keep L.pop_front() until you get to the right position
    
    return;
}

bool Case::ajouterPions(forward_list<Pion*> fl, int nbPionsToAdd) {
  if(nbPions + nbPionsToAdd > nbPionsMax) {
    cout << "[Case.cpp/ajouterPions] Erreur : Impossible de rajouter les pions. Pas assez de place." << endl;
    return false;
  }
  else {
    listePions.splice_after(listePions.before_begin(), fl);
    nbPions += nbPionsToAdd;
    
    for(auto it=fl.begin() ; it!=fl.end() ; ++it)
      (*it)->setPosition(position);
    
    return true;
  }
}

void copieListe(forward_list<TypeInfo> maListeOriginale, forward_list<TypeInfo>& maListecopiee) {
    // pour conserver l'ordre dans la copie il faut :
    // 1 empiler les valeurs de la liste originale en faisant cun parcours complet gauche droite de la liste
    // 2 dépiler les valeurs de la liste originale en les insérant en tête de la copie
    // on peut au choix utiliser la ListeChaineePile déjà définie, une liste chainée en avant de la STL, ou une pile de la STL

    // AVEC UNE LISTE de la STL
    forward_list<TypeInfo> maCopieInversee;
    // étape 1
    for (TypeInfo& val : maListeOriginale) {
        maCopieInversee.push_front(val);
    } // end for
    // étape 2
    for (TypeInfo& val : maCopieInversee) {
        maListecopiee.push_front(val);
    } // end for
    
    /*
    // AVEC UNE PILE de la STL
    stack<TypeInfo> maPile;
    // étape 1
    for (TypeInfo& val : maListeOriginale) {
        maPile.push(val);
    } // end for
    // étape 2
    while (!maPile.empty()) {
        maListecopiee.push_front(maPile.top());
        maPile.pop();
    } // end while
    */
}

inline int primeCount(forward_list<int> lst)
{
    forward_list<int>::iterator itr = lst.begin(); //starts iterator at beg
    
    int total = primeCount(lst, itr); //calls recursive helper function
    
    return total; //returns total # of primes
}

int LinkedListsExpert::getNthToLast(forward_list<int> list, int n){
    forward_list<int>::iterator current = list.begin();
    forward_list<int>::iterator previous = list.begin();
    
    for(int i=1; i<=n; i++){
        if (current != list.end()) {
            current++;
        }
    }
    
    while (current != list.end()) {
        current++;
        previous++;
    }
    
    return *previous;
}