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