KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > oracle > toplink > essentials > internal > sessions > CommitOrderCalculator


1 /*
2  * The contents of this file are subject to the terms
3  * of the Common Development and Distribution License
4  * (the "License"). You may not use this file except
5  * in compliance with the License.
6  *
7  * You can obtain a copy of the license at
8  * glassfish/bootstrap/legal/CDDLv1.0.txt or
9  * https://glassfish.dev.java.net/public/CDDLv1.0.html.
10  * See the License for the specific language governing
11  * permissions and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL
14  * HEADER in each file and include the License file at
15  * glassfish/bootstrap/legal/CDDLv1.0.txt. If applicable,
16  * add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your
18  * own identifying information: Portions Copyright [yyyy]
19  * [name of copyright owner]
20  */
21 // Copyright (c) 1998, 2006, Oracle. All rights reserved.
22 package oracle.toplink.essentials.internal.sessions;
23
24 import java.util.*;
25 import oracle.toplink.essentials.descriptors.ClassDescriptor;
26
27 /**
28  * This class calculates a commit order for a series of classes
29  * based on the dependencies between them. It builds up a graph of
30  * dependencies (CommitOrderDependencyNodes) then applies topological
31  * sort to them to get an ordering.
32  * This is a throwaway class, which exists only for the lifetime of
33  * the calculation.
34  *
35  * The algorithm is descrbied in the method comment for orderCommits().
36  * This class also includes static methods for quicksort, copied from
37  * the standard libraries and adapted for these objects, since that
38  * seemed like the easiest way to sort.
39  */
40 public class CommitOrderCalculator {
41     protected int currentTime;
42     protected Vector nodes;
43     protected Vector orderedDescriptors;
44     protected AbstractSession session;
45
46     /**
47      *
48      */
49     public CommitOrderCalculator(AbstractSession session) {
50         super();
51         this.currentTime = 0;
52         this.nodes = new Vector(1);
53         this.session = session;
54     }
55
56     protected void addNode(ClassDescriptor d) {
57         nodes.addElement(new CommitOrderDependencyNode(this, d, session));
58     }
59
60     public void addNodes(Vector descriptors) {
61         Enumeration descriptorsEnum = descriptors.elements();
62         while (descriptorsEnum.hasMoreElements()) {
63             ClassDescriptor descriptor = (ClassDescriptor)descriptorsEnum.nextElement();
64             addNode(descriptor);
65         }
66     }
67
68     /*
69      * Add to each node the dependent nodes
70      */
71     public void calculateMappingDependencies() {
72         for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
73             CommitOrderDependencyNode node = (CommitOrderDependencyNode)e.nextElement();
74             node.recordMappingDependencies();
75         }
76     }
77
78     /*
79      * Add to each node the dependent nodes
80      */
81     public void calculateSpecifiedDependencies() {
82         for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
83             CommitOrderDependencyNode node = (CommitOrderDependencyNode)e.nextElement();
84             node.recordSpecifiedDependencies();
85         }
86     }
87
88     public void depthFirstSearch() {
89
90         /*
91          * Traverse the entire graph in breadth-first order. When finished, every node will have a
92          * predecessor which indicates the node that came efore it in the search
93          * It will also have a discovery time (the value of the counter when we first saw it) and
94          * finishingTime (the value of the counter after we've visited all the adjacent nodes).
95          * See Cormen, Leiserson and Rivest, Section 23.3, page 477 for a full explanation of the algorithm
96          */
97
98         //Setup
99 for (Enumeration e = getNodes().elements(); e.hasMoreElements();) {
100             CommitOrderDependencyNode node = (CommitOrderDependencyNode)e.nextElement();
101             node.markNotVisited();
102             node.setPredecessor(null);
103         }
104         currentTime = 0;
105
106         //Execution
107 for (Enumeration e = getNodes().elements(); e.hasMoreElements();) {
108             CommitOrderDependencyNode node = (CommitOrderDependencyNode)e.nextElement();
109             if (node.hasNotBeenVisited()) {
110                 node.visit();
111             }
112         }
113     }
114
115     /* Support for quicksort */
116     /*
117      * Implement the doCompare method.
118      */
119     private static int doCompare(Object JavaDoc o1, Object JavaDoc o2) {
120         // I don't care if they're equal, and I want to sort largest first.
121 int first;
122
123         // I don't care if they're equal, and I want to sort largest first.
124 int second;
125         first = ((CommitOrderDependencyNode)o1).getFinishingTime();
126         second = ((CommitOrderDependencyNode)o2).getFinishingTime();
127         if (first >= second) {
128             return 1;
129         } else {
130             return -1;
131         }
132     }
133
134     /* Support for quicksort */
135     /*
136      * Implement the doCompare method.
137      */
138     private static int doCompare(CommitOrderDependencyNode o1, CommitOrderDependencyNode o2) {
139         // I don't care if they're equal, and I want to sort largest first.
140 int first;
141
142         // I don't care if they're equal, and I want to sort largest first.
143 int second;
144         first = o1.getFinishingTime();
145         second = o2.getFinishingTime();
146         if (first >= second) {
147             return 1;
148         } else {
149             return -1;
150         }
151     }
152
153     public int getNextTime() {
154         int result = currentTime;
155         currentTime++;
156         return result;
157     }
158
159     public Vector getNodes() {
160         return nodes;
161     }
162
163     /*
164      * Return the constraint ordered classes.
165      */
166     public Vector getOrderedClasses() {
167         Vector orderedClasses = oracle.toplink.essentials.internal.helper.NonSynchronizedVector.newInstance(getOrderedDescriptors().size());
168         for (Enumeration orderedDescriptorsEnum = getOrderedDescriptors().elements();
169                  orderedDescriptorsEnum.hasMoreElements();) {
170             orderedClasses.addElement(((ClassDescriptor)orderedDescriptorsEnum.nextElement()).getJavaClass());
171         }
172
173         return orderedClasses;
174     }
175
176     /*
177      * Return the constraint ordered descriptors.
178      */
179     public Vector getOrderedDescriptors() {
180         return orderedDescriptors;
181     }
182
183     public CommitOrderDependencyNode nodeFor(Class JavaDoc c) {
184         for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
185             CommitOrderDependencyNode n = (CommitOrderDependencyNode)e.nextElement();
186             if (n.getDescriptor().getJavaClass() == c) {
187                 return n;
188             }
189         }
190         return null;
191     }
192
193     public CommitOrderDependencyNode nodeFor(ClassDescriptor d) {
194         for (Enumeration e = nodes.elements(); e.hasMoreElements();) {
195             CommitOrderDependencyNode n = (CommitOrderDependencyNode)e.nextElement();
196             if (n.getDescriptor() == d) {
197                 return n;
198             }
199         }
200         return null;
201     }
202
203     /*
204      * Calculate the commit order.
205      * Do a depth first search on the graph, skipping nodes that we have
206      * already visited or are in the process of visiting. Keep a counter
207      * and note when we first encounter a node and when we finish visiting
208      * it. Once we've visited everything, sort nodes by finishing time
209      */
210     public void orderCommits() {
211         depthFirstSearch();
212
213         Object JavaDoc[] nodeArray = new Object JavaDoc[nodes.size()];
214         nodes.copyInto(nodeArray);
215
216         quicksort(nodeArray);
217         Vector result = new Vector(nodes.size());
218         for (int i = 0; i < nodes.size(); i++) {
219             CommitOrderDependencyNode node = (CommitOrderDependencyNode)nodeArray[i];
220             result.addElement(node.getDescriptor());
221         }
222         this.orderedDescriptors = result;
223     }
224
225     /*
226      * Preform a sort using the specified comparitor object.
227      */
228     private static void quicksort(Object JavaDoc[] arr) {
229         quicksort(arr, 0, arr.length - 1);
230     }
231
232     /*
233      * quicksort the array of objects.
234      *
235      * @param arr[] - an array of objects
236      * @param left - the start index - from where to begin sorting
237      * @param right - the last index.
238      */
239     private static void quicksort(Object JavaDoc[] arr, int left, int right) {
240         int i;
241         int last;
242
243         if (left >= right) {/* do nothing if array contains fewer than two */
244             return;/* two elements */
245         }
246         swap(arr, left, (left + right) / 2);
247         last = left;
248         for (i = left + 1; i <= right; i++) {
249             if (doCompare(arr[i], arr[left]) < 0) {
250                 swap(arr, ++last, i);
251             }
252         }
253         swap(arr, left, last);
254         quicksort(arr, left, last - 1);
255         quicksort(arr, last + 1, right);
256     }
257
258     private static void swap(Object JavaDoc[] arr, int i, int j) {
259         Object JavaDoc tmp;
260
261         tmp = arr[i];
262         arr[i] = arr[j];
263         arr[j] = tmp;
264     }
265 }
266
Popular Tags