KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > ui > internal > cheatsheets > composite > model > TaskDependencies


1 /*******************************************************************************
2  * Copyright (c) 2005, 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11
12 package org.eclipse.ui.internal.cheatsheets.composite.model;
13
14 import java.util.ArrayList JavaDoc;
15 import java.util.HashMap JavaDoc;
16 import java.util.HashSet JavaDoc;
17 import java.util.Iterator JavaDoc;
18 import java.util.List JavaDoc;
19 import java.util.Map JavaDoc;
20 import java.util.Set JavaDoc;
21
22 import org.eclipse.core.runtime.IStatus;
23 import org.eclipse.osgi.util.NLS;
24 import org.eclipse.ui.internal.cheatsheets.Messages;
25 import org.eclipse.ui.internal.cheatsheets.composite.parser.IStatusContainer;
26 import org.eclipse.ui.internal.provisional.cheatsheets.ICompositeCheatSheetTask;
27
28 /**
29  * Class to keep track of dependencies between tasks
30  */
31
32 public class TaskDependencies {
33     
34     private class Dependency {
35         private AbstractTask sourceTask;
36         
37         private String JavaDoc requiredTaskId;
38         
39         public Dependency(AbstractTask sourceTask, String JavaDoc requiredTaskId) {
40             this.sourceTask = sourceTask;
41             this.requiredTaskId = requiredTaskId;
42         }
43         
44         public AbstractTask getSourceTask() {
45             return sourceTask;
46         }
47         
48         public String JavaDoc getRequiredTaskId() {
49             return requiredTaskId;
50         }
51     }
52     
53     private List JavaDoc dependencies;
54     
55     private Map JavaDoc taskIdMap = new HashMap JavaDoc();
56
57     public void saveId(AbstractTask task) {
58         String JavaDoc id = task.getId();
59         if (id != null) {
60             taskIdMap.put(id, task);
61         }
62     }
63     
64     public AbstractTask getTask(String JavaDoc id) {
65         return (AbstractTask)taskIdMap.get(id);
66     }
67     
68     public TaskDependencies() {
69         dependencies = new ArrayList JavaDoc();
70     }
71     
72     /**
73      * Register a dependency between tasks
74      * @param sourceTask a task which cannot be started until another task is completed
75      * @param requiredTaskId the id of the task which must be completed first
76      */
77     public void addDependency(AbstractTask sourceTask, String JavaDoc requiredTaskId) {
78         dependencies.add(new Dependency(sourceTask, requiredTaskId));
79     }
80     
81     /**
82      * Resolve all of the dependencies updating the individual tasks
83      * @param model The composite cheat sheet
84      * @param status An object used to add error status
85      */
86     public void resolveDependencies(IStatusContainer status) {
87         for (Iterator JavaDoc dependencyIterator = dependencies.iterator(); dependencyIterator.hasNext();) {
88              Dependency dep = (Dependency)dependencyIterator.next();
89              AbstractTask sourceTask = dep.getSourceTask();
90              AbstractTask requiredTask = getTask(dep.requiredTaskId);
91              if (requiredTask == null) {
92                     String JavaDoc message = NLS.bind(Messages.ERROR_PARSING_INVALID_ID, (new Object JavaDoc[] {dep.getRequiredTaskId()}));
93                     status.addStatus(IStatus.ERROR, message, null);
94              } else if (!sourceTask.requiresTask(requiredTask)) {
95                  sourceTask.addRequiredTask(requiredTask);
96              }
97         }
98         checkForCircularities (status);
99     }
100
101     /**
102      * Check for circular dependencies using the following algorithm.
103      * 1. Create a set of all the tasks which have an id (tasks without id cannot be in a cycle).;
104      * 2. Remove from the set any tasks which depend on no other task, these cannot be part of a cycle
105      * 3. Remove from the set any tasks which only depend on tasks already removed, these cannot be
106      * part of a cycle.
107      * 4. Repeat step 3 until not further tasks can be removed
108      * 5. Any tasks remaining are part of a cycle or depend on a task in a cycle
109      * @param model
110      * @param status
111      */
112     private void checkForCircularities (IStatusContainer status) {
113         Set JavaDoc tasks = new HashSet JavaDoc();
114         // Combine steps 1 + 2
115 for (Iterator JavaDoc idIterator = taskIdMap.values().iterator(); idIterator.hasNext(); ) {
116             AbstractTask nextTask = (AbstractTask)idIterator.next();
117             if (nextTask.getRequiredTasks().length > 0) {
118                 tasks.add(nextTask);
119             }
120         }
121         boolean makingProgress = true;
122         while (makingProgress) {
123             // Use a new set to store the tasks which are still cycle candidates to avoid
124 // iterating over and deleting from the same set.
125 Set JavaDoc remainingTasks = new HashSet JavaDoc();
126             makingProgress = false;
127             for (Iterator JavaDoc taskIterator = tasks.iterator(); taskIterator.hasNext() && !makingProgress; ) {
128                 boolean mayBeInCycle = false;
129                 ICompositeCheatSheetTask nextTask = (ICompositeCheatSheetTask)taskIterator.next();
130                 ICompositeCheatSheetTask[] requiredTasks = nextTask.getRequiredTasks();
131                 for (int i = 0; i < requiredTasks.length; i++) {
132                     if (tasks.contains(requiredTasks[i])) {
133                         mayBeInCycle = true;
134                     }
135                 }
136                 if (mayBeInCycle) {
137                     remainingTasks.add(nextTask);
138                 } else {
139                     makingProgress = true;
140                 }
141             }
142             tasks = remainingTasks;
143         }
144         if (!tasks.isEmpty()) {
145             status.addStatus(IStatus.ERROR, Messages.ERROR_PARSING_CYCLE_DETECTED, null);
146             // Detect one of the cycles and report its members
147 List JavaDoc cycle = new ArrayList JavaDoc();
148             ICompositeCheatSheetTask cycleStartTask = (ICompositeCheatSheetTask)tasks.iterator().next();
149             while (!cycle.contains(cycleStartTask)) {
150                 cycle.add(cycleStartTask);ICompositeCheatSheetTask[] requiredTasks = cycleStartTask.getRequiredTasks();
151                 for (int i = 0; i < requiredTasks.length; i++) {
152                     if (tasks.contains(requiredTasks[i])) {
153                         cycleStartTask=requiredTasks[i];
154                     }
155                 }
156             }
157             // Now the list contains a cycle and possibly additional tasks at the start
158 // of the list
159 boolean cycleStarted = false;
160             String JavaDoc thisTask = null;
161             String JavaDoc lastTask = null;
162             String JavaDoc firstTask = null;
163             for (Iterator JavaDoc cycleIterator = cycle.iterator(); cycleIterator.hasNext();) {
164                 ICompositeCheatSheetTask task = (ICompositeCheatSheetTask)cycleIterator.next();
165                 if (task == cycleStartTask) {
166                     cycleStarted = true;
167                     firstTask = task.getName();
168                 }
169                 if (cycleStarted) {
170                     // Save the name of this task
171 lastTask = thisTask;
172                     thisTask = task.getName();
173                     if (lastTask != null) {
174                         String JavaDoc message = NLS.bind(Messages.ERROR_PARSING_CYCLE_CONTAINS, (new Object JavaDoc[] {lastTask, thisTask}));
175                         status.addStatus(IStatus.ERROR, message, null);
176                     }
177                 }
178             }
179             String JavaDoc message = NLS.bind(Messages.ERROR_PARSING_CYCLE_CONTAINS, (new Object JavaDoc[] {thisTask, firstTask}));
180             status.addStatus(IStatus.ERROR, message, null);
181         }
182     }
183
184 }
185
Popular Tags