Блог

Главная - Вопросы по программированию - Поиск всех предков до идентификатора узла

Поиск всех предков до идентификатора узла

#c# #lambda #ienumerable

#c# #лямбда #ienumerable

Вопрос:

У меня есть дерево узлов, которое я хотел бы перебирать, чтобы найти всех предков до заданной точки (узла) в дереве. Таким образом, я могу вставить / сохранить его обратно в свою базу данных. Пока у меня есть что-то вроде следующего, что пока оказалось очень полезным: 

 public IEnumerable<INode> Ancestors()
{
   var parent = this.Parent;
   while (parent != null)
   {
      yield return parent;
      parent = parent.Parent;
   }
}

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

Какая это была бы лучшая реализация?.Ta

Отредактировано: даны ответы ниже. Я думаю о чем-то более производительном, например:

  public IEnumerable<INode> Ancestors(Func<INode, bool> predicate)
 {
    var parent = this.Parent;
    while (parent != null)
    {
      if (predicate(parent))
      { 
         yield return parent;
      }
      else
      { 
         yield break; 
      }

      parent = parent.Parent;
    }
 }

Правильно ли я говорю, что ответ Джона создаст 2 счетчика?

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

1. вам нужен диапазон? Например, получить все до id = X? который может повторно выполнить 15 элементов, если идентификатор начинается с 1 и X = 15

2. да, в этом суть!, но это может быть любой идентификатор или любой предикат

Ответ №1:

Как насчет:

 var desiredNode = child.Ancestors().FirstOrDefault(node => node.Id == desiredId);

Это дает null , если правильный узел не может быть найден.

РЕДАКТИРОВАТЬ: Хорошо, если вам нужна полная последовательность снизу вверх, вы можете просто использовать:

 var nodes = child.Ancestors().TakeUntil(node => node.Id == desiredId);

где TakeUntil это метод, подобный TakeWhile , но который включает в себя конечный узел, который соответствует предикату. Вы можете найти пример реализации в MoreLINQ. Если вы не возражаете против отсутствия проверки аргументов (которую предоставляет MoreLINQ), это очень просто написать:

 public static IEnumerable<T> TakeUntil<T>(this IEnumerable<T> source,
                                          Func<T, bool> predicate)
{
    foreach (T item in source)
    {
        yield return item;
        if (predicate(item))
        {
            yield break;
        }
    }
}

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

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

1. Мне нужна вся последовательность, снизу вверх и остановка в идентификаторе

2. должен сказать.. Я доволен, что мистер Скит ответил на мой самый первый вопрос в SO. Спасибо и продолжайте в том же духе.

3. На самом деле …, как будут выполняться два запроса. все сразу или это будет повторяться дважды?. Это операция, которую я намерен использовать довольно часто. На самом деле, вероятно, будет находиться в объекте Entity. хотя мне тоже нравится метод расширения. я думаю, что ответ Джилли может быть более производительным, что в данном случае является простым.

4. @ErMasca: он передает потоки — он не собирается копировать все в список или что-то в этом роде. Представьте, что ваш метод Ancestors() поддерживает курсор в текущей позиции. Он выдает значение для takeUntil, которое затем решает, передавать его вызывающей стороне или нет. Похоже, вам не помешало бы прочитать мою серию блогов Edulinq 🙂 msmvps.com/blogs/jon_skeet/archive/tags/Edulinq/default.aspx (Это не совсем LINQ, но это те же идеи …)

Ответ №2:

Попробуйте это:

 public IEnumerable<INode> Ancestors(Func<INode, bool> takeUntil)
{
   var parent = this.Parent;
   while (parent != null)
   {
      yield return parent;
      if (takeUntil(parent))
      {
         break;
      }
      parent = parent.Parent;
   }
}
...
var ancestors = node.Ancestors(n => n.Id == 123);

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

1. Я думаю, что было бы чище отделить поведение «take until» от поведения «find ancestors». Композиция качается 🙂