indexing

Karl Goiser kgoiser at bigpond.net.au
Tue Jun 11 09:48:00 UTC 2002


Why not override the OrderedCollection class and add your own methods, like:

at0:

and

at0: put:

?


After all, isn't that what object oriented programming is all about?


Karl


>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>hola!
>
>Am Dienstag, 11. Juni 2002 11:43 schrieb goran.hultgren at bluefish.se:
>
>>  > Is there a way to index OrderedCollections beginning at 0?
>>
>>  Eh, well, perhaps I don't understand the question but why not just add 1
>>  to the index you are looking for? Why do you want to index it beginning
>>
>>  >from 0?
>
>Cos I'm currently working on basic data structures, such as heaps.
>It's the same reason for which I came up with my MarkingKey: I use it e.g. to
>mark the top of a heap, so that I never have to check if I go out of bounds.
>But when the MarkingKey shall be the first element, then the "real" first
>element must be number 2, and phew: it's really buggy to always access your
>1st element as 2, the 3rd one as 4 and so on.
>But it's not only unpractical, it also steals some great conveniences.
>
>heaps typically have a replace method, which works like this:
>replace the biggest element with a new one (except when the new one is
>bigger).
>
>a nice implementation would be:
>
>replace: v
>a at: 0 put: v.
>self downheap: 0.
>^ a at: 0.
>
>So what's happening here? Well, in a heap (with element 1 at slot 1) the
>element above a[k] is always at a[k // 2]. The two elements below a[k] are
>a[2*k] and a[2*k+1].
>
>For a[0] two elements below are a[0] and a[1], so that the conditions are
>perfectly met.
>
>This, of course, does not work anymore when you start indexing at 2. Oh well,
>it would work, but then I had to indirect _every_ access by -1ing it, and
>that would be plainly ugly.
>
>So, instead of my over beautiful snippet up there, I had to implement it like
>this:
>
>replace: anElement
>	"Replace the greatest number in the heap by anElement except when 
>	anElement is greater than the top of the heap"
>	| r |
>	self size = 1
>		ifTrue: [^ self].
>	anElement
>			> (self at: 2)
>		ifTrue: [^ self].
>	r _ self at: 2 put: anElement.
>	self downheap: 2.
>	^ r
>
>regards,
>
>nick
>
>- --
>"A University without students is like an ointment without a fly."
>	-- Ed Nather, professor of astronomy at UT Austin
>-----BEGIN PGP SIGNATURE-----
>Version: GnuPG v1.0.6 (GNU/Linux)
>Comment: For info see http://www.gnupg.org
>
>iD8DBQE9Bbz0c9uyCiO8RNQRAh3RAJ9abopBmp362/3sIy982uPIecnIlACgn0Ad
>LSlA8rtG5ktcY/KBntMpKaU=
>=toOz
>-----END PGP SIGNATURE-----


-- 
----
Klaatu barada nikto    (http://www.wattle.net/klaatu.wav)



More information about the Squeak-dev mailing list