[Newbies] Objects graph

[Levente Uzonyi]

On Thu, 27 Sep 2012, Mateusz Grotek wrote:

> Dear Squeakers,
> I have the following problem:
> Please imagine objects as a directed graph.
> What I want to do is to run a method exactly once for each object. I can
> do it in O(N*log(N)) time by using a tree or other datastructures. It
> seems it's impossible to do it in O(N). The reason for that is there is
> a comment in Object class which  says I should not extend it by adding
> any additional instance variables.

The common solution to your problem is to use an IdentitySet to hold 
already visited objects. Since it is a hash table, and hash tables offer 
O(1) average access time, therefore your algorithm will have O(N) average 
runtime cost. If your object graph is expected to be larger than a few 
thousand objects, then I suggest you to give my LargeIdentitySet a try, 
which offers better performance in that case:
http://leves.web.elte.hu/squeak/LargeIdentitySet.st

>
> Additional points:
> 1. I want to be able to do this for ANY object, so subclassing and
> adding an instance variable to a subclass won't work. (imagine for
> example, that I need to create an extension of Smalltalk which should
> work with all current Smalltalk classes, or something like that)
> 2. I cannot create an isomorphic graph with some other objects (of a
> special class created by me), because I do not know how to detect
> sharing of subobjects and cycles.
>
> Is there a nice solution of this problem? What would happen if I add an
> instance variable to Object (besides more memory used)? Do you think
> adding one instance variable to Object class as a standard feature of
> Squeak's library would break anything. This variable could be used for
> example in veryDeepCopy etc. Maybe it's not a good idea...

The system would hang. The VM has some expectations for the slots of some 
classes. For example it expects that the 3rd slot of a Process is its 
myList instance variable. If you add an instance variable to Object, then 
the index of the myList variable will be the 4 instead of 3.


Levente

>
> Kind regards,
> Mateusz
> _______________________________________________
> Beginners mailing list
> Beginners at lists.squeakfoundation.org
> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>