Ok, so I'm really struggeling to find a good solution to this (presumably) simple problem:

Given a class of objects, where each object can have one parent, and each parent can have multiple childs:

class Object
{
public:
	bool IsBaseOf(const Object& child) const noexcept;
private:
	Object* m_pBase;
};

How would I sort an array of X “objects” in an order, where the base-classes always come before their respective childs? I tried simply using the IsBaseOf to establish a weak-order by essentially saying “A < B if A is a base of B", but I'm not getting the correct results (I assume because the default sort-algorithm simply doesn't work with the type of mixed-sorting where only particular elements are in a certain order:

std::vector<Object*> vObjects;

// doesn't really work some of the time
std::sort(vObjects.begin(), vObjects.end(), [](const Object* pA, const ObjectA* pB)
{
	return pA->IsBaseOf(*pB);
});

Any ideas on a (somewhat efficient) and elegant way of achieving this? I know I could do crazy things like getting all root-objects, then traversing their children and putting all that are in that vector as well simply in the order of traversal, but I'm interested in whether there is somehing less complicated.

If every node knows at which level of the tree it is, you could use the tree level to sort.
If present, tree level can be found quickly by following parent pointers and counting.

I know I could do crazy things like getting all root-objects, then traversing their children and putting all that are in that vector as well simply in the order of traversal, but I'm interested in whether there is somehing less complicated.

To me that's the best solution because traversing once is faster than sort, i guess. And it's not complicated - neither needs a stack nor recursion.

JoeJ said:
If every node knows at which level of the tree it is, you could use the tree level to sort. If present, tree level can be found quickly by following parent pointers and counting.

Ah, thats sounds double, yes. I could generate that data on the fly or pregenerate it, which should do the job.

JoeJ said:
To me that's the best solution because traversing once is faster than sort, i guess. And it's not complicated - neither needs a stack nor recursion.

The problem is just that in the vector that not every element is contained in the vector that I want to sort. So this solution would be complicated because I would a) need to find the local-root elements (those whose parents are not part of the vector) and/or b) when traversing over children, I would make sure to only insert those that are actually contained, meaning I would have to build a map/set of sorts to check if object is contained in the vector. Thats what making this solution not practical in my case.

Traverse the tree in depth or breadth first order and push it into the array. It doesn't become any easier than this.

In general what you are looking for is called a topological sort:

https://en.wikipedia.org/wiki/Topological_sorting#:~:text=In%20computer%20science%2C%20a%20topological,before%20v%20in%20the%20ordering.

Dirk Gregorius said:
Traverse the tree in depth or breadth first order and push it into the array. It doesn't become any easier than this.

As I specified in my reply to JoeJ, not all elements in the tree are in the vector that I want to sort, so this would require building lookup-information to be used to see what elements actually need to be pushed when traversing the whole tree. In practice, only a limited amount of elements will be in the vector compared to the size of the tree (the use-case is a vector of classes in my visual-scripting that need to be compiled), so I think most of the time traversing the whole tree might be doing more work than just sorting. But I'm going to double-check once I got my main project up and running again.

So you have several sub-trees? Just add one ‘root’ at a time? It might become more complicated if subtrees can overlap. You can then sort by node height (as suggested above), but you still would need to care of duplicates in the vector.

Juliean said:
In practice, only a limited amount of elements will be in the vector compared to the size of the tree (the use-case is a vector of classes in my visual-scripting that need to be compiled), so I think most of the time traversing the whole tree might be doing more work than just sorting.

Eventually you could redesign your tree so some nodes own those vectors of classes/further nodes/anything that makes their child branch.
If that's possible, you could skip traversal on nodes that belong to different vectors than the current interest. And there might be other advantages, but also restrictions ofc.

Juliean said:

Ok, so I'm really struggeling to find a good solution to this (presumably) simple problem:

Given a class of objects, where each object can have one parent, and each parent can have multiple childs:

class Object
{
public:
	bool IsBaseOf(const Object& child) const noexcept;
private:
	Object* m_pBase;
};

How would I sort an array of X “objects” in an order, where the base-classes always come before their respective childs? I tried simply using the IsBaseOf to establish a weak-order by essentially saying “A < B if A is a base of B", but I'm not getting the correct results (I assume because the default sort-algorithm simply doesn't work with the type of mixed-sorting where only particular elements are in a certain order:

std::vector<Object*> vObjects;

// doesn't really work some of the time
std::sort(vObjects.begin(), vObjects.end(), [](const Object* pA, const ObjectA* pB)
{
	return pA->IsBaseOf(*pB);
});

Any ideas on a (somewhat efficient) and elegant way of achieving this? I know I could do crazy things like getting all root-objects, then traversing their children and putting all that are in that vector as well simply in the order of traversal, but I'm interested in whether there is somehing less complicated.

So basically the only order that matters, is that the parent is always before the child? If so, what if we number the elements based on their parents: An element without a parent gets 0, and every other element gets parent+1 as their number. After this you just do a numerical ascending sort, and you get an order that fulfills the above requirement. The actual numbering part could be implemented as a part of the parent→child attach mechanism, the newly attached child asks for the parents number, corrects their own, and if it has any child of their own, triggers a cascading update downstream.

Juliean said:
I assume because the default sort-algorithm simply doesn't work with the type of mixed-sorting where only particular elements are in a certain order

(respectfully) no ?

how is this defined ?

bool IsBaseOf(const Object& child)
{
 ???
}

Until then ?

Dirk Gregorius said:
So you have several sub-trees? Just add one ‘root’ at a time? It might become more complicated if subtrees can overlap. You can then sort by node height (as suggested above), but you still would need to care of duplicates in the vector.

JoeJ said:
Eventually you could redesign your tree so some nodes own those vectors of classes/further nodes/anything that makes their child branch. If that's possible, you could skip traversal on nodes that belong to different vectors than the current interest. And there might be other advantages, but also restrictions ofc.

Using tree-height to sort actually worked really well:

sys::sort(vInstances, [](const Instance* pInstance1, const Instance* pInstance2)
{
	return pInstance1->GetHierachyDepth() < pInstance2->GetHierachyDepth();
});

For completions sake though, since I seem to have failed to make it clear: My problem is, that given a certain tree of objects, like this:

- A
	-AA
	-AB
- B
	-BA
- C	
	-CA
	-CB
	-CC
		-CCA
-D

The vector that I want to sort could contain any sequence of between 0 and all elements from that tree, lets just say it now has “CC", “BA”, “B”, CCA", “AA”, “AB” and “D" in that order. My goal is/was to sort that subset of the tree that parets are always before children, so that “B” comes before “BA”, “CC” comes before “CCA”, rest doesn't matter.

ddlox said:
how is this defined ? bool IsBaseOf(const Object& child) { ??? } Until then ?

Its defined to return “true”; when the Object is eigther direct or indirect base of “child”, like in a inheritance-hierachy.