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:

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

To remove an object from S at index i:

<br />I[i]=undefined<br />S.splice(i, 1)<br />

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

<br />if S[i] &gt; 0:<br /> S[i]=</span></s>(N+1)<br /> I[N]=X<br /> N=N+1<br />else:<br /> I[<s>S[i]</s> 1]=X<br />

The value of S[i] is

<br /> A[S[i] - 1] if S[i] &gt; 0<br /> I[<s>S[i]</s> 1] otherwise<br />

Bugs?

It may be possible for I to grow without bound.

The Code

This code assumes

<br />// A is the unmutable array<br />var A

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

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

// N is the index of the next element of S.<br />var N=0<br />

<br />function get(i)<br />{<br /> return (S[i] &gt; 0) ? A[S[i] - 1] : I[<s>S[i]</s> 1]<br />}<br />

<br />function insert(i, j)<br />{<br /> S.splice(i, 0, <s><span class="N+1">)<br /> I[N]=j<br /> N++<br />}<br />

<br />function remove(i)<br />{<br /> I[i]=undefined<br /> S.splice(i, 1)<br />}<br />

<br />function set(i,j)<br />{<br /> if (S[i] &gt; 0) {<br /> S[i]=</span></s>(N+1)<br /> I[N]=j<br /> N++<br /> }<br /> else<br /> {<br /> I[<s>S[i]</s> 1]=j<br /> }<br />}<br />