Mutate-immutable-arrays-in-javascript: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
In my work with | [[Category:HowTo]]<br />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. | ||
= | [toc align_right=“yes” depth=“3”] | ||
= | = The Outline = | ||
Let S, A, and I be zero-based arrays.<br /> Let A be an immutable array<br /> Let I be empty<br /> Let N be an integer with initial value 0 | == Variables == | ||
Let S, A, and I be zero-based arrays.<br />Let A be an immutable array<br />Let I be empty<br />Let N be an integer with initial value 0 | |||
Let S[i]=i+1 for all i in {0..||A||} | 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] | Let a positive value in S indicate an element of A:<br /> S[i] indicates A[S[i] - 1]. | ||
Let a negative value in S indicate an element of I: S[i] indicates I[ | Let a negative value in S indicate an element of I:<br /> S[i] indicates I[<s>S[i]</s> 1] | ||
S is the mutable | S is the mutable "face&quot; of A. | ||
Let N indicate the next unused element of I. | Let N indicate the next unused element of I. | ||
==Pseudocode== | == Pseudocode == | ||
To insert an object X into S at index i:<br /> To remove an object from S at index i:<br /> | To insert an object X into S at index i:<br /><code><br />S.splice(i, 0, <s><span class="N+1"><br />I[N]=X<br />N=N+1<br /></code><br />To remove an object from S at index i:<br /><code><br />I[i]=undefined<br />S.splice(i, 1)<br /></code> | ||
<br />To change an the object at S[i] to X:<br /><code><br />if S[i] > 0:<br /> S[i]=</span></s>(N+1)<br /> I[N]=X<br /> N=N+1<br />else:<br /> I[<s>S[i]</s> 1]=X<br /></code> | |||
The value of S[i] is<br /><code><br /> A[S[i] - 1] if S[i] > 0<br /> I[<s>S[i]</s> 1] otherwise<br /></code> | |||
== Bugs? == | |||
It may be possible for I to grow without bound. | |||
= The Code = | |||
This code assumes<br /><code><br />// A is the unmutable array<br />var A | |||
// S is the mutable face of A.<br />// You must initialize S as described in the outline<br />var S=new Array() | |||
= | // I contains the values you insert<br />// or change in A and its mutable face.<br />var I=new Array() | ||
// N is the index of the next element of S.<br />var N=0<br /></code><br /><code><br />function get(i)<br />{<br /> return (S[i] > 0) ? A[S[i] - 1] : I[<s>S[i]</s> 1]<br />}<br /></code><br /><code><br />function insert(i, j)<br />{<br /> S.splice(i, 0, <s><span class="N+1">)<br /> I[N]=j<br /> N++<br />}<br /></code><br /><code><br />function remove(i)<br />{<br /> I[i]=undefined<br /> S.splice(i, 1)<br />}<br /></code><br /><code><br />function set(i,j)<br />{<br /> if (S[i] > 0) {<br /> S[i]=</span></s>(N+1)<br /> I[N]=j<br /> N++<br /> }<br /> else<br /> {<br /> I[<s>S[i]</s> 1]=j<br /> }<br />}<br /></code> |
Revision as of 10:30, 24 February 2015
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.
[toc align_right=“yes” depth=“3”]
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:
<br />S.splice(i, 0, <s><span class="N+1"><br />I[N]=X<br />N=N+1<br />
To remove an object from S at index i:
<br />I[i]=undefined<br />S.splice(i, 1)<br />
To change an the object at S[i] to X:
<br />if S[i] > 0:<br /> S[i]=</span></s>(N+1)<br /> I[N]=X<br /> N=N+1<br />else:<br /> I[<s>S[i]</s> 1]=X<br />
The value of S[i] is
<br /> A[S[i] - 1] if S[i] > 0<br /> I[<s>S[i]</s> 1] otherwise<br />
Bugs?
It may be possible for I to grow without bound.
The Code
This code assumes
<br />// A is the unmutable array<br />var A
// S is the mutable face of A.<br />// You must initialize S as described in the outline<br />var S=new Array()
// I contains the values you insert<br />// or change in A and its mutable face.<br />var I=new Array()
// N is the index of the next element of S.<br />var N=0<br />
<br />function get(i)<br />{<br /> return (S[i] > 0) ? A[S[i] - 1] : I[<s>S[i]</s> 1]<br />}<br />
<br />function insert(i, j)<br />{<br /> S.splice(i, 0, <s><span class="N+1">)<br /> I[N]=j<br /> N++<br />}<br />
<br />function remove(i)<br />{<br /> I[i]=undefined<br /> S.splice(i, 1)<br />}<br />
<br />function set(i,j)<br />{<br /> if (S[i] > 0) {<br /> S[i]=</span></s>(N+1)<br /> I[N]=j<br /> N++<br /> }<br /> else<br /> {<br /> I[<s>S[i]</s> 1]=j<br /> }<br />}<br />