Mutate-immutable-arrays-in-javascript
From Qt Wiki
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 } }