Lập bản đồ một danh sách phẳng vào một danh sách thứ bậc với cha mẹ ID C#

Question

tôi có một danh sách phẳng các loại như trong các lớp sau

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

Tôi đang cố gắng để ánh xạ danh sách căn hộ của tôi trong danh mục cho một cấu trúc heirarical chẳng hạn như được hiển thị bên dưới:

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

Câu hỏi của tôi là cách tốt nhất để đạt được điều này, vì có thể có một số lượng vô hạn?

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

Sử dụng giải pháp hai đường. Điều này giả định bộ sưu tập đầy đủ có thể phù hợp với bộ nhớ. Vượt qua đầu tiên quét danh sách các danh mục phẳng và xây dựng một từ điển Danh mục, được lập chỉ mục theo ID. Các bộ sưu tập con là tất cả sản phẩm nào tại thời điểm này, và tài sản mẹ là null. Sau đó, lần thứ hai vượt qua quét chúng một lần nữa, và xây dựng các bộ sưu tập con và đặt thuộc tính cha.

đang chưa được kiểm tra:

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

} 

này sẽ có thời gian O (n) đang chạy, vì nó là hai quét tuyến tính, với một số tra cứu từ điển, mà là O (1).

Answer 3

Một cách rất dễ dàng và rất performant để làm cho chuyển đổi này là để tạo ra một tra cứu trong đó bạn ánh xạ giá trị ID để các nút đó nên con cái mà giá trị ID. Tra cứu này có thể được tạo ra trong một lần truyền các nút. Sau đó, bạn có thể lặp qua tất cả các nút một lần nữa gán bộ sưu tập con của chúng là giá trị của giá trị ID của chúng trong tra cứu.

Lưu ý rằng việc này đơn giản hơn nếu bản đồ tra cứu tìm đến đối tượng thuộc loại bạn đang chuyển đổi, không chuyển đổi.

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