Nick,

I don't understand at all what you are saying. First of all, you don't
need zero-based indexing for heaps (check out Squeak's builtin class
Heap). Secondly, if you want to introduce some boundary element all you
need to do is to make sure it always sorts correctly. So given your code
snipped all you should have to do is to write:

replace: v
	a at: 1 put: v.
	self downheap: 1.
	^ a at: 1.

What's wrong with that? Incidentally, I don't get the problem with your
current implementation because it does things that the above does not do
(and never can). First of all, it checks if the heap is empty - and
that's an operation which would be required no matter if you do
zero-based indexing or not. Secondly, it seems pretty clear that your
boundary element must sort wrongly since otherwise you wouldn't need any
of these checks at all. It might even make sense to exclude the boundary
element completely from the heap since a test for "array size = 0" or
somesuch is almost at zero cost.

Cheers,
  - Andreas


> -----Original Message-----
> From: squeak-dev-admin at lists.squeakfoundation.org 
> [mailto:squeak-dev-admin at lists.squeakfoundation.org] On 
> Behalf Of Niko Schwarz
> Sent: Tuesday, June 11, 2002 11:04 AM
> To: squeak-dev at lists.squeakfoundation.org
> Subject: Re: indexing
> 
> 
> -----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-----
> 
>