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