Sorting IList by parent object which can be null

Question

I've been looking through the search system and not come across an answer for my problem, while these questions are similar and I even used some of them to make a start I've hit a brick wall.

I've already checked out these questions

• Algorithm for sorting a list of objects in c#
• Sorting an IList in C#

I have an object brought back by nHibernate called Person as follows

 public class Person : IPerson, IComparable<Person>{

    // private properties
    private int _id;
    private string _name;
    private Person _parent;
    private IList<Person> _children;
    private IList<Group> _groups;

    // public properties
    public virtual int id
    {
       get { return _id; }
       set { _id = value; }
    }

    public virtual string name
    {
       get { return _name; }
       set { _name= value; }
    }

    public virtual Person Parent
    {
       get { return _parent; }
       set { _parent = value; }
    }

    public virtual IList<Person> Children
    {
       get { return _children; }
       set { _children = value; }
    }

    public virtual IList<Group> Groups
    {
       get { return _groups; }
       set { _groups = value; }
    }

    // constructor
    public Person() {}

    // this section I added after looking on SO
    public virtual Int32 parentid
    {
       get {
          if (_parent == null)
          {
             return _id;
          } else {
             return _parent.id;
          }
       }
    }

    public virtual Int32 CompareTo(Person obj)
    {
       if (this.id == obj.id)
          return 0;
       return this.parentid.CompareTo(obj.parentid);
    }
 }

Then a method in my Dao which brings back a list of all the Person Objects in the database under a group. Unfortunately it brings them back in the order they were entered and I want to sort them into a parent child relationship.

 i.e. (id,name,parent)
 person 1 (1,"Alice",null)
 person 2 (2,"Bob",1)
 person 3 (3,"Charlie",null)
 person 4 (4,"Dejgo",2) // child of a child
 person 5 (5,"Edgar", null)
 person 6 (6,"Florence", 3)

When I do a sort as mentioned in this answer like so:

 class PeopleBLL : IPeopleBLL {

    // spring properties
    private IGroupsBLL _groupsBLL;
    private IPeopleDao _peopleDao;

    // public properties where spring sets up the links to the other dao and bll methods
    public IGroupsBLL {
        set{_groupsBLL = value;}
    }
    public IPeopleDao {
        set{_peopleDao= value;}
    }

    // constructor
    public PeopleBLL()
    {
    }

    // method we are interested in
    public IList<Person> GetAllInGroup(int groupID){
       //get the group object
       Group groupObject = _groupsBLL.Get(groupID); 
       // get the people in the group
       IList<Person> people = _peopleDao.GetAllInGroup(groupObject);
       // do something here to sort the people
       people.Sort();
       // return the list of people to aspx page
       return people;
    }
 }

I get the list in the format

    person 2
 person 1
    person 6
 person 3
 person 5
       person 4

but I want it in the format

 person 1
    person 2
        person 4
 person 3
    person 6
 person 5

Any ideas?

EDIT:

I didn't put the rest of this in because I didn't want to confuse the question by all the extra technologies used but since I was asked. Spring.Net is used to link up all the objects, I have a 3-tier architecture Front end (asp.net pages), Business layer, and Dao layer which communicates with the database. I have updated the GetAllInGroup() to show everything it does but it is only the sorting I am interested in. The Dao uses an nHibernate Criteria Query to get all the objects under the group as follows.

  public IList<Person> getRegistrationsForDonor(Group groupObject) {
      IList<Person> rv = CurrentSession.CreateCriteria(typeof(Person),"p")
                         .CreateCriteria("Groups","g")
                         .Add(Expression.Eq("g.id", groupObject.id))
                         .List<Person>();
      return rv;
  }

And all this is started in an aspx page in an object datasource

 <asp:ObjectDataSource ID="ObjectDataSource1" OnObjectCreating="DataSource_ObjectCreating" runat="server" DataObjectTypeName="Domain.Person"  TypeName="BusinessLayer.PersonBLL" DeleteMethod="delete" SelectMethod="GetAllInGroup" UpdateMethod="update">
    <SelectParameters>
        <asp:ControlParameter ControlID="groupid" Type="Int32" DefaultValue="0" Name="groupID" />
    </SelectParameters>
</asp:ObjectDataSource>

which is then used by a gridview, so unfortunately I need to return a sorted IList from the BLL to the front end in the BLL method as a single IList.

Edit 2

Sorry An assumption has been made that all parents will be null at the top level and I can understand where that assumption can come from but you could in theory have only children in the group so none of the object would have a parent of null. for example the following is a valid group.

 person 2 (2,"Bob",1)
 person 4 (4,"Dejgo",2) // child of a child
 person 6 (6,"Florence", 3)

which I would hope would return

 person 2
    person 4
 person 6

Edit 3

Unfortunately all of this could not be surmised in a comment so I will have to respond here.

Having tried @jon-senchyna answer at 17:30, I am definitely getting closer, I have just tried this on some live data and it is nearly there but I seem to be running into problems with the children coming before the parents in the group. Take the following example in Group 1 there are 48 people, I will highlight the ones of interest.

 (789, "person 1", null)
 (822, "Person 34", null)
 (825, "Person 37", 789)
 (3060, "Person 47", 822)
 (3061, "Person 48", 825)

This is the order they are returned from the database, but when they are put through the sort they are in the order

 Person 48 - id: 3061
 Person 37 - id: 825
 Person 1 - id: 789
 Person 47 - id: 3060
 Person 34 - id: 822

So the children are next to the parents but in the reverse order, where I would like them in the order

 Person 1 - id: 789
 Person 37 - id: 825
 Person 48 - id: 3061
 Person 34 - id: 822
 Person 47 - id: 3060

Answer 1

If you want to do this via CompareTo, you may need some more comlpex logic to handle comparing the parent trees. Below is a possible solution:

public virtual Int32 CompareTo(Person person2)
{
    Stack<Person> parents1 = GetParents(this);
    Stack<Person> parents2 = GetParents(person2);
    foreach (Person parent1 in parents1)
    {
        Person parent2 = parents2.Pop();
        // These two persons have the same parent tree:
        // Compare their ids
        if (parent1 == null && parent2 == null)
        {
            return 0;
        }
        // 'this' person's parent tree is contained in person2's:
        // 'this' must be a parent of person2
        else if (parent1 == null)
        {
            return -1;
        }
        // 'this' person's parent tree contains person2's:
        // 'this' must be a child of person2
        else if (parent2 == null)
        {
            return 1;
        }
        // So far, both parent trees are the same size
        // Compare the ids of each parent.
        // If they are the same, go down another level.
        else
        {
            int comparison = parent1.id.CompareTo(parent2.id);
            if (comparison != 0)
            {
                return comparison;
            }
        }
    }
    // We should never get here anymore, but if we do,
    // these are the same Person
    return 0;
}

public static Stack<Person> GetParents(Person p)
{
    Stack<Person> parents = new Stack<Person>();
    // Add a null so that we don't have to check
    // if the stack is empty before popping.
    parents.Push(null);
    Person parent = p;
    // Recurse through tree to root
    while (parent != null)
    {
        parents.Push(parent);
        parent = parent.Parent;
    }
    return parents;
}

Update: Both parent-stacks now contain the original person, making the comparison logic a little easier.

Answer 2

Just a consideration: You don't need to load all people. If you only load the people without a parent you will retrieve 1, 3, and 5. And you can access 2, 4 and 6 with the Children-property. To get a list of all 6 in that order (without a hierachy) you could go through the 3 root nodes recursivly and create the final list.