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

Вы можете попробовать это

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

}

Answer 3

Это не рекурсивно, но вот решение (при условии, что у вас есть все группы в списке с именем 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 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

Группировка по ParentID (Linq: GroupBy), заказ по ID.

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

Answer 6

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