mcs/class/referencesource/System.Data.SqlXml/System/Xml/Xsl/Runtime/SetIterators.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="SetIterators.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</owner>
   6 //------------------------------------------------------------------------------
   7 using System;
   8 using System.Xml;
   9 using System.Xml.XPath;
  10 using System.Xml.Schema;
  11 using System.Diagnostics;
  12 using System.Collections;
  13 using System.ComponentModel;
  14
  15 namespace System.Xml.Xsl.Runtime {
  16
  17     /// <summary>
  18     /// Set iterators (Union, Intersection, Difference) that use containment to control two nested iterators return
  19     /// one of the following values from MoveNext().
  20     /// </summary>
  21     [EditorBrowsable(EditorBrowsableState.Never)]
  22     public enum SetIteratorResult {
  23         NoMoreNodes,                // Iteration is complete; there are no more nodes
  24         InitRightIterator,          // Initialize right nested iterator
  25         NeedLeftNode,               // The next node needs to be fetched from the left nested iterator
  26         NeedRightNode,              // The next node needs to be fetched from the right nested iterator
  27         HaveCurrentNode,            // This iterator's Current property is set to the next node in the iteration
  28     };
  29
  30
  31     /// <summary>
  32     /// This iterator manages two sets of nodes that are already in document order with no duplicates.
  33     /// Using a merge sort, this operator returns the union of these sets in document order with no duplicates.
  34     /// </summary>
  35     [EditorBrowsable(EditorBrowsableState.Never)]
  36     public struct UnionIterator {
  37         private XmlQueryRuntime runtime;
  38         private XPathNavigator navCurr, navOther;
  39         private IteratorState state;
  40
  41         private enum IteratorState {
  42             InitLeft = 0,
  43             NeedLeft,
  44             NeedRight,
  45             LeftIsCurrent,
  46             RightIsCurrent,
  47         };
  48
  49         /// <summary>
  50         /// Create SetIterator.
  51         /// </summary>
  52         public void Create(XmlQueryRuntime runtime) {
  53             this.runtime = runtime;
  54             this.state = IteratorState.InitLeft;
  55         }
  56
  57         /// <summary>
  58         /// Position this iterator to the next node in the union.
  59         /// </summary>
  60         public SetIteratorResult MoveNext(XPathNavigator nestedNavigator) {
  61             switch (this.state) {
  62                 case IteratorState.InitLeft:
  63                     // Fetched node from left iterator, now get initial node from right iterator
  64                     this.navOther = nestedNavigator;
  65                     this.state = IteratorState.NeedRight;
  66                     return SetIteratorResult.InitRightIterator;
  67
  68                 case IteratorState.NeedLeft:
  69                     this.navCurr = nestedNavigator;
  70                     this.state = IteratorState.LeftIsCurrent;
  71                     break;
  72
  73                 case IteratorState.NeedRight:
  74                     this.navCurr = nestedNavigator;
  75                     this.state = IteratorState.RightIsCurrent;
  76                     break;
  77
  78                 case IteratorState.LeftIsCurrent:
  79                     // Just returned left node as current, so get new left
  80                     this.state = IteratorState.NeedLeft;
  81                     return SetIteratorResult.NeedLeftNode;
  82
  83                 case IteratorState.RightIsCurrent:
  84                     // Just returned right node as current, so get new right
  85                     this.state = IteratorState.NeedRight;
  86                     return SetIteratorResult.NeedRightNode;
  87             }
  88
  89             // Merge left and right nodes
  90             if (this.navCurr == null) {
  91                 // If both navCurr and navOther are null, then iteration is complete
  92                 if (this.navOther == null)
  93                     return SetIteratorResult.NoMoreNodes;
  94
  95                 Swap();
  96             }
  97             else if (this.navOther != null) {
  98                 int order = this.runtime.ComparePosition(this.navOther, this.navCurr);
  99
 100                 // If navCurr is positioned to same node as navOther,
 101                 if (order == 0) {
 102                     // Skip navCurr, since it is a duplicate
 103                     if (this.state == IteratorState.LeftIsCurrent) {
 104                         this.state = IteratorState.NeedLeft;
 105                         return SetIteratorResult.NeedLeftNode;
 106                     }
 107
 108                     this.state = IteratorState.NeedRight;
 109                     return SetIteratorResult.NeedRightNode;
 110                 }
 111
 112                 // If navOther is before navCurr in document order, then swap navCurr with navOther
 113                 if (order < 0)
 114                     Swap();
 115             }
 116
 117             // Return navCurr
 118             return SetIteratorResult.HaveCurrentNode;
 119         }
 120
 121         /// <summary>
 122         /// Return the current result navigator.  This is only defined after MoveNext() has returned -1.
 123         /// </summary>
 124         public XPathNavigator Current {
 125             get { return this.navCurr; }
 126         }
 127
 128         /// <summary>
 129         /// Swap navCurr with navOther and invert state to reflect the change.
 130         /// </summary>
 131         private void Swap() {
 132             XPathNavigator navTemp = this.navCurr;
 133             this.navCurr = this.navOther;
 134             this.navOther = navTemp;
 135
 136             if (this.state == IteratorState.LeftIsCurrent)
 137                 this.state = IteratorState.RightIsCurrent;
 138             else
 139                 this.state = IteratorState.LeftIsCurrent;
 140         }
 141     }
 142
 143
 144     /// <summary>
 145     /// This iterator manages two sets of nodes that are already in document order with no duplicates.
 146     /// This iterator returns the intersection of these sets in document order with no duplicates.
 147     /// </summary>
 148     [EditorBrowsable(EditorBrowsableState.Never)]
 149     public struct IntersectIterator {
 150         private XmlQueryRuntime runtime;
 151         private XPathNavigator navLeft, navRight;
 152         private IteratorState state;
 153
 154         private enum IteratorState {
 155             InitLeft = 0,
 156             NeedLeft,
 157             NeedRight,
 158             NeedLeftAndRight,
 159             HaveCurrent,
 160         };
 161
 162         /// <summary>
 163         /// Create IntersectIterator.
 164         /// </summary>
 165         public void Create(XmlQueryRuntime runtime) {
 166             this.runtime = runtime;
 167             this.state = IteratorState.InitLeft;
 168         }
 169
 170         /// <summary>
 171         /// Position this iterator to the next node in the union.
 172         /// </summary>
 173         public SetIteratorResult MoveNext(XPathNavigator nestedNavigator) {
 174             int order;
 175
 176             switch (this.state) {
 177                 case IteratorState.InitLeft:
 178                     // Fetched node from left iterator, now get initial node from right iterator
 179                     this.navLeft = nestedNavigator;
 180                     this.state = IteratorState.NeedRight;
 181                     return SetIteratorResult.InitRightIterator;
 182
 183                 case IteratorState.NeedLeft:
 184                     this.navLeft = nestedNavigator;
 185                     break;
 186
 187                 case IteratorState.NeedRight:
 188                     this.navRight = nestedNavigator;
 189                     break;
 190
 191                 case IteratorState.NeedLeftAndRight:
 192                     // After fetching left node, still need right node
 193                     this.navLeft = nestedNavigator;
 194                     this.state = IteratorState.NeedRight;
 195                     return SetIteratorResult.NeedRightNode;
 196
 197                 case IteratorState.HaveCurrent:
 198                     // Just returned left node as current, so fetch new left and right nodes
 199                     Debug.Assert(nestedNavigator == null, "null is passed to MoveNext after IteratorState.HaveCurrent has been returned.");
 200                     this.state = IteratorState.NeedLeftAndRight;
 201                     return SetIteratorResult.NeedLeftNode;
 202             }
 203
 204             if (this.navLeft == null || this.navRight == null) {
 205                 // No more nodes from either left or right iterator (or both), so iteration is complete
 206                 return SetIteratorResult.NoMoreNodes;
 207             }
 208
 209             // Intersect left and right sets
 210             order = this.runtime.ComparePosition(this.navLeft, this.navRight);
 211
 212             if (order < 0) {
 213                 // If navLeft is positioned to a node that is before navRight, skip left node
 214                 this.state = IteratorState.NeedLeft;
 215                 return SetIteratorResult.NeedLeftNode;
 216             }
 217             else if (order > 0) {
 218                 // If navLeft is positioned to a node that is after navRight, so skip right node
 219                 this.state = IteratorState.NeedRight;
 220                 return SetIteratorResult.NeedRightNode;
 221             }
 222
 223             // Otherwise, navLeft is positioned to the same node as navRight, so found one item in the intersection
 224             this.state = IteratorState.HaveCurrent;
 225             return SetIteratorResult.HaveCurrentNode;
 226         }
 227
 228         /// <summary>
 229         /// Return the current result navigator.  This is only defined after MoveNext() has returned -1.
 230         /// </summary>
 231         public XPathNavigator Current {
 232             get { return this.navLeft; }
 233         }
 234     }
 235
 236
 237     /// <summary>
 238     /// This iterator manages two sets of nodes that are already in document order with no duplicates.
 239     /// This iterator returns the difference of these sets (Left - Right) in document order with no duplicates.
 240     /// </summary>
 241     [EditorBrowsable(EditorBrowsableState.Never)]
 242     public struct DifferenceIterator {
 243         private XmlQueryRuntime runtime;
 244         private XPathNavigator navLeft, navRight;
 245         private IteratorState state;
 246
 247         private enum IteratorState {
 248             InitLeft = 0,
 249             NeedLeft,
 250             NeedRight,
 251             NeedLeftAndRight,
 252             HaveCurrent,
 253         };
 254
 255         /// <summary>
 256         /// Create DifferenceIterator.
 257         /// </summary>
 258         public void Create(XmlQueryRuntime runtime) {
 259             this.runtime = runtime;
 260             this.state = IteratorState.InitLeft;
 261         }
 262
 263         /// <summary>
 264         /// Position this iterator to the next node in the union.
 265         /// </summary>
 266         public SetIteratorResult MoveNext(XPathNavigator nestedNavigator) {
 267             switch (this.state) {
 268                 case IteratorState.InitLeft:
 269                     // Fetched node from left iterator, now get initial node from right iterator
 270                     this.navLeft = nestedNavigator;
 271                     this.state = IteratorState.NeedRight;
 272                     return SetIteratorResult.InitRightIterator;
 273
 274                 case IteratorState.NeedLeft:
 275                     this.navLeft = nestedNavigator;
 276                     break;
 277
 278                 case IteratorState.NeedRight:
 279                     this.navRight = nestedNavigator;
 280                     break;
 281
 282                 case IteratorState.NeedLeftAndRight:
 283                     // After fetching left node, still need right node
 284                     this.navLeft = nestedNavigator;
 285                     this.state = IteratorState.NeedRight;
 286                     return SetIteratorResult.NeedRightNode;
 287
 288                 case IteratorState.HaveCurrent:
 289                     // Just returned left node as current, so fetch new left node
 290                     Debug.Assert(nestedNavigator == null, "null is passed to MoveNext after IteratorState.HaveCurrent has been returned.");
 291                     this.state = IteratorState.NeedLeft;
 292                     return SetIteratorResult.NeedLeftNode;
 293             }
 294
 295             if (this.navLeft == null) {
 296                 // If navLeft is null, then difference operation is complete
 297                 return SetIteratorResult.NoMoreNodes;
 298             }
 299             else if (this.navRight != null) {
 300                 int order = this.runtime.ComparePosition(this.navLeft, this.navRight);
 301
 302                 // If navLeft is positioned to same node as navRight,
 303                 if (order == 0) {
 304                     // Skip navLeft and navRight
 305                     this.state = IteratorState.NeedLeftAndRight;
 306                     return SetIteratorResult.NeedLeftNode;
 307                 }
 308
 309                 // If navLeft is after navRight in document order, then skip navRight
 310                 if (order > 0) {
 311                     this.state = IteratorState.NeedRight;
 312                     return SetIteratorResult.NeedRightNode;
 313                 }
 314             }
 315
 316             // Return navLeft
 317             this.state = IteratorState.HaveCurrent;
 318             return SetIteratorResult.HaveCurrentNode;
 319         }
 320
 321         /// <summary>
 322         /// Return the current result navigator.  This is only defined after MoveNext() has returned -1.
 323         /// </summary>
 324         public XPathNavigator Current {
 325             get { return this.navLeft; }
 326         }
 327     }
 328 }