1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
4 
5 using System.Collections.Generic;
6 using System.Diagnostics;
7 using System.Xml.XPath;
8 
9 namespace MS.Internal.Xml.XPath
10 {
11     // This class can be rewritten much more efficient.
12     // Algorithm could be like one for FollowingSibling:
13     // - Build InputArrays: pares (first, sentinel)
14     // -- Cash all input nodes as sentinel
15     // -- Add first node of its parent for each input node.
16     // -- Sort these pares by first nodes.
17     // - Advance algorithm will look like:
18     // -- For each row in InputArrays we will output first node + all its following nodes which are < sentinel
19     // -- Before outputting each node in row #I we will check that it is < first node in row #I+1
20     // --- if true we actually output it
21     // --- if false, we hold with row #I and apply this algorithm starting for row #I+1
22     // --- when we done with #I+1 we continue with row #I
23 
24     internal class PreSiblingQuery : CacheAxisQuery
25     {
PreSiblingQuery(Query qyInput, string name, string prefix, XPathNodeType typeTest)26         public PreSiblingQuery(Query qyInput, string name, string prefix, XPathNodeType typeTest) : base(qyInput, name, prefix, typeTest) { }
PreSiblingQuery(PreSiblingQuery other)27         protected PreSiblingQuery(PreSiblingQuery other) : base(other) { }
28 
NotVisited(XPathNavigator nav, List<XPathNavigator> parentStk)29         private static bool NotVisited(XPathNavigator nav, List<XPathNavigator> parentStk)
30         {
31             XPathNavigator nav1 = nav.Clone();
32             nav1.MoveToParent();
33             for (int i = 0; i < parentStk.Count; i++)
34             {
35                 if (nav1.IsSamePosition(parentStk[i]))
36                 {
37                     return false;
38                 }
39             }
40             parentStk.Add(nav1);
41             return true;
42         }
43 
Evaluate(XPathNodeIterator context)44         public override object Evaluate(XPathNodeIterator context)
45         {
46             base.Evaluate(context);
47 
48             // Fill up base.outputBuffer
49             List<XPathNavigator> parentStk = new List<XPathNavigator>();
50             Stack<XPathNavigator> inputStk = new Stack<XPathNavigator>();
51             while ((currentNode = qyInput.Advance()) != null)
52             {
53                 inputStk.Push(currentNode.Clone());
54             }
55             while (inputStk.Count != 0)
56             {
57                 XPathNavigator input = inputStk.Pop();
58                 if (input.NodeType == XPathNodeType.Attribute || input.NodeType == XPathNodeType.Namespace)
59                 {
60                     continue;
61                 }
62                 if (NotVisited(input, parentStk))
63                 {
64                     XPathNavigator prev = input.Clone();
65                     if (prev.MoveToParent())
66                     {
67                         bool test = prev.MoveToFirstChild();
68                         Debug.Assert(test, "We just moved to parent, how we can not have first child?");
69                         while (!prev.IsSamePosition(input))
70                         {
71                             if (matches(prev))
72                             {
73                                 Insert(outputBuffer, prev);
74                             }
75                             if (!prev.MoveToNext())
76                             {
77                                 Debug.Fail("We managed to miss sentinel node (input)");
78                                 break;
79                             }
80                         }
81                     }
82                 }
83             }
84             return this;
85         }
86 
Clone()87         public override XPathNodeIterator Clone() { return new PreSiblingQuery(this); }
88         public override QueryProps Properties { get { return base.Properties | QueryProps.Reverse; } }
89     }
90 }
91