mcs/class/System.Xml.Linq/System.Xml.Linq/XNodeDocumentOrderComparer.cs

   1 //
   2 // Authors:
   3 //   Atsushi Enomoto
   4 //
   5 // Copyright 2007 Novell (http://www.novell.com)
   6 //
   7 // Permission is hereby granted, free of charge, to any person obtaining
   8 // a copy of this software and associated documentation files (the
   9 // "Software"), to deal in the Software without restriction, including
  10 // without limitation the rights to use, copy, modify, merge, publish,
  11 // distribute, sublicense, and/or sell copies of the Software, and to
  12 // permit persons to whom the Software is furnished to do so, subject to
  13 // the following conditions:
  14 //
  15 // The above copyright notice and this permission notice shall be
  16 // included in all copies or substantial portions of the Software.
  17 //
  18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  22 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  23 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  24 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25 //
  26
  27 using System;
  28 using System.Collections;
  29 using System.Collections.Generic;
  30
  31 namespace System.Xml.Linq
  32 {
  33         public sealed class XNodeDocumentOrderComparer : IComparer, IComparer<XNode>
  34         {
  35                 public XNodeDocumentOrderComparer ()
  36                 {
  37                 }
  38
  39                 enum CompareResult
  40                 {
  41                         Same,
  42                         Random,
  43                         Parent,
  44                         Child,
  45                         Ancestor,
  46                         Descendant,
  47                         Preceding,
  48                         Following
  49                 }
  50
  51                 public int Compare (XNode x, XNode y)
  52                 {
  53                         switch (CompareCore (x,y)) {
  54                         case CompareResult.Same:
  55                                 return 0;
  56                         case CompareResult.Random:
  57                                 return DateTime.Now.Ticks % 2 == 1 ? 1 : -1;
  58                         case CompareResult.Parent:
  59                         case CompareResult.Ancestor:
  60                         case CompareResult.Preceding:
  61                                 return 1;
  62                         default:
  63                                 return -1;
  64                         }
  65                 }
  66
  67                 CompareResult CompareCore (XNode n1, XNode n2)
  68                 {
  69                         if (n1 == n2)
  70                                 return CompareResult.Same;
  71                         if (n1.Owner == null) {
  72                                 if (n2.Owner == null)
  73                                         // n1 and n2 do not share the same
  74                                         // top-level node, so return semi-
  75                                         // random value.
  76                                         return CompareResult.Random;
  77
  78                                 CompareResult result = CompareCore (n1, n2.Owner);
  79                                 switch (result) {
  80                                 case CompareResult.Same:
  81                                         return CompareResult.Child;
  82                                 case CompareResult.Child:
  83                                 case CompareResult.Descendant:
  84                                         return CompareResult.Descendant;
  85                                 case CompareResult.Parent:
  86                                 case CompareResult.Ancestor:
  87                                         throw new Exception ("INTERNAL ERROR: should not happen");
  88                                 default:
  89                                         return result;
  90                                 }
  91                         }
  92                         // else
  93                         if (n2.Owner == null) {
  94                                 // do reverse
  95                                 CompareResult rev = CompareCore (n2, n1);
  96                                 switch (rev) {
  97                                 case CompareResult.Parent:
  98                                         return CompareResult.Child;
  99                                 case CompareResult.Child:
 100                                         return CompareResult.Parent;
 101                                 case CompareResult.Ancestor:
 102                                         return CompareResult.Descendant;
 103                                 case CompareResult.Descendant:
 104                                         return CompareResult.Ancestor;
 105                                 case CompareResult.Following:
 106                                         return CompareResult.Preceding;
 107                                 case CompareResult.Preceding:
 108                                         return CompareResult.Following;
 109                                 case CompareResult.Same:
 110                                 case CompareResult.Random:
 111                                         return rev;
 112                                 }
 113                         }
 114                         // both have parents
 115                         CompareResult ret = CompareCore (n1.Owner, n2.Owner);
 116                         switch (ret) {
 117                         case CompareResult.Same:
 118                                 // n1 and n2 are sibling each other.
 119                                 return CompareSibling (n1, n2, CompareResult.Same);
 120                         case CompareResult.Child:
 121                                 return CompareSibling (n1, n2.Owner, CompareResult.Child);
 122                         case CompareResult.Parent:
 123                                 return CompareSibling (n1.Owner, n2, CompareResult.Parent);
 124                         case CompareResult.Descendant:
 125                                 for (XNode i2 = n2; ; i2 = i2.Owner)
 126                                         if (i2.Owner == n1.Owner)
 127                                                 return CompareSibling (n1, i2, CompareResult.Descendant);
 128                         case CompareResult.Ancestor:
 129                                 for (XNode i1 = n1; ; i1 = i1.Owner)
 130                                         if (i1.Owner == n2.Owner)
 131                                                 return CompareSibling (i1, n2, CompareResult.Ancestor);
 132                         default:
 133                                 return ret;
 134                         }
 135                 }
 136
 137                 // results are returned as following/preceding, as it is also
 138                 // used for comparing parents.
 139                 CompareResult CompareSibling (XNode n1, XNode n2, CompareResult forSameValue)
 140                 {
 141                         if (n1 == n2)
 142                                 return forSameValue;
 143
 144                         for (XNode n = n1.NextNode; n != null; n = n.NextNode)
 145                                 if (n == n2)
 146                                         return CompareResult.Following;
 147                         return CompareResult.Preceding;
 148                 }
 149
 150                 int IComparer.Compare (object n1, object n2)
 151                 {
 152                         return Compare ((XNode) n1, (XNode) n2);
 153                 }
 154         }
 155 }