#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_personnes;  // pointeur car vector<Personne&> (vector de références) n'est pas possible

// =========================================================
struct Personne {
  const string nom;
  Liste_personnes amis;
  // MAIS CERTAINEMENT PAS CA : vector<Personne> amis; !!!!
};

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

/*** NON ! SURTOUT PAS COMME CA !!!
void ajoute_ami(Personne nouvel_ami, Personne& quidam)
{
///  quidam.amis.push_back(&nouvel_ami); // SURTOUT PAS !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  / * 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)
{
  // Et s'il/elle était déjà là ???
  // --> 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 !!)
   */
}

/* Autre proposition :
 *    void ajoute_ami(const Personne* nouvel_ami, Personne& quidam); 
 *
 *  --> pas terrible : impose un style « pas cool » à l'UTILISATEUR de la fonction
 *                     l'oblige lui/elle à passer le pointeur
 */


/* *********************************************************
 * est-ce que a est ami de b ?
 */

// PENSEZ A FAIRE DES FONCTIONS-OUTILS !
bool recherche(const Personne* a, Liste_personnes const& L)
{
  // recherche (linéaire) dans L

  for (auto p_personne : L) {
    if (p_personne == a) return true;
  }

  return false;
}

bool est_ami(Personne const& a, Personne const& b)
{
  // est-ce le tableau (des amis) de b contient l'adresse de a ?
  return recherche(&a, b.amis);
  // OUI : l'adresse d'un « objet » est bien son identifiant unique
}

/* *************************************************************
 * Fonction outil pour cherche_amis :
 *   ajoute (sans répétition) une liste L2 à une liste L1
 */
void ajoute(Liste_personnes& L1, Liste_personnes const& L2)
{
  for (auto p_ami : L2) {
    if (not recherche(p_ami, L1))
      L1.push_back(p_ami);
  }
}

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

  Liste_personnes 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;
}

/* *********************************************************
 * PENSEZ À MODULARISER (lorsque cela fait sens CONCEPTUELLEMENT) :
 * afficher une Personne
 */
void affiche(Personne const& p)
{
  cout << p.nom;
}
  
/* *********************************************************
 * afficher une liste d'amis
 */
void affiche(Liste_personnes const& L, string const& separateur = ", ")
{
  for (auto p_ami : L) {
    affiche(*p_ami);
    cout << separateur;
  }
  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;
}