Рекурсивный метод превращения плоской структуры к рекурсивным


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

Теперь код ниже-это лишь предположение, как решать подобные "проблемы", я создал FlatObject для имитации входящего с данными.

class Program
{
    static void Main(string[] args)
    {
        // Fill list with sample data
        List<FlatObject> flatObjects = new List<FlatObject>
        {
            new FlatObject(1,0),
            new FlatObject(2,0),
            new FlatObject(3,0),
            new FlatObject(4,0),
            new FlatObject(5,1),
            new FlatObject(6,2),
            new FlatObject(7,6),
            new FlatObject(8,6)
        };

        // call the recursive method
        var recursiveObjects = FillRecursive(flatObjects, 0);

    }

    private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
    {
        List<RecursiveObject> recursiveObjects = new List<RecursiveObject>();

        foreach (var item in flatObjects.Where(x => x.ParentId.Equals(parentId)))
        {
            recursiveObjects.Add(new RecursiveObject
            {
                Id = item.Id,
                ParentId = item.ParentId,
                Children = FillRecursive(flatObjects, item.Id)
            });
        }

        return recursiveObjects;
    }
}

public class FlatObject
{
    public int Id { get; set; }
    public int ParentId { get; set; }

    public FlatObject(int id, int parentId)
    {
        Id = id;
        ParentId = parentId;
    }
}

public class RecursiveObject
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public List<RecursiveObject> Children { get; set; }
}

Я знаю некоторые LINQ и варианты решения по каждому элементу петли, но это никак не изменить подход к этому.

private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
    return flatObjects.Where(x => x.ParentId.Equals(parentId)).Select(item => new RecursiveObject
    {
        Id = item.Id, ParentId = item.ParentId, Children = FillRecursive(flatObjects, item.Id)
    }).ToList();
}


23959
5
задан 20 декабря 2011 в 11:12 Источник Поделиться
Комментарии
3 ответа

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

Некоторые отличия от оригинальных настройки:


  • Свойство атрибутом parentId на FlatObject допускает значения null, поэтому объекты, которые имеют родителя будет иметь значение null.

  • Дети собственность на RecursiveObject имеет тип IEnumerable вместо списка. Это предотвращает потребителей от изменения содержимого списка. Если вы хотите, чтобы потребители могли добавить/удалить элементы из списка, то RecursiveObject должен предоставлять методы, чтобы выполнить эти действия, так что вы можете убедитесь, что свойство parent назначается правильно, когда ребенок будет добавлен/удален.

  • Я сделал идентификатор, родитель, и дети свойства RecursiveObject только для чтения. Это конечно не обязательно, но вы можете сделать это при желании. Это причина, почему я сделал метод FlatObjectsToRecursiveObjects как статический метод класса RecursiveObjects; так что он может иметь доступ к закрытому сеттеры собственность.

Суть такого подхода заключается в том, что мы сначала преобразовать FlatObjects в RecursiveObjects и хранить их в словарь с ключом по идентификатору. Затем, мы делаем еще один проход по FlatObjects для того, чтобы назначить родителей и детей свойства каждого RecursiveObject, используя словарь, выполнить необходимые окна с кодом в FlatObject и свойства атрибутом parentId.

class FlatObject
{
public int Id { get; set; }
public int? ParentId { get; set; }
}

class RecursiveObject
{
public int Id { get; private set; }
public RecursiveObject Parent { get; private set; }
public IEnumerable<RecursiveObject> Children { get; private set; }

public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
{
// convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject { Id = item.Id }).ToDictionary(item => item.Id);

// group flat objects by their ParentId
var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
foreach (var group in flatObjectsGroupedByParentId)
{
// find each group's parent object
RecursiveObject parent;
if (recursiveObjectsById.TryGetValue(group.Key, out parent))
{
// convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
parent.Children = group.Select(item => recursiveObjectsById[item.Id]).ToList();

// assign the parent object to each child object
foreach (var child in parent.Children)
{
child.Parent = parent;
}
}
else
{
// something's wrong!!! ParentId refers to a non-existant object.
}
}

return recursiveObjectsById.Values;
}
}

Редактирования: добавил "улучшенные" версии мой оригинальный подход, как показано ниже. Следующая реализация обеспечивает следующие преимущества:


  • Дети собственность на RecursiveObject никогда не возвращает null, но он по-прежнему сохраняет "благо" ленивая инициализация. Свойство Children добытчик проверяет, если _Children поле имеет значение null, и если так, она возвращает значение по умолчанию экземпляр EmptyEnumerable класс (код в комплекте).

  • Дети теперь могут быть добавлены/удалены с помощью нового метода addChild, метода removechild и методы метод addchildren на RecursiveObject.

  • Метод FlatObjectsToRecursiveObjects сейчас немного проще, потому что он использует новый метод метод addchildren.

  • Метод FlatObjectsToRecursiveObjects больше не должна быть членом класса RecursiveObject, поскольку он не имеет доступа к любой личной информации класса.

  • Моя настройка кода включает в себя второй корень (новый FlatObject(9,-1)) и циклические ссылки (новые FlatObject(10,10) и новый FlatObject(0,2)), просто чтобы убедиться, что реализация может обрабатывать особыми случаями.

    class FlatObject
    {
    public int Id { get; set; }
    public int? ParentId { get; set; }

    public FlatObject(int id)
    {
    this.Id = id;
    }

    public FlatObject(int id, int parentId)
    : this(id)
    {
    this.ParentId = parentId;
    }
    }

    class RecursiveObject
    {
    public int Id { get; private set; }
    public RecursiveObject Parent { get; private set; }
    private List<RecursiveObject> _Children;

    public IEnumerable<RecursiveObject> Children
    {
    get
    {
    IEnumerable<RecursiveObject> value = _Children;
    if (value == null)
    value = EmptyEnumerable<RecursiveObject>.Default;
    return value;
    }
    }

    public RecursiveObject(int id)
    {
    this.Id = id;
    }

    public void AddChild(RecursiveObject child)
    {
    if (_Children == null)
    _Children = new List<RecursiveObject>();
    _Children.Add(child);
    child.Parent = this;
    }

    public bool RemoveChild(RecursiveObject child)
    {
    if (_Children != null)
    {
    bool removed = _Children.Remove(child);
    if (removed)
    child.Parent = null;
    return removed;
    }
    else
    {
    return false;
    }
    }

    public void AddChildren(IEnumerable<RecursiveObject> children)
    {
    if (children == null)
    throw new ArgumentNullException("children");

    if (_Children == null)
    _Children = new List<RecursiveObject>(children);
    else
    _Children.AddRange(children);

    foreach (var child in children)
    {
    child.Parent = this;
    }
    }
    }

    class Program
    {
    public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
    {
    // convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
    var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject(item.Id)).ToDictionary(item => item.Id);

    // group flat objects by their ParentId
    var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
    foreach (var group in flatObjectsGroupedByParentId)
    {
    // find each group's parent object
    RecursiveObject parent;
    if (recursiveObjectsById.TryGetValue(group.Key, out parent))
    {
    // convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
    parent.AddChildren(group.Select(item => recursiveObjectsById[item.Id]));
    }
    else
    {
    // something's wrong!!! ParentId refers to a non-existant object.
    }
    }

    return recursiveObjectsById.Values;
    }

    static void Main(string[] args)
    {
    List<FlatObject> flatObjects = new List<FlatObject>()
    {
    new FlatObject(1,0),
    new FlatObject(2,0),
    new FlatObject(3,0),
    new FlatObject(4,0),
    new FlatObject(5,1),
    new FlatObject(6,2),
    new FlatObject(7,6),
    new FlatObject(8,6),
    new FlatObject(9,-1),
    new FlatObject(10,10),
    new FlatObject(0,2),
    };

    var recursiveObjects = FlatObjectsToRecursiveObjects(flatObjects).ToList();
    }
    }

    #region Universal Code

    class EmptyEnumerator<T> : IEnumerator<T>
    {
    public static readonly EmptyEnumerator<T> Default = new EmptyEnumerator<T>();

    public T Current
    {
    get { throw new InvalidOperationException(); }
    }

    public void Dispose()
    {
    }

    object System.Collections.IEnumerator.Current
    {
    get { throw new InvalidOperationException(); }
    }

    public bool MoveNext()
    {
    return false;
    }

    public void Reset()
    {
    }
    }

    class EmptyEnumerable<T> : IEnumerable<T>
    {
    public static readonly EmptyEnumerable<T> Default = new EmptyEnumerable<T>();

    public IEnumerator<T> GetEnumerator()
    {
    return EmptyEnumerator<T>.Default;
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
    return this.GetEnumerator();
    }
    }

    #endregion


5
ответ дан 21 декабря 2011 в 06:12 Источник Поделиться

Можно, пожалуй, вывести RecursiveObject от FlatObject.

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

1
ответ дан 20 декабря 2011 в 11:12 Источник Поделиться

Я фанат неизменяемые объекты и коллекции инициализатор синтаксиса себя:

    private static void Main()
{
// Fill list with sample data
FlatObjectList flatObjects = new FlatObjectList
{
{ 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, { 5, 1 }, { 6, 2 }, { 7, 6 }, { 8, 6 }
};

// call the recursive method
RecursiveObjectList recursiveObjects = FillRecursive(flatObjects, 0);
}

private static RecursiveObjectList FillRecursive(IEnumerable<FlatObject> flatObjects, int parentId)
{
return new RecursiveObjectList(flatObjects
.Where(x => x.ParentId.Equals(parentId))
.Select(item => new RecursiveObject(item.Id, item.ParentId, FillRecursive(flatObjects, item.Id))));
}
}

public sealed class FlatObjectList : List<FlatObject>
{
public void Add(int id, int parentId)
{
this.Add(new FlatObject(id, parentId));
}
}

public sealed class RecursiveObjectList : List<RecursiveObject>
{
public RecursiveObjectList(IEnumerable<RecursiveObject> list)
{
this.AddRange(list);
}

public void Add(int id, int parentId, RecursiveObjectList children)
{
this.Add(new RecursiveObject(id, parentId, children));
}
}

public sealed class FlatObject
{
private readonly int id;

private readonly int parentId;

public int Id { get { return this.id; } }

public int ParentId { get { return this.parentId; } }

public FlatObject(int id, int parentId)
{
this.id = id;
this.parentId = parentId;
}
}

public sealed class RecursiveObject
{
private readonly int id;

private readonly int parentId;

private readonly ReadOnlyCollection<RecursiveObject> children;

public RecursiveObject(int id, int parentId, IList<RecursiveObject> children)
{
this.id = id;
this.parentId = parentId;
this.children = new ReadOnlyCollection<RecursiveObject>(children);
}

public int Id { get { return this.id; } }

public int ParentId { get { return this.parentId; } }

public ReadOnlyCollection<RecursiveObject> Children { get { return this.children; } }
}

1
ответ дан 20 декабря 2011 в 11:12 Источник Поделиться