Mutate-immutable-arrays-in-javascript

From Qt Wiki
Revision as of 12:25, 17 April 2015 by AutoSpider (talk | contribs) (Remove non-functioning "toc" command)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
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, - 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
}

}