//
// Authors:
// Atsushi Enomoto
//
// Copyright 2007 Novell (http://www.novell.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
using System;
using System.Collections;
using System.Collections.Generic;
namespace System.Xml.Linq{
public sealed class XNodeDocumentOrderComparer : IComparer, IComparer<XNode>
{
public XNodeDocumentOrderComparer ()
{
}
enum CompareResult
{
Same,
Random,
Parent,
Child,
Ancestor,
Descendant,
Preceding,
Following
}
public int Compare (XNode n1, XNode n2)
{
switch (CompareCore (n1, n2)) {
case CompareResult.Same:
return 0;
case CompareResult.Random:
return DateTime.Now.Ticks % 2 == 1 ? 1 : -1;
case CompareResult.Parent:
case CompareResult.Ancestor:
case CompareResult.Preceding:
return 1;
default:
return -1;
}
}
CompareResult CompareCore (XNode n1, XNode n2)
{
if (n1 == n2)
return CompareResult.Same;
if (n1.Owner == null) {
if (n2.Owner == null)
// n1 and n2 do not share the same
// top-level node, so return semi-
// random value.
return CompareResult.Random;
CompareResult result = CompareCore (n1, n2.Owner);
switch (result) {
case CompareResult.Same:
return CompareResult.Child;
case CompareResult.Child:
case CompareResult.Descendant:
return CompareResult.Descendant;
case CompareResult.Parent:
case CompareResult.Ancestor:
throw new Exception ("INTERNAL ERROR: should not happen");
default:
return result;
}
}
// else
if (n2.Owner == null) {
// do reverse
CompareResult rev = CompareCore (n2, n1);
switch (rev) {
case CompareResult.Parent:
return CompareResult.Child;
case CompareResult.Child:
return CompareResult.Parent;
case CompareResult.Ancestor:
return CompareResult.Descendant;
case CompareResult.Descendant:
return CompareResult.Ancestor;
case CompareResult.Following:
return CompareResult.Preceding;
case CompareResult.Preceding:
return CompareResult.Following;
case CompareResult.Same:
case CompareResult.Random:
return rev;
}
}
// both have parents
CompareResult ret = CompareCore (n1.Owner, n2.Owner);
switch (ret) {
case CompareResult.Same:
// n1 and n2 are sibling each other.
return CompareSibling (n1, n2, CompareResult.Same);
case CompareResult.Child:
return CompareSibling (n1, n2.Owner, CompareResult.Child);
case CompareResult.Parent:
return CompareSibling (n1.Owner, n2, CompareResult.Parent);
case CompareResult.Descendant:
for (XNode i2 = n2; ; i2 = i2.Owner)
if (i2.Owner == n1.Owner)
return CompareSibling (n1, i2, CompareResult.Descendant);
case CompareResult.Ancestor:
for (XNode i1 = n1; ; i1 = i1.Owner)
if (i1.Owner == n2.Owner)
return CompareSibling (i1, n2, CompareResult.Ancestor);
default:
return ret;
}
}
// results are returned as following/preceding, as it is also
// used for comparing parents.
CompareResult CompareSibling (XNode n1, XNode n2, CompareResult forSameValue)
{
if (n1 == n2)
return forSameValue;
for (XNode n = n1.NextNode; n != null; n = n.NextNode)
if (n == n2)
return CompareResult.Following;
return CompareResult.Preceding;
}
int IComparer.Compare (object n1, object n2)
{
return Compare ((XNode) n1, (XNode) n2);
}
}
}
|