package exam2011;

import java.util.LinkedList;
import java.util.List;

public class TriListes {
	
	/* Exercice 2.1 et 2.2
	 * Comme la méthode n'utilise aucun objet de type TriListe,
	 * il est normal qu'elle soit statique.
	 */
	
	public static boolean estTriee(List<Integer> s) {
		int i = s.get(0);
		for(int j : s) {
			if(j<i)
				return false;
			i=j;
		}
		return true;
	}
	
	//Exercice 2.3
	public static LinkedList<Integer> fusion(List<Integer> l1,List<Integer> l2) {
		LinkedList<Integer> f = new LinkedList<Integer>();
		LinkedList<Integer> ml1 = new LinkedList<Integer>(l1);
		LinkedList<Integer> ml2 = new LinkedList<Integer>(l2);

		while(!ml1.isEmpty() && !ml2.isEmpty()) {
			int i1=ml1.getFirst();
			int i2=ml2.getFirst();
			if(i1<i2) {
				f.add(i1);
				ml1.removeFirst();
			} else {
				f.add(i2);
				ml2.removeFirst();				
			}
		}
		if(ml1.isEmpty())
			f.addAll(ml2);
		else
			f.addAll(ml1);
		return f;
	}
	
	//Exercice 2.4
	public static void split(List<Integer> l, List<Integer> r1, List<Integer> r2) {
		boolean pair=true;
		for(int i: l) {
			if(pair)
				r1.add(i);
			else
				r2.add(i);
			pair=!pair;
		}
	}
	
	//Exercice 2.5
	public static List<Integer> tri(List<Integer> l) {
		if(l.size()<= 1)
			return l;
		List<Integer> r1 = new LinkedList<Integer>();
		List<Integer> r2 = new LinkedList<Integer>();
		split(l,r1,r2);
		r1=tri(r1);
		r2=tri(r2);
		return fusion(r1,r2);
	}
}