Array Index Mapping

Array index mapping converts a logical index into the physical position where the value is stored. The logical order seen by the algorithm may differ from the storage order used in memory.

You use it when arrays are sliced, rotated, circular, strided, blocked, or stored in multidimensional layouts.

Problem

Given a logical index $i$ , compute the physical index $p$ used to access the backing array.

For a simple offset view:

p = start + i

where:

0 \le i < length

Structure

A mapped array stores:

backing array
start offset
logical length

For example:

B = [8, 3, 5, 1, 9]

A view with:

start = 1

and:

length = 3

represents:

[3, 5, 1]

Algorithm

Map a logical index to a physical index.

physical_index(M, i):
    if i < 0 or i >= M.length:
        error "index out of bounds"

    return M.start + i

Read through the mapping:

get(M, i):
    p = physical_index(M, i)
    return M.base[p]

Example

Let:

B = [8, 3, 5, 1, 9]

and define a mapped view:

field	value
start	1
length	3

Logical access:

M[2]

maps to:

B[1 + 2] = B[3]

logical index	physical index	value
0	1	3
1	2	5
2	3	1

Return:

1

Correctness

The bounds check ensures that the logical index lies inside the mapped view. Adding the start offset shifts the logical position into the backing array. Therefore, each logical index refers to exactly one physical index, and reading through the mapping returns the corresponding stored value.

Complexity

operation	time
physical index mapping	$O(1)$
get	$O(1)$
set	$O(1)$

Space usage:

O(1)

for the mapping metadata.

When to Use

Index mapping is appropriate when:

a view should avoid copying
a circular buffer wraps around storage
a matrix is stored in a flat array
logical order differs from physical order

It is less suitable when the mapping becomes complex enough to dominate access cost.

Implementation

class MappedArray:
    def __init__(self, base, start, length):
        if start < 0 or length < 0 or start + length > len(base):
            raise IndexError("invalid mapping")
        self.base = base
        self.start = start
        self.length = length

    def physical_index(self, i):
        if i < 0 or i >= self.length:
            raise IndexError("index out of bounds")
        return self.start + i

    def get(self, i):
        return self.base[self.physical_index(i)]

    def set(self, i, x):
        self.base[self.physical_index(i)] = x

type MappedArray[T any] struct {
    base   []T
    start  int
    length int
}

func NewMappedArray[T any](base []T, start, length int) (*MappedArray[T], bool) {
    if start < 0 || length < 0 || start+length > len(base) {
        return nil, false
    }

    return &MappedArray[T]{
        base:   base,
        start:  start,
        length: length,
    }, true
}

func (m *MappedArray[T]) physicalIndex(i int) (int, bool) {
    if i < 0 || i >= m.length {
        return 0, false
    }
    return m.start + i, true
}

func (m *MappedArray[T]) Get(i int) (T, bool) {
    var zero T
    p, ok := m.physicalIndex(i)
    if !ok {
        return zero, false
    }
    return m.base[p], true
}

func (m *MappedArray[T]) Set(i int, x T) bool {
    p, ok := m.physicalIndex(i)
    if !ok {
        return false
    }
    m.base[p] = x
    return true
}