#include <iostream>
#include <string>
#include <vector>
using namespace std;

// =========================================================
/* Il est préférable d'expliciter le type « liste d'amis »
 *   (ne serait-ce que pour le retour cherche_amis())
 * ... mais pour cela il faut faire une pré-déclaration de 
 *     la structure Personne !
 */
struct Personne;
typedef vector<const Personne*> Liste;

// =========================================================
struct Personne
{
  string nom;
  //  Id id; // pas nécessaire : un pointeur est un identifiant unique de son contenu pointé
  Liste amis;
  // MAIS CERTAINEMENT PAS CA : vector<Personne> amis; !!!!
};

/* *********************************************************
 * ajoute nouvel_ami aux amis de quidam
 */

/* Proposition 1 :
 *    void ajoute_ami(const Personne* nouvel_ami, Personne& quidam); 
 *  --> pas terrible : impose un style « pas cool » à l'utilisateur
 */

/*** NON ! SURTOUT PAS COMME CA !!!
void ajoute_ami(Personne nouvel_ami, Personne& quidam)
{
  quidam.amis.push_back(&nouvel_ami); / * NON ! JAMAIS JAMAIS JAMAIS !!!!!!!!!!

                                       * car adresse d'une variable locale qui N'existera PLUS 
                                       * dès la fin de cette fonction !!   * /
}
***/

void ajoute_ami(Personne const& nouvel_ami, Personne& quidam)
{
  // une fois est_ami() fait : ne pas ajouter à double :
  // if (not est_ami(nouvel_ami, quidam))

  quidam.amis.push_back( &nouvel_ami );
  /* OK car passé par référence (mais attention quand même à la durée
   * de vie de l'objet externe !!)
   */
}

/* *********************************************************
 * PENSEZ A FAIRE DES FONCTIONS-OUTIL !
 */
bool contient(Liste const& L, const Personne& e)
{
  // recherche (linéaire) dans L

  // if (a.nom == p_ami->nom) { // NON : plusieures personnes peuvent avoir le même non

  // if (a == *p_ami) { // NON : (1) == ne compile pas --> il faudrait faire une fonction
                        //       (2) mais plus largement on peut se demander si 2 Personnes ayant le même contenu sont quand même la même personne... (manque peut être un champ « identifiant unique », mais voir le OUI ci-dessous)

  for (auto p_personne : L) {
    if (p_personne == &e) { // OUI : l'adresse d'un « objet » est bien son identifiant unique
      return true;
    }
  }

  return false;
}

/* *********************************************************
 * est-ce que a est ami de b ?
 */
bool est_ami(Personne const& a, Personne const& b)
{
  return contient(b.amis, a);
}

/* *************************************************************
 * ajoute (sans répétition) une liste L2 à une liste L1
 */
void ajoute(Liste& L1, Liste const& L2)
{
  for (auto p_ami : L2) {
    if (not contient(L1, *p_ami))
      L1.push_back(p_ami);
  }
}

/* *********************************************************
 * les amis de mes amis (...de mes amis... ; 
 *   à une distance donnée)
 */
Liste cherche_amis(const Personne& quidam, unsigned int distance)
{
  if (distance <= 1) return quidam.amis;

  Liste retour;

  for (auto p_ami : quidam.amis) {
    ajoute(retour, cherche_amis(*p_ami, distance - 1));
    /* NOTE : cet appel récursif pourrait être potentiellement « dangereux »
     * si l'on n'avait pas l'argument de distance : il risquerait de boucler
     * sans fin en cas de cycle (p.ex. ami1 --> ami2 --> ami1 ).
     * Pour éviter les récursions infinies sur les cycles, sans argument de distance maximale,
     * il faudrait ajouter à chaque ami un booléen indiquant si l'on est déjà passé ou non.
     */
  }
  
  return retour;
}

/* *********************************************************
 * afficher une liste d'amis
 */
void affiche(Liste const& L)
{
  for (auto p_ami : L) {
    cout << p_ami->nom << ", ";  // le mieux serait de faire une fonction pour afficher une Personne
  }
  cout << endl;
}

// *********************************************************
void test_est_ami(const Personne& p1, const Personne& p2)
{
  cout << p1.nom << ' ';
  if (est_ami(p1, p2)) {
    cout << "est";
  } else {
    cout << "n'est pas";
  }
  cout << " ami de " << p2.nom
       << endl;
}

// *********************************************************
int main()
{
  Personne p1({ "Pierre"  , {} });
  Personne p2({ "Paul"    , {} });
  Personne p3({ "Jacques" , {} });

  // Paul est ami de Pierre : passer p2 ou &p2 ?
  ajoute_ami( p2 , p1); 

  test_est_ami(p2, p1);
  test_est_ami(p3, p1);

  Personne p4({ "Jean"    , {} });

  ajoute_ami(p3, p1); // Jacques est ami de Pierre
  ajoute_ami(p3, p2); // Jacques est aussi ami de Paul

  ajoute_ami(p4, p3); // Jean est ami de Jacques
  ajoute_ami(p4, p2); // Jean est aussi ami de Paul

  ajoute_ami(p1, p4); // Pierre est ami de Jean
  
  ajoute_ami(p2, p1); /* Paul est à nouveau ami de Pierre : 
                       * pas d''ajout, donc             */

  // Tous les amis de Pierre : Paul, Jacques
  cout << "=== Tous les amis de Pierre :" << endl;
  affiche(cherche_amis(p1, 1));

  // Tous les amis des amis de Pierre : Jacques, Jean
  // Jean ne doit y être qu'une seule fois
  cout << "=== Tous les amis des amis de Pierre :" << endl;
  affiche(cherche_amis(p1, 2));

  /* Tous les amis des amis des amis de Pierre :
   *   Jean, Pierre, ..
   * Pierre lui-même y est, mais ça NE doit PAS boucler
   *   à l'infini (grace à l'argument de distance)...
   */
  cout << "=== Tous les amis des amis des amis de Pierre :"
       << endl;
  affiche(cherche_amis(p1, 3));
  
  return 0;
}