Как мне вырваться из рекурсивных циклов IEnumerable <T>, используя разрыв доходности? - PullRequest
Новая
       39

Как мне вырваться из рекурсивных циклов IEnumerable <T>, используя разрыв доходности?

4 голосов
/ 27 июля 2010

У меня есть следующий метод, который работает хорошо, за исключением того, что оператор yield break вырывается только из текущего перечислителя.Я понимаю, почему это так, но я вычеркиваю пробел относительно того, как распространять доходность по рекурсивному стеку. 

    private static IEnumerable<Node> FindChildrenById(IEnumerable nodes, string parentText) {
        var en = nodes.GetEnumerator();
        var targetFound = false;
        while (en.MoveNext())  {
            var node = en.Current as Node;
            if (node != null) 
            {
                if (node.Parent == null && string.IsNullOrEmpty(parentText))
                {
                    //Returns the top level nodes if an empty parentIdis entered
                    targetFound = true;
                    yield return node;
                }
                else if (node.Parent != null && node.Parent.Text == parentText)
                {
                    //returns the nodes belonging to the parent
                    yield return node;
                }
                else
                {
                    //Recurse into the children to see whether one of these is the node to find
                    foreach (var nd in FindChildrenById(node.Nodes, parentText))
                    {
                        yield return nd;
                    }
                }
            }
        }
        if (targetFound)
        {
            yield break;
        }
    }

Поэтому, когда у меня есть следующие узлы и я передаю "Top 2 a"как parentText ... 

Top 1
    Top 1 a
    Top 1 b
Top 2
    Top 2 a
       Top 2 aa
       Top 2 ab
       Top 2 ac
    Top 2 b
Top 3
    Top 3 a
    Top 3 b
Top 4

... тогда я получаю результат: 

Top 2 aa
Top 2 ab
Top 2 ac

Это правильный результат, однако, когда я перебираю свой код, внешнийСамый последний цикл продолжает обрабатывать Top 3 и Top 4. Как выйти из этого внешнего цикла?

Ответы [ 3 ]

2 голосов
/ 27 июля 2010

Если я правильно понял ваш код, я полагаю, что приведенный ниже код решит вашу проблему 

private static IEnumerable<Node> FindChildrenById(IEnumerable nodes, string parentText)
    {
        var result =
               (from node in nodes
                where (node.Parent == null && string.IsNullOrEmpty(parentText))
                      || (node.Parent != null && node.Parent.Text == parentText)
                select node).TakeWhile(node => !(node.Parent == null && string.IsNullOrEmpty(parentText)));
        return result;
    }

Он построен на двух методах расширения (см. Ниже) и должен повторяться только до тех пор, пока не будет достигнут критерий найденной цели 

public static class IEnumerablExtensions
        {
            //Will iterate the graph in depth first order
            public static IEnumerable<TResult> Select<TResult>(this IEnumerable collection, Func<Node, TResult> selector)
            {
                foreach (var obj in collection)
                {
                    var node = obj as Node;
                    if (node != null)
                    {
                        yield return selector(node);
                        foreach (var n in node.Nodes.Select(selector))
                        {
                           yield return n;
                        }
                    }
                }
            }

        public static IEnumerable<Node> Where(this IEnumerable collection, Predicate<Node> pred)
        {
            foreach (var node in collection.Select(x => x)) //iterate the list in graph first order
            {
                if (pred(node))
                    yield return node;
            }
        }
    }

РЕДАКТИРОВАТЬ: Произошла ошибка в методе Select в исходном сообщении (он не повторял дочерние элементы детей), который теперь исправляется

1 голос
/ 27 июля 2010

Я предполагаю, что функция на самом деле называется FindChildrenById, в противном случае я не вижу никакой рекурсии.

В этом предположении вы можете использовать исключения (которые я настоятельно рекомендую не использовать)или верните KeyValuePair<bool, IEnumerable<Node>>, где часть bool будет использоваться для оповещения о начале цепочки.

Затем на уровне API предоставьте метод-обертку, который просто возвращает часть IEnumerable<Node>и перебрасывает bool часть.

Вот пример, приведенный для класса Node: 

public class Node
{
    List<Node> children;
    public string Text { get; set; }
    public List<Node> Children { get { return children ?? (children = new List<Node>()); } }
}

Вы можете перемещаться и сокращаться следующим образом: 

public class NodeTraverser
{
    private static KeyValuePair<bool, IEnumerable<Node>> GetChildrenById(string text, Node node)
    {
        if(node.Text == text)
        {
            return new KeyValuePair<bool,IEnumerable<Node>>(true, node.Children);
        }
        foreach(var child in node.Children)
        {
            var result = GetChildrenById(text, child);
            if(result.Key)
            {
                return result; // early out
            }
        }
        return new KeyValuePair<bool,IEnumerable<Node>>(false, Enumerable.Empty<Node>());
    }

    public static IEnumerable<Node> FindChildrenbyId(string text, Node root)
    {
        return GetChildrenById(text, root).Value; 
    }
}
1 голос
/ 27 июля 2010 
//Returns the top level nodes if an empty parentIdis entered
targetFound = true;
yield return node;
yield break;

Будет ли это работать для вас?

Обновление:

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

Если бы C # имел хвостовую рекурсию, я бы предложил преобразовать код в CPS .

Вы всегда можете написать это в MSIL:)

...