001: /*******************************************************************************
002: * Copyright (c) 2005, 2006 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.ui.internal.cheatsheets.composite.model;
011:
012: import java.util.ArrayList;
013: import java.util.HashMap;
014: import java.util.HashSet;
015: import java.util.Iterator;
016: import java.util.List;
017: import java.util.Map;
018: import java.util.Set;
019:
020: import org.eclipse.core.runtime.IStatus;
021: import org.eclipse.osgi.util.NLS;
022: import org.eclipse.ui.internal.cheatsheets.Messages;
023: import org.eclipse.ui.internal.cheatsheets.composite.parser.IStatusContainer;
024: import org.eclipse.ui.internal.provisional.cheatsheets.ICompositeCheatSheetTask;
025:
026: /**
027: * Class to keep track of dependencies between tasks
028: */
029:
030: public class TaskDependencies {
031:
032: private class Dependency {
033: private AbstractTask sourceTask;
034:
035: private String requiredTaskId;
036:
037: public Dependency(AbstractTask sourceTask, String requiredTaskId) {
038: this .sourceTask = sourceTask;
039: this .requiredTaskId = requiredTaskId;
040: }
041:
042: public AbstractTask getSourceTask() {
043: return sourceTask;
044: }
045:
046: public String getRequiredTaskId() {
047: return requiredTaskId;
048: }
049: }
050:
051: private List dependencies;
052:
053: private Map taskIdMap = new HashMap();
054:
055: public void saveId(AbstractTask task) {
056: String id = task.getId();
057: if (id != null) {
058: taskIdMap.put(id, task);
059: }
060: }
061:
062: public AbstractTask getTask(String id) {
063: return (AbstractTask) taskIdMap.get(id);
064: }
065:
066: public TaskDependencies() {
067: dependencies = new ArrayList();
068: }
069:
070: /**
071: * Register a dependency between tasks
072: * @param sourceTask a task which cannot be started until another task is completed
073: * @param requiredTaskId the id of the task which must be completed first
074: */
075: public void addDependency(AbstractTask sourceTask,
076: String requiredTaskId) {
077: dependencies.add(new Dependency(sourceTask, requiredTaskId));
078: }
079:
080: /**
081: * Resolve all of the dependencies updating the individual tasks
082: * @param model The composite cheat sheet
083: * @param status An object used to add error status
084: */
085: public void resolveDependencies(IStatusContainer status) {
086: for (Iterator dependencyIterator = dependencies.iterator(); dependencyIterator
087: .hasNext();) {
088: Dependency dep = (Dependency) dependencyIterator.next();
089: AbstractTask sourceTask = dep.getSourceTask();
090: AbstractTask requiredTask = getTask(dep.requiredTaskId);
091: if (requiredTask == null) {
092: String message = NLS.bind(
093: Messages.ERROR_PARSING_INVALID_ID,
094: (new Object[] { dep.getRequiredTaskId() }));
095: status.addStatus(IStatus.ERROR, message, null);
096: } else if (!sourceTask.requiresTask(requiredTask)) {
097: sourceTask.addRequiredTask(requiredTask);
098: }
099: }
100: checkForCircularities(status);
101: }
102:
103: /**
104: * Check for circular dependencies using the following algorithm.
105: * 1. Create a set of all the tasks which have an id (tasks without id cannot be in a cycle).;
106: * 2. Remove from the set any tasks which depend on no other task, these cannot be part of a cycle
107: * 3. Remove from the set any tasks which only depend on tasks already removed, these cannot be
108: * part of a cycle.
109: * 4. Repeat step 3 until not further tasks can be removed
110: * 5. Any tasks remaining are part of a cycle or depend on a task in a cycle
111: * @param model
112: * @param status
113: */
114: private void checkForCircularities(IStatusContainer status) {
115: Set tasks = new HashSet();
116: // Combine steps 1 + 2
117: for (Iterator idIterator = taskIdMap.values().iterator(); idIterator
118: .hasNext();) {
119: AbstractTask nextTask = (AbstractTask) idIterator.next();
120: if (nextTask.getRequiredTasks().length > 0) {
121: tasks.add(nextTask);
122: }
123: }
124: boolean makingProgress = true;
125: while (makingProgress) {
126: // Use a new set to store the tasks which are still cycle candidates to avoid
127: // iterating over and deleting from the same set.
128: Set remainingTasks = new HashSet();
129: makingProgress = false;
130: for (Iterator taskIterator = tasks.iterator(); taskIterator
131: .hasNext()
132: && !makingProgress;) {
133: boolean mayBeInCycle = false;
134: ICompositeCheatSheetTask nextTask = (ICompositeCheatSheetTask) taskIterator
135: .next();
136: ICompositeCheatSheetTask[] requiredTasks = nextTask
137: .getRequiredTasks();
138: for (int i = 0; i < requiredTasks.length; i++) {
139: if (tasks.contains(requiredTasks[i])) {
140: mayBeInCycle = true;
141: }
142: }
143: if (mayBeInCycle) {
144: remainingTasks.add(nextTask);
145: } else {
146: makingProgress = true;
147: }
148: }
149: tasks = remainingTasks;
150: }
151: if (!tasks.isEmpty()) {
152: status.addStatus(IStatus.ERROR,
153: Messages.ERROR_PARSING_CYCLE_DETECTED, null);
154: // Detect one of the cycles and report its members
155: List cycle = new ArrayList();
156: ICompositeCheatSheetTask cycleStartTask = (ICompositeCheatSheetTask) tasks
157: .iterator().next();
158: while (!cycle.contains(cycleStartTask)) {
159: cycle.add(cycleStartTask);
160: ICompositeCheatSheetTask[] requiredTasks = cycleStartTask
161: .getRequiredTasks();
162: for (int i = 0; i < requiredTasks.length; i++) {
163: if (tasks.contains(requiredTasks[i])) {
164: cycleStartTask = requiredTasks[i];
165: }
166: }
167: }
168: // Now the list contains a cycle and possibly additional tasks at the start
169: // of the list
170: boolean cycleStarted = false;
171: String this Task = null;
172: String lastTask = null;
173: String firstTask = null;
174: for (Iterator cycleIterator = cycle.iterator(); cycleIterator
175: .hasNext();) {
176: ICompositeCheatSheetTask task = (ICompositeCheatSheetTask) cycleIterator
177: .next();
178: if (task == cycleStartTask) {
179: cycleStarted = true;
180: firstTask = task.getName();
181: }
182: if (cycleStarted) {
183: // Save the name of this task
184: lastTask = this Task;
185: this Task = task.getName();
186: if (lastTask != null) {
187: String message = NLS.bind(
188: Messages.ERROR_PARSING_CYCLE_CONTAINS,
189: (new Object[] { lastTask, this Task }));
190: status.addStatus(IStatus.ERROR, message, null);
191: }
192: }
193: }
194: String message = NLS.bind(
195: Messages.ERROR_PARSING_CYCLE_CONTAINS,
196: (new Object[] { thisTask, firstTask }));
197: status.addStatus(IStatus.ERROR, message, null);
198: }
199: }
200:
201: }
|