# Mutate-immutable-arrays-in-javascript

In my work with QML, I needed a way to mutate an immutable array. It's surprisingly easy to do this in Javascript. In this article, I give an outline of the technique followed by working Javascript code.

# The Outline

## Variables

Let S, A, and I be zero-based arrays. Let A be an immutable array Let I be empty Let N be an integer with initial value 0

Let S[i]=i+1 for all i in {0..||A||}

Let a positive value in S indicate an element of A:

```S[i] indicates A[S[i] - 1].
```

Let a negative value in S indicate an element of I:

```S[i] indicates I[-S[i]- 1]
```

S is the mutable "face" of A.

Let N indicate the next unused element of I.

## Pseudocode

To insert an object X into S at index i:

```S.splice(i, 0, -<span class="N+1">
I[N]=X
N=N+1```

To remove an object from S at index i:

```I[i]=undefined
S.splice(i, 1)```

To change an the object at S[i] to X:

```if S[i] > 0:
S[i]=</span>-(N+1)
I[N]=X
N=N+1
else:
I[-S[i]- 1]=X```

The value of S[i] is

``` A[S[i] - 1] if S[i] > 0
I[-S[i]- 1] otherwise```

## Bugs?

It may be possible for I to grow without bound.

# The Code

This code assumes

```// A is the unmutable array
var A

// S is the mutable face of A.
// You must initialize S as described in the outline
var S=new Array()

// I contains the values you insert
// or change in A and its mutable face.
var I=new Array()

// N is the index of the next element of S.
var N=0```
```function get(i)
{
return (S[i] > 0) ? A[S[i] - 1] : I[-S[i]- 1]
}```
```function insert(i, j)
{
S.splice(i, 0, -<span class="N+1">)
I[N]=j
N++
}```
```function remove(i)
{
I[i]=undefined
S.splice(i, 1)
}```
```function set(i,j)
{
if (S[i] > 0) {
S[i]=</span>-(N+1)
I[N]=j
N++
}
else
{
I[-S[i]- 1]=j
}
}```