can a character be negative?

[Phil Carmody]

I've seen people implement Heapsort in C by sticking an
unused [0] element at the start of the array, so maybe you're
right that some people find array indexing difficult to fathom.
Personally, I think such people are in the wrong line of work.

It simplifies the code greatly, and even works as a perfect place to
build a new entry before inserting it, for example. I think your
ability to comprehend others' code and designs must be lacking.

If it's used for building a new entry before inserting, then it
isn't "unused." I don't think you're disagreeing as much as you
think you are.

It's unused in the heap. The heap is defined by the heap property,
and [0] doesn't have that property.

Phil

 

[bartc]

So what's the outcome? In the original 1-based heap we had
(assuming integer division for array indices)

parent [j] -> child [2*j]
parent [j] -> child [2*j+1]
child [j] -> parent [j/2]

In the 0-based heap we have

parent [k] -> child [2*k+1]
parent [k] -> child [2*k+2]
child [k] -> parent [(k-1)/2]

Is the code for the 1-based heap simpler? Yes, by one + operator
and one - operator. Is the code "greatly" simpler? Yes, for
anybody who thinks one + and one - amount to a "great" complexity.
A person who boggles at that trivial level of complication will very
likely have a hard time as a computer programmer.

It's not a question of one scheme using a extra symbol or two more than
another. Some people think better 1-based, and others 0-based; if that extra
symbol is in the wrong place then it's more than trivial.

And if an algorithm is being adapted from elsewhere, it's best to stick to
it's original array base, if you want it to still work.

 

[Eric Sosman]

So what's the outcome? In the original 1-based heap we had
(assuming integer division for array indices)

parent [j] -> child [2*j]
parent [j] -> child [2*j+1]
child [j] -> parent [j/2]

In the 0-based heap we have

parent [k] -> child [2*k+1]
parent [k] -> child [2*k+2]
child [k] -> parent [(k-1)/2]

Is the code for the 1-based heap simpler? Yes, by one + operator
and one - operator. Is the code "greatly" simpler? Yes, for
anybody who thinks one + and one - amount to a "great" complexity.
A person who boggles at that trivial level of complication will very
likely have a hard time as a computer programmer.

It's not a question of one scheme using a extra symbol or two more than
another. Some people think better 1-based, and others 0-based; if that
extra symbol is in the wrong place then it's more than trivial.

And if an algorithm is being adapted from elsewhere, it's best to stick
to it's original array base, if you want it to still work.

Okay. Given a C array, zero-based by its nature, how would
you apply the Heapsort algorithm to it if you insist on the 1-based
formulation? The only route I can see is to malloc() (or in C99,
VLA) an array one slot larger, copy the original data into the new
array with a plus-one offset, Heapsort the tail of the new array,
copy the sorted data back, and (if not VLA-ed) free() the scratch
array.

Well, no, that's not the "only" way. You might Heapsort all
the elements except the [0], then do binary search to find where
the [0] element actually belongs, then slide everything over and
stuff it into place. (You can do this without additional space
to store that [0] element if you use the triple-reverse trick.)
Of course, this hybrid is not precisely "Heapsort" any more, but
"Mostly Heapsort, with an admixture of other stuff."

Please comment on the relative complexity of these solutions
in comparison to the index transformation I've shown. For the
first, be sure to specify how to proceed if malloc() returns NULL
(or if the array is too big for a VLA).

 

[Phil Carmody]

I've seen people implement Heapsort in C by sticking an
unused [0] element at the start of the array, so maybe you're
right that some people find array indexing difficult to fathom.
Personally, I think such people are in the wrong line of work.
It simplifies the code greatly, and even works as a perfect place
to build a new entry before inserting it, for example. I think
your ability to comprehend others' code and designs must be
lacking.
If it's used for building a new entry before inserting, then it
isn't "unused." I don't think you're disagreeing as much as you
think you are.

It's unused in the heap. The heap is defined by the heap property,
and [0] doesn't have that property.

The heap property is that each node's key is >= those of
its children, if it has any. (Or <=, if you're building a heap
the other way around.) Another important feature of a heap is
that there is a simple way to calculate the indices of the
children from the index of the parent, and to calculate the
index of a parent from the index of a child. The calculation
is simple, no matter where the heap indices start.

But I sense you are unconvinced. All right, let's go through
the transformation; maybe it will be instructive.

In the traditional description of a heap, we number the nodes
from 1 to N and adopt the convention that the children of node
number j are the nodes with numbers 2*j and 2*j+1. If we store
these in a 1-based array, so the indices match the node numbers,
we say that the node at index [j] has children at [2*j] and [2*j+1].
The parent of the node numbered j is the node numbered floor(j/2);
with 1-based indexing we navigate from a child at [j] to a parent
at [floor(j/2)]. Agreed?
Agreed.

Okay: Let's put this heap into a zero-based array. We can
begin by simply storing the node whose number is j at the array
index [j-1], which we'll call index [k] for expository purposes:
The node whose number is j gets stored at index [k], with k==j-1.
The node at index [k] has node number j, with j=k+1. With me?

With you.

Now to the parent->child calculations. If we've got a parent
at index [k], its node number is j=k+1. The node numbers of its
children are 2*j==2*(k+1)==2*k+2 and 2*j+1==2*(k+1)+1==2*k+3. We
then subtract 1 to get the indices where those node numbers are
stored; they are at [2*k+1] and [2*k+2]. A parent at index [k]
has children at [2*k+1] and [2*k+2]. Clear?
Clear.

Finally, the child->parent calculation. If we've got a child
at index [k], its node number is j=k+1. The node number of its
parent is floor(j/2)==floor((k+1)/2). The node with that number
is stored at index [floor(j/2)-1], which is [floor(j/2-1)], which
is [floor((k+1)/2-1)] which is [floor((k-1)/2)]. A child at index
[k] has a parent at index [floor((k-1)/2)]. Still clear?

Still clear.

Having said that, you may have sneaked some deliberate mistakes into
the above in order to trick me, in which case haha, it worked, as I
didn't actually read them, as I already understand perfectly well how
a heap works. Quite what gave you the impression otherwise, I know not.

So what's the outcome? In the original 1-based heap we had
(assuming integer division for array indices)

parent [j] -> child [2*j]
parent [j] -> child [2*j+1]
child [j] -> parent [j/2]

In the 0-based heap we have

parent [k] -> child [2*k+1]
parent [k] -> child [2*k+2]
child [k] -> parent [(k-1)/2]

Is the code for the 1-based heap simpler? Yes

Right, we're in perfect agreement up to here.

, by one + operator
and one - operator. Is the code "greatly" simpler? Yes, for
anybody who thinks one + and one - amount to a "great" complexity.

You've doubled the length of two thirds of the expressions from
being a single operator to being two operators. So most of the time
it's twice as verbose.

A person who boggles at that trivial level of complication will very
likely have a hard time as a computer programmer.

Fortunately I don't boggle at the complication, I boggle at the
programmer who would chose that lack of simplicity.

I likewise boggle why people do the following, which I saw in the
linux kernel, for example, only yesterday:

t1*p=getp();
foo(p->q->r1);
bar(p->q->r2);
baz(p->q->r3);
//...
quux(p->q->rN);

rather than
t1*p=getp();
t2*q=p->q;
foo(q->r1);
bar(q->r2);
baz(q->r3);
//...
quux(q->rN);

Yet I have no problem understanding the complexity of pointers to
pointers, even when N reaches exceeds the number of fingers I possess.

Similarly, I boggle at why people do the following, which I again saw in
some never-gonna-be-accepted-into-the-mainline-ever module for the linux
kernel only yesterday:

void*p=getp();
((t1*)p)->q1=r1;
((t1*)p)->q2=r2;
((t1*)p)->q3=r3;
//...
((t1*)p)->qN=rN;

rather than the following:

void*p=getp();
t1*pt=(t1*)p;
pt->q1=r1;
pt->q2=r2;
pt->q3=r3;
//...
pt->qN=rN;

Despite my ability to understand the concept of casting pointers, even
when N reaches the heady heights of, oooh, I think I saw about 40 in one
function.

In each of those, I do genuinely prefer the expression with 1 operator
than the expression with 2 operator. Really. I believe it's tangibly
less complicated at the source code level. Yes, it's only one operator,
maybe I'm just sensitive to wasted characters.

In summary - p>>1 is a thing of beauty, (p-1)/2 is gross.

(Another, and possibly simpler way to figure out the navigation
is to imagine using the illegal ptr=array-1 hack and then formulate
the heap in terms of 1-based indexing with ptr. Return to legality
by substituting array-1 for each appearance of ptr in the solution,
then simplify the indices. I didn't use that route, because people's
alarms might have gone off as soon as they saw the hack, and they might
have thought the solution itself was somehow contaminated by it.
Hence the somewhat longer "change of variable" construction shown.)

Extra credit: Imagine yourself using a language like Pascal,

You sadist!

where arrays can have any index ranges you like. Figure out the
parent->child and child->parent navigation for a heap in an array
whose indices start at [-42]. Comment on the complexity of your
solution.

Computational complexity identical, but entirely lacking elegance.

Funnily enough, I'm going to venture into user-space today or next
week and have to use [2]-based addressing for something, gack.

Phil

 

[Phil Carmody]

So what's the outcome? In the original 1-based heap we had
(assuming integer division for array indices)

parent [j] -> child [2*j]
parent [j] -> child [2*j+1]
child [j] -> parent [j/2]

In the 0-based heap we have

parent [k] -> child [2*k+1]
parent [k] -> child [2*k+2]
child [k] -> parent [(k-1)/2]

Is the code for the 1-based heap simpler? Yes, by one + operator
and one - operator. Is the code "greatly" simpler? Yes, for
anybody who thinks one + and one - amount to a "great" complexity.
A person who boggles at that trivial level of complication will very
likely have a hard time as a computer programmer.

It's not a question of one scheme using a extra symbol or two more
than another. Some people think better 1-based, and others 0-based; if
that extra symbol is in the wrong place then it's more than trivial.

For reference, I think better 0-based.
Floor-wise, the 1st floor is 1 floor above the ground floor.
And I'm with Bourbaki regarding the natural numbers.

Phil

 

[Chris M. Thomasson]

Rahul wrote: [...]
2.and in what scenarios should I define a character as unsigned?

You shouldn't. If you know that it is a character, use char. Only use
unsigned char if you're storing numbers rather that characters.

Well, mostly. The is*() and to*() functions in <ctype.h> expect
arguments representable as an unsigned char (or the value EOF).

Wishy-washy-signedness of chars is full of traps - your list isn't
exaustive.

Once can reduce to:



#define xxx_ctype_invoke(f, a) f((unsigned int)a)

#define xislower(a) xxx_ctype_invoke(islower, a)
#define xisupper(a) xxx_ctype_invoke(isupper, a)
/* ... */



?

 

[bartc]

bartc wrote:

Okay. Given a C array, zero-based by its nature, how would
you apply the Heapsort algorithm to it if you insist on the 1-based
formulation? The only route I can see is to malloc() (or in C99,
VLA) an array one slot larger, copy the original data into the new
array with a plus-one offset, Heapsort the tail of the new array,
copy the sorted data back, and (if not VLA-ed) free() the scratch
array.

You mean, given an array which is already indexed from [0], to apply a
1-based algorithm to it in an efficient manner?

What about creating a pointer to the array, pointing at the [-1] element? Or
if it's already a pointer, to temporary subtract 1 from it:

int array[]={1,2,3,4,5,6,7,8,9,10};
int *onearray;
int i;

onearray = array-1;

for (i=1; i<=10; ++i) printf("%2d: %d\n",i,onearray);

In practice you'd just subtract 1 from any array passed to a function
implementing such an algorithm.

 

[bartc]

[... concerning the "perversity" of CHAR_MIN != 0 ...]

(If you entered a skyscraper and found floor 0 was half-way up the
building,
that wouldn't seem odd?)

It would seem quite usual, aside from the odd numbering.
I haven't checked to be absolutely sure, but I don't think
I've ever been in a skyscraper whose ground floor was its
bottommost floor, and I doubt that you have, either.

(My analogy was not quite right. A more apt one is a building with 256
floors, numbered normally from 0 (European ground floor) up to 127. Then the
next floor is at -128! Then counting up towards floor -1, the 256th floor.

This is workable (although a bit awkward, for example, when you want to know
whether one floor is above or below another), but undeniably "perverse".)

 

[Stefan Ram]

For reference, I think better 0-based.
Floor-wise, the 1st floor is 1 floor above the ground floor.
And I'm with Bourbaki regarding the natural numbers.

See also:

http://www.purl.org/stefan_ram/pub/zero

.

 

[Chris Dollin]

You mean, given an array which is already indexed from [0], to apply a
1-based algorithm to it in an efficient manner?

What about creating a pointer to the array, pointing at the [-1] element?

That would provoke undefined behaviour.

Or if it's already a pointer, to temporary subtract 1 from it:

That might provoke undefined behaviour, depending on where the
poitner pointed.

int array[]={1,2,3,4,5,6,7,8,9,10};
int *onearray;
int i;

onearray = array-1;

Undefined behaviour. BOOM. Or, more worryingly, no boom /today/.

Attempting to form a pointer to a place that does not exist before
an array is undefined, just as forming a pointer more than 1 past
the upper end is undefined, just as dereferencing a pointer one
past the upper end of an array is undefined.

--
"My name is Hannelore Ellicott-Chatham. I *end messes*." Hannelore,
/Questionable Content/

Hewlett-Packard Limited registered office: Cain Road, Bracknell,
registered no: 690597 England Berks RG12 1HN

 

[Ben Bacarisse]

Rahul wrote:
[...]
2.and in what scenarios should I define a character as unsigned?

You shouldn't. If you know that it is a character, use char. Only use
unsigned char if you're storing numbers rather that characters.

Well, mostly. The is*() and to*() functions in <ctype.h> expect
arguments representable as an unsigned char (or the value EOF).

Wishy-washy-signedness of chars is full of traps - your list isn't
exaustive.

Once can reduce to:

#define xxx_ctype_invoke(f, a) f((unsigned int)a)

#define xislower(a) xxx_ctype_invoke(islower, a)
#define xisupper(a) xxx_ctype_invoke(isupper, a)

How does that help? It may just be insufficient coffee, but i can't
see how converting a signed char to a large positive number meets the
requirements imposed by the ctype functions. In fact, it seems to add
another problem if the large unsigned value can't be represented as an
int. That's not UB, but since the conversion can do anything
including raising a signal it is almost as troublesome as UB.

 

[Eric Sosman]

bartc wrote:

Okay. Given a C array, zero-based by its nature, how would
you apply the Heapsort algorithm to it if you insist on the 1-based
formulation? The only route I can see is to malloc() (or in C99,
VLA) an array one slot larger, copy the original data into the new
array with a plus-one offset, Heapsort the tail of the new array,
copy the sorted data back, and (if not VLA-ed) free() the scratch
array.

You mean, given an array which is already indexed from [0], to apply a
1-based algorithm to it in an efficient manner?

Yes, exactly. Can you use Heapsort on a C array, or must
you simply write off the algorithm as un-C-worthy because
"some people think better 1-based?"

What about creating a pointer to the array, pointing at the [-1]
element? Or if it's already a pointer, to temporary subtract 1 from it:

That's "the illegal ptr=array-1 hack" I mentioned in an
earlier message. It is the subject of Question 6.17 in the
comp.lang.c Frequently Asked Questions (FAQ) list, found at
<http://www.c-faq.com/>. Perhaps it's time you renewed your
acquaintance with the FAQ.

 

[bartc]

You mean, given an array which is already indexed from [0], to apply
a 1-based algorithm to it in an efficient manner?

What about creating a pointer to the array, pointing at the [-1]
element?

That would provoke undefined behaviour. ...
That might provoke undefined behaviour, depending on where the
poitner pointed. ....
Undefined behaviour. BOOM. Or, more worryingly, no boom /today/.

OK. You have a deadline to meet, and you are 100% certain your architecture
has no problem with manipulating such pointers, provided they dereferenced
with the correct offset or index.

What would you do? Make a quick workaround such as my suggestion (assuming
it worked), start reallocating and copying large arrays (and hoping no
pointers existed to part of the original array), or start rewriting someone
else's complicated algorithm?

 

[Eric Sosman]

[... lengthy development of trivial transformation ...]

Having said that, you may have sneaked some deliberate mistakes into
the above in order to trick me,

I am less duplicitous than you suppose, and perhaps than
you deserve.

[...] I already understand perfectly well how
a heap works. Quite what gave you the impression otherwise, I know not.

Your own words gave me that impression: "The heap is defined
by the heap property, and [0] doesn't have that property," which
suggests to me that you have at best a muddled idea of how a
heap works.

> [... concerning the "great" complication of inserting one
> addition and one subtraction ...]
Fortunately I don't boggle at the complication, I boggle at the
programmer who would chose that lack of simplicity.

I boggle at the programmer who would reject an algorithm
simply because the numeric values of array indices are not the
same as the numeric values of the subscripts in a textbook.
See also "The Fox and the Grapes."

>> Extra credit: Imagine yourself using a language like Pascal,

>
> You sadist!
>

>> where arrays can have any index ranges you like. Figure out the
>> parent->child and child->parent navigation for a heap in an array
>> whose indices start at [-42]. Comment on the complexity of your
>> solution.

>
> Computational complexity identical, but entirely lacking elegance.

... so if somebody handed you a minus-42-based array your
response would be "I refuse to Heapsort it because it's not
elegant enough for me?"

Algorithms are algorithms. Implementations are realizations
of them. There is no compelling reason to transliterate notation
between the two domains when the notation creates inconveniences.
If the algorithm is described in terms of a_sub_j and you are
implementing it with array references jimjam[k], there is no
fundamental reason to insist on k==j, just as there is no reason
to rename the array from jimjam[] to a[]. Notation is not Fate.

 

[bartc]

bartc wrote:

another. Some people think better 1-based, and others 0-based; if that
extra symbol is in the wrong place then it's more than trivial.

And if an algorithm is being adapted from elsewhere, it's best to stick
to it's original array base, if you want it to still work.

Okay. Given a C array, zero-based by its nature, how would
you apply the Heapsort algorithm to it if you insist on the 1-based
formulation?

You mean, given an array which is already indexed from [0], to apply a
1-based algorithm to it in an efficient manner?

Yes, exactly. Can you use Heapsort on a C array, or must
you simply write off the algorithm as un-C-worthy because
"some people think better 1-based?"

I'm not familiar with heapsort (for that matter, I rarely use any sort of
sort, if that makes sense).

Ideally these algorithms need to be carefully converted to 0-based, if one
has the time. But I've found these base-conversions are error-prone.

What about creating a pointer to the array, pointing at the [-1] element?
Or if it's already a pointer, to temporary subtract 1 from it:

That's "the illegal ptr=array-1 hack" I mentioned in an
earlier message.

Oh.

It is the subject of Question 6.17 in the

comp.lang.c Frequently Asked Questions (FAQ) list, found at
<http://www.c-faq.com/>. Perhaps it's time you renewed your
acquaintance with the FAQ.

OK. It's illegal because the Standard can't guarantee it will work on every
machine. So it was not a good idea to suggest it on usenet but presumably an
individual programmer can choose to ignore the restriction for his machine,
if that's balanced by some obvious benefit (eg. less work).

(BTW I agree it's a bit of a hack. I once had to implement a language
feature for allocated arrays where the lower-bound could be anything. The
choice was for the array pointer to always point to a phantom element 0, or
to the first element but at a cost of an extra offset when indexing. I chose
the latter; I thought pointers pointing into the middle of other variables
was an untidy way of doing things)

 

[Seebs]

It is if you're a complete idiot. "Normal" in the context normally used
FREQUENTLY means the "majority".

Yes, and sometimes doesn't. Making the term ambiguous, and leaving the
reader free choice of how to interpret it.

e.g It is normal for people to look left and right when crossing the
road.

I wouldn't consider that to be a "majority" usage. But then, I live in
a small town.

I find it disturbing that you two are rubbing up against each other and
gloating about another show of outstanding pedantic dickness.

Well, here you are gloating about your interpretation of words, too.

-s

 

[Seebs]

Then you need to learn to read or actually look at the threads.

I read quite well, thank you. I do admit to not being very responsive
to some kinds of "status" cues -- but that's caused me to study how people
perceive them, and learn that many people appear to misinterpret some
kinds of tone-free communication as though it were arrogant.

This
newsgroup is quite unique in technical circles : nasty, pedantic god
botherer types who like nothing more than to bully and belittle others
who challenge for their self perceived dominant role in the group.

This language reminds me a great deal of language I've seen from other people
who are so extremely status-aware that they aren't aware that their status
awareness is not an external reality, but an internally-generated
interpretation of the world.

In short: I doubt that Richard Heathfield is thinking in terms of a "dominant
role". He comes across as a bit pedantic and focused on technical matters
rather than persons. That may be callous at times, and I certainly know that
I sometimes hurt people by not thinking about them when I'm busy thinking
about interesting technical questions. However, it also pretty much
excludes any concept of a "self-perceived dominant role".

Your theory here is based very much on speculation as to motive, and I would
suggest that you check out your evidence for that speculation carefully. Not
everyone you meet on Usenet has the same emotional or social responses you
do.

-s

 

[Antoninus Twink]

What's with the "we"? Have we a new tag team in Carmody and
Heathfield? Kind of creepy.

Yes - I think there's no longer any doubt that Carmody is the latest
occupant of the spot on the branch behind Heathfield where he can pick
the fleas from the alpha male's coat.

This group is truly a case study in sociology. Heathfield always says
that the way relationships involving him develop is nothing to do with
his personality, but we see exactly the same things time and again with
him!

Eventually there's no way you can believe it's just coincidence. He's
simply a magnet both for fan-boys and for ant-fan-boys.

On the submissive side, there have been a whole string of lackeys
wanting to gain Heathfield's favor by attacking those who can see
through him and obsequiously embracing his eccentric opinions, e.g. that
C99 is evil.

And on the other side, there have now been so many people over so many
years who've had a personality clash with Heathfield that it's just not
believable that he's really Mr Nice Guy, and all these other people are
psychopaths.

It's clear that Heathfield is a damaged individual, and his personal
issues have been the cause of deep problems in this group.

 

[BGB / cr88192]

On 30 Sep, 00:49, "BGB / cr88192" <[email protected]> wrote:

[char] is normally signed, since this is what a majority of the
compilers on
a majority of the common architectures do.

granted, it is not safe to rely on this, and hence I often use an
explicit signed type if it really matters.

Then you're using the word "normally" in a manner that's inconsistent
with the way I and, I believe, most other people use it.

Something is not "normal" just because it's in the majority, and it
certainly isn't abnormal just because it's in the minority.

normal == "common as to the point of not typically being considered".

for example, "in the US people normally speak English".
this does not, for example, deny the existence of Mexicans, only that
people
can "normally" disregard the possibility of them using Spanish when
engaging
in conversations with people.

not a very good example given the number of Spainish speakers.
Not everyone who speaks Spainish is Mexican or of Mexican origin.

in the US those who speak Spanish are normally Mexicans...

not that there are not other people who speak Spanish (such as Cubans,
people from Spain, ...), but their presence in the US can be largely ignored
given the strong majority held on this front by the Mexicans.

either way, people in the US, Mexican or not, normally speak English (except
in the minority of cases where they are not, as one can note via Univision
and Telemundo and similar, or in grocery stores, ...).

a strong majority rules de-facto.


granted, in this usage, normal is essentially a synonym for common, although
it is stronger as there is a difference in terms of the level of majority
implied in each case.

for example, people are commonly right handed (for example, I am outside
this group in being left-handed), however, computers are normally x86
(32/64) and run Windows.

it is not an axiom, simply a probability...

 

[Seebs]

granted, in this usage, normal is essentially a synonym for common, although
it is stronger as there is a difference in terms of the level of majority
implied in each case.

It's not at all obvious to me that it's always "stronger".

Examples:

* Many people would argue that a particular human experience of grief is
"normal", although particular experiences or feelings may occur in only
a few percent of the population.
* There is fierce debate over whether or not it is reasonable to call
homosexuality "normal", but it seems to occur in somewhere between 3 and
10 percent of the population.
* Depending on context, people might describe left-handedness as either
"abnormal" or "perfectly normal".

The real problem, which these cases highlight, is the confusion between
statistical norms and normative norms. Even among the statistical
norms, there is ambiguity about whether you mean "this is the most common
case" or "this case is common enough that it is not cause for special
remark". For instance, left-handedness is not so uncommon that you would
be likely to wonder why someone is left-handed, but blindness is rare
enough that you might well be curious about it -- it's sufficiently atypical
to merit some kind of search for an explanation.

for example, people are commonly right handed (for example, I am outside
this group in being left-handed), however, computers are normally x86
(32/64) and run Windows.

it is not an axiom, simply a probability...

The vast majority of devices which run code written in C are not x86 devices
running Windows.

-s