Newsgroup: it.comp.lang.c++
Titolo: Classe Tree: dove la trovo ?

Ho letto la documentazione della STL ma non ho trovato alcun riferimento ad
una classe di tipo Tree che vorrei usare per implementare un albero non
binario di elementi..forse non esiste e me la devo fare io da zero ?
Nella dir usr/include ho trovato un tree.h che include un stl_tree.h, in
questo header c'e' una nota all' inizio che dice di non usarlo
direttamente..
Mi date un suggerimento ? Credevo che avrei trovato qualcosa di gia' pronto
come per le classi list e vector per esempio..
--
Visita la mia pagina personale:
 
http://members.xoom.it/Ake
*** grafica - ingegneria - midi - humour ***
****  abandonware - emulatori - MUD ****
 ***             DragonBall / Z                ****
Il Covo di Ake ora e' anche senza fili,
visitalo con il tuo cellulare WAP a:
 
tagtag.com/ake
Le Sabbie del Tempo scorrono ancora!
Vieni a giocare su:
  telnet://
sabbie.dhs.org:4000
Sito ufficiale: 
http://sabbie.dhs.org

 come per le classi list e vector per esempio..
List e vector sono previste dallo standard e fanno parte del linguaggio.
Gli alberi no. Nota che quasi (ripeto quasi) tutto quello che puoi fare
con una operazione freestanding di un albero binario bilanciato lo puoi
fare anche usando gli associative container.
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

Dunque, escludendo che io mi metta a fare una classe Tree da zero (dubito
che ne sarei in grado, magari potrei scopiazzare quella che c'e' nel
Thinking in C++), e volendo utilizzare le classi standard, dovrei fare
ricorso a list o vector...ma non capisco come, dato che per simulare un tree
dovrei creare un grafo mentre list e vector mi permettono di collezionare
oggetti in modo lineare...sbaglio ?
Andrea Ferro <And...@UrkaDVD.it> wrote in message
VsoZ7.53$l34....@nreader3.kpnqwest.net...


 oggetti in modo lineare...sbaglio ?
Dovrestio pre prima cosa imparare a quotare.
Poi se vuoi un consiglio dovresti cercare di dirci cosa vuoi fare.
Ovvero: perchè pensi che ti serva un tree? Quale è il problema che devi
effettivamente risolvere?



Voglio descrivere una collezione di oggetti che da un punto di vista logico
e' strutturata ad albero, per questo volevo il Tree.
Si tratta delle abilita' che il personaggio di un gioco puo' imparare: ci
sara' un' abilita' fondamentale che fara' da nodo root e che permettera' di
apprendere altre abilita' piu' specialistiche, le quali a loro volta si
ramificheranno ulteriormente per permettere l' apprendimento di altre ancora
piu' specialistiche etc..
Mentre scrivo questo pero' mi sto rendendo conto che in realta' di Tree ce
ne dovra' essere piu' di uno (le abilita' fondamentali saranno certamente
piu' di una) e dovranno essere collegati tra loro, forse allora mi serve
qualche classe diversa...


come per le classi list e vector per esempio..
Io ho scritto un po' di tempo fa una template Tree (alberi
n-ari) e un template Graph (grafi orientati). Sono abbastanza
rozzi... comunque se ti interessano mandami una mail e ti
invio i sorgenti. Un esempio di uso del tree e' il seguente...
#include <stdio.h>
#include "tree.h"
void PrintTree(int level,TreeIterator<char *> n)
{
  if (n)
  {
    printf("%*s%s\n",level*2,"",n());
    for (n=n.first(); n; n=n.next())
    {
      PrintTree(level+1,n);
    }
  }
}
int main()
{
  Tree<char *> t;
  typedef TreeIterator<char *> TI;
  TI imelde = t.addNode("Imelde");
   TI marta  = t.addNode("Marta",imelde);
    TI giorgio = t.addNode("Giorgio",marta);
    TI andrea  = t.addNode("Andrea",marta);
    TI alfonso = t.addNode("Alfonso",marta);
   TI gerry  = t.addNode("Gerry",imelde);
    TI paolo   = t.addNode("Paolo",gerry);
     TI filippo = t.addNode("Filippo",paolo);
    TI wilma   = t.addNode("Wilma",gerry);
   TI nina   = t.addNode("Nina",imelde);
    TI lorenzo = t.addNode("Lorenzo",nina);
     TI cesare = t.addNode("Cesare",lorenzo);
     TI enrico = t.addNode("Enrico",lorenzo);
    TI lorena  = t.addNode("Lorena",nina);
     TI sergio2 = t.addNode("Sergio",lorena);
     TI alfonsa = t.addNode("Alfonsa",lorena);
      TI chiara = t.addNode("Chiara",alfonsa);
   TI sergio = t.addNode("Sergio",imelde);
    TI mariangela = t.addNode("Mariangela",sergio);
     TI ilaria = t.addNode("Ilaria",mariangela);
    TI liviana    = t.addNode("Liviana",sergio);
     TI mauro = t.addNode("Mauro",liviana);
     TI fabio = t.addNode("Fabio",liviana);
   TI laura  = t.addNode("Laura",imelde);
  PrintTree(0,t.root());
 
  return 0;
}
Andrea

 qualche classe diversa...
Se non ho capito male, le operazioni che farai non hanno a che vedere
con la struttura ad albero ma piuttosto con il fatto che per attivare un
certo oggetto bisogna prima aver attivato tutto gli oggetti che ne sono
dei presupposti.
Quindi quello che ti serve è modellare la relazione bidirezionale
many-to-many fra gli oggetti che potresti chiamare RelazionePrerequisito
dato che gli archi hanno la logica (bidirezionale come detto)
"prerequisiti/prerequisitoPer".
Lo puoi fare in vari modi. Sia gestendo un oggetto separato che mantiene
i due riferimenti agli oggetti legati dalla relazione, sia inserendo in
ciascun oggetto un riferimento all'altro (per esempio sotto forma di due
std::set).
Esempio di questo secondo caso (non testato):
class MioOggetto {
    typedef std::set<MioOggetto*> Relazione;
    Relazione prerequisiti, prerequisitoPer;
    void rimuoviDaPrerequisiti(MioOggetto*p)
    {
        p->prerequisiti.erase(this);
    }
    void rimuoviDaPrerequisitoPer(MioOggetto*p)
    {
        p->prerequisitoPer.erase(this);
    }
public:
    ....
    void rendiPrerequsitoPer( MioOggetto*p )
    {
        prerequisitoPer.insert(p);
        p->prerequisiti.insert(this),
    }
    ....
    // ritorna vero se l'oggetto è attivo
    bool attivato() const;
    ....
    bool prerequisitiSoddisfatti() const
    {
        return std::find_if( prerequisiti.begin(),
                             prerequisiti.end(),
                             std::mem_fun(&MioOggetto::attivato) )
                == prerequisiti.end();
    }
    ...
    virtual ~MioOggetto()
    {
        std::for_each( prerequisitoPer.begin(),
                       prerequisitoPer.end(),
                       std::bind1st(
std::mem_fun(&MioOggetto::rimuoviDaPrerequisiti),
                           this ) );
        std::for_each( prerequisiti.begin(),
                       prerequisiti.end(),
                       std::bind1st(
std::mem_fun(&MioOggetto::rimuoviDaPrerequisitoPer),
                           this ) );
    }
};


Grazie, non ci ho capito niente di primo acchito, ma e' gia' un buono spunto
per cominciare !!
Vado a meditarci sopra..
Andrea Ferro <And...@UrkaDVD.it> wrote in message
iVo_7.59$_Z....@nreader1.kpnqwest.net...
