001: /*
002: The contents of this file are subject to the Common Public Attribution License
003: Version 1.0 (the "License"); you may not use this file except in compliance with
004: the License. You may obtain a copy of the License at
005: http://www.projity.com/license . The License is based on the Mozilla Public
006: License Version 1.1 but Sections 14 and 15 have been added to cover use of
007: software over a computer network and provide for limited attribution for the
008: Original Developer. In addition, Exhibit A has been modified to be consistent
009: with Exhibit B.
010:
011: Software distributed under the License is distributed on an "AS IS" basis,
012: WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for the
013: specific language governing rights and limitations under the License. The
014: Original Code is OpenProj. The Original Developer is the Initial Developer and
015: is Projity, Inc. All portions of the code written by Projity are Copyright (c)
016: 2006, 2007. All Rights Reserved. Contributors Projity, Inc.
017:
018: Alternatively, the contents of this file may be used under the terms of the
019: Projity End-User License Agreeement (the Projity License), in which case the
020: provisions of the Projity License are applicable instead of those above. If you
021: wish to allow use of your version of this file only under the terms of the
022: Projity License and not to allow others to use your version of this file under
023: the CPAL, indicate your decision by deleting the provisions above and replace
024: them with the notice and other provisions required by the Projity License. If
025: you do not delete the provisions above, a recipient may use your version of this
026: file under either the CPAL or the Projity License.
027:
028: [NOTE: The text of this license may differ slightly from the text of the notices
029: in Exhibits A and B of the license at http://www.projity.com/license. You should
030: use the latest text at http://www.projity.com/license for your modifications.
031: You may not remove this license text from the source files.]
032:
033: Attribution Information: Attribution Copyright Notice: Copyright © 2006, 2007
034: Projity, Inc. Attribution Phrase (not exceeding 10 words): Powered by OpenProj,
035: an open source solution from Projity. Attribution URL: http://www.projity.com
036: Graphic Image as provided in the Covered Code as file: openproj_logo.png with
037: alternatives listed on http://www.projity.com/logo
038:
039: Display of Attribution Information is required in Larger Works which are defined
040: in the CPAL as a work which combines Covered Code or portions thereof with code
041: not governed by the terms of the CPAL. However, in addition to the other notice
042: obligations, all copies of the Covered Code in Executable and Source Code form
043: distributed must, as a form of attribution of the original author, include on
044: each user interface screen the "OpenProj" logo visible to all users. The
045: OpenProj logo should be located horizontally aligned with the menu bar and left
046: justified on the top left of the screen adjacent to the File menu. The logo
047: must be at least 100 x 25 pixels. When users click on the "OpenProj" logo it
048: must direct them back to http://www.projity.com.
049: */
050: package com.projity.pm.criticalpath;
051:
052: import java.util.Iterator;
053: import java.util.ListIterator;
054: import com.projity.configuration.Configuration;
055: import com.projity.document.Document;
056: import com.projity.document.ObjectEvent;
057: import com.projity.field.Field;
058: import com.projity.options.ScheduleOption;
059: import com.projity.pm.assignment.Assignment;
060: import com.projity.pm.calendar.WorkingCalendar;
061: import com.projity.pm.dependency.Dependency;
062: import com.projity.pm.dependency.DependencyService;
063: import com.projity.pm.scheduling.ConstraintType;
064: import com.projity.pm.scheduling.ScheduleEvent;
065: import com.projity.pm.task.BelongsToDocument;
066: import com.projity.pm.task.NormalTask;
067: import com.projity.pm.task.Project;
068: import com.projity.pm.task.SubProj;
069: import com.projity.pm.task.Task;
070: import com.projity.strings.Messages;
071: import com.projity.transaction.MultipleTransaction;
072:
073: /**
074: * The critical path calculation
075: */
076: public class CriticalPath implements SchedulingAlgorithm {
077: PredecessorTaskList predecessorTaskList = new PredecessorTaskList(
078: this );
079: private CriticalPathFields fieldUpdater = null;
080: NormalTask finishSentinel;
081: NormalTask startSentinel;
082: Project project;
083: boolean suspendUpdates = false; // flag to suspend updates when multiple objects are treated
084: boolean needsReset = false; // flag to indicate that a reset is pending during suspended updates
085: long earliestStart;
086: long latestFinish;
087: private boolean criticalPathJustChanged = false;
088:
089: private static Field constraintTypeField = Configuration
090: .getFieldFromId("Field.constraintType");
091:
092: public CriticalPath(Project project) {
093: this .project = project;
094: project.setSchedulingAlgorithm(this );
095: // project.addObjectListener(this);
096: // project.getMultipleTransactionManager().addListener(this);
097: fieldUpdater = CriticalPathFields.getInstance(this , project);
098:
099: startSentinel = new NormalTask(true, project); //local
100: startSentinel.setDuration(0);
101: startSentinel.setName("<Start>"); // name doesn't matter - useful for debugging purposes
102:
103: finishSentinel = new NormalTask(true, project); //local
104: finishSentinel.setDuration(0);
105: finishSentinel.setName("<End>"); // name doesn't matter - useful for debugging purposes
106:
107: setForward(isForward());
108: setProjectBoundaries();
109: initEarliestAndLatest();
110: }
111:
112: private void setProjectBoundaries() {
113: // update sentinels based on read in project
114:
115: if (isForward()) {
116: startSentinel.setWindowEarlyStart(project
117: .getStartConstraint());
118: finishSentinel.setWindowLateFinish(0); //no end constraint
119: } else {
120: startSentinel.setWindowEarlyStart(0); // no start constraint
121: finishSentinel.setWindowLateFinish(project.getEnd());
122: }
123: predecessorTaskList.getList().add(0,
124: new PredecessorTaskList.TaskReference(startSentinel));
125: predecessorTaskList.getList().add(
126: new PredecessorTaskList.TaskReference(finishSentinel));
127: }
128:
129: public void initialize(Object object) {
130: project = (Project) object;
131: predecessorTaskList.getList().clear(); // get rid of sentinels that are in lis
132: predecessorTaskList.addAll(project.getTasks());
133: initSentinelsFromTasks();
134: setProjectBoundaries(); // put back sentinels
135:
136: calculate(false);
137: }
138:
139: /**
140: * Initialize the sentinels so that the start sentinel has all start tasks as successors, and the end sentinel has all end tasks as predecessors
141: *
142: */
143: private void initSentinelsFromTasks() {
144: Iterator i = predecessorTaskList.listIterator();
145: Task task;
146: while (i.hasNext()) {
147: task = ((PredecessorTaskList.TaskReference) i.next())
148: .getTask();
149: if (task.getPredecessorList().size() == 0)
150: addStartSentinelDependency(task);
151: if (task.getSuccessorList().size() == 0)
152: addEndSentinelDependency(task);
153: }
154: // System.out.println("start sentinel successors");
155: // startSentinel.getSuccessorList().dump(false);
156: // System.out.println("end sentinel preds");
157: // finishSentinel.getPredecessorList().dump(true);
158:
159: }
160:
161: public String getName() {
162: return Messages.getString("Text.forwardScheduled");
163: }
164:
165: private boolean isHonorRequiredDates() {
166: return ScheduleOption.getInstance().isHonorRequiredDates();
167: }
168:
169: private int getFreshCalculationStateCount() {
170: return predecessorTaskList.getFreshCalculationStateCount();
171: }
172:
173: private int getNextCalculationStateCount() {
174: return predecessorTaskList.getNextCalculationStateCount();
175: }
176:
177: public int getCalculationStateCount() {
178: return predecessorTaskList.getCalculationStateCount();
179: }
180:
181: private Task getBeginSentinel(boolean forward) {
182: return forward ? startSentinel : finishSentinel;
183: }
184:
185: private Task getEndSentinel(boolean forward) {
186: return forward ? finishSentinel : startSentinel;
187: }
188:
189: /**
190: * Run the critical path. There are three possibilities:
191: * 1) The task that is modified does not affect the Critical Path. In this case, only a single pass is performed and dates are set
192: * 2) The CP is modified, but the project contains no ALAP tasks. In which case early and current dates are set in the first pass, and late in the second
193: * 3) The CP is modified and the project has ALAP tasks. In which case, after both forward and backward passes are perfomed, a third pass sets current dates
194: * @param startTask
195: */
196: private void fastCalc(Task startTask) {
197: Task beginSentinel = getBeginSentinel(isForward());
198: Task endSentinel = getEndSentinel(isForward());
199:
200: long firstBoundary = isForward() ? project.getStartConstraint()
201: : -project.getEnd();
202: boolean hasReverseScheduledTasks = predecessorTaskList
203: .hasReverseScheduledTasks();
204:
205: TaskSchedule.CalculationContext context = new TaskSchedule.CalculationContext();
206: context.stateCount = getNextCalculationStateCount();
207: context.honorRequiredDates = isHonorRequiredDates();
208: context.forward = isForward();
209: context.boundary = firstBoundary;
210: context.sentinel = endSentinel;
211: context.earlyOnly = false;
212: context.assign = false;
213: context.scheduleType = isForward() ? TaskSchedule.EARLY
214: : TaskSchedule.LATE;
215: ;
216: context.pass = 0;
217: boolean affectsCriticalPath = (startTask == beginSentinel)
218: || startTask.getSchedule(context.scheduleType)
219: .affectsCriticalPath(context);
220:
221: boolean worstCase = affectsCriticalPath
222: && hasReverseScheduledTasks;
223: context.earlyOnly = worstCase;
224: context.assign = true;
225: context.pass = 1;
226: criticalPathJustChanged = affectsCriticalPath;
227: doPass(startTask, context); // always assign in first pass. Dates may change in third pass
228:
229: if (affectsCriticalPath) {
230: context.stateCount = getNextCalculationStateCount(); // backward pass treats next increment
231: context.sentinel = endSentinel;
232: long secondBoundary = -endSentinel.getSchedule(
233: context.scheduleType).getBegin(); // sent bounds of end sentinel for backward pass
234: context.boundary = secondBoundary;
235: context.sentinel = beginSentinel;
236: context.forward = !context.forward;
237: context.assign = false;
238: context.scheduleType = -context.scheduleType;
239: context.pass++;
240: doPass(null, context);
241:
242: //set project fields
243: project.setStart(startSentinel.getEarlyStart());
244: project.setEnd(finishSentinel.getEarlyFinish());
245:
246: if (hasReverseScheduledTasks) {
247: context.stateCount = getNextCalculationStateCount(); // backward pass treats next increment
248: context.forward = !context.forward;
249: context.boundary = firstBoundary;
250: context.sentinel = endSentinel;
251: context.earlyOnly = false;
252: context.assign = true;
253: context.scheduleType = -context.scheduleType;
254: context.pass++;
255: doPass(null, context);
256:
257: }
258:
259: }
260: getFreshCalculationStateCount(); // For next time;
261: }
262:
263: private void doPass(Task startTask,
264: TaskSchedule.CalculationContext context) {
265: if (startTask != null) {
266: startTask.getSchedule(context.scheduleType).invalidate();
267: startTask
268: .setCalculationStateCount(getCalculationStateCount());
269: }
270:
271: PredecessorTaskList.TaskReference taskReference;
272: boolean forward = context.forward;
273: ListIterator i = forward ? predecessorTaskList.listIterator()
274: : predecessorTaskList.reverseIterator();
275: Task task;
276: TaskSchedule schedule;
277:
278: // int count = 0;
279: // long z = System.currentTimeMillis();
280: while (forward ? i.hasNext() : i.hasPrevious()) {
281: taskReference = (PredecessorTaskList.TaskReference) (forward ? i
282: .next()
283: : i.previous());
284: task = taskReference.getTask();
285: context.taskReferenceType = taskReference.getType();
286: schedule = task.getSchedule(context.scheduleType);
287: if (!forward)
288: context.taskReferenceType = -taskReference.getType();
289:
290: if (task.isReverseScheduled()) {// reverse scheduled must always be calculated
291: schedule.invalidate();
292: task.setCalculationStateCount(context.stateCount);
293: }
294: if (task.getCalculationStateCount() >= context.stateCount) {
295: schedule.calcDates(context);
296: if (context.assign) {
297: if (schedule.getBegin() != 0L && !isSentinel(task))
298: earliestStart = Math.min(earliestStart,
299: schedule.getStart());
300: if (schedule.getEnd() != 0 && !isSentinel(task))
301: latestFinish = Math.max(latestFinish, schedule
302: .getFinish());
303: }
304: // schedule.dump();
305: }
306: }
307: // System.out.println("pass forward=" + forward + " tasks:" + count + " time " + (System.currentTimeMillis() -z) + " ms");
308: }
309:
310: public void calculate(boolean update) {
311: calculate(update, null);
312: }
313:
314: public void initEarliestAndLatest() {
315: long date = project.getStartConstraint();
316: // if (!isForward())
317: // date = -date;
318: earliestStart = latestFinish = date;
319: }
320:
321: private void _calculate(boolean update, Task task) {
322: long t = System.currentTimeMillis();
323: if (predecessorTaskList.getList().size() < 3) {// if no tasks, nothing to calculate. This is needed to avoid a null pointer execption because of sentinels not having any preds/succs
324: if (isForward())
325: project.setEnd(project.getStartConstraint());
326: else
327: project.setStart(project.getEnd());
328: return;
329:
330: }
331: if (task == null) {
332: task = getBeginSentinel(isForward());
333: }
334: fastCalc(task);
335: if (update)
336: fireScheduleChanged();
337: }
338:
339: private void calculate(final boolean update, final Task task) {
340: if (suspendUpdates)
341: return;
342: _calculate(update, task);
343: // instead of calculating immediately, we can perhaps delay the calculation till the end of all other updates. This may
344: // cause problems in other cases where an immediate update is required, so I am commenting it out for now. See bug 225
345: // SwingUtilities.invokeLater(new Runnable() {
346: // public void run() {
347: // _calculate(update,task);
348: // }
349: // });
350: }
351:
352: /*
353: * (non-Javadoc)
354: *
355: * @see com.projity.pm.criticalpath.SchedulingAlgorithm#getDefaultTaskConstraintType()
356: */
357: public int getDefaultTaskConstraintType() {
358: return ConstraintType.ASAP;
359: }
360:
361: private void fireScheduleChanged() {
362: ((Project) project).fireScheduleChanged(this ,
363: ScheduleEvent.SCHEDULE);
364: }
365:
366: private boolean updating = false;
367:
368: private synchronized CriticalPathFields getOrClearUpdater(
369: boolean get) {
370: if (get) {
371: if (updating == true) {
372: System.out.println("interrupting update thread");
373: fieldUpdater.interrupt(); // interrupt existing thread
374: fieldUpdater = CriticalPathFields.getInstance(this ,
375: project); // make new one
376: }
377: updating = true;
378: return fieldUpdater;
379: } else {
380: updating = false;
381: return null;
382:
383: }
384: }
385:
386: //
387: // public void scheduleTask(NormalTask task) {
388: // calcEarlyStartAndFinish(task, task.getProject().getStart());
389: // calcLateStartAndLateFinish(task, task.getProject().getEnd(), false);
390: // task.calcStartAndFinish();
391: // }
392:
393: /**
394: * Respond to object create/delete events
395: */
396: public void objectChanged(ObjectEvent objectEvent) {
397: if (!project.isInitialized()) {
398: System.out
399: .println("Error - Message received when Project is not init"
400: + project);
401: return;
402: }
403: if (objectEvent.getSource() == this )
404: return;
405: Object changedObject = objectEvent.getObject();
406: Task task = null;
407: if (changedObject instanceof Task) {
408: if (objectEvent.isCreate()) {
409: predecessorTaskList.arrangeTask((Task) changedObject);
410: return; // let the hierarchy event that follow run the CP
411: } else if (objectEvent.isDelete()) {
412: Task removedTask = (Task) changedObject;
413: predecessorTaskList.removeTask(removedTask);
414: reset(); // Fix of bug 91 31/8/05. This ensures the ancestors of this task that are no longer parents will be replaced as single entries in pred list
415: } else if (objectEvent.isUpdate()) {
416: task = (Task) changedObject;
417: Field field = objectEvent.getField();
418: if (field != null && !fieldUpdater.inputContains(field))
419: return;
420: if (field == constraintTypeField) {
421: reset();
422: task.invalidateSchedules();
423: task.markTaskAsNeedingRecalculation();
424: }
425: }
426: calculate(true, task);
427:
428: } else if (changedObject instanceof Dependency) { // dependency added or
429: // removed
430: Dependency dependency = (Dependency) changedObject;
431: if (!dependency.refersToDocument(project))
432: return;
433: if (!objectEvent.isUpdate()) {
434: reset(); // refresh predecssor list - the whold thing may change drastically no matter what the link because of parents
435: }
436: task = (Task) dependency.getPredecessor();
437: Task successor = (Task) dependency.getSuccessor(); // the successor needs to be scheduled
438:
439: // to fix a bug, I am invalidating both early and late schedules
440: task.invalidateSchedules();
441: task.markTaskAsNeedingRecalculation();
442: if (successor.isSubproject()) { // special case for subprojects - need to reset all
443: SubProj sub = (SubProj) successor;
444: if (sub.isSubprojectOpen())
445: sub.getSubproject()
446: .markAllTasksAsNeedingRecalculation(true);
447: }
448: successor.invalidateSchedules();
449: successor.markTaskAsNeedingRecalculation();
450:
451: // The line below fixes a bug with nested parents of the sort pred->grand par sib1->sib2. Of course, it means most of the code above is redundant (except for subproject stuff)
452: project.markAllTasksAsNeedingRecalculation(true);
453: calculate(true, null); // Run both passes, since the CP might be modified and it's hard to tell if so
454: } else if (changedObject == project) { // if whole project changed, such
455: // as hierarchy event
456: reset();
457: calculate(true, null);
458: } else if (changedObject instanceof WorkingCalendar) { // if whole project changed, such
459: //TODO for now just invalidating all projects, eventually be smarter
460: project.markAllTasksAsNeedingRecalculation(false);
461: calculate(true, null);
462: } else if (changedObject instanceof Assignment) {
463: Assignment assignment = (Assignment) changedObject;
464: task = assignment.getTask();
465: if (task.getProject().getSchedulingAlgorithm() != this )
466: return;
467: // if (((NormalTask)task).isEffortDriven())
468: calculate(true, task);
469: } else if (changedObject instanceof BelongsToDocument) { // for other things, such as assignment entry
470: if (((BelongsToDocument) changedObject).getDocument() instanceof Project) {
471: Project proj = (Project) ((BelongsToDocument) changedObject)
472: .getDocument();
473: if (proj.getSchedulingAlgorithm() != this )
474: return;
475: }
476: Field field = objectEvent.getField();
477: if (field != null && fieldUpdater.inputContains(field))
478: calculate(true, null);
479: }
480: }
481:
482: public void reset() {
483: if (suspendUpdates) {
484: needsReset = true;
485: return;
486: }
487:
488: needsReset = false;
489: initEarliestAndLatest();
490: predecessorTaskList.rearrangeAll();
491: }
492:
493: public void addEndSentinelDependency(Task task) {
494: if (task.getOwningProject() == project && !task.isExternal())
495: DependencyService.getInstance().addEndSentinelDependency(
496: finishSentinel, task);
497: }
498:
499: public boolean removeEndSentinelDependency(Task task) {
500: if (task.getOwningProject() == project && !task.isExternal())
501: return DependencyService.getInstance().removeEndSentinel(
502: finishSentinel, task);
503: return false;
504: }
505:
506: public void addStartSentinelDependency(Task task) {
507: if (task.getOwningProject() == project && !task.isExternal())
508: DependencyService.getInstance().addStartSentinelDependency(
509: startSentinel, task);
510: }
511:
512: public boolean removeStartSentinelDependency(Task task) {
513: if (task.getOwningProject() == project && !task.isExternal())
514: return DependencyService.getInstance().removeStartSentinel(
515: startSentinel, task);
516: return false;
517: }
518:
519: public long getStartConstraint() {
520: return startSentinel.getConstraintDate();
521: }
522:
523: /* (non-Javadoc)
524: * @see com.projity.pm.criticalpath.HasSentinels#setStartConstraint(long)
525: */
526: public void setStartConstraint(long date) {
527: startSentinel.setScheduleConstraint(ConstraintType.SNET, date);
528: markBoundsAsDirty();
529: }
530:
531: /* (non-Javadoc)
532: * @see com.projity.pm.criticalpath.HasSentinels#setEndConstraint(long)
533: */
534: public void setEndConstraint(long date) {
535: finishSentinel.setScheduleConstraint(ConstraintType.FNLT, date);
536: markBoundsAsDirty();
537: }
538:
539: public void markBoundsAsDirty() {
540: startSentinel.markTaskAsNeedingRecalculation();
541: finishSentinel.markTaskAsNeedingRecalculation();
542:
543: // mark all tasks without preds or without succs as dirty
544: // the purpose of this is to handle cases where a task that determines the project bounds is deleted.
545:
546: Iterator i = startSentinel.getSuccessorList().iterator();
547: Task task;
548: while (i.hasNext()) {
549: task = ((Task) ((Dependency) i.next()).getTask(false));
550: task.invalidateSchedules();
551: task.markTaskAsNeedingRecalculation();
552: }
553:
554: i = finishSentinel.getPredecessorList().iterator();
555: while (i.hasNext()) {
556: task = ((Task) ((Dependency) i.next()).getTask(true));
557: task.invalidateSchedules();
558: task.markTaskAsNeedingRecalculation();
559: }
560:
561: }
562:
563: /**
564: * @return
565: */
566: public boolean isForward() {
567: return project.isForward();
568: }
569:
570: public void setForward(boolean forward) {
571: if (forward) {
572: setStartConstraint(project.getStartConstraint());
573: finishSentinel.setRawConstraintType(ConstraintType.ASAP);
574: } else {
575: setEndConstraint(project.getEnd());
576: startSentinel.setRawConstraintType(ConstraintType.ASAP);
577: }
578: startSentinel.setForward(forward);
579: finishSentinel.setForward(forward);
580: }
581:
582: /* (non-Javadoc)
583: * @see com.projity.transaction.MultipleTransaction.Listener#multipleTransaction(com.projity.transaction.MultipleTransaction)
584: */
585: public void multipleTransaction(MultipleTransaction objectEvent) {
586: if (objectEvent.isFinalEnd()) {
587: suspendUpdates = false;
588: if (needsReset)
589: reset();
590: calculate(true, null);
591: } else {
592: suspendUpdates = true;
593: }
594:
595: }
596:
597: /**
598: * @return
599: */
600: public boolean getMarkerStatus() {
601: return predecessorTaskList.getMarkerStatus();
602: }
603:
604: /**
605: * To add a new object such as when pasting
606: */
607: public void addObject(Object task) {
608: NormalTask newTask = (NormalTask) task;
609: if (newTask.getSuccessorList().isEmpty()) { // if pred has no successors, tell end sentinel about it
610: addEndSentinelDependency(newTask);
611: } else { // make sure not in sentinel's list
612: removeEndSentinelDependency(newTask);
613: }
614: if (newTask.getPredecessorList().isEmpty()) { // if pred has no successors, tell end sentinel about it
615: addStartSentinelDependency(newTask);
616: } else { // make sure not in sentinel's list
617: removeStartSentinelDependency(newTask);
618: }
619:
620: newTask.markTaskAsNeedingRecalculation();
621: predecessorTaskList.arrangeTask(newTask);
622: }
623:
624: public void addSubproject(Task subproject) {
625: predecessorTaskList.addSubproject(subproject);
626: }
627:
628: /* (non-Javadoc)
629: * @see com.projity.pm.criticalpath.SchedulingAlgorithm#getDocument()
630: */
631: public Document getMasterDocument() {
632: return project;
633: }
634:
635: public void dumpPredecessorList() {
636: predecessorTaskList.dump();
637: }
638:
639: public final long getEarliestStart() {
640: return earliestStart;
641: }
642:
643: public final long getLatestFinish() {
644: return latestFinish;
645: }
646:
647: private boolean isSentinel(Task task) {
648: return task == startSentinel || task == finishSentinel;
649: }
650:
651: public final Project getProject() {
652: return project;
653: }
654:
655: public boolean isCriticalPathJustChanged() {
656: return criticalPathJustChanged;
657: }
658:
659: public CriticalPathFields getFieldUpdater() {
660: return fieldUpdater;
661: }
662:
663: public void setEarliestAndLatest(long earliest, long latest) {
664: this.earliestStart = earliest;
665: this.latestFinish = latest;
666: }
667: }
|