Mutate-immutable-arrays-in-javascript

From Qt Wiki
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
This article may require cleanup to meet the Qt Wiki's quality standards. Reason: Auto-imported from ExpressionEngine.
Please improve this article if you can. Remove the {{cleanup}} tag and add this page to Updated pages list after it's clean.

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