economizing with functions that do the same thing

[Your Uncle]

About a month ago, Heathfield posted the peudosource for random permuting
from TAOCP. It was all of maybe five lines. You needed to be able to do
two things: be able to get a random number in a range and swap. I
remembered that Dan Pop taught me to write the swap as a macro. With forum
improvements, this became:
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)
The random number comes, again with forum improvements:
int rand_in_range(i nt m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_thre shold, divisor, result, tmp, offset, num_results;

if (m>n) SWAP(m, n);
offset = m;
num_results = n - m + 1;

if (num_results == 1) {
return m;
}
roll_again_thre shold = RAND_MAX - RAND_MAX%num_re sults;
divisor = roll_again_thre shold/num_results;

do {
result = rand();
} while (result >= roll_again_thre shold);
result /= divisor;
return offset + result;
}
But then I starting thinking, and that is, of course, where the trouble
began. I posted elsewhere, and I don't think you need much of a language
background to get the gist of it:
Ich habe zwei Funktionen bei file scope erklaert:
void permute_string( char * m, int n);
void permute_int(int * m, int n);
Sie tun das genau Gleiche, allerdings erstere mit chars und letztere mit
ints. Wie werden diese Funktionen Eine?
Basically, how do I take 2 functions that differ only in the type they
operate on, and make them one? I was advised to use:
void permute (void *data, int n, size_t elsize);
that could be called for an array a with
permute(a, sizeof a / sizeof a[0], sizeof a[0]);
Is this going to work? If it isn't, then the idea is mine. If it will then
it's Erich Fruehstueck's. cheers, furunculus

[Dann Corbit]

"Your Uncle" <in*****@crippl ed.net> wrote in message
news:44******** *************** @news.usenetmon ster.com...

About a month ago, Heathfield posted the peudosource for random permuting
from TAOCP. It was all of maybe five lines. You needed to be able to do
two things: be able to get a random number in a range and swap. I
remembered that Dan Pop taught me to write the swap as a macro. With
forum improvements, this became:
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)
The random number comes, again with forum improvements:
int rand_in_range(i nt m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_thre shold, divisor, result, tmp, offset, num_results;

if (m>n) SWAP(m, n);
offset = m;
num_results = n - m + 1;

if (num_results == 1) {
return m;
}
roll_again_thre shold = RAND_MAX - RAND_MAX%num_re sults;
divisor = roll_again_thre shold/num_results;

do {
result = rand();
} while (result >= roll_again_thre shold);
result /= divisor;
return offset + result;
}
But then I starting thinking, and that is, of course, where the trouble
began. I posted elsewhere, and I don't think you need much of a language
background to get the gist of it:
Ich habe zwei Funktionen bei file scope erklaert:
void permute_string( char * m, int n);
void permute_int(int * m, int n);
Sie tun das genau Gleiche, allerdings erstere mit chars und letztere mit
ints. Wie werden diese Funktionen Eine?
Basically, how do I take 2 functions that differ only in the type they
operate on, and make them one? I was advised to use:
void permute (void *data, int n, size_t elsize);
that could be called for an array a with
permute(a, sizeof a / sizeof a[0], sizeof a[0]);
Is this going to work? If it isn't, then the idea is mine. If it will
then it's Erich Fruehstueck's. cheers, furunculus

Use a template. Oh, wait. That's C++.
;-)

The problem with the void pointer thingy is that the function taking the
void pointer will not know what is being passed in. So you are stuck with a
whole bunch of callback functions.

If I understand what you want to do, that is.

[Richard Heathfield]

Your Uncle said:

About a month ago, Heathfield posted the peudosource for random permuting
from TAOCP.
No, I didn't. I did, however, post some shuffling pseudocode and source,
just a few days ago, which was not taken from TAOCP.
It was all of maybe five lines. You needed to be able to do
two things: be able to get a random number in a range and swap.
Yes.
I
remembered that Dan Pop taught me to write the swap as a macro.
I find that surprising. I'd have thought Dan Pop would have more sense.
With
forum improvements, this became:
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)
That's fine as far as it goes, provided tmp exists and is of the appropriate
type.
The random number comes, again with forum improvements:
int rand_in_range(i nt m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_thre shold, divisor, result, tmp, offset, num_results;

if (m>n) SWAP(m, n);
offset = m;
num_results = n - m + 1;

if (num_results == 1) {
return m;
}
roll_again_thre shold = RAND_MAX - RAND_MAX%num_re sults;
divisor = roll_again_thre shold/num_results;

do {
result = rand();
} while (result >= roll_again_thre shold);
result /= divisor;
return offset + result;
}
That's ghastly, but I can see what you're doing. Presumably this bit works
fine, so let's move on.
But then I starting thinking, and that is, of course, where the trouble
began. I posted elsewhere, and I don't think you need much of a language
background to get the gist of it:
Ich habe zwei Funktionen bei file scope erklaert:
"I explained two functions with file scope", according to Babelfish.
void permute_string( char * m, int n);
void permute_int(int * m, int n);
Sie tun das genau Gleiche, allerdings erstere mit chars und letztere mit
ints. Wie werden diese Funktionen Eine?
"They do that exactly resemble, however first with chars and the latters
with ints. How do these functions become one?"
Basically, how do I take 2 functions that differ only in the type they
operate on, and make them one? I was advised to use:
void permute (void *data, int n, size_t elsize);
that could be called for an array a with
permute(a, sizeof a / sizeof a[0], sizeof a[0]);
Is this going to work?
It can be made to work.
If it isn't, then the idea is mine. If it will
then it's Erich Fruehstueck's.

I doubt whether it's either your idea or Erich Fruehstueck's.

Incidentally, this isn't really permuting. It's shuffling.

Here is a generic swapping function:

void swap(void *s, void *t, size_t len)
{
unsigned char *u = s;
unsigned char *v = t;
unsigned char tmp;
while(len--)
{
tmp = *u;
*u++ = *v;
*v++ = tmp;
}
}

Here is a generic shuffling function:

void shuffle(void *s, size_t size, size_t len)
{
unsigned char *t = s;
unsigned char *u = s;
size_t i = 0;
size_t r = 0;
for(i = 0; i < len; i++)
{
r = (len - i) * rand() / (RAND_MAX + 1.0);
swap(t + size * i, u + size * r, size);
}
}

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Your Uncle]

"Dann Corbit" <dc*****@connx. com> wrote in message
news:e7******** **@nntp.aioe.or g...

"Your Uncle" <in*****@crippl ed.net> wrote in message
news:44******** *************** @news.usenetmon ster.com...

About a month ago, Heathfield posted the peudosource for random permuting
from TAOCP. It was all of maybe five lines. You needed to be able to do
two things: be able to get a random number in a range and swap. I
remembered that Dan Pop taught me to write the swap as a macro. With
forum improvements, this became:
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)
The random number comes, again with forum improvements:
int rand_in_range(i nt m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_thre shold, divisor, result, tmp, offset, num_results;

if (m>n) SWAP(m, n);
offset = m;
num_results = n - m + 1;

if (num_results == 1) {
return m;
}
roll_again_thre shold = RAND_MAX - RAND_MAX%num_re sults;
divisor = roll_again_thre shold/num_results;

do {
result = rand();
} while (result >= roll_again_thre shold);
result /= divisor;
return offset + result;
}
But then I starting thinking, and that is, of course, where the trouble
began. I posted elsewhere, and I don't think you need much of a language
background to get the gist of it:
Ich habe zwei Funktionen bei file scope erklaert:
void permute_string( char * m, int n);
void permute_int(int * m, int n);
Sie tun das genau Gleiche, allerdings erstere mit chars und letztere mit
ints. Wie werden diese Funktionen Eine?
Basically, how do I take 2 functions that differ only in the type they
operate on, and make them one? I was advised to use:
void permute (void *data, int n, size_t elsize);
that could be called for an array a with
permute(a, sizeof a / sizeof a[0], sizeof a[0]);
Is this going to work? If it isn't, then the idea is mine. If it will
then it's Erich Fruehstueck's. cheers, furunculus
Use a template. Oh, wait. That's C++.
;-)

I'm on thin ice with topicality, so I better condemn this outrageous
suggestion.

The problem with the void pointer thingy is that the function taking the
void pointer will not know what is being passed in. So you are stuck with
a whole bunch of callback functions.

I'm not sure what that means. Maybe we could make a better trivial example:

void print_a_char(ch ar);
void print_an_int(in t);
would be definitions and then
print_a_char(ch ar g){ printf(" %c\n", g) }
print_an_int(in t g){ printf(" %d\n", g) }
Does that clarify, obfuscate, or just bore? cheers, f

[Ian Collins]

Your Uncle wrote:

"Dann Corbit" <dc*****@connx. com> wrote in message
news:e7******** **@nntp.aioe.or g...

The problem with the void pointer thingy is that the function taking the
void pointer will not know what is being passed in. So you are stuck with
a whole bunch of callback functions.

I'm not sure what that means. Maybe we could make a better trivial example:

void print_a_char(ch ar);
void print_an_int(in t);
would be definitions and then
print_a_char(ch ar g){ printf(" %c\n", g) }
print_an_int(in t g){ printf(" %d\n", g) }
Does that clarify, obfuscate, or just bore? cheers, f

For a trivial example, the overhead would outweigh the benifit of a
generic function.

For a more complex example, you are stuck with the function not knowing
the type passed in and the compiler not being able to check whether the
passed types are supported.

--
Ian Collins.

[Your Uncle]

"Richard Heathfield" <in*****@invali d.invalid> wrote in message
news:hv******** ************@bt .com...

Your Uncle said:

About a month ago, Heathfield posted the peudosource for random permuting
from TAOCP.
No, I didn't. I did, however, post some shuffling pseudocode and source,
just a few days ago, which was not taken from TAOCP.

I'm experiencing a wonderful time-dilation while rehabbing an injury. Why
doesn't time drag when you're golfing?

It was all of maybe five lines. You needed to be able to do
two things: be able to get a random number in a range and swap.

Yes.

I
remembered that Dan Pop taught me to write the swap as a macro.

I find that surprising. I'd have thought Dan Pop would have more sense.

He does, but you have to remember he was talking to me.

With
forum improvements, this became:
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)

That's fine as far as it goes, provided tmp exists and is of the
appropriate
type.

I'm surprised at how often this has caused me trouble.

The random number comes, again with forum improvements:
int rand_in_range(i nt m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_thre shold, divisor, result, tmp, offset, num_results;

if (m>n) SWAP(m, n);
offset = m;
num_results = n - m + 1;

if (num_results == 1) {
return m;
}
roll_again_thre shold = RAND_MAX - RAND_MAX%num_re sults;
divisor = roll_again_thre shold/num_results;

do {
result = rand();
} while (result >= roll_again_thre shold);
result /= divisor;
return offset + result;
}

That's ghastly, but I can see what you're doing. Presumably this bit works
fine, so let's move on.

But then I starting thinking, and that is, of course, where the trouble
began. I posted elsewhere, and I don't think you need much of a language
background to get the gist of it:
Ich habe zwei Funktionen bei file scope erklaert:

"I explained two functions with file scope", according to Babelfish.

void permute_string( char * m, int n);
void permute_int(int * m, int n);
Sie tun das genau Gleiche, allerdings erstere mit chars und letztere mit
ints. Wie werden diese Funktionen Eine?

"They do that exactly resemble, however first with chars and the latters
with ints. How do these functions become one?"

Basically, how do I take 2 functions that differ only in the type they
operate on, and make them one? I was advised to use:
void permute (void *data, int n, size_t elsize);
that could be called for an array a with
permute(a, sizeof a / sizeof a[0], sizeof a[0]);
Is this going to work?

It can be made to work.

If I fail, will a possible reason for this be that it was ill-advised to do
so as opposed to just having two awfully similar functions?

If it isn't, then the idea is mine. If it will
then it's Erich Fruehstueck's.

I doubt whether it's either your idea or Erich Fruehstueck's.

Incidentally, this isn't really permuting. It's shuffling.

Here is a generic swapping function:

void swap(void *s, void *t, size_t len)
{
unsigned char *u = s;
unsigned char *v = t;
unsigned char tmp;
while(len--)
{
tmp = *u;
*u++ = *v;
*v++ = tmp;
}
}

I'll just snipe this wholesale, thank you.
Here is a generic shuffling function:

void shuffle(void *s, size_t size, size_t len)
{
unsigned char *t = s;
unsigned char *u = s;
size_t i = 0;
size_t r = 0;
for(i = 0; i < len; i++)
{
r = (len - i) * rand() / (RAND_MAX + 1.0);
swap(t + size * i, u + size * r, size);
}
}

I'll need to take a closer look at this. Thanks and cheers, f

[Richard Heathfield]

Your Uncle said:

"Richard Heathfield" <in*****@invali d.invalid> wrote in message
news:hv******** ************@bt .com...

Your Uncle said:

Is this going to work?

It can be made to work.

If I fail, will a possible reason for this be that it was ill-advised to
do so as opposed to just having two awfully similar functions?

No. If you fail, it will be because you didn't manage to copy and paste the
code I gave you. :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Keith Thompson]

"Your Uncle" <in*****@crippl ed.net> writes:
[snip]

I've recently seen (or thought I saw) evidence that "Your Uncle",
"Frederick Gotham", and "Joe Smith" are the same person, posting under
different aliases. I recently asked you about this in the "wit's end"
thread, and you never answered.

Are "Your Uncle", "Frederick Gotham", and "Joe Smith" (or any two of
them) in fact the same person? If so, I ask you to pick a single
handle and stick with it. I don't care whether it's your real name or
not; pseudonyms are perfectly acceptable. But if you keep changing
identities, it makes the discussion more difficult to follow, with no
benefit.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[pete]

Your Uncle wrote:

"Richard Heathfield" <in*****@invali d.invalid> wrote in message
news:hv******** ************@bt .com...

Your Uncle said:

I
remembered that Dan Pop taught me to write the swap as a macro.

I find that surprising.
I'd have thought Dan Pop would have more sense.

He does, but you have to remember he was talking to me.

With
forum improvements, this became:
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)

That's fine as far as it goes, provided tmp exists and is of the
appropriate
type.

I'm surprised at how often this has caused me trouble.

This is what I use:

#define SWAP(A, B, T) \
((void)(*(T) = *(A), *(A) = *(B), *(B) = *(T)))
--
pete

[Michael Mair]

Richard Heathfield schrieb:

Your Uncle said:

I
remembered that Dan Pop taught me to write the swap as a macro.

I find that surprising. I'd have thought Dan Pop would have more sense.

It is a matter of context:
http://groups.google.de/group/comp.l...c5271ccb9149a/
somewhere around message 70 in the tree view; starting at
<2u************ *@uni-berlin.de> may suffice.
"Merrill & Michele" was the name the OP went by back then.

Dan Pop IIRC mainly argued against my suggestions of how to
"fix" the macro and pointed out how they fell short -- in
the light of that, the original swap macro was a better
solution for him.
Disclaimer: It is easily possible that I misremember -- I
just tracked down the thread but did not read it.
<snip>

#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)

<snip>
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.