Swap list item according to multiple parameters

Question

I have a list like the one below. I want to sort this list according to the rule I specified. If there is an element to which the list element is attached, it must be in the front row.

For example, since the RequiredCourse field of the record with Id 2 is 3, the element with Id 3 must come before the element with Id 2. To do this, I created a swap method as follows. But the record with Id 3 depends on 4 and I couldn't create the sorting properly. Additionally, it depends on 10 with Id 8 and below. But 9 is not connected to anything. Since I changed the place of the records with id 8 and 10, 8 goes after 9.

The sample output should be as follows:

        var list = new List<Course>();

        list.Add(new Course { Id = 1 });
        list.Add(new Course { Id = 2, RequiredCourse = "3" });
        list.Add(new Course { Id = 3, RequiredCourse = "4" });
        list.Add(new Course { Id = 4 });
        list.Add(new Course { Id = 5 });
        list.Add(new Course { Id = 6 });
        list.Add(new Course { Id = 7 });
        list.Add(new Course { Id = 8, RequiredCourse = "10" });
        list.Add(new Course { Id = 9 });
        list.Add(new Course { Id = 10 });
        list = list.OrderBy(i => i.Id).ThenBy(i => i.RequiredCourse).ToList();

        var copy = new List<Course>(list);

        for (int i = 0; i < copy.Count; i++)
        {
            if (!string.IsNullOrEmpty(copy[i].RequiredCourse) && Int32.Parse(copy[i].RequiredCourse) > copy[i].Id)
            {
                var index = list.FindIndex(k => k.Id == Int32.Parse(copy[i].RequiredCourse));
                if (index > -1)
                {
                    var temp = list[i];
                    list[i] = list[index];
                    list[index] = temp;
                }
            }
        }

Defective Output using code above

1                
3                4
4                
2                3
5                
6                
7                
10               
9                
8                10

Expected Output

1                
4                
3                4
2                3
5                
6                
7                
10               
8                10
9                

Answer 1

I think this is easy enough to understand.

var list = new List<Course>();

list.Add(new Course { Id = 1 });
list.Add(new Course { Id = 2, RequiredCourse = "3" });
list.Add(new Course { Id = 3, RequiredCourse = "4" });
list.Add(new Course { Id = 4 });
list.Add(new Course { Id = 5 });
list.Add(new Course { Id = 6 });
list.Add(new Course { Id = 7 });
list.Add(new Course { Id = 8, RequiredCourse = "10" });
list.Add(new Course { Id = 9 });
list.Add(new Course { Id = 10 });

var output = new List<Course>();
var toProcess = new SortedDictionary<int, Course>(list.ToDictionary(c => c.Id));
var pendingAdd = new Stack<Course>();

while (toProcess.Count > 0)
{
    Course currentCourse = toProcess.First().Value;
    if (string.IsNullOrEmpty(currentCourse.RequiredCourse))
    {
        // Course has no dependency, process it.
        output.Add(currentCourse);
        toProcess.Remove(currentCourse.Id);
    }
    else
    {
        int courseId = currentCourse.Id;
        // Course has dependency. Trace down linked courses.
        while (toProcess.ContainsKey(courseId) && !string.IsNullOrEmpty(toProcess[courseId].RequiredCourse))
        {
            pendingAdd.Push(toProcess[courseId]);
            courseId = int.Parse(toProcess[courseId].RequiredCourse);
        }
        // dont forget to add the "top-level" course for the dependency chain
        pendingAdd.Push(toProcess[courseId]);

        // Add in reverse depdency order using Stack
        while (pendingAdd.Count > 0)
        {
            var course = pendingAdd.Pop();
            output.Add(course);
            toProcess.Remove(course.Id);
        }
    }
}

Your wanted list is in output.