git.iko.soy/elk
on fa1ea89 help sign in
elk/libraries/Native/Array.js
592 lines 19 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 // Gets the value at index i recursively.
28 function get(i, array) {
29 if (i < 0 || i >= length(array)) {
30 throw new Error("Index " + i + " is out of range. Check the length of " +
31 "your array first or use getMaybe or getWithDefault.");
32 }
33 return unsafeGet(i, array);
34 }
36 function unsafeGet(i, array) {
37 if (array.height == 0) {
38 return array.table[i];
39 }
40 var slot = getSlot(i, array);
41 var offset = slot > 0 ? array.lengths[slot-1] : 0;
42 return unsafeGet(i - offset, array.table[slot]);
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, a) {
48 if (length(a) <= i) {
49 return a;
50 }
51 var newA = nodeCopy(a);
52 newA.table = a.table.slice();
54 if (a.height == 0) {
55 newA.table[i] = item;
56 } else {
57 var slot = getSlot(i, a);
58 var sub = slot > 0 ? a.lengths[slot-1] : 0;
59 newA.table[slot] = set(i - sub, item, a.table[slot]);
60 }
61 return newA;
62 }
64 function initialize(len, f) {
65 if (len == 0) { return empty; }
66 var h = Math.floor(Math.log(len)/Math.log(M));
67 return initialize_(f, h, 0, len);
68 }
70 function initialize_(f, h, from, to) {
71 if (h == 0) {
72 var table = new Array((to - from) % (M + 1));
73 for (var i = 0; i < table.length; i++) {
74 table[i] = f(from + i);
75 }
76 return { ctor:"_Array", height:0, table:table };
77 }
79 var step = Math.pow(M, h);
80 var table = new Array(Math.ceil((to - from) / step));
81 var lengths = new Array(table.length);
82 for (var i = 0; i < table.length; i++) {
83 table[i] = initialize_( f, h - 1, from + (i * step)
84 , Math.min(from + ((i + 1) * step), to));
85 lengths[i] = length(table[i]) + (i > 0 ? lengths[i-1] : 0);
86 }
87 return { ctor:"_Array", height:h, table:table, lengths:lengths };
88 }
90 function fromList(list) {
91 if (list == List.Nil) { return empty; }
93 // Allocate M sized blocks (table) and write list elements to it.
94 var table = new Array(M);
95 var nodes = new Array();
96 var i = 0;
98 while (list.ctor !== '[]') {
99 table[i] = list._0;
100 list = list._1;
101 i++;
103 // table is full, so we can push a leaf containing it into the
104 // next node.
105 if (i == M) {
106 fromListPush({ ctor:"_Array", height:0, table:table }
107 , nodes);
108 table = new Array(M);
109 i = 0;
110 }
111 }
113 // Maybe there is something left on the table.
114 if (i > 0) {
115 fromListPush({ ctor:"_Array", height:0, table:table.splice(0,i) }
116 , nodes);
117 }
119 // Go through all of the nodes and eventually push them into higher nodes.
120 for (var h = 0; h < nodes.length - 1; h++) {
121 if (nodes[h].table.length > 0) {
122 fromListPush(nodes[h], nodes);
123 }
124 }
126 var head = nodes[nodes.length - 1];
127 if (head.height > 0 && head.table.length == 1) {
128 return head.table[0];
129 } else {
130 return head;
131 }
132 }
134 // Push a node into a higher node as a child.
135 function fromListPush(toPush, nodes) {
136 var h = toPush.height;
138 // Maybe the node on this height does not exist.
139 if (nodes.length == h) {
140 nodes.push({ ctor:"_Array", height:h + 1
141 , table:new Array()
142 , lengths:new Array() });
143 }
145 nodes[h].table.push(toPush);
146 var len = length(toPush);
147 if (nodes[h].lengths.length > 0) {
148 len += nodes[h].lengths[nodes[h].lengths.length - 1];
149 }
150 nodes[h].lengths.push(len);
152 if (nodes[h].table.length == M) {
153 fromListPush(nodes[h], nodes);
154 nodes[h] = { ctor:"_Array", height:h + 1
155 , table:new Array()
156 , lengths:new Array() };
157 }
158 }
160 // Pushes an item via push_ to the bottom right of a tree.
161 function push(item, a) {
162 var pushed = push_(item, a);
163 if (pushed !== null) {
164 return pushed;
165 }
167 var newTree = create(item, a.height);
168 return siblise(a, newTree);
169 }
171 // Recursively tries to push an item to the bottom-right most
172 // tree possible. If there is no space left for the item,
173 // null will be returned.
174 function push_(item, a) {
175 // Handle resursion stop at leaf level.
176 if (a.height == 0) {
177 if (a.table.length < M) {
178 var newA = { ctor:"_Array", height:0, table:a.table.slice() };
179 newA.table.push(item);
180 return newA;
181 } else {
182 return null;
183 }
184 }
186 // Recursively push
187 var pushed = push_(item, botRight(a));
189 // There was space in the bottom right tree, so the slot will
190 // be updated.
191 if (pushed != null) {
192 var newA = nodeCopy(a);
193 newA.table[newA.table.length - 1] = pushed;
194 newA.lengths[newA.lengths.length - 1]++;
195 return newA
196 }
198 // When there was no space left, check if there is space left
199 // for a new slot with a tree which contains only the item
200 // at the bottom.
201 if (a.table.length < M) {
202 var newSlot = create(item, a.height - 1);
203 var newA = nodeCopy(a);
204 newA.table.push(newSlot);
205 newA.lengths.push(newA.lengths[newA.lengths.length - 1] + length(newSlot));
206 return newA
207 } else {
208 return null;
209 }
210 }
212 // Converts an array into a list of elements.
213 function toList(a) {
214 return toList_(List.Nil, a);
215 }
217 function toList_(list, a) {
218 for (var i = a.table.length - 1; i >= 0; i--) {
219 list = a.height == 0 ? List.Cons(a.table[i], list) : toList_(list, a.table[i]);
220 }
221 return list;
222 }
224 // Maps a function over the elements of an array.
225 function map(f, a) {
226 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
227 if (a.height > 0) { newA.lengths = a.lengths; }
228 for (var i = 0; i < a.table.length; i++) {
229 newA.table[i] = a.height == 0 ? f(a.table[i]) : map(f, a.table[i]);
230 }
231 return newA;
232 }
234 // Maps a function over the elements with their index as first argument.
235 function indexedMap(f, a) {
236 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
237 if (a.height > 0) { newA.lengths = a.lengths; }
238 for (var i = 0; i < a.table.length; i++) {
239 newA.table[i] = a.height == 0 ? A2(f, i, a.table[i]) : indexedMap(f, a.table[i]);
240 }
241 return newA;
242 }
244 function foldl(f, b, a) {
245 for (var i = 0; i < a.table.length; i++) {
246 b = A2(f, a.height == 0 ? a.table[i] : foldl(f, b, a.table[i]), b);
247 }
248 return b;
249 }
251 function foldr(f, b, a) {
252 for (var i = a.table.length; i--; ) {
253 b = A2(f, a.height == 0 ? a.table[i] : foldr(f, b, a.table[i]), b);
254 }
255 return b;
256 }
258 // Returns a sliced tree. "to" is inclusive, but this may change,
259 // when I understand, why e.g. JS does not handle it this way. :-)
260 // If "from" or "to" is negative, they will select from the end on.
261 // TODO: currently, it slices the right, then the left. This can be
262 // optimized.
263 function slice(from, to, a) {
264 if (from < 0) { from += length(a); }
265 if (to < 0) { to += length(a); }
266 return sliceLeft(from, sliceRight(to, a));
267 }
269 function sliceRight(to, a) {
270 if (to == length(a)) {
271 return a;
272 }
274 // Handle leaf level.
275 if (a.height == 0) {
276 var newA = { ctor:"_Array", height:0 };
277 newA.table = a.table.slice(0, to + 1);
278 return newA;
279 }
281 // Slice the right recursively.
282 var right = getSlot(to, a);
283 var sliced = sliceRight(to - (right > 0 ? a.lengths[right - 1] : 0), a.table[right]);
285 // Maybe the a node is not even needed, as sliced contains the whole slice.
286 if (right == 0) {
287 return sliced;
288 }
290 // Create new node.
291 var newA = { ctor:"_Array", height:a.height
292 , table:a.table.slice(0, right + 1)
293 , lengths:a.lengths.slice(0, right + 1) };
294 newA.table[right] = sliced;
295 newA.lengths[right] = length(sliced) + (right > 0 ? newA.lengths[right - 1] : 0);
296 return newA;
297 }
299 function sliceLeft(from, a) {
300 if (from == 0) {
301 return a;
302 }
304 // Handle leaf level.
305 if (a.height == 0) {
306 var newA = { ctor:"_Array", height:0 };
307 newA.table = a.table.slice(from, a.table.length + 1);
308 return newA;
309 }
311 // Slice the left recursively.
312 var left = getSlot(from, a);
313 var sliced = sliceLeft(from - (left > 0 ? a.lengths[left - 1] : 0), a.table[left]);
315 // Maybe the a node is not even needed, as sliced contains the whole slice.
316 if (left == a.table.length - 1) {
317 return sliced;
318 }
320 // Create new node.
321 var newA = { ctor:"_Array", height:a.height
322 , table:a.table.slice(left, a.table.length + 1)
323 , lengths:new Array(a.table.length - left) };
324 newA.table[left] = sliced;
325 var len = 0;
326 for (var i = 0; i < newA.table.length; i++) {
327 len += length(newA.table[i]);
328 newA.lengths[i] = len;
329 }
331 return newA;
332 }
334 // Appends two trees.
335 // TODO: Add support for appending trees of different sizes. Current
336 // behavior will just rise the lower tree and then append them.
337 function append(a,b) {
338 if (b.height > a.height) { return append(parentise(a, b.height), b); }
339 if (a.height > b.height) { return append(a, parentise(b, a.height)); }
340 if (a.height == 0) { return append(parentise(a, 1), parentise(b, 1)); }
342 var c = append_(a, b);
343 if (c[1].table.length > 0) {
344 return siblise(c[0], c[1]);
345 } else {
346 return c[0];
347 }
348 }
350 // Returns an array of two nodes. The second node _may_ be empty. This case
351 // needs to be handled by the function, that called append_. May be only
352 // called for trees with an minimal height of 1.
353 function append_(a, b) {
354 if (a.height == 1) {
355 // Check if balancing is needed and return based on that.
356 var toRemove = calcToRemove(a, b);
357 if (toRemove <= E) {
358 return [a,b];
359 }
361 return shuffle(a, b, toRemove);
362 }
364 var appended = append_(botRight(a), botLeft(b));
365 a = nodeCopy(a), b = nodeCopy(b);
367 // Adjust the bottom right side of the new tree.
368 a.table[a.table.length - 1] = appended[0];
369 a.lengths[a.lengths.length - 1] = length(appended[0])
370 a.lengths[a.lengths.length - 1] += a.lengths.length > 1 ? a.lengths[a.lengths.length - 2] : 0;
372 // Adjust the bottom left side of the new tree.
373 if (appended[1].table.length > 0) {
374 b.table[0] = appended[1];
375 b.lengths[0] = length(appended[1]);
376 for (var i = 1, len = length(b.table[0]); i < b.lengths.length; i++) {
377 len += length(b.table[i]);
378 b.lengths[i] = len;
379 }
380 } else {
381 b.table.shift();
382 for (var i = 1; i < b.lengths.length; i++) {
383 b.lengths[i] = b.lengths[i] - b.lengths[0];
384 }
385 b.lengths.shift();
386 }
388 // Check if balancing is needed and return based on that.
389 var toRemove = calcToRemove(a, b);
390 if (toRemove <= E || b.table.length == 0) {
391 return [a,b];
392 }
394 return shuffle(a, b, toRemove);
395 }
397 // Returns the extra search steps for E. Refer to the paper.
398 function calcToRemove(a, b) {
399 var subLengths = 0;
400 for (var i = 0; i < a.table.length; i++) {
401 subLengths += a.table[i].table.length;
402 }
403 for (var i = 0; i < b.table.length; i++) {
404 subLengths += b.table[i].table.length;
405 }
407 var toRemove = a.table.length + b.table.length
408 return toRemove - (Math.floor((subLengths - 1) / M) + 1);
409 }
411 // get2, set2 and saveSlot are helpers for accessing elements over two arrays.
412 function get2(a, b, index) {
413 return index < a.length ? a[index] : b[index - a.length];
414 }
416 function set2(a, b, index, value) {
417 if (index < a.length) {
418 a[index] = value;
419 } else {
420 b[index - a.length] = value;
421 }
422 }
424 function saveSlot(a, b, index, slot) {
425 set2(a.table, b.table, index, slot);
427 var l = (index == 0 || index == a.lengths.length) ?
428 0 : get2(a.lengths, a.lengths, index - 1);
429 set2(a.lengths, b.lengths, index, l + length(slot));
430 }
432 // Creates a node or leaf with a given length at their arrays for perfomance.
433 // Is only used by shuffle.
434 function createNode(h, length) {
435 if (length < 0) { length = 0; }
436 var a = { ctor:"_Array", height:h, table:new Array(length) };
437 if (h > 0) {
438 a.lengths = new Array(length);
439 }
440 return a;
441 }
443 // Returns an array of two balanced nodes.
444 function shuffle(a, b, toRemove) {
445 var newA = createNode(a.height, Math.min(M, a.table.length + b.table.length - toRemove));
446 var newB = createNode(a.height, newA.table.length - (a.table.length + b.table.length - toRemove));
448 // Skip the slots with size M. More precise: copy the slot references
449 // to the new node
450 var read = 0;
451 while (get2(a.table, b.table, read).table.length % M == 0) {
452 set2(newA.table, newB.table, read, get2(a.table, b.table, read));
453 set2(newA.lengths, newB.lengths, read, get2(a.lengths, b.lengths, read));
454 read++;
455 }
457 // Pulling items from left to right, caching in a slot before writing
458 // it into the new nodes.
459 var write = read;
460 var slot = new createNode(a.height - 1, 0);
461 var from = 0;
463 // If the current slot is still containing data, then there will be at
464 // least one more write, so we do not break this loop yet.
465 while (read - write - (slot.table.length > 0 ? 1 : 0) < toRemove) {
466 // Find out the max possible items for copying.
467 var source = get2(a.table, b.table, read);
468 var to = Math.min(M - slot.table.length, source.table.length)
470 // Copy and adjust size table.
471 slot.table = slot.table.concat(source.table.slice(from, to));
472 if (slot.height > 0) {
473 var len = slot.lengths.length;
474 for (var i = len; i < len + to - from; i++) {
475 slot.lengths[i] = length(slot.table[i]);
476 slot.lengths[i] += (i > 0 ? slot.lengths[i - 1] : 0);
477 }
478 }
480 from += to;
482 // Only proceed to next slots[i] if the current one was
483 // fully copied.
484 if (source.table.length <= to) {
485 read++; from = 0;
486 }
488 // Only create a new slot if the current one is filled up.
489 if (slot.table.length == M) {
490 saveSlot(newA, newB, write, slot);
491 slot = createNode(a.height - 1,0);
492 write++;
493 }
494 }
496 // Cleanup after the loop. Copy the last slot into the new nodes.
497 if (slot.table.length > 0) {
498 saveSlot(newA, newB, write, slot);
499 write++;
500 }
502 // Shift the untouched slots to the left
503 while (read < a.table.length + b.table.length ) {
504 saveSlot(newA, newB, write, get2(a.table, b.table, read));
505 read++; write++;
506 }
508 return [newA, newB];
509 }
511 // Navigation functions
512 function botRight(a) { return a.table[a.table.length - 1]; }
513 function botLeft(a) { return a.table[0]; }
515 // Copies a node for updating. Note that you should not use this if
516 // only updating only one of "table" or "lengths" for performance reasons.
517 function nodeCopy(a) {
518 var newA = { ctor:"_Array", height:a.height
519 , table:a.table.slice() };
520 if (a.height > 0) { newA.lengths = a.lengths.slice(); }
521 return newA;
522 }
524 // Returns how many items are in the tree.
525 function length(array) {
526 if (array.height == 0) {
527 return array.table.length;
528 } else {
529 return array.lengths[array.lengths.length - 1];
530 }
531 }
533 // Calculates in which slot of "table" the item probably is, then
534 // find the exact slot via forward searching in "lengths". Returns the index.
535 function getSlot(i, a) {
536 var slot = Math.floor(i / (Math.pow(M, a.height)));
537 while (a.lengths[slot] <= i) {
538 slot++
539 }
540 return slot;
541 }
543 // Recursively creates a tree with a given height containing
544 // only the given item.
545 function create(item, h) {
546 if (h == 0) {
547 return { ctor:"_Array", height:0
548 , table:[item] };
549 } else {
550 return { ctor:"_Array", height:h
551 , table:[create(item, h - 1)]
552 , lengths:[1] };
553 }
554 }
556 // Recursively creates a tree that contains the given tree.
557 function parentise(tree, h) {
558 if (h == tree.height) {
559 return tree;
560 } else {
561 return { ctor:"_Array", height:h
562 , table:[parentise(tree, h - 1)]
563 , lengths:[length(tree)] };
564 }
565 }
567 // Emphasizes blood brotherhood beneath two trees.
568 function siblise(a, b) {
569 return { ctor:"_Array", height:a.height + 1
570 , table:[a, b]
571 , lengths:[length(a), length(a) + length(b)] };
572 }
574 Elm.Native.Array.values = {
575 empty:empty,
576 fromList:fromList,
577 toList:toList,
578 initialize:F2(initialize),
579 append:F2(append),
580 push:F2(push),
581 slice:F3(slice),
582 get:F2(get),
583 set:F3(set),
584 map:F2(map),
585 indexedMap:F2(indexedMap),
586 foldl:F3(foldl),
587 foldr:F3(foldr),
588 length:length
589 };
591 return elm.Native.Array.values = Elm.Native.Array.values;