git.iko.soy/elk
on ef6a2d6 help sign in
elk/libraries/Native/Array.js
494 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, 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 // Pushes an item via push_ to the bottom right of a tree.
65 function push(item, a) {
66 var pushed = push_(item, a);
67 if (pushed !== null) {
68 return pushed;
69 }
71 var newTree = create(item, a.height);
72 return siblise(a, newTree);
73 }
75 // Recursively tries to push an item to the bottom-right most
76 // tree possible. If there is no space left for the item,
77 // null will be returned.
78 function push_(item, a) {
79 // Handle resursion stop at leaf level.
80 if (a.height == 0) {
81 if (a.table.length < M) {
82 var newA = { ctor:"_Array", height:0, table:a.table.slice() };
83 newA.table.push(item);
84 return newA;
85 } else {
86 return null;
87 }
88 }
90 // Recursively push
91 var pushed = push_(item, botRight(a));
93 // There was space in the bottom right tree, so the slot will
94 // be updated.
95 if (pushed != null) {
96 var newA = nodeCopy(a);
97 newA.table[newA.table.length - 1] = pushed;
98 newA.lengths[newA.lengths.length - 1]++;
99 return newA
100 }
102 // When there was no space left, check if there is space left
103 // for a new slot with a tree which contains only the item
104 // at the bottom.
105 if (a.table.length < M) {
106 var newSlot = create(item, a.height - 1);
107 var newA = nodeCopy(a);
108 newA.table.push(newSlot);
109 newA.lengths.push(newA.lengths[newA.lengths.length - 1] + length(newSlot));
110 return newA
111 } else {
112 return null;
113 }
114 }
116 // Converts an array into a list of elements.
117 function toList(a) {
118 return toList_(List.Nil, a);
119 }
121 function toList_(list, a) {
122 for (var i = a.table.length - 1; i >= 0; i--) {
123 list = a.height == 0 ? List.Cons(a.table[i], list) : toList_(list, a.table[i]);
124 }
125 return list;
126 }
128 // Maps a function over the elements of an array.
129 function map(f, a) {
130 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
131 if (a.height > 0) { newA.lengths = a.lengths; }
132 for (var i = 0; i < a.table.length; i++) {
133 newA.table[i] = a.height == 0 ? f(a.table[i]) : map(f, a.table[i]);
134 }
135 return newA;
136 }
138 // Maps a function over the elements with their index as first argument.
139 function indexedMap(f, a) {
140 var newA = { ctor:"_Array", height:a.height, table:new Array(a.table) };
141 if (a.height > 0) { newA.lengths = a.lengths; }
142 for (var i = 0; i < a.table.length; i++) {
143 newA.table[i] = a.height == 0 ? A2(f, i, a.table[i]) : indexedMap(f, a.table[i]);
144 }
145 return newA;
146 }
148 function foldl(f, b, a) {
149 for (var i = a.table.length - 1; i >= 0; i--) {
150 b = A2(f, a.height == 0 ? a.table[i] : foldl(f, b, a.table[i]), b);
151 }
152 return b;
153 }
155 function foldr(f, b, a) {
156 for (var i = 0; i < a.table.length; i++) {
157 b = A2(f, a.height == 0 ? a.table[i] : foldr(f, b, a.table[i]), b);
158 }
159 return b;
160 }
162 // Returns a sliced tree. "to" is inclusive, but this may change,
163 // when I understand, why e.g. JS does not handle it this way. :-)
164 // If "from" or "to" is negative, they will select from the end on.
165 // TODO: currently, it slices the right, then the left. This can be
166 // optimized.
167 function slice(from, to, a) {
168 if (from < 0) { from += length(a); }
169 if (to < 0) { to += length(a); }
170 return sliceLeft(from, sliceRight(to, a));
171 }
173 function sliceRight(to, a) {
174 if (to == length(a)) {
175 return a;
176 }
178 // Handle leaf level.
179 if (a.height == 0) {
180 var newA = { ctor:"_Array", height:0 };
181 newA.table = a.table.slice(0, to + 1);
182 return newA;
183 }
185 // Slice the right recursively.
186 var right = getSlot(to, a);
187 var sliced = sliceRight(to - (right > 0 ? a.lengths[right - 1] : 0), a.table[right]);
189 // Maybe the a node is not even needed, as sliced contains the whole slice.
190 if (right == 0) {
191 return sliced;
192 }
194 // Create new node.
195 var newA = { ctor:"_Array", height:a.height
196 , table:a.table.slice(0, right + 1)
197 , lengths:a.lengths.slice(0, right + 1) };
198 newA.table[right] = sliced;
199 newA.lengths[right] = length(sliced) + (right > 0 ? newA.lengths[right - 1] : 0);
200 return newA;
201 }
203 function sliceLeft(from, a) {
204 if (from == 0) {
205 return a;
206 }
208 // Handle leaf level.
209 if (a.height == 0) {
210 var newA = { ctor:"_Array", height:0 };
211 newA.table = a.table.slice(from, a.table.length + 1);
212 return newA;
213 }
215 // Slice the left recursively.
216 var left = getSlot(from, a);
217 var sliced = sliceLeft(from - (left > 0 ? a.lengths[left - 1] : 0), a.table[left]);
219 // Maybe the a node is not even needed, as sliced contains the whole slice.
220 if (left == a.table.length - 1) {
221 return sliced;
222 }
224 // Create new node.
225 var newA = { ctor:"_Array", height:a.height
226 , table:a.table.slice(left, a.table.length + 1)
227 , lengths:new Array(a.table.length - left) };
228 newA.table[left] = sliced;
229 var len = 0;
230 for (var i = 0; i < newA.table.length; i++) {
231 len += length(newA.table[i]);
232 newA.lengths[i] = len;
233 }
235 return newA;
236 }
238 // Appends two trees.
239 // TODO: Add support for appending trees of different sizes. Current
240 // behavior will just rise the lower tree and then append them.
241 function append(a,b) {
242 if (b.height > a.height) { return append(parentise(a, b.height), b); }
243 if (a.height > b.height) { return append(a, parentise(b, a.height)); }
244 if (a.height == 0) { return append(parentise(a, 1), parentise(b, 1)); }
246 var c = append_(a, b);
247 if (c[1].table.length > 0) {
248 return siblise(c[0], c[1]);
249 } else {
250 return c[0];
251 }
252 }
254 // Returns an array of two nodes. The second node _may_ be empty. This case
255 // needs to be handled by the function, that called append_. May be only
256 // called for trees with an minimal height of 1.
257 function append_(a, b) {
258 if (a.height == 1) {
259 // Check if balancing is needed and return based on that.
260 var toRemove = calcToRemove(a, b);
261 if (toRemove <= E) {
262 return [a,b];
263 }
265 return shuffle(a, b, toRemove);
266 }
268 var appended = append_(botRight(a), botLeft(b));
269 a = nodeCopy(a), b = nodeCopy(b);
271 // Adjust the bottom right side of the new tree.
272 a.table[a.table.length - 1] = appended[0];
273 a.lengths[a.lengths.length - 1] = length(appended[0])
274 a.lengths[a.lengths.length - 1] += a.lengths.length > 1 ? a.lengths[a.lengths.length - 2] : 0;
276 // Adjust the bottom left side of the new tree.
277 if (appended[1].table.length > 0) {
278 b.table[0] = appended[1];
279 b.lengths[0] = length(appended[1]);
280 for (var i = 1, len = length(b.table[0]); i < b.lengths.length; i++) {
281 len += length(b.table[i]);
282 b.lengths[i] = len;
283 }
284 } else {
285 b.table.shift();
286 for (var i = 1; i < b.lengths.length; i++) {
287 b.lengths[i] = b.lengths[i] - b.lengths[0];
288 }
289 b.lengths.shift();
290 }
292 // Check if balancing is needed and return based on that.
293 var toRemove = calcToRemove(a, b);
294 if (toRemove <= E || b.table.length == 0) {
295 return [a,b];
296 }
298 return shuffle(a, b, toRemove);
299 }
301 // Returns the extra search steps for E. Refer to the paper.
302 function calcToRemove(a, b) {
303 var subLengths = 0;
304 for (var i = 0; i < a.table.length; i++) {
305 subLengths += a.table[i].table.length;
306 }
307 for (var i = 0; i < b.table.length; i++) {
308 subLengths += b.table[i].table.length;
309 }
311 var toRemove = a.table.length + b.table.length
312 return toRemove - (Math.floor((subLengths - 1) / M) + 1);
313 }
315 // get2, set2 and saveSlot are helpers for accessing elements over two arrays.
316 function get2(a, b, index) {
317 return index < a.length ? a[index] : b[index - a.length];
318 }
320 function set2(a, b, index, value) {
321 if (index < a.length) {
322 a[index] = value;
323 } else {
324 b[index - a.length] = value;
325 }
326 }
328 function saveSlot(a, b, index, slot) {
329 set2(a.table, b.table, index, slot);
331 var l = (index == 0 || index == a.lengths.length) ?
332 0 : get2(a.lengths, a.lengths, index - 1);
333 set2(a.lengths, b.lengths, index, l + length(slot));
334 }
336 // Creates a node or leaf with a given length at their arrays for perfomance.
337 // Is only used by shuffle.
338 function createNode(h, length) {
339 if (length < 0) { length = 0; }
340 var a = { ctor:"_Array", height:h, table:new Array(length) };
341 if (h > 0) {
342 a.lengths = new Array(length);
343 }
344 return a;
345 }
347 // Returns an array of two balanced nodes.
348 function shuffle(a, b, toRemove) {
349 var newA = createNode(a.height, Math.min(M, a.table.length + b.table.length - toRemove));
350 var newB = createNode(a.height, newA.table.length - (a.table.length + b.table.length - toRemove));
352 // Skip the slots with size M. More precise: copy the slot references
353 // to the new node
354 var read = 0;
355 while (get2(a.table, b.table, read).table.length % M == 0) {
356 set2(newA.table, newB.table, read, get2(a.table, b.table, read));
357 set2(newA.lengths, newB.lengths, read, get2(a.lengths, b.lengths, read));
358 read++;
359 }
361 // Pulling items from left to right, caching in a slot before writing
362 // it into the new nodes.
363 var write = read;
364 var slot = new createNode(a.height - 1, 0);
365 var from = 0;
367 // If the current slot is still containing data, then there will be at
368 // least one more write, so we do not break this loop yet.
369 while (read - write - (slot.table.length > 0 ? 1 : 0) < toRemove) {
370 // Find out the max possible items for copying.
371 var source = get2(a.table, b.table, read);
372 var to = Math.min(M - slot.table.length, source.table.length)
374 // Copy and adjust size table.
375 slot.table = slot.table.concat(source.table.slice(from, to));
376 if (slot.height > 0) {
377 var len = slot.lengths.length;
378 for (var i = len; i < len + to - from; i++) {
379 slot.lengths[i] = length(slot.table[i]);
380 slot.lengths[i] += (i > 0 ? slot.lengths[i - 1] : 0);
381 }
382 }
384 from += to;
386 // Only proceed to next slots[i] if the current one was
387 // fully copied.
388 if (source.table.length <= to) {
389 read++; from = 0;
390 }
392 // Only create a new slot if the current one is filled up.
393 if (slot.table.length == M) {
394 saveSlot(newA, newB, write, slot);
395 slot = createNode(a.height - 1,0);
396 write++;
397 }
398 }
400 // Cleanup after the loop. Copy the last slot into the new nodes.
401 if (slot.table.length > 0) {
402 saveSlot(newA, newB, write, slot);
403 write++;
404 }
406 // Shift the untouched slots to the left
407 while (read < a.table.length + b.table.length ) {
408 saveSlot(newA, newB, write, get2(a.table, b.table, read));
409 read++; write++;
410 }
412 return [newA, newB];
413 }
415 // Navigation functions
416 function botRight(a) { return a.table[a.table.length - 1]; }
417 function botLeft(a) { return a.table[0]; }
419 // Copies a node for updating. Note that you should not use this if
420 // only updating only one of "table" or "lengths" for performance reasons.
421 function nodeCopy(a) {
422 var newA = { ctor:"_Array", height:a.height
423 , table:a.table.slice() };
424 if (a.height > 0) { newA.lengths = a.lengths.slice(); }
425 return newA;
426 }
428 // Returns how many items are in the tree.
429 function length(array) {
430 if (array.height == 0) {
431 return array.table.length;
432 } else {
433 return array.lengths[array.lengths.length - 1];
434 }
435 }
437 // Calculates in which slot of "table" the item probably is, then
438 // find the exact slot via forward searching in "lengths". Returns the index.
439 function getSlot(i, a) {
440 var slot = Math.floor(i / (Math.pow(M, a.height)));
441 while (a.lengths[slot] <= i) {
442 slot++
443 }
444 return slot;
445 }
447 // Recursively creates a tree with a given height containing
448 // only the given item.
449 function create(item, h) {
450 if (h == 0) {
451 return { ctor:"_Array", height:0
452 , table:[item] };
453 } else {
454 return { ctor:"_Array", height:h
455 , table:[create(item, h - 1)]
456 , lengths:[1] };
457 }
458 }
460 // Recursively creates a tree that contains the given tree.
461 function parentise(tree, h) {
462 if (h == tree.height) {
463 return tree;
464 } else {
465 return { ctor:"_Array", height:h
466 , table:[parentise(tree, h - 1)]
467 , lengths:[length(tree)] };
468 }
469 }
471 // Emphasizes blood brotherhood beneath two trees.
472 function siblise(a, b) {
473 return { ctor:"_Array", height:a.height + 1
474 , table:[a, b]
475 , lengths:[length(a), length(a) + length(b)] };
476 }
478 Elm.Native.Array.values = {
479 empty:empty,
480 toList:toList,
481 append:F2(append),
482 push:F2(push),
483 slice:F3(slice),
484 get:F2(get),
485 set:F3(set),
486 map:F2(map),
487 indexedMap:F2(indexedMap),
488 foldl:F3(foldl),
489 foldr:F3(foldr),
490 length:length
491 };
493 return elm.Native.Array.values = Elm.Native.Array.values;