Mapowanie listę płaski do hierarchicznej listy z rodzicem identyfikatory C#

Question

mam płaską listę kategorii, jak pokazano w następujących klasach

public class FlatCategoryList 
{ 
    public List<FlatCategory> Categories { get; set; } 
} 
public class FlatCategory 
{ 
    public string ID { get; set; } 
    public string Name { get; set; } 
    public string ParentID { get; set; } 
} 

Próbuję map moją płaską listę kategorii do heirarical struktury tak jak pokazano poniżej:

public class HieraricalCategoryList 
{ 
    public List<Category> Categories { get; set; } 
} 
public class Category 
{ 
    public string ID { get; set; } 
    public string Name { get; set; } 
    public string ParentID { get; set; } 

    public List<Category> ChildCategories { get; set; } 
} 

Moje pytanie brzmi, co jest najlepszym sposobem osiągnięcia tego celu, biorąc pod uwagę fakt, że nie może być nieskończona ilość szczebli dziecko?

public HieraricalCategoryList MapCategories(FlatCategoryList flatCategoryList) 
{ 
    var hieraricalCategoryList = new HieraricalCategoryList(); 

    //Do something here to map the flat category list to the hierarichal one... 

    return hieraricalCategoryList; 
} 

Answer 1

public HieraricalCategoryList MapCategories(FlatCategoryList flatCategoryList) 
{ 
    var categories = (from fc in flatCategoryList.Categories 
         select new Category() { 
          ID = fc.ID, 
          Name = fc.Name, 
          ParentID = fc.ParentID 
         }).ToList(); 

    var lookup = categories.ToLookup(c => c.ParentID); 

    foreach(var c in categories) 
    { 
     // you can skip the check if you want an empty list instead of null 
     // when there is no children 
     if(lookup.Contains(c.ID)) 
      c.ChildCategories = lookup[c.ID].ToList(); 
    } 

    return new HieraricalCategoryList() { Categories = categories }; 
} 

Answer 2

Użyj rozwiązania dwuprzebiegowego. Zakłada to, że cała kolekcja mieści się w pamięci. Pierwsze przejście skanuje listę kategorii płaskich i tworzy słownik Kategorii indeksowany przez identyfikator. Zbiory podrzędne są w tym momencie puste, a właściwość nadrzędna ma wartość NULL. Następnie drugie przejście skanuje je ponownie i tworzy kolekcje dzieci i ustawia nadrzędną własność.

kod Nietestowane:

var final = new Dictionary<string, Category>(); 
var rootCategories = new List<Category>(); 

// Pass 1 
foreach (var flat in flatList) 
{ 
    Category cat = new Category() { ID = flat.ID, Name = flat.Name, parent = null } 
    cat.Children = new List<Category>(); 
    final[flat.ID] = cat; 
} 

// Pass 2 
foreach (var flat in flatList) 
{ 
    // find myself -- must exist 
    var self = final[flat.ID]; 

    // find parent -- may not exist 
    if (final.ContainsKey(flat.ParentID) 
    { 
    var parent = final[flat.ParentID]; 
    parent.Children.Add(self); 
    self.Parent = parent;  
    } 
    else 
    { 
    rootCategories.Add(self); 
    } 

} 

ten będzie miał czas O (n) działa, ponieważ jest to dwa skany liniowe, z pewnymi Przeszukiwanie słownika, które są O (1).

Answer 3

Bardzo proste i wysoce wydajnych sposób, aby tej transformacji jest stworzenie odnośnika w którym mapowanie wartości identyfikatorów do węzłów, które powinny być synami tej wartości ID. To wyszukiwanie można utworzyć w pojedynczym przebiegu węzłów. Następnie można powtórzyć wszystkie węzły ponownie przypisując ich kolekcję podrzędną do wartości ich wartości identyfikacyjnej w odnośniku.

Należy zauważyć, że jest to prostsze, jeśli wyszukiwanie mapuje do obiektów typu, na które się konwertuje, a nie konwertujących.

var lookup = list.Categories 
    .Select(category => new Category() 
    { 
     ID = category.ID, 
     Name = category.Name, 
     ParentID = category.ParentID, 
    }) 
    .ToLookup(category => category.ParentID); 

foreach (var category in lookup.SelectMany(x => x)) 
    category.ChildCategories = lookup[category.ID].ToList(); 

var newList = new HieraricalCategoryList() 
{ 
    Categories = lookup[null].ToList(), 
};