4-variable mapping into an array

Question

I need to choose an aray item based on the values of 4 variables, as shown below, in C.

  0  | 1  | 0  | -1 | array[1][0]
  -1 | 0  | 1  | 0  | array[1][1]
  0  | -1 | 0  | 1  | array[1][2]
  1  | 0  | -1 | 0  | array[1][3]

  1  | 0  | 0  | -1 | array[2][0]
  1  | 0  | 0  | 1  | array[2][1]
  -1 | 0  | 0  | 1  | array[2][2]
  -1 | 0  | 0  | -1 | array[2][3]

  0  | 1  | -1 | 0  | array[3][0]
  0  | 1  | 1  | 0  | array[3][1]
  0  | -1 | 1  | 0  | array[3][2]
  0  | -1 | -1 | 0  | array[3][3]

(The order of the second column in the array isn't important and can be reordered if needed.)

While it's possible (and completely acceptable) to just stick all the possibilities in 12 chained ifs, I'd like to see if anyone can come up with a "cleaner" solution.

EDIT: to clarify: I want a function f(a,b,c,d) where (for example) f(0, 1, 0, -1) returns the value held in array[1][0].

Answer 1

Put the table you posted in array and search in it with a loop for the correct entry. This way you will code data as data and not as code.

Any cleverer method will generate undue maintenance work once your mapping specification changes. Unless the performance of the loop is proven to be unsufficient I would use the loop.

Answer 2

I've described this solution in a way which is slightly less efficient than it could be to make it easier to explain; the more concise version is easily derived from what I have shown here.

Map the values -1, 0, and 1 to 0x00, 0x01, and 0x02, and store them, using 2 bits per value, in an 8-bit value so e.g. your array values correspond to the following numbers:

array[1][0]: binary value 01100100 = 0x64
array[1][1]: binary value 00011001 = 0x19
array[1][2]: binary value 01000110 = 0x46
array[1][3]: binary value 10010001 = 0x91

Create an array for all 255 possible values which can be held in an 8-bit value (note that some entries won't be used, i.e. any with both bits set to 1 - this is the inefficiency I mentioned).

So e.g.

array[0] points to the appropriate array for -1, -1, -1, -1
array[1] points to the appropriate array for -1, -1, -1, 0
array[2] points to the appropriate array for -1, -1, -1, 1
array[3] points nowhere

array[4] points to the appropriate array for -1, -1, 0, -1
array[5] points to the appropriate array for -1, -1, 0, 0
array[6] points to the appropriate array for -1, -1, 0, 1
array[7] points nowhere

(etc, obviously)

And then all you need is a single lookup, with no loop, to get the right array (or whatever you are keying to).

In the more concise solution, the table has no entries pointing to nowhere.

EDIT:

In this case, with array as above, the desired function is:

f(a,b,c,d) {
       return array[(a+1) << 6 + (b+1) << 4 + (c+1) << 2 + (d+1)];
} 

Answer 3

Revise your way of thinking and recognise that an array IS a function, from a set of indices to a set of values. Looked at this way, you would want to define your array like this:

  array[0][1][0][-1] = value currently in array[1][0]
  array[-1][0][1][0] = value currently in array[1][1]
  etc

Now, it's unfortunate that C can't directly index arrays with arbitrary ranges of integers, but you could get round this in one of two ways:

• defining constants such as one=1,zero=0,minusone=2 and use those in your array expressions;
• use an offset such as adding 1 to every index and subtracting it when you make a reference to the array, eg array[1-1][2-1][1-1][0-1].

Of these two the former is probably preferable.

Finally, this array will have entries for values not in your table, you'll have to put some sort of null code into them.

Answer 4

In addition to approaches suggested by @James McLeod and @High Performance Mark you could use the auto-generated switch statement:

f(a,b,c,d) {
  switch(ind(a,b,c,d)) {
# include "cases.h"
  default: assert(0);
  };
}

Where ind():

enum { BASE = 3 };
int ind(int a, int b, int c, int d) {
  // ind() should produce the same result as the one from the script (see below)
  return (BASE*(BASE*(BASE*(a+1) + b+1) + c+1) + d+1);
}    

And cases.h:

case 48: return  array[1][0];
case 16: return  array[1][1];
case 32: return  array[1][2];
case 64: return  array[1][3];
case 66: return  array[2][0];
case 68: return  array[2][1];
case 14: return  array[2][2];
case 12: return  array[2][3];
case 46: return  array[3][0];
case 52: return  array[3][1];
case 34: return  array[3][2];
case 28: return  array[3][3];

cases.h could be generated by the following script:

#!/usr/bin/env python
import csv, fileinput

# parse stdin or file(s) given at command-line as csv-file
rows = ((map(int, row[:-1]), row[-1])
        for row in csv.reader(fileinput.input(), delimiter='|') if row)

# function that arranges indexes in C-order
# . any function that produces unique integers will do
# . -1 <= n <= 1
ind = lambda args, base=3: reduce(lambda acc, n: base*acc + (n+1), args, 0)

# print cases for switch(ind(a,b,c,d)) statement
print '\n'.join("case %d: return %s;" % (ind(indexes), value) 
                for indexes, value in rows if value)

The script accepts as an input the table from your question.