KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > modules > tasklist > usertasks > schedule > ScheduleUtils


1 /*
2  * The contents of this file are subject to the terms of the Common Development
3  * and Distribution License (the License). You may not use this file except in
4  * compliance with the License.
5  *
6  * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7  * or http://www.netbeans.org/cddl.txt.
8  *
9  * When distributing Covered Code, include this CDDL Header Notice in each file
10  * and include the License file at http://www.netbeans.org/cddl.txt.
11  * If applicable, add the following below the CDDL Header, with the fields
12  * enclosed by brackets [] replaced by your own identifying information:
13  * "Portions Copyrighted [year] [name of copyright owner]"
14  *
15  * The Original Software is NetBeans. The Initial Developer of the Original
16  * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17  * Microsystems, Inc. All Rights Reserved.
18  */
19
20 package org.netbeans.modules.tasklist.usertasks.schedule;
21
22 import java.util.Arrays JavaDoc;
23 import java.util.Collections JavaDoc;
24 import java.util.Comparator JavaDoc;
25 import java.util.List JavaDoc;
26 import org.netbeans.modules.tasklist.core.util.ObjectList;
27 import org.netbeans.modules.tasklist.usertasks.model.Dependency;
28 import org.netbeans.modules.tasklist.usertasks.model.UserTask;
29 import org.netbeans.modules.tasklist.usertasks.util.UTUtils;
30
31 /**
32  * Some utility methods for scheduling.
33  *
34  * @author tl
35  */
36 public class ScheduleUtils {
37     /**
38      * Creates a new instance of ScheduleUtils.
39      */
40     private ScheduleUtils() {
41     }
42     
43     /**
44      * Just sorts tasks by priority.
45      *
46      * @param tasks list of tasks
47      */
48     public static void createPriorityListByPriority(List JavaDoc<UserTask> tasks) {
49         Collections.sort(tasks, new Comparator JavaDoc() {
50             public int compare(Object JavaDoc o1, Object JavaDoc o2) {
51                 UserTask ut1 = (UserTask) o1;
52                 UserTask ut2 = (UserTask) o2;
53                 return ut1.getPriority() - ut2.getPriority();
54             }
55         });
56     }
57
58     /**
59      * Schedule long tasks first.
60      * Decreasing-Time Algorithm (DTA).
61      * see http://www.ctl.ua.edu/math103/scheduling/scheduling_algorithms.htm#
62      * Scheduling%20Algorithms
63      *
64      * @param tasks list of tasks
65      */
66     public static void createPriorityListByDuration(List JavaDoc<UserTask> tasks) {
67         Collections.sort(tasks, new Comparator JavaDoc() {
68             public int compare(Object JavaDoc o1, Object JavaDoc o2) {
69                 UserTask ut1 = (UserTask) o1;
70                 UserTask ut2 = (UserTask) o2;
71                 return ut2.getEffort() - ut1.getEffort();
72             }
73         });
74     }
75        
76     /**
77      * Holds a UserTask and it's critical time
78      */
79     private static class UserTaskAndCriticalTime {
80         /** a task */
81         public UserTask ut;
82         
83         /** critical time */
84         public float ct;
85     }
86     
87     /**
88      * Schedule tasks with higher critical times first.
89      * Critical-Path Algorithm (CPA).
90      * see http://www.ctl.ua.edu/math103/scheduling/scheduling_algorithms.htm#
91      * Scheduling%20Algorithms
92      *
93      * @param tasks list of tasks
94      */
95     public static void createPriorityListBackflow(List JavaDoc<UserTask> tasks) {
96         // convert data to call backflow
97 boolean[][] deps = new boolean[tasks.size()][tasks.size()];
98         for (int i = 0; i < tasks.size(); i++) {
99             ObjectList<Dependency> ds = tasks.get(i).getDependencies();
100             for (int j = 0; j < ds.size(); j++) {
101                 Dependency d = ds.get(j);
102                 if (d.getType() == Dependency.END_BEGIN) {
103                     UserTask don = d.getDependsOn();
104                     int index = -1;
105                     for (int k = 0; k < tasks.size(); k++) {
106                         if (tasks.get(k) == don) {
107                             index = k;
108                             break;
109                         }
110                     }
111                     assert index >= 0;
112                     deps[i][index] = true;
113                 }
114             }
115         }
116         float[] durations = new float[tasks.size()];
117         for (int i = 0; i < tasks.size(); i++) {
118             durations[i] = tasks.get(i).getEffort() *
119                     tasks.get(i).getProgress() / 100.0f;
120         }
121         float[] ct = backflow(deps, durations);
122         
123         // sorting using critical times
124 UserTaskAndCriticalTime[] v = new UserTaskAndCriticalTime[tasks.size()];
125         for (int i = 0; i < v.length; i++) {
126             UserTaskAndCriticalTime utct = new UserTaskAndCriticalTime();
127             utct.ut = tasks.get(i);
128             utct.ct = ct[i];
129             v[i] = utct;
130         }
131         Arrays.sort(v, new Comparator JavaDoc() {
132             public int compare(Object JavaDoc o1, Object JavaDoc o2) {
133                 UserTaskAndCriticalTime ut1 = (UserTaskAndCriticalTime) o1;
134                 UserTaskAndCriticalTime ut2 = (UserTaskAndCriticalTime) o2;
135                 return Float.compare(ut2.ct, ut1.ct);
136             }
137         });
138         
139         // writing results back
140 tasks.clear();
141         for (int i = 0; i < v.length; i++) {
142             tasks.add(v[i].ut);
143         }
144     }
145        
146     /**
147      * Backflow algorithm.
148      * http://www.ctl.ua.edu/math103/scheduling/cpaprelim.htm#The%20Backflow%20Algorithm
149      *
150      * @param deps dependencies between tasks. Square matrix with
151      * deps[i][j] = true if task[i] depends on task[j]
152      * @param durations durations of tasks
153      * @return critical times
154      */
155     public static float[] backflow(boolean[][] deps, float[] durations) {
156         assert deps.length == durations.length;
157         
158         int n = durations.length;
159         if (n == 0)
160             return new float[0];
161         
162         float[] ct = new float[n];
163         Arrays.fill(ct, -1);
164         
165         for (int i = 0; i < n; i++) {
166             backflow2(ct, deps, durations, i);
167         }
168         
169         return ct;
170     }
171     
172     private static void backflow2(float[] ct, boolean[][] deps, float[] durations,
173             int knot) {
174         if (ct[knot] >= 0)
175             return;
176         
177         float max = 0;
178         for (int i = 0; i < durations.length; i++) {
179             if (deps[i][knot]) {
180                 backflow2(ct, deps, durations, i);
181                 if (ct[i] > max)
182                     max = ct[i];
183             }
184         }
185         ct[knot] = max + durations[knot];
186     }
187     
188     /**
189      * Sorts tasks using dependencies such that tasks can be completed in
190      * the order they are in <code>tasks</code>
191      *
192      * @param tasks list of tasks
193      */
194     public static void sortForDependencies(List JavaDoc<UserTask> tasks) {
195         boolean swapped;
196         do {
197             swapped = false;
198             outer:
199             for (int i = 0; i < tasks.size() - 1; i++) {
200                 UserTask t = tasks.get(i);
201                 for (int j = i + 1; j < tasks.size(); j++) {
202                     UserTask t2 = tasks.get(j);
203                     for (Dependency d: t.getDependencies()) {
204                         if (d.getType() == Dependency.END_BEGIN &&
205                                 d.getDependsOn() == t2) {
206                             swapped = true;
207                             tasks.add(i, tasks.remove(j));
208                             break outer;
209                         }
210                     }
211                 }
212             }
213         } while (swapped);
214     }
215 }
216
Popular Tags