package exam2011;

import java.util.LinkedList;

public class TriListes2 extends LinkedList<Integer>{
	private static final long serialVersionUID = 1L;

	/* Exercice 2.6
	 * Maintenant la liste testée est l'objet courant.
	 * La méthode n'est donc plus statique.
	 */
	public boolean estTriee() {
		int i = get(0);
		for(int j : this) {
			if(j<i)
				return false;
			i=j;
		}
		return true;
	}
		
	public TriListes2 fusion(TriListes2 l2) {
		TriListes2 f = new TriListes2();

		while(!isEmpty() && !l2.isEmpty()) {
			int i1=getFirst();
			int i2=l2.getFirst();
			if(i1<i2) {
				f.add(i1);
				removeFirst();
			} else {
				f.add(i2);
				l2.removeFirst();				
			}
		}
		if(isEmpty())
			f.addAll(l2);
		else
			f.addAll(this);
		return f;
	}
	
	public void split(TriListes2 r1, TriListes2 r2) {
		boolean pair=true;
		for(int i: this) {
			if(pair)
				r1.add(i);
			else
				r2.add(i);
			pair=!pair;
		}
	}
	
	public TriListes2 tri() {
		if(size()<= 1)
			return this;
		TriListes2 r1 = new TriListes2();
		TriListes2 r2 = new TriListes2();
		split(r1,r2);
		return r1.tri().fusion(r2.tri());
	}
}