Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / WinForms, .Net Framework Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Сделать дерево плоским списком  [new]
Qwe.Qwe1
Member

Откуда:
Сообщений: 237
Есть класс, хранящий дерево элементов. Дочерние элементы хранятся в поле списка List<BaseTreeData> Child. Хочу вывести это дерево как "плоский" (линейный) список всех элементов. После разделения класса на два (базовый и наследник) метод GetChildren выдают ошибку про несоответствие типов. Скорее всего все логично, но как это исправить?

namespace ConsoleApplication1
{
    class Program
    {        
        static void Main(string[] args)
        {
            var data = new List<TreeData>();
            for (int i = 0; i < 5; i++)
            {
                var item = new TreeData() { Name = i.ToString() };
                for (int j = 0; j < 3; j++)
                {
                    var number = (i + 1) * 10 + j;
                    item.Child.Add(new TreeData() { ID = number, Name = number.ToString(), Parent = item });                    
                }
                data.Add(item);
            }

            foreach (var item in data.SelectMany(x => GetChildren(x)))
            {
                Console.WriteLine(item.ID + " " + item.Name + " " + item.IsChecked);
            }
        }

        static IEnumerable<TreeData> GetChildren(TreeData d)
        {
            return new[] { d }.Concat(d.Child).SelectMany(x => GetChildren(x));
        }
    }

    class BaseTreeData
    {
        public bool IsChecked { get; set; }
        public BaseTreeData Parent { get; set; }
        public List<BaseTreeData> Child { get; set; }

        public BaseTreeData()
        {
            Child = new List<BaseTreeData>();
        }
    }

    class TreeData : BaseTreeData
    {
        public int ID { get; set; }
        public string Name { get; set; }
    }
}
29 авг 18, 15:46    [21657822]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3345
        public static IEnumerable<T> GetAll<T>(T item, Func<T, IEnumerable<T>> getChild)
        {
            yield return item;
            foreach (var i in getChild(item))
            {
                foreach (var j in GetAll(i, getChild))
                {
                    yield return j;
                }
            }
        }
29 авг 18, 15:56    [21657834]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
Qwe.Qwe1
Member

Откуда:
Сообщений: 237
А как вызывать? А можно сделать этот метод - методом расширения?
29 авг 18, 16:27    [21657869]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3345
using System;
using System.Collections.Generic;

namespace TreeEnumerableExample
{
    class Program
    {
        static void Main(string[] args)
        {
            var treeItem = new TreeItem("A1")
            {
                Children =
                {
                    new TreeItem("B1")
                    {
                        Children =
                        {
                            new TreeItem("C1")
                            {
                                Children =
                                {
                                    new TreeItem("D1"),
                                    new TreeItem("D2"),
                                }
                            }
                        }
                    },
                    new TreeItem("B2")
                    {
                        Children =
                        {
                            new TreeItem("C2")
                        }
                    }
                }
            };

            foreach (var i in TreeEx.GetAll(treeItem, p=>p.Children))
            {
                Console.WriteLine(i.Name);
            }

            Console.ReadKey();
        }
    }

    public class TreeItem
    {
        public TreeItem(string name)
        {
            Name = name;
            Children = new List<TreeItem>();
        }
        public string Name { get; }
        public List<TreeItem> Children { get; }
    }

    public class TreeEx
    {
        public static IEnumerable<T> GetAll<T>(T item, Func<T, IEnumerable<T>> getChild)
        {
            yield return item;
            foreach (var i in getChild(item))
            {
                foreach (var j in GetAll(i, getChild))
                {
                    yield return j;
                }
            }
        }

        public static IEnumerable<T> GetAll<T>(IEnumerable<T> items, Func<T, IEnumerable<T>> getChild)
        {
            foreach (var i in items)
            {
                foreach (var j in GetAll(i, getChild))
                {
                    yield return j;
                }
            }
        }
    }
}
29 авг 18, 17:53    [21657983]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
Qwe.Qwe1
Member

Откуда:
Сообщений: 237
Спасибо. А зачем второй метод GetAll? И как быть, если я класс дерева унаследую (см. код ниже), как привести тип при вызове
foreach (var i in TreeEx.GetAll(treeItem, p => p.Children))

public class TreeItem2 : TreeItem
{
    public string Address { get; set; }

    public TreeItem2() : base (null) { }
    public TreeItem2(string name) : base(name) { }
    public TreeItem2(string name, string address) : base(name)
    {
        Address = address;
    }
}

var treeItem = new TreeItem2("A1")
{
    Children =
    {
        new TreeItem2("B1")
        ...
30 авг 18, 09:25    [21658448]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
Roman Mejtes,

лучше избегать рекурсии, без крайней необходимости
30 авг 18, 10:30    [21658524]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4673
hVostt
Roman Mejtes,

лучше избегать рекурсии, без крайней необходимости

А как тут избежишь?
30 авг 18, 12:10    [21658664]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3345
hVostt,

опасность есть только в переполнении стека, если дерево не супер глубокое и не имеет циклических ссылок, когда потомки ссылаются на предка в качестве свою потомков, проблем не будет.
30 авг 18, 12:10    [21658665]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
ViPRos
Member

Откуда:
Сообщений: 9533
Roman Mejtes,

все это ужасно медленно
30 авг 18, 12:55    [21658742]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3345
ЕвгенийВ
hVostt
Roman Mejtes,

лучше избегать рекурсии, без крайней необходимости

А как тут избежишь?

Создаете очередь\коллекцию вершин которые нужно обойти. Добавляете в неё Root ветку.
Запускаете цикл до тех пор пока коллекция вершин не будет пуста.
В цикле извлекаете элемент из очереди\коллекции элемент и возвращаете его через yield return, после чего добавляете все его ветки в очередь\коллекцию. Затем повторяете так до тех пор, пока цикл не закончится. Профит.
Преимущество этого способа в том, что вы не зависите от размера стека и глубины дерева.

Примерно вот так:
        public static IEnumerable<T> GetAllWithOutRecursion<T>(T item, Func<T, IEnumerable<T>> getChild)
        {
            Queue<T> queue= new Queue<T>();
            queue.Enqueue(item);
            while (itemsForScan.Count > 0)
            {
                var currentItem = queue.Dequeue();
                foreach (var i in getChild(currentItem))
                {
                    queue.Enqueue(i);
                }
                yield return currentItem;
            }
        }
30 авг 18, 13:04    [21658760]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
ЕвгенийВ
А как тут избежишь?


https://docs.microsoft.com/ru-ru/dotnet/api/system.collections.stack
30 авг 18, 13:08    [21658767]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
Roman Mejtes,

лучше использовать коллекцию Stack, а не очередь :)
30 авг 18, 13:19    [21658788]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
Исправил. Убрал ненужное заталкивание в очередь/стек всех элементов для извлечения. Только целые коллекции.

        public static IEnumerable<T> GetAllWithOutRecursion<T>(T item, Func<T, IEnumerable<T>> getChild)
        {
            var stack = new Stack<IEnumerable<T>>();
            stack.Push(new[] {item});
            while (stack.Count > 0)
            {
                var items = stack.Pop();
                foreach (var item in items)
                {
                    yield return item;                    
                    stack.Push(getChild(item));
                }
            }
        }
30 авг 18, 13:26    [21658802]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
ViPRos
все это ужасно медленно


Потестим на Benchamark.NET :)
30 авг 18, 13:27    [21658804]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3345
hVostt,

я делал на коленке в процессе между сборками проекта :) сейчас работы очень много, у тебя косяк в коде
2 раза подряд в одной области видимости определяется переменная item
T item и var item, а так всё ок :)
30 авг 18, 13:47    [21658829]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
Roman Mejtes,

рабочий код так и пишем, всё на коленке
шутка
30 авг 18, 14:46    [21658952]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4673
hVostt
Исправил. Убрал ненужное заталкивание в очередь/стек всех элементов для извлечения. Только целые коллекции.

        public static IEnumerable<T> GetAllWithOutRecursion<T>(T item, Func<T, IEnumerable<T>> getChild)
        {
            var stack = new Stack<IEnumerable<T>>();
            stack.Push(new[] {item});
            while (stack.Count > 0)
            {
                var items = stack.Pop();
                foreach (var item in items)
                {
                    yield return item;                    
                    stack.Push(getChild(item));
                }
            }
        }

А как сюда добавить асинхронную блокировку по значению?
30 авг 18, 15:00    [21658988]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
ЕвгенийВ,

Троллишь чтоли?
30 авг 18, 15:15    [21659011]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4673
hVostt
ЕвгенийВ,

Троллишь чтоли?

Так, для поднятия настроения. :)

А вот тут можно обойтись без рекурсии?
  public class A
    {
        public IEnumerable<B> Items { get; set; }
    }
    public class B
    {
        public IEnumerable<C> Items { get; set; }
    }
    public class C
    {
        public IEnumerable<A> Items { get; set; }
    }
    public class C1
    {
        public void Run(A a)
        {
            //обработка a
            //...........
            foreach (var b in a.Items)
            {
                Run(b);
            }
        }
        public void Run(B b)
        {
            //обработка b
            //...........
            foreach (var c in b.Items)
            {
                Run(c);
            }
        }
        public void Run(C c)
        {
            //обработка c
            //...........
            foreach (var a in c.Items)
            {
                Run(a);
            }
        }
    }
30 авг 18, 15:50    [21659091]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3345
для этого нужно использовать наследование, а элементы в стеке могут иметь тип Object, а наследники можно получать через условие по типу
30 авг 18, 15:55    [21659109]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
ЕвгенийВ,

Визитор ))
30 авг 18, 19:50    [21659345]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4673
hVostt
ЕвгенийВ,

Визитор ))


Вот попробуй как нибудь отнаследоваться от ExpressionVisitor, хотя бы тупо переопределить виртуальные методы простым вызовом базового и посмотреть в отладчике стек вызовов.
Не пойдет визитор :)
30 авг 18, 21:34    [21659429]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
ЕвгенийВ,

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

Визитор может обойти иерархию и сделать что-нибудь, нахаляву получишь сформированный плоский список.
31 авг 18, 07:42    [21659585]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4673
hVostt,
Визитор обойдет иерархию с использованием взаимной рекурсии.
31 авг 18, 09:18    [21659684]     Ответить | Цитировать Сообщить модератору
 Re: Сделать дерево плоским списком  [new]
hVostt
Member

Откуда:
Сообщений: 15397
ЕвгенийВ,

Визитор тут нужен не для рекурсии, а для извлечения из объекта X, коллекции, если она вообще там есть. Это будет реализация визитора для построения плоского списка из иерархии любой вложенности.
31 авг 18, 12:59    [21660140]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / WinForms, .Net Framework Ответить