content: /*
   * $Header$
   * $Revision$
   * $Date$
   *
   * ====================================================================
   *
   * Copyright 2005 Elliotte Rusty Harold.
   * All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions are
   * met:
   * 
   *   * Redistributions of source code must retain the above copyright
   *     notice, this list of conditions and the following disclaimer.
   * 
   *   * Redistributions in binary form must reproduce the above copyright
   *     notice, this list of conditions and the following disclaimer in the
   *     documentation and/or other materials provided with the distribution.
   * 
   *   * Neither the name of the Jaxen Project nor the names of its
   *     contributors may be used to endorse or promote products derived 
   *     from this software without specific prior written permission.
   * 
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
   * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
   * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
   * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   *
   * ====================================================================
   * This software consists of voluntary contributions made by many 
   * individuals on behalf of the Jaxen Project and was originally 
   * created by bob mcwhirter <bob@werken.com> and 
   * James Strachan <jstrachan@apache.org>.  For more information on the 
   * Jaxen Project, please see <http://www.jaxen.org/>.
   * 
   * $Id$
   */
  package org.jaxen.expr;
  
  import java.util.Comparator;
  import java.util.Iterator;
  
  import org.jaxen.Navigator;
  import org.jaxen.UnsupportedAxisException;
  
  
  class NodeComparator implements Comparator {
      
      private Navigator navigator;
  
  
      NodeComparator(Navigator navigator) {
          this.navigator = navigator;
      }
      
      public int compare(Object o1, Object o2) {
          
      	if (o1 == o2) return 0;
      	
      	// treat all objects as equal
          if (navigator == null) return 0;
          
          if (isNonChild(o1) && isNonChild(o2)) {
              
              try {
                  Object p1 = navigator.getParentNode(o1);
                  Object p2 = navigator.getParentNode(o2);
              
                  if (p1 == p2) {
                      if (navigator.isNamespace(o1) && navigator.isAttribute(o2)) {
                          return -1;
                      }
                      else if (navigator.isNamespace(o2) && navigator.isAttribute(o1)) {
                          return 1;
                      }
                      else if (navigator.isNamespace(o1)) {
                      	String prefix1 = navigator.getNamespacePrefix(o1);
                      	String prefix2 = navigator.getNamespacePrefix(o2);
                      	return prefix1.compareTo(prefix2);
                      }
                      else if (navigator.isAttribute(o1)) {
                      	String name1 = navigator.getAttributeQName(o1);
                      	String name2 = navigator.getAttributeQName(o2);
                      	return name1.compareTo(name2);
                      }
                  }
  
                  return compare(p1, p2);
              }
              catch (UnsupportedAxisException ex) {
                  return 0;
              }
              
          }
  
          try {
              int depth1 = getDepth(o1);
              int depth2 = getDepth(o2);
              
              Object a1 = o1;
              Object a2 = o2;
                          
              while (depth1 > depth2) {
                  a1 = navigator.getParentNode(a1);
                  depth1--;
              }
              if (a1 == o2) return 1;
              
              while (depth2 > depth1) {
                  a2 = navigator.getParentNode(a2);
                  depth2--;
              }
              if (a2 == o1) return -1;
              
              // a1 and a2 are now at same depth; and are not the same
              while (true) {
                  Object p1 = navigator.getParentNode(a1);
                  Object p2 = navigator.getParentNode(a2);
                  if (p1 == p2) {
                      return compareSiblings(a1, a2);
                  }
                  a1 = p1;
                  a2 = p2;
              }
              
          }
          catch (UnsupportedAxisException ex) {
              return 0; // ???? should I throw an exception instead?
          }
      }
      
  
      private boolean isNonChild(Object o) {
          return navigator.isAttribute(o) || navigator.isNamespace(o);
      }
  
      private int compareSiblings(Object sib1, Object sib2) 
        throws UnsupportedAxisException {
  
      	// attributes and namespaces sort before child nodes 
      	if (isNonChild(sib1)) {
      		return 1;
      	} else if (isNonChild(sib2)) {
      		return -1;
      	}
      	
          Iterator following = navigator.getFollowingSiblingAxisIterator(sib1);
          while (following.hasNext()) {
              Object next = following.next();
              if (next.equals(sib2)) return -1;
          }
          return 1;
          
      }
  
      private int getDepth(Object o) throws UnsupportedAxisException {
  
          int depth = 0;
          Object parent = o;
          
          while ((parent = navigator.getParentNode(parent)) != null) {
              depth++;
          }
          return depth;
          
      }
      
  }
  