View Javadoc

1   /*
2    * $Header$
3    * $Revision$
4    * $Date$
5    *
6    * ====================================================================
7    *
8    * Copyright 2005 Elliotte Rusty Harold.
9    * All rights reserved.
10   *
11   * Redistribution and use in source and binary forms, with or without
12   * modification, are permitted provided that the following conditions are
13   * met:
14   * 
15   *   * Redistributions of source code must retain the above copyright
16   *     notice, this list of conditions and the following disclaimer.
17   * 
18   *   * Redistributions in binary form must reproduce the above copyright
19   *     notice, this list of conditions and the following disclaimer in the
20   *     documentation and/or other materials provided with the distribution.
21   * 
22   *   * Neither the name of the Jaxen Project nor the names of its
23   *     contributors may be used to endorse or promote products derived 
24   *     from this software without specific prior written permission.
25   * 
26   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
27   * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
28   * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
29   * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
30   * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34   * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35   * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37   *
38   * ====================================================================
39   * This software consists of voluntary contributions made by many 
40   * individuals on behalf of the Jaxen Project and was originally 
41   * created by bob mcwhirter <bob@werken.com> and 
42   * James Strachan <jstrachan@apache.org>.  For more information on the 
43   * Jaxen Project, please see <http://www.jaxen.org/>.
44   * 
45   * $Id$
46   */
47  package org.jaxen.expr;
48  
49  import java.util.Comparator;
50  import java.util.Iterator;
51  
52  import org.jaxen.Navigator;
53  import org.jaxen.UnsupportedAxisException;
54  
55  
56  class NodeComparator implements Comparator {
57      
58      private Navigator navigator;
59  
60  
61      NodeComparator(Navigator navigator) {
62          this.navigator = navigator;
63      }
64      
65      public int compare(Object o1, Object o2) {
66          
67      	if (o1 == o2) return 0;
68      	
69      	// treat all objects as equal
70          if (navigator == null) return 0;
71          
72          if (isNonChild(o1) && isNonChild(o2)) {
73              
74              try {
75                  Object p1 = navigator.getParentNode(o1);
76                  Object p2 = navigator.getParentNode(o2);
77              
78                  if (p1 == p2) {
79                      if (navigator.isNamespace(o1) && navigator.isAttribute(o2)) {
80                          return -1;
81                      }
82                      else if (navigator.isNamespace(o2) && navigator.isAttribute(o1)) {
83                          return 1;
84                      }
85                      else if (navigator.isNamespace(o1)) {
86                      	String prefix1 = navigator.getNamespacePrefix(o1);
87                      	String prefix2 = navigator.getNamespacePrefix(o2);
88                      	return prefix1.compareTo(prefix2);
89                      }
90                      else if (navigator.isAttribute(o1)) {
91                      	String name1 = navigator.getAttributeQName(o1);
92                      	String name2 = navigator.getAttributeQName(o2);
93                      	return name1.compareTo(name2);
94                      }
95                  }
96  
97                  return compare(p1, p2);
98              }
99              catch (UnsupportedAxisException ex) {
100                 return 0;
101             }
102             
103         }
104 
105         try {
106             int depth1 = getDepth(o1);
107             int depth2 = getDepth(o2);
108             
109             Object a1 = o1;
110             Object a2 = o2;
111                         
112             while (depth1 > depth2) {
113                 a1 = navigator.getParentNode(a1);
114                 depth1--;
115             }
116             if (a1 == o2) return 1;
117             
118             while (depth2 > depth1) {
119                 a2 = navigator.getParentNode(a2);
120                 depth2--;
121             }
122             if (a2 == o1) return -1;
123             
124             // a1 and a2 are now at same depth; and are not the same
125             while (true) {
126                 Object p1 = navigator.getParentNode(a1);
127                 Object p2 = navigator.getParentNode(a2);
128                 if (p1 == p2) {
129                     return compareSiblings(a1, a2);
130                 }
131                 a1 = p1;
132                 a2 = p2;
133             }
134             
135         }
136         catch (UnsupportedAxisException ex) {
137             return 0; // ???? should I throw an exception instead?
138         }
139     }
140     
141 
142     private boolean isNonChild(Object o) {
143         return navigator.isAttribute(o) || navigator.isNamespace(o);
144     }
145 
146     private int compareSiblings(Object sib1, Object sib2) 
147       throws UnsupportedAxisException {
148 
149     	// attributes and namespaces sort before child nodes 
150     	if (isNonChild(sib1)) {
151     		return 1;
152     	} else if (isNonChild(sib2)) {
153     		return -1;
154     	}
155     	
156         Iterator following = navigator.getFollowingSiblingAxisIterator(sib1);
157         while (following.hasNext()) {
158             Object next = following.next();
159             if (next.equals(sib2)) return -1;
160         }
161         return 1;
162         
163     }
164 
165     private int getDepth(Object o) throws UnsupportedAxisException {
166 
167         int depth = 0;
168         Object parent = o;
169         
170         while ((parent = navigator.getParentNode(parent)) != null) {
171             depth++;
172         }
173         return depth;
174         
175     }
176     
177 }