Name
global.CycleDetector
Description
Cycle Detector for Project Diagnosis
Script
var CycleDetector = Class.create();
CycleDetector.prototype = {
tasks: [],
taskSysIds: [],
relations: [],
taskProcessStack: [],
cyclicTasks: [],
cycleDetected: false,
initialize: function() {
gs.info("Into CycleDetector");
},
isNil: function(value) {
if( !value || value == "" || value == null ) {
return true;
}
return false;
},
getTaskObject: function(gr) {
if( gr.isValid()) {
return {
sys_id: gr.getValue("sys_id"),
parent: gr.getValue("parent"),
top_task: gr.getValue("tap_task"),
number: gr.getValue("number"),
short_description: gr.getValue("short_description"),
start_date: gr.getValue("start_date"),
end_date: gr.getValue("en_date"),
duration: gr.getValue("duration"),
children: [],
predecessors: [],
successors: [],
processed: false
};
}
return;
},
getRelationObject: function(gr) {
if( gr.isValid()) {
return {
sys_id: gr.getValue("sys_id"),
parent: gr.getValue("parent"),
child: gr.getValue("child"),
lag: gr.getValue("lag"),
type: gr.getValue("type"),
sub_type: gr.getValue("sub_type"),
processed: false
};
}
return;
},
glideRecord: function() {
var gr = new GlideRecord("planned_task");
return gr;
},
getTasks: function(sysId) {
var plannedTasks = this.glideRecord();
plannedTasks.addQuery("top_task", sysId).addOrCondition("parent", sysId);
plannedTasks.query();
return plannedTasks;
},
getRelations: function(sysIds) {
var taskRelations = new GlideRecord("planned_task_rel_planned_task");
taskRelations.addQuery("parent", "IN", sysIds).addOrCondition("child", "IN", sysIds);
taskRelations.query();
return taskRelations;
},
loadTask: function(gr) {
var task = this.getTaskObject(gr);
this.tasks.push(task);
this.taskSysIds.push(task.sys_id);
},
loadTasks: function(sysId) {
var tasks = this.getTasks(sysId);
gs.info("Tasks Count: " + tasks.getRowCount());
while( tasks.next() ) {
this.loadTask(tasks);
}
},
loadRelation: function(gr) {
var relation = this.getRelationObject(gr);
this.relations.push(relation);
},
loadRelations: function() {
var relations = this.getRelations(this.taskSysIds.join(","));
gs.info("Relations Count: " + relations.getRowCount());
while( relations.next() ) {
this.loadRelation(relations);
}
},
getTaskBySysId: function(sysId) {
for (var i = 0; i < this.tasks.length; i++) {
if(this.tasks[i].sys_id == sysId) {
return this.tasks[i];
}
}
},
processParentChild: function() {
if( this.tasks.length > 0) {
for (var i = 0; i < this.tasks.length; i++) {
var task = this.tasks[i];
if( !this.isNil(task.parent)) {
var parentTask = this.getTaskBySysId(task.parent);
parentTask.children.push(task.sys_id);
}
}
} else {
gs.info("*** No Tasks Found ***");
}
},
proccessPredecessorSuccessor: function() {
if(this.relations.length > 0) {
for (var i = 0; i < this.relations.length; i++) {
var relation = this.relations[i];
if( !this.isNil(relation.parent)) {
var predecessorTask = this.getTaskBySysId(relation.parent);
if( predecessorTask )
predecessorTask.successors.push(relation);
}
if( !this.isNil(relation.child)) {
var successorTask = this.getTaskBySysId(relation.child);
if( successorTask )
successorTask.predecessors.push(relation);
}
}
} else {
gs.info("*** No Relations Found ***");
}
},
processForDetectCycles: function(sysId) {
this.propagateParentRelationsToLeafTasks();
this.propagateParentAsSuccessors();
this.startDetectCycles(sysId);
},
startDetectCycles: function(sysId) {
var leafTasks = this.getSubTreeLeafs(sysId);
for (var i = 0; i < leafTasks.length; i++) {
if( this.detectCycle(leafTasks[i]) ) {
this.cycleDetected = true;
break;
}
}
},
detectCycle: function(sysId) {
// Add the task
this.taskProcessStack.push(sysId);
while( this.taskProcessStack.length > 0) {
var lastTaskInStack = this.taskProcessStack[this.taskProcessStack.length-1];
// Get the next successors
var nextSuccessorSysId = this.getSuccessorForTask(lastTaskInStack);
if( !this.isNil(nextSuccessorSysId) ) {
if( this.taskProcessStackContains(nextSuccessorSysId) ) {
var message = this.printTaskProccessStack(nextSuccessorSysId);
this.cyclicTasks.push({sys_id: nextSuccessorSysId,
message: message});
return true; // Cycle Detected
} else {
this.taskProcessStack.push(nextSuccessorSysId);
}
} else {
// pop the last task
this.taskProcessStack.pop();
}
}
this.resetAllTaskSuccessors();
return false;
},
getSuccessorForTask: function(sysId) {
var task = this.getTaskBySysId(sysId);
var successors = task.successors;
for (var i = 0; i < successors.length; i++) {
var successor = successors[i];
if( !successor.processed ) {
successor.processed = true;
return successor.child;
}
}
return;
},
taskProcessStackContains: function(sysId) {
for (var i = 0; i < this.taskProcessStack.length; i++) {
if( sysId == this.taskProcessStack[i]) {
return true;
}
}
return false;
},
resetAllTaskSuccessors: function() {
/*for (var i = 0; i < this.tasks.length; i++) {
gs.info("Resetting task: " + this.tasks[i].short_description + " - " + this.tasks[i].sys_id);
var successors = this.tasks[i].successors;
for (var i = 0; i < successors.length; i++) {
successors[i].processed = false;
}
}*/
},
printTaskProccessStack: function(sysId) {
var cycleString = "";
for (var i = 0; i < this.taskProcessStack.length; i++) {
var task = this.getTaskBySysId(this.taskProcessStack[i]);
cycleString = cycleString + task.number + " -> ";
}
var recursiveTask = this.getTaskBySysId(sysId);
gs.info( cycleString + recursiveTask.number);
return cycleString + recursiveTask.number;
},
getCloneRelation: function( parent, child, type ) {
return {
sys_id: undefined,
parent: parent,
child: child,
lag: undefined,
type: type,
sub_type: type,
processed: false
};
},
propagateParentAsSuccessors: function() {
for (var i = 0; i < this.tasks.length; i++) {
var task = this.tasks[i];
if( !this.isNil(task.parent) ) {
var parentTask = this.getTaskBySysId(task.parent);
var cloneRelation = this.getCloneRelation(task.sys_id, task.parent, "child");
task.successors.push(cloneRelation);
parentTask.predecessors.push(cloneRelation);
}
}
},
propagateParentRelationsToLeafTasks: function() {
for (var i = 0; i < this.tasks.length; i++) {
var task = this.tasks[i];
// " | children -> " + task.children.length);
if( task.predecessors.length > 0 && task.children.size > 0 ) {
var subTreeLeafTasks = this.getSubTreeLeafs(task.sys_id);
var predecessorRelations = task.predecessors;
for (var i = 0; i < subTreeLeafTasks.length; i++) {
var subTreeLeafTask = subTreeLeafTasks[i];
for (var i = 0; i < predecessorRelations.length; i++) {
var predecessorRelation = predecessorRelations[i];
var cloneRelation = this.cloneRelation(predecessorRelation.parent, subTreeLeafTask.sys_id, "parent_clone");
var predecessorTask = this.getTaskBySysId(task.parent);
predecessorTask.successors.push(cloneRelation);
subTreeLeafTask.predecessors.push(cloneRelation);
}
}
}
}
},
getSubTreeLeafs: function(sysId) {
var subTreeLeafTasks = [];
this.addSubTreeLeaf(sysId, subTreeLeafTasks);
return subTreeLeafTasks;
},
addSubTreeLeaf: function(sysId, subTreeLeafTasks) {
var task = this.getTaskBySysId(sysId);
if(task.children.length > 0) {
var childSysIdes = task.children;
for (var i = 0; i < childSysIdes.length; i++) {
if( sysId != childSysIdes[i]) {
this.addSubTreeLeaf(childSysIdes[i], subTreeLeafTasks);
} else {
gs.info("***** Parent it self is mapped to child *****");
}
}
} else {
subTreeLeafTasks.push(sysId);
}
},
processProject: function(sysId) {
this.loadTasks(sysId);
this.loadRelations();
this.processParentChild();
this.proccessPredecessorSuccessor();
this.processForDetectCycles(sysId);
},
isCyclic: function() {
return this.cycleDetected;
},
getCyclicTasks: function () {
return this.cyclicTasks;
},
type: 'CycleDetector'
};
Sys ID
6f20d2539f75220088265bb0657fcf22