/*
 * $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 (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;
                    }
                }

                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 {

        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;
        
    }
    
}
