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

   1 //------------------------------------------------------------------------------
   2 // <copyright file="DodSequenceMerge.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">[....]</owner>
   6 //------------------------------------------------------------------------------
   7 using System;
   8 using System.Collections.Generic;
   9 using System.Xml.XPath;
  10 using System.Diagnostics;
  11 using System.Globalization;
  12 using System.ComponentModel;
  13
  14 namespace System.Xml.Xsl.Runtime {
  15
  16     /// <summary>
  17     /// Merges several doc-order-distinct sequences into a single doc-order-distinct sequence.
  18     /// </summary>
  19     [EditorBrowsable(EditorBrowsableState.Never)]
  20     public struct DodSequenceMerge {
  21         private IList<XPathNavigator> firstSequence;
  22         private List<IEnumerator<XPathNavigator>> sequencesToMerge;
  23         private int nodeCount;
  24         private XmlQueryRuntime runtime;
  25
  26         /// <summary>
  27         /// Initialize this instance of DodSequenceMerge.
  28         /// </summary>
  29         public void Create(XmlQueryRuntime runtime) {
  30             this.firstSequence = null;
  31             this.sequencesToMerge = null;
  32             this.nodeCount = 0;
  33             this.runtime = runtime;
  34         }
  35
  36         /// <summary>
  37         /// Add a new sequence to the list of sequences to merge.
  38         /// </summary>
  39         public void AddSequence(IList<XPathNavigator> sequence) {
  40             // Ignore empty sequences
  41             if (sequence.Count == 0)
  42                 return;
  43
  44             if (this.firstSequence == null) {
  45                 this.firstSequence = sequence;
  46             }
  47             else {
  48                 if (this.sequencesToMerge == null) {
  49                     this.sequencesToMerge = new List<IEnumerator<XPathNavigator>>();
  50                     MoveAndInsertSequence(this.firstSequence.GetEnumerator());
  51                     this.nodeCount = this.firstSequence.Count;
  52                 }
  53
  54                 MoveAndInsertSequence(sequence.GetEnumerator());
  55                 this.nodeCount += sequence.Count;
  56             }
  57         }
  58
  59         /// <summary>
  60         /// Return the fully merged sequence.
  61         /// </summary>
  62         public IList<XPathNavigator> MergeSequences() {
  63             XmlQueryNodeSequence newSequence;
  64
  65             // Zero sequences to merge
  66             if (this.firstSequence == null)
  67                 return XmlQueryNodeSequence.Empty;
  68
  69             // One sequence to merge
  70             if (this.sequencesToMerge == null || this.sequencesToMerge.Count <= 1)
  71                 return this.firstSequence;
  72
  73             // Two or more sequences to merge
  74             newSequence = new XmlQueryNodeSequence(this.nodeCount);
  75
  76             while (this.sequencesToMerge.Count != 1) {
  77                 // Save last item in list in temp variable, and remove it from list
  78                 IEnumerator<XPathNavigator> sequence = this.sequencesToMerge[this.sequencesToMerge.Count - 1];
  79                 this.sequencesToMerge.RemoveAt(this.sequencesToMerge.Count - 1);
  80
  81                 // Add current node to merged sequence
  82                 newSequence.Add(sequence.Current);
  83
  84                 // Now move to the next node, and re-insert it into the list in reverse document order
  85                 MoveAndInsertSequence(sequence);
  86             }
  87
  88             // Add nodes in remaining sequence to end of list
  89             Debug.Assert(this.sequencesToMerge.Count == 1, "While loop should terminate when count == 1");
  90             do {
  91                 newSequence.Add(this.sequencesToMerge[0].Current);
  92             }
  93             while (this.sequencesToMerge[0].MoveNext());
  94
  95             return newSequence;
  96         }
  97
  98         /// <summary>
  99         /// Move to the next item in the sequence.  If there is no next item, then do not
 100         /// insert the sequence.  Otherwise, call InsertSequence.
 101         /// </summary>
 102         private void MoveAndInsertSequence(IEnumerator<XPathNavigator> sequence) {
 103             if (sequence.MoveNext())
 104                 InsertSequence(sequence);
 105         }
 106
 107         /// <summary>
 108         /// Insert the specified sequence into the list of sequences to be merged.
 109         /// Insert it in reverse document order with respect to the current nodes in other sequences.
 110         /// </summary>
 111         private void InsertSequence(IEnumerator<XPathNavigator> sequence) {
 112             for (int i = this.sequencesToMerge.Count - 1; i >= 0; i--) {
 113                 int cmp = this.runtime.ComparePosition(sequence.Current, this.sequencesToMerge[i].Current);
 114
 115                 if (cmp == -1) {
 116                     // Insert after current item
 117                     this.sequencesToMerge.Insert(i + 1, sequence);
 118                     return;
 119                 }
 120                 else if (cmp == 0) {
 121                     // Found duplicate, so skip the duplicate
 122                     if (!sequence.MoveNext()) {
 123                         // No more nodes, so don't insert anything
 124                         return;
 125                     }
 126
 127                     // Next node must be after current node in document order, so don't need to reset loop
 128                 }
 129             }
 130
 131             // Insert at beginning of list
 132             this.sequencesToMerge.Insert(0, sequence);
 133         }
 134     }
 135 }
 136