-----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-----