Velocity Reviews > Re: ruler

Re: ruler

Phil Carmody
Guest
Posts: n/a

 12-08-2009
superpollo <(E-Mail Removed)> writes:
> hello clc.
>
> this is a simple program based on sedgewick's algorithms in c, 3ed,
> pag. 202. it draws a ruler (like this:
> http://cs.oberlin.edu/~jdonalds/150/ruler-final.png), recursively
> defined upon the height of middle mark.
>
> superpollo@192.168.1.152:~/test\$ cat ruler.c
> #include <stdio.h>
> #include <stdlib.h>
> #include <math.h>
> #define ENOUGH 10000

> void Mark(int Ruler[] , int Pos , int Height)

If this is a private helper function not for general use,
consiser marking it as static.

to be mostly lower case.

> {
> Ruler[Pos] = Height;
> }
> void Rule(int Ruler[] , int Left , int Right , int Height)
> {
> int Middle = (Left+Right)/2;
> if (Height > 0)
> {
> Rule(Ruler , Left , Middle , Height-1);
> Mark(Ruler , Middle , Height);
> Rule(Ruler , Middle , Right , Height-1);
> }

Well, odd things will happen if odd lengths are encountered.

> }
> void PrintRlr(int Ruler[] , int Last)

Ruler's not modified, nor would you want it to be modified -
make it const.

> {
> int Pos , Height;
> for (Pos = 0 ; Pos <= Last ; Pos++)
> {
> for (Height = 1 ; Height <= Ruler[Pos] ; Height++)

C loops desiring N repetitions traditionally count from 0 to N,
exiting once <N is false, rather than counting from 1 to N+1,
exiting once <=N is false.

> printf("-");
> printf("\n");

Consider putchar() instead for calls so simple.

> }
> }
> int main(int argc, char *argv[])
> {
> int Ruler[ENOUGH];
> int MaxHt;
> int Last;
> if (argc == 1)
> {
> printf("usage: %s HEIGHT_OF_MIDDLE_MARK\n" , argv[0]);
> return EXIT_FAILURE;
> }
> MaxHt = atoi(argv[1]);
> Last = pow(2 , MaxHt);

No need for floating point. Just use << to create a power of 2.

> Ruler[0] = 0;
> Ruler[Last] = 0;

But for pity's sake check it's within a usable range before using it.

> Rule(Ruler , 0 , Last , MaxHt);
> PrintRlr(Ruler , Last);
> return EXIT_SUCCESS;
> }
> superpollo@192.168.1.152:~/test\$ cc -ansi -pedantic -Wall -o ruler
> ruler.c -lm
> superpollo@192.168.1.152:~/test\$ ./ruler
> usage: ./ruler HEIGHT_OF_MIDDLE_MARK
> superpollo@192.168.1.152:~/test\$ ./ruler 4
>
> -
> --
> -
> ---
> -
> --
> -
> ----
> -
> --
> -
> ---
> -
> --
> -
>
> superpollo@192.168.1.152:~/test\$
>
> any comments and suggestions are more than welcome, and so is criticism.

While printing the ruler, also print out Pos^(Pos-1) using %x as the
format string. See if you can find a relationship between the value
printed and the length of the tick mark printed.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

Phil Carmody
Guest
Posts: n/a

 12-08-2009
superpollo <(E-Mail Removed)> writes:
> Phil Carmody ha scritto:
>> superpollo <(E-Mail Removed)> writes:
>>> hello clc.

>
> mr carmody,
>
> i would like to thank you for your very thorough comments, and i would
> take further advantage of you courtesy -- so to speak -- by asking
> for some deeper explanation (or pointer to relevant documents such as
> the faq).

It's late. It's probably best someone else chimes in. Still daytime
in the land of Keith, for example ...

>>> this is a simple program based on sedgewick's algorithms in c, 3ed,
>>> pag. 202. it draws a ruler (like this:
>>> http://cs.oberlin.edu/~jdonalds/150/ruler-final.png), recursively
>>> defined upon the height of middle mark.
>>>
>>> superpollo@192.168.1.152:~/test\$ cat ruler.c
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>> #include <math.h>
>>> #define ENOUGH 10000

>>
>>> void Mark(int Ruler[] , int Pos , int Height)

>>
>> If this is a private helper function not for general use,

>
> what is the meaning of "private helper function" ?

I just meant that it's a function that exists only in order to help
out a few other functions in the same module, but isn't intended to
be used by arbitrary other code.

>> consiser marking it as static.

>
> of not doing so?

You don't pollute the global namespace if you don't make it visible
to the outside world.

>> Your choice of capitalisation may turn a few heads. C tends
>> to be mostly lower case.

>
> i read at pag. 41 of c unleashed (heathfield) that mixed case is an
> option, though. also, sedgewick uses this style too from time to time.

Everything's an option. (Apart from the few things that aren't.)

>>> {
>>> Ruler[Pos] = Height;
>>> }
>>> void Rule(int Ruler[] , int Left , int Right , int Height)
>>> {
>>> int Middle = (Left+Right)/2;
>>> if (Height > 0)
>>> {
>>> Rule(Ruler , Left , Middle , Height-1);
>>> Mark(Ruler , Middle , Height);
>>> Rule(Ruler , Middle , Right , Height-1);
>>> }

>>
>> Well, odd things will happen if odd lengths are encountered.

>
> given that the first invocation of Rule is given a power-of-2 RIght
> argument, successive recursive calls are warranted to be given too (or
> so sedgewick claims). the case Right == 1 is ok, since then it is
> Height == 0, so no call is performed.

You might want to add a check that the parameter is indeed a power
of 2, or at least even, to ensure that nothing unexpected happens.
However, if you know that the only function(s) calling it will call
it with an appropriate argument, then the chances are that it can
be made a static function too. If you export it, then it might be
called by someone who doesn't play by your rules.

>>> }
>>> void PrintRlr(int Ruler[] , int Last)

>>
>> Ruler's not modified, nor would you want it to be modified -
>> make it const.

>
> now for a silly question: Last is not mod too, so why not const int
> Last also?

Because Ruler represents memory referenced by some other part of the
code. In fact, despite what it looks like, it's a pointer to that
memory. Arrays and pointers to their first element were designed to
look practically identical, such that if you see the use of one you
can rarely know whether it's one or the other. The extreme case of
that is the use of array syntax to represent the pointer in examples
such as the above. C physically cannot pass naked arrays by value,
the above int Ruler[] is an illusion. (And you can pass them by
wrapping them in other things too, but that's another matter.)

>>> {
>>> int Pos , Height;
>>> for (Pos = 0 ; Pos <= Last ; Pos++)
>>> {
>>> for (Height = 1 ; Height <= Ruler[Pos] ; Height++)

>>
>> C loops desiring N repetitions traditionally count from 0 to N,
>> exiting once <N is false, rather than counting from 1 to N+1,
>> exiting once <=N is false.

>
> ok in general, and i thought about it writing it in the first place,
> but in this case Height denotes the height of the mark, which goes
> from 1 to Ruler[Pos] included. would not the other way be more opaque?

I'm not asking you to change how you represent the height of the mark,
merely suggesting a more common idiom for counting up to it.

And just as an aside - I'm sure I saw 2 height 0 gaps in your ruler
that followed. It looks like you too easily forget 0s.

It might be because I take the lift up 1 floor to get to the 1st
floor, and up 6 floors to get to the th floor that I'm perfectly happy
counting from zero.

>>> printf("-");
>>> printf("\n");

>>
>> Consider putchar() instead for calls so simple.

>
> ok.
>
>>> }
>>> }
>>> int main(int argc, char *argv[])
>>> {
>>> int Ruler[ENOUGH];
>>> int MaxHt;
>>> int Last;
>>> if (argc == 1)
>>> {
>>> printf("usage: %s HEIGHT_OF_MIDDLE_MARK\n" , argv[0]);
>>> return EXIT_FAILURE;
>>> }
>>> MaxHt = atoi(argv[1]);
>>> Last = pow(2 , MaxHt);

>>
>> No need for floating point. Just use << to create a power of 2.

>
> like this?
>
> Last = 1 << MaxHt;

That would do.

>>> Ruler[0] = 0;
>>> Ruler[Last] = 0;

>>
>> But for pity's sake check it's within a usable range before using it.
>>

>
> like this?
>
> ...
> MaxHt = atoi(argv[1]);
> Last = 1 << MaxHt;
> if (Last > ENOUGH-1)
> return EXIT_FAILURE;

It's possible to break even that. Checking MaxHt itself catches the
problem even earlier. However, it's possible to confuse atoi with
deliberately crafted strings, so the safest way is to use a function
which lets you know that it's parsed the value unambiguously and
correctly. I believe that strtol does a far better job than atoi.

> Ruler[0] = 0;
> ...
>
>>> Rule(Ruler , 0 , Last , MaxHt);
>>> PrintRlr(Ruler , Last);
>>> return EXIT_SUCCESS;
>>> }
>>> superpollo@192.168.1.152:~/test\$ cc -ansi -pedantic -Wall -o ruler
>>> ruler.c -lm
>>> superpollo@192.168.1.152:~/test\$ ./ruler
>>> usage: ./ruler HEIGHT_OF_MIDDLE_MARK
>>> superpollo@192.168.1.152:~/test\$ ./ruler 4
>>>

That was height 0, I'm sure.

>>> -
>>> --
>>> -
>>> ---
>>> -
>>> --
>>> -
>>> ----
>>> -
>>> --
>>> -
>>> ---
>>> -
>>> --
>>> -
>>>
>>> superpollo@192.168.1.152:~/test\$
>>>
>>> any comments and suggestions are more than welcome, and so is criticism.

>>
>> While printing the ruler, also print out Pos^(Pos-1) using %x as the
>> format string. See if you can find a relationship between the value
>> printed and the length of the tick mark printed.

>
> superpollo@192.168.1.152:~/test\$ grep -A 10 "void DisplayRlr" ruler02.c
> void DisplayRlr(const int Ruler[] , int Last)
> {
> int Pos , Height;
> for (Pos = 0 ; Pos <= Last ; Pos++)
> {
> printf("%x\t" , Pos^(Pos-1));
> for (Height = 1 ; Height <= Ruler[Pos] ; Height++)
> putchar('-');
> putchar('\n');
> }
> }
> superpollo@192.168.1.152:~/test\$ cc -ansi -pedantic -Wall -o ruler
> ruler02.c -lm
> superpollo@192.168.1.152:~/test\$ ./ruler 4
> ffffffff
> 1 -
> 3 --
> 1 -
> 7 ---
> 1 -
> 3 --
> 1 -
> f ----
> 1 -
> 3 --
> 1 -
> 7 ---
> 1 -
> 3 --
> 1 -
> 1f
> superpollo@192.168.1.152:~/test\$
>
> mmm... seems like the binary representation of Pos... in fact
> sedgewick wrote something similar in the following pages (counting the
> number of trailing zeros in the binary rep of even integers).

Bingo!

> thanks for help and insight.

It's a pleasure having someone learning who not only asks appropriate
questions, but also pays attention to the answers. Now pay attention
to all the people who correct me!

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1