1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.scxml.semantics;
18
19 import java.io.Serializable;
20 import java.util.Comparator;
21 import java.util.Iterator;
22
23 import org.apache.commons.scxml.SCXMLHelper;
24 import org.apache.commons.scxml.model.Parallel;
25 import org.apache.commons.scxml.model.State;
26 import org.apache.commons.scxml.model.TransitionTarget;
27
28
29 /**
30 * A comparator for TransitionTarget instances.
31 *
32 */
33 final class TransitionTargetComparator implements Comparator, Serializable {
34
35 /**
36 * Serial version UID.
37 */
38 private static final long serialVersionUID = 1L;
39
40 /**
41 * Constructor.
42 */
43 TransitionTargetComparator() {
44 super();
45 }
46
47 /**
48 * Compares two instances of TransitionTarget in terms of the
49 * SCXML tree hierarchy.
50 * <p>Important Remarks:</p> does not fullfill the Comparator contract,
51 * since it returns 0 if o1 == o2 and also if they are not related to each
52 * other and at the same time the chain-to-parent length for o1 is the
53 * same length as for o2 (that is, they are equally deeply nested)
54 *
55 * @param o1 The first TransitionTarget object
56 * @param o2 The second TransitionTarget object
57 * @return int The comparation result
58 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
59 * @see TransitionTarget
60 */
61 public int compare(final Object o1, final Object o2) {
62 TransitionTarget tt1 = (TransitionTarget) o1;
63 TransitionTarget tt2 = (TransitionTarget) o2;
64 if (tt1 == tt2) {
65 return 0;
66 } else if (SCXMLHelper.isDescendant(tt1, tt2)) {
67 return -1;
68 } else if (SCXMLHelper.isDescendant(tt2, tt1)) {
69 return 1;
70 } else {
71 //the tt1 and tt2 are parallel, now we have to count chain sizes
72 int tc1 = countChainLength(tt1);
73 int tc2 = countChainLength(tt2);
74 if (tc2 == tc1) {
75 // use document order as priority
76 // - not a requirement
77 // - though useful for an impl to have repeatable behavior
78 // - downside is users may rely on this behavior
79 Parallel lca = (Parallel) SCXMLHelper.getLCA(tt1, tt2);
80 TransitionTarget parent1 = tt1;
81 while (parent1.getParent() != lca) {
82 parent1 = parent1.getParent();
83 }
84 TransitionTarget parent2 = tt2;
85 while (parent2.getParent() != lca) {
86 parent2 = parent2.getParent();
87 }
88 for (Iterator iter = lca.getChildren().iterator();
89 iter.hasNext();) {
90 State s = (State) iter.next();
91 if (s == parent1) {
92 return 1;
93 } else if (s == parent2) {
94 return -1;
95 }
96 }
97 }
98 //longer the chain, deeper the node is
99 return tc2 - tc1;
100 }
101 }
102
103 /**
104 * The "depth" at which this TransitionTarget exists in the
105 * SCXML object model.
106 *
107 * @param tt The TransitionTarget
108 * @return int The "depth"
109 */
110 private int countChainLength(final TransitionTarget tt) {
111 int count = 0;
112 TransitionTarget parent = tt.getParent();
113 while (parent != null) {
114 count++;
115 parent = parent.getParent();
116 }
117 return count;
118 }
119 }
120