11
11
* Xerox/PARC initial implementation
12
12
* ******************************************************************/
15
14
package org.aspectj.util;
20
/** This class implements a partial order
16
import java.util.ArrayList;
17
import java.util.Iterator;
18
import java.util.LinkedList;
19
import java.util.List;
22
* This class implements a partial order
22
24
* It includes routines for doing a topo-sort
25
27
public class PartialOrder {
27
/** All classes that want to be part of a partial order must implement
28
* PartialOrder.PartialComparable.
30
public static interface PartialComparable {
33
* <li>+1 if this is greater than other</li>
34
* <li>-1 if this is less than other</li>
35
* <li>0 if this is not comparable to other</li>
38
* <b> Note: returning 0 from this method doesn't mean the same thing as returning
39
* 0 from java.util.Comparable.compareTo()</b>
41
public int compareTo(Object other);
44
* This method can provide a deterministic ordering for elements that
45
* are strictly not comparable. If you have no need for this, this method
46
* can just return 0 whenever called.
48
public int fallbackCompareTo(Object other);
51
private static class SortObject {
52
PartialComparable object;
53
List/*SortObject*/ smallerObjects = new LinkedList();
54
List/*SortObject*/ biggerObjects = new LinkedList();
56
public SortObject(PartialComparable o) {
60
boolean hasNoSmallerObjects() { return smallerObjects.size() == 0; }
62
boolean removeSmallerObject(SortObject o) {
63
smallerObjects.remove(o);
64
return hasNoSmallerObjects();
67
void addDirectedLinks(SortObject other) {
68
int cmp = object.compareTo(other.object);
71
this.smallerObjects.add(other);
72
other.biggerObjects.add(this);
74
this.biggerObjects.add(other);
75
other.smallerObjects.add(this);
79
public String toString() {
80
return object.toString(); //+smallerObjects+biggerObjects;
84
private static void addNewPartialComparable(List graph, PartialComparable o) {
85
SortObject so = new SortObject(o);
86
for (Iterator i = graph.iterator(); i.hasNext(); ) {
87
SortObject other = (SortObject)i.next();
88
so.addDirectedLinks(other);
93
private static void removeFromGraph(List graph, SortObject o) {
94
for (Iterator i = graph.iterator(); i.hasNext(); ) {
95
SortObject other = (SortObject)i.next();
97
if (o == other) i.remove();
98
//??? could use this to build up a new queue of objects with no
100
other.removeSmallerObject(o);
105
* @param objects must all implement PartialComparable
107
* @returns the same members as objects, but sorted according to their partial
108
* order. returns null if the objects are cyclical
111
public static List sort(List objects) {
112
// lists of size 0 or 1 don't need any sorting
113
if (objects.size() < 2) return objects;
115
//??? we might want to optimize a few other cases of small size
117
//??? I don't like creating this data structure, but it does give good
118
//??? separation of concerns.
119
List sortList = new LinkedList(); //objects.size());
120
for (Iterator i = objects.iterator(); i.hasNext(); ) {
121
addNewPartialComparable(sortList, (PartialComparable)i.next());
124
//System.out.println(sortList);
126
// now we have built our directed graph
127
// use a simple sort algorithm from here
128
// can increase efficiency later
129
// List ret = new ArrayList(objects.size());
130
final int N = objects.size();
131
for (int index = 0; index < N; index++) {
132
//System.out.println(sortList);
133
//System.out.println("-->" + ret);
135
SortObject leastWithNoSmallers = null;
137
for (Iterator i = sortList.iterator(); i.hasNext(); ) {
138
SortObject so = (SortObject)i.next();
139
//System.out.println(so);
140
if (so.hasNoSmallerObjects()) {
141
if (leastWithNoSmallers == null ||
142
so.object.fallbackCompareTo(leastWithNoSmallers.object) < 0)
144
leastWithNoSmallers = so;
149
if (leastWithNoSmallers == null) return null;
151
removeFromGraph(sortList, leastWithNoSmallers);
152
objects.set(index, leastWithNoSmallers.object);
158
/***********************************************************************************
159
/* a minimal testing harness
160
***********************************************************************************/
161
static class Token implements PartialComparable {
168
public int compareTo(Object other) {
169
Token t = (Token)other;
171
int cmp = s.charAt(0) - t.s.charAt(0);
172
if (cmp == 1) return 1;
173
if (cmp == -1) return -1;
177
public int fallbackCompareTo(Object other) {
178
return -s.compareTo( ((Token)other).s );
181
public String toString() {
186
public static void main(String[] args) {
187
List l = new ArrayList();
188
l.add(new Token("a1"));
189
l.add(new Token("c2"));
190
l.add(new Token("b3"));
191
l.add(new Token("f4"));
192
l.add(new Token("e5"));
193
l.add(new Token("d6"));
194
l.add(new Token("c7"));
195
l.add(new Token("b8"));
197
l.add(new Token("z"));
198
l.add(new Token("x"));
200
l.add(new Token("f9"));
201
l.add(new Token("e10"));
202
l.add(new Token("a11"));
203
l.add(new Token("d12"));
204
l.add(new Token("b13"));
205
l.add(new Token("c14"));
207
System.out.println(l);
211
System.out.println(l);
30
* All classes that want to be part of a partial order must implement PartialOrder.PartialComparable.
32
public static interface PartialComparable {
35
* <li>+1 if this is greater than other</li>
36
* <li>-1 if this is less than other</li>
37
* <li>0 if this is not comparable to other</li>
40
* <b> Note: returning 0 from this method doesn't mean the same thing as returning 0 from
41
* java.util.Comparable.compareTo()</b>
43
public int compareTo(Object other);
46
* This method can provide a deterministic ordering for elements that are strictly not comparable. If you have no need for
47
* this, this method can just return 0 whenever called.
49
public int fallbackCompareTo(Object other);
52
private static class SortObject {
53
PartialComparable object;
54
List<SortObject> smallerObjects = new LinkedList<SortObject>();
55
List<SortObject> biggerObjects = new LinkedList<SortObject>();
57
public SortObject(PartialComparable o) {
61
boolean hasNoSmallerObjects() {
62
return smallerObjects.size() == 0;
65
boolean removeSmallerObject(SortObject o) {
66
smallerObjects.remove(o);
67
return hasNoSmallerObjects();
70
void addDirectedLinks(SortObject other) {
71
int cmp = object.compareTo(other.object);
76
this.smallerObjects.add(other);
77
other.biggerObjects.add(this);
79
this.biggerObjects.add(other);
80
other.smallerObjects.add(this);
84
public String toString() {
85
return object.toString(); // +smallerObjects+biggerObjects;
89
private static void addNewPartialComparable(List<SortObject> graph, PartialComparable o) {
90
SortObject so = new SortObject(o);
91
for (Iterator<SortObject> i = graph.iterator(); i.hasNext();) {
92
SortObject other = i.next();
93
so.addDirectedLinks(other);
98
private static void removeFromGraph(List<SortObject> graph, SortObject o) {
99
for (Iterator<SortObject> i = graph.iterator(); i.hasNext();) {
100
SortObject other = i.next();
105
// ??? could use this to build up a new queue of objects with no
107
other.removeSmallerObject(o);
112
* @param objects must all implement PartialComparable
114
* @returns the same members as objects, but sorted according to their partial order. returns null if the objects are cyclical
117
public static List sort(List objects) {
118
// lists of size 0 or 1 don't need any sorting
119
if (objects.size() < 2) {
123
// ??? we might want to optimize a few other cases of small size
125
// ??? I don't like creating this data structure, but it does give good
126
// ??? separation of concerns.
127
List<SortObject> sortList = new LinkedList<SortObject>(); // objects.size());
128
for (Iterator i = objects.iterator(); i.hasNext();) {
129
addNewPartialComparable(sortList, (PartialComparable) i.next());
132
// System.out.println(sortList);
134
// now we have built our directed graph
135
// use a simple sort algorithm from here
136
// can increase efficiency later
137
// List ret = new ArrayList(objects.size());
138
final int N = objects.size();
139
for (int index = 0; index < N; index++) {
140
// System.out.println(sortList);
141
// System.out.println("-->" + ret);
143
SortObject leastWithNoSmallers = null;
145
for (Iterator i = sortList.iterator(); i.hasNext();) {
146
SortObject so = (SortObject) i.next();
147
// System.out.println(so);
148
if (so.hasNoSmallerObjects()) {
149
if (leastWithNoSmallers == null || so.object.fallbackCompareTo(leastWithNoSmallers.object) < 0) {
150
leastWithNoSmallers = so;
155
if (leastWithNoSmallers == null) {
159
removeFromGraph(sortList, leastWithNoSmallers);
160
objects.set(index, leastWithNoSmallers.object);
166
/***********************************************************************************
167
* /* a minimal testing harness
168
***********************************************************************************/
169
static class Token implements PartialComparable {
176
public int compareTo(Object other) {
177
Token t = (Token) other;
179
int cmp = s.charAt(0) - t.s.charAt(0);
189
public int fallbackCompareTo(Object other) {
190
return -s.compareTo(((Token) other).s);
193
public String toString() {
198
public static void main(String[] args) {
199
List<Token> l = new ArrayList<Token>();
200
l.add(new Token("a1"));
201
l.add(new Token("c2"));
202
l.add(new Token("b3"));
203
l.add(new Token("f4"));
204
l.add(new Token("e5"));
205
l.add(new Token("d6"));
206
l.add(new Token("c7"));
207
l.add(new Token("b8"));
209
l.add(new Token("z"));
210
l.add(new Token("x"));
212
l.add(new Token("f9"));
213
l.add(new Token("e10"));
214
l.add(new Token("a11"));
215
l.add(new Token("d12"));
216
l.add(new Token("b13"));
217
l.add(new Token("c14"));
219
System.out.println(l);
223
System.out.println(l);
added
removed
org.aspectj/modules/util/src/org/aspectj/util/PartialOrder.java
