C# IComparer with respect of the hierarchy

Question

I implement IComparable / IComparer for custom sorting but I need to keep some hierarchy.

My class :

public class Attribut : IComparable
{
    public int       ATT_ID          { get; set; }
    public string    ATT_LIBELLE     { get; set; }
    public int       ATT_PARENT_ID   { get; set; }
}

The test data are as follows:

ATT_ID      ATT_LIBELLE                         ATT_PARENT_ID   
356         Avis client requis                  0
357         Nom du destinataire client          356
358         Date d'envoi au client pour avis    356
366         CNPE ?                              0
367         Palier                              366
368         Tranche                             366
369         Site                                366 
370         Materiel                            366
371         Machine                             366
372         Affaire parent                      366

I would like sorting is done ascending / descending on ATT_LIBELLE but respecting the hierarchy.

FYI, under Oracle there is the clause Order By Siblings. There is no equivalent in C #?

Here is the desired result for ascending:

ATT_ID      ATT_LIBELLE                         ATT_PARENT_ID   
356         Avis client requis                  0
358         Date d'envoi au client pour avis    356
357         Nom du destinataire client          356
366         CNPE ?                              0
372         Affaire parent                      366
371         Machine                             366
370         Materiel                            366
367         Palier                              366
369         Site                                366
368         Tranche                             366

Here is the desired result for descending:

ATT_ID      ATT_LIBELLE                         ATT_PARENT_ID   
366         CNPE ?                              0
368         Tranche                             366
369         Site                                366
367         Palier                              366
370         Materiel                            366
371         Machine                             366
372         Affaire parent                      366
356         Avis client requis                  0
357         Nom du destinataire client          356
358         Date d'envoi au client pour avis    356

It's possible in C# ?

Thanks all!

EDIT :

Here is the code of the IComparable implementation :

public static IComparer sortAscending_ATT_LIBELLE       { get { return new sortLibelleAscendingHelper(); } }
public static IComparer sortDescending_ATT_LIBELLE      { get { return new sortLibelleDescendingHelper(); } }

private class sortLibelleAscendingHelper : IComparer
{
    int IComparer.Compare(object a, object b)
    {
        var oAtta = (a as Attribut);
        var oAttb = (b as Attribut);

        if (a == null || b == null) { return 0; }

        int ret = (oAtta.ATT_LIBELLE).CompareTo(oAttb.ATT_LIBELLE);

        if ((oAtta.ATT_PARENT_ID != oAttb.ATT_PARENT_ID) || (oAtta.ATT_PARENT_ID == oAttb.ATT_ID))
        {
            ret = 1;
        }

        return ret;
    }
}

private class sortLibelleDescendingHelper : IComparer
{
    int IComparer.Compare(object a, object b)
    {
        var oAtta = (a as Attribut);
        var oAttb = (b as Attribut);

        if (a == null || b == null) { return 0; }

        int ret = (oAttb.ATT_LIBELLE).CompareTo(oAtta.ATT_LIBELLE);

        if ((oAtta.ATT_PARENT_ID != oAttb.ATT_PARENT_ID) || (oAtta.ATT_PARENT_ID == oAttb.ATT_ID))
        {
            ret = -1;
        }

        return ret;
    }
}

what do you mean by "respecting the hierarchy" What hierarchy? — Sam I am says Reinstate Monica, Aug 10 '18 at 16:55
I propose you make your own comparer class and pass this on to the sort method. This gives tou full control of the sorting. — Aldert, Aug 10 '18 at 17:02
@Aldert That's what I did, but I can not find the right comparison algorithm ... — WDKyle, Aug 10 '18 at 17:27
OK, From your example, I could only see that you are using IComparable, which has not been implemented. So please show us your code so we can understand what you have been doing so far. At the same time, I understand what you look for so will do an effort for you. — Aldert, Aug 10 '18 at 17:36
You are on the right track but feels like you overcomplicate. That said, I need some time think this through... — Aldert, Aug 10 '18 at 17:58
I did tests with a path ID also but it did not work better. Thank you for your interest — WDKyle, Aug 10 '18 at 18:01
@SamIam The element with ATT_ID = 358 is the children of the element with ATT_ID = 356 for example — WDKyle, Aug 10 '18 at 18:08

score 1 · Answer 1 · answered Aug 10 '18 at 17:28

Your data structure is incompatible with IComparable. IComparable implements pairwise comparisons: in other words, given any two elements, you need to be able to know their relative ordering. In your example, this is not possible, since your data structure is a tree and comparing two elements requires the context of the whole tree structure.

The challenge with implementing sorting for your data is that the representation you're working with is its flattened, relational representation. There might be a clever in-place way to sort it, but if you convert it to an in-memory tree representation like this, the sorting becomes straightforward:

public class AttributNode
{
    public Attribut       ATTRIBUT        { get; set; }
    public AttributNode[] CHILDREN        { get; set; }

    public void Sort() {
        foreach (Attribut child in CHILDREN) {
            child.Sort();
        }

        Array.Sort(
            CHILDREN,
            (x, y) => x.ATTRIBUT.ATT_LIBELLE.CompareTo(y.ATTRIBUT.ATT_LIBELLE));
    }

    IEnumerator<Attribut> Flatten()
    {
        yield return ATTRIBUT;

        foreach (IEnumerable<Attribut> items in CHILDREN.Select((c) => c.Flatten()))
        {
            foreach (Attribut item in items) {
                yield return item;
            }
        }
    }
}

Building the tree from the flattened representation should be covered in other answers like this one.

Thank you but I do not know if it is compatible with the rest of my code. I have a List linked to a DataGrid and so with your solution I do not see how to bind all the elements ... — WDKyle, Aug 10 '18 at 17:51

Aldert · Accepted Answer · 2018-08-14T06:02:33.550

Here the complete code, it is not elegant but working. On the constructor of the comparer I create a shadowdictionary keeping track of Parent_Libelle. This is to do proper sorting. You can do ascending sorting by setting Order to true.

using System;
using System.Collections.Generic;
using System.Reflection;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {

        static void Main(string[] args)
        {
            List<Attribut> sortList = new List<Attribut>();
            sortList.Add(new Attribut() { ATT_ID = 356, ATT_LIBELLE = "Avis client requis", ATT_PARENT_ID = 0 });
            sortList.Add(new Attribut() { ATT_ID = 357, ATT_LIBELLE = "Nom du destinataire client", ATT_PARENT_ID = 356 });
            sortList.Add(new Attribut() { ATT_ID = 358, ATT_LIBELLE = "Date d'envoi au client pour avis", ATT_PARENT_ID = 356 });
            sortList.Add(new Attribut() { ATT_ID = 366, ATT_LIBELLE = "CNPE ?", ATT_PARENT_ID = 0 });
            sortList.Add(new Attribut() { ATT_ID = 367, ATT_LIBELLE = "Palier", ATT_PARENT_ID = 366 });
            sortList.Add(new Attribut() { ATT_ID = 368, ATT_LIBELLE = "Tranche", ATT_PARENT_ID = 366 });
            sortList.Add(new Attribut() { ATT_ID = 369, ATT_LIBELLE = "Site", ATT_PARENT_ID = 367 });
            sortList.Add(new Attribut() { ATT_ID = 370, ATT_LIBELLE = "Materiel", ATT_PARENT_ID = 367 });
            sortList.Add(new Attribut() { ATT_ID = 371, ATT_LIBELLE = "Machine", ATT_PARENT_ID = 366 });
            sortList.Add(new Attribut() { ATT_ID = 372, ATT_LIBELLE = "Affaire parent", ATT_PARENT_ID = 366 });



            Random rand = new Random();
            for (int i = 0; i < 30; i++)
            {
                int ra = rand.Next(10);
                Attribut move = sortList[ra];
                sortList.RemoveAt(ra);
                sortList.Add(move);
            }

            sortList.Sort(new CompareAttribut(sortList, false));

            foreach (Attribut oneAtt in sortList)
            {
                Console.WriteLine(oneAtt.ATT_ID + " " + oneAtt.ATT_LIBELLE + " " + oneAtt.ATT_PARENT_ID);
            }

        }

        public class CompareAttribut : IComparer<Attribut>
        {
            private class AttributTree
            {
                private Attribut self;
                public AttributTree(Attribut Self)
                {
                    self = Self;
                }
                public Attribut Self
                {
                    get { return self; }
                }
                public AttributTree Parent { get; set; }

                public string [] SortorderLib { get; set; }

            }

            private bool order = false;

            private Dictionary<int,AttributTree> kHelpers = new Dictionary<int, AttributTree>();
            public CompareAttribut(List<Attribut> StartList, bool Order)
            {

                order = Order;

                foreach (Attribut a in StartList)
                {
                    int key = a.ATT_ID;
                    AttributTree at = new AttributTree(a);


                    //string value = a.ATT_PARENT_ID > 0 ? StartList.Single(p => p.ATT_ID == a.ATT_PARENT_ID).ATT_LIBELLE : a.ATT_LIBELLE;

                    kHelpers.Add(key, at);
                }

                //Create the tree
                foreach (AttributTree at in kHelpers.Values)
                {
                    at.Parent = kHelpers[at.Self.ATT_ID];
                }

                foreach (AttributTree at in kHelpers.Values)
                {
                    List<string> libelles = new List<string>();
                    libelles.Add(at.Self.ATT_LIBELLE);
                    AttributTree up = at;

                    while (up.Self.ATT_PARENT_ID != 0)
                    {
                        up = kHelpers[up.Self.ATT_PARENT_ID];
                        libelles.Insert(0, up.Self.ATT_LIBELLE);
                    }

                    at.SortorderLib = libelles.ToArray();
                }



            }

            public int Compare(Attribut x, Attribut y)
            {
                string[] xParentLib = kHelpers[x.ATT_ID].SortorderLib;
                string[] yParentLib = kHelpers[y.ATT_ID].SortorderLib;

                int i = 0;

                int outcome = 0;
                while (outcome == 0)
                {
                    if (i == xParentLib.Length) outcome = -1;//x above y
                    else if (i == yParentLib.Length) outcome = 1;//x  under y
                    else outcome = xParentLib[i].CompareTo(yParentLib[i]);
                    if (outcome == 0)
                    {
                        i++;
                        continue;
                    }
                    break;
                }
                return outcome * (order ? 1 : -1); 
            }
        }

        public class Attribut
        {
            public int ATT_ID { get; set; }
            public string ATT_LIBELLE { get; set; }
            public int ATT_PARENT_ID { get; set; }
        }
    }
}

It works great! I'm going to adapt your code for my application because I'm currently using a ListCollectionView and the CustomSort method but it should not be too hard :) thanks ! — WDKyle, Aug 11 '18 at 11:39
I come to realize a little trouble is that an "Attribut" can be parent and have son... Do you think your code is adaptable to manage x levels? — WDKyle, Aug 13 '18 at 16:38
It's great ! I just tested by adding: sortList.Add(new Attribut() { ATT_ID = 400, ATT_LIBELLE = "sous Affaire", ATT_PARENT_ID = 372 }); Thaaaaanks ! — WDKyle, Aug 13 '18 at 19:21
I have an IndexOutOfRangeException randomly on the following line: int outcome = xParentLib[i].CompareTo(yParentLib[i]) * (order ? 1 : -1); I'm going to look at what's wrong :) — WDKyle, Aug 13 '18 at 19:54

C# IComparer with respect of the hierarchy

2 Answers2