Swap list item according to multiple parameters-CodePudding

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

CodePudding user response：

The problem is that you want the item "2 - 3" below the "4 - ''". I'm sure there's a way to improve what I've done, but here's version 1.0:

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 });

// isolating items with RequiredCourse
var withRequired = (
    from o in list
    where !string.IsNullOrWhiteSpace(o.RequiredCourse)
    select o
).ToList();
list = list.Except(withRequired).ToList();

// First I arrange the items without "RequiredCourse" with their respective ones.
for (var i = 0; i < list.Count; i  )
{
    var primary = list[i];
    var parents =
        withRequired
            .Where(o => o.RequiredCourse == primary.Id.ToString())
            .OrderBy(o => o.Id)
            .ToList();
    var children = (
        from o in withRequired.Except(parents)
        join o2 in parents
            on o.Id.ToString() equals o2.RequiredCourse
            into grp
        from o3 in grp
        orderby o3.Id descending
        select o3
    ).ToList();

    if (!parents.Any())
    {
        continue;
    }

    i  ;
    foreach (var p in parents)
    {
        list.Insert(i  , p);
        foreach (var c in children.Where(o => p.Id.ToString() == o.RequiredCourse))
        {
            list.Insert(i  , c);
        }
    }
}

// retrieving items that only link to items that have RequiredCourse
var childOfChildren = withRequired.Except(list).ToList();

// Then I arrange items with RequiredCourses that are linked to other items with RequiredCourses.
for (var i = 0; i < list.Count; i  )
{
    var primary = list[i];
    var children = (
        from o in childOfChildren
        where primary.Id.ToString() == o.RequiredCourse
        orderby o.Id descending
        select o
    ).ToList();

    if (!children.Any())
    {
        continue;
    }

    i  ;
    list.InsertRange(i, children);
}

// CONSOLE APPLICATION PART
foreach (var o in list)
{
    if (string.IsNullOrEmpty(o.RequiredCourse))
    {
        o.RequiredCourse = "-";
    }

    Console.WriteLine($"Course: {o.Id} - {o.RequiredCourse}");
}

CodePudding user response：

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.