LINQ: Можем ли мы создать плоский список из иерархии

Question

ОК ... заголовок правильный ...

Я не хочу иерархии из плоского списка, но с точностью до наоборот

У меня есть класс папки, в котором есть списокПапок в нем содержится имущество Children.Так что это типичная модель иерархии.

Теперь я хочу сгладить этот список ... это будет предварительный обход, т. Е.

Предположим

   A
   - A.1
   ----- A.1.1
   ----- A.1.2
   - A.2
   ----- A.2.1
   - A.3
   B
   - B.1
   - B.2
   ----- B.2.1
   ----- B.2.2
   ----------- B.2.2.1
   ----------- B.2.2.2 

Исходя из этой иерархии, плоский список, который я ожидаю, представляет собой именно тот порядок, в котором он появляется выше!

Если LINQ не может этого сделать, то может ли XSLT превратить его в список элементов xml?

Answer 1

Если LINQ не может сделать это, может ли XSLT превратить его в список XML-элементы?

Несколько человек показали, как это сделать с помощью LINQ.

Вот краткое и простое решение XSLT , которое преобразует XML-представление предоставленного списка вложенных элементов в плоский упорядоченный список элементов:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>
 <xsl:strip-space elements="*"/>

 <xsl:template match="/*">
  <xsl:apply-templates select="*[1]"/>
 </xsl:template>

 <xsl:template match="*/*">
   <xsl:copy/>
   <xsl:apply-templates select="*[1]"/>
   <xsl:apply-templates select="following-sibling::*[1]"/>
 </xsl:template>
</xsl:stylesheet>

когда это преобразование применяется к XML-представлению предоставленного вами ввода :

<t>
    <A>
        <A.1>
            <A.1.1/>
            <A.1.2/>
        </A.1>
        <A.2>
            <A.2.1/>
        </A.2>
        <A.3/>
    </A>
    <B>
        <B.1/>
        <B.2>
            <B.2.1/>
            <B.2.2>
                <B.2.2.1/>
                <B.2.2.2/>
            </B.2.2>
        </B.2>
    </B>
</t>

Требуется искомая, правильно упорядоченная плоская последовательность :

<A/>
<A.1/>
<A.1.1/>
<A.1.2/>
<A.2/>
<A.2.1/>
<A.3/>
<B/>
<B.1/>
<B.2/>
<B.2.1/>
<B.2.2/>
<B.2.2.1/>
<B.2.2.2/>

ОБНОВЛЕНИЕ : Вот нерекурсивное и еще более простое решение XSLT (спасибо Эндрю Уэлчу за напоминание об этом):

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">
  <xsl:for-each select="//*">
   <xsl:copy/>
  </xsl:for-each>
 </xsl:template>
</xsl:stylesheet>

Это решение работает без проблем в случаях, когда рекурсивное решение заканчивается реальным переполнением стека .

Answer 2

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

var doc = XDocument.Load(stream);
var descendants = doc.Descendants("Folder");
// Use descendants now

То, что может оказаться даже проще, чем подход XSLT. Например, если вы хотите преобразовать его в List<string>, взяв атрибут из каждого элемента:

var doc = XDocument.Load(stream);
var names = doc.Descendants("Folder")
               .Select(x => (strong) x.Attribute("name"))
               .ToList();   

Недостатком является то, что он все равно будет загружать весь XML-файл в память в виде XElement (и т. Д.) Объектов. Вполне возможно, что версия XSLT может обрабатывать это потоковым способом с более эффективным использованием памяти. Димитр, без сомнения, может дать больше информации, если это уместно.

---

В LINQ нет ничего, что могло бы сгладить несколько уровней иерархии без выполнения рекурсии самостоятельно. SelectMany выполняет один уровень сглаживания, но вам придется повторить, чтобы свести вашу многоуровневую иерархию к одному списку.

Теперь, если вы используете LINQ to XML, поддерживает очень легко - вы можете просто использовать метод Descendants:

var allFolders = root.Descendants("Folder");

Чтобы написать что-то похожее для вашего класса домена, вам нужно написать больше кода. Если вы можете дать больше информации о том, что вы действительно получили (XML или классы доменов), мы можем помочь вам больше.

РЕДАКТИРОВАТЬ: Хорошо, похоже, XML здесь красная сельдь. Но найти всех потомков довольно легко. Вы можете сделать это, используя блоки итераторов, но это становится довольно неприятно неэффективно довольно быстро. Вот еще одна простая альтернатива:

public IList<Folder> SelfAndDescendants()
{
    List<Folder> ret = new List<Folder>();
    AddSelfAndDescendants(ret);
    return ret;
}

private void AddSelfAndDescendants(IList<Folder> list)
{
    list.Add(this);
    foreach (var child in children)
    {
        AddSelfAndDescendants(list);
    }
}

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

Answer 3

Вы можете использовать SelectMany для выравнивания иерархии

http://msdn.microsoft.com/en-us/library/bb534336.aspx

Answer 4

Это будет моя первая попытка:

    public static IEnumerable<Folder> SelfPlusChildren(Folder f)
    {
        return new[] {f}.Concat(f.Children.SelectMany(SelfPlusChildren));
    }

Answer 5

Вот метод расширения в стиле linq, который делает то, что вы просите (без рекурсии, циклы обрабатываются).

    public static IEnumerable<T> WalkTreeDepthFirst<T>(this IEnumerable<T> source,
       Func<T, IEnumerable<T>> childFunction)
    {
        // http://en.wikipedia.org/wiki/Depth-first_search
        HashSet<T> seenIt = new HashSet<T>();
        Stack<T> toVisit = new Stack<T>();

        foreach (T item in source.Reverse())
        {
            toVisit.Push(item);
        }

        while (toVisit.Any())
        {
            T item = toVisit.Pop();
            if (!seenIt.Contains(item))
            {
                seenIt.Add(item);
                foreach (T child in childFunction(item).Reverse())
                {
                    toVisit.Push(child);
                }
                yield return item;
            }
        }
    }

Answer 6

В .Net Framework нет стандартной реализации, но вы можете реализовать ее самостоятельно.

Вот как вы можете это сделать:

public static IEnumerable<T> FlattenTree<T>(this T root, Func<T, IEnumerable<T>> getChildren)
{
    var state = new Stack<T>();
    state.Push(root);

    while (state.Count != 0)
    {
        T top = state.Pop();
        yield return top;

        IEnumerable<T> children = getChildren(top) ?? Enumerable.Empty<T>();
        foreach (T child in children.Reverse())
        {
            state.Push(child);
        }
    }
}

Answer 7

Вы можете написать простой метод расширения, чтобы сделать это:

public static IEnumerable<Folder> GetFolders(this Folder rootFolder)
{
    yield return rootFolder;

    foreach (var child in rootFolder.Children)
        foreach(var folder in GetFolders(child))
            yield return folder;
}

или короче, используя SelectMany():

public static IEnumerable<Folder> GetFolders(this Folder rootFolder)
{
    yield return rootFolder;

    foreach (var folder in rootFolder.Children.SelectMany(GetFolders))
        yield return folder;
}