src/MEDMEM/INTERPOLATION/MEDMEM_dTree.hxx

   1 #ifndef MEDMEM_DTREE_HXX
   2 #define MEDMEM_DTREE_HXX
   3
   4 #include "MEDMEM_dTreeSommet.hxx"
   5
   6 #define DTREE_FANTOME -1
   7 #define DTREE_RACINE 0
   8 #define DTREE_TERMINAL 1
   9 #define DTREE_COURANT 2
  10 // etat_descendance
  11 #define DTREE_NON_CALCULE -1
  12 #define DTREE_AUCUNE 0
  13 #define DTREE_VALIDE 1
  14 // val min nbr noeud
  15 #define DTREE_NBR_MIN_NOEUDS 2
  16 #define DTREE_NBR_MAX_DESC 8
  17 // pour meilleu re lecture
  18 #define _TEMPLATE_ template <class NOEUD,class NUAGENOEUD,int DIMENSION,int NBR_NOEUDS_PAR_CASE>
  19 #define _DTREE_ dTree<NOEUD,NUAGENOEUD,DIMENSION,NBR_NOEUDS_PAR_CASE>
  20
  21 //////////////////////////////////////////////////////////////////
  22 ///                                                            ///
  23 ///                       DECLARATIONS                         ///
  24 ///                                                            ///
  25 //////////////////////////////////////////////////////////////////
  26
  27 /*********************************************************/
  28 /*                                                       */
  29 /*             Calcul Statique de Puissance              */
  30 /*                                                       */
  31 /*********************************************************/
  32
  33 // Permet de Calculer 2^n de façon statique
  34
  35 template < int DIMENSION > struct DeuxPuissance
  36         {
  37         enum { valeur = 2 * DeuxPuissance<DIMENSION-1>::valeur } ;
  38         };
  39
  40 template <> struct DeuxPuissance<0>
  41         {
  42         enum { valeur = 1  } ;
  43         };
  44
  45 /*********************************************************/
  46 /*                                                       */
  47 /*                         DTREE                         */
  48 /*                                                       */
  49 /*********************************************************/
  50
  51 // Construit un d-Tree sur un nuage de noeud et pour un noeud donné donne lequel des noeuds du nuage est le plus proche
  52
  53 // # Bugs connus :
  54 //      -  Problemes avec points sur les faces des hypercubes ?
  55 //      -  Plantage sauvage si le point est plus loin de l'hypercube père que le diametre Linf de celui-ci.
  56 // # Politique de classe :
  57 //      - NOEUD : voir dans MEDMEM_WrapperNodes.hxx la classe Wrapper_Noeud<..>
  58 //      - NUAGENOEUD : typiquement, c'est vector<NOEUD> en rédefinissant NUAGENOEUD<...>::SIZE()=vector<...>::size()
  59 // Remarques :
  60 //      - NBR_NOEUDS_PAR_CASE ne doit pas être modifié sauf peut-être dans le cas où l'utilisateur veut utiliser des d-Tree parallèles
  61 //        ou utilise des nuages de noeud trop grands
  62
  63 template <class NOEUD,class NUAGENOEUD,int DIMENSION,int NBR_NOEUDS_PAR_CASE=DTREE_NBR_MIN_NOEUDS> class dTree
  64 {
  65 protected :
  66         // types
  67         typedef _DTREE_ * Ptr_dTree;
  68         // Static Const
  69         static const int nbr_descendants=DeuxPuissance<DIMENSION>::valeur;
  70         // champs
  71         NUAGENOEUD * nuage;
  72         Ptr_dTree descendant[nbr_descendants];
  73         // numéro des noeuds contenus
  74         vector<int> * noeud_contenu;
  75         int etat;
  76         int niveau;
  77         dTree * pere;
  78         // extrémités de l'hypercube du dTree
  79         Sommet_dTree<DIMENSION> coord_max;
  80         Sommet_dTree<DIMENSION> coord_min;
  81 public :
  82
  83         void init();
  84         dTree();
  85         // Ce constructeur est le seul constructeur utilisateur, il construit le père puis tous les descendants
  86         dTree(NUAGENOEUD *n);
  87         // Ce Constructeur est utilisé par le précédent, pour un pere donné, avec deux extrémités données,
  88         // il instantie un dTree sans en calculer les noeuds contenus
  89         dTree(const Sommet_dTree<DIMENSION> &A,const Sommet_dTree<DIMENSION> &B,dTree *mypere);
  90         dTree(const dTree &F);
  91         ~dTree();
  92         // Renvoie les numéros de noeuds contenus dans le dTree
  93         void Get_Noeuds_Filtre(vector<int> &tmp);
  94         // renvoie les extrémités
  95         Sommet_dTree<DIMENSION> Get_Max() const;
  96         Sommet_dTree<DIMENSION> Get_Min() const;
  97         // renvoie vrai si P est dans le dTree
  98         int is_in_dTree(NOEUD P) const;
  99         // calcule la distance topologique locale de P au dTree
 100         double calcule_distance(NOEUD P) const;
 101         dTree & operator = (const dTree & F);
 102         // retourne le sommet du dTree codé par l'entier selecteur (voir explications dans le code)
 103         Sommet_dTree<DIMENSION> donne_sommet(int selecteur) const;
 104         int a_des_fils() const;
 105         // renvoi une reference sur le dTree terminal descendant de this contenant P
 106         dTree * trouve_dTree_contenant(NOEUD P) const;
 107         // renvoie le point le plus proche de P dans this par la méthode exhaustive brutale
 108         int trouve_plus_proche_point_bourrin(NOEUD P) const;
 109         // renvoie le point le plus proche de p dans this par la méthode dtree
 110         int trouve_plus_proche_point(NOEUD P) const;
 111         // renvoie un numéro de point contenu dans this
 112         int trouve_un_point() const;
 113         // méthode récursive utilisée par trouve_plus_proche_point
 114         int tppp_rec(NOEUD P,double &delta,int &flag) const;
 115         // dit si P est d-proche de l'hypercube de this
 116         int Localise_Point(NOEUD P,double d) const;
 117         // utilisé par le constructeur pour créer tout la filiation du dTree
 118         void cree_filiation();
 119         // méthodes de mesure
 120         int Get_Nbr_Descendants_Non_Vides() const;
 121         int Get_Nbr_Descendants_Vides() const;
 122         int Get_Profondeur_Max() const;
 123 };
 124
 125
 126 //////////////////////////////////////////////////////////////////
 127 ///                                                            ///
 128 ///                           CODE                             ///
 129 ///                                                            ///
 130 //////////////////////////////////////////////////////////////////
 131
 132 _TEMPLATE_ void _DTREE_::init()
 133         {
 134         int i;
 135         nuage=NULL;
 136         noeud_contenu=NULL;
 137         etat=DTREE_FANTOME;
 138         for (i=0;i<nbr_descendants;i++) descendant[i]=NULL;
 139         niveau=-1;
 140         pere=NULL;
 141         }
 142 _TEMPLATE_ _DTREE_::dTree()
 143         {
 144         init();
 145         coord_max=0.0;
 146         coord_min=0.0;
 147         }
 148 _TEMPLATE_ _DTREE_::dTree(NUAGENOEUD *n)
 149         {
 150         int i,j;
 151         double tmp;
 152
 153         if (n==NULL)
 154                 {
 155                 cerr<<"DTREE : Nuage vide !"<<endl;
 156                 exit(-1);
 157                 }
 158
 159         init();
 160         nuage=n;
 161         etat=DTREE_RACINE;
 162         noeud_contenu=new vector<int>(nuage->size());
 163         niveau=0;
 164
 165         // calcule les extrémités du dTree pere
 166         for (i=0;i<DIMENSION;i++)
 167                 {
 168                 coord_max[i]=(*nuage)[0][i];
 169                 coord_min[i]=(*nuage)[0][i];
 170                 }
 171         (*noeud_contenu)[0]=0;
 172         for (i=1;i<nuage->size();i++)
 173                 {
 174                 (*noeud_contenu)[i]=i;
 175                 for (j=0;j<DIMENSION;j++)
 176                         {
 177                         if ((*nuage)[i][j]>coord_max[j]) coord_max[j]=(*nuage)[i][j];
 178                         if ((*nuage)[i][j]<coord_min[j]) coord_min[j]=(*nuage)[i][j];
 179                         }
 180                 }
 181         for (j=0;j<DIMENSION;j++)
 182                 {
 183                 tmp=(coord_max[j]-coord_min[j])*0.01;
 184                 coord_max[j]+=tmp;
 185                 coord_min[j]-=tmp;
 186                 }
 187
 188         // méthode récursive qui construit la filiation
 189         cree_filiation();
 190
 191         }
 192 _TEMPLATE_ _DTREE_::dTree(const Sommet_dTree<DIMENSION> &A,const Sommet_dTree<DIMENSION> &B,dTree *mypere)
 193         {
 194         if (mypere!=NULL)
 195                 {
 196
 197                 int i,j;
 198                 double tmp;
 199
 200                 init();
 201
 202                 pere=mypere;
 203                 nuage=pere->nuage;
 204                 niveau=pere->niveau+1;
 205
 206                 etat=DTREE_COURANT;
 207
 208                 noeud_contenu=new vector<int>;
 209                 noeud_contenu->reserve((pere->noeud_contenu->size())/nbr_descendants);
 210
 211                 for (i=0;i<DIMENSION;i++)
 212                         {
 213                         coord_max[i]=(*nuage)[0][i];
 214                         coord_min[i]=(*nuage)[0][i];
 215                         }
 216
 217                 for (i=0;i<DIMENSION;i++)
 218                         {
 219                         if (A[i]>B[i])
 220                                 {
 221                                 coord_max[i]=A[i];
 222                                 coord_min[i]=B[i];
 223                                 }
 224                         else
 225                                 {
 226                                 coord_min[i]=A[i];
 227                                 coord_max[i]=B[i];
 228                                 }
 229                         }
 230                 }
 231         else
 232                 {
 233                 cerr<<"DTREE : Construction de descendance sans père !"<<endl;
 234                 exit(-1);
 235                 }
 236         }
 237 _TEMPLATE_ _DTREE_::dTree(const _DTREE_ &F)
 238         {
 239         // Pas Super Top Moumoute ... Recopie de pointeurs et pas de contenus, merdique
 240         int i,j;
 241         init();
 242         for (i=0;i<nbr_descendants;i++) descendant[i]=F.descendant[i];
 243         noeud_contenu=F.noeud_contenu;
 244         etat=F.etat;
 245         niveau=F.niveau;
 246         pere=F.pere;
 247         coord_max=F.coord_max;
 248         coord_min=F.coord_min;
 249         }
 250 _TEMPLATE_ _DTREE_::~dTree()
 251         {
 252         int i;
 253         nuage=NULL;
 254         pere=NULL;
 255         // cout<<*this<<endl;
 256         if (noeud_contenu)
 257                 {
 258                 delete noeud_contenu;
 259                 }
 260         for (i=0;i<nbr_descendants;i++) if (descendant[i])
 261                 {
 262                 delete descendant[i];
 263                 }
 264         }
 265 _TEMPLATE_ void _DTREE_::Get_Noeuds_Filtre(vector<int> &tmp)
 266         {
 267         int i;
 268         switch (etat)
 269                 {
 270                 case DTREE_RACINE : int pourlefunlecompilolesttropcon;
 271                 case DTREE_COURANT :
 272                         for (i=0;i<nbr_descendants;i++) descendant[i]->Get_Noeuds_Filtre(tmp);
 273                 case DTREE_TERMINAL :
 274                         if (noeud_contenu->size()>0)
 275                                 {
 276                                 for (i=0;i<NBR_NOEUDS_PAR_CASE;i++) tmp.push_back((*noeud_contenu)[i]);
 277                                 }
 278                 default :
 279                         cerr<<"DTREE : dTree Non Valide dans Rempli_Noeuds_Filtre"<<endl;
 280                         exit(-1);
 281                 }
 282         }
 283 _TEMPLATE_ Sommet_dTree<DIMENSION> _DTREE_::Get_Max() const
 284         {
 285         return coord_max;
 286         }
 287 _TEMPLATE_ Sommet_dTree<DIMENSION> _DTREE_::Get_Min() const
 288         {
 289         return coord_min;
 290         }
 291 _TEMPLATE_ int _DTREE_::is_in_dTree(NOEUD P) const
 292         {
 293         int test;
 294         for (int i=0;i<DIMENSION;i++)
 295                 {
 296                 test=((coord_min[i]<=P[i])&&(P[i]<=coord_max[i]));
 297                 if (!test) return 0;
 298                 }
 299         return 1;
 300
 301         }
 302 // calcule la distance Linf d'un point exterieur, si le point est interieur, le resultat sera erroné
 303 _TEMPLATE_ double _DTREE_::calcule_distance(NOEUD P) const
 304         {
 305         double min=fabs(coord_max[0]-P[0]);
 306         double tmp;
 307         int i;
 308         for (i=0;i<DIMENSION;i++)
 309                 {
 310                 tmp=fabs(coord_max[i]-P[i]);
 311                 if (min>tmp) min=tmp;
 312                 tmp=fabs(coord_min[i]-P[i]);
 313                 if (min>tmp) min=tmp;
 314                 }
 315         return min;
 316         }
 317 _TEMPLATE_ _DTREE_ & _DTREE_::operator = (const _DTREE_ & F)
 318         {
 319         // Pas Super Top Moumoute ... Recopie de pointeurs et pas de contenus, merdique
 320         int i,j;
 321         init();
 322         for (i=0;i<nbr_descendans;i++) descendant[i]=F.descendant[i];
 323         noeud_contenu=F.noeud_contenu;
 324         etat=F.etat;
 325         niveau=F.niveau;
 326         pere=F.pere;
 327         coord_max=F.coord_max;
 328         coord_min=F.coord_min;
 329         }
 330 // selecteur doit etre lu comme un nombre en base 2
 331 // il specifie les coordonnes de reference du sommet dont on veut les coordonnees reelles
 332 // ex : en dim 3 : coord_min=0+0*2+0*4=0
 333 //                 coord_max=1+1*2*1*4=7
 334 // donc les unites pour x, les 2aines pour y, les 4aines pour z
 335 _TEMPLATE_ Sommet_dTree<DIMENSION> _DTREE_::donne_sommet(int selecteur) const
 336         {
 337         Sommet_dTree<DIMENSION> p;
 338         int i;
 339         int residu=selecteur;
 340         int reste;
 341         for (i=0;i<DIMENSION;i++)
 342                 {
 343                 reste=residu%2;
 344                 if (reste==0) p[i]=coord_min[i]; else p[i]=coord_max[i];
 345                 residu=(residu-reste)/2;
 346                 }
 347         return p;
 348         }
 349 _TEMPLATE_ int _DTREE_::a_des_fils() const
 350         {
 351         if ((etat==DTREE_COURANT)||(etat=DTREE_RACINE)) return 1;
 352         else return 0;
 353         }
 354 _TEMPLATE_ _DTREE_ * _DTREE_::trouve_dTree_contenant(NOEUD P) const
 355         {
 356         Sommet_dTree<DIMENSION> B(coord_min,coord_max);
 357         int i;
 358         if ((etat==DTREE_RACINE)&&(!is_in_dTree(P))) return NULL; // Le noeud est extérieur a l'dTree
 359         else if (etat==DTREE_TERMINAL) return (dTree *) this;     // Le noeud est dans *this qui est terminal
 360
 361         for (i=0;i<nbr_descendants;i++)
 362                 {
 363                 Sommet_dTree<DIMENSION> A=donne_sommet(i);
 364                 int test,j;
 365                 for (j=0;j<DIMENSION;j++)
 366                         {
 367                         if (A[j]<=B[j]) test=((A[j]<=P[j])&&(P[j]<=B[j]));
 368                         else test=((A[j]>=P[j])&&(P[j]>=B[j]));
 369                         if (!test) break;
 370                         }
 371
 372                 if (test) return descendant[i]->trouve_dTree_contenant(P); // Propagation
 373                 }
 374         }
 375 // si de le dTree n'est pas TERMINAL, scanne tous les points du nuage du pere pour trouver le point le plus proche
 376 // sinon scanne uniquement les points contenus dans le dTree
 377 _TEMPLATE_ int _DTREE_::trouve_plus_proche_point_bourrin(NOEUD P) const
 378         {
 379         int i;
 380         int num_sol=0;
 381         double min;
 382         double tmp;
 383         if (etat!=DTREE_TERMINAL)
 384                 {
 385                 min=DistanceL2(P,(*nuage)[0]);
 386                 for (i=1;i<nuage->size();i++)
 387                         {
 388                         tmp=DistanceL2(P,(*nuage)[i]);
 389                         if (tmp<min)
 390                                 {
 391                                 num_sol=i;
 392                                 min=tmp;
 393                                 }
 394                         }
 395                 return num_sol;
 396                 }
 397         else
 398                 {
 399                 if (noeud_contenu->size()!=0)
 400                         {
 401                         num_sol=(*noeud_contenu)[0];
 402                         min=DistanceL2(P,(*nuage)[num_sol]);
 403                         for (i=1;i<noeud_contenu->size();i++)
 404                                 {
 405                                 tmp=DistanceL2(P,(*nuage)[(*noeud_contenu)[i]]);
 406                                 if (tmp<min)
 407                                         {
 408                                         num_sol=(*noeud_contenu)[i];
 409                                         min=tmp;
 410                                         }
 411                                 }
 412                         return num_sol;
 413                         }
 414                 else return DTREE_FANTOME;
 415                 }
 416         }
 417 // Fonction de pilotage de la recursion, lance les tests preliminaires et invoque la recursion
 418 _TEMPLATE_ int _DTREE_::trouve_plus_proche_point(NOEUD P) const
 419         {
 420
 421         if (etat==DTREE_FANTOME)
 422                 {
 423                 cerr<<"DTREE : TROUVE PLUS PROCHE POINT : L'octree n'est pas construit !"<<endl;
 424                 exit(-1);
 425                 }
 426         dTree *ref=trouve_dTree_contenant(P);
 427         double delta;
 428
 429         if (ref!=NULL)
 430                 {
 431                 // Le point est intérieur
 432
 433                 if (ref->pere!=NULL)
 434                         {
 435                         delta=DistanceInf((ref->pere->coord_max),(ref->pere->coord_min));
 436                         }
 437                 else
 438                         {
 439                         cerr<<"DTREE : TROUVE PLUS PROCHE POINT : l'octree contenant le noeud n'a pas de pere !"<<endl;
 440                         exit(-1);
 441                         }
 442                 }
 443         else
 444                 {
 445                 // Le point est extérieur
 446
 447                 delta=DistanceL2(P,(*nuage)[0]);
 448                 }
 449
 450         int flag=0;
 451         int retour;
 452
 453         retour=tppp_rec(P,delta,flag);
 454
 455         return retour;
 456         }
 457 _TEMPLATE_ int _DTREE_::trouve_un_point() const
 458         {
 459         if (noeud_contenu!=NULL)
 460                 {
 461                 if (noeud_contenu->size()>0) return (*(noeud_contenu))[0];
 462                 }
 463         else
 464                 {
 465                 int i;
 466                 for (i=0;i<nbr_descendants;i++)
 467                         {
 468                         return descendant[i]->trouve_un_point();
 469                         }
 470                 }
 471         }
 472 // partie recursive de trouve_plus_proche_point
 473 // change le flag en 1 si un point plus proche est trouvé
 474 // adapte automatiquement la distance delta de filtrage
 475 _TEMPLATE_ int _DTREE_::tppp_rec(NOEUD P,double &delta,int &flag) const
 476         {
 477         if (Localise_Point(P,delta)==0)
 478                 {
 479
 480         // La distance du point à l'octree est plus grande que delta
 481
 482                 return DTREE_FANTOME;
 483                 }
 484         int num_Ptmp;
 485         double dtmp;
 486         if (etat==DTREE_TERMINAL)
 487                 {
 488                 if (noeud_contenu->size()>0)
 489                         {
 490                         num_Ptmp=trouve_plus_proche_point_bourrin(P);
 491                         dtmp=DistanceL2((*nuage)[num_Ptmp],P);
 492                         if (dtmp<=delta)
 493                                 {
 494
 495         // Le point le plus proche minimise delta, c'est un bon candidat, on l'envoie !
 496
 497                                 delta=dtmp;
 498                                 flag=1;
 499                                 return num_Ptmp;
 500                                 }
 501
 502         // Le point le plus proche ne minimise pas delta
 503
 504                         // ===========> peut etre rajouter exit(-1); ??????????
 505                         return DTREE_FANTOME;
 506                         }
 507                 else
 508                         {
 509
 510         // L'octree qui contient P ne contient aucun point
 511
 512                         return DTREE_FANTOME;
 513                         }
 514                 }
 515         int i;
 516         int num_sol=DTREE_FANTOME;
 517         for (i=0;i<nbr_descendants;i++)
 518                 {
 519                 num_Ptmp=descendant[i]->tppp_rec(P,delta,flag);
 520                 if ((num_Ptmp!=DTREE_FANTOME)&&(flag==1))
 521                         {
 522
 523         // On a trouvé un point qui minimise delta dans une branche
 524
 525                         num_sol=num_Ptmp;
 526                         }
 527                 }
 528         // A ce stade, on a trouvé un point qui minimise tous les deltas, c'est donc le point le plus proche
 529         // REMARQUE : cette affirmation est à la base de l'algorithme par dTree mais est loin d'étre évidente
 530
 531         return num_sol;
 532         }
 533
 534 // renvoie 1 si la distance L inf du noeud a l'octree est plus petite que d, 0 sinon
 535 _TEMPLATE_ int _DTREE_::Localise_Point(NOEUD P,double d) const
 536         {
 537         int i;
 538         for (i=0;i<DIMENSION;i++)
 539                 {
 540                 if (P[i]>coord_max[i]+d) return 0;
 541                 if (P[i]<coord_min[i]-d) return 0;
 542                 }
 543         return 1;
 544         }
 545
 546 // Méthode de construction du dTree par propagation
 547 _TEMPLATE_ void _DTREE_::cree_filiation()
 548         {
 549         if (etat!=DTREE_RACINE)
 550                 {
 551                 niveau=pere->niveau+1;
 552                 }
 553         else
 554                 {
 555                 niveau=0;
 556                 }
 557
 558         if (noeud_contenu->size()<=NBR_NOEUDS_PAR_CASE)
 559                 {
 560                 etat=DTREE_TERMINAL;
 561                 }
 562         else
 563                 {
 564                 int i,num_loc,test;
 565
 566                 Sommet_dTree<DIMENSION> centre(coord_max,coord_min);
 567
 568                 for (i=0;i<nbr_descendants;i++)
 569                         {
 570                         descendant[i]=new dTree(centre,donne_sommet(i),this);
 571                         }
 572
 573                 for (num_loc=0;num_loc<noeud_contenu->size();num_loc++)
 574                         {
 575                         int indice=(*noeud_contenu)[num_loc];
 576                         NOEUD & courant=(*nuage)[indice];
 577                         test=1;
 578                         for (i=0;(test)&&(i<nbr_descendants);i++)
 579                                 {
 580                                 if (descendant[i]->is_in_dTree(courant))
 581                                         {
 582                                         descendant[i]->noeud_contenu->push_back(indice);
 583                                         test=0;
 584                                         }
 585                                 }
 586                         }
 587
 588                 delete noeud_contenu;
 589                 noeud_contenu=NULL;
 590
 591                 for (i=0;i<nbr_descendants;i++) descendant[i]->cree_filiation();
 592                 }
 593         }
 594 _TEMPLATE_ int _DTREE_::Get_Nbr_Descendants_Non_Vides() const
 595         {
 596         int i;
 597         int ndnv=0;
 598         switch (etat)
 599                 {
 600                 case DTREE_RACINE : int pourlefunlecompilolesttropcon;
 601                 case DTREE_COURANT :
 602                         for (i=0;i<nbr_descendants;i++) ndnv+=descendant[i]->Get_Nbr_Descendants_Non_Vides();
 603                         return ndnv;
 604                 case DTREE_TERMINAL :
 605                         if (noeud_contenu->size()>0) return 1;
 606                         else return 0;
 607                 default :
 608                         cerr<<"dTree Non Valide dans Get_Nbr_Descendants_Non_Vides"<<endl;
 609                         return -1;
 610                 }
 611         }
 612 _TEMPLATE_ int _DTREE_::Get_Nbr_Descendants_Vides() const
 613         {
 614         int i;
 615         int ndnv=0;
 616         switch (etat)
 617                 {
 618                 case DTREE_RACINE : int pourlefunlecompilolesttropcon;
 619                 case DTREE_COURANT :
 620                         for (i=0;i<nbr_descendants;i++) ndnv+=descendant[i]->Get_Nbr_Descendants_Vides();
 621                         return ndnv;
 622                 case DTREE_TERMINAL :
 623                         if (noeud_contenu->size()==0) return 1;
 624                         else return 0;
 625                 default :
 626                         cerr<<"dTree Non Valide dans Get_Nbr_Descendants_Non_Vides"<<endl;
 627                         return -1;
 628                 }
 629         }
 630 _TEMPLATE_ int _DTREE_::Get_Profondeur_Max() const
 631         {
 632         int i;
 633         int prof=0;
 634         int tmp;
 635         switch (etat)
 636                 {
 637                 case DTREE_RACINE : int pourlefunlecompilolesttropcon;
 638                 case DTREE_COURANT :
 639                         for (i=0;i<nbr_descendants;i++)
 640                                 {
 641                                 tmp=descendant[i]->Get_Profondeur_Max();
 642                                 if (tmp>prof) prof=tmp;
 643                                 }
 644                         return prof;
 645                 case DTREE_TERMINAL : return niveau;
 646                 default :
 647                         cerr<<"dTree Non Valide dans Get_Nbr_Descendants_Non_Vides"<<endl;
 648                         return -1;
 649                 }
 650         }
 651
 652 #undef _TEMPLATE_
 653 #undef _DTREE_
 654
 655
 656 #endif