среда, 3 ноября 2010 г.

Рекурсия Linq'ом

Задача рекурсивного обхода встает очень часто. Например, в SharePoint'е, я сталкивался с этим при рекурсивном добавлении пунктов меню и при удалении пунктов меню с флагом IsExternal (про это есть отдельный пост, "Локализация меню SharePoint 2010"); любые деревообразные контролы типа TreeView также частенько этого требуют, ну да и без всяких контролов, любые вложенные объекты рано или поздно требуют рекурсии или аналогичной по смыслу операции.

Раньше как-то не задумывался, что это можно реализовать на Linq'е. А ведь оказывается, простейший Extension Method эту проблему решает. Например, потребовалось подписать на событие MouseDown все вложенные контролы некой формы, код в таком случае будет выглядеть примерно так:
foreach(Control c in this.Controls.WithDescendants(c => c.Controls))
{
    c.MouseDown += new EventHandler<MouseEventArgs>(Controls_MouseDown);
}
Код для метода Descendants я взял с mutable.net, он выглядит следующим образом:
static public class LinqExtensions
{
    static public IEnumerable<T> WithDescendants<T>(this IEnumerable<T> source, 
                                                Func<T, IEnumerable<T>> DescendBy)
    {
        foreach (T value in source)
        {
            yield return value;

            foreach (T child in DescendBy(value).Descendants<T>(DescendBy))
            {
                yield return child;
            }
        }
    }
}
Выглядит всё очень красиво, и пользоваться тоже очень удобно. Тема оказалась довольно старинной, но повторюсь, иногда подобные решения просто не приходят в голову, особенно когда в голове уже много лет сидит прочное: "рекурсия реализуется так-то и так-то". Надеюсь, кому-то этот пост поможет, как и мне, открыть вот такой вот великолепный велосипед :)

Update:
Когда важна производительность, лучше использовать распрямление рекурсии в цикл. Думаю, это всем итак понятно, но уж коли мы имеем уникальную возможность сделать некий реюзабельный метод расширения, то о производительности стоит побеспокоиться сразу.
Я нашел пост Алексея Шинкарева LINQ-ом по деревьям (часть 2) с уже готовыми замерами различных алгоритмов. Ну вкратце, рекурсию, конечно же, следует распрямлять. Иначе в случае глубокого дерева получим банальный StackOverflowException.

Распрямление более-менее интуитивное, для быстроты привожу код-победитель по результатам Алексея, немного измененный мной под вызов для IEnumerable:
class ListNode<T>
{
    public T Value { get; private set; }
    public ListNode<T> Next { get; private set; }

    public ListNode(T value, ListNode<T> next)
    {
        Value = value;
        Next = next;
    }
}

public static IEnumerable<T> WithDescendants<T>(this IEnumerable<T> rootNodes, Func<T, IEnumerable<T>> next)
{
    if (rootNodes == null)
        yield break;

    ListNode<T> list = null;
    foreach (T listNode in rootNodes)
    {
        list = new ListNode<T>(listNode, list);
    }

    while (list != null)
    {
        var currentNode = list;
        var nextNode = list.Next;
        yield return currentNode.Value;

        ListNode<T> tmpList = null;
        IEnumerable<T> nextNodes = next(currentNode.Value);
        if (nextNodes != null)
        {
            foreach (var v in nextNodes)
            {
                tmpList = new ListNode<T>(v, tmpList);
            }
        }

        if (tmpList != null)
        {
            for (; tmpList != null; tmpList = tmpList.Next)
            {
                nextNode = new ListNode<T>(tmpList.Value, nextNode);
            }
        }
        list = nextNode;
    }
}

Update:
Обновил немного код, в процессе опытной эксплуатации выяснилось что там требуется несколько дополнительных проверок.

Комментариев нет:

Отправить комментарий

Внимание! Реклама и прочий спам будут беспощадно удаляться.