/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author hf
 */
class CelluleInt {

    public int val;
    public CelluleInt suivant;

    public CelluleInt() {
        this(0, null);
    }

    public CelluleInt(int v) {
        this(v, null);
    }

    public CelluleInt(int v, CelluleInt s) {
        val = v;
        suivant = s;
    }
}

interface PileInt {
    public boolean estVide();
    public int sommet();
    public PileInt empiler(int v);
    public PileInt depiler();
    public void afficher();
    public void afficherR();
    public PileInt concat(PileInt p);
}

// cette classe n'était pas indispensable
class ListeInt {
    public CelluleInt tete;
    public ListeInt(CelluleInt l) {
        tete = l;
    }
    public ListeInt() {
        tete = null;
    }
    public ListeInt(ListeInt l) {
        tete = l.tete;
    }
    public int valTete() {
        return tete.val;
    }
    public boolean estVide() {
        return tete == null;
    }
    public void afficher() {
        CelluleInt tmp = tete;
        while (tmp != null) {
            System.out.print(tmp.val + " ");
            tmp = tmp.suivant;
        }
        System.out.println();
    }

    public static void afficher(ListeInt l) {
        l.afficher();
    }

    public ListeInt listeSuivant() {
        tete = tete.suivant;
        return this;
    }
    public static ListeInt listeSuivant(ListeInt l) {
        return l.listeSuivant();
    }
    public static ListeInt insererTete(Integer v, ListeInt l) {
        ListeInt tmp = l;
        return tmp.insererTete(v);
    }

    public ListeInt insererTete(Integer v) {
        if (tete == null) {
            tete = new CelluleInt(v);
        } else {
            tete = new CelluleInt(v, tete);
        }
        return this;
    }
}

// cette classe utilise ListeInt
// on peut aussi intégrer les diverses méthodes
// de LiisteInt à l'intérieur de PileInt
class PileIntListe implements PileInt {
    ListeInt data;
    public PileIntListe() {
        data = new ListeInt();
    }

    public boolean estVide() {
        return data.estVide();
    }

    public int sommet() {
        return data.valTete();
    }

    public PileInt depiler() {
        data = data.listeSuivant();
        return this;
    }

    public PileInt empiler(int v) {
        data = data.insererTete(v);
        return this;
    }
    public PileInt concat(PileInt l1) {
        if (estVide()) {
            return l1;
        } else {
            int tmp = sommet();
            depiler();
            return concat(l1.empiler(tmp));
        }

    }

    public static PileInt concat(PileInt p1, PileInt p2) {
        if (p1.estVide()) {
            return p2;
        } else {
            int tmp = p1.sommet();
            return concat(p1.depiler(), p2).empiler(tmp);

        }
    }

    public void afficherR() {
        PileIntListe tmp = new PileIntListe();
        while (!estVide()) {
            tmp.empiler(sommet());
            depiler();
        }
        while (!tmp.estVide()) {
            empiler(tmp.sommet());
            System.out.print(tmp.sommet() + " ");
            tmp.depiler();
        }
        System.out.println();
    }
    public static void split(PileInt l, int pivot, PileInt inf, PileInt sup) {
        for (PileInt tmp = l; !tmp.estVide(); tmp.depiler()) {
            if (tmp.sommet() < pivot) {
                inf.empiler(tmp.sommet());
            } else {
                sup.empiler(tmp.sommet());
            }
        }

    }

    public void afficher() {
        data.afficher();
    }

    public static PileInt tri(PileInt l) {
        if (l.estVide()) {
            return l;
        }
        int val = l.sommet();
        PileInt inf = new PileIntListe();
        PileInt sup = new PileIntListe();
        split(l.depiler(), val, inf, sup);
        return concat(tri(inf), tri(sup).empiler(val));
    }
}

class ExamjuinIF2 {

    public static void main(String[] args) {
        // créer une PileInt à partir d'une PileIntListe
        PileInt p1= new PileIntListe();
        for(int i=0;i<6; i++) p1.empiler(i);
        System.out.println("Pile l1");
        p1.afficher();
        PileInt p2= new PileIntListe();
        for(int i=0;i<5;i++)p2.empiler(i*i);
        // essai de afficherR et afficher
        System.out.println("Pile l2 sommet en fin");
        p2.afficherR();
        System.out.println("Pile l1 sommet en tete");
        p2.afficher();
        // essaie de concat
        (p1.concat(p2)).afficher();
        PileIntListe p3=new PileIntListe();
        // tir de liste
        for (int i=0; i<100; i++)p3.empiler((int)(Math.random()*100));
        System.out.println("trier la liste");
        p3.afficher();
        System.out.println("triee:");
        (PileIntListe.tri(p3)).afficherR();
    }
}