# Mutate-immutable-arrays-in-javascript

# 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, -
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]=-(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, -)
I[N]=j
N++
```

```
}
```

```
function remove(i)
{
```

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

```
}
```

```
function set(i,j)
{
```

```
if (S[i] > 0) {
S[i]=-(N+1)
I[N]=j
N++
}
else
{
I[-S[i]- 1]=j
}
```

```
}
```