git.iko.soy/elk
on a7be9f7 help sign in
elk/libraries/Native/Array.js
491 lines 16 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, a) {
29 if (a.height == 0) {
30 if (i < a.table.length) {
31 return a.table[i];
32 } else {
33 throw new Error("Index "+ i +" is out of range. Check the length of your array first or use getSafe or getMaybe.");
34 }
35 }
37 var slot = getSlot(i, a);
38 var sub = slot > 0 ? a.lengths[slot-1] : 0;
39 return get(i - sub, a.table[slot]);
40 }
42 // Sets the value at the index i. Only the nodes leading to i will get
43 // copied and updated.
44 function set(i, item, a) {
45 if (length(a) <= i) {
46 return a;
47 }
48 var newA = nodeCopy(a);
49 newA.table = a.table.slice();
51 if (a.height == 0) {
52 newA.table[i] = item;
53 } else {
54 var slot = getSlot(i, a);
55 var sub = slot > 0 ? a.lengths[slot-1] : 0;
56 newA.table[slot] = set(i - sub, item, a.table[slot]);
57 }
58 return newA;
59 }
61 // Pushes an item via push_ to the bottom right of a tree.
62 function push(item, a) {
63 var pushed = push_(item, a);
64 if (pushed !== null) {
65 return pushed;
66 }
68 newTree = create(item, a.height);
69 return siblise(a, newTree);
70 }
72 // Recursively tries to push an item to the bottom-right most
73 // tree possible. If there is no space left for the item,
74 // null will be returned.
75 function push_(item, a) {
76 // Handle resursion stop at leaf level.
77 if (a.height == 0) {
78 if (a.table.length < M) {
79 var newA = { ctor:"_Array", height:0, table:a.table.slice() };
80 newA.table.push(item);
81 return newA;
82 } else {
83 return null;
84 }
85 }
87 // Recursively push
88 var pushed = push_(item, botRight(a));
90 // There was space in the bottom right tree, so the slot will
91 // be updated.
92 if (pushed != null) {
93 var newA = nodeCopy(a);
94 newA.table[newA.table.length - 1] = pushed;
95 newA.lengths[newA.lengths.length - 1]++;
96 return newA
97 }
99 // When there was no space left, check if there is space left
100 // for a new slot with a tree which contains only the item
101 // at the bottom.
102 if (a.table.length < M) {
103 var newSlot = create(item, a.height - 1);
104 var newA = nodeCopy(a);
105 newA.table.push(newSlot);
106 newA.lengths.push(newA.lengths[newA.lengths.length - 1] + length(newSlot));
107 return newA
108 } else {
109 return null;
110 }
111 }
113 // Converts an array into a list of elements.
114 function toList(a) {
115 return toList_(List.Nil, a);
116 }
118 function toList_(list, a) {
119 for (var i = a.table.length - 1; i >= 0; i--) {
120 list = a.height == 0 ? List.Cons(a.table[i], list) : toList_(list, a.table[i]);
121 }
122 return list;
123 }
125 // Maps a function over the elements of an array.
126 function map(f, a) {
127 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
128 if (a.height > 0) { newA.lengths = a.lengths; }
129 for (var i = 0; i < a.table.length; i++) {
130 newA.table[i] = a.height == 0 ? f(a.table[i]) : map(f, a.table[i]);
131 }
132 return newA;
133 }
135 // Maps a function over the elements with their index as first argument.
136 function indexedMap(f, a) {
137 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
138 if (a.height > 0) { newA.lengths = a.lengths; }
139 for (var i = 0; i < a.table.length; i++) {
140 newA.table[i] = a.height == 0 ? A2(f, i, a.table[i]) : indexedMap(f, a.table[i]);
141 }
142 return newA;
143 }
145 function foldl(f, b, a) {
146 for (var i = a.table.length - 1; i >= 0; i--) {
147 b = A2(f, a.height == 0 ? a.table[i] : foldl(f, b, a.table[i]), b);
148 }
149 return b;
150 }
152 function foldr(f, b, a) {
153 for (var i = 0; i < a.table.length; i++) {
154 b = A2(f, a.height == 0 ? a.table[i] : foldr(f, b, a.table[i]), b);
155 }
156 return b;
157 }
159 // Returns a sliced tree. "to" is inclusive, but this may change,
160 // when I understand, why e.g. JS does not handle it this way. :-)
161 // If "from" or "to" is negative, they will select from the end on.
162 // TODO: currently, it slices the right, then the left. This can be
163 // optimized.
164 function slice(from, to, a) {
165 if (from < 0) { from += length(a); }
166 if (to < 0) { to += length(a); }
167 return sliceLeft(from, sliceRight(to, a));
168 }
170 function sliceRight(to, a) {
171 if (to == length(a)) {
172 return a;
173 }
175 // Handle leaf level.
176 if (a.height == 0) {
177 var newA = { ctor:"_Array", height:0 };
178 newA.table = a.table.slice(0, to + 1);
179 return newA;
180 }
182 // Slice the right recursively.
183 var right = getSlot(to, a);
184 var sliced = sliceRight(to - (right > 0 ? a.lengths[right - 1] : 0), a.table[right]);
186 // Maybe the a node is not even needed, as sliced contains the whole slice.
187 if (right == 0) {
188 return sliced;
189 }
191 // Create new node.
192 var newA = { ctor:"_Array", height:a.height
193 , table:a.table.slice(0, right + 1)
194 , lengths:a.lengths.slice(0, right + 1) };
195 newA.table[right] = sliced;
196 newA.lengths[right] = length(sliced) + (right > 0 ? newA.lengths[right - 1] : 0);
197 return newA;
198 }
200 function sliceLeft(from, a) {
201 if (from == 0) {
202 return a;
203 }
205 // Handle leaf level.
206 if (a.height == 0) {
207 var newA = { ctor:"_Array", height:0 };
208 newA.table = a.table.slice(from, a.table.length + 1);
209 return newA;
210 }
212 // Slice the left recursively.
213 var left = getSlot(from, a);
214 var sliced = sliceLeft(from - (left > 0 ? a.lengths[left - 1] : 0), a.table[left]);
216 // Maybe the a node is not even needed, as sliced contains the whole slice.
217 if (left == a.table.length - 1) {
218 return sliced;
219 }
221 // Create new node.
222 var newA = { ctor:"_Array", height:a.height
223 , table:a.table.slice(left, a.table.length + 1)
224 , lengths:new Array(a.table.length - left) };
225 newA.table[left] = sliced;
226 var len = 0;
227 for (var i = 0; i < newA.table.length; i++) {
228 len += length(newA.table[i]);
229 newA.lengths[i] = len;
230 }
232 return newA;
233 }
235 // Concats two trees.
236 // TODO: Add support for concatting trees of different sizes. Current
237 // behavior will just rise the lower tree and then concat them.
238 function concat(a, b) {
239 if (b.height > a.height) { return concat(parentise(a, b.height), b); }
240 if (a.height > b.height) { return concat(a, parentise(b, a.height)); }
241 if (a.height == 0) { return concat(parentise(a, 1), parentise(b, 1)); }
243 var c = concat_(a, b);
244 if (c[1].table.length > 0) {
245 return siblise(c[0], c[1]);
246 } else {
247 return c[0];
248 }
249 }
251 // Returns an array of two nodes. The second node _may_ be empty. This case
252 // needs to be handled by the function, that called concat_. May be only
253 // called for trees with an minimal height of 1.
254 function concat_(a, b) {
255 if (a.height == 1) {
256 // Check if balancing is needed and return based on that.
257 var toRemove = calcToRemove(a, b);
258 if (toRemove <= E) {
259 return [a,b];
260 }
262 return shuffle(a, b, toRemove);
263 }
265 var concated = concat_(botRight(a), botLeft(b));
266 a = nodeCopy(a), b = nodeCopy(b);
268 // Adjust the bottom right side of the new tree.
269 a.table[a.table.length - 1] = concated[0];
270 a.lengths[a.lengths.length - 1] = length(concated[0])
271 a.lengths[a.lengths.length - 1] += a.lengths.length > 1 ? a.lengths[a.lengths.length - 2] : 0;
273 // Adjust the bottom left side of the new tree.
274 if (concated[1].table.length > 0) {
275 b.table[0] = concated[1];
276 b.lengths[0] = length(concated[1]);
277 for (var i = 1, len = length(b.table[0]); i < b.lengths.length; i++) {
278 len += length(b.table[i]);
279 b.lengths[i] = len;
280 }
281 } else {
282 b.table.shift();
283 for (var i = 1; i < b.lengths.length; i++) {
284 b.lengths[i] = b.lengths[i] - b.lengths[0];
285 }
286 b.lengths.shift();
287 }
289 // Check if balancing is needed and return based on that.
290 var toRemove = calcToRemove(a, b);
291 if (toRemove <= E || b.table.length == 0) {
292 return [a,b];
293 }
295 return shuffle(a, b, toRemove);
296 }
298 // Returns the extra search steps for E. Refer to the paper.
299 function calcToRemove(a, b) {
300 var subLengths = 0;
301 for (var i = 0; i < a.table.length; i++) {
302 subLengths += a.table[i].table.length;
303 }
304 for (var i = 0; i < b.table.length; i++) {
305 subLengths += b.table[i].table.length;
306 }
308 var toRemove = a.table.length + b.table.length
309 return toRemove - (Math.floor((subLengths - 1) / M) + 1);
310 }
312 // get2, set2 and saveSlot are helpers for accessing elements over two arrays.
313 function get2(a, b, index) {
314 return index < a.length ? a[index] : b[index - a.length];
315 }
317 function set2(a, b, index, value) {
318 if (index < a.length) {
319 a[index] = value;
320 } else {
321 b[index - a.length] = value;
322 }
323 }
325 function saveSlot(a, b, index, slot) {
326 set2(a.table, b.table, index, slot);
328 var l = (index == 0 || index == a.lengths.length) ?
329 0 : get2(a.lengths, a.lengths, index - 1);
330 set2(a.lengths, b.lengths, index, l + length(slot));
331 }
333 // Creates a node or leaf with a given length at their arrays for perfomance.
334 // Is only used by shuffle.
335 function createNode(h, length) {
336 if (length < 0) { length = 0; }
337 var a = { ctor:"_Array", height:h, table:new Array(length) };
338 if (h > 0) {
339 a.lengths = new Array(length);
340 }
341 return a;
342 }
344 // Returns an array of two balanced nodes.
345 function shuffle(a, b, toRemove) {
346 var newA = createNode(a.height, Math.min(M, a.table.length + b.table.length - toRemove));
347 var newB = createNode(a.height, newA.table.length - (a.table.length + b.table.length - toRemove));
349 // Skip the slots with size M. More precise: copy the slot references
350 // to the new node
351 var read = 0;
352 while (get2(a.table, b.table, read).table.length % M == 0) {
353 set2(newA.table, newB.table, read, get2(a.table, b.table, read));
354 set2(newA.lengths, newB.lengths, read, get2(a.lengths, b.lengths, read));
355 read++;
356 }
358 // Pulling items from left to right, caching in a slot before writing
359 // it into the new nodes.
360 var write = read;
361 var slot = new createNode(a.height - 1, 0);
362 var from = 0;
364 // If the current slot is still containing data, then there will be at
365 // least one more write, so we do not break this loop yet.
366 while (read - write - (slot.table.length > 0 ? 1 : 0) < toRemove) {
367 // Find out the max possible items for copying.
368 var source = get2(a.table, b.table, read);
369 var to = Math.min(M - slot.table.length, source.table.length)
371 // Copy and adjust size table.
372 slot.table = slot.table.concat(source.table.slice(from, to));
373 if (slot.height > 0) {
374 var len = slot.lengths.length;
375 for (var i = len; i < len + to - from; i++) {
376 slot.lengths[i] = length(slot.table[i]);
377 slot.lengths[i] += (i > 0 ? slot.lengths[i - 1] : 0);
378 }
379 }
381 from += to;
383 // Only proceed to next slots[i] if the current one was
384 // fully copied.
385 if (source.table.length <= to) {
386 read++; from = 0;
387 }
389 // Only create a new slot if the current one is filled up.
390 if (slot.table.length == M) {
391 saveSlot(newA, newB, write, slot);
392 slot = createNode(a.height - 1,0);
393 write++;
394 }
395 }
397 // Cleanup after the loop. Copy the last slot into the new nodes.
398 if (slot.table.length > 0) {
399 saveSlot(newA, newB, write, slot);
400 write++;
401 }
403 // Shift the untouched slots to the left
404 while (read < a.table.length + b.table.length ) {
405 saveSlot(newA, newB, write, get2(a.table, b.table, read));
406 read++; write++;
407 }
409 return [newA, newB];
410 }
412 // Navigation functions
413 function botRight(a) { return a.table[a.table.length - 1]; }
414 function botLeft(a) { return a.table[0]; }
416 // Copies a node for updating. Note that you should not use this if
417 // only updating only one of "table" or "lengths" for performance reasons.
418 function nodeCopy(a) {
419 var newA = { ctor:"_Array", height:a.height
420 , table:a.table.slice() };
421 if (a.height > 0) { newA.lengths = a.lengths.slice(); }
422 return newA;
423 }
425 // Returns how many items are in the tree.
426 function length(a) {
427 if (a.height == 0) {
428 return a.table.length;
429 } else {
430 return a.lengths[a.lengths.length - 1];
431 }
432 }
434 // Calculates in which slot of "table" the item probably is, then
435 // find the exact slot via forward searching in "lengths". Returns the index.
436 function getSlot(i, a) {
437 var slot = Math.floor(i / (Math.pow(M, a.height)));
438 while (a.lengths[slot] <= i) {
439 slot++
440 }
441 return slot;
442 }
444 // Recursively creates a tree with a given height containing
445 // only the given item.
446 function create(item, h) {
447 if (h == 0) {
448 return { ctor:"_Array", height:0
449 , table:[item] };
450 } else {
451 return { ctor:"_Array", height:h
452 , table:[create(item, h - 1)]
453 , lengths:[1] };
454 }
455 }
457 // Recursively creates a tree that contains the given tree.
458 function parentise(tree, h) {
459 if (h == tree.height) {
460 return tree;
461 } else {
462 return { ctor:"_Array", height:h
463 , table:[parentise(tree, h - 1)]
464 , lengths:[length(tree)] };
465 }
466 }
468 // Emphasizes blood brotherhood beneath two trees.
469 function siblise(a, b) {
470 return { ctor:"_Array", height:a.height + 1
471 , table:[a, b]
472 , lengths:[length(a), length(a) + length(b)] };
473 }
475 Elm.Native.Array.values = {
476 empty:empty,
477 toList:toList,
478 concat:F2(concat),
479 push:F2(push),
480 slice:F3(slice),
481 get:F2(get),
482 set:F3(set),
483 map:F2(map),
484 indexedMap:F2(indexedMap),
485 foldl:F3(foldl),
486 foldr:F3(foldr),
487 length:length
488 };
490 return elm.Native.Array.values = Elm.Native.Array.values;