2-Dimension matrix to 1-D array, index translations.

Work has me working with hardware registers. Many registers; arrayed registers; multi-arrayed registers!.

The verifiction library I use has code to handle 1-D arrays of registers but not for 2-d (matrix) of registers - which is the problem I have today.

Problem Statement

A useful description of the problem is:
Given a 2-D matrix of values to store and access in a system that allows the storingof 1-D arrays of values, how do you map from the 2-D x,y indices to the 1-D i index - and vice-versa?

Partial memory

It's several decades since I first looked into this but I do remember divmod! Divmod was a part of the solution: divmod(x, y) returns (x // y, x % y) i.e the integer divisor and the integer remainder of x and y, as a tuple.

Rather than "do the math" to work out the correct functions needed to generate a 1-D array index i, from two matrix indices x and y - as well as the reverse function - I decided to take a suck-it-and-see approach. I had ideas that contain the correct solution and devised tests to reject faulty implementations.

Setup

1. Indices in any dimension count up from zero.
2. Use a different maximum index in each matrix dimension to aid later checks
3. I created function irange (line 14+), as sometimes people like to generate integer ranges that include both endpoints.

1-D to 2-D

Variable i_to_xy_list on lines 35+, has the source for four functions alternatives that when given a 1-D index generate a tuple of index numbers representing x and y. All four use divmod.

To test them I create a python function from the text using eval in line 50 then, knowing that if the matrix has three possible x values and four possible y values and so indexes exactly 3*4 = 24 values, I use a range of 1-D index of 0-to-23 inclsive to hold the corresponding x,y tuples generated, in the (oredered) dict dim_1 in line 52.
Sets all_xy, all_x, and all_y (lines54-56), accumulate the different indexing number-pairs and numbers seen in all/each dimension of the matrix indexing generated from this function i2xy. They are then tested to ensure they have the expected number and range of individual indeces
 in lines 57-68.

2-D to 1-D

Similarly xy_to_i_list has four possible ways that could match-up with a passing 1-D to 2-D fnction to do the reverse conversion from x,y coords to linear array index i.
all permutations of the range of x and y index values are used to generate sample 1-D indeces in dict dim_n (line 73), then the generated 1-D indices are checked (line 76+)

The last check, from line 86, checks that the i2xy function and xy2i functions are inverses of each other, generating and decoding the same indeces.

The output

## ORIGINAL 2-D ARRAY:
0,0 0,1 0,2 0,3
1,0 1,1 1,2 1,3
2,0 2,1 2,2 2,3

  # TRIAL MAPPINGS TO 1-D ARRAY
  FAIL! x count from `x, y = (lambda index_i: divmod(index_i, xcount))(index_i)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x * xcount + y)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x + y * ycount)(x, y)`
  FAIL! Mapping index_i to/from x, y using `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x * xcount + y)(x, y)`
  FAIL! Mapping index_i to/from x, y using `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x + y * ycount)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`
  FAIL! x count from `x, y = (lambda index_i: divmod(index_i, ycount)[::-1])(index_i)`

# SUMMARY
  PASS! `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`

Or to rewrite the lambdas as functions:

# These two:
def i2xy(i):
    return divmod(i, ycount)
def xy2i(x, y):
    return x * ycount + y
# Or these two:
def i2xy(i):
    return reversed(divmod(i, xcount))
def xy2i(x, y):
    return x + y * xcount

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

# -*- coding: utf-8 -*- """ Created on Sat Aug 24 21:31:03 2019 @author: Paddy3118 """ from collections import OrderedDict from itertools import product from pprint import pprint as pp #%% def irange(mini, maxi): "Integer range mini-to-maxi inclusive of _both_ endpoints" # Some think ranges should include _both_ endpoints, oh well. return range(mini, maxi+1) #%% xrange = irange(0, 2) yrange = irange(0, 3) xcount = len(xrange) # 3 ycount = len(yrange) # 4 print("\n## ORIGINAL 2-D ARRAY:") for x in xrange: print(' '.join(f"{x},{y}" for y in yrange)) #%% print("\n # TRIAL MAPPINGS TO 1-D ARRAY") print_on_fail, print_on_pass = False, False # Possible ways to get what n-dimensional index-tuple is stored at linear index i_to_xy_list = """ lambda index_i: divmod(index_i, xcount) lambda index_i: divmod(index_i, ycount) lambda index_i: divmod(index_i, xcount)[::-1] lambda index_i: divmod(index_i, ycount)[::-1] """.strip().split('\n') # Possible ways to generate a linear 1-D index from n-D tuple of indices xy_to_i_list = """ lambda x, y: x * xcount + y lambda x, y: x * ycount + y lambda x, y: x + y * ycount lambda x, y: x + y * xcount """.strip().split('\n') passes = [] for i_to_xy in i_to_xy_list: i2xy = eval(i_to_xy) # Representing a 1-D array as OrderedDict preserves insertion order dim_1 = OrderedDict((index_i, i2xy(index_i)) for index_i in irange(0, xcount*ycount - 1)) all_xy = set(dim_1.values()) all_x = set(x for x, y in dim_1.values()) all_y = set(y for x, y in dim_1.values()) if len(all_xy) != xcount * ycount: print(f" FAIL! x,y count from `x, y = ({i_to_xy})(index_i)`") if print_on_fail: pp(dim_1) continue if len(all_x) != xcount: print(f" FAIL! x count from `x, y = ({i_to_xy})(index_i)`") if print_on_fail: pp(dim_1) continue if len(all_y) != ycount: print(f" FAIL! y count from `x, y = ({i_to_xy})(index_i)`") if print_on_fail: pp(dim_1) continue # for xy_to_i in xy_to_i_list: xy2i = eval(xy_to_i) # Representing a N-D array dim_n = OrderedDict(((x, y), xy2i(x, y)) for x, y in product(xrange, yrange)) all_i = set(dim_n.values()) if min(all_i) != 0: print(f" FAIL! Min index_i not zero in " f"`index_i = ({xy_to_i})(x, y)`") if print_on_fail: pp(dim_n) continue if max(all_i) != xcount * ycount - 1: print(f" FAIL! Max index_i not {xcount * ycount - 1} in " f"`index_i = ({xy_to_i})(x, y)`") if print_on_fail: pp(dim_n) continue if not all(dim_1[dim_n[xy]] == xy for xy in dim_n): print(f" FAIL! Mapping index_i to/from x, y using " f"`x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`") if print_on_fail: pp(dim_1) if print_on_fail: pp(dim_n) continue passes.append((i_to_xy, xy_to_i)) print(f" PASS! `x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`") if print_on_pass: pp(dim_1) pp(dim_n) print('\n# SUMMARY') for i_to_xy, xy_to_i in passes: print(f" PASS! `x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`") #