[comp.lang.c] Table lookups

jlh@loral.UUCP (The Mad Merkin Hunter) (06/26/88)

Lets say I have a value that can range from 0-15 and I want to print
an ascii string based on that value.  Normally I create an array of
strings and index into it.  K&R does this with the names of the months
when they talk about arrays of pointers.  Now lets say that instead of
index values from 0-15 I have bit positions, i.e., the values are
0x1, 0x2, 0x4, ..., 0x80.  I'd like to do a table lookup on these values
also, as opposed to building a switch statement.  The only methods I
can come up with take a lot longer and are much less clear than the
switch statement (for example, logarithms).  Anyone got any ideas?

To quell the flames rising in your breasts, let me say that this isn't
one of the major questions of the universe.  It's just that for the
kind of programming I do this comes up quite a bit, and my sense of
order gets it's nose tweaked everytime I type in the 'case 0x?? :doit;break'
sequence.


							Jim


-- 
Jim Harkins 
Loral Instrumentation, San Diego
{ucbvax, ittvax!dcdwest, akgua, decvax, ihnp4}!ucsd!sdcc6!loral!jlh

gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/27/88)

Consider using an array of (value, function) pairs; search this table
for a matching value then execute the corresponding function.  (If the
table is sorted by value, you can use bsearch() to search it.)

jk@hpfelg.HP.COM (John Kessenich) (06/28/88)

    How about taking the log (base 2) of your number?  Here is a
    (maybe too slow) way of doing this.

    t = bitvariable;
    i = -1;
    while (t) {
        t >>= 1;
	++i;
    }

    It takes your number (bitvariable) and leaves log base 2 in i, assuming
    bitvariable contains exactly one on-bit.

leo@philmds.UUCP (Leo de Wit) (07/03/88)

In article <1802@loral.UUCP> jlh@loral.UUCP (The Mad Merkin Hunter) writes:
>Lets say I have a value that can range from 0-15 and I want to print
>an ascii string based on that value.  Normally I create an array of
>strings and index into it.  K&R does this with the names of the months
>when they talk about arrays of pointers.  Now lets say that instead of
>index values from 0-15 I have bit positions, i.e., the values are
>0x1, 0x2, 0x4, ..., 0x80.  I'd like to do a table lookup on these values
>also, as opposed to building a switch statement.  The only methods I
>can come up with take a lot longer and are much less clear than the
>switch statement (for example, logarithms).  Anyone got any ideas?

A general solution is a function that maps values to natural numbers;
for instance if you have a function log2(n) that returns the base 2 logarithm
of a number (leaving in the middle what should be returned if the number
is not a power of 2) then you have your problem solved. For instance:

      answer = table[log2(n)];

(You probably have to check the range of the function before using it).

This scheme is also useful as an alternative to switch cases; you could do
something like:

some_type firstf(), secondf(), thirdf(); 

some_type (*funcarr[])() = { firstf, secondf, thirdf };

some_type some_var;

    /* now use it ... */

    some_var = (*funcarr[log2(n)])(param);

especially when you have much code in the switch cases, this can be a real
nice alternative.

Consider a single key command editor; the mapping function degenerates
to a simple cast to unsigned char (if the input character value hadn't
already this type) - possibly preceded by a simple range check -, the
array of functions are the diverse actions to be performed for each input
(including 'invalid key' actions: sounding the bell), a parameter is
the 'current count' for instance, the return value is a boolean indicated
whether there was a problem.
Another nice example is a disassembler that uses the (first part of
the) opcode to index into an array of functions that handle moving,
shifting, logic, control flow, arithmetic etc. I've done that for a 68K
disassembler (hint:  use the first 4 bits of the instruction word to
index into an array of 16 functions).

As for the log2 function itself, some suggestion has already been made.

       Leo.