git.iko.soy/elk
on 3f23d77 help sign in
elk/libraries/Native/Array.js
490 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 +" on the array is out of range. Check the length first or you safeGet.");
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 elements(a) {
115 return elements_(List.Nil, a);
116 }
118 function elements_(list, a) {
119 for (var i = a.table.length - 1; i >= 0; i--) {
120 list = a.height == 0 ? List.Cons(a.table[i], list) : elements_(list, a.table[i]);
121 }
122 return list;
123 }
125 // Maps a function over 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 function assocMap(f, a) {
136 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
137 if (a.height > 0) { newA.lengths = a.lengths; }
138 for (var i = 0; i < a.table.length; i++) {
139 newA.table[i] = a.height == 0 ? A2(f, i, a.table[i]) : assocMap(f, a.table[i]);
140 }
141 return newA;
142 }
144 function foldl(f, b, a) {
145 for (var i = a.table.length - 1; i >= 0; i--) {
146 b = A2(f, a.height == 0 ? a.table[i] : foldl(f, b, a.table[i]), b);
147 }
148 return b;
149 }
151 function foldr(f, b, a) {
152 for (var i = 0; i < a.table.length; i++) {
153 b = A2(f, a.height == 0 ? a.table[i] : foldr(f, b, a.table[i]), b);
154 }
155 return b;
156 }
158 // Returns a sliced tree. The to is inclusive, but this may change,
159 // when I understand, why e.g. JS does not handle it this way. :-)
160 // If from or to is negative, they will select from the end on.
161 // TODO: currently, it slices the right, then the left. This can be
162 // optimized.
163 function slice(from, to, a) {
164 if (from < 0) { from += length(a); }
165 if (to < 0) { to += length(a); }
166 return sliceLeft(from, sliceRight(to, a));
167 }
169 function sliceRight(to, a) {
170 if (to == length(a)) {
171 return a;
172 }
174 // Handle leaf level.
175 if (a.height == 0) {
176 var newA = { ctor:"_Array", height:0 };
177 newA.table = a.table.slice(0, to + 1);
178 return newA;
179 }
181 // Slice the right recursively.
182 var right = getSlot(to, a);
183 var sliced = sliceRight(to - (right > 0 ? a.lengths[right - 1] : 0), a.table[right]);
185 // Maybe the a node is not even needed, as sliced contains the whole slice.
186 if (right == 0) {
187 return sliced;
188 }
190 // Create new node.
191 var newA = { ctor:"_Array", height:a.height
192 , table:a.table.slice(0, right + 1)
193 , lengths:a.lengths.slice(0, right + 1) };
194 newA.table[right] = sliced;
195 newA.lengths[right] = length(sliced) + (right > 0 ? newA.lengths[right - 1] : 0);
196 return newA;
197 }
199 function sliceLeft(from, a) {
200 if (from == 0) {
201 return a;
202 }
204 // Handle leaf level.
205 if (a.height == 0) {
206 var newA = { ctor:"_Array", height:0 };
207 newA.table = a.table.slice(from, a.table.length + 1);
208 return newA;
209 }
211 // Slice the left recursively.
212 var left = getSlot(from, a);
213 var sliced = sliceLeft(from - (left > 0 ? a.lengths[left - 1] : 0), a.table[left]);
215 // Maybe the a node is not even needed, as sliced contains the whole slice.
216 if (left == a.table.length - 1) {
217 return sliced;
218 }
220 // Create new node.
221 var newA = { ctor:"_Array", height:a.height
222 , table:a.table.slice(left, a.table.length + 1)
223 , lengths:new Array(a.table.length - left) };
224 newA.table[left] = sliced;
225 var len = 0;
226 for (var i = 0; i < newA.table.length; i++) {
227 len += length(newA.table[i]);
228 newA.lengths[i] = len;
229 }
231 return newA;
232 }
234 // Concats two trees.
235 // TODO: Add support for concatting trees of different sizes. Current
236 // behavior will just rise the lower tree and then concat them.
237 function concat(a, b) {
238 if (b.height > a.height) { return concat(parentise(a, b.height), b); }
239 if (a.height > b.height) { return concat(a, parentise(b, a.height)); }
240 if (a.height == 0) { return concat(parentise(a, 1), parentise(b, 1)); }
242 var c = concat_(a, b);
243 if (c[1].table.length > 0) {
244 return siblise(c[0], c[1]);
245 } else {
246 return c[0];
247 }
248 }
250 // Returns an array of two nodes. The second node _may_ be empty. This case
251 // needs to be handled by the function, that called concat_. May be only
252 // called for trees with an minimal height of 1.
253 function concat_(a, b) {
254 if (a.height == 1) {
255 // Check if balancing is needed and return based on that.
256 var toRemove = calcToRemove(a, b);
257 if (toRemove <= E) {
258 return [a,b];
259 }
261 return shuffle(a, b, toRemove);
262 }
264 var concated = concat_(botRight(a), botLeft(b));
265 a = nodeCopy(a), b = nodeCopy(b);
267 // Adjust the bottom right side of the new tree.
268 a.table[a.table.length - 1] = concated[0];
269 a.lengths[a.lengths.length - 1] = length(concated[0])
270 a.lengths[a.lengths.length - 1] += a.lengths.length > 1 ? a.lengths[a.lengths.length - 2] : 0;
272 // Adjust the bottom left side of the new tree.
273 if (concated[1].table.length > 0) {
274 b.table[0] = concated[1];
275 b.lengths[0] = length(concated[1]);
276 for (var i = 1, len = length(b.table[0]); i < b.lengths.length; i++) {
277 len += length(b.table[i]);
278 b.lengths[i] = len;
279 }
280 } else {
281 b.table.shift();
282 for (var i = 1; i < b.lengths.length; i++) {
283 b.lengths[i] = b.lengths[i] - b.lengths[0];
284 }
285 b.lengths.shift();
286 }
288 // Check if balancing is needed and return based on that.
289 var toRemove = calcToRemove(a, b);
290 if (toRemove <= E || b.table.length == 0) {
291 return [a,b];
292 }
294 return shuffle(a, b, toRemove);
295 }
297 // Returns the extra search steps for E. Refer to the paper.
298 function calcToRemove(a, b) {
299 var subLengths = 0;
300 for (var i = 0; i < a.table.length; i++) {
301 subLengths += a.table[i].table.length;
302 }
303 for (var i = 0; i < b.table.length; i++) {
304 subLengths += b.table[i].table.length;
305 }
307 var toRemove = a.table.length + b.table.length
308 return toRemove - (Math.floor((subLengths - 1) / M) + 1);
309 }
311 // get2 and set2 are helpers for accessing over two arrays.
312 function get2(a, b, index) {
313 return index < a.length ? a[index] : b[index - a.length];
314 }
316 function set2(a, b, index, value) {
317 if (index < a.length) {
318 a[index] = value;
319 } else {
320 b[index - a.length] = value;
321 }
322 }
324 // Creates a node or leaf with a given length at their arrays for perfomance.
325 // Is only used by shuffle.
326 function createNode(h, length) {
327 if (length < 0) { length = 0; }
328 var a = { ctor:"_Array", height:h, table:new Array(length) };
329 if (h > 0) {
330 a.lengths = new Array(length);
331 }
332 return a;
333 }
335 function saveSlot(a, b, index, slot) {
336 set2(a.table, b.table, index, slot);
338 var l = (index == 0 || index == a.lengths.length) ?
339 0 : get2(a.lengths, a.lengths, index - 1);
340 set2(a.lengths, b.lengths, index, l + length(slot));
341 }
343 // Returns an array of two balanced nodes.
344 function shuffle(a, b, toRemove) {
345 var newA = createNode(a.height, Math.min(M, a.table.length + b.table.length - toRemove));
346 var newB = createNode(a.height, newA.table.length - (a.table.length + b.table.length - toRemove));
348 // Skip the slots with size M. More precise: copy the slot references
349 // to the new node
350 var read = 0;
351 while (get2(a.table, b.table, read).table.length % M == 0) {
352 set2(newA.table, newB.table, read, get2(a.table, b.table, read));
353 set2(newA.lengths, newB.lengths, read, get2(a.lengths, b.lengths, read));
354 read++;
355 }
357 // Pulling items from left to right, caching in a slot before writing
358 // it into the new nodes.
359 var write = read;
360 var slot = new createNode(a.height - 1, 0);
361 var from = 0;
363 // If the current slot is still containing data, then there will be at
364 // least one more write, so we do not break this loop yet.
365 while (read - write - (slot.table.length > 0 ? 1 : 0) < toRemove) {
366 // Find out the max possible items for copying.
367 var source = get2(a.table, b.table, read);
368 var to = Math.min(M - slot.table.length, source.table.length)
370 // Copy and adjust size table.
371 slot.table = slot.table.concat(source.table.slice(from, to));
372 if (slot.height > 0) {
373 var len = slot.lengths.length;
374 for (var i = len; i < len + to - from; i++) {
375 slot.lengths[i] = length(slot.table[i]);
376 slot.lengths[i] += (i > 0 ? slot.lengths[i - 1] : 0);
377 }
378 }
380 from += to;
382 // Only proceed to next slots[i] if the current one was
383 // fully copied.
384 if (source.table.length <= to) {
385 read++; from = 0;
386 }
388 // Only create a new slot if the current one is filled up.
389 if (slot.table.length == M) {
390 saveSlot(newA, newB, write, slot);
391 slot = createNode(a.height - 1,0);
392 write++;
393 }
394 }
396 // Cleanup after the loop. Copy the last slot into the new nodes.
397 if (slot.table.length > 0) {
398 saveSlot(newA, newB, write, slot);
399 write++;
400 }
402 // Shift the untouched slots to the left
403 while (read < a.table.length + b.table.length ) {
404 saveSlot(newA, newB, write, get2(a.table, b.table, read));
405 read++; write++;
406 }
408 return [newA, newB];
409 }
411 // Navigation functions
412 function botRight(a) { return a.table[a.table.length - 1]; }
413 function botLeft(a) { return a.table[0]; }
415 // Copies a node for updating. Note that you should not use this if
416 // only updating only one of "table" or "lengths" for performance reasons.
417 function nodeCopy(a) {
418 var newA = { ctor:"_Array", height:a.height
419 , table:a.table.slice() };
420 if (a.height > 0) { newA.lengths = a.lengths.slice(); }
421 return newA;
422 }
424 // Returns how many items are in the tree.
425 function length(a) {
426 if (a.height == 0) {
427 return a.table.length;
428 } else {
429 return a.lengths[a.lengths.length - 1];
430 }
431 }
433 // Calculates in which slot the item probably is, then
434 // find the exact slot in "lengths". Returns the index.
435 function getSlot(i, a) {
436 var slot = Math.floor(i / (Math.pow(M, a.height)));
437 while (a.lengths[slot] <= i) {
438 slot++
439 }
440 return slot;
441 }
443 // Recursively creates a tree with a given height containing
444 // only the given item.
445 function create(item, h) {
446 if (h == 0) {
447 return { ctor:"_Array", height:0
448 , table:[item] };
449 } else {
450 return { ctor:"_Array", height:h
451 , table:[create(item, h - 1)]
452 , lengths:[1] };
453 }
454 }
456 // Recursively creates a tree that contains the given tree.
457 function parentise(tree, h) {
458 if (h == tree.height) {
459 return tree;
460 } else {
461 return { ctor:"_Array", height:h
462 , table:[parentise(tree, h - 1)]
463 , lengths:[length(tree)] };
464 }
465 }
467 // Emphasizes blood brotherhood beneath two trees.
468 function siblise(a, b) {
469 return { ctor:"_Array", height:a.height + 1
470 , table:[a, b]
471 , lengths:[length(a), length(a) + length(b)] };
472 }
474 Elm.Native.Array.values = {
475 empty:empty,
476 elements:elements,
477 concat:F2(concat),
478 push:F2(push),
479 slice:F3(slice),
480 get:F2(get),
481 set:F3(set),
482 map:F2(map),
483 assocMap:F2(assocMap),
484 foldl:F3(foldl),
485 foldr:F3(foldr),
486 length:length
487 };
489 return elm.Native.Array.values = Elm.Native.Array.values;