PDA

Visualizza la versione completa : [C++] Creazione iterator per grafo


giuseppe500
23-03-2011, 16:45
ciao.
Vorrei realizzare e possibilmente riutilizzare un iterator per grafi.
mi spiego meglio:
invece che enumerare tutti i nodi in una funzione ricorsiva vorrei chiamare il metodo next() ad es per passare al nodo successivo e farmi restituire il corrente e cosi via fino alla fine dei nodi.
ho cercato un po su google ma non ho trovato per questo chiedo qui.

mi serve per copiare e eseguire delle funzioni di caricamento in base ai nodi restituiti.
infatti i nodi restituiti possono essere di diverso tipo ma tutti derivati da una classe base ad es

se ho

next()
getNodeCurrent() : N1 type lightNode

importero la luce , quindi
getLightsFrom(N1)

altrimenti :
next()
getNodeCurrent() : N2 type geometryNode
getGeometryFrom(N2).

fino a creare delle funzioni virtuali nella classe base che fanno il lavoro relativo in base al tipo di nodo che sono.
grazie.

shodan
23-03-2011, 18:06
Le definizioni delle classi come sono?

giuseppe500
25-03-2011, 15:15
scusa shodan ma mi ero dimenticato di questo post , adesso le classi non riesco a postartele perchè sono al lavoro, ma devo generare un grafo di nodi CNodeImporter(classe di un composite) da una gerarchia di istanze di classi IskProvider(una classe composite anch' essa).

Mi sono trovato molto in difficoltà su questo punto:
1)non riesco a capire come fare il debug dell' algoritmo che fa l'attraversamento delle istanze IskProvider(che chiaramente possono avere uno o piu figli IskProvider sempre di tipo IskProvider o non hanno nessun figlio )


io ho strutturato in questo modo a memoria:



void Traverse(CNodeimporter ParentNode, IskProvider)
{
//con figli
for(IskProvider prov in Iskprovider.children)//pseudo code
{
CNodeImporter ChildNode = new CNodeImporter(prov)//carica alcune caratteristiche da //prov
ParentNode.insert(ChildNode);
parentNode = ChildNode;
Traverse(parentNode,prov);//
}

if(IskProvider!= NULL && IskProvider.children.Lenght == 0)//l'istanza IskProvider non ha figli
{
CNodeImporter ChildNode = new CNodeImporter(prov)//carica caratteristiche
ParentNode.insert(ChildNode);
parentNode = ChildNode;
}
}
}


ma sono ancora lontano dalla soluzione.
soprattutto non capisco come debuggare il tutto, e come le variabili di una chiamata cambino , penso , dico penso che tutte le variabili di una chiamata vengano "salvate" nello stack , ma come ritornano (automaticamente) e in che ordine?
è soprattutto l'ordine che non riesco a capire , come si srotola il tutto quando ho finito le chiamate ricorsive?

scusa l'ignoranza ma è una delle prime volte che affronto l'argomento e vorrei capire.

grazie.
ciao

giuseppe500
25-03-2011, 21:24
void CSketchupReader::SceneNodeReset(CNodeImporter* pNode, ISkpEntityProvider* pEntityProvider, bool bInit)
{
vector<ISkpEntityProvider*>* pProvChild = new vector<ISkpEntityProvider*>();

if(bInit){

HRESULT hr = m_doc->QueryInterface(&pEntityProvider);
long nElem = 0;
CComPtr<ISkpComponentInstances> pInstances = NULL;
pEntityProvider->get_ComponentInstances(&pInstances);

pInstances->get_Count(&nElem);

for(int i = 0; i < nElem; i++){

CComPtr<ISkpComponentInstance> pInstance = NULL;
hr = pInstances->get_Item(i, &pInstance.p);

CComPtr<ISkpComponentDefinition> pDef;
pInstance->get_ComponentDefinition(&pDef);

ISkpEntityProvider * pProvider = NULL;
pDef->QueryInterface(__uuidof(ISkpEntityProvider), (void**) &pProvider);

CNodeImporter* pNodeChild = GetChildNodeImporter(pEntityProvider,i);

pProvChild->push_back(pEntityProvider);

}
}
if(!bInit){
pProvChild = GetChildNodes(pEntityProvider);
}

for ( int i = 0; i < pProvChild->size(); i++)
{
pEntityProvider = (*pProvChild)[i];
if(GetChildNodes(pEntityProvider)->empty()){
CNodeImporter* pNodeChild = GetChildNodeImporter(pEntityProvider,i);
pNode->Insert(pNodeChild);

}
else{
CNodeImporter* pNodeChild = GetChildNodeImporter((*pProvChild)[i],i);
pNode->Insert(pNodeChild);
pNode = pNodeChild;
SceneNodeReset(pNode, (*pProvChild)[i], false); // ----->>>problema

}
}
}



questa è la funzione incriminata.
il problema è col parametro pNode che deve sempre essere il padre del nodo che andro' ad aggiungere , in modo da formare un albero uguale a quello delle istanze.
ho il seguente semplice albero:


->nodo1 ->nodo2
->nodo3

all'inizio è corretto , entro in questa funzione:


else{
CNodeImporter* pNodeChild = GetChildNodeImporter((*pProvChild)[i],i);
pNode->Insert(pNodeChild);
pNode = pNodeChild;
SceneNodeReset(pNode, (*pProvChild)[i], false); // ----->>>problema

}


perchè ho un nodo con figli ,
poi passa qui erchè nodo2 non ha figli :


if(GetChildNodes(pEntityProvider)->empty()){
CNodeImporter* pNodeChild = GetChildNodeImporter(pEntityProvider,i);
pNode->Insert(pNodeChild);

}

e aggiunge correttamente a nodo1 nodo2 , poi pero' sbaglio , perchè in questa chiamata a funzione:


SceneNodeReset(pNode, (*pProvChild)[i], false);
|->pnode era pnode1 e ritorna pnode1



solo che dovrei aggiungerlo alla root node3 mentre va a finire che lo aggiungo a node1.
ho provato e riprovato una soluzione ma non ci salto fuori.
ciao.

shodan
25-03-2011, 23:49
Ma non è che il problema dipenda da quel: pProvChild?
Perché ogni volta che inizia una ricorsione viene ricreato da zero e oltre ad avere un memory leak (non lo deallochi mai), perdi i dati che immagino vorresti passare a ogni chiamata.

Loading