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

Answer 1

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

Answer 2

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.