Отображение плоского списка иерархического списка с родительским идентификаторы C#

Question

У меня есть плоский список категорий, как показано в следующих классах

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; } 
} 

Я пытаюсь сопоставить мой плоский список категорий к heirarical структуры например, как показано ниже:

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; } 
} 

Мой вопрос, что является лучшим способом для достижения этой цели, учитывая тот факт, что там может быть бесконечное число дочерних уровней?

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

Использовать двухпроходное решение. Это предполагает, что полная коллекция может поместиться в память. Первый проход просматривает список плоских категорий и строит словарь категории, индексированный по идентификатору. В этот момент дочерние коллекции пусты, а родительское свойство равно null. Затем второй проход сканирует их снова и создает дочерние коллекции и устанавливает родительское свойство.

неопробованные код:

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); 
    } 

} 

Это будет иметь время О (п) работает, так как это два линейных сканирования, с некоторыми словарных выборок, которые являются O (1).

Answer 3

очень легко и очень производительный способ сделать это преобразованием является создание поиска, в котором вы сопоставить значение идентификатора к узлам, которые должны быть детьми этого ID значения. Этот поиск может быть создан за один проход узлов. После этого вы можете перебирать все узлы, снова присваивая их дочерней коллекции значение их идентификатора в поиске.

Обратите внимание, что это проще, если поиск сопоставляется с объектами того типа, в который вы конвертируете, а не с переводом.

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(), 
};