src/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;
 198
 199                 init();
 200
 201                 pere=mypere;
 202                 nuage=pere->nuage;
 203                 niveau=pere->niveau+1;
 204
 205                 etat=DTREE_COURANT;
 206
 207                 noeud_contenu=new vector<int>;
 208                 noeud_contenu->reserve((pere->noeud_contenu->size())/nbr_descendants);
 209
 210                 for (i=0;i<DIMENSION;i++)
 211                         {
 212                         coord_max[i]=(*nuage)[0][i];
 213                         coord_min[i]=(*nuage)[0][i];
 214                         }
 215
 216                 for (i=0;i<DIMENSION;i++)
 217                         {
 218                         if (A[i]>B[i])
 219                                 {
 220                                 coord_max[i]=A[i];
 221                                 coord_min[i]=B[i];
 222                                 }
 223                         else
 224                                 {
 225                                 coord_min[i]=A[i];
 226                                 coord_max[i]=B[i];
 227                                 }
 228                         }
 229                 }
 230         else
 231                 {
 232                 cerr<<"DTREE : Construction de descendance sans père !"<<endl;
 233                 exit(-1);
 234                 }
 235         }
 236 _TEMPLATE_ _DTREE_::dTree(const _DTREE_ &F)
 237         {
 238         // Pas Super Top Moumoute ... Recopie de pointeurs et pas de contenus, merdique
 239         int i,j;
 240         init();
 241         for (i=0;i<nbr_descendants;i++) descendant[i]=F.descendant[i];
 242         noeud_contenu=F.noeud_contenu;
 243         etat=F.etat;
 244         niveau=F.niveau;
 245         pere=F.pere;
 246         coord_max=F.coord_max;
 247         coord_min=F.coord_min;
 248         }
 249 _TEMPLATE_ _DTREE_::~dTree()
 250         {
 251         int i;
 252         nuage=NULL;
 253         pere=NULL;
 254         // cout<<*this<<endl;
 255         if (noeud_contenu)
 256                 {
 257                 delete noeud_contenu;
 258                 }
 259         for (i=0;i<nbr_descendants;i++) if (descendant[i])
 260                 {
 261                 delete descendant[i];
 262                 }
 263         }
 264 _TEMPLATE_ void _DTREE_::Get_Noeuds_Filtre(vector<int> &tmp)
 265         {
 266         int i;
 267         switch (etat)
 268                 {
 269                 case DTREE_RACINE : int pourlefunlecompilolesttropcon;
 270                 case DTREE_COURANT :
 271                         for (i=0;i<nbr_descendants;i++) descendant[i]->Get_Noeuds_Filtre(tmp);
 272                 case DTREE_TERMINAL :
 273                         if (noeud_contenu->size()>0)
 274                                 {
 275                                 for (i=0;i<NBR_NOEUDS_PAR_CASE;i++) tmp.push_back((*noeud_contenu)[i]);
 276                                 }
 277                 default :
 278                         cerr<<"DTREE : dTree Non Valide dans Rempli_Noeuds_Filtre"<<endl;
 279                         exit(-1);
 280                 }
 281         }
 282 _TEMPLATE_ Sommet_dTree<DIMENSION> _DTREE_::Get_Max() const
 283         {
 284         return coord_max;
 285         }
 286 _TEMPLATE_ Sommet_dTree<DIMENSION> _DTREE_::Get_Min() const
 287         {
 288         return coord_min;
 289         }
 290 _TEMPLATE_ int _DTREE_::is_in_dTree(NOEUD P) const
 291         {
 292         int test;
 293         for (int i=0;i<DIMENSION;i++)
 294                 {
 295                 test=((coord_min[i]<=P[i])&&(P[i]<=coord_max[i]));
 296                 if (!test) return 0;
 297                 }
 298         return 1;
 299
 300         }
 301 // calcule la distance Linf d'un point exterieur, si le point est interieur, le resultat sera erroné
 302 _TEMPLATE_ double _DTREE_::calcule_distance(NOEUD P) const
 303         {
 304         double min=fabs(coord_max[0]-P[0]);
 305         double tmp;
 306         int i;
 307         for (i=0;i<DIMENSION;i++)
 308                 {
 309                 tmp=fabs(coord_max[i]-P[i]);
 310                 if (min>tmp) min=tmp;
 311                 tmp=fabs(coord_min[i]-P[i]);
 312                 if (min>tmp) min=tmp;
 313                 }
 314         return min;
 315         }
 316 _TEMPLATE_ _DTREE_ & _DTREE_::operator = (const _DTREE_ & F)
 317         {
 318         // Pas Super Top Moumoute ... Recopie de pointeurs et pas de contenus, merdique
 319         int i,j;
 320         init();
 321         for (i=0;i<_DTREE_::nbr_descendans;i++) descendant[i]=F.descendant[i];
 322         noeud_contenu=F.noeud_contenu;
 323         etat=F.etat;
 324         niveau=F.niveau;
 325         pere=F.pere;
 326         coord_max=F.coord_max;
 327         coord_min=F.coord_min;
 328         }
 329 // selecteur doit etre lu comme un nombre en base 2
 330 // il specifie les coordonnes de reference du sommet dont on veut les coordonnees reelles
 331 // ex : en dim 3 : coord_min=0+0*2+0*4=0
 332 //                 coord_max=1+1*2*1*4=7
 333 // donc les unites pour x, les 2aines pour y, les 4aines pour z
 334 _TEMPLATE_ Sommet_dTree<DIMENSION> _DTREE_::donne_sommet(int selecteur) const
 335         {
 336         Sommet_dTree<DIMENSION> p;
 337         int i;
 338         int residu=selecteur;
 339         int reste;
 340         for (i=0;i<DIMENSION;i++)
 341                 {
 342                 reste=residu%2;
 343                 if (reste==0) p[i]=coord_min[i]; else p[i]=coord_max[i];
 344                 residu=(residu-reste)/2;
 345                 }
 346         return p;
 347         }
 348 _TEMPLATE_ int _DTREE_::a_des_fils() const
 349         {
 350         if ((etat==DTREE_COURANT)||(etat=DTREE_RACINE)) return 1;
 351         else return 0;
 352         }
 353 _TEMPLATE_ _DTREE_ * _DTREE_::trouve_dTree_contenant(NOEUD P) const
 354         {
 355         Sommet_dTree<DIMENSION> B(coord_min,coord_max);
 356         int i;
 357         if ((etat==DTREE_RACINE)&&(!is_in_dTree(P))) return NULL; // Le noeud est extérieur a l'dTree
 358         else if (etat==DTREE_TERMINAL) return (dTree *) this;     // Le noeud est dans *this qui est terminal
 359
 360         for (i=0;i<nbr_descendants;i++)
 361                 {
 362                 Sommet_dTree<DIMENSION> A=donne_sommet(i);
 363                 int test,j;
 364                 for (j=0;j<DIMENSION;j++)
 365                         {
 366                         if (A[j]<=B[j]) test=((A[j]<=P[j])&&(P[j]<=B[j]));
 367                         else test=((A[j]>=P[j])&&(P[j]>=B[j]));
 368                         if (!test) break;
 369                         }
 370
 371                 if (test)
 372                   return descendant[i]->trouve_dTree_contenant(P); // Propagation
 373                 }
 374         return NULL;
 375         }
 376 // si de le dTree n'est pas TERMINAL, scanne tous les points du nuage du pere pour trouver le point le plus proche
 377 // sinon scanne uniquement les points contenus dans le dTree
 378 _TEMPLATE_ int _DTREE_::trouve_plus_proche_point_bourrin(NOEUD P) const
 379         {
 380         int i;
 381         int num_sol=0;
 382         double min;
 383         double tmp;
 384         if (etat!=DTREE_TERMINAL)
 385                 {
 386                 min=DistanceL2(P,(*nuage)[0]);
 387                 for (i=1;i<nuage->size();i++)
 388                         {
 389                         tmp=DistanceL2(P,(*nuage)[i]);
 390                         if (tmp<min)
 391                                 {
 392                                 num_sol=i;
 393                                 min=tmp;
 394                                 }
 395                         }
 396                 return num_sol;
 397                 }
 398         else
 399                 {
 400                 if (noeud_contenu->size()!=0)
 401                         {
 402                         num_sol=(*noeud_contenu)[0];
 403                         min=DistanceL2(P,(*nuage)[num_sol]);
 404                         for (i=1;i<noeud_contenu->size();i++)
 405                                 {
 406                                 tmp=DistanceL2(P,(*nuage)[(*noeud_contenu)[i]]);
 407                                 if (tmp<min)
 408                                         {
 409                                         num_sol=(*noeud_contenu)[i];
 410                                         min=tmp;
 411                                         }
 412                                 }
 413                         return num_sol;
 414                         }
 415                 else return DTREE_FANTOME;
 416                 }
 417         }
 418 // Fonction de pilotage de la recursion, lance les tests preliminaires et invoque la recursion
 419 _TEMPLATE_ int _DTREE_::trouve_plus_proche_point(NOEUD P) const
 420         {
 421
 422         if (etat==DTREE_FANTOME)
 423                 {
 424                 cerr<<"DTREE : TROUVE PLUS PROCHE POINT : L'octree n'est pas construit !"<<endl;
 425                 exit(-1);
 426                 }
 427         dTree *ref=trouve_dTree_contenant(P);
 428         double delta;
 429
 430         if (ref!=NULL)
 431                 {
 432                 // Le point est intérieur
 433
 434                 if (ref->pere!=NULL)
 435                         {
 436                         delta=DistanceInf((ref->pere->coord_max),(ref->pere->coord_min));
 437                         }
 438                 else
 439                         {
 440                         cerr<<"DTREE : TROUVE PLUS PROCHE POINT : l'octree contenant le noeud n'a pas de pere !"<<endl;
 441                         exit(-1);
 442                         }
 443                 }
 444         else
 445                 {
 446                 // Le point est extérieur
 447
 448                 delta=DistanceL2(P,(*nuage)[0]);
 449                 }
 450
 451         int flag=0;
 452         int retour;
 453
 454         retour=tppp_rec(P,delta,flag);
 455
 456         return retour;
 457         }
 458 _TEMPLATE_ int _DTREE_::trouve_un_point() const
 459         {
 460         if (noeud_contenu!=NULL)
 461                 {
 462                 if (noeud_contenu->size()>0) return (*(noeud_contenu))[0];
 463                 }
 464         else
 465                 {
 466                 int i;
 467                 for (i=0;i<nbr_descendants;i++)
 468                         {
 469                         return descendant[i]->trouve_un_point();
 470                         }
 471                 }
 472         }
 473 // partie recursive de trouve_plus_proche_point
 474 // change le flag en 1 si un point plus proche est trouvé
 475 // adapte automatiquement la distance delta de filtrage
 476 _TEMPLATE_ int _DTREE_::tppp_rec(NOEUD P,double &delta,int &flag) const
 477         {
 478         if (Localise_Point(P,delta)==0)
 479                 {
 480
 481         // La distance du point à l'octree est plus grande que delta
 482
 483                 return DTREE_FANTOME;
 484                 }
 485         int num_Ptmp;
 486         double dtmp;
 487         if (etat==DTREE_TERMINAL)
 488                 {
 489                 if (noeud_contenu->size()>0)
 490                         {
 491                         num_Ptmp=trouve_plus_proche_point_bourrin(P);
 492                         dtmp=DistanceL2((*nuage)[num_Ptmp],P);
 493                         if (dtmp<=delta)
 494                                 {
 495
 496         // Le point le plus proche minimise delta, c'est un bon candidat, on l'envoie !
 497
 498                                 delta=dtmp;
 499                                 flag=1;
 500                                 return num_Ptmp;
 501                                 }
 502
 503         // Le point le plus proche ne minimise pas delta
 504
 505                         // ===========> peut etre rajouter exit(-1); ??????????
 506                         return DTREE_FANTOME;
 507                         }
 508                 else
 509                         {
 510
 511         // L'octree qui contient P ne contient aucun point
 512
 513                         return DTREE_FANTOME;
 514                         }
 515                 }
 516         int i;
 517         int num_sol=DTREE_FANTOME;
 518         for (i=0;i<nbr_descendants;i++)
 519                 {
 520                 num_Ptmp=descendant[i]->tppp_rec(P,delta,flag);
 521                 if ((num_Ptmp!=DTREE_FANTOME)&&(flag==1))
 522                         {
 523
 524         // On a trouvé un point qui minimise delta dans une branche
 525
 526                         num_sol=num_Ptmp;
 527                         }
 528                 }
 529         // A ce stade, on a trouvé un point qui minimise tous les deltas, c'est donc le point le plus proche
 530         // REMARQUE : cette affirmation est à la base de l'algorithme par dTree mais est loin d'étre évidente
 531
 532         return num_sol;
 533         }
 534
 535 // renvoie 1 si la distance L inf du noeud a l'octree est plus petite que d, 0 sinon
 536 _TEMPLATE_ int _DTREE_::Localise_Point(NOEUD P,double d) const
 537         {
 538         int i;
 539         for (i=0;i<DIMENSION;i++)
 540                 {
 541                 if (P[i]>coord_max[i]+d) return 0;
 542                 if (P[i]<coord_min[i]-d) return 0;
 543                 }
 544         return 1;
 545         }
 546
 547 // Méthode de construction du dTree par propagation
 548 _TEMPLATE_ void _DTREE_::cree_filiation()
 549         {
 550         if (etat!=DTREE_RACINE)
 551                 {
 552                 niveau=pere->niveau+1;
 553                 }
 554         else
 555                 {
 556                 niveau=0;
 557                 }
 558
 559         if (noeud_contenu->size()<=NBR_NOEUDS_PAR_CASE)
 560                 {
 561                 etat=DTREE_TERMINAL;
 562                 }
 563         else
 564                 {
 565                 int i,num_loc,test;
 566
 567                 Sommet_dTree<DIMENSION> centre(coord_max,coord_min);
 568
 569                 for (i=0;i<nbr_descendants;i++)
 570                         {
 571                         descendant[i]=new dTree(centre,donne_sommet(i),this);
 572                         }
 573
 574                 for (num_loc=0;num_loc<noeud_contenu->size();num_loc++)
 575                         {
 576                         int indice=(*noeud_contenu)[num_loc];
 577                         NOEUD & courant=(*nuage)[indice];
 578                         test=1;
 579                         for (i=0;(test)&&(i<nbr_descendants);i++)
 580                                 {
 581                                 if (descendant[i]->is_in_dTree(courant))
 582                                         {
 583                                         descendant[i]->noeud_contenu->push_back(indice);
 584                                         test=0;
 585                                         }
 586                                 }
 587                         }
 588
 589                 delete noeud_contenu;
 590                 noeud_contenu=NULL;
 591
 592                 for (i=0;i<nbr_descendants;i++) descendant[i]->cree_filiation();
 593                 }
 594         }
 595 _TEMPLATE_ int _DTREE_::Get_Nbr_Descendants_Non_Vides() const
 596         {
 597         int i;
 598         int ndnv=0;
 599         switch (etat)
 600                 {
 601                 case DTREE_RACINE : int pourlefunlecompilolesttropcon;
 602                 case DTREE_COURANT :
 603                         for (i=0;i<nbr_descendants;i++) ndnv+=descendant[i]->Get_Nbr_Descendants_Non_Vides();
 604                         return ndnv;
 605                 case DTREE_TERMINAL :
 606                         if (noeud_contenu->size()>0) return 1;
 607                         else return 0;
 608                 default :
 609                         cerr<<"dTree Non Valide dans Get_Nbr_Descendants_Non_Vides"<<endl;
 610                         return -1;
 611                 }
 612         }
 613 _TEMPLATE_ int _DTREE_::Get_Nbr_Descendants_Vides() const
 614         {
 615         int i;
 616         int ndnv=0;
 617         switch (etat)
 618                 {
 619                 case DTREE_RACINE : int pourlefunlecompilolesttropcon;
 620                 case DTREE_COURANT :
 621                         for (i=0;i<nbr_descendants;i++) ndnv+=descendant[i]->Get_Nbr_Descendants_Vides();
 622                         return ndnv;
 623                 case DTREE_TERMINAL :
 624                         if (noeud_contenu->size()==0) return 1;
 625                         else return 0;
 626                 default :
 627                         cerr<<"dTree Non Valide dans Get_Nbr_Descendants_Non_Vides"<<endl;
 628                         return -1;
 629                 }
 630         }
 631 _TEMPLATE_ int _DTREE_::Get_Profondeur_Max() const
 632         {
 633         int i;
 634         int prof=0;
 635         int tmp;
 636         switch (etat)
 637                 {
 638                 case DTREE_RACINE : int pourlefunlecompilolesttropcon;
 639                 case DTREE_COURANT :
 640                         for (i=0;i<nbr_descendants;i++)
 641                                 {
 642                                 tmp=descendant[i]->Get_Profondeur_Max();
 643                                 if (tmp>prof) prof=tmp;
 644                                 }
 645                         return prof;
 646                 case DTREE_TERMINAL : return niveau;
 647                 default :
 648                         cerr<<"dTree Non Valide dans Get_Nbr_Descendants_Non_Vides"<<endl;
 649                         return -1;
 650                 }
 651         }
 652
 653 #undef _TEMPLATE_
 654 #undef _DTREE_
 655
 656
 657 #endif