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.
Table of Content
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, -(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]=-(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, -(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]=-(N+1)
- I[N]=j
- N++
- }
- else
- {
- I[-S[i] - 1]=j
- }
- }
