Let $f(i,j)$ be a function that takes $i,j$ ie column and row number and gives the index $k$ where $A(i,j)^{th}$ element is stored in the compact one-dimension array representation.
In the compact representation, first we’ll store elements of $row \space 1$ followed by $row \space n$ and at last remaining elements $column \space 1$.
Following this, we can define –
$\begin{align*} f(i,j) &= j, \text{ if } i = 1 \\ &= (n+j), \text{ if } i = n \\ &= (2n+(i-1)), \text{ if } i \neq 1,i \neq n \end{align*}$
Now, we’ve to merge these $3$ piecewise functions.
Now, what we want is few functions that can map to $0,1$ depending in the value of $i$.
- We want a function that can output $1$ when $i = 1$ and $0$ when $i \neq 1$.
- We want a function that can output $1$ when $i = n$ and $0$ when $i \neq n$.
- We want a function that can output $1$ when $i \neq 1, i \neq n$ and $0$ when $i = 1, i = n$.
We can do this using ceil and floor functions.
Consider this function,
$\begin{align*} \Bigl \lceil \frac{i-1}{i} \Bigr \rceil &=0, \text{ if } i = 1 \\ &= 1, \text{ if } i > 1 \end{align*}$
This is exactly opposite to what we need, so we can take its negation and add $1$ to make it behave as we want.
$\begin{align*} \left( 1 – \Bigl \lceil \frac{i-1}{i} \Bigr \rceil \right) &=1, \text{ if } i = 1 \\ &= 0, \text{ if } i > 1 \end{align*}$
Now, this is exactly what we need.
Consider this function,
$\begin{align*} \Bigl \lfloor \frac{i}{n} \Bigr \rfloor &=0, \text{ if } i < n \\ &= 1, \text{ if } i = n \end{align*}$
This is exactly what we need.
Using above equations, we can also fulfill our $3^{rd}$ function requirement.
$\begin{align*} \left( \Bigl \lceil \frac{i-1}{i} \Bigr \rceil \right) * \left( 1 – \Bigl \lfloor \frac{i}{n} \Bigr \rfloor \right) &=0, \text{ if } i = 1, i = n \\ &= 1, \text{ if } i \neq 1, i \neq n \end{align*}$
Now,
$f(i,j) = \left( 1 – \Bigl \lceil \frac{i-1}{i} \Bigr \rceil \right) * j + \left( \Bigl \lfloor \frac{i}{n} \Bigr \rfloor \right) * (n+j) + \left( \Bigl \lceil \frac{i-1}{i} \Bigr \rceil \right) * \left( 1 – \Bigl \lfloor \frac{i}{n} \Bigr \rfloor \right) * (2*n + (i-1))$
Now, we have $f(i,j)$ that gives index of $A(i,j)$. Assume that our $1-D$ array starts from base address $b$ and each element occupies $s$ bytes.
Location of $A(i,j) = b + \left( f(i,j) - 1 \right)* s$.