How to sort a list so that managers are always ahead of their subordinates (How do I do a topological sort in Groovy, or an FP language)

Question

I am working on a project using Groovy, and I would like to take an array of employees, so that no manager follows their subordinates in the array. The reason being that I need to add people to a database and I would prefer not to do it in two passes.

So, I basically have:

<employees>
  <employee>
     <employeeid>12</employeeid>
     <manager>3</manager>
  </employee>   
  <employee>
     <employeeid>1</employeeid>
     <manager></manager>
  </employee>   
  <employee>
     <employeeid>3</employeeid>
     <manager>1</manager>
  </employee>   
</employees>

So, it should be sorted as such:

employeeid = 1
employeeid = 3
employeeid = 12

The first person should have a null for managers.

I am thinking about a binary tree representation, but I expect it will be very unbalanced, and I am not certain the best way to do this using Groovy properly.

Is there a way to do this that isn't going to involve using nested loops?

Answer 1

http://en.wikipedia.org/wiki/Topological_sorting

Assuming that each employee other than the CEO has exactly one manager, I would insert all of the employee records into an associative structure that maps each employee ID to a list of their direct reports. Now we call the following recursive procedure on the CEO:

def recursiveinsert(e):
    insert e into the database
    for each direct report d of e:
        recursiveinsert(d)