Sorting a tree of classes ( was Properties of "<" ... )

[squeak-dev] Properties of "<" in SortedCollection>>#sortBlock - reflexive, symmetric, transitive required?

Hi Milan,

Squeak is often much simpler than you think.
A sort block is only required to answer true or false.
True means a sorts before b and false vice-versa.

So the questions you raise are side stepped.

How do you intend to deal with siblings? 
(Classes that have the same parent?).
Can you associate a tree level with each class? 
(the lowest level has no children 
the next level only children from the lower etc.)
The sort would be highest level first then next highest etc.)
If two classes are at the same level 
then you would use the second sort criterion.

[ :each :eachOther |  each level = eachOther level 
						ifTrue: [ "...secondary search" ]
						ifFalse: [ each level < eachOther level ] .

where level accessing the tree level which you will probably have to compute beforehand.

Something like: 

youngerClasses := OrderedCollection new .

unOrderedClasses := OrderCollection new withAll: myClasses .

[ unOrderedClasses isEmpty ] whileFalse: [ | thisLevel | 
	thisLevel := 
	  unOrderClasses select: [ :each | 
		each child isNil or: [ youngerClasses includes: each child ] ] .
	unOrderedClasses removeAll: thisLevel .
	youngerClasses addAll: thisLevel . ]

of course at this point the reverse of the youngerClasses list will be a reasonable load order.

This is pseudo-code. You have to fill in the missing pieces.
You would have to define #child or find the right method to express it. 
Ditto #level.  I also don't guarantee the other methed selectors 
I used to be exactly the right names. 
I am just conveying the jist of a solution.

Good luck.

hth,

Yours in curiosity and service, --Jerome Peace



***
Milan Zimmermann milan.zimmermann at sympatico.ca 
Sun May 4 10:39:55 UTC 2008 wrote:
>Hi,
>
>Is the "<" opertaion in SortedCollection>>#sortBlock required to be
>reflexive, 
>symmetric and transitive ? 
>
>I have a set of classes with known parent class and try to sort them so they 
>install into the image in the right order (parent first). The obvious "<" 
>implementation of parent < child may not be enough because it not transitive 
>unless I do some more sophisticated manipulation (I only immediate descendant 
>relationship)..
>
>The sortBlock documentation provides no help on this...
>
>Thanks Milan
***



      ____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ