Conversione da lista ad albero

[daniele_dll]

Hola a tutti,

volevo sentire qualche parere e qualche modalità di sviluppo di qualche altro programmatore, giusto per farmi un idea

Cosa intendo dire? voi come fate per trasformare le liste in alberi? Liste che hanno SOLO il riferimento al parent (niente sistemi circolari)?

Non mi interessano i sistemi ricorsivi, quindi non li postate

Detto questo, vi illustro la mia modalità di sviluppo in queste situazioni:
- Leggi gli elementi dalla sorgente dati (database, file di testo, webservice e cosi via)
- Mi costruisco una hashtable (un array con chiavi non numeriche in php) contenente un oggetto con due proprietà ovvero Element, che si riferisce all'elemento della lista, e Children, che si riferisce all'elenco dei figli, ed infine come chiave dell'hashtable utilizzo l'id dell'elemento (ID come chiave di identificazione univoca che di solito corrisponde al ID del db ma ovviamente se la sorgente è un altra va bene qualsiasi altro riferimento, basta che sia usato pure nel parent)
- Dopo aver effettuato questo primo ciclo, ne effettuo un secondo che non fa altro che inserire tutti gli elementi che non hanno parent corrisponde a zero nell'elemento Children del parent, operazione effettuata per riferimento
- Fatto questo effettuo un terzo ciclo che mi elimina tutti gli elementi che non hanno parent zero dall'elenco principale

In questo modo tiro fuori la struttura ad albero dalla semplice lista che si limita ad elencare 3 volte l'intero array però sono operazioni abbastanza semplici

Or dunque, qualche suggerimento o consiglio?

[daniele_dll]

uppete

[MicheleWT]

perchè non ti interessano i sistemi ricorsivi?

[daniele_dll]

Originariamente inviato da MicheleWT
perchè non ti interessano i sistemi ricorsivi?

perché sono CONSIDEREVOLMENTE soggetti a consumi estremi (sia di processore sia di memoria) e sono soggetti a problemi chiamati STACK OVERFLOW quando quando ci sono troppe chiamate ricorsive

http://it.wikipedia.org/wiki/Algoritmo_ricorsivo

[dottwatson]

spero di aver capito la tua esigenza

questa è una funzione che utilizzo per legger eil contenuto di una directory per tuttal la sua profondità... non utilizza nessuna ricorsione

spero ti possa dare un buono spunto

function list_elements($dir,$out) 
  {
  $file_list = '';
  $stack[] = $dir;
  while ($stack) 
    {
    $current_dir = array_pop($stack);
    if ($dh = opendir($current_dir)) 
      {
      while (($file = readdir($dh)) !== false) 
        {
        if ($file !== '.' && $file !== '..') 
          {
          $current_file = "{$current_dir}/{$file}";
          if (is_file($current_file)) 
            {
            $file_list[] = "{$current_dir}/{$file}";
            } 
          elseif (is_dir($current_file)) 
            {
            $stack[] = $current_file;
            $dirs[]=$current_file; //l' array delle directory
            }
          }
        }
      }
    }
  if ($out=='file') return $file_list;
  if ($out=='dir')  return $dirs;
  } 

[daniele_dll]

ok quello che fai tu direi che è per convertire un albero in una lista

Che è quello che fò pure io dopo essermi costruito l'albero

    public function BuildTree($Categories)
    {
        // Inizializza l'albero
        $categoryTree = array();
        
        // Come prima cosa inserisce tutte le categorie nella struttura che conterrà
        // l'albero senza però associarli
        while(list($key, $value) = each($Categories))
        {
            // Inzializza il nodo dell'albero
            $categoryNode = new stdClass();
            $categoryNode->Element = $value;
            $categoryNode->Children = array();

            // Aggiunge il nodo all'albero
            $categoryTree[$key] = $categoryNode;
        }

        // Resetta le categorie
        reset($Categories);

questo primo while si occupa di prendere un elenco di categorie già estratte dal database (poi questo metodo lo rinomino in InternalBuildTree e ne creo un secondo al quale se non vien passato nulla effettua lui l'estrazione dei dati e salta la prima fase in modo da mantenere la flessibilità e in modo da potermi muovere come mi serve senza perderci)

Siccome lavoro con gli oggetti e mi interessa crearmi un albero devo fare questo rigiro qua

        // Cicla le categorie
        while(list($key, $categoryNode) = each($categoryTree))
        {
            // Verifica se l'elemento va inserito in un nodo e se questo esiste
            if (($isChildElement = ($categoryNode->Element->GetParentID() !== 0)) &&
                isset($categoryTree[$categoryNode->Element->GetParentID()]) === true)
            {
                $categoryTree[$categoryNode->Element->GetParentID()]->
                    Children[$categoryNode->Element->GetID()] = $categoryNode;
            }

            // L'if precedente non si è verificato quindi controlla se l'elemento
            // non è un parent e quindi il ciclo non si deve interrompere
            else if($isChildElement === true)
            {
                // Imposta lo switch
                $foundedChildCategories = true;
            }
        }

        // Resetta le categorie
        reset($categoryTree);

questo secondo while associa i child con i parent usando i riferimenti

[code]
// Elimina tutti gli elementi che non appartengono alla root dall'albero
while(list($key, $categoryNode) = each($categoryTree))
{
// Verifica se appartiene alla root
if ($categoryNode->Element->GetParentID() != 0)
{
// Elimina l'elemento
unset($categoryTree[$key]);
}
}

// Resetta le categorie
reset($categoryTree);
[code]
per finire quest'ultimo elimina dall'elemento root dell'albero tutti gli elementi che non vi appartengono ... tanto sono stati settati come figli dei vari elementi e quindi stanno tutti li dentro

        // Restituisce l'elenco
        return $categoryTree;
    }

secondo voi posso ottimizzare/migliorare in qualche punto? Inoltre come potrei ottenere l'ordinamento? forse non mi conviene farlo qua ma dopo quando effettuo la visualizzazione e quindi lo riconverto in lista

Alternativamente, avete qualche strada alternativa?