indexing
Niko Schwarz
niko.schwarz at gmx.net
Tue Jun 11 09:03:48 UTC 2002
-----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-----
More information about the Squeak-dev
mailing list
|