Порядок всех элементов в XML-порядке предварительного и пост-заказа обхода в C#
Мне нужна функция, чтобы вернуть предварительный порядок и порядок всех элементов в C#, который возвращает мне список (XElement, Preorder, Postorder) для всех элементов. Как я могу это сделать?
например, с этим XML:
<?xml version='1.0' encoding='ISO-8859-1' ?>
<!--
XML-Page generated by PENELOPE.
Copyright (c) 1999 Araneus Group and University 'Roma Tre', Rome, ITALY
All rights reserved.
-->
<SigmodRecord>
<issue>
<volume>11</volume>
<number>1</number>
<articles>
<article>
<title>Architecture of Future Data Base Systems</title>
<authors>
<author position="00">Lawrence A. Rowe</author>
<author position="01">Michael Stonebraker</author>
</authors>
<initPage>30</initPage>
<endPage>44</endPage>
</article>
<article>
<title>Multisafe - A Data Security Architecture</title>
<authors>
<author position="00">Robert P. Trueblood</author>
<author position="01">ii. Rex Hartson</author>
</authors>
<initPage>45</initPage>
<endPage>63</endPage>
</article>
</articles>
</issue>
<issue>
<volume>12</volume>
<number>2</number>
<articles>
<article>
<title>Comparison and Mapping of the Relational and CODASYL Data Models</title>
<authors>
<author position="00">Gary H. Sockut</author>
</authors>
<initPage>55</initPage>
<endPage>68</endPage>
</article>
</articles>
</issue>
</SigmodRecord>
Мне нужен этот ответ:
Element = <SigmodRecord>,preorder = 1, postorder = 29
Element = <SigmodRecord/issue>,preorder = 2, postorder = 18
.
.
.
Я написал этот класс, но он работает медленно в больших XML-файлах, потому что для каждого элемента он обрабатывает все узлы!
class CTraversal
{
private int preorderID = 0;
private int postorderID = 0;
public int PreOrderTraversal(XElement RootNode, XElement CurrentNode)
{
if (CurrentNode == RootNode)
{
return ++preorderID;
}
if (RootNode.DescendantNodes().Count() > 1)
{
foreach (var child in RootNode.Elements())
{
if (PreOrderTraversal(child, CurrentNode) != -1) return preorderID;
}
}
return -1;
}
public int PostOrderTraversal(XElement RootNode, XElement CurrentNode)
{
if (RootNode.DescendantNodes().Count() > 1)
{
foreach (var child in RootNode.Elements())
{
if (PostOrderTraversal(child, CurrentNode) != -1) return postorderID;
}
}
if (CurrentNode == RootNode)
{
return ++postorderID;
}
++postorderID;
return -1;
}
}
1 ответ
Так что обработка обхода дерева предзаказа проще, поэтому мы начнем с него.
Метод примет последовательность элементов и функцию, которая принимает элемент и преобразует его в последовательность элементов, что позволяет нам получить все дочерние элементы для любого данного узла.
Тогда в нашем методе у нас будет стек итераторов, чтобы начать итератор начальной последовательности в стек.
Оттуда мы выполняем цикл, пока есть какие-то итераторы для обработки. Мы получаем текущий элемент для обработки, если у него есть дочерние элементы, мы выдаем его текущий элемент, помещаем итератор обратно в стек для последующей обработки, извлекаем последовательность дочерних элементов, помещаем их в стек для обработки.
public static IEnumerable<T> PreOrder<T>(
IEnumerable<T> source,
Func<T, IEnumerable<T>> childSelector)
{
var stack = new Stack<IEnumerator<T>>();
stack.Push(source.GetEnumerator());
try
{
while (stack.Any())
{
var current = stack.Pop();
if (current.MoveNext())
{
stack.Push(current);
var children = childSelector(current.Current);
stack.Push(children.GetEnumerator());
yield return current.Current;
}
else
{
current.Dispose();
}
}
}
finally
{
foreach (var iterator in stack)
iterator.Dispose();
}
}
Это касается нашего алгоритма предварительного заказа: для каждого элемента, который нужно обработать, выведите его, а затем обработайте все дочерние элементы.
Вот контрольный пример, чтобы продемонстрировать это. Это XML-документ, в котором каждый узел имеет значение, представляющее порядок, который он должен быть получен из обхода предварительного заказа:
string preOrderExample =
@"<node value='1'>
<node value='2'>
<node value='3'/>
<node value='4'/>
<node value='5'/>
</node>
<node value='6'>
<node value='7'>
<node value='8'/>
<node value='9'>
<node value='10'/>
</node>
</node>
<node value='11'/>
</node>
</node>";
var preOrderDoc = XDocument.Parse(preOrderExample);
var query = PreOrder(new[] { preOrderDoc.Root }, node => node.Elements());
foreach (var node in query)
Console.WriteLine(node.Attribute("value").Value);
Это напечатает 1, 2, 3, ..., 11, указывая, что они обрабатываются в правильном порядке.
Почтовый заказ очень похож, но требует небольшой настройки. По сути, мы хотим, чтобы у нас был один и тот же алгоритм, но каждый элемент получался после обработки всех его дочерних элементов. Первое, что нужно сделать, это скопировать-вставить тот же алгоритм и просто удалить `yield. Теперь, где в нашем алгоритме мы знаем, где были обработаны все дочерние элементы?
Ну, сразу после того, как мы вытолкнули итератор из стека, Current элемент этого итератора только что обработал все свои элементы. Ну, если мы еще не позвонили MoveNext на этом итераторе вообще, в этом случае нет текущего элемента. Итак, если есть предмет, мы должны его отдать.
К сожалению, нет никакого способа, учитывая IEnumerator, чтобы знать, если это было MoveNext позвонил еще. Мы могли бы создать новый тип, который оборачивает IEnumerator и отслеживает, было ли это начато. Это, вероятно, на самом деле хорошая идея, но так как это используется только в этом одном методе, я немного обманул и просто использовал Tuple<IEnumerator<T>, bool> удерживать последовательность, которая может или не может быть начата, заменяя все использование IEnumerator<T> в методе с этим Tuple и установкой логического значения в зависимости от того, знаем ли мы, что мы запросили значение у этого итератора.
public static IEnumerable<T> PostOrder<T>(
IEnumerable<T> source,
Func<T, IEnumerable<T>> childSelector)
{
var stack = new Stack<Tuple<IEnumerator<T>, bool>>();
stack.Push(Tuple.Create(source.GetEnumerator(), false));
try
{
while (stack.Any())
{
var current = stack.Pop();
if (current.Item2)
yield return current.Item1.Current;
if (current.Item1.MoveNext())
{
stack.Push(Tuple.Create(current.Item1, true));
var children = childSelector(current.Item1.Current);
stack.Push(Tuple.Create(children.GetEnumerator(), false));
}
else
{
current.Item1.Dispose();
}
}
}
finally
{
foreach (var iterator in stack)
iterator.Item1.Dispose();
}
}
Наконец, у нас есть тестовый пример, в котором значения узлов упорядочены так, что они будут распечатывать 1, 2, 3,..., если они написаны в почтовом порядке:
string postOrderExample =
@"<node value='11'>
<node value='4'>
<node value='1'/>
<node value='2'/>
<node value='3'/>
</node>
<node value='10'>
<node value='8'>
<node value='5'/>
<node value='7'>
<node value='6'/>
</node>
</node>
<node value='9'/>
</node>
</node>";
var postOrderDoc = XDocument.Parse(postOrderExample);
query = PostOrder(new[] { postOrderDoc.Root }, node => node.Elements());
foreach (var node in query)
Console.WriteLine(node.Attribute("value").Value);