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
|