git.iko.soy/elk
on dcba223 help sign in
elk/libraries/Native/Array.js
490 lines 15 kB history raw
1Elm.Native.Array = {};
2Elm.Native.Array.make = function(elm) {
3 elm.Native = elm.Native || {};
4 elm.Native.Array = elm.Native.Array || {};
5 if (elm.Native.Array.values) return elm.Native.Array.values;
6 if ('values' in Elm.Native.Array)
7 return elm.Native.Array.values = Elm.Native.Array.values;
9 var List = Elm.Native.List.make(elm);
11 // An RRB-Tree has two distinct data types. A leaf which contains data as
12 // an array in _1, and a height in _0, that is always 0. A node has in
13 // addition its size table in _2, while _1 contains an array of nodes or
14 // leaves.
16 // M is the maximal node size. 32 seems fast. E is the allowed increase
17 // of search steps when concatting to find an index. Lower values will
18 // decrease balancing, but will increase search steps.
19 var M = 32;
20 var E = 2;
22 // An empty array.
23 var empty = { ctor:"_Array", _0:0, _1:new Array() };
25 // Gets the value at index i recursively.
26 function get(i, a) {
27 if (a._0 == 0) {
28 if (i < a._1.length) {
29 return a._1[i];
30 } else {
31 throw new Error("Index "+ i +" on the array is out of range. Check the length first or you safeGet.");
32 }
33 }
35 var slot = getSlot(i, a);
36 var sub = slot > 0 ? a._2[slot-1] : 0;
37 return get(i - sub, a._1[slot]);
38 }
40 // Sets the value at the index i. Only the nodes leading to i will get
41 // copied and updated.
42 function set(i, item, a) {
43 if (length(a) <= i) {
44 return a;
45 }
46 var newA = nodeCopy(a);
47 newA._1 = a._1.slice();
49 if (a._0 == 0) {
50 newA._1[i] = item;
51 } else {
52 var slot = getSlot(i, a);
53 var sub = slot > 0 ? a._2[slot-1] : 0;
54 newA._1[slot] = set(i - sub, item, a._1[slot]);
55 }
56 return newA;
57 }
59 // Pushes an item via push_ to the bottom right of a tree.
60 function push(item, a) {
61 var pushed = push_(item, a);
62 if (pushed !== null) {
63 return pushed;
64 }
66 newTree = create(item, a._0);
67 return siblise(a, newTree);
68 }
70 // Recursively tries to push an item to the bottom-right most
71 // tree possible. If there is no space left for the item,
72 // null will be returned.
73 function push_(item, a) {
74 // Handle resursion stop at leaf level.
75 if (a._0 == 0) {
76 if (a._1.length < M) {
77 var newA = { ctor:"_Array", _0:0, _1:a._1.slice() };
78 newA._1.push(item);
79 return newA;
80 } else {
81 return null;
82 }
83 }
85 // Recursively push
86 var pushed = push_(item, botRight(a));
88 // There was space in the bottom right tree, so the slot will
89 // be updated.
90 if (pushed != null) {
91 var newA = nodeCopy(a);
92 newA._1[newA._1.length - 1] = pushed;
93 newA._2[newA._2.length - 1]++;
94 return newA
95 }
97 // When there was no space left, check if there is space left
98 // for a new slot with a tree which contains only the item
99 // at the bottom.
100 if (a._1.length < M) {
101 var newSlot = create(item, a._0 - 1);
102 var newA = nodeCopy(a);
103 newA._1.push(newSlot);
104 newA._2.push(newA._2[newA._2.length - 1] + length(newSlot));
105 return newA
106 } else {
107 return null;
108 }
109 }
111 // Converts an array into a list of elements.
112 function elements(a) {
113 return elements_(List.Nil, a);
114 }
116 function elements_(list, a) {
117 for (var i = a._1.length - 1; i >= 0; i--) {
118 list = a._0 == 0 ? List.Cons(a._1[i], list) : elements_(list, a._1[i]);
119 }
120 return list;
121 }
123 // Maps a function over an array.
124 function map(f, a) {
125 var newA = { ctor:"_Array", _0:a._0, _1:new Array(a._1) };
126 if (a._0 > 0) { newA._2 = a._2; }
127 for (var i = 0; i < a._1.length; i++) {
128 newA._1[i] = a._0 == 0 ? f(a._1[i]) : map(f, a._1[i]);
129 }
130 return newA;
131 }
133 function assocMap(f, a) {
134 var newA = { ctor:"_Array", _0:a._0, _1:new Array(a._1) };
135 if (a._0 > 0) { newA._2 = a._2; }
136 for (var i = 0; i < a._1.length; i++) {
137 newA._1[i] = a._0 == 0 ? A2(f, i, a._1[i]) : assocMap(f, a._1[i]);
138 }
139 return newA;
140 }
142 function foldl(f, b, a) {
143 for (var i = a._1.length - 1; i >= 0; i--) {
144 b = A2(f, a._0 == 0 ? a._1[i] : foldl(f, b, a._1[i]), b);
145 }
146 return b;
147 }
149 function foldr(f, b, a) {
150 for (var i = 0; i < a._1.length; i++) {
151 b = A2(f, a._0 == 0 ? a._1[i] : foldr(f, b, a._1[i]), b);
152 }
153 return b;
154 }
156 // Returns a sliced tree. The to is inclusive, but this may change,
157 // when I understand, why e.g. JS does not handle it this way. :-)
158 // If from or to is negative, they will select from the end on.
159 // TODO: currently, it slices the right, then the left. This can be
160 // optimized.
161 function slice(from, to, a) {
162 if (from < 0) { from += length(a); }
163 if (to < 0) { to += length(a); }
164 return sliceLeft(from, sliceRight(to, a));
165 }
167 function sliceRight(to, a) {
168 if (to == length(a)) {
169 return a;
170 }
172 // Handle leaf level.
173 if (a._0 == 0) {
174 var newA = { ctor:"_Array", _0:0 };
175 newA._1 = a._1.slice(0, to + 1);
176 return newA;
177 }
179 // Slice the right recursively.
180 var right = getSlot(to, a);
181 var sliced = sliceRight(to - (right > 0 ? a._2[right - 1] : 0), a._1[right]);
183 // Maybe the a node is not even needed, as sliced contains the whole slice.
184 if (right == 0) {
185 return sliced;
186 }
188 // Create new node.
189 var newA = { ctor:"_Array", _0:a._0
190 , _1:a._1.slice(0, right + 1)
191 , _2:a._2.slice(0, right + 1) };
192 newA._1[right] = sliced;
193 newA._2[right] = length(sliced) + (right > 0 ? newA._2[right - 1] : 0);
194 return newA;
195 }
197 function sliceLeft(from, a) {
198 if (from == 0) {
199 return a;
200 }
202 // Handle leaf level.
203 if (a._0 == 0) {
204 var newA = { ctor:"_Array", _0:0 };
205 newA._1 = a._1.slice(from, a._1.length + 1);
206 return newA;
207 }
209 // Slice the left recursively.
210 var left = getSlot(from, a);
211 var sliced = sliceLeft(from - (left > 0 ? a._2[left - 1] : 0), a._1[left]);
213 // Maybe the a node is not even needed, as sliced contains the whole slice.
214 if (left == a._1.length - 1) {
215 return sliced;
216 }
218 // Create new node.
219 var newA = { ctor:"_Array", _0:a._0
220 , _1:a._1.slice(left, a._1.length + 1)
221 , _2:new Array(a._1.length - left) };
222 newA._1[left] = sliced;
223 var len = 0;
224 for (var i = 0; i < newA._1.length; i++) {
225 len += length(newA._1[i]);
226 newA._2[i] = len;
227 }
229 return newA;
230 }
232 // Concats two trees.
233 // TODO: Add support for concatting trees of different sizes. Current
234 // behavior will just rise the lower tree and then concat them.
235 function concat(a, b) {
236 if (b._0 > a._0) { return concat(parentise(a, b._0), b); }
237 if (a._0 > b._0) { return concat(a, parentise(b, a._0)); }
238 if (a._0 == 0) { return concat(parentise(a, 1), parentise(b, 1)); }
240 var c = concat_(a, b);
241 if (c[1]._1.length > 0) {
242 return siblise(c[0], c[1]);
243 } else {
244 return c[0];
245 }
246 }
248 // Returns an array of two nodes. The second node _may_ be empty. This case
249 // needs to be handled by the function, that called concat_. May be only
250 // called for trees with an minimal height of 1.
251 function concat_(a, b) {
252 if (a._0 == 1) {
253 // Check if balancing is needed and return based on that.
254 var toRemove = calcToRemove(a, b);
255 if (toRemove <= E) {
256 return [a,b];
257 }
259 return shuffle(a, b, toRemove);
260 }
262 var concated = concat_(botRight(a), botLeft(b));
263 a = nodeCopy(a), b = nodeCopy(b);
265 // Adjust the bottom right side of the new tree.
266 a._1[a._1.length - 1] = concated[0];
267 a._2[a._2.length - 1] = length(concated[0])
268 a._2[a._2.length - 1] += a._2.length > 1 ? a._2[a._2.length - 2] : 0;
270 // Adjust the bottom left side of the new tree.
271 if (concated[1]._1.length > 0) {
272 b._1[0] = concated[1];
273 b._2[0] = length(concated[1]);
274 for (var i = 1, len = length(b._1[0]); i < b._2.length; i++) {
275 len += length(b._1[i]);
276 b._2[i] = len;
277 }
278 } else {
279 b._1.shift();
280 for (var i = 1; i < b._2.length; i++) {
281 b._2[i] = b._2[i] - b._2[0];
282 }
283 b._2.shift();
284 }
286 // Check if balancing is needed and return based on that.
287 var toRemove = calcToRemove(a, b);
288 if (toRemove <= E || b._1.length == 0) {
289 return [a,b];
290 }
292 return shuffle(a, b, toRemove);
293 }
295 // Returns the extra search steps for E. Refer to the paper.
296 function calcToRemove(a, b) {
297 var subLengths = 0;
298 for (var i = 0; i < a._1.length; i++) {
299 subLengths += a._1[i]._1.length;
300 }
301 for (var i = 0; i < b._1.length; i++) {
302 subLengths += b._1[i]._1.length;
303 }
305 var toRemove = a._1.length + b._1.length
306 return toRemove - (Math.floor((subLengths - 1) / M) + 1);
307 }
309 // get2 and set2 are helpers for accessing over two arrays.
310 function get2(a, b, index) {
311 return index < a.length ? a[index] : b[index - a.length];
312 }
314 function set2(a, b, index, value) {
315 if (index < a.length) {
316 a[index] = value;
317 } else {
318 b[index - a.length] = value;
319 }
320 }
322 // Creates a node or leaf with a given length at their arrays for perfomance.
323 // Is only used by shuffle.
324 function createNode(height, length) {
325 if (length < 0) { length = 0; }
326 var a = { ctor:"_Array", _0:height, _1:new Array(length) };
327 if (height > 0) {
328 a._2 = new Array(length);
329 }
330 return a;
331 }
333 function saveSlot(a, b, index, slot) {
334 set2(a._1, b._1, index, slot);
336 var l = (index == 0 || index == a._2.length) ?
337 0 : get2(a._2, a._2, index - 1);
338 set2(a._2, b._2, index, l + length(slot));
339 }
341 // Returns an array of two balanced nodes.
342 function shuffle(a, b, toRemove) {
343 var newA = createNode(a._0, Math.min(M, a._1.length + b._1.length - toRemove));
344 var newB = createNode(a._0, newA._1.length - (a._1.length + b._1.length - toRemove));
346 // Skip the slots with size M. More precise: copy the slot references
347 // to the new node
348 var read = 0;
349 while (get2(a._1, b._1, read)._1.length % M == 0) {
350 set2(newA._1, newB._1, read, get2(a._1, b._1, read));
351 set2(newA._2, newB._2, read, get2(a._2, b._2, read));
352 read++;
353 }
355 // Pulling items from left to right, caching in a slot before writing
356 // it into the new nodes.
357 var write = read;
358 var slot = new createNode(a._0 - 1, 0);
359 var from = 0;
361 // If the current slot is still containing data, then there will be at
362 // least one more write, so we do not break this loop yet.
363 while (read - write - (slot._1.length > 0 ? 1 : 0) < toRemove) {
364 // Find out the max possible items for copying.
365 var source = get2(a._1, b._1, read);
366 var to = Math.min(M - slot._1.length, source._1.length)
368 // Copy and adjust size table.
369 slot._1 = slot._1.concat(source._1.slice(from, to));
370 if (slot._0 > 0) {
371 var len = slot._2.length;
372 for (var i = len; i < len + to - from; i++) {
373 slot._2[i] = length(slot._1[i]);
374 slot._2[i] += (i > 0 ? slot._2[i - 1] : 0);
375 }
376 }
378 from += to;
380 // Only proceed to next slots[i] if the current one was
381 // fully copied.
382 if (source._1.length <= to) {
383 read++; from = 0;
384 }
386 // Only create a new slot if the current one is filled up.
387 if (slot._1.length == M) {
388 saveSlot(newA, newB, write, slot);
389 slot = createNode(a._0 - 1,0);
390 write++;
391 }
392 }
394 // Cleanup after the loop. Copy the last slot into the new nodes.
395 if (slot._1.length > 0) {
396 saveSlot(newA, newB, write, slot);
397 write++;
398 }
400 // Shift the untouched slots to the left
401 while (read < a._1.length + b._1.length ) {
402 saveSlot(newA, newB, write, get2(a._1, b._1, read));
403 read++; write++;
404 }
406 return [newA, newB];
407 }
409 // Helper functions
410 function botRight(a) { return a._1[a._1.length - 1]; }
411 function botLeft(a) { return a._1[0]; }
413 // Copies a node for updating. Note that you should not use
414 // this if only updating one of _1 and _2 for performance reasons.
415 function nodeCopy(a) {
416 var newA = { ctor:"_Array", _0:a._0
417 , _1:a._1.slice() };
418 if (a._0 > 0) { newA._2 = a._2.slice(); }
419 return newA;
420 }
422 // Returns how many items are in the tree.
423 function length(a) {
424 if (a._0 == 0) {
425 return a._1.length;
426 } else {
427 return a._2[a._2.length - 1];
428 }
429 }
431 // Calculates in which slot the item probably is, then
432 // find the exact slot in the size table ._2. Returns the index.
433 function getSlot(i, a) {
434 var slot = Math.floor(i / (Math.pow(M, a._0)));
435 while (a._2[slot] <= i) {
436 slot++
437 }
438 return slot;
439 }
441 // Recursively creates a tree with a given height containing
442 // only the given item.
443 function create(item, height) {
444 if (height == 0) {
445 return { ctor:"_Array", _0:0
446 , _1:[item] };
447 } else {
448 return { ctor:"_Array", _0:height
449 , _1:[create(item, height - 1)]
450 , _2:[1] };
451 }
452 }
454 // Recursively creates a tree that contains the given tree.
455 function parentise(tree, height) {
456 if (height == tree._0) {
457 return tree;
458 } else {
459 return { ctor:"_Array", _0:height
460 , _1:[parentise(tree, height - 1)]
461 , _2:[length(tree)] };
462 }
463 }
465 // Emphasizes blood brotherhood beneath two trees.
466 function siblise(a, b) {
467 return { ctor:"_Array", _0:a._0 + 1
468 , _1:[a, b]
469 , _2:[length(a), length(a) + length(b)] };
470 }
472 Elm.Native.Array.values = {
473 empty:empty,
474 elements:elements,
475 concat:F2(concat),
476 push:F2(push),
477 slice:F3(slice),
478 get:F2(get),
479 set:F3(set),
480 map:F2(map),
481 assocMap:F2(assocMap),
482 foldl:F3(foldl),
483 foldr:F3(foldr),
484 length:length
485 };
487 return elm.Native.Array.values = Elm.Native.Array.values;