git.iko.soy/elk
on c3c52cd help sign in
elk/libraries/Native/Array.js
709 lines 22 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 while (array.lengths[slot] <= i) {
39 slot++;
40 }
41 if (slot > 0) {
42 i -= array.lengths[slot - 1];
43 }
44 array = array.table[slot];
45 }
46 return array.table[i];
47 }
49 // Sets the value at the index i. Only the nodes leading to i will get
50 // copied and updated.
51 function set(i, item, array) {
52 if (i < 0 || length(array) <= i) {
53 return array;
54 }
55 return unsafeSet(i, item, array);
56 }
58 function unsafeSet(i, item, array) {
59 array = nodeCopy(array);
61 if (array.height == 0) {
62 array.table[i] = item;
63 } else {
64 var slot = getSlot(i, array);
65 if (slot > 0) {
66 i -= array.lengths[slot - 1];
67 }
68 array.table[slot] = unsafeSet(i, item, array.table[slot]);
69 }
70 return array;
71 }
73 function initialize(len, f) {
74 if (len == 0) { return empty; }
75 var h = Math.floor(Math.log(len)/Math.log(M));
76 return initialize_(f, h, 0, len);
77 }
79 function initialize_(f, h, from, to) {
80 if (h == 0) {
81 var table = new Array((to - from) % (M + 1));
82 for (var i = 0; i < table.length; i++) {
83 table[i] = f(from + i);
84 }
85 return { ctor:"_Array", height:0, table:table };
86 }
88 var step = Math.pow(M, h);
89 var table = new Array(Math.ceil((to - from) / step));
90 var lengths = new Array(table.length);
91 for (var i = 0; i < table.length; i++) {
92 table[i] = initialize_( f, h - 1, from + (i * step)
93 , Math.min(from + ((i + 1) * step), to));
94 lengths[i] = length(table[i]) + (i > 0 ? lengths[i-1] : 0);
95 }
96 return { ctor:"_Array", height:h, table:table, lengths:lengths };
97 }
99 function fromList(list) {
100 if (list == List.Nil) { return empty; }
102 // Allocate M sized blocks (table) and write list elements to it.
103 var table = new Array(M);
104 var nodes = new Array();
105 var i = 0;
107 while (list.ctor !== '[]') {
108 table[i] = list._0;
109 list = list._1;
110 i++;
112 // table is full, so we can push a leaf containing it into the
113 // next node.
114 if (i == M) {
115 fromListPush({ ctor:"_Array", height:0, table:table }
116 , nodes);
117 table = new Array(M);
118 i = 0;
119 }
120 }
122 // Maybe there is something left on the table.
123 if (i > 0) {
124 fromListPush({ ctor:"_Array", height:0, table:table.splice(0,i) }
125 , nodes);
126 }
128 // Go through all of the nodes and eventually push them into higher nodes.
129 for (var h = 0; h < nodes.length - 1; h++) {
130 if (nodes[h].table.length > 0) {
131 fromListPush(nodes[h], nodes);
132 }
133 }
135 var head = nodes[nodes.length - 1];
136 if (head.height > 0 && head.table.length == 1) {
137 return head.table[0];
138 } else {
139 return head;
140 }
141 }
143 // Push a node into a higher node as a child.
144 function fromListPush(toPush, nodes) {
145 var h = toPush.height;
147 // Maybe the node on this height does not exist.
148 if (nodes.length == h) {
149 nodes.push({ ctor:"_Array", height:h + 1
150 , table:new Array()
151 , lengths:new Array() });
152 }
154 nodes[h].table.push(toPush);
155 var len = length(toPush);
156 if (nodes[h].lengths.length > 0) {
157 len += nodes[h].lengths[nodes[h].lengths.length - 1];
158 }
159 nodes[h].lengths.push(len);
161 if (nodes[h].table.length == M) {
162 fromListPush(nodes[h], nodes);
163 nodes[h] = { ctor:"_Array", height:h + 1
164 , table:new Array()
165 , lengths:new Array() };
166 }
167 }
169 // Pushes an item via push_ to the bottom right of a tree.
170 function push(item, a) {
171 var pushed = push_(item, a);
172 if (pushed !== null) {
173 return pushed;
174 }
176 var newTree = create(item, a.height);
177 return siblise(a, newTree);
178 }
180 // Recursively tries to push an item to the bottom-right most
181 // tree possible. If there is no space left for the item,
182 // null will be returned.
183 function push_(item, a) {
184 // Handle resursion stop at leaf level.
185 if (a.height == 0) {
186 if (a.table.length < M) {
187 var newA = { ctor:"_Array", height:0, table:a.table.slice() };
188 newA.table.push(item);
189 return newA;
190 } else {
191 return null;
192 }
193 }
195 // Recursively push
196 var pushed = push_(item, botRight(a));
198 // There was space in the bottom right tree, so the slot will
199 // be updated.
200 if (pushed != null) {
201 var newA = nodeCopy(a);
202 newA.table[newA.table.length - 1] = pushed;
203 newA.lengths[newA.lengths.length - 1]++;
204 return newA
205 }
207 // When there was no space left, check if there is space left
208 // for a new slot with a tree which contains only the item
209 // at the bottom.
210 if (a.table.length < M) {
211 var newSlot = create(item, a.height - 1);
212 var newA = nodeCopy(a);
213 newA.table.push(newSlot);
214 newA.lengths.push(newA.lengths[newA.lengths.length - 1] + length(newSlot));
215 return newA
216 } else {
217 return null;
218 }
219 }
221 // Converts an array into a list of elements.
222 function toList(a) {
223 return toList_(List.Nil, a);
224 }
226 function toList_(list, a) {
227 for (var i = a.table.length - 1; i >= 0; i--) {
228 list = a.height == 0 ? List.Cons(a.table[i], list) : toList_(list, a.table[i]);
229 }
230 return list;
231 }
233 // Maps a function over the elements of an array.
234 function map(f, a) {
235 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
236 if (a.height > 0) { newA.lengths = a.lengths; }
237 for (var i = 0; i < a.table.length; i++) {
238 newA.table[i] = a.height == 0 ? f(a.table[i]) : map(f, a.table[i]);
239 }
240 return newA;
241 }
243 // Maps a function over the elements with their index as first argument.
244 function indexedMap(f, a) {
245 return indexedMap_(f, a, 0);
246 }
248 function indexedMap_(f, a, from) {
249 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
250 if (a.height > 0) { newA.lengths = a.lengths; }
251 for (var i = 0; i < a.table.length; i++) {
252 newA.table[i] = a.height == 0 ? A2(f, from + i, a.table[i])
253 : indexedMap_( f, a.table[i]
254 , i == 0 ? 0 : a.lengths[i - 1]);
255 }
256 return newA;
257 }
259 function foldl(f, b, a) {
260 if (a.height == 0) {
261 for (var i = 0; i < a.table.length; i++) {
262 b = A2(f, a.table[i], b);
263 }
264 } else {
265 for (var i = 0; i < a.table.length; i++) {
266 b = foldl(f, b, a.table[i]);
267 }
268 }
269 return b;
270 }
272 function foldr(f, b, a) {
273 if (a.height == 0) {
274 for (var i = a.table.length; i--; ) {
275 b = A2(f, a.table[i], b);
276 }
277 } else {
278 for (var i = a.table.length; i--; ) {
279 b = foldl(f, b, a.table[i]);
280 }
281 }
282 return b;
283 }
285 // TODO: currently, it slices the right, then the left. This can be
286 // optimized.
287 function slice(from, to, a) {
288 if (from < 0) { from += length(a); }
289 if (to < 0) { to += length(a); }
290 return sliceLeft(from, sliceRight(to, a));
291 }
293 function sliceRight(to, a) {
294 if (to == length(a)) {
295 return a;
296 }
298 // Handle leaf level.
299 if (a.height == 0) {
300 var newA = { ctor:"_Array", height:0 };
301 newA.table = a.table.slice(0, to);
302 return newA;
303 }
305 // Slice the right recursively.
306 var right = getSlot(to, a);
307 var sliced = sliceRight(to - (right > 0 ? a.lengths[right - 1] : 0), a.table[right]);
309 // Maybe the a node is not even needed, as sliced contains the whole slice.
310 if (right == 0) {
311 return sliced;
312 }
314 // Create new node.
315 var newA = { ctor:"_Array", height:a.height
316 , table:a.table.slice(0, right)
317 , lengths:a.lengths.slice(0, right) };
318 if (sliced.table.length > 0) {
319 newA.table[right] = sliced;
320 newA.lengths[right] = length(sliced) + (right > 0 ? newA.lengths[right - 1] : 0);
321 }
322 return newA;
323 }
325 function sliceLeft(from, a) {
326 if (from == 0) {
327 return a;
328 }
330 // Handle leaf level.
331 if (a.height == 0) {
332 var newA = { ctor:"_Array", height:0 };
333 newA.table = a.table.slice(from, a.table.length + 1);
334 return newA;
335 }
337 // Slice the left recursively.
338 var left = getSlot(from, a);
339 var sliced = sliceLeft(from - (left > 0 ? a.lengths[left - 1] : 0), a.table[left]);
341 // Maybe the a node is not even needed, as sliced contains the whole slice.
342 if (left == a.table.length - 1) {
343 return sliced;
344 }
346 // Create new node.
347 var newA = { ctor:"_Array", height:a.height
348 , table:a.table.slice(left, a.table.length + 1)
349 , lengths:new Array(a.table.length - left) };
350 newA.table[0] = sliced;
351 var len = 0;
352 for (var i = 0; i < newA.table.length; i++) {
353 len += length(newA.table[i]);
354 newA.lengths[i] = len;
355 }
357 return newA;
358 }
360 // Appends two trees.
361 function append(a,b) {
362 if (a.table.length === 0) {
363 return b;
364 }
365 if (b.table.length === 0) {
366 return a;
367 }
369 var c = append_(a, b);
371 // Check if both nodes can be crunshed together.
372 if (c[0].table.length + c[1].table.length <= M) {
373 if (c[0].table.length === 0) {
374 return c[1];
375 }
376 if (c[1].table.length === 0) {
377 return c[0];
378 }
380 // Adjust .table and .lengths
381 c[0].table = c[0].table.concat(c[1].table);
382 if (c[0].height > 0) {
383 var len = length(c[0]);
384 for (var i = 0; i < c[1].lengths.length; i++) {
385 c[1].lengths[i] += len;
386 }
387 c[0].lengths = c[0].lengths.concat(c[1].lengths);
388 }
390 return c[0];
391 }
393 var toRemove = calcToRemove(a, b);
394 if (toRemove > E) {
395 c = shuffle(c[0], c[1], toRemove);
396 }
398 return siblise(c[0], c[1]);
399 }
401 // Returns an array of two nodes; right and left. One node _may_ be empty.
402 function append_(a, b) {
403 if (a.height === 0 && b.height === 0) {
404 return [a, b];
405 }
407 if (a.height !== 1 || b.height !== 1) {
408 if (a.height === b.height) {
409 a = nodeCopy(a);
410 b = nodeCopy(b);
411 var appended = append_(botRight(a), botLeft(b));
413 insertRight(a, appended[1]);
414 insertLeft(b, appended[0]);
415 } else if (a.height > b.height) {
416 a = nodeCopy(a);
417 var appended = append_(botRight(a), b);
419 insertRight(a, appended[0]);
420 b = parentise(appended[1], appended[1].height + 1);
421 } else {
422 b = nodeCopy(b);
423 var appended = append_(a, botLeft(b));
425 var left = appended[0].table.length === 0 ? 0 : 1;
426 var right = left === 0 ? 1 : 0;
427 insertLeft(b, appended[left]);
428 a = parentise(appended[right], appended[right].height + 1);
429 }
430 }
432 // Check if balancing is needed and return based on that.
433 if (a.table.length === 0 || b.table.length === 0) {
434 return [a,b];
435 }
437 var toRemove = calcToRemove(a, b);
438 if (toRemove <= E) {
439 return [a,b];
440 }
441 return shuffle(a, b, toRemove);
442 }
444 // Helperfunctions for append_. Replaces a child node at the side of the parent.
445 function insertRight(parent, node) {
446 var index = parent.table.length - 1;
447 parent.table[index] = node;
448 parent.lengths[index] = length(node)
449 parent.lengths[index] += index > 0 ? parent.lengths[index - 1] : 0;
450 }
452 function insertLeft(parent, node) {
453 if (node.table.length > 0) {
454 parent.table[0] = node;
455 parent.lengths[0] = length(node);
457 var len = length(parent.table[0]);
458 for (var i = 1; i < parent.lengths.length; i++) {
459 len += length(parent.table[i]);
460 parent.lengths[i] = len;
461 }
462 } else {
463 parent.table.shift();
464 for (var i = 1; i < parent.lengths.length; i++) {
465 parent.lengths[i] = parent.lengths[i] - parent.lengths[0];
466 }
467 parent.lengths.shift();
468 }
469 }
471 // Returns the extra search steps for E. Refer to the paper.
472 function calcToRemove(a, b) {
473 var subLengths = 0;
474 for (var i = 0; i < a.table.length; i++) {
475 subLengths += a.table[i].table.length;
476 }
477 for (var i = 0; i < b.table.length; i++) {
478 subLengths += b.table[i].table.length;
479 }
481 var toRemove = a.table.length + b.table.length
482 return toRemove - (Math.floor((subLengths - 1) / M) + 1);
483 }
485 // get2, set2 and saveSlot are helpers for accessing elements over two arrays.
486 function get2(a, b, index) {
487 return index < a.length ? a[index] : b[index - a.length];
488 }
490 function set2(a, b, index, value) {
491 if (index < a.length) {
492 a[index] = value;
493 } else {
494 b[index - a.length] = value;
495 }
496 }
498 function saveSlot(a, b, index, slot) {
499 set2(a.table, b.table, index, slot);
501 var l = (index == 0 || index == a.lengths.length) ?
502 0 : get2(a.lengths, a.lengths, index - 1);
503 set2(a.lengths, b.lengths, index, l + length(slot));
504 }
506 // Creates a node or leaf with a given length at their arrays for perfomance.
507 // Is only used by shuffle.
508 function createNode(h, length) {
509 if (length < 0) { length = 0; }
510 var a = { ctor:"_Array", height:h, table:new Array(length) };
511 if (h > 0) {
512 a.lengths = new Array(length);
513 }
514 return a;
515 }
517 // Returns an array of two balanced nodes.
518 function shuffle(a, b, toRemove) {
519 var newA = createNode(a.height, Math.min(M, a.table.length + b.table.length - toRemove));
520 var newB = createNode(a.height, newA.table.length - (a.table.length + b.table.length - toRemove));
522 // Skip the slots with size M. More precise: copy the slot references
523 // to the new node
524 var read = 0;
525 while (get2(a.table, b.table, read).table.length % M == 0) {
526 set2(newA.table, newB.table, read, get2(a.table, b.table, read));
527 set2(newA.lengths, newB.lengths, read, get2(a.lengths, b.lengths, read));
528 read++;
529 }
531 // Pulling items from left to right, caching in a slot before writing
532 // it into the new nodes.
533 var write = read;
534 var slot = new createNode(a.height - 1, 0);
535 var from = 0;
537 // If the current slot is still containing data, then there will be at
538 // least one more write, so we do not break this loop yet.
539 while (read - write - (slot.table.length > 0 ? 1 : 0) < toRemove) {
540 // Find out the max possible items for copying.
541 var source = get2(a.table, b.table, read);
542 var to = Math.min(M - slot.table.length, source.table.length)
544 // Copy and adjust size table.
545 slot.table = slot.table.concat(source.table.slice(from, to));
546 if (slot.height > 0) {
547 var len = slot.lengths.length;
548 for (var i = len; i < len + to - from; i++) {
549 slot.lengths[i] = length(slot.table[i]);
550 slot.lengths[i] += (i > 0 ? slot.lengths[i - 1] : 0);
551 }
552 }
554 from += to;
556 // Only proceed to next slots[i] if the current one was
557 // fully copied.
558 if (source.table.length <= to) {
559 read++; from = 0;
560 }
562 // Only create a new slot if the current one is filled up.
563 if (slot.table.length == M) {
564 saveSlot(newA, newB, write, slot);
565 slot = createNode(a.height - 1,0);
566 write++;
567 }
568 }
570 // Cleanup after the loop. Copy the last slot into the new nodes.
571 if (slot.table.length > 0) {
572 saveSlot(newA, newB, write, slot);
573 write++;
574 }
576 // Shift the untouched slots to the left
577 while (read < a.table.length + b.table.length ) {
578 saveSlot(newA, newB, write, get2(a.table, b.table, read));
579 read++; write++;
580 }
582 return [newA, newB];
583 }
585 // Navigation functions
586 function botRight(a) { return a.table[a.table.length - 1]; }
587 function botLeft(a) { return a.table[0]; }
589 // Copies a node for updating. Note that you should not use this if
590 // only updating only one of "table" or "lengths" for performance reasons.
591 function nodeCopy(a) {
592 var newA = { ctor:"_Array", height:a.height
593 , table:a.table.slice() };
594 if (a.height > 0) { newA.lengths = a.lengths.slice(); }
595 return newA;
596 }
598 // Returns how many items are in the tree.
599 function length(array) {
600 if (array.height == 0) {
601 return array.table.length;
602 } else {
603 return array.lengths[array.lengths.length - 1];
604 }
605 }
607 // Calculates in which slot of "table" the item probably is, then
608 // find the exact slot via forward searching in "lengths". Returns the index.
609 function getSlot(i, a) {
610 var slot = i >> (5 * a.height);
611 while (a.lengths[slot] <= i) {
612 slot++;
613 }
614 return slot;
615 }
617 // Recursively creates a tree with a given height containing
618 // only the given item.
619 function create(item, h) {
620 if (h == 0) {
621 return { ctor:"_Array", height:0
622 , table:[item] };
623 } else {
624 return { ctor:"_Array", height:h
625 , table:[create(item, h - 1)]
626 , lengths:[1] };
627 }
628 }
630 // Recursively creates a tree that contains the given tree.
631 function parentise(tree, h) {
632 if (h == tree.height) {
633 return tree;
634 } else {
635 return { ctor:"_Array", height:h
636 , table:[parentise(tree, h - 1)]
637 , lengths:[length(tree)] };
638 }
639 }
641 // Emphasizes blood brotherhood beneath two trees.
642 function siblise(a, b) {
643 return { ctor:"_Array", height:a.height + 1
644 , table:[a, b]
645 , lengths:[length(a), length(a) + length(b)] };
646 }
648 function toJSArray(a) {
649 var jsArray = new Array(length(a));
650 toJSArray_(jsArray, 0, a);
651 return jsArray;
652 }
654 function toJSArray_(jsArray, i, a) {
655 for (var t = 0; t < a.table.length; t++) {
656 if (a.height == 0) {
657 jsArray[i + t] = a.table[t];
658 } else {
659 var inc = t == 0 ? 0 : a.lengths[t - 1];
660 toJSArray_(jsArray, i + inc, a.table[t]);
661 }
662 }
663 }
665 function fromJSArray(jsArray) {
666 if (jsArray.length == 0) { return empty; }
667 var h = Math.floor(Math.log(jsArray.length) / Math.log(M));
668 return fromJSArray_(jsArray, h, 0, jsArray.length);
669 }
671 function fromJSArray_(jsArray, h, from, to) {
672 if (h == 0) {
673 return { ctor:"_Array", height:0
674 , table:jsArray.slice(from, to) };
675 }
677 var step = Math.pow(M, h);
678 var table = new Array(Math.ceil((to - from) / step));
679 var lengths = new Array(table.length);
680 for (var i = 0; i < table.length; i++) {
681 table[i] = fromJSArray_( jsArray, h - 1, from + (i * step)
682 , Math.min(from + ((i + 1) * step), to));
683 lengths[i] = length(table[i]) + (i > 0 ? lengths[i-1] : 0);
684 }
685 return { ctor:"_Array", height:h, table:table, lengths:lengths };
686 }
688 Elm.Native.Array.values = {
689 empty:empty,
690 fromList:fromList,
691 toList:toList,
692 initialize:F2(initialize),
693 append:F2(append),
694 push:F2(push),
695 slice:F3(slice),
696 get:F2(get),
697 set:F3(set),
698 map:F2(map),
699 indexedMap:F2(indexedMap),
700 foldl:F3(foldl),
701 foldr:F3(foldr),
702 length:length,
704 toJSArray:toJSArray,
705 fromJSArray:fromJSArray
706 };
708 return elm.Native.Array.values = Elm.Native.Array.values;