offset 1 list indexing

[James Kuyper]

No, programmers who WON'T perform simple arithmetic that unnecessarily
complicates their code. There's a big difference.

Were you the person in that old thread who maintained that
heaps couldn't/wouldn't/shouldn't be implemented with anything
other than 1-based arrays? I've forgotten. But it's clear that
no important property of a heap depends on the raw numerical
values of the array indices: As long as you can compute the child
indices from the parent's index and vice versa, you can implement
a heap in an N-based array.

And converting between a one-based index and an N-based
index *is* simple arithmetic.

That the transformation can be done, and even that it's easy, doesn't
mean that it's a good idea to perform it. That it's not necessarily a
transformation worth performing, means that it's just plain ridiculous
to misinterpret a refusal to perform it as indicating an inability to
perform it.

 

[Malcolm McLean]

That the transformation can be done, and even that it's easy, doesn't
mean that it's a good idea to perform it. That it's not necessarily a
transformation worth performing, means that it's just plain ridiculous
to misinterpret a refusal to perform it as indicating an inability to
perform it.

If you're working with a mixture of C and Fortran you often have to
simultaneously convert between row-major to column-major, and offset
the arrays. It's too much.

 

[James Kuyper]

On 06/16/2011 09:29 AM, Malcolm McLean wrote:
....

If you're working with a mixture of C and Fortran you often have to
simultaneously convert between row-major to column-major, and offset
the arrays. It's too much.

I know, I've done it. It's not too much to do, but it's too much to do
without a good reason.

 

[Angel]

After 30 years of Fortran77, and 20 years of Fortran90+ there is no such
thing as 1-based array indexing in Fortran.
It is only the DEFAULT lower bound 1 if nothing is specified in the
declaration:
integer array(0:N)
integer array(-10:N)
integer array(N) is equivalent integer array(1:N)

It's only C being inflexible!

Fortran was designed for complex calculations, C was designed to be a
general-purpose language. There is a limit to the number of features
that can (or should) be squeezed in, and N-based arrays are not
something that would see a lot of use in generic programs.

It's easy enough to implement an N-based array in C with accessor
functions or -macros, just more work. Likewise, there are probably things
that are easy to do in C but difficult or impossible in Fortran. It's a
matter of picking the right tool for the job.

 

[Eric Sosman]

[...]
And converting between a one-based index and an N-based
index *is* simple arithmetic.

That the transformation can be done, and even that it's easy, doesn't
mean that it's a good idea to perform it. That it's not necessarily a
transformation worth performing, means that it's just plain ridiculous
to misinterpret a refusal to perform it as indicating an inability to
perform it.

"Heaps" was advanced, and I believe advanced sincerely, as a
reason to rely on one-based array indexing. That's nonsense.

 

[Michael Press]

Were you the person in that old thread who maintained that
heaps couldn't/wouldn't/shouldn't be implemented with anything
other than 1-based arrays?

Was I?

 

[James Kuyper]

[...]
And converting between a one-based index and an N-based
index *is* simple arithmetic.

That the transformation can be done, and even that it's easy, doesn't
mean that it's a good idea to perform it. That it's not necessarily a
transformation worth performing, means that it's just plain ridiculous
to misinterpret a refusal to perform it as indicating an inability to
perform it.

"Heaps" was advanced, and I believe advanced sincerely, as a
reason to rely on one-based array indexing. That's nonsense.

That's too vague, in that it depends upon what you mean by "reason to
rely on". If it was given a an example of code that's easier to write,
read, and understand when using one-based indexing, that's entirely
possible (though I cannot vouch for whether or not it's true), and no
one has suggested anything stronger than that in this thread. If, on the
other hand, they suggested that it COULD NOT be implemented with 0-based
indexing, that would be, as you say, "nonsense".

 

[Phil Carmody]

Was I?

If '/' represents selection rather than aggregation, then it
was probably me. I certainly *wouldn't* implement then 0-based
unless there was an extraordinary reason to do that. I've yet
to encounter such a reason. Having said that, looking at the
prior replies in this thread, several other people have said
that too, so there's no guarantee it was me. 0-based heaps
have carbunkles. End of.

Phil

 

[jacob navia]

Le 16/06/11 09:28, Joseph Huber a écrit :

After 30 years of Fortran77, and 20 years of Fortran90+ there is no such
thing as 1-based array indexing in Fortran.
It is only the DEFAULT lower bound 1 if nothing is specified in the
declaration:
integer array(0:N)
integer array(-10:N)
integer array(N) is equivalent integer array(1:N)

It's only C being inflexible!

1) integer array[0:N];

In C you allocate one more element and use 1 based indexing. The
zero element is left empty. Very easy

2) integer array[-10:N];

In C you set up a pointer to the 10th element and use that for indexing.

Yes, you CAN write fortran in any language, even C.

 

[Tim Rentsch]

[discussing 1-origin arrays versus 0-origin arrays]

0-based heaps have carbunkles. End of.

Please excuse my temerity, but I think you are too good
a programmer for this to be true. Take a run at writing
a 0-based heap, not just dashing it off but really trying
to do a good clean job, and see if it comes out better
than you expect. I will if you will.

 

[Eric Sosman]

[...]

[...]

I don't see what the problem is with 0 based heaps.

It's slightly awkward. In a 0 based heap the children of node n are
at nodes 2*n+1 and 2*n+2. The parent of node n is at (n-1)/2. In a 1
based heap the children of node n are at 2*n and 2*n+2; the parent of
node n is at n/2.

Tastes vary, but I prefer correct awkwardness to graceful error.

True. Then again, civilized languages let you select the array base
to suit the problem.

It's a poor workman who blames his tools.

 

[James Kuyper]

It's a poor workman who blames his tools.

That's true - but only insofar as good workmen accept responsibility for
choosing the right tool for a job, and for making sure that it's in good
working condition. The assertion that a given tool is not in good
condition, or is not the right one for a given job is (if correct) a
sign of competence, not incompetence.

I wouldn't value the ability to adjust the array base quite as highly as
he did, but that's a judgment call that may reflect the fact that I have
more, and more recent, experience with C than with Fortran.

 

[Ike Naar]

In other words, if you want to do one based indexing and you're
willing to discard a location, you do something like:

a = malloc((n+1)*sizeof(node)); /* Yes, Keith I know you don't need
parentheses for sizeof. */

In the above case, you do need them; you can re-write it as

a = malloc((n+1) * sizeof *a);

and then you don't need them.

heap = a+1;

I don't follow; if ``heap'' is supposed to be one-based, wouldn't
it simply be:

heap = malloc((n+1) * sizeof *heap); /* or ... sizeof(node) */

and then ignore heap[0], use heap[1..n], and free(heap) when done?

 

[Eric Sosman]

[...]
Tim Rentsch wrote:
[...]
I don't see what the problem is with 0 based heaps.

It's slightly awkward. In a 0 based heap the children of node n are
at nodes 2*n+1 and 2*n+2. The parent of node n is at (n-1)/2. In a 1
based heap the children of node n are at 2*n and 2*n+2; the parent of
node n is at n/2.

Tastes vary, but I prefer correct awkwardness to graceful error.

And so you should. I, on the other hand, prefer correct gracefulness
to awkward error.

Have you not spotted your mistake yet?

Yes, it's a "simple" error -- but the fact that it was made
rather cuts against the arguments that 1-based indexing for heaps
is somehow "clearer" or "more natural" than 0-based. If in fact
1-based indexing is better, why is it that you were unable to get
its arithmetic right while performing flawlessly on 0-based?

 

[Eric Sosman]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

void work_on_stuff(int *offset0, int length)
{
int offset1 = offset0 - 1;

for(idx = 1; idx<= length; idx++)
{
... offset1[idx] ...
}
}

Is this likely to fail? Possible to fail?
Very unlikely to fail? Not guaranteed by the standard?

An assinine compiler might make a big deal that offset0-1 is an address outside
the array and therefore an error. Any compiler you're likely to use won't have a
problem.

AS/400 (or whatever they're calling it these days) is rather
persnickety about addresses. I've not personally written code for
it, but an acquaintance who has done so reported

char *p = malloc(N); // assume success
char *q = p + N; // perfectly legal
q += 42; // undefined behavior -- but, hey...
q -= 42; // all back to normal now, right?
assert (q == p + N); // fails -- hey, what happened?

True, that's probing beyond the high end rather than the low. But
since the hardware detects straying in one direction, it wouldn't
surprise me at all if it detected the other.

 

[Eric Sosman]

On Sat, 25 Jun 2011 15:56:36 -0400, Eric Sosman

On 6/25/2011 2:18 PM, Richard Harter wrote:
[...]
Tim Rentsch wrote:
[...]
I don't see what the problem is with 0 based heaps.

It's slightly awkward. In a 0 based heap the children of node n are
at nodes 2*n+1 and 2*n+2. The parent of node n is at (n-1)/2. In a 1
based heap the children of node n are at 2*n and 2*n+2; the parent of
node n is at n/2.

Tastes vary, but I prefer correct awkwardness to graceful error.

And so you should. I, on the other hand, prefer correct gracefulness
to awkward error.

Have you not spotted your mistake yet?

Yes, it's a "simple" error -- but the fact that it was made
rather cuts against the arguments that 1-based indexing for heaps
is somehow "clearer" or "more natural" than 0-based. If in fact
1-based indexing is better, why is it that you were unable to get
its arithmetic right while performing flawlessly on 0-based?

Ah, you found a typo. Well done sir. I own my fault; I thought you
were called 1-based indexing an error; it didn't occur to me to check
for typos. If you want to use a typo as an argument pro/con 1-based
indexing have at it.

Already did, thanks. The fact that the error was made, and
the fact that it escaped your notice on re-reading, both somewhat
sap the strength of your argument that the 1-based code is

"a bit easier to read, write, and debug"
-- Richard Harter, 6/17/2011

 

[Michael Press]

I want to index into a list using offset one indexing.
The obvious thing to do is make a pointer that points
one element before the list.

void work_on_stuff(int *offset0, int length)
{
int offset1 = offset0 - 1;

for(idx = 1; idx <= length; idx++)
{
... offset1[idx] ...
}
}

Is this likely to fail? Possible to fail?
Very unlikely to fail? Not guaranteed by the standard?

An assinine compiler might make a big deal that offset0-1 is an address outside
the array and therefore an error. Any compiler you're likely to use won't have a
problem.

You might also allocate the array with an extra element and just ignore [0]:
int array[n+1];
for (i=1; i<=n; i++) array = f(i);
If you never use array[0], it's uninitialisedness is irrelevant.

Yes, thanks.

 

[Phil Carmody]

[discussing 1-origin arrays versus 0-origin arrays]

0-based heaps have carbunkles. End of.

Please excuse my temerity, but I think you are too good
a programmer for this to be true.

Well thanks, but it wasn't the programmer in me speaking,
it was the craftsman.

Take a run at writing
a 0-based heap, not just dashing it off but really trying
to do a good clean job, and see if it comes out better
than you expect. I will if you will.

I'm a great believer that less is more. The simplicity of
the representation of the indices in binary is the epitomy
of clean. The equivalence between length of representation
and depth of the node likewise. Nothing with a '+2' in can
ever be as clean.

I've been meaning to revisit my heap library for a while,
but I know that when I do the first thing I will do is
remove a little inefficiency, and even looking at 0-basing
it will be the last thing on my mind. Sorry.

Phil

 

[Phil Carmody]

If you're writing a heapsort,
one alternative is to use what I call a "casual heap"
where the first element is its own first child.

That's a curious approach, not one I've seen before.

Then, the children of node n are at 2*n and 2*n+1.

On the implementation that I'm using right now,
I get faster times using the casual heap
on sorting randomised arrays of long unsigned,
even though the casual heap uses
both more data comparisons and more data movement.
I think the speed difference us cache related.

http://www.mindspring.com/~pfilandr/C/e_driver/

MOV(&temp, array + parent);

I see lots of use of temp in your code. And other people complain
about [0] not being used in 1-based heaps, and therefore wasted.
Unsurprisingly, these two aspects can annihilate each other.

Phil

 

[Phil Carmody]

On 6/25/2011 11:41 PM, Richard Harter wrote:
On Sat, 25 Jun 2011 15:56:36 -0400, Eric Sosman

On 6/25/2011 2:18 PM, Richard Harter wrote:
[...]
Tim Rentsch wrote:
[...]
I don't see what the problem is with 0 based heaps.

It's slightly awkward. In a 0 based heap the children of node n are
at nodes 2*n+1 and 2*n+2. The parent of node n is at (n-1)/2. In a 1
based heap the children of node n are at 2*n and 2*n+2; the parent of
node n is at n/2.

Tastes vary, but I prefer correct awkwardness to graceful error.

And so you should. I, on the other hand, prefer correct gracefulness
to awkward error.

Have you not spotted your mistake yet?

Yes, it's a "simple" error -- but the fact that it was made
rather cuts against the arguments that 1-based indexing for heaps
is somehow "clearer" or "more natural" than 0-based. If in fact
1-based indexing is better, why is it that you were unable to get
its arithmetic right while performing flawlessly on 0-based?

Ah, you found a typo. Well done sir. I own my fault; I thought you
were called 1-based indexing an error; it didn't occur to me to check
for typos. If you want to use a typo as an argument pro/con 1-based
indexing have at it.

Already did, thanks. The fact that the error was made, and
the fact that it escaped your notice on re-reading, both somewhat
sap the strength of your argument that the 1-based code is

"a bit easier to read, write, and debug"
-- Richard Harter, 6/17/2011

Well, it wasn't code so isn't strictly relevant, but you proved his
description was easy to debug.

Phil