git.iko.soy/elk
on a4ea68e help sign in
elk/libraries/Native/Array.js
657 lines 21 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 // A RRB-Tree has two distinct data types.
12 // Leaf -> "height" is always 0
13 // "table" is an array of elements
14 // Node -> "height" is always greater than 0
15 // "table" is an array of child nodes
16 // "lengths" is an array of accumulated lengths of the child nodes
18 // M is the maximal table size. 32 seems fast. E is the allowed increase
19 // of search steps when concatting to find an index. Lower values will
20 // decrease balancing, but will increase search steps.
21 var M = 32;
22 var E = 2;
24 // An empty array.
25 var empty = { ctor:"_Array", height:0, table:new Array() };
27 function get(i, array) {
28 if (i < 0 || i >= length(array)) {
29 throw new Error("Index " + i + " is out of range. Check the length of " +
30 "your array first or use getMaybe or getWithDefault.");
31 }
32 return unsafeGet(i, array);
33 }
35 function unsafeGet(i, array) {
36 for (var x = array.height; x > 0; x--) {
37 var slot = i >> (x * 5);
38 if (slot > 0) {
39 while (array.lengths[slot - 1] > i) { slot--; }
40 i -= array.lengths[slot - 1];
41 }
42 array = array.table[slot];
43 }
44 return array.table[i];
45 }
47 // Sets the value at the index i. Only the nodes leading to i will get
48 // copied and updated.
49 function set(i, item, array) {
50 if (i < 0 || length(array) <= i) {
51 return array;
52 }
53 return unsafeSet(i, item, array);
54 }
56 function unsafeSet(i, item, array) {
57 array = nodeCopy(array);
59 if (array.height == 0) {
60 array.table[i] = item;
61 } else {
62 var slot = getSlot(i, array);
63 if (slot > 0) {
64 i -= array.lengths[slot - 1];
65 }
66 array.table[slot] = unsafeSet(i, item, array.table[slot]);
67 }
68 return array;
69 }
71 function initialize(len, f) {
72 if (len == 0) { return empty; }
73 var h = Math.floor(Math.log(len)/Math.log(M));
74 return initialize_(f, h, 0, len);
75 }
77 function initialize_(f, h, from, to) {
78 if (h == 0) {
79 var table = new Array((to - from) % (M + 1));
80 for (var i = 0; i < table.length; i++) {
81 table[i] = f(from + i);
82 }
83 return { ctor:"_Array", height:0, table:table };
84 }
86 var step = Math.pow(M, h);
87 var table = new Array(Math.ceil((to - from) / step));
88 var lengths = new Array(table.length);
89 for (var i = 0; i < table.length; i++) {
90 table[i] = initialize_( f, h - 1, from + (i * step)
91 , Math.min(from + ((i + 1) * step), to));
92 lengths[i] = length(table[i]) + (i > 0 ? lengths[i-1] : 0);
93 }
94 return { ctor:"_Array", height:h, table:table, lengths:lengths };
95 }
97 function fromList(list) {
98 if (list == List.Nil) { return empty; }
100 // Allocate M sized blocks (table) and write list elements to it.
101 var table = new Array(M);
102 var nodes = new Array();
103 var i = 0;
105 while (list.ctor !== '[]') {
106 table[i] = list._0;
107 list = list._1;
108 i++;
110 // table is full, so we can push a leaf containing it into the
111 // next node.
112 if (i == M) {
113 fromListPush({ ctor:"_Array", height:0, table:table }
114 , nodes);
115 table = new Array(M);
116 i = 0;
117 }
118 }
120 // Maybe there is something left on the table.
121 if (i > 0) {
122 fromListPush({ ctor:"_Array", height:0, table:table.splice(0,i) }
123 , nodes);
124 }
126 // Go through all of the nodes and eventually push them into higher nodes.
127 for (var h = 0; h < nodes.length - 1; h++) {
128 if (nodes[h].table.length > 0) {
129 fromListPush(nodes[h], nodes);
130 }
131 }
133 var head = nodes[nodes.length - 1];
134 if (head.height > 0 && head.table.length == 1) {
135 return head.table[0];
136 } else {
137 return head;
138 }
139 }
141 // Push a node into a higher node as a child.
142 function fromListPush(toPush, nodes) {
143 var h = toPush.height;
145 // Maybe the node on this height does not exist.
146 if (nodes.length == h) {
147 nodes.push({ ctor:"_Array", height:h + 1
148 , table:new Array()
149 , lengths:new Array() });
150 }
152 nodes[h].table.push(toPush);
153 var len = length(toPush);
154 if (nodes[h].lengths.length > 0) {
155 len += nodes[h].lengths[nodes[h].lengths.length - 1];
156 }
157 nodes[h].lengths.push(len);
159 if (nodes[h].table.length == M) {
160 fromListPush(nodes[h], nodes);
161 nodes[h] = { ctor:"_Array", height:h + 1
162 , table:new Array()
163 , lengths:new Array() };
164 }
165 }
167 // Pushes an item via push_ to the bottom right of a tree.
168 function push(item, a) {
169 var pushed = push_(item, a);
170 if (pushed !== null) {
171 return pushed;
172 }
174 var newTree = create(item, a.height);
175 return siblise(a, newTree);
176 }
178 // Recursively tries to push an item to the bottom-right most
179 // tree possible. If there is no space left for the item,
180 // null will be returned.
181 function push_(item, a) {
182 // Handle resursion stop at leaf level.
183 if (a.height == 0) {
184 if (a.table.length < M) {
185 var newA = { ctor:"_Array", height:0, table:a.table.slice() };
186 newA.table.push(item);
187 return newA;
188 } else {
189 return null;
190 }
191 }
193 // Recursively push
194 var pushed = push_(item, botRight(a));
196 // There was space in the bottom right tree, so the slot will
197 // be updated.
198 if (pushed != null) {
199 var newA = nodeCopy(a);
200 newA.table[newA.table.length - 1] = pushed;
201 newA.lengths[newA.lengths.length - 1]++;
202 return newA
203 }
205 // When there was no space left, check if there is space left
206 // for a new slot with a tree which contains only the item
207 // at the bottom.
208 if (a.table.length < M) {
209 var newSlot = create(item, a.height - 1);
210 var newA = nodeCopy(a);
211 newA.table.push(newSlot);
212 newA.lengths.push(newA.lengths[newA.lengths.length - 1] + length(newSlot));
213 return newA
214 } else {
215 return null;
216 }
217 }
219 // Converts an array into a list of elements.
220 function toList(a) {
221 return toList_(List.Nil, a);
222 }
224 function toList_(list, a) {
225 for (var i = a.table.length - 1; i >= 0; i--) {
226 list = a.height == 0 ? List.Cons(a.table[i], list) : toList_(list, a.table[i]);
227 }
228 return list;
229 }
231 // Maps a function over the elements of an array.
232 function map(f, a) {
233 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
234 if (a.height > 0) { newA.lengths = a.lengths; }
235 for (var i = 0; i < a.table.length; i++) {
236 newA.table[i] = a.height == 0 ? f(a.table[i]) : map(f, a.table[i]);
237 }
238 return newA;
239 }
241 // Maps a function over the elements with their index as first argument.
242 function indexedMap(f, a) {
243 return indexedMap_(f, a, 0);
244 }
246 function indexedMap_(f, a, from) {
247 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
248 if (a.height > 0) { newA.lengths = a.lengths; }
249 for (var i = 0; i < a.table.length; i++) {
250 newA.table[i] = a.height == 0 ? A2(f, from + i, a.table[i])
251 : indexedMap_( f, a.table[i]
252 , i == 0 ? 0 : a.lengths[i - 1]);
253 }
254 return newA;
255 }
257 function foldl(f, b, a) {
258 if (a.height == 0) {
259 for (var i = 0; i < a.table.length; i++) {
260 b = A2(f, a.table[i], b);
261 }
262 } else {
263 for (var i = 0; i < a.table.length; i++) {
264 b = foldl(f, b, a.table[i]);
265 }
266 }
267 return b;
268 }
270 function foldr(f, b, a) {
271 if (a.height == 0) {
272 for (var i = a.table.length; i--; ) {
273 b = A2(f, a.table[i], b);
274 }
275 } else {
276 for (var i = a.table.length; i--; ) {
277 b = foldl(f, b, a.table[i]);
278 }
279 }
280 return b;
281 }
283 // TODO: currently, it slices the right, then the left. This can be
284 // optimized.
285 function slice(from, to, a) {
286 if (from < 0) { from += length(a); }
287 if (to < 0) { to += length(a); }
288 return sliceLeft(from, sliceRight(to, a));
289 }
291 function sliceRight(to, a) {
292 if (to == length(a)) {
293 return a;
294 }
296 // Handle leaf level.
297 if (a.height == 0) {
298 var newA = { ctor:"_Array", height:0 };
299 newA.table = a.table.slice(0, to);
300 return newA;
301 }
303 // Slice the right recursively.
304 var right = getSlot(to, a);
305 var sliced = sliceRight(to - (right > 0 ? a.lengths[right - 1] : 0), a.table[right]);
307 // Maybe the a node is not even needed, as sliced contains the whole slice.
308 if (right == 0) {
309 return sliced;
310 }
312 // Create new node.
313 var newA = { ctor:"_Array", height:a.height
314 , table:a.table.slice(0, right + 1)
315 , lengths:a.lengths.slice(0, right + 1) };
316 newA.table[right] = sliced;
317 newA.lengths[right] = length(sliced) + (right > 0 ? newA.lengths[right - 1] : 0);
318 return newA;
319 }
321 function sliceLeft(from, a) {
322 if (from == 0) {
323 return a;
324 }
326 // Handle leaf level.
327 if (a.height == 0) {
328 var newA = { ctor:"_Array", height:0 };
329 newA.table = a.table.slice(from, a.table.length + 1);
330 return newA;
331 }
333 // Slice the left recursively.
334 var left = getSlot(from, a);
335 var sliced = sliceLeft(from - (left > 0 ? a.lengths[left - 1] : 0), a.table[left]);
337 // Maybe the a node is not even needed, as sliced contains the whole slice.
338 if (left == a.table.length - 1) {
339 return sliced;
340 }
342 // Create new node.
343 var newA = { ctor:"_Array", height:a.height
344 , table:a.table.slice(left, a.table.length + 1)
345 , lengths:new Array(a.table.length - left) };
346 newA.table[left] = sliced;
347 var len = 0;
348 for (var i = 0; i < newA.table.length; i++) {
349 len += length(newA.table[i]);
350 newA.lengths[i] = len;
351 }
353 return newA;
354 }
356 // Appends two trees.
357 // TODO: Add support for appending trees of different sizes. Current
358 // behavior will just rise the lower tree and then append them.
359 function append(a,b) {
360 if (a.table.length == 0) return b;
361 if (b.table.length == 0) return a;
362 if (b.height > a.height) return append(parentise(a, b.height), b);
363 if (a.height > b.height) return append(a, parentise(b, a.height));
364 if (a.height == 0) return append(parentise(a, 1), parentise(b, 1));
366 var c = append_(a, b);
367 if (c[1].table.length > 0) {
368 return siblise(c[0], c[1]);
369 } else {
370 return c[0];
371 }
372 }
374 // Returns an array of two nodes. The second node _may_ be empty. This case
375 // needs to be handled by the function, that called append_. May be only
376 // called for trees with an minimal height of 1.
377 function append_(a, b) {
378 if (a.height == 1) {
379 // Check if balancing is needed and return based on that.
380 var toRemove = calcToRemove(a, b);
381 if (toRemove <= E) {
382 return [a,b];
383 }
385 return shuffle(a, b, toRemove);
386 }
388 var appended = append_(botRight(a), botLeft(b));
389 a = nodeCopy(a), b = nodeCopy(b);
391 // Adjust the bottom right side of the new tree.
392 a.table[a.table.length - 1] = appended[0];
393 a.lengths[a.lengths.length - 1] = length(appended[0])
394 a.lengths[a.lengths.length - 1] += a.lengths.length > 1 ? a.lengths[a.lengths.length - 2] : 0;
396 // Adjust the bottom left side of the new tree.
397 if (appended[1].table.length > 0) {
398 b.table[0] = appended[1];
399 b.lengths[0] = length(appended[1]);
400 for (var i = 1, len = length(b.table[0]); i < b.lengths.length; i++) {
401 len += length(b.table[i]);
402 b.lengths[i] = len;
403 }
404 } else {
405 b.table.shift();
406 for (var i = 1; i < b.lengths.length; i++) {
407 b.lengths[i] = b.lengths[i] - b.lengths[0];
408 }
409 b.lengths.shift();
410 }
412 // Check if balancing is needed and return based on that.
413 var toRemove = calcToRemove(a, b);
414 if (toRemove <= E || b.table.length == 0) {
415 return [a,b];
416 }
418 return shuffle(a, b, toRemove);
419 }
421 // Returns the extra search steps for E. Refer to the paper.
422 function calcToRemove(a, b) {
423 var subLengths = 0;
424 for (var i = 0; i < a.table.length; i++) {
425 subLengths += a.table[i].table.length;
426 }
427 for (var i = 0; i < b.table.length; i++) {
428 subLengths += b.table[i].table.length;
429 }
431 var toRemove = a.table.length + b.table.length
432 return toRemove - (Math.floor((subLengths - 1) / M) + 1);
433 }
435 // get2, set2 and saveSlot are helpers for accessing elements over two arrays.
436 function get2(a, b, index) {
437 return index < a.length ? a[index] : b[index - a.length];
438 }
440 function set2(a, b, index, value) {
441 if (index < a.length) {
442 a[index] = value;
443 } else {
444 b[index - a.length] = value;
445 }
446 }
448 function saveSlot(a, b, index, slot) {
449 set2(a.table, b.table, index, slot);
451 var l = (index == 0 || index == a.lengths.length) ?
452 0 : get2(a.lengths, a.lengths, index - 1);
453 set2(a.lengths, b.lengths, index, l + length(slot));
454 }
456 // Creates a node or leaf with a given length at their arrays for perfomance.
457 // Is only used by shuffle.
458 function createNode(h, length) {
459 if (length < 0) { length = 0; }
460 var a = { ctor:"_Array", height:h, table:new Array(length) };
461 if (h > 0) {
462 a.lengths = new Array(length);
463 }
464 return a;
465 }
467 // Returns an array of two balanced nodes.
468 function shuffle(a, b, toRemove) {
469 var newA = createNode(a.height, Math.min(M, a.table.length + b.table.length - toRemove));
470 var newB = createNode(a.height, newA.table.length - (a.table.length + b.table.length - toRemove));
472 // Skip the slots with size M. More precise: copy the slot references
473 // to the new node
474 var read = 0;
475 while (get2(a.table, b.table, read).table.length % M == 0) {
476 set2(newA.table, newB.table, read, get2(a.table, b.table, read));
477 set2(newA.lengths, newB.lengths, read, get2(a.lengths, b.lengths, read));
478 read++;
479 }
481 // Pulling items from left to right, caching in a slot before writing
482 // it into the new nodes.
483 var write = read;
484 var slot = new createNode(a.height - 1, 0);
485 var from = 0;
487 // If the current slot is still containing data, then there will be at
488 // least one more write, so we do not break this loop yet.
489 while (read - write - (slot.table.length > 0 ? 1 : 0) < toRemove) {
490 // Find out the max possible items for copying.
491 var source = get2(a.table, b.table, read);
492 var to = Math.min(M - slot.table.length, source.table.length)
494 // Copy and adjust size table.
495 slot.table = slot.table.concat(source.table.slice(from, to));
496 if (slot.height > 0) {
497 var len = slot.lengths.length;
498 for (var i = len; i < len + to - from; i++) {
499 slot.lengths[i] = length(slot.table[i]);
500 slot.lengths[i] += (i > 0 ? slot.lengths[i - 1] : 0);
501 }
502 }
504 from += to;
506 // Only proceed to next slots[i] if the current one was
507 // fully copied.
508 if (source.table.length <= to) {
509 read++; from = 0;
510 }
512 // Only create a new slot if the current one is filled up.
513 if (slot.table.length == M) {
514 saveSlot(newA, newB, write, slot);
515 slot = createNode(a.height - 1,0);
516 write++;
517 }
518 }
520 // Cleanup after the loop. Copy the last slot into the new nodes.
521 if (slot.table.length > 0) {
522 saveSlot(newA, newB, write, slot);
523 write++;
524 }
526 // Shift the untouched slots to the left
527 while (read < a.table.length + b.table.length ) {
528 saveSlot(newA, newB, write, get2(a.table, b.table, read));
529 read++; write++;
530 }
532 return [newA, newB];
533 }
535 // Navigation functions
536 function botRight(a) { return a.table[a.table.length - 1]; }
537 function botLeft(a) { return a.table[0]; }
539 // Copies a node for updating. Note that you should not use this if
540 // only updating only one of "table" or "lengths" for performance reasons.
541 function nodeCopy(a) {
542 var newA = { ctor:"_Array", height:a.height
543 , table:a.table.slice() };
544 if (a.height > 0) { newA.lengths = a.lengths.slice(); }
545 return newA;
546 }
548 // Returns how many items are in the tree.
549 function length(array) {
550 if (array.height == 0) {
551 return array.table.length;
552 } else {
553 return array.lengths[array.lengths.length - 1];
554 }
555 }
557 // Calculates in which slot of "table" the item probably is, then
558 // find the exact slot via forward searching in "lengths". Returns the index.
559 function getSlot(i, a) {
560 var slot = i >> (5 * a.height);
561 while (a.lengths[slot - 1] > i) { slot--; }
562 return slot;
563 }
565 // Recursively creates a tree with a given height containing
566 // only the given item.
567 function create(item, h) {
568 if (h == 0) {
569 return { ctor:"_Array", height:0
570 , table:[item] };
571 } else {
572 return { ctor:"_Array", height:h
573 , table:[create(item, h - 1)]
574 , lengths:[1] };
575 }
576 }
578 // Recursively creates a tree that contains the given tree.
579 function parentise(tree, h) {
580 if (h == tree.height) {
581 return tree;
582 } else {
583 return { ctor:"_Array", height:h
584 , table:[parentise(tree, h - 1)]
585 , lengths:[length(tree)] };
586 }
587 }
589 // Emphasizes blood brotherhood beneath two trees.
590 function siblise(a, b) {
591 return { ctor:"_Array", height:a.height + 1
592 , table:[a, b]
593 , lengths:[length(a), length(a) + length(b)] };
594 }
596 function toJSArray(a) {
597 var jsArray = new Array(length(a));
598 toJSArray_(jsArray, 0, a);
599 return jsArray;
600 }
602 function toJSArray_(jsArray, i, a) {
603 for (var t = 0; t < a.table.length; t++) {
604 if (a.height == 0) {
605 jsArray[i + t] = a.table[t];
606 } else {
607 var inc = t == 0 ? 0 : a.lengths[t - 1];
608 toJSArray_(jsArray, i + inc, a.table[t]);
609 }
610 }
611 }
613 function fromJSArray(jsArray) {
614 if (jsArray.length == 0) { return empty; }
615 var h = Math.floor(Math.log(jsArray.length) / Math.log(M));
616 return fromJSArray_(jsArray, h, 0, jsArray.length);
617 }
619 function fromJSArray_(jsArray, h, from, to) {
620 if (h == 0) {
621 return { ctor:"_Array", height:0
622 , table:jsArray.slice(from, to) };
623 }
625 var step = Math.pow(M, h);
626 var table = new Array(Math.ceil((to - from) / step));
627 var lengths = new Array(table.length);
628 for (var i = 0; i < table.length; i++) {
629 table[i] = fromJSArray_( jsArray, h - 1, from + (i * step)
630 , Math.min(from + ((i + 1) * step), to));
631 lengths[i] = length(table[i]) + (i > 0 ? lengths[i-1] : 0);
632 }
633 return { ctor:"_Array", height:h, table:table, lengths:lengths };
634 }
636 Elm.Native.Array.values = {
637 empty:empty,
638 fromList:fromList,
639 toList:toList,
640 initialize:F2(initialize),
641 append:F2(append),
642 push:F2(push),
643 slice:F3(slice),
644 get:F2(get),
645 set:F3(set),
646 map:F2(map),
647 indexedMap:F2(indexedMap),
648 foldl:F3(foldl),
649 foldr:F3(foldr),
650 length:length,
652 toJSArray:toJSArray,
653 fromJSArray:fromJSArray
654 };
656 return elm.Native.Array.values = Elm.Native.Array.values;