# Capacity Reservation

# Capacity Reservation

Capacity reservation allocates enough storage before elements are inserted. It separates allocated capacity from logical size so that append operations can use existing memory.

You use it when the approximate final size is known and repeated resizing would waste time.

## Problem

Given a dynamic array $A$, reserve enough capacity for at least $m$ elements while preserving existing elements.

The invariant is:

$$
size(A) \le capacity(A)
$$

After reservation:

$$
capacity(A) \ge m
$$

## Structure

A dynamic array stores:

* size: number of valid elements
* capacity: number of allocated slots
* data: backing storage

Reservation changes capacity but does not change size.

## Algorithm

Reserve capacity:

```id="capacity-reserve"
reserve(A, m):
    if m <= capacity:
        return

    B = allocate(m)

    for i from 0 to size - 1:
        B[i] = A[i]

    A = B
    capacity = m
```

Append after reservation:

```id="capacity-append"
append(A, x):
    if size == capacity:
        reserve(A, max(1, 2 * capacity))

    A[size] = x
    size += 1
```

## Example

Start with a dynamic array:

| field    |     value |
| -------- | --------: |
| size     |         3 |
| capacity |         4 |
| elements | [8, 3, 5] |

Call:

$$
reserve(A, 10)
$$

After reservation:

| field    |     value |
| -------- | --------: |
| size     |         3 |
| capacity |        10 |
| elements | [8, 3, 5] |

The logical array remains unchanged. Only the available storage increases.

## Correctness

If the requested capacity is already available, the structure satisfies the required condition and no work is needed. Otherwise, the algorithm allocates a larger block and copies each valid element from index $0$ through $size - 1$. Therefore, all existing elements remain in the same logical order.

Since the new capacity is $m$, the postcondition $capacity(A) \ge m$ holds.

## Complexity

| operation                       |   time |
| ------------------------------- | -----: |
| reserve when capacity is enough | $O(1)$ |
| reserve with allocation         | $O(n)$ |
| append after enough reservation | $O(1)$ |

Here $n$ is the current size.

Space usage during reallocation is:

$$
O(n + m)
$$

After the old storage is released, retained storage is:

$$
O(m)
$$

## When to Use

Capacity reservation is appropriate when:

* the final size is known approximately
* many append operations are expected
* reallocation cost should be avoided
* pointer or reference stability matters within a growth phase

It is less suitable when the size estimate is much larger than the actual data, since unused capacity wastes memory.

## Implementation

```python id="capacity-reservation-python"
class ReservedArray:
    def __init__(self):
        self.a = []
        self.size = 0

    def reserve(self, capacity):
        if capacity <= len(self.a):
            return

        b = [None] * capacity
        for i in range(self.size):
            b[i] = self.a[i]

        self.a = b

    def append(self, x):
        if self.size == len(self.a):
            new_capacity = max(1, 2 * len(self.a))
            self.reserve(new_capacity)

        self.a[self.size] = x
        self.size += 1

    def get(self, i):
        if i < 0 or i >= self.size:
            raise IndexError("index out of bounds")
        return self.a[i]
```

```go id="capacity-reservation-go"
type ReservedArray[T any] struct {
    data []T
    size int
}

func NewReservedArray[T any]() *ReservedArray[T] {
    return &ReservedArray[T]{}
}

func (r *ReservedArray[T]) Reserve(capacity int) {
    if capacity <= cap(r.data) {
        return
    }

    next := make([]T, r.size, capacity)
    copy(next, r.data[:r.size])
    r.data = next
}

func (r *ReservedArray[T]) Append(x T) {
    if r.size == cap(r.data) {
        next := max(1, 2*cap(r.data))
        r.Reserve(next)
    }

    if r.size == len(r.data) {
        r.data = r.data[:r.size+1]
    } else {
        r.data[r.size] = x
        r.size++
        return
    }

    r.data[r.size] = x
    r.size++
}

func (r *ReservedArray[T]) Get(i int) (T, bool) {
    var zero T
    if i < 0 || i >= r.size {
        return zero, false
    }
    return r.data[i], true
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```