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

   1 //------------------------------------------------------------------------------
   2 // <copyright file="DocumentOrderComparer.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.Collections;
   9 using System.Collections.Generic;
  10 using System.Xml;
  11 using System.Xml.XPath;
  12 using System.Diagnostics;
  13
  14 namespace System.Xml.Xsl.Runtime {
  15
  16     /// <summary>
  17     /// IComparer implementation that orders navigators based on ComparePosition.  When ComparePosition returns
  18     /// XmlNodeOrder.Unknown, a stable order between documents is maintained by an ordered list mapping each root node
  19     /// to an ordering index.
  20     /// </summary>
  21     internal class DocumentOrderComparer : IComparer<XPathNavigator> {
  22         private List<XPathNavigator> roots;
  23
  24         /// <summary>
  25         /// Return:
  26         ///     -1 if navThis is positioned before navThat
  27         ///      0 if navThis has the same position as navThat
  28         ///      1 if navThis is positioned after navThat
  29         /// </summary>
  30         public int Compare(XPathNavigator navThis, XPathNavigator navThat) {
  31             switch (navThis.ComparePosition(navThat)) {
  32                 case XmlNodeOrder.Before: return -1;
  33                 case XmlNodeOrder.Same: return 0;
  34                 case XmlNodeOrder.After: return 1;
  35             }
  36
  37             // Use this.roots to impose stable ordering
  38             if (this.roots == null)
  39                 this.roots = new List<XPathNavigator>();
  40
  41             Debug.Assert(GetDocumentIndex(navThis) != GetDocumentIndex(navThat));
  42             return GetDocumentIndex(navThis) < GetDocumentIndex(navThat) ? -1 : 1;
  43         }
  44
  45         /// <summary>
  46         /// Map navigator's document to a unique index.
  47         /// When consecutive calls are made to GetIndexOfNavigator for navThis and navThat, it is not possible
  48         /// for them to return the same index.  navThis compared to navThat is always XmlNodeOrder.Unknown.
  49         /// Therefore, no matter where navThis is inserted in the list, navThat will never be inserted just
  50         /// before navThis, and therefore will never have the same index.
  51         /// </summary>
  52         public int GetDocumentIndex(XPathNavigator nav) {
  53             XPathNavigator navRoot;
  54
  55             // Use this.roots to impose stable ordering
  56             if (this.roots == null)
  57                 this.roots = new List<XPathNavigator>();
  58
  59             // Position navigator to root
  60             navRoot = nav.Clone();
  61             navRoot.MoveToRoot();
  62
  63             for (int idx = 0; idx < this.roots.Count; idx++) {
  64                 if (navRoot.IsSamePosition(this.roots[idx])) {
  65                     // navigator's document was previously mapped to a unique index
  66                     return idx;
  67                 }
  68             }
  69
  70             // Add navigator to this.roots mapping
  71             this.roots.Add(navRoot);
  72
  73             return this.roots.Count - 1;
  74         }
  75     }
  76 }