The Labs \ Source Viewer \ SSCLI \ System.Xml.Xsl.Runtime \ NodeRangeIterator

  1. //------------------------------------------------------------------------------
  2. // <copyright file="TreeIterators.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. using System;
  16. using System.Xml;
  17. using System.Xml.XPath;
  18. using System.Xml.Schema;
  19. using System.Diagnostics;
  20. using System.Collections;
  21. using System.ComponentModel;
  22. namespace System.Xml.Xsl.Runtime
  23. {
  24.    
  25.     /// <summary>
  26.     /// Iterate over all descendant content nodes according to XPath descendant axis rules.
  27.     /// </summary>
  28.     [EditorBrowsable(EditorBrowsableState.Never)]
  29.     public struct DescendantIterator
  30.     {
  31.         private XmlNavigatorFilter filter;
  32.         private XPathNavigator navCurrent, navEnd;
  33.         private bool hasFirst;
  34.        
  35.         /// <summary>
  36.         /// Initialize the DescendantIterator (no possibility of duplicates).
  37.         /// </summary>
  38.         public void Create(XPathNavigator input, XmlNavigatorFilter filter, bool orSelf)
  39.         {
  40.             // Save input node as current node
  41.             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
  42.             this.filter = filter;
  43.            
  44.             // Position navEnd to the node at which the descendant scan should terminate
  45.             if (input.NodeType == XPathNodeType.Root) {
  46.                 this.navEnd = null;
  47.             }
  48.             else {
  49.                 this.navEnd = XmlQueryRuntime.SyncToNavigator(this.navEnd, input);
  50.                 this.navEnd.MoveToNonDescendant();
  51.             }
  52.            
  53.             // If self node matches, then return it first
  54.             this.hasFirst = (orSelf && !this.filter.IsFiltered(this.navCurrent));
  55.         }
  56.        
  57.         /// <summary>
  58.         /// Position this iterator to the next descendant node. Return false if there are no more descendant nodes.
  59.         /// Return true if the Current property is set to the next node in the iteration.
  60.         /// </summary>
  61.         public bool MoveNext()
  62.         {
  63.             if (this.hasFirst) {
  64.                 this.hasFirst = false;
  65.                 return true;
  66.             }
  67.             return (this.filter.MoveToFollowing(this.navCurrent, this.navEnd));
  68.         }
  69.        
  70.         /// <summary>
  71.         /// Return the current result navigator. This is only defined after MoveNext() has returned true.
  72.         /// </summary>
  73.         public XPathNavigator Current {
  74.             get { return this.navCurrent; }
  75.         }
  76.     }
  77.    
  78.    
  79.     /// <summary>
  80.     /// Iterate over all descendant content nodes according to XPath descendant axis rules. Eliminate duplicates by not
  81.     /// querying over nodes that are contained in the subtree of the previous node.
  82.     /// </summary>
  83.     [EditorBrowsable(EditorBrowsableState.Never)]
  84.     public struct DescendantMergeIterator
  85.     {
  86.         private XmlNavigatorFilter filter;
  87.         private XPathNavigator navCurrent, navRoot, navEnd;
  88.         private IteratorState state;
  89.         private bool orSelf;
  90.        
  91.         private enum IteratorState
  92.         {
  93.             NoPrevious = 0,
  94.             NeedCurrent,
  95.             NeedDescendant
  96.         }
  97.        
  98.         /// <summary>
  99.         /// Initialize the DescendantIterator (merge multiple sets of descendant nodes in document order and remove duplicates).
  100.         /// </summary>
  101.         public void Create(XmlNavigatorFilter filter, bool orSelf)
  102.         {
  103.             this.filter = filter;
  104.             this.state = IteratorState.NoPrevious;
  105.             this.orSelf = orSelf;
  106.         }
  107.        
  108.         /// <summary>
  109.         /// Position this iterator to the next descendant node. Return IteratorResult.NoMoreNodes if there are no more
  110.         /// descendant nodes. Return IteratorResult.NeedInputNode if the next input node needs to be fetched.
  111.         /// Return IteratorResult.HaveCurrent if the Current property is set to the next node in the iteration.
  112.         /// </summary>
  113.         public IteratorResult MoveNext(XPathNavigator input)
  114.         {
  115.             if (this.state != IteratorState.NeedDescendant) {
  116.                 if (input == null)
  117.                     return IteratorResult.NoMoreNodes;
  118.                
  119.                 // Descendants of the input node will be duplicates if the input node is in the subtree
  120.                 // of the previous root.
  121.                 if (this.state != IteratorState.NoPrevious && this.navRoot.IsDescendant(input))
  122.                     return IteratorResult.NeedInputNode;
  123.                
  124.                 // Save input node as current node and end of input's tree in navEnd
  125.                 this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
  126.                 this.navRoot = XmlQueryRuntime.SyncToNavigator(this.navRoot, input);
  127.                 this.navEnd = XmlQueryRuntime.SyncToNavigator(this.navEnd, input);
  128.                 this.navEnd.MoveToNonDescendant();
  129.                
  130.                 this.state = IteratorState.NeedDescendant;
  131.                
  132.                 // If self node matches, then return it
  133.                 if (this.orSelf && !this.filter.IsFiltered(input))
  134.                     return IteratorResult.HaveCurrentNode;
  135.             }
  136.            
  137.             if (this.filter.MoveToFollowing(this.navCurrent, this.navEnd))
  138.                 return IteratorResult.HaveCurrentNode;
  139.            
  140.             // No more descendants, so transition to NeedCurrent state and get the next input node
  141.             this.state = IteratorState.NeedCurrent;
  142.             return IteratorResult.NeedInputNode;
  143.         }
  144.        
  145.         /// <summary>
  146.         /// Return the current result navigator. This is only defined after MoveNext() has returned true or IteratorResult.HaveCurrentNode.
  147.         /// </summary>
  148.         public XPathNavigator Current {
  149.             get { return this.navCurrent; }
  150.         }
  151.     }
  152.    
  153.    
  154.     /// <summary>
  155.     /// Iterate over matching parent node according to XPath parent axis rules.
  156.     /// </summary>
  157.     [EditorBrowsable(EditorBrowsableState.Never)]
  158.     public struct ParentIterator
  159.     {
  160.         private XPathNavigator navCurrent;
  161.         private bool haveCurrent;
  162.        
  163.         /// <summary>
  164.         /// Initialize the ParentIterator.
  165.         /// </summary>
  166.         public void Create(XPathNavigator context, XmlNavigatorFilter filter)
  167.         {
  168.             // Save context node as current node
  169.             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, context);
  170.            
  171.             // Attempt to find a matching parent node
  172.             this.haveCurrent = (this.navCurrent.MoveToParent()) && (!filter.IsFiltered(this.navCurrent));
  173.         }
  174.        
  175.         /// <summary>
  176.         /// Return true if a matching parent node exists and set Current property. Otherwise, return false
  177.         /// (Current property is undefined).
  178.         /// </summary>
  179.         public bool MoveNext()
  180.         {
  181.             if (this.haveCurrent) {
  182.                 this.haveCurrent = false;
  183.                 return true;
  184.             }
  185.            
  186.             // Iteration is complete
  187.             return false;
  188.         }
  189.        
  190.         /// <summary>
  191.         /// Return the current result navigator. This is only defined after MoveNext() has returned true.
  192.         /// </summary>
  193.         public XPathNavigator Current {
  194.             get { return this.navCurrent; }
  195.         }
  196.     }
  197.    
  198.    
  199.     /// <summary>
  200.     /// Iterate over all ancestor nodes according to XPath ancestor axis rules, returning nodes in reverse
  201.     /// document order.
  202.     /// </summary>
  203.     [EditorBrowsable(EditorBrowsableState.Never)]
  204.     public struct AncestorIterator
  205.     {
  206.         private XmlNavigatorFilter filter;
  207.         private XPathNavigator navCurrent;
  208.         private bool haveCurrent;
  209.        
  210.         /// <summary>
  211.         /// Initialize the AncestorIterator.
  212.         /// </summary>
  213.         public void Create(XPathNavigator context, XmlNavigatorFilter filter, bool orSelf)
  214.         {
  215.             this.filter = filter;
  216.            
  217.             // Save context node as current node
  218.             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, context);
  219.            
  220.             // If self node matches, then next call to MoveNext() should return it
  221.             // Otherwise, MoveNext() will fetch next ancestor
  222.             this.haveCurrent = (orSelf && !this.filter.IsFiltered(this.navCurrent));
  223.         }
  224.        
  225.         /// <summary>
  226.         /// Position the iterator on the next matching ancestor node. Return true if such a node exists and
  227.         /// set Current property. Otherwise, return false (Current property is undefined).
  228.         /// </summary>
  229.         public bool MoveNext()
  230.         {
  231.             if (this.haveCurrent) {
  232.                 this.haveCurrent = false;
  233.                 return true;
  234.             }
  235.            
  236.             while (this.navCurrent.MoveToParent()) {
  237.                 if (!this.filter.IsFiltered(this.navCurrent))
  238.                     return true;
  239.             }
  240.            
  241.             // Iteration is complete
  242.             return false;
  243.         }
  244.        
  245.         /// <summary>
  246.         /// Return the current result navigator. This is only defined after MoveNext() has returned true.
  247.         /// </summary>
  248.         public XPathNavigator Current {
  249.             get { return this.navCurrent; }
  250.         }
  251.     }
  252.    
  253.    
  254.     /// <summary>
  255.     /// Iterate over all ancestor nodes according to XPath ancestor axis rules, but return the nodes in document order.
  256.     /// </summary>
  257.     [EditorBrowsable(EditorBrowsableState.Never)]
  258.     public struct AncestorDocOrderIterator
  259.     {
  260.         private XmlNavigatorStack stack;
  261.         private XPathNavigator navCurrent;
  262.        
  263.         /// <summary>
  264.         /// Initialize the AncestorDocOrderIterator (return ancestor nodes in document order, no possibility of duplicates).
  265.         /// </summary>
  266.         public void Create(XPathNavigator context, XmlNavigatorFilter filter, bool orSelf)
  267.         {
  268.             AncestorIterator wrapped = new AncestorIterator();
  269.            
  270.             wrapped.Create(context, filter, orSelf);
  271.            
  272.             // Fetch all ancestor nodes in reverse document order and push them onto the stack
  273.             while (wrapped.MoveNext())
  274.                 stack.Push(wrapped.Current.Clone());
  275.         }
  276.        
  277.         /// <summary>
  278.         /// Return true if the Current property is set to the next Ancestor node in document order.
  279.         /// </summary>
  280.         public bool MoveNext()
  281.         {
  282.             if (stack.IsEmpty)
  283.                 return false;
  284.            
  285.             this.navCurrent = stack.Pop();
  286.             return true;
  287.         }
  288.        
  289.         /// <summary>
  290.         /// Return the current result navigator. This is only defined after MoveNext() has returned true.
  291.         /// </summary>
  292.         public XPathNavigator Current {
  293.             get { return this.navCurrent; }
  294.         }
  295.     }
  296.    
  297.    
  298.     /// <summary>
  299.     /// Iterate over all following nodes according to XPath following axis rules. These rules specify that
  300.     /// descendants are not included, even though they follow the starting node in document order. For the
  301.     /// "true" following axis, see FollowingIterator.
  302.     /// </summary>
  303.     [EditorBrowsable(EditorBrowsableState.Never)]
  304.     public struct XPathFollowingIterator
  305.     {
  306.         private XmlNavigatorFilter filter;
  307.         private XPathNavigator navCurrent;
  308.         bool needFirst;
  309.        
  310.         /// <summary>
  311.         /// Initialize the XPathFollowingIterator (no possibility of duplicates).
  312.         /// </summary>
  313.         public void Create(XPathNavigator input, XmlNavigatorFilter filter)
  314.         {
  315.             // Save input node as current node
  316.             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
  317.             this.filter = filter;
  318.             this.needFirst = true;
  319.         }
  320.        
  321.         /// <summary>
  322.         /// Position this iterator to the next following node. Return false if there are no more following nodes.
  323.         /// Return true if the Current property is set to the next node in the iteration.
  324.         /// </summary>
  325.         public bool MoveNext()
  326.         {
  327.             if (this.needFirst) {
  328.                 if (!MoveFirst(this.filter, this.navCurrent))
  329.                     return false;
  330.                
  331.                 this.needFirst = false;
  332.                 return true;
  333.             }
  334.            
  335.             return this.filter.MoveToFollowing(this.navCurrent, null);
  336.         }
  337.        
  338.         /// <summary>
  339.         /// Return the current result navigator. This is only defined after MoveNext() has returned true.
  340.         /// </summary>
  341.         public XPathNavigator Current {
  342.             get { return this.navCurrent; }
  343.         }
  344.        
  345.         /// <summary>
  346.         /// Position "nav" to the matching node which follows it in document order but is not a descendant node.
  347.         /// Return false if this is no such matching node.
  348.         /// </summary>
  349.         static internal bool MoveFirst(XmlNavigatorFilter filter, XPathNavigator nav)
  350.         {
  351.             // Attributes and namespace nodes include descendants of their owner element in the set of following nodes
  352.             if (nav.NodeType == XPathNodeType.Attribute || nav.NodeType == XPathNodeType.Namespace) {
  353.                 if (!nav.MoveToParent()) {
  354.                     // Floating attribute or namespace node that has no following nodes
  355.                     return false;
  356.                 }
  357.                
  358.                 if (!filter.MoveToFollowing(nav, null)) {
  359.                     // No matching following nodes
  360.                     return false;
  361.                 }
  362.             }
  363.             else {
  364.                 // XPath spec doesn't include descendants of the input node in the following axis
  365.                 if (!nav.MoveToNonDescendant())
  366.                     // No following nodes
  367.                     return false;
  368.                
  369.                 // If the sibling does not match the node-test, find the next following node that does
  370.                 if (filter.IsFiltered(nav)) {
  371.                     if (!filter.MoveToFollowing(nav, null)) {
  372.                         // No matching following nodes
  373.                         return false;
  374.                     }
  375.                 }
  376.             }
  377.            
  378.             // Success
  379.             return true;
  380.         }
  381.     }
  382.    
  383.    
  384.     /// <summary>
  385.     /// Iterate over all following nodes according to XPath following axis rules. Merge multiple sets of following nodes
  386.     /// in document order and remove duplicates.
  387.     /// </summary>
  388.     [EditorBrowsable(EditorBrowsableState.Never)]
  389.     public struct XPathFollowingMergeIterator
  390.     {
  391.         private XmlNavigatorFilter filter;
  392.         private IteratorState state;
  393.         private XPathNavigator navCurrent, navNext;
  394.        
  395.         private enum IteratorState
  396.         {
  397.             NeedCandidateCurrent = 0,
  398.             HaveCandidateCurrent,
  399.             HaveCurrentNeedNext,
  400.             HaveCurrentHaveNext,
  401.             HaveCurrentNoNext
  402.         }
  403.        
  404.         /// <summary>
  405.         /// Initialize the XPathFollowingMergeIterator (merge multiple sets of following nodes in document order and remove duplicates).
  406.         /// </summary>
  407.         public void Create(XmlNavigatorFilter filter)
  408.         {
  409.             this.filter = filter;
  410.             this.state = IteratorState.NeedCandidateCurrent;
  411.         }
  412.        
  413.         /// <summary>
  414.         /// Position this iterator to the next following node. Prune by finding the first input node in
  415.         /// document order that has no other input nodes in its subtree. All other input nodes should be
  416.         /// discarded. Return IteratorResult.NeedInputNode if the next input node needs to be fetched
  417.         /// first. Return IteratorResult.HaveCurrent if the Current property is set to the next node in the
  418.         /// iteration.
  419.         /// </summary>
  420.         public IteratorResult MoveNext(XPathNavigator input)
  421.         {
  422.             switch (this.state) {
  423.                 case IteratorState.NeedCandidateCurrent:
  424.                     // If there are no more input nodes, then iteration is complete
  425.                     if (input == null)
  426.                         return IteratorResult.NoMoreNodes;
  427.                    
  428.                     // Save input node as current node
  429.                     this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
  430.                    
  431.                     // Still must check next input node to see if is a descendant of this one
  432.                     this.state = IteratorState.HaveCandidateCurrent;
  433.                     return IteratorResult.NeedInputNode;
  434.                 case IteratorState.HaveCandidateCurrent:
  435.                    
  436.                     // If there are no more input nodes,
  437.                     if (input == null) {
  438.                         // Then candidate node has been selected, and there are no further input nodes
  439.                         this.state = IteratorState.HaveCurrentNoNext;
  440.                         return MoveFirst();
  441.                     }
  442.                    
  443.                     // If input node is in the subtree of the candidate node, then use the input node instead
  444.                     if (this.navCurrent.IsDescendant(input))
  445.                         goto case IteratorState.NeedCandidateCurrent;
  446.                    
  447.                     // Found node on which to perform following scan. Now skip past all input nodes in the same document.
  448.                     this.state = IteratorState.HaveCurrentNeedNext;
  449.                     goto case IteratorState.HaveCurrentNeedNext;
  450.                     break;
  451.                 case IteratorState.HaveCurrentNeedNext:
  452.                    
  453.                     // If there are no more input nodes,
  454.                     if (input == null) {
  455.                         // Then candidate node has been selected, and there are no further input nodes
  456.                         this.state = IteratorState.HaveCurrentNoNext;
  457.                         return MoveFirst();
  458.                     }
  459.                    
  460.                     // Skip input node unless it's in a different document than the node on which the following scan was performed
  461.                     if (this.navCurrent.ComparePosition(input) != XmlNodeOrder.Unknown)
  462.                         return IteratorResult.NeedInputNode;
  463.                    
  464.                     // Next node is in a different document, so save it
  465.                     this.navNext = XmlQueryRuntime.SyncToNavigator(this.navNext, input);
  466.                     this.state = IteratorState.HaveCurrentHaveNext;
  467.                     return MoveFirst();
  468.             }
  469.            
  470.             if (!this.filter.MoveToFollowing(this.navCurrent, null))
  471.                 return MoveFailed();
  472.            
  473.             return IteratorResult.HaveCurrentNode;
  474.         }
  475.        
  476.         /// <summary>
  477.         /// Return the current result navigator. This is only defined after MoveNext() has returned true or IteratorResult.HaveCurrentNode.
  478.         /// </summary>
  479.         public XPathNavigator Current {
  480.             get { return this.navCurrent; }
  481.         }
  482.        
  483.         /// <summary>
  484.         /// Called when an attempt to move to a following node failed. If a Next node exists, then make that the new
  485.         /// candidate current node. Otherwise, iteration is complete.
  486.         /// </summary>
  487.         private IteratorResult MoveFailed()
  488.         {
  489.             XPathNavigator navTemp;
  490.             Debug.Assert(this.state == IteratorState.HaveCurrentHaveNext || this.state == IteratorState.HaveCurrentNoNext);
  491.            
  492.             if (this.state == IteratorState.HaveCurrentNoNext) {
  493.                 // No more nodes, so iteration is complete
  494.                 this.state = IteratorState.NeedCandidateCurrent;
  495.                 return IteratorResult.NoMoreNodes;
  496.             }
  497.            
  498.             // Make next node the new candidate node
  499.             this.state = IteratorState.HaveCandidateCurrent;
  500.            
  501.             // Swap navigators in order to sometimes avoid creating clones
  502.             navTemp = this.navCurrent;
  503.             this.navCurrent = this.navNext;
  504.             this.navNext = navTemp;
  505.            
  506.             return IteratorResult.NeedInputNode;
  507.         }
  508.        
  509.         /// <summary>
  510.         /// Position this.navCurrent to the node which follows it in document order but is not a descendant node.
  511.         /// </summary>
  512.         private IteratorResult MoveFirst()
  513.         {
  514.             Debug.Assert(this.state == IteratorState.HaveCurrentHaveNext || this.state == IteratorState.HaveCurrentNoNext);
  515.            
  516.             if (!XPathFollowingIterator.MoveFirst(this.filter, this.navCurrent))
  517.                 return MoveFailed();
  518.            
  519.             return IteratorResult.HaveCurrentNode;
  520.         }
  521.     }
  522.    
  523.    
  524.     /// <summary>
  525.     /// Iterate over all content-typed nodes which precede the starting node in document order. Return nodes
  526.     /// in reverse document order.
  527.     /// </summary>
  528.     [EditorBrowsable(EditorBrowsableState.Never)]
  529.     public struct PrecedingIterator
  530.     {
  531.         private XmlNavigatorStack stack;
  532.         private XPathNavigator navCurrent;
  533.        
  534.         /// <summary>
  535.         /// Initialize the PrecedingIterator (no possibility of duplicates).
  536.         /// </summary>
  537.         public void Create(XPathNavigator context, XmlNavigatorFilter filter)
  538.         {
  539.             // Start at root, which is always first node in the document
  540.             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, context);
  541.             this.navCurrent.MoveToRoot();
  542.            
  543.             // If root node is not the ending node,
  544.             if (!this.navCurrent.IsSamePosition(context)) {
  545.                 // Push root onto the stack if it is not filtered
  546.                 if (!filter.IsFiltered(this.navCurrent))
  547.                     this.stack.Push(this.navCurrent.Clone());
  548.                
  549.                 // Push all matching nodes onto stack
  550.                 while (filter.MoveToFollowing(this.navCurrent, context))
  551.                     this.stack.Push(this.navCurrent.Clone());
  552.             }
  553.         }
  554.        
  555.         /// <summary>
  556.         /// Return true if the Current property is set to the next Preceding node in reverse document order.
  557.         /// </summary>
  558.         public bool MoveNext()
  559.         {
  560.             if (stack.IsEmpty)
  561.                 return false;
  562.            
  563.             this.navCurrent = stack.Pop();
  564.             return true;
  565.         }
  566.        
  567.         /// <summary>
  568.         /// Return the current result navigator. This is only defined after MoveNext() has returned true.
  569.         /// </summary>
  570.         public XPathNavigator Current {
  571.             get { return this.navCurrent; }
  572.         }
  573.     }
  574.    
  575.    
  576.     /// <summary>
  577.     /// Iterate over all preceding nodes according to XPath preceding axis rules, returning nodes in reverse
  578.     /// document order. These rules specify that ancestors are not included, even though they precede the
  579.     /// starting node in document order. For the "true" preceding axis, see PrecedingIterator.
  580.     /// </summary>
  581.     [EditorBrowsable(EditorBrowsableState.Never)]
  582.     public struct XPathPrecedingIterator
  583.     {
  584.         private XmlNavigatorStack stack;
  585.         private XPathNavigator navCurrent;
  586.        
  587.         /// <summary>
  588.         /// Initialize the XPathPrecedingIterator (no possibility of duplicates).
  589.         /// </summary>
  590.         public void Create(XPathNavigator context, XmlNavigatorFilter filter)
  591.         {
  592.             XPathPrecedingDocOrderIterator wrapped = new XPathPrecedingDocOrderIterator();
  593.            
  594.             wrapped.Create(context, filter);
  595.            
  596.             // Fetch all preceding nodes in document order and push them onto the stack
  597.             while (wrapped.MoveNext())
  598.                 stack.Push(wrapped.Current.Clone());
  599.         }
  600.        
  601.         /// <summary>
  602.         /// Return true if the Current property is set to the next Preceding node in reverse document order.
  603.         /// </summary>
  604.         public bool MoveNext()
  605.         {
  606.             if (stack.IsEmpty)
  607.                 return false;
  608.            
  609.             this.navCurrent = stack.Pop();
  610.             return true;
  611.         }
  612.        
  613.         /// <summary>
  614.         /// Return the current result navigator. This is only defined after MoveNext() has returned true.
  615.         /// </summary>
  616.         public XPathNavigator Current {
  617.             get { return this.navCurrent; }
  618.         }
  619.     }
  620.    
  621.    
  622.     /// <summary>
  623.     /// Iterate over all preceding nodes according to XPath preceding axis rules, returning nodes in document order.
  624.     /// </summary>
  625.     [EditorBrowsable(EditorBrowsableState.Never)]
  626.     public struct XPathPrecedingDocOrderIterator
  627.     {
  628.         private XmlNavigatorFilter filter;
  629.         private XPathNavigator navCurrent;
  630.         private XmlNavigatorStack navStack;
  631.        
  632.         /// <summary>
  633.         /// Initialize the XPathPrecedingDocOrderIterator (return preceding nodes in document order, no possibility of duplicates).
  634.         /// </summary>
  635.         public void Create(XPathNavigator input, XmlNavigatorFilter filter)
  636.         {
  637.             // Save input node as current node
  638.             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
  639.             this.filter = filter;
  640.             PushAncestors();
  641.         }
  642.        
  643.         /// <summary>
  644.         /// Position this iterator to the next preceding node. Return false if there are no more preceding nodes.
  645.         /// Return true if the Current property is set to the next node in the iteration.
  646.         /// </summary>
  647.         public bool MoveNext()
  648.         {
  649.             if (!this.navStack.IsEmpty) {
  650.                 while (true) {
  651.                     // Move to the next matching node that is before the top node on the stack in document order
  652.                     if (this.filter.MoveToFollowing(this.navCurrent, this.navStack.Peek()))
  653.                         // Found match
  654.                         return true;
  655.                    
  656.                     // Do not include ancestor nodes as part of the preceding axis
  657.                     this.navCurrent.MoveTo(this.navStack.Pop());
  658.                    
  659.                     // No more preceding matches possible
  660.                     if (this.navStack.IsEmpty)
  661.                         break;
  662.                 }
  663.             }
  664.            
  665.             return false;
  666.         }
  667.        
  668.         /// <summary>
  669.         /// Return the current result navigator. This is only defined after MoveNext() has returned true or
  670.         /// IteratorResult.HaveCurrentNode.
  671.         /// </summary>
  672.         public XPathNavigator Current {
  673.             get { return this.navCurrent; }
  674.         }
  675.        
  676.         /// <summary>
  677.         /// Push all ancestors of this.navCurrent onto a stack. The set of preceding nodes should not contain any of these
  678.         /// ancestors.
  679.         /// </summary>
  680.         private void PushAncestors()
  681.         {
  682.             this.navStack.Reset();
  683.             do {
  684.                 this.navStack.Push(this.navCurrent.Clone());
  685.             }
  686.             while (this.navCurrent.MoveToParent());
  687.            
  688.             // Pop the root of the tree, since MoveToFollowing calls will never return it
  689.             this.navStack.Pop();
  690.         }
  691.     }
  692.    
  693.    
  694.     /// <summary>
  695.     /// Iterate over all preceding nodes according to XPath preceding axis rules, except that nodes are always
  696.     /// returned in document order. Merge multiple sets of preceding nodes in document order and remove duplicates.
  697.     /// </summary>
  698.     [EditorBrowsable(EditorBrowsableState.Never)]
  699.     public struct XPathPrecedingMergeIterator
  700.     {
  701.         private XmlNavigatorFilter filter;
  702.         private IteratorState state;
  703.         private XPathNavigator navCurrent, navNext;
  704.         private XmlNavigatorStack navStack;
  705.        
  706.         private enum IteratorState
  707.         {
  708.             NeedCandidateCurrent = 0,
  709.             HaveCandidateCurrent,
  710.             HaveCurrentHaveNext,
  711.             HaveCurrentNoNext
  712.         }
  713.        
  714.         /// <summary>
  715.         /// Initialize the XPathPrecedingMergeIterator (merge multiple sets of preceding nodes in document order and remove duplicates).
  716.         /// </summary>
  717.         public void Create(XmlNavigatorFilter filter)
  718.         {
  719.             this.filter = filter;
  720.             this.state = IteratorState.NeedCandidateCurrent;
  721.         }
  722.        
  723.         /// <summary>
  724.         /// Position this iterator to the next preceding node in document order. Discard all input nodes
  725.         /// that are followed by another input node in the same document. This leaves one node per document from
  726.         /// which the complete set of preceding nodes can be derived without possibility of duplicates.
  727.         /// Return IteratorResult.NeedInputNode if the next input node needs to be fetched first. Return
  728.         /// IteratorResult.HaveCurrent if the Current property is set to the next node in the iteration.
  729.         /// </summary>
  730.         public IteratorResult MoveNext(XPathNavigator input)
  731.         {
  732.             switch (this.state) {
  733.                 case IteratorState.NeedCandidateCurrent:
  734.                     // If there are no more input nodes, then iteration is complete
  735.                     if (input == null)
  736.                         return IteratorResult.NoMoreNodes;
  737.                    
  738.                     // Save input node as current node
  739.                     this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
  740.                    
  741.                     // Scan for additional input nodes within the same document (since they are after navCurrent in docorder)
  742.                     this.state = IteratorState.HaveCandidateCurrent;
  743.                     return IteratorResult.NeedInputNode;
  744.                 case IteratorState.HaveCandidateCurrent:
  745.                    
  746.                     // If there are no more input nodes,
  747.                     if (input == null) {
  748.                         // Then candidate node has been selected, and there are no further input nodes
  749.                         this.state = IteratorState.HaveCurrentNoNext;
  750.                     }
  751.                     else {
  752.                         // If the input node is in the same document as the current node,
  753.                         if (this.navCurrent.ComparePosition(input) != XmlNodeOrder.Unknown) {
  754.                             // Then update the current node and get the next input node
  755.                             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, input);
  756.                             return IteratorResult.NeedInputNode;
  757.                         }
  758.                        
  759.                         // Save the input node as navNext
  760.                         this.navNext = XmlQueryRuntime.SyncToNavigator(this.navNext, input);
  761.                         this.state = IteratorState.HaveCurrentHaveNext;
  762.                     }
  763.                     PushAncestors();
  764.                     break;
  765.             }
  766.            
  767.             if (!this.navStack.IsEmpty) {
  768.                 while (true) {
  769.                     // Move to the next matching node that is before the top node on the stack in document order
  770.                     if (this.filter.MoveToFollowing(this.navCurrent, this.navStack.Peek()))
  771.                         // Found match
  772.                         return IteratorResult.HaveCurrentNode;
  773.                    
  774.                     // Do not include ancestor nodes as part of the preceding axis
  775.                     this.navCurrent.MoveTo(this.navStack.Pop());
  776.                    
  777.                     // No more preceding matches possible
  778.                     if (this.navStack.IsEmpty)
  779.                         break;
  780.                 }
  781.             }
  782.            
  783.             if (this.state == IteratorState.HaveCurrentNoNext) {
  784.                 // No more nodes, so iteration is complete
  785.                 this.state = IteratorState.NeedCandidateCurrent;
  786.                 return IteratorResult.NoMoreNodes;
  787.             }
  788.            
  789.             // Make next node the current node and start trying to find input node greatest in docorder
  790.             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, this.navNext);
  791.             this.state = IteratorState.HaveCandidateCurrent;
  792.             return IteratorResult.HaveCurrentNode;
  793.         }
  794.        
  795.         /// <summary>
  796.         /// Return the current result navigator. This is only defined after MoveNext() has returned true or
  797.         /// IteratorResult.HaveCurrentNode.
  798.         /// </summary>
  799.         public XPathNavigator Current {
  800.             get { return this.navCurrent; }
  801.         }
  802.        
  803.         /// <summary>
  804.         /// Push all ancestors of this.navCurrent onto a stack. The set of preceding nodes should not contain any of these
  805.         /// ancestors.
  806.         /// </summary>
  807.         private void PushAncestors()
  808.         {
  809.             Debug.Assert(this.state == IteratorState.HaveCurrentHaveNext || this.state == IteratorState.HaveCurrentNoNext);
  810.            
  811.             this.navStack.Reset();
  812.             do {
  813.                 this.navStack.Push(this.navCurrent.Clone());
  814.             }
  815.             while (this.navCurrent.MoveToParent());
  816.            
  817.             // Pop the root of the tree, since MoveToFollowing calls will never return it
  818.             this.navStack.Pop();
  819.         }
  820.     }
  821.    
  822.    
  823.     /// <summary>
  824.     /// Iterate over these nodes in document order (filtering out those that do not match the filter test):
  825.     /// 1. Starting node
  826.     /// 2. All content-typed nodes which follow the starting node until the ending node is reached
  827.     /// 3. Ending node
  828.     ///
  829.     /// If the starting node is the same node as the ending node, iterate over the singleton node.
  830.     /// If the starting node is after the ending node, or is in a different document, iterate to the
  831.     /// end of the document.
  832.     /// </summary>
  833.     [EditorBrowsable(EditorBrowsableState.Never)]
  834.     public struct NodeRangeIterator
  835.     {
  836.         private XmlNavigatorFilter filter;
  837.         private XPathNavigator navCurrent, navEnd;
  838.         private IteratorState state;
  839.        
  840.         private enum IteratorState
  841.         {
  842.             HaveCurrent,
  843.             NeedCurrent,
  844.             HaveCurrentNoNext,
  845.             NoNext
  846.         }
  847.        
  848.         /// <summary>
  849.         /// Initialize the NodeRangeIterator (no possibility of duplicates).
  850.         /// </summary>
  851.         public void Create(XPathNavigator start, XmlNavigatorFilter filter, XPathNavigator end)
  852.         {
  853.             // Save start node as current node and save ending node
  854.             this.navCurrent = XmlQueryRuntime.SyncToNavigator(this.navCurrent, start);
  855.             this.navEnd = XmlQueryRuntime.SyncToNavigator(this.navEnd, end);
  856.             this.filter = filter;
  857.            
  858.             if (start.IsSamePosition(end)) {
  859.                 // Start is end, so only return node if it is not filtered
  860.                 this.state = !filter.IsFiltered(start) ? IteratorState.HaveCurrentNoNext : IteratorState.NoNext;
  861.             }
  862.             else {
  863.                 // Return nodes until end is reached
  864.                 this.state = !filter.IsFiltered(start) ? IteratorState.HaveCurrent : IteratorState.NeedCurrent;
  865.             }
  866.         }
  867.        
  868.         /// <summary>
  869.         /// Position this iterator to the next following node. Return false if there are no more following nodes,
  870.         /// or if the end node has been reached. Return true if the Current property is set to the next node in
  871.         /// the iteration.
  872.         /// </summary>
  873.         public bool MoveNext()
  874.         {
  875.             switch (this.state) {
  876.                 case IteratorState.HaveCurrent:
  877.                     this.state = IteratorState.NeedCurrent;
  878.                     return true;
  879.                 case IteratorState.NeedCurrent:
  880.                    
  881.                     // Move to next following node which matches
  882.                     if (!this.filter.MoveToFollowing(this.navCurrent, this.navEnd)) {
  883.                         // No more nodes unless ending node matches
  884.                         if (filter.IsFiltered(this.navEnd)) {
  885.                             this.state = IteratorState.NoNext;
  886.                             return false;
  887.                         }
  888.                        
  889.                         this.navCurrent.MoveTo(this.navEnd);
  890.                         this.state = IteratorState.NoNext;
  891.                     }
  892.                     return true;
  893.                 case IteratorState.HaveCurrentNoNext:
  894.                    
  895.                     this.state = IteratorState.NoNext;
  896.                     return true;
  897.             }
  898.            
  899.             Debug.Assert(this.state == IteratorState.NoNext, "Illegal state: " + this.state);
  900.             return false;
  901.         }
  902.        
  903.         /// <summary>
  904.         /// Return the current result navigator. This is only defined after MoveNext() has returned true.
  905.         /// </summary>
  906.         public XPathNavigator Current {
  907.             get { return this.navCurrent; }
  908.         }
  909.     }
  910. }

Developer Fusion