/**
   POGL : programmation objet et génie logiciel
   Polymophisme et classes paramétrées

   @author Thibaut Balabonski @ Université Paris-Sud
   @version 28 janvier 2019
*/

import java.util.ArrayList;

/**
   Une classe pour représenter une donnée de type [String] associée à une
   priorité de type [int].
*/
class IntStringPair {
    // Un élément est plus prioritaire si son attribut [priority] est plus
    // élevé.
    private int priority;
    private String contents;

    // Constructeur
    public IntStringPair(int p, String c) {
	this.priority = p;
	this.contents = c;
    }

    // Une méthode pour récupérer le contenu
    public String getContents() {
	return this.contents;
    }

    // Renvoie un nombre négatif si [this] moins prioritaire que [other]
    //                   positif si [this] plus prioritaire que [other]
    public int compareTo(IntStringPair other) {
	return this.priority - other.priority;
    }

    // Exemple d'utilisation
    public static void main(String[] args) {
	IntStringPair p3 = new IntStringPair(3, "trois");
	IntStringPair p4 = new IntStringPair(4, "quatre");
	System.out.println("Attendu -1 : " + p3.compareTo(p4));
	System.out.println("Attendu  1 : " + p4.compareTo(p3));
	System.out.println("Attendu  0 : " + p3.compareTo(p3));
	String maxPContents = (p3.compareTo(p4)>0)?p3.contents:p4.contents;
	System.out.println("Attendu quatre : " + maxPContents);
    }
}

/**
   La classe précédente impose un contenu de type [String], mais aucune de ses
   opérations ne repose sur ce fait : le même code pourrait être utilisé pour
   un contenu de n'importe quel type.

   On peut ajouter à la définition de la classe un paramètre de type, qui
   introduit un type [T] quelconque à la place de [String].
*/
class PairWithIntPriority<T> {
    // Le code est identique à celui de la classe précédente.
    // Chaque mention à [String] est remplacée par [T].
    private int priority;
    private T   contents;
    public PairWithIntPriority(int p, T c) {
	this.priority = p;
	this.contents = c;
    }
    public T getContents() {
	return this.contents;
    }
    public int compareTo(PairWithIntPriority<T> other) {
	return this.priority - other.priority;
    }

    // Exemples d'utilisation
    public static void main(String[] args) {
	PairWithIntPriority<String> p3 = new PairWithIntPriority<>(3, "trois");
	PairWithIntPriority<Integer> p4 = new PairWithIntPriority<>(4, 4);
	PairWithIntPriority<Integer[]> p5 = new PairWithIntPriority<>(5, new Integer[5]);
	PairWithIntPriority<Integer[]> p6 = new PairWithIntPriority<>(6, new Integer[6]);
	System.out.println("Attendu -1 : " + p5.compareTo(p6));
	// [p4.compareTo(p5)] serait refusé, pour incompatibilité entre
	// [Integer] et [Integer[] ].
    }
}
/**
   Dans ce code, [T] désigne un type quelconque. Tout cela fonctionne tant
   qu'on se contente de prendre et de renvoyer des objets de type [T] sans
   leur appliquer de méthodes ou d'opérations spécifiques.

   C'est ce mécanisme qui est mis en jeu dans des classes de la bibliothèque
   standard comme [ArrayList<T>] où [HashMap<K, V>].
*/

/**
   Les paramètres de type peuvent également apparaître dans des interfaces.
   Ci-dessous une interface pour les classes d'objets comparables avec des
   objets de type [U].
*/
interface Comparable<U> {
    // compareTo renvoie un négatif si [this] plus petit que [other]
    //                      positif si [this] plus grand que [other]
    int compareTo(U other);
}

/**   
   En général, cette interface s'applique à une classe dont les éléments
   sont comparables entre eux. Par exemple, voici une classe encapsulant des
   entiers et permettant la comparaison. Le paramètre [Int] donné à [Comparable]
   est la classe [Int] elle-même.
*/
class Int implements Comparable<Int> {
    int i;
    public Int(int i) { this.i = i; }
    public int compareTo(Int other) {
	return this.i - other.i;
    }
}
/**
   Deux autres exemples de classes implémentant l'interface [Comparable<U>]
   sont [IntStringPair] et [PairWithIntPriority]. Ces classes auraient
   également pu être introduites avec respectivement :

   class IntStringPair implements Comparable<IntStringPair>

   et
   
   class PairWithIntPriority<T> implements Comparable<PairWithIntPriority<T>>
*/


/**
   La bibliothèque standard propose déjà une bibliothèque [ArrayList<T>] pour
   des tableaux redimensionables contenant des éléments d'un type [T]
   quelconque.
   Les opérations permises sur ces tableaux, comme [add], [remove], [get] sont
   génériques. Elles permettent de manipuler les éléments du tableau sans rien
   supposer de leur structure.
   
   Si on veut une opération permettant d'extraire un élément maximal d'un
   tableau, on a besoin de s'assurer que les éléments du tableau sont
   comparables deux à deux. On peut pour cela utiliser un paramètre de type
   contraint par une interface avec le mot-clé [extends].

   Ci-dessous, on introduit donc un paramètre de type [T], en précisant qu'il
   ne peut être instancié que par des classes implémentant l'interface 
   [Comparable<T>].
*/
class PriorityArray<T extends Comparable<T>> {
    // Pour le contenu, on reprend les tableaux de la bibliothèque.
    private ArrayList<T> contents;

    // On fournit un constructeur trivial et une méthode d'ajout d'un élément
    public PriorityArray() { this.contents = new ArrayList<T>(); }
    public void add(T e) { this.contents.add(e); }
    
    // Une méthode pour renvoyer un élément maximal
    public T getElementWithMaxPriority() {
	// On enregistre un maximum courant (échoue si le tableau est vide)
	T currentMax = contents.get(0);
	// Pour chaque élément du tableau, s'il est plus grand que le maximum
	// courant alors il devient le nouveau maximum courant.
	for (T elt : contents) {
	    // Comme [T] implémente [Comparable<T>] on a accès à la méthode
	    // [compareTo].
	    // Sans mention [extends Comparable<T>] dans la définition de
	    // la classe, le test suivant eût été rejeté par le compilateur.
	    if (elt.compareTo(currentMax) > 0) {
		currentMax = elt;
	    }
	}
	return currentMax;
    }

    // Un exemple d'utilisation
    public static void main(String[] agrs) {
	PriorityArray<Int> parr = new PriorityArray<>(arr);
        // Remarque : à la ligne précédente il n'est pas nécessaire de préciser
        // le type du contenu du tableau créé avec [new], qui est déduit du
        // contexte.
	parr.add(new Int(1));
	parr.add(new Int(5));
	parr.add(new Int(2));
	System.out.println("Attendu 5 : " + parr.getElementWithMaxPriority().i);
	parr.add(new Int(6));
	System.out.println("Attendu 6 : " + parr.getElementWithMaxPriority().i);
    }
    public PriorityArray(ArrayList<T> arr) {
	this.contents = arr;
    }
}

/**
   On peut utiliser le même mécanisme pour généraliser le type donné aux
   priorités dans notre classe [PairWithIntPriority]. Au lieu de [int], on
   acceptera n'importe quel type [P] implémentant l'interface [Comparable<P>].

   Remarquez qu'à l'instar de [HashMap<K, V>], nos classes paramétrées peuvent
   dépendre de plusieurs paramètres de types.

   Aussi, comme remarqué précédemment, la class obtenue fournit une méthode
   [compareTo], et implémente donc l'interface [Comparable<U>].
*/
class PairWithPriority<P extends Comparable<P>, T>
    implements Comparable<PairWithPriority<P, T>>
{
    // Le code est similaire aux versions précédentes.
    // Le type [int] des priorités est remplacé par [P].
    private P priority;
    private T contents;
    public PairWithPriority(P p, T c) {
	this.priority = p;
	this.contents = c;
    }
    public T getContents() {
	return this.contents;
    }
    // Seule différence dans le code : la comparaison des priorités ne se fait
    // plus par une opération arithmétique directe sur les attributs, mais via
    // un appel à la méthode [compareTo] fournie par la classe [P].
    public int compareTo(PairWithPriority<P, T> other) {
	return this.priority.compareTo(other.priority);
    }

    // Exemples d'utilisation
    public static void main(String[] args) {
	// Construction et utilisation de paires
	PairWithPriority<Int, String> p3 =
	    new PairWithPriority<>(new Int(3), "trois");
	PairWithPriority<Int, String> p4 =
	    new PairWithPriority<>(new Int(4), "quatre");
	System.out.println("Attendu -1 : " + p3.compareTo(p4));

	// Utilisation comme contenu d'un tableau de priorités
	PriorityArray<PairWithPriority<Int, String>> parr =
	    new PriorityArray<>(arr);
	parr.add(p3);
	parr.add(p4);
	System.out.println("Attendu quatre : " +
			   parr.getElementWithMaxPriority().getContents());
    }
}