Можно ли написать рекурсивный IEnumerable <T>

Question

У меня есть класс, как:

class Spline
    int ChildrenCount;
    Spline GetChild (int index)

class SplineCollection : IEnumerable<Spline>
    Spline Master

Можно ли написать рекурсивный IEnumerable для коллекции SplineCollection, где он будет возвращать всех дочерних элементов по одному?

РЕДАКТИРОВАТЬ: Таким образом, Мастер является корневой коробкой, и иерархия его дочерних элементов может быть любой глубины.

РЕДАКТИРОВАТЬ: Используя имя Box, я думаю, что я запутал некоторых людей. Это должен быть геометрический объект, а не контейнер. Так что изменив его на сплайн.

Answer 1

Я бы пошел с ручным обслуживанием стека вместо того, чтобы полагаться на стек вызовов здесь. Причина в том, что для каждого посещенного Spline нужно было бы создавать новый IEnumerable<Spline>, если бы вы использовали стек вызовов путем рекурсивного вызова метода, который получает потомков. Это было бы неэффективно. Вы можете значительно улучшить обход, используя свой собственный стек.

public IEnumerable<Spline> Descendants
{
    get
    {
        // This performs a simple iterative preorder traversal.
        var stack = new Stack<Spline>(new Spline[] { this });
        while (stack.Count > 0)
        {
            Spline current = stack.Pop();
            yield return current;
            for (int i = current.ChildrenCount - 1; i >= 0; i--)
            {
                stack.Push(current.GetChild(i));
            }
        }
    }
}

Answer 2

Это будет делать первый в глубину обход дерева Box. Затем вы можете просто вызвать этот метод в поле Master, чтобы вернуть все рекурсивные дочерние элементы.

public class Box
{
    // ...

    public IEnumerable<Box> GetBoxes() 
    {
        yield return this;

        for (int i=0; i<box.ChildrenCount; i++)
        {
            foreach (Box child in box.GetChild(i).GetBoxes())
            {
                 yield return child;
            }
        }
    }
}

Answer 3

Да - смотрите этот раздел для Рекурсивных итераций с использованием итераторов C #.

Answer 4

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

IEnumerable<int> Triangle(int n) {
    yield return n;
    if (n > 0)
        foreach (var e in Triangle(n - 1))
            yield return e;
}

Answer 5

class Box
{
  int ChildrenCount;
  Box GetChild (int index){/* some implementation*/}
  public IEnumerable<Box> Children
  {
    get
    {
      for(int i = 0; i != ChildrenCount; ++i)
        yield return GetChild(i);
    }
  }
  public IEnumerable<Box> Descendants
  {
    get
    {
      foreach(Box child in Children)
      {
        yield return child;
        foreach(Box desc in child.Descendants)
          yield return desc;
      }
    }
  }
}

Вы можете вызвать это из BoxCollection, но, поскольку Box уже является коллекцией Boxes, я не вижу цели BoxCollection здесь. В этом отношении использование Box * IEnumerable<Box> или одного из его потомков (ICollection<Box>, IList<Box>), вероятно, улучшит полезность.

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

Answer 6

Конечно. Вам даже не нужен BoxContainer, так как box, по его имени, существует как контейнер:

public class Box
{
    private List<Box> myBoxes;

    public IEnumerable<Box> GetAllBoxes()
    {
        yield return this;
        foreach (var box in myBoxes)
        {
            var enumerator = box.GetAllBoxes().GetEnumerator();
            while(enumerator.MoveNext()) 
                yield return enumerator.Current;
        }
    }
}

Если в ячейке A хранятся ячейки B и C, в ячейке B - ячейки D и E, а в ячейке C - ячейка F, перечислимые значения будут выводиться A, B, D, E, C, F.