Creazione di oggetti gerarchici da un elenco semplice di padre / figlio
-
11-07-2019 - |
Domanda
Ho un elenco di elementi in una gerarchia e sto tentando di analizzare questo elenco in una vera gerarchia di oggetti. Sto usando traversal tree pre-order modificato per archiviare / iterare attraverso questo elenco, e quindi quello che ho è un sottoinsieme dell'albero, inclusi tutti i bambini, ordinati dalla loro "sinistra" valore.
Ad esempio, dato l'albero:
- Articolo A
- Articolo A.1
- Articolo A.2
- Articolo A.2.2
- Articolo B
- Articolo B.1
- Articolo C
Ottengo l'elenco:
- Articolo A, Articolo A.1, Articolo A.2, Articolo A.2.2, Articolo B, Articolo B.1, Articolo C
(Questo è nell'ordine del valore "a sinistra" dalla configurazione dell'albero pre-ordine modificata).
Quello che voglio fare è analizzarlo in oggetti che contengono la struttura reale dell'albero, ad esempio:
Class TreeObject {
String Name;
Guid ID;
Guid ParentID;
List<TreeObject> Children;
}
L'elenco flat viene restituito come Elenco di TreeObjects - e ogni TreeObject ha proprietà per ID, ParentID, Sinistra e Destra. Quello che sto cercando è una funzione:
List<TreeObject> FlatToHeirarchy(List<TreeObject> list);
che accetta l'elenco flat e restituisce un elenco nidificato.
In altre parole:
List<TreeObject> flatSet = LoadTreeObjectsFromDatabase();
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2
Non riesco a farlo: tenere traccia dei genitori e riuscire a fare un salto più grande (ad esempio, Articolo A.2.2 - > Articolo B).
Modifica: sto cercando una soluzione senza forza bruta (ad esempio, non eseguire più cicli ripetutamente, spostare elementi in nodi figlio, fino a quando rimangono solo i genitori di livello superiore). Immagino che esista un metodo elegante che può essere ripetuto una volta e posizionare gli oggetti secondo necessità.
Ricorda, sono sempre in un ordine gerarchico (dal momento che sto usando MPTT), quindi un determinato oggetto sarà sempre figlio o fratello dell'elemento precedente, o almeno condividi un genitore con l'elemento precedente. Non verrà mai da qualche altra parte nell'albero.
Soluzione
Ecco la funzione che ho finito per scrivere. Sto usando MPTT per archiviare oggetti, quindi l'elenco è in ordine del valore 'left', il che significa sostanzialmente che il genitore viene sempre prima di ogni dato elemento nell'elenco. In altre parole, l'elemento a cui fa riferimento item.ParentID è sempre stato aggiunto (tranne nel caso di nodi di livello superiore o radice).
public class TreeObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
public IList<TreeObject> Children { get; set; } = new List<TreeObject>();
}
public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list)
{
// hashtable lookup that allows us to grab references to containers based on id
var lookup = new Dictionary<int, TreeObject>();
// actual nested collection to return
var nested = new List<TreeObject>();
foreach (TreeObject item in list)
{
if (lookup.ContainsKey(item.ParentId))
{
// add to the parent's child list
lookup[item.ParentId].Children.Add(item);
}
else
{
// no parent added yet (or this is the first time)
nested.Add(item);
}
lookup.Add(item.Id, item);
}
return nested;
}
e un semplice test (che funziona in LinqPad):
void Main()
{
var list = new List<TreeObject>() {
new TreeObject() { Id = 1, ParentId = 0, Name = "A" },
new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" },
new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" },
new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" },
new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" }
};
FlatToHierarchy(list).Dump();
}
Risultati:
Da quando lo sto aggiornando 5 anni dopo, ecco una versione ricorsiva di LINQ:
public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) {
return (from i in list
where i.ParentId == parentId
select new TreeObject {
Id = i.Id,
ParentId = i.ParentId,
Name = i.Name,
Children = FlatToHierarchy(list, i.Id)
}).ToList();
}
Altri suggerimenti
Presumo che tu conosca già il genitore di tutti gli elementi .
Tutto ciò che devi fare è iterare una volta tutti gli elementi dell'elenco e aggiungere l'elemento corrente all'elenco figlio del suo genitore. Conserva gli articoli solo senza i genitori nell'elenco nidificato di destinazione.
Ecco un pseudo codice:
foreach Item item in flatlist
if item.Parent != null
Add item to item.Parent.ChildrenList
Remove item from flatlist
end if
end for
Per quanto riguarda ottenere i genitori, da quello che posso vedere nel tuo esempio, potresti dover analizzare il nome e costruire uno stack man mano che avanzi nella lista.
Questo problema sembra difficile ma non lo è. Molte persone vedono questo problema da un'angolazione sbagliata; non devi provare a popolare tutti gli elenchi di bambini, ma piuttosto a eliminare gli elementi di figlio dall'elenco piatto, quindi diventa facile.
Versione alternativa che viene compilata normalmente, non ero sicuro che ci fosse un problema con il codice sopra.
private List<Page> FlatToHierarchy(List<Page> list) {
// hashtable lookup that allows us to grab references to the parent containers, based on id
Dictionary<int, Page> lookup = new Dictionary<int, Page>();
// actual nested collection to return
List<Page> nested = new List<Page>();
foreach(Page item in list) {
if (lookup.ContainsKey(item.parentId)) {
// add to the parent's child list
lookup[item.parentId].children.Add(item); //add item to parent's childs list
lookup.Add(item.pageId, item); //add reference to page in lookup table
} else {
// no parent added yet (or this is the first time)
nested.Add(item); //add item directly to nested list
lookup.Add(item.pageId, item); //add reference to page in lookup table
}
}
return nested;
}
Ecco un esempio, spero che questo aiuti
class Program
{
static void Main(string[] args)
{
TreeObject a = new TreeObject() { Name = "Item A" };
a.Children.Add( new TreeObject() { Name = "Item A.1" });
a.Children.Add( new TreeObject() { Name = "Item A.2" });
TreeObject b = new TreeObject() { Name = "Item B" };
b.Children.Add(new TreeObject() { Name = "Item B.1" });
b.Children.Add(new TreeObject() { Name = "Item B.2" });
TreeObject c = new TreeObject() { Name = "Item C" };
List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c });
string list = BuildList(nodes);
Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
List<TreeObject> newlist = new List<TreeObject>();
TreeObject temp = null;
foreach (string s in list.Split(','))
{
if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length)
{
temp = new TreeObject() { Name = s };
newlist.Add(temp);
}
else
{
temp.Children.Add(new TreeObject() { Name = s });
}
}
Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
}
static string BuildList(List<TreeObject> nodes)
{
StringBuilder output = new StringBuilder();
BuildList(output, nodes);
return output.Remove(output.Length - 1, 1).ToString();
}
static void BuildList(StringBuilder output, List<TreeObject> nodes)
{
foreach (var node in nodes)
{
output.AppendFormat("{0},", node.Name);
BuildList(output, node.Children);
}
}
}
public class TreeObject
{
private List<TreeObject> _children = new List<TreeObject>();
public string Name { get; set; }
public Guid Id { get; set; }
public List<TreeObject> Children { get { return _children; } }
}
}
Correzione dell'esempio fornito da gregmac
IList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId)
{
var q = (from i in list
where i.parent_id == parentId
select new
{
id = i.id,
parent_id = i.parent_id,
kks = i.kks,
nome = i.nome
}).ToList();
return q.Select(x => new TreeObject
{
children = FlatToHierarchy(list, x.id)
}).ToList();
}