Mutate-immutable-arrays-in-javascript
Jump to navigation
Jump to search
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
}
}