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.
michi - 27.Oct 2005 21:08 -
technisches
Michi a.k.a. 'Michael Platzer' is one of the Knallgraus, a Vienna-based New Media Agency, that deals more and more with 'stuff' that is commonly termed as Social Software.
