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

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

Developer Fusion