Build all project dependencies

Write algorithm that will travel trough project dependency tree and build the projects in the right order. Make sure that parallel build support can be easily added.

Given the following project tree

P1

-> P2 

    -> PX

-> P3

    -> P4

      ->PX

    -> P5

 

Test:

        [TestMethod]
        public void TestBuildProjects()
        {
            var p1 = new Project("P1");
            var p2 = new Project("P2");
            var p3 = new Project("P3");
            var p4 = new Project("P4");
            var p5 = new Project("P5");
            var px = new Project("PX");
            p1.Projects.Add(p2);
            p1.Projects.Add(p3);
            p2.Projects.Add(px);
            p3.Projects.Add(p4);
            p3.Projects.Add(p5);
            p4.Projects.Add(px);
            BuildProject.BuildDependencies(p1);

            Assert.AreEqual(ProjectBuildStatus.Completed, p1.Status);
            AssertProjectBuildCompleted(p1.Projects);
            // Test circular dependency detection
            px.Projects.Add(p2);
            try
            {
                BuildProject.BuildDependencies(p1);

                Assert.Fail("Counldn't detect circular dependency");
            }
            catch{
            }
        }

Solution:

    public class BuildProject
    {
        public static void BuildDependencies(Project root)
        {
            var first = new List<Project>();
            first.Add(root);
            var trackingLists = new List<ProjectTrackingList>();
            CreateTrackingTree(first, root.Projects, trackingLists);

            BuildAll(trackingLists);
        }

        private static void CreateTrackingTree(List<Project> list, IList<Project> projects, List<ProjectTrackingList> trackingLists)
        {
            bool forkTheList = projects.Count > 1;
            foreach (Project project in projects)
            {
                CheckCircularDependency(list, project);

                List<Project> forkList;
                if (forkTheList)
                {
                    forkList = new List<Project>(list);
                }
                else
                {
                    forkList = list;
                }
                forkList.Add(project);
                if (project.Projects.Count == 0)
                {
                    trackingLists.Add(new ProjectTrackingList(forkList));
                }
                else
                {
                    CreateTrackingTree(forkList, project.Projects, trackingLists);
                }
            }
        }

        private static void CheckCircularDependency(IEnumerable<Project> trackList, Project project)
        {
            foreach (var project1 in trackList)
            {
                if (project.Name == project1.Name)
                {
                    throw new Exception("Circular Dependency on " + project.Name);
                }
            }
        }

        private static void BuildAll(List<ProjectTrackingList> trackingLists)
        {
            bool exit = false;
            while (!exit)
            {
                exit = true;
                foreach (var projectTrackingList in trackingLists)
                {
                    if (projectTrackingList.IsEmpty)
                    {
                        continue;
                    }
                    exit = false;

                    Project project = projectTrackingList.Get();
                    if (project.Status == ProjectBuildStatus.Completed)
                    {
                        projectTrackingList.MoveNext();
                        continue;
                    }

                    if (IsReadyForBuild(project.Projects))
                    {
                        // Build the project...

                        project.Status = ProjectBuildStatus.Completed;
                        projectTrackingList.MoveNext();
                    }
                }
            }
        }

        private static bool IsReadyForBuild(IEnumerable<Project> projects)
        {
            foreach (var project in projects)
            {
                if (project.Status != ProjectBuildStatus.Completed)
                {
                    return false;
                }
            }
            return true;
        }
    }

    public enum ProjectBuildStatus
    {
        NotStarted,
        Building,
        Completed
    }

    public class Project
    {
        private readonly string name;

        readonly List<Project> projects = new List<Project>();

        public Project(string name)
        {
            this.name = name;
        }

        public ProjectBuildStatus Status { get; set; }

        public IList<Project> Projects
        {
            get { return projects; }
        }

        public string Name
        {
            get { return name; }
        }

        public string Path { get; set; }
    }

    public class ProjectTrackingList
    {
        private readonly IList<Project> projects;
        private int trackingCounter;

        public ProjectTrackingList(IList<Project> projects)
        {
            this.projects = projects;
            trackingCounter = projects.Count;
        }

        public Project Get()
        {
            return projects[trackingCounter-1];
        }

        public void MoveNext()
        {
            trackingCounter--;
        }

        public bool IsEmpty
        {
            get { return trackingCounter == 0; }
        }
    }