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.

[toc align_right=“yes” depth=“3”]

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
 }
}