//////////////// FIRST CLASS TABLE /////////////////
class MinGetter extends Object {
    /*
        Renvoie le plus petit des entiers donnés.
    */
    Int min(Int a, Int b){
        return a.lt(b).ite(a,b);
    }
    /*
        Renvoie le minimum de la liste, renvoie None si elle est vide.
    */
    Optional listMin(List a) {
        return a.ensureFinite().isEmpty().ite(new None(), new Some(this.min((Int)this.listMin(a.tail).orElse(a.head), a.head)))
    }
}
class Sort extends Object {
    List sort(List in){
        ensure(in).isEmpty().ite(in,minOnStart(in,(Int)((Some)new MinGetter().listMin(in)).value));
    }
    /*
        Place la première occurence de 'min' trouvée dans 'in' au début de la liste, et trie le reste.
    */
    List minOnStart(List in, Int min) {
        return min::this.sort(in.removeFirst(min));
    }
}

///////////////// SECOND CLASS TABLE /////////////////
class MaxGetter extends Object {
    /*
        Renvoie le plus grand des entiers donnés.
    */
    Int max(Int a, Int b){
        return a.gt(b).ite(a,b);
    }
    /*
        Renvoie le maximum de la liste, renvoie None si elle est vide.
    */
    Optional listMax(List a) {
        return a.ensureFinite().isEmpty().ite(
            new None(), 
            new Some(this.max((Int)this.listMax(a.tail).orElse(a.head), (Int)a.head)))
    }
}

class Sort extends Object {
    
    List sort(List in){
        return this.sortAcc(in, []);
    }
    
    List sortAcc(List in, List acc) {
        ensure(in).isEmpty().ite(acc,maxToEnd(in,((Some)new MaxGetter().listMax(in)).value));
    }
    
    /*
        Enlève 'max' de la liste 'in', et applique sortAcc en ajoutant max à l'accumulateur.
    */
    List maxToEnd(List in, Int max) {
        return this.sortAcc(in.removeFirst(max), max::in.removeFirst(max));
    }
}

///////////////// TEST INTERFACE /////////////////¨
// Ces trois lignes permettent de construire les entiers
Int ()
S (Int)
S <: Int

// Ces trois lines permettent de construire les listes
List ()
Cons (List, o)
Cons <: List

// Ces deux lignes permettent l'utilisation des méthodes de tri
// C'est le seul endroit où les deux class tables diffèrent du point de vue de la test interface.
Sort ()
Sort: sort(List)