How can I reorder a List hierarchically according to the items' parent/child relation?

Question

My object looks something like this:

public class Transaction
{
   long Id;
   long Amount;
   DateTime Date;
   string ReferenceNumber;
   string ParentReferenceNumber;
}

It is already coming in sorted by Date, but what I need to do is arrange the list of these transactions so that those having a ParentReferenceNumber that matches the ReferenceNumber on another Transaction appear in the order of "Parent then Child".

Here is what I tried. It produces the error "Collection was modified; enumeration operation may not execute." That's what I was afraid of, hence the question.

foreach (var p in Model.PaymentInfo)
{
    var child = Model.PaymentInfo.SingleOrDefault(x => x.ParentReferenceNumber == p.ReferenceNumber);

    if (child != null)
    {
        var parentIndex = Model.PaymentInfo.IndexOf(p);
        var childIndex = Model.PaymentInfo.IndexOf(child);
        Model.PaymentInfo.RemoveAt(childIndex);
        Model.PaymentInfo.Insert(parentIndex + 1, child);
    }

}

You can never remove an item from a collection when you are looping through it. Looking at this again though, you are over thinking it, just add a groupby in your select, and order on the groupby. That will give you what want without a lot of extra code. — Kelso Sharp, Jun 14 '16 at 18:26

Jim Mischel · Answer 1 · 2016-06-13T17:08:00.137

Start by adding a list of children to each node. For example:

public class WorkingTransaction
{
    public Transaction Details;
    public List<WorkingTransaction> Children;
    public bool HasParent;
}

Then, create a dictionary of WorkingTransactions, keyed on Id. Here, transactions is your sorted list of transactions.

var workDict = transactions
    .Select(t => new WorkingTransaction
        { 
            Details = t, 
            Children = new List<WorkingTransaction, 
            HasParent = false
         })
    .ToDictionary(t => t.Details.Id, t);

Now, go through the dictionary and add those that have parent references to the parent's list of children, and update the HasParent flag. At the same time, any item that doesn't have a parent is added to the "root level" list.

List<WorkingTransaction> rootParents = new List<WorkingTransaction>();

foreach (var kvp in workDict)
{
    WorkingTransaction parent;
    if (workDict.TryGetValue(kvp.Value.Details.ParentReferenceNumber, out parent)
    {
        parent.Children.Add(kvp.Value);
        kvp.Value.HasParent = true;
    }
    else
    {
        rootParents.Add(kvp.Value);
    }
}

Now, you can go through each of the parents and process each of the children:

foreach (var t in rootParents)
{
    processChildren(t.Children);
}

void ProcessChildren(WorkingTransaction t)
{
    t.Children = t.Children.OrderBy(child => child.Details.Id).ThenBy(child => child.Details.Date);
    // and recursively process the children of this transaction
    foreach (var child in t.Children)
    {
        ProcessChildren(child);
    }
}

You can use a similar recursive method to output the children in the proper order.

score 0 · Accepted Answer · answered Jun 13 '16 at 18:05

I had to create a new list in order to implement this in a simple way. I didn't want to change the client's existing object structure. Here's how I accomplished it:

var sortedList = new List<Transaction>();

foreach (var p in ListOfTransactions)
{
    if (sortedList.Contains(p))
    {
        continue; // Don't add duplicates
    }

    sortedList.Add(p); //  Add the transaction

    var child = ListOfTransactions.SingleOrDefault(x => x.ParentReferenceNumber == p.ReferenceNumber);

    if (child != null) // Add the child, if exists
    {
        sortedList.Add(child);
    }
}

score -1 · Answer 3 · answered Jun 13 '16 at 16:07

-1

You are looking for information on an object sort. Look here for more information. http://www.codeproject.com/Tips/761292/How-to-sort-an-object-list-in-Csharp

list.Sort(delegate(Member  x, Member y)
{
    // Sort by total in descending order
    int a = y.Total.CompareTo(x.Total);

    // Both Member has the same total.
    // Sort by name in ascending order
    a = x.Name.CompareTo(y.Name);

    return a;
});

answered Jun 13 '16 at 16:07

Kelso Sharp

972
8
12

This is not a simple (sequential) sort. It needs to match different properties on different objects in order to sort as intended. – 333Matt Jun 13 '16 at 18:01
Ok clearly you did not read the article, The sample I just gave you does exactly what you asked, this will give you a sorted list with descending of property values that are matching. You should be able to extrapolate the rest of the code. – Kelso Sharp Jun 14 '16 at 18:23

How can I reorder a List hierarchically according to the items' parent/child relation?

3 Answers3