Mutate-immutable-arrays-in-javascript: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
AutoSpider (talk | contribs) (Remove non-functioning "toc" command) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
{{Cleanup | reason=Auto-imported from ExpressionEngine.}} | |||
[[Category:HowTo]] | |||
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. | |||
Let S, A, and I be zero-based arrays. | = 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 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: | ||
S[i] indicates A[S[i] - 1]. | |||
Let a negative value in S indicate an element of I: S[i] indicates I[-S[i] | Let a negative value in S indicate an element of I: | ||
S[i] indicates I[-S[i]- 1] | |||
S is the mutable | S is the mutable "face" 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:< | To insert an object X into S at index i: | ||
<code> | |||
S.splice(i, 0, -<span class="N+1"> | |||
I[N]=X | |||
N=N+1 | |||
</code> | |||
To remove an object from S at index i: | |||
<code> | |||
I[i]=undefined | |||
S.splice(i, 1) | |||
</code> | |||
To change an the object at S[i] to X:< | To change an the object at S[i] to X: | ||
<code> | |||
if S[i] > 0: | |||
S[i]=</span>-(N+1) | |||
I[N]=X | |||
N=N+1 | |||
else: | |||
I[-S[i]- 1]=X | |||
</code> | |||
The value of S[i] is< | The value of S[i] is | ||
<code> | |||
A[S[i] - 1] if S[i] > 0 | |||
I[-S[i]- 1] otherwise | |||
</code> | |||
==Bugs?== | == Bugs? == | ||
It may be possible for I to grow without bound. | It may be possible for I to grow without bound. | ||
=The Code= | = The Code = | ||
This code assumes | |||
<code> | |||
// 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 | |||
</code> | |||
<code> | |||
function get(i) | |||
{ | |||
return (S[i] > 0) ? A[S[i] - 1] : I[-S[i]- 1] | |||
} | |||
</code> | |||
<code> | |||
function insert(i, j) | |||
{ | |||
S.splice(i, 0, -<span class="N+1">) | |||
I[N]=j | |||
N++ | |||
} | |||
</code> | |||
<code> | |||
function remove(i) | |||
{ | |||
I[i]=undefined | |||
S.splice(i, 1) | |||
} | |||
</code> | |||
<code> | |||
function set(i,j) | |||
{ | |||
if (S[i] > 0) { | |||
S[i]=</span>-(N+1) | |||
I[N]=j | |||
N++ | |||
} | |||
else | |||
{ | |||
I[-S[i]- 1]=j | |||
} | |||
} | |||
</code> |
Latest revision as of 12:25, 17 April 2015
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
}
}