Topological sort of classes

Hi all,

I have a <Set> of classes and need an <OrderedCollection> for them,
depending on
class references (topological sort, i.e. which class _references_ another
class)

What is the easiest approach to achieve this ?


Thanks
Ingo

Ingo,

> I have a <Set> of classes and need an <OrderedCollection> for them,
> depending on class references (topological sort, i.e. which class
> _references_ another class)
>
> What is the easiest approach to achieve this ?

Leaving aside the problems that are only solvable by knowing what you want
to achieve (what to do about circular references and how to order equivalent
items (two classes both reference another) for example), the following
should help get the raw data out of the image.

refs := LookupTable new.
Class allMethodsDo: [:each |
    each literals do: [:eachLiteral |
        (eachLiteral isKindOf: Class)
            ifTrue: [referenced := eachLiteral].
        ((eachLiteral isKindOf: Association)
                and: [eachLiteral value isKindOf: Class])
            ifTrue: [referenced := eachLiteral value].
        referenced notNil
            ifTrue: [
                (refs at: referenced ifAbsentPut: [Set new])
                    add: each methodClass.
                referenced := nil]]].

refs ends up as a LookupTable where the keys are each a class in the current
image and the values are the classes that reference that key.  You can use
this LookupTable to find out what to put in your OrderedCollection, once you
decide how to order it <g>

Ian

Thanks Ian,

that's what I needed.
Although I found another way, yours seems to be more efficient.

What I want to achieve is the following:
I have a Set of Classes to fileOut, and I need an ordering,
how to fileIn them again. Well, cycles are deadly here (like almost
always)...
But then, it's simply not solveable.

I know, how to order them... :-)

Ingo

"Ian Bartholomew" <[hidden email]> schrieb im Newsbeitrag
news:9k3j77$2ch1e$[hidden email]... equivalent current
> image and the values are the classes that reference that key.  You can use
> this LookupTable to find out what to put in your OrderedCollection, once
you

Ingo,

> What I want to achieve is the following:
> I have a Set of Classes to fileOut, and I need an ordering,
> how to fileIn them again. Well, cycles are deadly here (like almost
> always)...
> But then, it's simply not solveable.
>
> I know, how to order them... :-)

Another way which might be better, if you have control of the format in
which you are creating your output file, is to file out all the class
definitions first and _then_ file out all the method definitions. This is
easier to do as you then only have to arrange for the class definitions to
be in the correct hierarchical order for their position - superclasses come
before subclasses. This can be done by the following (cribbed from the
Dolphin Package class - see #fileOutClassesOn: and onwards for an
explanation)

fileOutOrder := Smalltalk allClasses intersection: yourClasses

When you file it back in you don't have to worry about methods referencing
other classes as you know that every class definition will already have been
installed into the image.

Ian

On Tue, 31 Jul 2001 08:05:15 +0100, "Ian Bartholomew"
<[hidden email]> wrote:

>Ingo,
>
>> What I want to achieve is the following:
>> I have a Set of Classes to fileOut, and I need an ordering,
>> how to fileIn them again. Well, cycles are deadly here (like almost
>> always)...
[snip]
>
>Another way which might be better, if you have control of the format in
>which you are creating your output file, is to file out all the class
>definitions first and _then_ file out all the method definitions.
[snip]

Excellant suggestion.

Eric Arseneau has implementations of SIF on his site for Dolphin,
Squeak, VW, and VAST.  He's done some really nice work with it.  I
added a couple lines of fixes for minor anomalies, but it worked like
a charm and is fast.  His current version can be downloaded from:

        http://www.pocketsmalltalk.com/sif/

I re-worked his version for Dolphin and Squeak. In it I file out the
globals, pools, then class definitions like Ian suggested and it works
like a charm.  I haven't checked Eric's site to see if he has added
them.  If not, my Dolphin, and Squeak versions are available for
downloading at my web page location:
 
        http://home.rconnect.com/~raharmon/

Might save you some work.


--
Richard A. Harmon          "The only good zombie is a dead zombie"
[hidden email]           E. G. McCarthy

Ian,

that's very cool!
Saves a _lot_ of work...

Thanks again
Ingo

"Ian Bartholomew" <[hidden email]> schrieb im Newsbeitrag
news:9k5let$2kf46$[hidden email]... come
> before subclasses. This can be done by the following (cribbed from the
> Dolphin Package class - see #fileOutClassesOn: and onwards for an
> explanation)
>
> fileOutOrder := Smalltalk allClasses intersection: yourClasses
>
> When you file it back in you don't have to worry about methods referencing
> other classes as you know that every class definition will already have
been
> installed into the image.
>
> Ian
>
>