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:

  1. S.splice(i, 0, -(N+1)
  2. I[N]=X
  3. N=N+1

To remove an object from S at index i:
  1. I[i]=undefined
  2. S.splice(i, 1)

To change an the object at S[i] to X:

  1. if S[i] > 0:
  2.   S[i]=-(N+1)
  3.   I[N]=X
  4.   N=N+1
  5. else:
  6.   I[-S[i] - 1]=X

The value of S[i] is

  1.   A[S[i] - 1] if S[i] > 0
  2.   I[-S[i] - 1] otherwise

Bugs?

It may be possible for I to grow without bound.

The Code

This code assumes

  1. // A is the unmutable array
  2. var A
  3.  
  4. // S is the mutable face of A.
  5. // You must initialize S as described in the outline
  6. var S=new Array()
  7.  
  8. // I contains the values you insert
  9. // or change in A and its mutable face.
  10. var I=new Array()
  11.  
  12. // N is the index of the next element of S.
  13. var N=0

  1. function get(i)
  2. {
  3.     return (S[i] > 0) ? A[S[i] - 1] : I[-S[i] - 1]
  4. }

  1. function insert(i, j)
  2. {
  3.     S.splice(i, 0, -(N+1))
  4.     I[N]=j
  5.     N++
  6. }

  1. function remove(i)
  2. {
  3.     I[i]=undefined
  4.     S.splice(i, 1)
  5. }

  1. function set(i,j)
  2. {
  3.     if (S[i] > 0) {
  4.         S[i]=-(N+1)
  5.         I[N]=j
  6.         N++
  7.     }
  8.     else
  9.     {
  10.         I[-S[i] - 1]=j
  11.     }
  12. }

Categories: