C# - Рекурсивная группировка

Question

У меня есть Список объектов типа IGroup. Они могут быть вложены на неограниченный уровень, и я пытаюсь сгруппировать их после извлечения их из базы данных. Я не могу понять, как рекурсивно добавлять все группы к правильным родителям. Любые группы с нулевым именем в качестве родителя представляют собой группы верхнего уровня. Я не могу гарантировать, что они выходят из базы данных.

public interface IGroup { 
    string ID { get; set; } 
    string Name { get; set; } 
    string ParentID { get; set; } 
    IList<IGroup> Groups { get; set; } 
    ... 

Так что, если у меня был список:

Group1: ID = g1, ParentID = null 
Group1a: ID = g2, ParentID = g1 
Group2: ID = g3, ParentID = null 
Group1b: ID = g4, ParentID = g3 
Group1bc: ID = g5, ParentID = g4 

Я пытаюсь группировать их как:

|Group1 
|--Group1a 
|--Group1b 
|--| 
    |--Group1bc 
|Group2 

Любой фантазии ножевое перегруппировать их рекурсивно?

Answer 1

Не нужно быть рекурсивным. Для остроумие:

var lookup = items.ToDictionary(g => g.ID); // items is IEnumerable<IGroup> 
foreach (var item in items.Where(g => g.ParentID != null)) { 
    lookup[item.ParentID].Groups.Add(item); 
} 
var parents = items.Where(g => g.ParentID == null); 

Обратите внимание, что lookup[item.ParentID] бросят, если нет IGroup с соответствующим ParentID. Вы можете обработать это более изящно с помощью TryGetValue.

Моя реализация IGroup:

public class Group : IGroup { 
    public string ID { get; set; } 
    public string Name { get; set; } 
    public string ParentID { get; set; } 
    public IList<IGroup> Groups { get; set; } 
    public Group() { 
     Groups = new List<IGroup>(); 
    } 
} 

Мои тестовые задания:

IEnumerable<IGroup> items = new List<IGroup>() { 
    new Group() { ID = "g1", ParentID = null }, 
    new Group() { ID = "g2", ParentID = "g1" }, 
    new Group() { ID = "g3", ParentID = null }, 
    new Group() { ID = "g4", ParentID = "g3" }, 
    new Group() { ID = "g5", ParentID = "g4" }, 
    new Group() { ID = "g6", ParentID = "g5" } 
};  

Answer 2

Вы можете попробовать заказать их по родительскому id, считая, что родительская группа всегда создается до дочерней группы.

Answer 3

Группа по ParentID (Linq: GroupBy), заказывайте ID.

Начните с пустого корневого узла (ID: null) и добавьте все элементы с этим ParentID. Рекурсивно продолжить этот процесс для любого добавленного элемента.

Answer 4

Как извлечь каждый элемент из базы данных, вам нужно добавить его к родителю. Поэтому держите словарь, чтобы помочь найти родителя. Если вы получаете ребенка до его родителя, тогда вы можете вставить местозаполнитель, пока не получите реальную вещь.

void BuildGroups() 
{ 
    foreach(IGroup x /* obtained from database or a collection or wherever */) 
     AddGroup(x); 
} 

Dictionary<string,IGroup> _groups = new Dictionary<string,IGroup>; 
string _parentGroupName = "PARENT"; 
void AddGroup(IGroup x) 
{ 
    // locate (or create) parent and add incoming group 
    IGroup parent; 
    string parentID = x.ParentID ?? _parentGroupName; 
    if(!groups.TryGetValue(parentID, out parent)) 
    { 
     parent = new Group(parentID); // SEE NOTE BELOW! 
     _groups[parentID] = parent; 
    } 
    parent.Groups.Add(x); 

    // locate (or insert) child, and make sure it's up to date 
    IGroup child; 
    if(groups.TryGetValue(x.ID, out child)) 
    { 
     // We must have inserted this ID before, because we found one 
     // of ITS children first. If there are any other values besides 
     // ParentID and ID, then copy them from X to child here. 
    } 
    else 
    { 
     // first time we've seen this child ID -- insert it 
     _groups[x.ID] = x; 
    } 

} 

Словарь элемент в _parentGroupName тогда будет фиктивный узел, чьи дети все из ваших групп верхнего уровня (то есть те, с NULL в качестве ParentId из базы данных); от этого элемента вы можете сделать рекурсивный обход:

VisitGroups(_groups[_parentGroupName], ""); 

void VisitGroups(string ID, string indent) 
{ 
    IGroup x; 
    if(_groups.TryGetValue(ID, out x)) 
    { 
     foreach(IGroup y in x.Groups) 
     { 
      WriteLine(indent + " {0}", y.ID); 
      VisitGroups(y.ID, indent + " "); 
     }   
    } 
} 

Примечание: Эта реализация работает в одном инлайн проходят через данные - вы можете добавить элементы сразу, как они извлекаются из базы данных, и вам нужно только чтобы сделать один проход через данные. Это означает, что вы сохраняете некоторое время и некоторую память. Но взамен это требует, чтобы вы могли назначить объект с типом IGroup(), чтобы действовать как заполнитель, в случае, если ребенок извлекается перед его родителем. Вы можете избежать этого требования, если знаете что-то о порядке объектов, или если вы обрабатываете словарь в два прохода, как показано в других ответах.

Я использую значение часового, _parentGroupName, чтобы поддерживать узлы верхнего уровня в той же коллекции, что и все остальные. Вы можете легко изменить это, чтобы вместо этого использовать отдельную коллекцию для узлов верхнего уровня.

Answer 5

Это не рекурсивный, но вот решение (если у вас есть все, что группы в списке называется groups)

var rootGroups = new List<IGroup>(); 
var dic = groups.ToDictionary(g => g.ID); 
foreach (var g in groups) 
{ 
    if (g.ParentID == null) 
    { 
     rootGroups.Add(g); 
    } 
    else 
    { 
     IGroup parent; 
     if (dic.TryGetValue(g.ParentID, out parent)) 
     { 
       parent.Groups.Add(g); 
     } 
    } 
} 

Answer 6

Вы могли бы попробовать это

public interface IGroup 
{ 
    string ID { get; set; } 
    string Name { get; set; } 
    string ParentID { get; set; } 
    List<IGroup> Groups { get; set; } 
} 
public class Group : IGroup 
{ 
    public string ID { get; set; } 
    public string Name { get; set; } 
    public string ParentID { get; set; } 
    public List<IGroup> Groups { get; set; } 
    public Group() 
    { 

    } 
    public Group(string id, string name, List<IGroup> childs) 
    { 
     ID = id; 
     Name = name; 
     Groups = (List<IGroup>)childs.Cast<IGroup>(); 
    } 

} 


class Program 
{ 
    static void Main(string[] args) 
    { 
     List<IGroup> OriginalList; 
     List<IGroup> HirarchList = new List<IGroup>(); 

     OriginalList = new List<IGroup>() 
     { 
      new Group() { ID = "g1", ParentID = null }, 
      new Group() { ID = "g2", ParentID = "g1" }, 
      new Group() { ID = "g3", ParentID = null }, 
      new Group() { ID = "g4", ParentID = "g3" }, 
      new Group() { ID = "g5", ParentID = "g4" }, 
      new Group() { ID = "g6", ParentID = "g5" } }; 

     HirarchList = GetCreateList(null, OriginalList); 
    } 
    public static List<IGroup> GetCreateList(string id, List<IGroup> list) 
    { 
     List<IGroup> temp = new List<IGroup>(); 
     temp = (from item in list 
       where item.ParentID == id 
       select (IGroup)new Group(item.ID, item.Name,GetCreateList(item.ID, list))).ToList(); 

     return (List<IGroup>)temp; 
    } 

}