michi bloggt!

TASK:
Given: An (unsorted) array of objects. Each of these objects can have a parent object defined, that is also contained in that array.
Problem: Determine an order for this array, that guarantees that for each object its parent object is positioned further to the beginning of the array.
Background: I am parsing an unsorted array of files, creating a database object for each of these files. Since i also need to store the parent reference for these objects, i had to pre-sort that array, so that when i loop through it, i can be certain that the parent object already exists (and that i know its unique id for the foregin reference)

SAMPLE:

• tick with parent donald
• dagobert with no parent defined
• trick with parent donald
• donald with parent dagobert

-> correct order: dagobert, donald, tick, trick

SOLUTION:

unsortedArray; // the unsorted array of objects
var sortedArray = new Array();
for (var i=0; i<unsortedArray.length; i++) {
  var obj = unsortedArray[i];
  if (obj.parent == null) {
    // position objects without parent at the beginning
    sortedArray.unshift(obj); 
  } else if (Array.contains(sortedArray, obj.parent)) {
    // position objects, with a parent that 
    // is already contained, at the end
    sortedArray.push(obj);  
  } else {
    // if parent is not contained yet, then we append 
    // it to the end of the original array
    unsortedArray.push(obj);
  }
}

Problem: A circular reference (dagobert is parent of donald, and donald is parent of dagobert) must be caught by breaking out of the loop at some point.