KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > aspectj > util > PartialOrder


1 /* -*- Mode: Java; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2  *
3  * This file is part of the compiler and core tools for the AspectJ(tm)
4  * programming language; see http://aspectj.org
5  *
6  * The contents of this file are subject to the Mozilla Public License
7  * Version 1.1 (the "License"); you may not use this file except in
8  * compliance with the License. You may obtain a copy of the License at
9  * either http://www.mozilla.org/MPL/ or http://aspectj.org/MPL/.
10  *
11  * Software distributed under the License is distributed on an "AS IS" basis,
12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13  * for the specific language governing rights and limitations under the
14  * License.
15  *
16  * The Original Code is AspectJ.
17  *
18  * The Initial Developer of the Original Code is Xerox Corporation. Portions
19  * created by Xerox Corporation are Copyright (C) 1999-2002 Xerox Corporation.
20  * All Rights Reserved.
21  *
22  * Contributor(s):
23  */
24
25 package org.aspectj.util;
26
27 import java.util.*;
28
29
30 /** This class implements a partial order
31  *
32  * It includes routines for doing a topo-sort
33  */
34
35 public class PartialOrder {
36     
37     /** All classes that want to be part of a partial order must implement
38      * PartialOrder.PartialComparable.
39      */
40     public static interface PartialComparable {
41         /**
42          * @returns <ul>
43          * <li>+1 if this is greater than other</li>
44          * <li>-1 if this is less than other</li>
45          * <li>0 if this is not comparable to other</li>
46          * </ul>
47          *
48          * <b> Note: returning 0 from this method doesn't mean the same thing as returning
49          * 0 from java.util.Comparable.compareTo()</b>
50          */
51         public int compareTo(Object JavaDoc other);
52         
53         /**
54          * This method can provide a deterministic ordering for elements that
55          * are strictly not comparable. If you have no need for this, this method
56          * can just return 0 whenever called.
57          */
58         public int fallbackCompareTo(Object JavaDoc other);
59     }
60     
61     private static class SortObject {
62         PartialComparable object;
63         List/*SortObject*/ smallerObjects = new LinkedList();
64         List/*SortObject*/ biggerObjects = new LinkedList();
65         
66         public SortObject(PartialComparable o) {
67             object = o;
68         }
69         
70         boolean hasNoSmallerObjects() { return smallerObjects.size() == 0; }
71         
72         boolean removeSmallerObject(SortObject o) {
73             smallerObjects.remove(o);
74             return hasNoSmallerObjects();
75         }
76         
77         void addDirectedLinks(SortObject other) {
78             int cmp = object.compareTo(other.object);
79             if (cmp == 0) return;
80             if (cmp > 0) {
81                 this.smallerObjects.add(other);
82                 other.biggerObjects.add(this);
83             } else {
84                 this.biggerObjects.add(other);
85                 other.smallerObjects.add(this);
86             }
87         }
88         
89         public String JavaDoc toString() {
90             return object.toString(); //+smallerObjects+biggerObjects;
91 }
92     }
93
94     private static void addNewPartialComparable(List graph, PartialComparable o) {
95         SortObject so = new SortObject(o);
96         for (Iterator i = graph.iterator(); i.hasNext(); ) {
97             SortObject other = (SortObject)i.next();
98             so.addDirectedLinks(other);
99         }
100         graph.add(so);
101     }
102     
103     private static void removeFromGraph(List graph, SortObject o) {
104         for (Iterator i = graph.iterator(); i.hasNext(); ) {
105             SortObject other = (SortObject)i.next();
106             
107             if (o == other) i.remove();
108             //??? could use this to build up a new queue of objects with no
109 //??? smaller ones
110 other.removeSmallerObject(o);
111         }
112     }
113     
114     /**
115      * @param objects must all implement PartialComparable
116      *
117      * @returns the same members as objects, but sorted according to their partial
118      * order. returns null if the objects are cyclical
119      *
120      */
121     public static List sort(List objects) {
122         // lists of size 0 or 1 don't need any sorting
123 if (objects.size() < 2) return objects;
124         
125         //??? we might want to optimize a few other cases of small size
126
127         //??? I don't like creating this data structure, but it does give good
128 //??? separation of concerns.
129 List sortList = new LinkedList(); //objects.size());
130 for (Iterator i = objects.iterator(); i.hasNext(); ) {
131             addNewPartialComparable(sortList, (PartialComparable)i.next());
132         }
133         
134         //System.out.println(sortList);
135
136         // now we have built our directed graph
137 // use a simple sort algorithm from here
138 // can increase efficiency later
139 // List ret = new ArrayList(objects.size());
140 final int N = objects.size();
141         for (int index = 0; index < N; index++) {
142             //System.out.println(sortList);
143 //System.out.println("-->" + ret);
144
145             SortObject leastWithNoSmallers = null;
146             
147             for (Iterator i = sortList.iterator(); i.hasNext(); ) {
148                 SortObject so = (SortObject)i.next();
149                 //System.out.println(so);
150 if (so.hasNoSmallerObjects()) {
151                     if (leastWithNoSmallers == null ||
152                             so.object.fallbackCompareTo(leastWithNoSmallers.object) < 0)
153                     {
154                         leastWithNoSmallers = so;
155                     }
156                 }
157             }
158             
159             if (leastWithNoSmallers == null) return null;
160             
161             removeFromGraph(sortList, leastWithNoSmallers);
162             objects.set(index, leastWithNoSmallers.object);
163         }
164         
165         return objects;
166     }
167     
168     /***********************************************************************************
169     /* a minimal testing harness
170     ***********************************************************************************/
171     static class Token implements PartialComparable {
172         private String JavaDoc s;
173         
174         Token(String JavaDoc s) {
175             this.s = s;
176         }
177         
178         public int compareTo(Object JavaDoc other) {
179             Token t = (Token)other;
180             
181             int cmp = s.charAt(0) - t.s.charAt(0);
182             if (cmp == 1) return 1;
183             if (cmp == -1) return -1;
184             return 0;
185         }
186             
187         public int fallbackCompareTo(Object JavaDoc other) {
188             return -s.compareTo( ((Token)other).s );
189         }
190         
191         public String JavaDoc toString() {
192             return s;
193         }
194     }
195     
196     public static void main(String JavaDoc[] args) {
197         List l = new ArrayList();
198         l.add(new Token("a1"));
199         l.add(new Token("c2"));
200         l.add(new Token("b3"));
201         l.add(new Token("f4"));
202         l.add(new Token("e5"));
203         l.add(new Token("d6"));
204         l.add(new Token("c7"));
205         l.add(new Token("b8"));
206         
207         l.add(new Token("z"));
208         l.add(new Token("x"));
209         
210         l.add(new Token("f9"));
211         l.add(new Token("e10"));
212         l.add(new Token("a11"));
213         l.add(new Token("d12"));
214         l.add(new Token("b13"));
215         l.add(new Token("c14"));
216         
217         System.out.println(l);
218         
219         sort(l);
220         
221         System.out.println(l);
222     }
223 }
224
Popular Tags