TaskGraphRepresentation


1   /*
2    * Copyright (C) Jakub Neubauer, 2007
3    *
4    * This file is part of TaskBlocks
5    *
6    * TaskBlocks is free software; you can redistribute it and/or modify
7    * it under the terms of the GNU General Public License as published by
8    * the Free Software Foundation; either version 3 of the License, or
9    * (at your option) any later version.
10   *
11   * TaskBlocks is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   * GNU General Public License for more details.
15   *
16   * You should have received a copy of the GNU General Public License
17   * along with this program.  If not, see <http://www.gnu.org/licenses/>.
18   */
19  
20  package taskblocks.graph;
21  
22  import java.util.ArrayList  ;
23  import java.util.Arrays  ;
24  import java.util.Collection  ;
25  import java.util.List  ;
26  
27  import javax.swing.event.ChangeListener  ;
28  
29  import taskblocks.ArrayUtils;
30  
31  /**
32   * helper class used to build the data structure from task graph model.
33   */
34  public class TaskGraphRepresentation {
35      
36      TaskRow[] _rows;
37      
38      Task[] _tasks;
39      
40      Connection[] _connections;
41      
42      TaskGraphModel _model;
43      
44      /** Used internally when shifting tasks */
45      boolean _somethingMoved;
46      
47      private ChangeListener   _graphChangeListener;
48      
49      /** Used to recognize when to recount bounds in {@link TaskGraphComponent#paint(java.awt.Graphics)}. */
50      private boolean _paintDirty;
51      
52      /** Used to recognize if the project has been changed since loaded from file */
53      private boolean _saveDirty;
54      
55      TaskGraphRepresentation(TaskGraphModel model) {
56          _model = model;
57      }
58  
59      public void clearSaveDirtyFlag() {
60          _saveDirty = false;
61          if(_graphChangeListener != null) {
62              _graphChangeListener.stateChanged(null);
63          }
64      }
65      
66      public boolean isSaveDirty() {
67          return _saveDirty;
68      }
69      
70      /**
71       * Builds all the data structures according to the model
72       * and recounts the starting times, so the tasks don't cross each other
73       */
74      void buildFromModel() {
75          
76          ChangeListener   oldChangeList = _graphChangeListener;
77          try {
78              _graphChangeListener = null;
79  
80          
81              Object  [] taskObjs = _model.getTasks();
82              Task[] tasks = new Task[taskObjs.length];
83              List  <TaskRow> rows = new ArrayList  <TaskRow>();
84              
85              // build list of tasks and rows.
86              int i = 0;
87              for(Object   taskObj: taskObjs) {
88                  Task t = new Task(taskObj, this);
89                  tasks[i] = t;
90                  
91                  Object   manObj = _model.getTaskMan(taskObj);
92                  TaskRow row = findRowForManObj(manObj, rows);
93                  if(row == null) {
94                      row = new TaskRow(manObj);
95                      row._name = _model.getManName(manObj);
96                      rows.add(row);
97                      row._index = rows.size()-1;
98                  }
99                  // task -> row mapping
100                 t._row = row;
101                 t.setDuration(_model.getTaskDuration(t._userObject));
102                 t.setStartTime(_model.getTaskStartTime(t._userObject));
103                 
104                 // we must initialize these arrays, so we don't care about nulls later
105                 t._incommingConnections = new Connection[0];
106                 t._outgoingConnections = new Connection[0];
107                 
108                 i++;
109             }
110             
111             // some rows doesn't have tasks, so create them
112             for(Object   manObj: _model.getMans()) {
113                 TaskRow row = findRowForManObj(manObj, rows);
114                 if(row == null) {
115                     row = new TaskRow(manObj);
116                     row._name = _model.getManName(manObj);
117                     rows.add(row);
118                     row._index = rows.size()-1;
119                 }
120             }
121             
122             // row -> tasks mapping
123             for(TaskRow row: rows) {
124                 List  <Task> rowTasks = new ArrayList  <Task>();
125                 for(Task t: tasks) {
126                     if(t.getRow() == row) {
127                         rowTasks.add(t);
128                     }
129                 }
130                 row._tasks = rowTasks.toArray(new Task[rowTasks.size()]);
131             }
132             
133             // build connections array
134             List  <Connection> connections = new ArrayList  <Connection>();
135             for(Task t: tasks) {
136                 Object  [] predecessorsUserObjects = _model.getTaskPredecessors(t._userObject);
137                 if(predecessorsUserObjects != null && predecessorsUserObjects.length > 0) {
138                     for(Object   predecessorUserObject: predecessorsUserObjects) {
139                         Task predTask = findTaskForUserObject(predecessorUserObject, tasks);
140                         Connection con = new Connection(predTask, t);
141                         predTask.addOutgoingConnection(con);
142                         t.addIncommingConnection(con);
143                         connections.add(con);
144                     }
145                 }
146             }
147             
148             synchronized(this) {
149                 _tasks = tasks;
150                 _rows = rows.toArray(new TaskRow[rows.size()]);
151                 Arrays.sort(_rows, new TaskRowNameComparator());
152                 // repair row indexes
153                 for(i = 0; i < _rows.length; i++) {
154                     _rows[i]._index = i;
155                 }
156                 _connections = connections.toArray(new Connection[connections.size()]);
157                 recountStartingTimes();
158                 _paintDirty = true;
159                 _saveDirty = false;
160             }
161         } finally {
162             _graphChangeListener = oldChangeList;
163             if(_graphChangeListener != null) {
164                 _graphChangeListener.stateChanged(null);
165             }
166         }
167         
168     }
169     
170     void changeTaskRow(Task t, TaskRow newRow) {
171         TaskRow oldRow = t._row;
172         if(oldRow == newRow) {
173             return;
174         }
175         
176         t._row = newRow;
177         oldRow._tasks = (Task[])ArrayUtils.removeFromArray(oldRow._tasks, t);
178         newRow._tasks = (Task[])ArrayUtils.addToArray(newRow._tasks, t);
179         
180         setDirty();
181     }
182     
183     /**
184      * Must be called synchronized on this object
185      */
186     void clearPaintDirtyFlag() {
187         _paintDirty = false;
188     }
189     
190     ChangeListener   getGraphChangeListener() {
191         return _graphChangeListener;
192     }
193 
194     boolean isPaintDirty() {
195         return _paintDirty;
196     }
197     
198     private List  <Task> getRootTasks() {
199         // build a list of tasks that don't have predecessor.
200         List  <Task> rootTasks = new ArrayList  <Task>();
201         for(Task t: _tasks) {
202             if(t._incommingConnections.length == 0) {
203                 rootTasks.add(t);
204             }
205         }
206         return rootTasks;
207     }
208     
209     /**
210      * Shifts tasks as it is needed, so they don't cross each other and the dependencies are OK.
211      */
212     synchronized void recountStartingTimes() {
213         
214         TaskStartTimeComarator taskStartTimeComparator = new TaskStartTimeComarator();
215         // sort tasks according to their starting time
216         Arrays.sort(_tasks, taskStartTimeComparator);
217         
218         
219         for(TaskRow row: _rows) {
220             // first, we must sort them according to their starting time, so they will appear
221             // in the same order as before.
222             Arrays.sort(row._tasks, taskStartTimeComparator);
223         }
224 
225         do {
226             _somethingMoved = false;
227             // build a list of tasks that don't have predecessor.
228             List  <Task> rootTasks = getRootTasks();
229             
230             // first, shift tasks according their predecessors.
231             for(Task t: rootTasks) {
232                 shiftSubsequentTasksAfterMe(t);
233             }
234             
235             // secondly, shift tasks, so they will not cross each other in row.
236             for(TaskRow row: _rows) {
237                 // we must sort them according to their starting time again, the previous
238                 // shifting could change their order.
239                 Arrays.sort(row._tasks, taskStartTimeComparator);
240                 
241                 for(int i = 0; i < row._tasks.length-1; i++) {
242                     Task t1 = row._tasks[i];
243                     Task t2 = row._tasks[i+1];
244                     long t1End = t1.getFinishTime();
245                     if(t2.getStartTime() < t1End) {
246                         _somethingMoved = true;
247                         // we must shift the t2 task. After shifting, check it's subsequent tasks.
248                         t2.setStartTime(t1End);
249                         shiftSubsequentTasksAfterMe(t2);
250                     }
251                 }
252             }
253         } while(_somethingMoved);
254     }
255     
256     /**
257      * Sets both, the "paint" and the "save" dirty flags
258      */
259     public synchronized void setDirty() {
260         _paintDirty = true;
261         _saveDirty = true;
262         if(_graphChangeListener != null) {
263             _graphChangeListener.stateChanged(null);
264         }
265     }
266     
267     void setGraphChangeListener(ChangeListener   cl) {
268         _graphChangeListener = cl;
269     }
270     
271     /**
272      * Sets just the "paint" dirty flag.
273      * Used only when the tasks bounds should be recounted but the model itself didn't change
274      * (for example just scale changed)
275      */
276     synchronized void setPaintDirty() {
277         _paintDirty = true;
278     }
279     
280     public synchronized void shrinkTasks() {
281         TaskStartTimeComarator taskStartTimeComparator = new TaskStartTimeComarator();
282         // find the lowest time
283         long firstTime = Long.MAX_VALUE;
284         for(Task t: _tasks) {
285             firstTime = Math.min(t.getStartTime(), firstTime);
286         }
287         for(TaskRow row: _rows) {
288             if(row._tasks.length > 0) {
289                 // first, we must sort them according to their starting time, so they will appear
290                 // in the same order as before.
291                 Arrays.sort(row._tasks, taskStartTimeComparator);
292                 row._tasks[0].setStartTime(firstTime);
293                 for(int i = 1; i < row._tasks.length; i++) {
294                     row._tasks[i].setStartTime(row._tasks[i-1].getFinishTime());
295                 }
296             }
297         }
298         recountStartingTimes();
299     }
300     
301     public void updateModel() {
302         for(Task t: _tasks) {
303             // build array of preceeding tasks
304             Object  [] preceedingTasksUserObjs = new Object  [t._incommingConnections.length];
305             for(int i = 0; i < t._incommingConnections.length; i++) {
306                 preceedingTasksUserObjs[i] = t._incommingConnections[i]._fromTask._userObject;
307             }
308             _model.updateTask(t._userObject, t._row._userManObject, t.getStartTime(), t.getDuration(), preceedingTasksUserObjs);
309         }
310     }
311     
312     /**
313      * Used when building data structures. Finds row for given user man object
314      * 
315      * @param manObj
316      * @param rows
317      * @return
318      */
319     private TaskRow findRowForManObj(Object   manObj, Collection  <TaskRow> rows) {
320         for(TaskRow row:rows) {
321             if(row._userManObject == manObj) {
322                 return row;
323             }
324         }
325         return null;
326     }
327 
328     private Task findTaskForUserObject(Object   taskUserobj, Task[] tasks) {
329         for(Task t: tasks) {
330             if(t._userObject == taskUserobj) {
331                 return t;
332             }
333         }
334         return null;
335     }
336     
337     /** Recursively checks all sub-tasks of given task and if they start before this task finishes,
338      * shifts them.
339      * 
340      * @param t Task to be checked
341      */
342     private void shiftSubsequentTasksAfterMe(Task t) {
343         for(Connection c: t._outgoingConnections) {
344             Task targetTask = c._toTask;
345             if(targetTask.getStartTime() < t.getFinishTime()) {
346                 targetTask.setStartTime(t.getFinishTime());
347                 _somethingMoved = true;
348             }
349         }
350         // recursion breath-first
351         for(Connection c: t._outgoingConnections) {
352             shiftSubsequentTasksAfterMe(c._toTask);
353         }
354     }
355 
356     /**
357      * 
358      * @param t1
359      * @param t2
360      * 
361      * @throws Exception if connection cannot be created because of cycle.
362      */
363     void createConnection(Task t1, Task t2) throws Exception   {
364         if(t1 == t2 || t1 == null || t2 == null) {
365             throw new IllegalArgumentException  ("Wrong connection");
366         }
367         
368         Connection c = new Connection(t1, t2);
369         t1._outgoingConnections = (Connection[])ArrayUtils.addToArray(t1._outgoingConnections, c);
370         t2._incommingConnections = (Connection[])ArrayUtils.addToArray(t2._incommingConnections, c);
371         _connections = (Connection[])ArrayUtils.addToArray(_connections, c);
372         
373         if(checkForCycles()) {
374             // UNDO and throw exception
375             t1._outgoingConnections = (Connection[])ArrayUtils.removeFromArray(t1._outgoingConnections, c);
376             t2._incommingConnections = (Connection[])ArrayUtils.removeFromArray(t2._incommingConnections, c);
377             _connections = (Connection[])ArrayUtils.removeFromArray(_connections, c);
378             throw new Exception  ("Loops are not allowed in task dependencies");
379         }
380         
381         setDirty();
382     }
383     
384     /**
385      * Returns true if there are some cycles in the task dependency graph
386      * 
387      * @return
388      */
389     private boolean checkForCycles() {
390         if(_tasks.length == 0) {
391             return false;
392         }
393         // initialize flags
394         for(Task t: _tasks) {
395             t._flag = false;
396         }
397         for(Task t: _tasks) {
398             if(checkForCyclesRec(t)) {
399                 return true;
400             }
401         }
402         return false;
403     }
404 
405     private boolean checkForCyclesRec(Task t) {
406         if(t._flag) {
407             return true;
408         }
409         t._flag = true;
410         
411         for(Connection outC: t._outgoingConnections) {
412             if(checkForCyclesRec(outC._toTask)) {
413                 return true;
414             }
415         }
416         
417         t._flag = false;
418         return false;
419     }
420 
421     public int getManCount() {
422         return _rows.length;
423     }
424 
425     public void removeConnection(Connection c) {
426         c._fromTask._outgoingConnections = (Connection[])ArrayUtils.removeFromArray(c._fromTask._outgoingConnections, c);
427         c._toTask._incommingConnections = (Connection[])ArrayUtils.removeFromArray(c._toTask._incommingConnections, c);
428         _connections = (Connection[])ArrayUtils.removeFromArray(_connections, c);
429         setDirty();
430     }
431 
432     public void removeTask(Task t) {
433         for(Connection c: t._incommingConnections) {
434             removeConnection(c);
435         }
436         for(Connection c: t._outgoingConnections) {
437             removeConnection(c);
438         }
439         _tasks = (Task[])ArrayUtils.removeFromArray(_tasks, t);
440         t._row._tasks = (Task[])ArrayUtils.removeFromArray(t._row._tasks, t);
441         _model.removeTask(t._userObject);
442         setDirty();
443     }
444 
445     public void removeRow(TaskRow row) {
446         for(Task t: row._tasks) {
447             removeTask(t);
448         }
449         _rows = (TaskRow[])ArrayUtils.removeFromArray(_rows, row);
450         _model.removeMan(row._userManObject);
451         setDirty();
452     }
453 }
454
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags