git.iko.soy/elk
on 481a730 help sign in
elk/libraries/Native/Array.js
655 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 while (array.lengths[slot] <= i) slot++;
39 if (slot > 0) i -= array.lengths[slot - 1];
40 array = array.table[slot];
41 }
42 return array.table[i];
43 }
45 // Sets the value at the index i. Only the nodes leading to i will get
46 // copied and updated.
47 function set(i, item, array) {
48 if (i < 0 || length(array) <= i) {
49 return array;
50 }
51 return unsafeSet(i, item, array);
52 }
54 function unsafeSet(i, item, array) {
55 array = nodeCopy(array);
57 if (array.height == 0) {
58 array.table[i] = item;
59 } else {
60 var slot = getSlot(i, array);
61 if (slot > 0) {
62 i -= array.lengths[slot - 1];
63 }
64 array.table[slot] = unsafeSet(i, item, array.table[slot]);
65 }
66 return array;
67 }
69 function initialize(len, f) {
70 if (len == 0) { return empty; }
71 var h = Math.floor(Math.log(len)/Math.log(M));
72 return initialize_(f, h, 0, len);
73 }
75 function initialize_(f, h, from, to) {
76 if (h == 0) {
77 var table = new Array((to - from) % (M + 1));
78 for (var i = 0; i < table.length; i++) {
79 table[i] = f(from + i);
80 }
81 return { ctor:"_Array", height:0, table:table };
82 }
84 var step = Math.pow(M, h);
85 var table = new Array(Math.ceil((to - from) / step));
86 var lengths = new Array(table.length);
87 for (var i = 0; i < table.length; i++) {
88 table[i] = initialize_( f, h - 1, from + (i * step)
89 , Math.min(from + ((i + 1) * step), to));
90 lengths[i] = length(table[i]) + (i > 0 ? lengths[i-1] : 0);
91 }
92 return { ctor:"_Array", height:h, table:table, lengths:lengths };
93 }
95 function fromList(list) {
96 if (list == List.Nil) { return empty; }
98 // Allocate M sized blocks (table) and write list elements to it.
99 var table = new Array(M);
100 var nodes = new Array();
101 var i = 0;
103 while (list.ctor !== '[]') {
104 table[i] = list._0;
105 list = list._1;
106 i++;
108 // table is full, so we can push a leaf containing it into the
109 // next node.
110 if (i == M) {
111 fromListPush({ ctor:"_Array", height:0, table:table }
112 , nodes);
113 table = new Array(M);
114 i = 0;
115 }
116 }
118 // Maybe there is something left on the table.
119 if (i > 0) {
120 fromListPush({ ctor:"_Array", height:0, table:table.splice(0,i) }
121 , nodes);
122 }
124 // Go through all of the nodes and eventually push them into higher nodes.
125 for (var h = 0; h < nodes.length - 1; h++) {
126 if (nodes[h].table.length > 0) {
127 fromListPush(nodes[h], nodes);
128 }
129 }
131 var head = nodes[nodes.length - 1];
132 if (head.height > 0 && head.table.length == 1) {
133 return head.table[0];
134 } else {
135 return head;
136 }
137 }
139 // Push a node into a higher node as a child.
140 function fromListPush(toPush, nodes) {
141 var h = toPush.height;
143 // Maybe the node on this height does not exist.
144 if (nodes.length == h) {
145 nodes.push({ ctor:"_Array", height:h + 1
146 , table:new Array()
147 , lengths:new Array() });
148 }
150 nodes[h].table.push(toPush);
151 var len = length(toPush);
152 if (nodes[h].lengths.length > 0) {
153 len += nodes[h].lengths[nodes[h].lengths.length - 1];
154 }
155 nodes[h].lengths.push(len);
157 if (nodes[h].table.length == M) {
158 fromListPush(nodes[h], nodes);
159 nodes[h] = { ctor:"_Array", height:h + 1
160 , table:new Array()
161 , lengths:new Array() };
162 }
163 }
165 // Pushes an item via push_ to the bottom right of a tree.
166 function push(item, a) {
167 var pushed = push_(item, a);
168 if (pushed !== null) {
169 return pushed;
170 }
172 var newTree = create(item, a.height);
173 return siblise(a, newTree);
174 }
176 // Recursively tries to push an item to the bottom-right most
177 // tree possible. If there is no space left for the item,
178 // null will be returned.
179 function push_(item, a) {
180 // Handle resursion stop at leaf level.
181 if (a.height == 0) {
182 if (a.table.length < M) {
183 var newA = { ctor:"_Array", height:0, table:a.table.slice() };
184 newA.table.push(item);
185 return newA;
186 } else {
187 return null;
188 }
189 }
191 // Recursively push
192 var pushed = push_(item, botRight(a));
194 // There was space in the bottom right tree, so the slot will
195 // be updated.
196 if (pushed != null) {
197 var newA = nodeCopy(a);
198 newA.table[newA.table.length - 1] = pushed;
199 newA.lengths[newA.lengths.length - 1]++;
200 return newA
201 }
203 // When there was no space left, check if there is space left
204 // for a new slot with a tree which contains only the item
205 // at the bottom.
206 if (a.table.length < M) {
207 var newSlot = create(item, a.height - 1);
208 var newA = nodeCopy(a);
209 newA.table.push(newSlot);
210 newA.lengths.push(newA.lengths[newA.lengths.length - 1] + length(newSlot));
211 return newA
212 } else {
213 return null;
214 }
215 }
217 // Converts an array into a list of elements.
218 function toList(a) {
219 return toList_(List.Nil, a);
220 }
222 function toList_(list, a) {
223 for (var i = a.table.length - 1; i >= 0; i--) {
224 list = a.height == 0 ? List.Cons(a.table[i], list) : toList_(list, a.table[i]);
225 }
226 return list;
227 }
229 // Maps a function over the elements of an array.
230 function map(f, a) {
231 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
232 if (a.height > 0) { newA.lengths = a.lengths; }
233 for (var i = 0; i < a.table.length; i++) {
234 newA.table[i] = a.height == 0 ? f(a.table[i]) : map(f, a.table[i]);
235 }
236 return newA;
237 }
239 // Maps a function over the elements with their index as first argument.
240 function indexedMap(f, a) {
241 return indexedMap_(f, a, 0);
242 }
244 function indexedMap_(f, a, from) {
245 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
246 if (a.height > 0) { newA.lengths = a.lengths; }
247 for (var i = 0; i < a.table.length; i++) {
248 newA.table[i] = a.height == 0 ? A2(f, from + i, a.table[i])
249 : indexedMap_( f, a.table[i]
250 , i == 0 ? 0 : a.lengths[i - 1]);
251 }
252 return newA;
253 }
255 function foldl(f, b, a) {
256 if (a.height == 0) {
257 for (var i = 0; i < a.table.length; i++) {
258 b = A2(f, a.table[i], b);
259 }
260 } else {
261 for (var i = 0; i < a.table.length; i++) {
262 b = foldl(f, b, a.table[i]);
263 }
264 }
265 return b;
266 }
268 function foldr(f, b, a) {
269 if (a.height == 0) {
270 for (var i = a.table.length; i--; ) {
271 b = A2(f, a.table[i], b);
272 }
273 } else {
274 for (var i = a.table.length; i--; ) {
275 b = foldl(f, b, a.table[i]);
276 }
277 }
278 return b;
279 }
281 // TODO: currently, it slices the right, then the left. This can be
282 // optimized.
283 function slice(from, to, a) {
284 if (from < 0) { from += length(a); }
285 if (to < 0) { to += length(a); }
286 return sliceLeft(from, sliceRight(to, a));
287 }
289 function sliceRight(to, a) {
290 if (to == length(a)) {
291 return a;
292 }
294 // Handle leaf level.
295 if (a.height == 0) {
296 var newA = { ctor:"_Array", height:0 };
297 newA.table = a.table.slice(0, to);
298 return newA;
299 }
301 // Slice the right recursively.
302 var right = getSlot(to, a);
303 var sliced = sliceRight(to - (right > 0 ? a.lengths[right - 1] : 0), a.table[right]);
305 // Maybe the a node is not even needed, as sliced contains the whole slice.
306 if (right == 0) {
307 return sliced;
308 }
310 // Create new node.
311 var newA = { ctor:"_Array", height:a.height
312 , table:a.table.slice(0, right + 1)
313 , lengths:a.lengths.slice(0, right + 1) };
314 newA.table[right] = sliced;
315 newA.lengths[right] = length(sliced) + (right > 0 ? newA.lengths[right - 1] : 0);
316 return newA;
317 }
319 function sliceLeft(from, a) {
320 if (from == 0) {
321 return a;
322 }
324 // Handle leaf level.
325 if (a.height == 0) {
326 var newA = { ctor:"_Array", height:0 };
327 newA.table = a.table.slice(from, a.table.length + 1);
328 return newA;
329 }
331 // Slice the left recursively.
332 var left = getSlot(from, a);
333 var sliced = sliceLeft(from - (left > 0 ? a.lengths[left - 1] : 0), a.table[left]);
335 // Maybe the a node is not even needed, as sliced contains the whole slice.
336 if (left == a.table.length - 1) {
337 return sliced;
338 }
340 // Create new node.
341 var newA = { ctor:"_Array", height:a.height
342 , table:a.table.slice(left, a.table.length + 1)
343 , lengths:new Array(a.table.length - left) };
344 newA.table[left] = sliced;
345 var len = 0;
346 for (var i = 0; i < newA.table.length; i++) {
347 len += length(newA.table[i]);
348 newA.lengths[i] = len;
349 }
351 return newA;
352 }
354 // Appends two trees.
355 // TODO: Add support for appending trees of different sizes. Current
356 // behavior will just rise the lower tree and then append them.
357 function append(a,b) {
358 if (a.table.length == 0) return b;
359 if (b.table.length == 0) return a;
360 if (b.height > a.height) return append(parentise(a, b.height), b);
361 if (a.height > b.height) return append(a, parentise(b, a.height));
362 if (a.height == 0) return append(parentise(a, 1), parentise(b, 1));
364 var c = append_(a, b);
365 if (c[1].table.length > 0) {
366 return siblise(c[0], c[1]);
367 } else {
368 return c[0];
369 }
370 }
372 // Returns an array of two nodes. The second node _may_ be empty. This case
373 // needs to be handled by the function, that called append_. May be only
374 // called for trees with an minimal height of 1.
375 function append_(a, b) {
376 if (a.height == 1) {
377 // Check if balancing is needed and return based on that.
378 var toRemove = calcToRemove(a, b);
379 if (toRemove <= E) {
380 return [a,b];
381 }
383 return shuffle(a, b, toRemove);
384 }
386 var appended = append_(botRight(a), botLeft(b));
387 a = nodeCopy(a), b = nodeCopy(b);
389 // Adjust the bottom right side of the new tree.
390 a.table[a.table.length - 1] = appended[0];
391 a.lengths[a.lengths.length - 1] = length(appended[0])
392 a.lengths[a.lengths.length - 1] += a.lengths.length > 1 ? a.lengths[a.lengths.length - 2] : 0;
394 // Adjust the bottom left side of the new tree.
395 if (appended[1].table.length > 0) {
396 b.table[0] = appended[1];
397 b.lengths[0] = length(appended[1]);
398 for (var i = 1, len = length(b.table[0]); i < b.lengths.length; i++) {
399 len += length(b.table[i]);
400 b.lengths[i] = len;
401 }
402 } else {
403 b.table.shift();
404 for (var i = 1; i < b.lengths.length; i++) {
405 b.lengths[i] = b.lengths[i] - b.lengths[0];
406 }
407 b.lengths.shift();
408 }
410 // Check if balancing is needed and return based on that.
411 var toRemove = calcToRemove(a, b);
412 if (toRemove <= E || b.table.length == 0) {
413 return [a,b];
414 }
416 return shuffle(a, b, toRemove);
417 }
419 // Returns the extra search steps for E. Refer to the paper.
420 function calcToRemove(a, b) {
421 var subLengths = 0;
422 for (var i = 0; i < a.table.length; i++) {
423 subLengths += a.table[i].table.length;
424 }
425 for (var i = 0; i < b.table.length; i++) {
426 subLengths += b.table[i].table.length;
427 }
429 var toRemove = a.table.length + b.table.length
430 return toRemove - (Math.floor((subLengths - 1) / M) + 1);
431 }
433 // get2, set2 and saveSlot are helpers for accessing elements over two arrays.
434 function get2(a, b, index) {
435 return index < a.length ? a[index] : b[index - a.length];
436 }
438 function set2(a, b, index, value) {
439 if (index < a.length) {
440 a[index] = value;
441 } else {
442 b[index - a.length] = value;
443 }
444 }
446 function saveSlot(a, b, index, slot) {
447 set2(a.table, b.table, index, slot);
449 var l = (index == 0 || index == a.lengths.length) ?
450 0 : get2(a.lengths, a.lengths, index - 1);
451 set2(a.lengths, b.lengths, index, l + length(slot));
452 }
454 // Creates a node or leaf with a given length at their arrays for perfomance.
455 // Is only used by shuffle.
456 function createNode(h, length) {
457 if (length < 0) { length = 0; }
458 var a = { ctor:"_Array", height:h, table:new Array(length) };
459 if (h > 0) {
460 a.lengths = new Array(length);
461 }
462 return a;
463 }
465 // Returns an array of two balanced nodes.
466 function shuffle(a, b, toRemove) {
467 var newA = createNode(a.height, Math.min(M, a.table.length + b.table.length - toRemove));
468 var newB = createNode(a.height, newA.table.length - (a.table.length + b.table.length - toRemove));
470 // Skip the slots with size M. More precise: copy the slot references
471 // to the new node
472 var read = 0;
473 while (get2(a.table, b.table, read).table.length % M == 0) {
474 set2(newA.table, newB.table, read, get2(a.table, b.table, read));
475 set2(newA.lengths, newB.lengths, read, get2(a.lengths, b.lengths, read));
476 read++;
477 }
479 // Pulling items from left to right, caching in a slot before writing
480 // it into the new nodes.
481 var write = read;
482 var slot = new createNode(a.height - 1, 0);
483 var from = 0;
485 // If the current slot is still containing data, then there will be at
486 // least one more write, so we do not break this loop yet.
487 while (read - write - (slot.table.length > 0 ? 1 : 0) < toRemove) {
488 // Find out the max possible items for copying.
489 var source = get2(a.table, b.table, read);
490 var to = Math.min(M - slot.table.length, source.table.length)
492 // Copy and adjust size table.
493 slot.table = slot.table.concat(source.table.slice(from, to));
494 if (slot.height > 0) {
495 var len = slot.lengths.length;
496 for (var i = len; i < len + to - from; i++) {
497 slot.lengths[i] = length(slot.table[i]);
498 slot.lengths[i] += (i > 0 ? slot.lengths[i - 1] : 0);
499 }
500 }
502 from += to;
504 // Only proceed to next slots[i] if the current one was
505 // fully copied.
506 if (source.table.length <= to) {
507 read++; from = 0;
508 }
510 // Only create a new slot if the current one is filled up.
511 if (slot.table.length == M) {
512 saveSlot(newA, newB, write, slot);
513 slot = createNode(a.height - 1,0);
514 write++;
515 }
516 }
518 // Cleanup after the loop. Copy the last slot into the new nodes.
519 if (slot.table.length > 0) {
520 saveSlot(newA, newB, write, slot);
521 write++;
522 }
524 // Shift the untouched slots to the left
525 while (read < a.table.length + b.table.length ) {
526 saveSlot(newA, newB, write, get2(a.table, b.table, read));
527 read++; write++;
528 }
530 return [newA, newB];
531 }
533 // Navigation functions
534 function botRight(a) { return a.table[a.table.length - 1]; }
535 function botLeft(a) { return a.table[0]; }
537 // Copies a node for updating. Note that you should not use this if
538 // only updating only one of "table" or "lengths" for performance reasons.
539 function nodeCopy(a) {
540 var newA = { ctor:"_Array", height:a.height
541 , table:a.table.slice() };
542 if (a.height > 0) { newA.lengths = a.lengths.slice(); }
543 return newA;
544 }
546 // Returns how many items are in the tree.
547 function length(array) {
548 if (array.height == 0) {
549 return array.table.length;
550 } else {
551 return array.lengths[array.lengths.length - 1];
552 }
553 }
555 // Calculates in which slot of "table" the item probably is, then
556 // find the exact slot via forward searching in "lengths". Returns the index.
557 function getSlot(i, a) {
558 var slot = i >> (5 * a.height);
559 while (a.lengths[slot] <= i) slot++;
560 return slot;
561 }
563 // Recursively creates a tree with a given height containing
564 // only the given item.
565 function create(item, h) {
566 if (h == 0) {
567 return { ctor:"_Array", height:0
568 , table:[item] };
569 } else {
570 return { ctor:"_Array", height:h
571 , table:[create(item, h - 1)]
572 , lengths:[1] };
573 }
574 }
576 // Recursively creates a tree that contains the given tree.
577 function parentise(tree, h) {
578 if (h == tree.height) {
579 return tree;
580 } else {
581 return { ctor:"_Array", height:h
582 , table:[parentise(tree, h - 1)]
583 , lengths:[length(tree)] };
584 }
585 }
587 // Emphasizes blood brotherhood beneath two trees.
588 function siblise(a, b) {
589 return { ctor:"_Array", height:a.height + 1
590 , table:[a, b]
591 , lengths:[length(a), length(a) + length(b)] };
592 }
594 function toJSArray(a) {
595 var jsArray = new Array(length(a));
596 toJSArray_(jsArray, 0, a);
597 return jsArray;
598 }
600 function toJSArray_(jsArray, i, a) {
601 for (var t = 0; t < a.table.length; t++) {
602 if (a.height == 0) {
603 jsArray[i + t] = a.table[t];
604 } else {
605 var inc = t == 0 ? 0 : a.lengths[t - 1];
606 toJSArray_(jsArray, i + inc, a.table[t]);
607 }
608 }
609 }
611 function fromJSArray(jsArray) {
612 if (jsArray.length == 0) { return empty; }
613 var h = Math.floor(Math.log(jsArray.length) / Math.log(M));
614 return fromJSArray_(jsArray, h, 0, jsArray.length);
615 }
617 function fromJSArray_(jsArray, h, from, to) {
618 if (h == 0) {
619 return { ctor:"_Array", height:0
620 , table:jsArray.slice(from, to) };
621 }
623 var step = Math.pow(M, h);
624 var table = new Array(Math.ceil((to - from) / step));
625 var lengths = new Array(table.length);
626 for (var i = 0; i < table.length; i++) {
627 table[i] = fromJSArray_( jsArray, h - 1, from + (i * step)
628 , Math.min(from + ((i + 1) * step), to));
629 lengths[i] = length(table[i]) + (i > 0 ? lengths[i-1] : 0);
630 }
631 return { ctor:"_Array", height:h, table:table, lengths:lengths };
632 }
634 Elm.Native.Array.values = {
635 empty:empty,
636 fromList:fromList,
637 toList:toList,
638 initialize:F2(initialize),
639 append:F2(append),
640 push:F2(push),
641 slice:F3(slice),
642 get:F2(get),
643 set:F3(set),
644 map:F2(map),
645 indexedMap:F2(indexedMap),
646 foldl:F3(foldl),
647 foldr:F3(foldr),
648 length:length,
650 toJSArray:toJSArray,
651 fromJSArray:fromJSArray
652 };
654 return elm.Native.Array.values = Elm.Native.Array.values;