//---------------------------------------------------------------------------
#ifndef Unit1H
#define Unit1H
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
//---------------------------------------------------------------------------
const AnsiString CA_tiret="-";
const AnsiString CA_nihil="";
const AnsiString CA_espace=" ";
const AnsiString CA_separ="------------------------------";
const AnsiString CA_ajout="Ajout n°";
const AnsiString CA_lien=" : lien ";
const char Cc_espace=' ';
const char Cc_tiret='-';
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:	// Composants gérés par l'EDI
   TMemo *Memo1;
   TButton *Button1;
   TLabel *Label1;
   void __fastcall Button1Click(TObject *Sender);
   void __fastcall FormClose(TObject *Sender, TCloseAction &Action);
private:	// Déclarations utilisateur
public:		// Déclarations utilisateur
int compteur, niveau;
bool nouveau_lien;
AnsiString A_pred,A_succ;
AnsiString A_pred_syr,A_succ_syr;
AnsiString couple;

// contient l'arborescence en construction
TStringList *SYR;

__fastcall TForm1(TComponent* Owner);

int succ_syr(int);
void suivant();
bool ajout(int,int);
bool ajout10();
void insert(int,int);
void insert10(int,int);
void insert20(int,int);
void insert30(int,int,int);

void Aff_memo();

void traite(AnsiString);

AnsiString traite10(AnsiString);
AnsiString supp_coupl(AnsiString);

void traite_couple();
AnsiString extrait_P(AnsiString);
AnsiString extrait_S(AnsiString);

bool existe_couple(int,int);
bool existe_couple10(int,int);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// Étude sur Syracuse — Gilles Louïse — février 2024
// Création de la section commençante
// de l'arborescence syracusienne infinie
// à partir du 1 initial (racine - niveau 0)
// sur la base des premières correspondances
// du type prédécesseur-successeur (p-s)
// sans cesse recalculées depuis le début
// pour simuler une liste infinie virtuelle
// et mettre à jour l'arborescence
// par le premier couple p-s
// qu'on peut ajouter quelque part
// à l'état actuel de l'arborescence
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
   : TForm(Owner)
{
// Création de la mémoire de l'arborescence
SYR=new TStringList;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
int n;

// Nombre d'ajouts à partir d'une arborescence vide
n=150;

// Ajoute à chaque itération un noeud 
// au premier endroit disponible où un lien
// peut être attaché à l'arborescence actuelle SYR
for(compteur=0;compteur<n;compteur++)
   {
   Label1->Caption=n-compteur;
   suivant();
   Application->ProcessMessages();
   }
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormClose(TObject *Sender, TCloseAction &Action)
{
// Rend la mémoire au système
delete SYR;
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//------------------   P R O C É D U R E S   --------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
// Renvoie le successeur unique du n envoyé
// selon la moulinete syracusienne
int TForm1::succ_syr(int n)
{
if((n%2)==0) return n/2; else return 3*n+1;
}
//---------------------------------------------------------------------------
// Calcule le lien suivant dans l'arborescence
// en cherchant un couple disponible
// dans la liste virtuelle infinie.
// On boucle jusqu'à ce qu'on trouve
// puisqu'il est certain qu'un couple suivant
// va pouvoir être inséré quelque part
// à l'état actuel de l'arborescence SYR
void TForm1::suivant()
{
int p,s;
bool b;

// Calcul à partir de la racine de la liste infinie virtuelle
p=0;
do
   {
   // test du couple p-s suivant de la liste infinie virtuelle
   s=succ_syr(++p);

   // Si ce couple existe déjà dans l'arborescence,
   // l'ajout n'a pas lieu puisque c'est déjà fait,
   // sinon le couple p-s est candidat
   // pour être inséré à l'arborescence,
   // c'est la procédure booléenne ajout
   // qui dira si l'ajout peut se faire ou non
   if(existe_couple(p,s)) b=false; else b=ajout(p,s);
   }
// boucle tant qu'on n'a pas trouvé un couple à ajouter
while(!b);

// Le lien suivant p-s a été détecté
// comme pouvant être attaché
// quelque part dans l'arborescence,
// on l'insère donc dans l'arborescence
insert(p,s);

// Affichage des détails du calcul
Aff_memo();
}
//---------------------------------------------------------------------------
// Vérifie si l'on peut ajouter le couple p-s dans l'arborescence
bool TForm1::ajout(int p, int s)
{
// mémorise le couple envoyé dans les variables générales
// A_pred et A_succ (de la liste virtuelle infinie)
A_pred=p;
A_succ=s;

// Si l'arborescence est vide, l'ajout peut se faire,
// sinon c'est ajout10 qui le dira
if(SYR->Count==0) return true; else return (ajout10());
}
//---------------------------------------------------------------------------
// On regarde s'il y a dans l'arborescence un couple
// dont le p correspond à A_succ
// (variable générale renseignée à ce stade)
// On sait ici que l'arborescence n'est pas vide
bool TForm1::ajout10()
{
int i;

// Pour chaque ligne de l'arborescence SYR
for(i=0;i<SYR->Count;i++)
   {
   // on traite la ligne i pour y tester les couples présents
   traite(SYR->Strings[i]);

   // si l'on peut placer A_succ dans l'arborescence SYR
   if(nouveau_lien)
      {
      // mémorise le niveau où l'insertion doit se faire,
      // sachant que cette insertion se fait à la ligne suivante
      // de celle actuellement visée par i.
      // Si i pointe la dernière ligne de l'arborescence,
      // on met niveau à -1 pour indiquer
      // la création d'une ligne à la suite de l'arborescence
      // pour y ajouter le couple p-s,
      // sinon l'ajout se fera à la ligne suivante qui existe
      if(i==SYR->Count-1) niveau=-1; else niveau=i+1;

      // sortie de boucle avec vrai pour insérer
      // le couple p-s au bon endroit dans l'arborescence
      return true;
      }
   }

// renvoie faux car on ne peut pas placer A_succ
// en l'état actuel de l'arborescence
return false;
}
//---------------------------------------------------------------------------
// Insère le couple p-s dans l'arborescence
void TForm1::insert(int p, int s)
{
if(SYR->Count==0) insert10(p,s); else insert20(p,s);
}
//---------------------------------------------------------------------------
// ici l'arborescence est vide, on y écrit le premier couple p-s.
void TForm1::insert10(int p, int s)
{
SYR->Add((AnsiString)p+CA_tiret+s);
}
//---------------------------------------------------------------------------
// Ici on insère le couple p-s
void TForm1::insert20(int p, int s)
{
if(niveau==-1) insert10(p,s); else insert30(niveau,p,s);
}
//---------------------------------------------------------------------------
// insére le couple p-s à la ligne i de l'arborescence SYR
void TForm1::insert30(int i, int p, int s)
{
AnsiString A;

A=SYR->Strings[i];
A=A+CA_espace;
A=A+p;
A=A+CA_tiret;
A=A+s;
SYR->Strings[i]=A;
}
//---------------------------------------------------------------------------
// Affichage de l'arborescence et du couple p-s inséré
void TForm1::Aff_memo()
{
int i;
AnsiString A;

// Détails de l'ajout
if(SYR->Count==1)
   {
   A="Ajout n°1 : racine de l'arborescence";
   }
else
   {
   Memo1->Lines->Add(CA_separ);
   A=CA_ajout;
   A=A+(compteur+1);
   A=A+CA_lien;
   A=A+A_pred;
   A=A+CA_tiret;
   A=A+A_succ;
   }

// On distingue la création d'une ligne d'un ajout quelconque
if(niveau==-1)
   {
   A=A+" à la fin de l'arborescence";
   }
else
   {
   A=A+" au niveau ";
   A=A+(niveau);
   }
Memo1->Lines->Add(A);

// affiche l'état actuel de l'arborescence
for(i=0;i<SYR->Count;i++)
   {
   A="Niveau ";
   A=A+(i);
   A=A+" : ";
   if(i==0) A=A+"1"; else A=A+SYR->Strings[i];
   Memo1->Lines->Add(A);
   }
}
//---------------------------------------------------------------------------
// traite une ligne de l'arborescence,
// renseigne la variable booléenne "nouveau_lien"
// qui dira si un nouveau lien possible a été détecté
// à ce niveau-là
void TForm1::traite(AnsiString A)
{
// par défaut, pas de nouveau lien possible
nouveau_lien=false;

do
   {
   // renseigne la variable générale "couple"
   // ainsi que A_pred_syr et A_succ_pred
   // et diminue la chaîne B de ce couple
   // pour qu'elle devienne vide
   // et puisse faire stopper la boucle
   A=traite10(A);

   // si un lien est possible ici
   if(A_succ==A_pred_syr)
      {
      // on renseigne la variable générale booléenne qui le signale
      nouveau_lien=true;

      // A=vide pour forcer la fin de la boucle
      // car on a trouvé un lien à insérer à l'arborescence
      A=CA_nihil;
      }
   }
while(A!=CA_nihil);
}
//---------------------------------------------------------------------------
// cherche le premier couple de l'AnsiString envoyé
// et renvoie la chaîne diminuée de ce couple
AnsiString TForm1::traite10(AnsiString A)
{
// renseigne la variable générale couple
// et supprime le couple de la chaîne
// pour qu'elle soit traitée jusqu'à ce qu'elle soit vide
A=supp_coupl(A);

// traite la variable générale couple
// i.e. extrait A_pred_syr et A_succ_syr
traite_couple();

return A;
}
//---------------------------------------------------------------------------
// Renseigne la variable générale couple
// et renvoie la chaîne diminuée de ce couple
AnsiString TForm1::supp_coupl(AnsiString A)
{
int i;
char c;
AnsiString B;

// AnsiString indicé à partir de 1
i=1;

// Ajout d'un espace en fin de chaîne comme délimiteur
A=A+CA_espace;

// chaîne de caractères jusqu'à espace détecté
// contenant les deux nombres p et s du couple
do
   {
   c=A[i];
   A[i++]=Cc_espace;
   B=B+(AnsiString)c;
   }
while(c!=Cc_espace);

couple=B;
return Trim(A);
}
//---------------------------------------------------------------------------
// Extrait de la variable générale couple
// les deux variables générales A_pred_syr et A_succ_syr
void TForm1::traite_couple()
{
A_pred_syr=extrait_P(couple);
A_succ_syr=extrait_S(couple);
}
//---------------------------------------------------------------------------
// renvoie le premier nombre de la variable générale couple
AnsiString TForm1::extrait_P(AnsiString A)
{
int i;
char c;
bool b;
AnsiString B;

i=1;
do
   {
   c=A[i++];
   b=(c==Cc_tiret);
   if(!b) B=B+(AnsiString)c;
   }
while(!b);

return B;
}
//---------------------------------------------------------------------------
// renvoie le deuxième nombre de la variable générale couple
AnsiString TForm1::extrait_S(AnsiString A)
{
int i;
char c;
bool b;
AnsiString B;

// Ajout d'un espace en fin de chaîne comme délimiteur
A=A+CA_espace;

i=1;
do
   {
   c=A[i++];
   b=(c==Cc_tiret);
   }
while(!b);

do
   {
   c=A[i++];
   b=(c==Cc_espace);
   if(!b) B=B+(AnsiString)c;
   }
while(!b);

return B;
}
//---------------------------------------------------------------------------
// Renvoie vrai si le couple p-s est dans SYR, sinon renvoie faux
bool TForm1::existe_couple(int p, int s)
{
// si SYR est vide, le couple p-s ne s'y trouve pas
// sinon c'est existe_couple10 qui le dira
if(SYR->Count==0) return false; else return(existe_couple10(p,s));
}
//---------------------------------------------------------------------------
// Renvoie vrai si le couple p-s est déjà dans l'arborescence SYR,
// sinon renvoie faux
// SYR est non vide à ce stade
bool TForm1::existe_couple10(int p, int s)
{
int i;
AnsiString A;

// Tous les couples dans un seul AnsiString
for(i=0;i<SYR->Count;i++) A=A+SYR->Strings[i]+CA_espace;

do
   {
   // renseigne la variable générale couple
   // et supprime le couple de la chaîne A
   // pour pouvoir stopper la boucle
   A=supp_coupl(A);

   // traite la variable générale couple
   // i.e. extrait A_pred_syr et A_succ_syr
   traite_couple();

   // renvoie vrai si le couple est détecté
   // dans l'arborescence SYR
   if((p==A_pred_syr) && (s==A_succ_syr)) return true;
   }
while(A!=CA_nihil);

// renvoie faux car le couple n'est pas dans l'arborescence
return false;
}
//---------------------------------------------------------------------------
//------------------------   F I N   ----------------------------------------
//---------------------------------------------------------------------------