Programming Challenge

[Steve Summit]

In article <1990Dec15.015355.15683 at fmrco> harold at fmrco (Harold Naparst) writes:
>I am trying to write a function which will return the index
>of the smallest element of an array.  I want the routine
>to work for any type array.

[Someone may well already have suggested this; I might have
missed it because my news feed appears to be flakey.]

Since the question was crossposted to comp.lang.c, here's the
straight-C answer, which doesn't involve any mucking about with
derived or generic types.  The caller does, on the other hand,
have to provide a comparison routine appropriate for the data
type being searched.  (Come to think of it, this probably isn't
what Mr. Naparst was looking for at all.  Oh, well, the technique
is instructive, and understanding it helps avoid problems when
using qsort and bsearch.)

Given

	sometype array[SOMESIZE];

and

	int sometypecmp(void *p1, void *p2)
	{
	sometype *sp1 = (sometype *)p1;
	sometype *sp2 = (sometype *)p2;

	if(*sp1 < *sp2)
		return -1;
	else if(*sp1 == *sp2)
		return 0;
	else	return 1;
	}

(this could return *sp1 - *sp2 if overflow wasn't a problem, and
might have to use more complicated relationals for nonarithmetic
types),

we can call

	findbiggest(array, SOMESIZE, sizeof(sometype), sometypecmp);

where findbiggest is

	findbiggest(void *a, size_t n, size_t elsize, int (*cmp)(void*,void*))
	{
	void *biggest = a;
	register int i;
	char *p2;		/* not void * so can do pointer arithmetic */

	for(i = 1, p2 = (char *)a + elsize; i < n; i++, p2 += elsize)
		{
		if((*cmp)(p2, biggest) > 0)
			biggest = p2;
		}

	return ((char *)biggest - (char *)a) / elsize;
	}

(Actually, a more likely implementation, closer to bsearch, would
return a pointer to the largest element, not the index.)

                                            Steve Summit
                                            scs at adam.mit.edu