Itération sur des multi-ensembles

Code fourni : cf. l'unité de compilation EnsemblesIterables.

Dans le paquet session3.tp.v1, recopier l'interface session3.demo.ensembles.Ensembles2 et la renommer en MultiEnsemble.

• La rendre générique, en paramétrant par le type E des éléments contenus dans le multi-ensemble.
• Ajouter des services :
  • la méthode int occurrences(Object e) permettant de calculer le nombre d'occurrences d'un élément dans le multi-ensemble,
  • la méthode MultiEnsemble<E> filtrer(Predicate<E> pred) permettant de filtrer le multi-ensemble en ne retenant que les éléments vérifiant le prédicat,
  • les méthodes String representer() et boolean estEgal(MultiEnsemble<?> ens), analogues de toString et equals.
• Rendre abstraites toutes les méthodes.

Implémenter cette interface en utilisant le patron composite.

• Utiliser la définition inductive suivante.

  MultiEnsemble ::= Vide | Cons(Element, MultiEnsemble) | Union(MultiEnsemble, MultiEnsemble)
  

• Créer une interface intermédiaire MultiEnsembleComposite. Y placer les méthodes factorisables.
• Pour chaque cas de la définition inductive, créer une classe d'implémentation.
• Ne pas utiliser la récursion, mais l'itération.
• Commenter la méthode privée decomposer de la classe Union de manière à expliquer ce qu'elle réalise.

Tester en utilisant la fonction principale suivante.

public static void main(String[] args) {
  MultiEnsemble<Integer> vide = Vide.SINGLETON();
  System.out.println("{} ? " +vide);
  MultiEnsemble<Integer> a = vide.cons(1).cons(1).cons(2);
  System.out.println("{2, 1, 1} ? " + a);
  System.out.println("false ? " + a.estVide());
  System.out.println("true ? " + a.estCons());
  System.out.println("false ? " + a.estUnion());
  System.out.println("{2, 1, 1, 2, 1, 1} ? " + a.union(a));
  System.out.println("{2, 1, 1} ? " + a.union(vide));
  a = vide.cons(3).cons(4).union(a);
  System.out.println("{4, 3, 2, 1, 1} ? " + a);
  System.out.println("{4, 3} ? " + a.gauche());
  System.out.println("{2, 1, 1} ? " + a.droit());
  System.out.println("0 ? " + a.occurrences(5));
  System.out.println("2 ? " + a.occurrences(1));              
  System.out.println("true ? " + a.equals(a));
  System.out.println("false ? " + a.equals(a.cons(5)));

  MultiEnsemble<Integer> b = vide;
  BigInteger max = BigInteger.valueOf(100000);
  for(int i = 0; i < max.intValue(); i++){
    b = b.union(vide.cons(i));
  }
  System.out.println(max + " ? " + b.taille());
  BigInteger s = BigInteger.ZERO;
  while(!b.estVide()){
    s = s.add(BigInteger.valueOf(b.element()));
    b = b.reste(); 
  }
  System.out.println(((max.multiply(max.subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)))) + " ? " + s);
}

Définir une fonction permettant d'éliminer les doublons dans un multi-ensemble. Proposer deux versions, l'une récursive, l'autre itérative. Les tester.

Code fourni : cf. l'unité de compilation EnsemblesIterablesAvecIterateur.

Dans un nouveau paquet session3.tp.v2, faire évoluer la première version ainsi.

• Déclarer que l'interface MultiEnsemble<E> étend l'interface Iterable<E>.
• Définir une classe Iterateur<E> implémentant Iterator<E>. Les instances de cette classe sont mutables.
• Utiliser pour itérer la boucle dite "For-each".

Reprendre tous les tests, en récrivant les itérations.

Code fourni : cf. l'unité de compilation EnsemblesIterablesAvecIterateurEtVisiteur.

Dans un nouveau paquet session3.tp.v3, faire évoluer la seconde version ainsi.

• Définir une interface Visiteur.

  interface Visiteur<T, E>{
    T resultat();
    Visiteur<T, E> visiterVide();
    Visiteur<T, E> visiterCons(Ensemble<E> ens);
  }
  

• Ajouter une méthode d'accueil du visiteur dans l'interface MultiEnsemble.

Définir deux visiteurs, l'un pour calculer le cardinal du multi-ensemble (nombre total d'occurrences), l'autre pour représenter le multi-ensemble.

Reprendre tous les tests. Ajouter des tests pour les visiteurs.