1//////////////////////////////////////////////////////////////////////
2// LibFile: lists.scad
3// Functions for operating on generic lists. Provides functiosn for indexing lists, changing list
4// structure, and constructing lists by rearranging or modifying another list.
5// Includes:
6// include <BOSL2/std.scad>
7// FileGroup: Data Management
8// FileSummary: List indexing, change list structure, rearrange/modify lists
9// FileFootnotes: STD=Included in std.scad
10//////////////////////////////////////////////////////////////////////
11
12// Terminology:
13// **List** = An ordered collection of zero or more arbitrary items. ie: `["a", "b", "c"]`, or `[3, "a", [4,5]]`
14// **Vector** = A list of numbers. ie: `[4, 5, 6]`
15// **Set** = A list of unique items.
16
17// Section: List Query Operations
18
19// Function: is_homogeneous()
20// Alias: is_homogenous()
21// Usage:
22// bool = is_homogeneous(list, [depth]);
23// Topics: List Handling, Type Checking
24// See Also: is_vector(), is_matrix()
25// Description:
26// Returns true when the list has elements of same type up to the depth `depth`.
27// Booleans and numbers are not distinguinshed as of distinct types.
28// Arguments:
29// l = the list to check
30// depth = the lowest level the check is done. Default: 10
31// Example:
32// a = is_homogeneous([[1,["a"]], [2,["b"]]]); // Returns true
33// b = is_homogeneous([[1,["a"]], [2,[true]]]); // Returns false
34// c = is_homogeneous([[1,["a"]], [2,[true]]], 1); // Returns true
35// d = is_homogeneous([[1,["a"]], [2,[true]]], 2); // Returns false
36// e = is_homogeneous([[1,["a"]], [true,["b"]]]); // Returns true
37function is_homogeneous(l, depth=10) =
38 !is_list(l) || l==[] ? false :
39 let( l0=l[0] )
40 [] == [for(i=[1:1:len(l)-1]) if( ! _same_type(l[i],l0, depth+1) ) 0 ];
41
42function is_homogenous(l, depth=10) = is_homogeneous(l, depth);
43
44
45function _same_type(a,b, depth) =
46 (depth==0) ||
47 (is_undef(a) && is_undef(b)) ||
48 (is_bool(a) && is_bool(b)) ||
49 (is_num(a) && is_num(b)) ||
50 (is_string(a) && is_string(b)) ||
51 (is_list(a) && is_list(b) && len(a)==len(b)
52 && []==[for(i=idx(a)) if( ! _same_type(a[i],b[i],depth-1) ) 0] );
53
54
55// Function: min_length()
56// Usage:
57// llen = min_length(list);
58// Topics: List Handling
59// See Also: max_length()
60// Description:
61// Returns the length of the shortest sublist in a list of lists.
62// Arguments:
63// list = A list of lists.
64// Example:
65// slen = min_length([[3,4,5],[6,7,8,9]]); // Returns: 3
66function min_length(list) =
67 assert(is_list(list), "Invalid input." )
68 min([for (v = list) len(v)]);
69
70
71// Function: max_length()
72// Usage:
73// llen = max_length(list);
74// Topics: List Handling
75// See Also: min_length()
76// Description:
77// Returns the length of the longest sublist in a list of lists.
78// Arguments:
79// list = A list of lists.
80// Example:
81// llen = max_length([[3,4,5],[6,7,8,9]]); // Returns: 4
82function max_length(list) =
83 assert(is_list(list), "Invalid input." )
84 max([for (v = list) len(v)]);
85
86
87
88
89// Internal. Not exposed.
90function _list_shape_recurse(v) =
91 !is_list(v[0])
92 ? len( [for(entry=v) if(!is_list(entry)) 0] ) == 0 ? [] : [undef]
93 : let(
94 firstlen = is_list(v[0]) ? len(v[0]): undef,
95 first = len( [for(entry = v) if(! is_list(entry) || (len(entry) != firstlen)) 0 ] ) == 0 ? firstlen : undef,
96 leveldown = flatten(v)
97 )
98 is_list(leveldown[0])
99 ? concat([first],_list_shape_recurse(leveldown))
100 : [first];
101
102function _list_shape_recurse(v) =
103 let( alen = [for(vi=v) is_list(vi) ? len(vi): -1] )
104 v==[] || max(alen)==-1 ? [] :
105 let( add = max(alen)!=min(alen) ? undef : alen[0] )
106 concat( add, _list_shape_recurse(flatten(v)));
107
108
109// Function: list_shape()
110// Usage:
111// dims = list_shape(v, [depth]);
112// Topics: Matrices, List Handling
113// Description:
114// Returns the size of a multi-dimensional array, a list of the lengths at each depth.
115// If the returned value has `dims[i] = j` then it means the ith index ranges of j items.
116// The return `dims[0]` is equal to the length of v. Then `dims[1]` is equal to the
117// length of the lists in v, and in general, `dims[i]` is equal to the length of the items
118// nested to depth i in the list v. If the length of items at that depth is inconsistent, then
119// `undef` is returned. If no items exist at that depth then `0` is returned. Note that
120// for simple vectors or matrices it is faster to compute `len(v)` and `len(v[0])`.
121// Arguments:
122// v = list to get shape of
123// depth = depth to compute the size of. If not given, returns a list of sizes at all depths.
124// Example:
125// a = list_shape([[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]]]); // Returns [2,2,3]
126// b = list_shape([[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]]], 0); // Returns 2
127// c = list_shape([[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]]], 2); // Returns 3
128// d = list_shape([[[1,2,3],[4,5,6]],[[7,8,9]]]); // Returns [2,undef,3]
129function list_shape(v, depth=undef) =
130 assert( is_undef(depth) || ( is_finite(depth) && depth>=0 ), "Invalid depth.")
131 ! is_list(v) ? 0 :
132 (depth == undef)
133 ? concat([len(v)], _list_shape_recurse(v))
134 : (depth == 0)
135 ? len(v)
136 : let( dimlist = _list_shape_recurse(v))
137 (depth > len(dimlist))? 0 : dimlist[depth-1] ;
138
139
140
141// Function: in_list()
142// Usage:
143// bool = in_list(val, list, [idx]);
144// Topics: List Handling
145// Description:
146// Returns true if value `val` is in list `list`. When `val==NAN` the answer will be false for any list.
147// Arguments:
148// val = The simple value to search for.
149// list = The list to search.
150// idx = If given, searches the given columns for matches for `val`.
151// Example:
152// a = in_list("bar", ["foo", "bar", "baz"]); // Returns true.
153// b = in_list("bee", ["foo", "bar", "baz"]); // Returns false.
154// c = in_list("bar", [[2,"foo"], [4,"bar"], [3,"baz"]], idx=1); // Returns true.
155
156// Note that a huge complication occurs because OpenSCAD's search() finds
157// index i as a hits if the val equals list[i] but also if val equals list[i][0].
158// This means every hit needs to be checked to see if it's actually a hit,
159// and if the first hit is a mismatch we have to keep searching.
160// We assume that the normal case doesn't have mixed data, and try first
161// with just one hit, but if this finds a mismatch then we try again
162// with all hits, which could be slow for long lists.
163function in_list(val,list,idx) =
164 assert(is_list(list),"Input is not a list")
165 assert(is_undef(idx) || is_finite(idx), "Invalid idx value.")
166 let( firsthit = search([val], list, num_returns_per_match=1, index_col_num=idx)[0] )
167 firsthit==[] ? false
168 : is_undef(idx) && val==list[firsthit] ? true
169 : is_def(idx) && val==list[firsthit][idx] ? true
170 // first hit was found but didn't match, so try again with all hits
171 : let ( allhits = search([val], list, 0, idx)[0])
172 is_undef(idx) ? [for(hit=allhits) if (list[hit]==val) 1] != []
173 : [for(hit=allhits) if (list[hit][idx]==val) 1] != [];
174
175
176
177// Section: List Indexing
178
179// Function: select()
180// Topics: List Handling
181// Description:
182// Returns a portion of a list, wrapping around past the beginning, if end<start.
183// The first item is index 0. Negative indexes are counted back from the end.
184// The last item is -1. If only the `start` index is given, returns just the value
185// at that position when `start` is a number or the selected list of entries when `start` is
186// a list of indices or a range.
187// Usage:
188// item = select(list, start);
189// item = select(list, [s:d:e]);
190// item = select(list, [i0,i1...,ik]);
191// list = select(list, start, end);
192// Arguments:
193// list = The list to get the portion of.
194// start = Either the index of the first item or an index range or a list of indices.
195// end = The index of the last item when `start` is a number. When `start` is a list or a range, `end` should not be given.
196// See Also: slice(), column(), last()
197// Example:
198// l = [3,4,5,6,7,8,9];
199// a = select(l, 5, 6); // Returns [8,9]
200// b = select(l, 5, 8); // Returns [8,9,3,4]
201// c = select(l, 5, 2); // Returns [8,9,3,4,5]
202// d = select(l, -3, -1); // Returns [7,8,9]
203// e = select(l, 3, 3); // Returns [6]
204// f = select(l, 4); // Returns 7
205// g = select(l, -2); // Returns 8
206// h = select(l, [1:3]); // Returns [4,5,6]
207// i = select(l, [3,1]); // Returns [6,4]
208function select(list, start, end) =
209 assert( is_list(list) || is_string(list), "Invalid list.")
210 let(l=len(list))
211 l==0
212 ? []
213 : end==undef
214 ? is_num(start)
215 ? list[ (start%l+l)%l ]
216 : assert( start==[] || is_vector(start) || is_range(start), "Invalid start parameter")
217 [for (i=start) list[ (i%l+l)%l ] ]
218 : assert(is_finite(start), "When `end` is given, `start` parameter should be a number.")
219 assert(is_finite(end), "Invalid end parameter.")
220 let( s = (start%l+l)%l, e = (end%l+l)%l )
221 (s <= e)
222 ? [ for (i = [s:1:e]) list[i] ]
223 : [ for (i = [s:1:l-1]) list[i],
224 for (i = [0:1:e]) list[i] ] ;
225
226
227// Function: slice()
228// Usage:
229// list = slice(list, s, e);
230// Description:
231// Returns a slice of a list, from the first position `s` up to and including the last position `e`.
232// The first item in the list is at index 0. Negative indexes are counted back from the end.
233// An index of -1 refers to the last list item.
234// Arguments:
235// list = The list to get the slice of.
236// start = The index of the first item to return. Default: 0
237// end = The index of the last item to return. Default: -1 (last item)
238// See Also: select(), column(), last()
239// Example:
240// a = slice([3,4,5,6,7,8,9], 3, 5); // Returns [6,7,8]
241// b = slice([3,4,5,6,7,8,9], 2, -1); // Returns [5,6,7,8,9]
242// c = slice([3,4,5,6,7,8,9], 1, 1); // Returns [4]
243// d = slice([3,4,5,6,7,8,9], 5); // Returns [8,9]
244// e = slice([3,4,5,6,7,8,9], 2, -2); // Returns [5,6,7,8]
245// f = slice([3,4,5,6,7,8,9], 4, 3; // Returns []
246function slice(list,start=0,end=-1) =
247 assert(is_list(list))
248 assert(is_int(start))
249 assert(is_int(end))
250 !list? [] :
251 let(
252 l = len(list),
253 start = constrain(start + (start<0? l : 0), 0, l-1),
254 end = constrain(end + (end<0? l : 0), 0, l-1)
255 )
256 [if (end>=start) for (i=[start:1:end]) list[i]];
257
258
259// Function: last()
260// Usage:
261// item = last(list);
262// Topics: List Handling
263// See Also: select(), slice(), column()
264// Description:
265// Returns the last element of a list, or undef if empty.
266// Arguments:
267// list = The list to get the last element of.
268// Example:
269// l = [3,4,5,6,7,8,9];
270// x = last(l); // Returns 9.
271function last(list) =
272 list[len(list)-1];
273
274
275// Function: list_head()
276// Usage:
277// list = list_head(list, [to]);
278// Topics: List Handling
279// See Also: select(), slice(), list_tail(), last()
280// Description:
281// Returns the head of the given list, from the first item up until the `to` index, inclusive.
282// By default returns all but the last element of the list.
283// If the `to` index is negative, then the length of the list is added to it, such that
284// `-1` is the last list item. `-2` is the second from last. `-3` is third from last, etc.
285// If the list is shorter than the given index, then the full list is returned.
286// Arguments:
287// list = The list to get the head of.
288// to = The last index to include. If negative, adds the list length to it. ie: -1 is the last list item. Default: -2
289// Example:
290// hlist1 = list_head(["foo", "bar", "baz"]); // Returns: ["foo", "bar"]
291// hlist2 = list_head(["foo", "bar", "baz"], -3); // Returns: ["foo"]
292// hlist3 = list_head(["foo", "bar", "baz"], 2); // Returns: ["foo","bar"]
293// hlist4 = list_head(["foo", "bar", "baz"], -5); // Returns: []
294// hlist5 = list_head(["foo", "bar", "baz"], 5); // Returns: ["foo","bar","baz"]
295function list_head(list, to=-2) =
296 assert(is_list(list))
297 assert(is_finite(to))
298 to<0? [for (i=[0:1:len(list)+to]) list[i]] :
299 to<len(list)? [for (i=[0:1:to]) list[i]] :
300 list;
301
302
303// Function: list_tail()
304// Usage:
305// list = list_tail(list, [from]);
306// Topics: List Handling
307// See Also: select(), slice(), list_tail(), last()
308// Description:
309// Returns the tail of the given list, from the `from` index up until the end of the list, inclusive.
310// By default returns all but the first item.
311// If the `from` index is negative, then the length of the list is added to it, such that
312// `-1` is the last list item. `-2` is the second from last. `-3` is third from last, etc.
313// If you want it to return the last three items of the list, use `from=-3`.
314// Arguments:
315// list = The list to get the tail of.
316// from = The first index to include. If negative, adds the list length to it. ie: -1 is the last list item. Default: 1.
317// Example:
318// tlist1 = list_tail(["foo", "bar", "baz"]); // Returns: ["bar", "baz"]
319// tlist2 = list_tail(["foo", "bar", "baz"], -1); // Returns: ["baz"]
320// tlist3 = list_tail(["foo", "bar", "baz"], 2); // Returns: ["baz"]
321// tlist4 = list_tail(["foo", "bar", "baz"], -5); // Returns: ["foo","bar","baz"]
322// tlist5 = list_tail(["foo", "bar", "baz"], 5); // Returns: []
323function list_tail(list, from=1) =
324 assert(is_list(list))
325 assert(is_finite(from))
326 from>=0? [for (i=[from:1:len(list)-1]) list[i]] :
327 let(from = from + len(list))
328 from>=0? [for (i=[from:1:len(list)-1]) list[i]] :
329 list;
330
331
332
333// Function: bselect()
334// Usage:
335// sublist = bselect(list, index);
336// Topics: List Handling
337// See Also: list_bset()
338// Description:
339// Returns the items in `list` whose matching element in `index` evaluates as true.
340// Arguments:
341// list = Initial list (or string) to extract items from.
342// index = List of values that will be evaluated as boolean, same length as `list`.
343// Example:
344// a = bselect([3,4,5,6,7], [false,true,true,false,true]); // Returns: [4,5,7]
345function bselect(list,index) =
346 assert(is_list(list)||is_string(list), "First argument must be a list or string." )
347 assert(is_list(index) && len(index)==len(list) , "Second argument must have same length as the first." )
348 is_string(list)? str_join(bselect( [for (x=list) x], index)) :
349 [for(i=idx(list)) if (index[i]) list[i]];
350
351
352// Section: List Construction
353
354
355// Function: repeat()
356// Usage:
357// list = repeat(val, n);
358// Topics: List Handling
359// See Also: count(), lerpn()
360// Description:
361// Generates a list of `n` copies of the given value `val`.
362// If the count `n` is given as a list of counts, then this creates a
363// multi-dimensional array, filled with `val`.
364// Arguments:
365// val = The value to repeat to make the list or array.
366// n = The number of copies to make of `val`. Can be a list to make an array of copies.
367// Example:
368// a = repeat(1, 4); // Returns [1,1,1,1]
369// b = repeat(8, [2,3]); // Returns [[8,8,8], [8,8,8]]
370// c = repeat(0, [2,2,3]); // Returns [[[0,0,0],[0,0,0]], [[0,0,0],[0,0,0]]]
371// d = repeat([1,2,3],3); // Returns [[1,2,3], [1,2,3], [1,2,3]]
372function repeat(val, n, i=0) =
373 is_num(n)? [for(j=[1:1:n]) val] :
374 assert( is_list(n), "Invalid count number.")
375 (i>=len(n))? val :
376 [for (j=[1:1:n[i]]) repeat(val, n, i+1)];
377
378
379
380// Function: list_bset()
381// Usage:
382// arr = list_bset(indexset, valuelist, [dflt]);
383// Topics: List Handling
384// See Also: bselect()
385// Description:
386// Opposite of `bselect()`. Returns a list the same length as `indexlist`, where each item will
387// either be 0 if the corresponding item in `indexset` is false, or the next sequential value
388// from `valuelist` if the item is true. The number of `true` values in `indexset` must be equal
389// to the length of `valuelist`.
390// Arguments:
391// indexset = A list of boolean values.
392// valuelist = The list of values to set into the returned list.
393// dflt = Default value to store when the indexset item is false. Default: 0
394// Example:
395// a = list_bset([false,true,false,true,false], [3,4]); // Returns: [0,3,0,4,0]
396// b = list_bset([false,true,false,true,false], [3,4], dflt=1); // Returns: [1,3,1,4,1]
397function list_bset(indexset, valuelist, dflt=0) =
398 assert(is_list(indexset), "The index set is not a list." )
399 assert(is_list(valuelist), "The `valuelist` is not a list." )
400 let( trueind = search([true], indexset,0)[0] )
401 assert( !(len(trueind)>len(valuelist)), str("List `valuelist` too short; its length should be ",len(trueind)) )
402 assert( !(len(trueind)<len(valuelist)), str("List `valuelist` too long; its length should be ",len(trueind)) )
403 concat(
404 list_set([],trueind, valuelist, dflt=dflt), // Fill in all of the values
405 repeat(dflt,len(indexset)-max(trueind)-1) // Add trailing values so length matches indexset
406 );
407
408
409
410// Function: list()
411// Topics: List Handling, Type Conversion
412// Usage:
413// list = list(l)
414// Description:
415// Expands a range into a full list. If given a list, returns it verbatim.
416// If given a string, explodes it into a list of single letters.
417// Arguments:
418// l = The value to expand.
419// See Also: scalar_vec3(), force_list()
420// Example:
421// l1 = list([3:2:9]); // Returns: [3,5,7,9]
422// l2 = list([3,4,5]); // Returns: [3,4,5]
423// l3 = list("Foo"); // Returns: ["F","o","o"]
424// l4 = list(23); // Returns: [23]
425function list(l) = is_list(l)? l : [for (x=l) x];
426
427
428// Function: force_list()
429// Usage:
430// list = force_list(value, [n], [fill]);
431// Topics: List Handling
432// See Also: scalar_vec3()
433// Description:
434// Coerces non-list values into a list. Makes it easy to treat a scalar input
435// consistently as a singleton list, as well as list inputs.
436// - If `value` is a list, then that list is returned verbatim.
437// - If `value` is not a list, and `fill` is not given, then a list of `n` copies of `value` will be returned.
438// - If `value` is not a list, and `fill` is given, then a list `n` items long will be returned where `value` will be the first item, and the rest will contain the value of `fill`.
439// Arguments:
440// value = The value or list to coerce into a list.
441// n = The number of items in the coerced list. Default: 1
442// fill = The value to pad the coerced list with, after the firt value. Default: undef (pad with copies of `value`)
443// Example:
444// x = force_list([3,4,5]); // Returns: [3,4,5]
445// y = force_list(5); // Returns: [5]
446// z = force_list(7, n=3); // Returns: [7,7,7]
447// w = force_list(4, n=3, fill=1); // Returns: [4,1,1]
448function force_list(value, n=1, fill) =
449 is_list(value) ? value :
450 is_undef(fill)? [for (i=[1:1:n]) value] : [value, for (i=[2:1:n]) fill];
451
452
453// Section: List Modification
454
455// Function: reverse()
456// Usage:
457// rlist = reverse(list);
458// Topics: List Handling
459// See Also: select(), list_rotate()
460// Description:
461// Reverses a list or string.
462// Arguments:
463// list = The list or string to reverse.
464// Example:
465// reverse([3,4,5,6]); // Returns [6,5,4,3]
466function reverse(list) =
467 assert(is_list(list)||is_string(list), str("Input to reverse must be a list or string. Got: ",list))
468 let (elems = [ for (i = [len(list)-1 : -1 : 0]) list[i] ])
469 is_string(list)? str_join(elems) : elems;
470
471
472// Function: list_rotate()
473// Usage:
474// rlist = list_rotate(list, [n]);
475// Topics: List Handling
476// See Also: select(), reverse()
477// Description:
478// Rotates the contents of a list by `n` positions left, so that list[n] becomes the first entry of the list.
479// If `n` is negative, then the rotation is `abs(n)` positions to the right.
480// If `list` is a string, then a string is returned with the characters rotates within the string.
481// Arguments:
482// list = The list to rotate.
483// n = The number of positions to rotate by. If negative, rotated to the right. Positive rotates to the left. Default: 1
484// Example:
485// l1 = list_rotate([1,2,3,4,5],-2); // Returns: [4,5,1,2,3]
486// l2 = list_rotate([1,2,3,4,5],-1); // Returns: [5,1,2,3,4]
487// l3 = list_rotate([1,2,3,4,5],0); // Returns: [1,2,3,4,5]
488// l4 = list_rotate([1,2,3,4,5],1); // Returns: [2,3,4,5,1]
489// l5 = list_rotate([1,2,3,4,5],2); // Returns: [3,4,5,1,2]
490// l6 = list_rotate([1,2,3,4,5],3); // Returns: [4,5,1,2,3]
491// l7 = list_rotate([1,2,3,4,5],4); // Returns: [5,1,2,3,4]
492// l8 = list_rotate([1,2,3,4,5],5); // Returns: [1,2,3,4,5]
493// l9 = list_rotate([1,2,3,4,5],6); // Returns: [2,3,4,5,1]
494function list_rotate(list,n=1) =
495 assert(is_list(list)||is_string(list), "Invalid list or string.")
496 assert(is_int(n), "The rotation number should be integer")
497 let (
498 ll = len(list),
499 n = ((n % ll) + ll) % ll,
500 elems = [
501 for (i=[n:1:ll-1]) list[i],
502 for (i=[0:1:n-1]) list[i]
503 ]
504 )
505 is_string(list)? str_join(elems) : elems;
506
507
508
509// Function: shuffle()
510// Usage:
511// shuffled = shuffle(list, [seed]);
512// Topics: List Handling
513// See Also: sort(), sortidx(), unique(), unique_count()
514// Description:
515// Shuffles the input list into random order.
516// If given a string, shuffles the characters within the string.
517// If you give a numeric seed value then the permutation
518// will be repeatable.
519// Arguments:
520// list = The list to shuffle.
521// seed = Optional random number seed for the shuffling.
522// Example:
523// // Spades Hearts Diamonds Clubs
524// suits = ["\u2660", "\u2661", "\u2662", "\u2663"];
525// ranks = [2,3,4,5,6,7,8,9,10,"J","Q","K","A"];
526// cards = [for (suit=suits, rank=ranks) str(rank,suit)];
527// deck = shuffle(cards);
528function shuffle(list,seed) =
529 assert(is_list(list)||is_string(list), "Invalid input." )
530 is_string(list)? str_join(shuffle([for (x = list) x],seed=seed)) :
531 len(list)<=1 ? list :
532 let(
533 rval = is_num(seed) ? rands(0,1,len(list),seed_value=seed)
534 : rands(0,1,len(list)),
535 left = [for (i=[0:len(list)-1]) if (rval[i]< 0.5) list[i]],
536 right = [for (i=[0:len(list)-1]) if (rval[i]>=0.5) list[i]]
537 )
538 concat(shuffle(left), shuffle(right));
539
540
541
542// Function: repeat_entries()
543// Usage:
544// newlist = repeat_entries(list, N, [exact]);
545// Topics: List Handling
546// See Also: repeat()
547// Description:
548// Takes a list as input and duplicates some of its entries to produce a list
549// with length `N`. If the requested `N` is not a multiple of the list length then
550// the entries will be duplicated as uniformly as possible. You can also set `N` to a vector,
551// in which case len(N) must equal len(list) and the output repeats the ith entry N[i] times.
552// In either case, the result will be a list of length `N`. The `exact` option requires
553// that the final length is exactly as requested. If you set it to `false` then the
554// algorithm will favor uniformity and the output list may have a different number of
555// entries due to rounding.
556// .
557// When applied to a path the output path is the same geometrical shape but has some vertices
558// repeated. This can be useful when you need to align paths with a different number of points.
559// (See also subdivide_path for a different way to do that.)
560// Arguments:
561// list = list whose entries will be repeated
562// N = scalar total number of points desired or vector requesting N[i] copies of vertex i.
563// exact = if true return exactly the requested number of points, possibly sacrificing uniformity. If false, return uniform points that may not match the number of points requested. Default: True
564// Example:
565// list = [0,1,2,3];
566// a = repeat_entries(list, 6); // Returns: [0,0,1,2,2,3]
567// b = repeat_entries(list, 6, exact=false); // Returns: [0,0,1,1,2,2,3,3]
568// c = repeat_entries(list, [1,1,2,1], exact=false); // Returns: [0,1,2,2,3]
569function repeat_entries(list, N, exact=true) =
570 assert(is_list(list) && len(list)>0, "The list cannot be void.")
571 assert((is_finite(N) && N>0) || is_vector(N,len(list)),
572 "Parameter N must be a number greater than zero or vector with the same length of `list`")
573 let(
574 length = len(list),
575 reps_guess = is_list(N)? N : repeat(N/length,length),
576 reps = exact ?
577 _sum_preserving_round(reps_guess)
578 : [for (val=reps_guess) round(val)]
579 )
580 [for(i=[0:length-1]) each repeat(list[i],reps[i])];
581
582
583// Function: list_pad()
584// Usage:
585// newlist = list_pad(list, minlen, [fill]);
586// Topics: List Handling
587// See Also: force_list(), scalar_vec3()
588// Description:
589// If the list `list` is shorter than `minlen` length, pad it to length with the value given in `fill`.
590// Arguments:
591// list = A list.
592// minlen = The minimum length to pad the list to.
593// fill = The value to pad the list with. Default: `undef`
594// Example:
595// list = [3,4,5];
596// nlist = list_pad(list,5,23); // Returns: [3,4,5,23,23]
597function list_pad(list, minlen, fill) =
598 assert(is_list(list), "Invalid input." )
599 concat(list,repeat(fill,minlen-len(list)));
600
601
602// Function: list_set()
603// Usage:
604// list = list_set(list, indices, values, [dflt], [minlen]);
605// Topics: List Handling
606// See Also: list_insert(), list_remove(), list_remove_values()
607// Description:
608// Takes the input list and returns a new list such that `list[indices[i]] = values[i]` for all of
609// the (index,value) pairs supplied and unchanged for other indices. If you supply `indices` that are
610// beyond the length of the list then the list is extended and filled in with the `dflt` value.
611// If you set `minlen` then the list is lengthed, if necessary, by padding with `dflt` to that length.
612// Repetitions in `indices` are not allowed. The lists `indices` and `values` must have the same length.
613// If `indices` is given as a scalar, then that index of the given `list` will be set to the scalar value of `values`.
614// Arguments:
615// list = List to set items in. Default: []
616// indices = List of indices into `list` to set.
617// values = List of values to set.
618// dflt = Default value to store in sparse skipped indices.
619// minlen = Minimum length to expand list to.
620// Example:
621// a = list_set([2,3,4,5], 2, 21); // Returns: [2,3,21,5]
622// b = list_set([2,3,4,5], [1,3], [81,47]); // Returns: [2,81,4,47]
623function list_set(list=[],indices,values,dflt=0,minlen=0) =
624 assert(is_list(list))
625 !is_list(indices)? (
626 (is_finite(indices) && indices<len(list))
627 ? concat([for (i=idx(list)) i==indices? values : list[i]], repeat(dflt, minlen-len(list)))
628 : list_set(list,[indices],[values],dflt)
629 ) :
630 indices==[] && values==[]
631 ? concat(list, repeat(dflt, minlen-len(list)))
632 : assert(is_vector(indices) && is_list(values) && len(values)==len(indices),
633 "Index list and value list must have the same length")
634 let( midx = max(len(list)-1, max(indices)) )
635 [
636 for (i=[0:1:midx]) let(
637 j = search(i,indices,0),
638 k = j[0]
639 )
640 assert( len(j)<2, "Repeated indices are not allowed." )
641 k!=undef
642 ? values[k]
643 : i<len(list) ? list[i] : dflt,
644 each repeat(dflt, minlen-max(len(list),max(indices)))
645 ];
646
647
648// Function: list_insert()
649// Usage:
650// list = list_insert(list, indices, values);
651// Topics: List Handling
652// See Also: list_set(), list_remove(), list_remove_values()
653// Description:
654// Insert `values` into `list` before position `indices`. The indices for insertion
655// are based on the original list, before any insertions have occurred.
656// Arguments:
657// list = list to insert items into
658// indices = index or list of indices where values are inserted
659// values = value or list of values to insert
660// Example:
661// a = list_insert([3,6,9,12],1,5); // Returns [3,5,6,9,12]
662// b = list_insert([3,6,9,12],[1,3],[5,11]); // Returns [3,5,6,9,11,12]
663function list_insert(list, indices, values) =
664 assert(is_list(list))
665 !is_list(indices) ?
666 assert( is_finite(indices) && is_finite(values), "Invalid indices/values." )
667 assert( indices<=len(list), "Indices must be <= len(list) ." )
668 [
669 for (i=idx(list)) each ( i==indices? [ values, list[i] ] : [ list[i] ] ),
670 if (indices==len(list)) values
671 ] :
672 indices==[] && values==[] ? list :
673 assert( is_vector(indices) && is_list(values) && len(values)==len(indices),
674 "Index list and value list must have the same length")
675 assert( max(indices)<=len(list), "Indices must be <= len(list)." )
676 let(
677 maxidx = max(indices),
678 minidx = min(indices)
679 ) [
680 for (i=[0:1:minidx-1] ) list[i],
681 for (i=[minidx : min(maxidx, len(list)-1)] )
682 let(
683 j = search(i,indices,0),
684 k = j[0],
685 x = assert( len(j)<2, "Repeated indices are not allowed." )
686 ) each ( k != undef ? [ values[k], list[i] ] : [ list[i] ] ),
687 for ( i = [min(maxidx, len(list)-1)+1 : 1 : len(list)-1] ) list[i],
688 if (maxidx == len(list)) values[max_index(indices)]
689 ];
690
691
692// Function: list_remove()
693// Usage:
694// list = list_remove(list, ind);
695// Topics: List Handling
696// See Also: list_set(), list_insert(), list_remove_values()
697// Description:
698// If `ind` is a number remove `list[ind]` from the list. If `ind` is a list of indices
699// remove from the list the item all items whose indices appear in `ind`. If you give
700// indices that are not in the list they are ignored.
701// Arguments:
702// list = The list to remove items from.
703// ind = index or list of indices of items to remove.
704// Example:
705// a = list_remove([3,6,9,12],1); // Returns: [3,9,12]
706// b = list_remove([3,6,9,12],[1,3]); // Returns: [3,9]
707// c = list_remove([3,6],3); // Returns: [3,6]
708function list_remove(list, ind) =
709 assert(is_list(list), "Invalid list in list_remove")
710 is_finite(ind) ?
711 (
712 (ind<0 || ind>=len(list)) ? list
713 :
714 [
715 for (i=[0:1:ind-1]) list[i],
716 for (i=[ind+1:1:len(list)-1]) list[i]
717 ]
718 )
719 : ind==[] ? list
720 : assert( is_vector(ind), "Invalid index list in list_remove")
721 let(sres = search(count(list),ind,1))
722 [
723 for(i=idx(list))
724 if (sres[i] == [])
725 list[i]
726 ];
727
728// This method is faster for long lists with few values to remove
729// let( rem = list_set([], indices, repeat(1,len(indices)), minlen=len(list)))
730// [for(i=idx(list)) if (rem[i]==0) list[i]];
731
732
733
734// Function: list_remove_values()
735// Usage:
736// list = list_remove_values(list, values, [all]);
737// Topics: List Handling
738// See Also: list_set(), list_insert(), list_remove()
739// Description:
740// Removes the first, or all instances of the given value or list of values from the list.
741// If you specify `all=false` and list a value twice then the first two instances will be removed.
742// Note that if you want to remove a list value such as `[3,4]` then you must give it as
743// a singleton list, or it will be interpreted as a list of two scalars to remove.
744// Arguments:
745// list = The list to modify.
746// values = The value or list of values to remove from the list.
747// all = If true, remove all instances of the value `value` from the list `list`. If false, remove only the first. Default: false
748// Example:
749// test = [3,4,[5,6],7,5,[5,6],4,[6,5],7,[4,4]];
750// a=list_remove_values(test,4); // Returns: [3, [5, 6], 7, 5, [5, 6], 4, [6, 5], 7, [4, 4]]
751// b=list_remove_values(test,[4,4]); // Returns: [3, [5, 6], 7, 5, [5, 6], [6, 5], 7, [4, 4]]
752// c=list_remove_values(test,[4,7]); // Returns: [3, [5, 6], 5, [5, 6], 4, [6, 5], 7, [4, 4]]
753// d=list_remove_values(test,[5,6]); // Returns: [3, 4, [5, 6], 7, [5, 6], 4, [6, 5], 7, [4, 4]]
754// e=list_remove_values(test,[[5,6]]); // Returns: [3,4,7,5,[5,6],4,[6,5],7,[4,4]]
755// f=list_remove_values(test,[[5,6]],all=true); // Returns: [3,4,7,5,4,[6,5],7,[4,4]]
756// animals = ["bat", "cat", "rat", "dog", "bat", "rat"];
757// animals2 = list_remove_values(animals, "rat"); // Returns: ["bat","cat","dog","bat","rat"]
758// nonflying = list_remove_values(animals, "bat", all=true); // Returns: ["cat","rat","dog","rat"]
759// animals3 = list_remove_values(animals, ["bat","rat"]); // Returns: ["cat","dog","bat","rat"]
760// domestic = list_remove_values(animals, ["bat","rat"], all=true); // Returns: ["cat","dog"]
761// animals4 = list_remove_values(animals, ["tucan","rat"], all=true); // Returns: ["bat","cat","dog","bat"]
762function list_remove_values(list,values=[],all=false) =
763 !is_list(values)? list_remove_values(list, values=[values], all=all) :
764 assert(is_list(list), "Invalid list")
765 len(values)==0 ? list :
766 len(values)==1 ?
767 (
768 !all ?
769 (
770 let(firsthit = search(values,list,1)[0])
771 firsthit==[] ? list
772 : list[firsthit]==values[0] ? list_remove(list,firsthit)
773 : let(allhits = search(values,list,0)[0],
774 allind = [for(i=allhits) if (list[i]==values[0]) i]
775 )
776 allind==[] ? list : list_remove(list,min(allind))
777 )
778 :
779 (
780 let(allhits = search(values,list,0)[0],
781 allind = [for(i=allhits) if (list[i]==values[0]) i]
782 )
783 allind==[] ? list : list_remove(list,allind)
784 )
785 )
786 :!all ? list_remove_values(list_remove_values(list, values[0],all=all), list_tail(values),all=all)
787 :
788 [
789 for(i=idx(list))
790 let(hit=search([list[i]],values,0)[0])
791 if (hit==[]) list[i]
792 else
793 let(check = [for(j=hit) if (values[j]==list[i]) 1])
794 if (check==[]) list[i]
795 ];
796
797
798
799
800// Section: Lists of Subsets
801
802// Function: idx()
803// Usage:
804// rng = idx(list, [s=], [e=], [step=]);
805// for(i=idx(list, [s=], [e=], [step=])) ...
806// Topics: List Handling, Iteration
807// See Also: pair(), triplet(), combinations(), permutations()
808// Description:
809// Returns the range of indexes for the given list.
810// Arguments:
811// list = The list to returns the index range of.
812// ---
813// s = The starting index. Default: 0
814// e = The delta from the end of the list. Default: -1 (end of list)
815// step = The step size to stride through the list. Default: 1
816// Example(2D):
817// colors = ["red", "green", "blue"];
818// for (i=idx(colors)) right(20*i) color(colors[i]) circle(d=10);
819function idx(list, s=0, e=-1, step=1) =
820 assert(is_list(list)||is_string(list), "Invalid input." )
821 let( ll = len(list) )
822 ll == 0 ? [0:1:ll-1] :
823 let(
824 _s = posmod(s,ll),
825 _e = posmod(e,ll)
826 ) [_s : step : _e];
827
828
829
830// Function: pair()
831// Usage:
832// p = pair(list, [wrap]);
833// for (p = pair(list, [wrap])) ... // On each iteration, p contains a list of two adjacent items.
834// Topics: List Handling, Iteration
835// See Also: idx(), triplet(), combinations(), permutations()
836// Description:
837// Returns a list of all of the pairs of adjacent items from a list, optionally wrapping back to the front. The pairs overlap, and
838// are returned in order starting with the first two entries in the list. If the list has less than two elements, the empty list is returned.
839// Arguments:
840// list = The list to use for making pairs
841// wrap = If true, wrap back to the start from the end. ie: return the last and first items as the last pair. Default: false
842// Example(2D): Does NOT wrap from end to start,
843// for (p = pair(circle(d=40, $fn=12)))
844// stroke(p, endcap2="arrow2");
845// Example(2D): Wraps around from end to start.
846// for (p = pair(circle(d=40, $fn=12), wrap=true))
847// stroke(p, endcap2="arrow2");
848// Example:
849// l = ["A","B","C","D"];
850// echo([for (p=pair(l)) str(p.y,p.x)]); // Outputs: ["BA", "CB", "DC"]
851function pair(list, wrap=false) =
852 assert(is_list(list)||is_string(list), "Invalid input." )
853 assert(is_bool(wrap))
854 let( L = len(list)-1)
855 L<1 ? [] :
856 [
857 for (i=[0:1:L-1]) [list[i], list[i+1]],
858 if(wrap) [list[L], list[0]]
859 ];
860
861
862
863// Function: triplet()
864// Usage:
865// list = triplet(list, [wrap]);
866// for (t = triplet(list, [wrap])) ...
867// Topics: List Handling, Iteration
868// See Also: idx(), pair(), combinations(), permutations()
869// Description:
870// Returns a list of all adjacent triplets from a list, optionally wrapping back to the front.
871// If you set `wrap` to true then the first triplet is the one centered on the first list element, so it includes
872// the last element and the first two elements. If the list has fewer than three elements then the empty list is returned.
873// Arguments:
874// list = list to produce triplets from
875// wrap = if true, wrap triplets around the list. Default: false
876// Example:
877// list = [0,1,2,3,4];
878// a = triplet(list); // Returns [[0,1,2],[1,2,3],[2,3,4]]
879// b = triplet(list,wrap=true); // Returns [[4,0,1],[0,1,2],[1,2,3],[2,3,4],[3,4,0]]
880// letters = ["A","B","C","D","E"];
881// [for (p=triplet(letters)) str(p.z,p.y,p.x)]; // Returns: ["CBA", "DCB", "EDC"]
882// Example(2D):
883// path = [for (i=[0:24]) polar_to_xy(i*2, i*360/12)];
884// for (t = triplet(path)) {
885// a = t[0]; b = t[1]; c = t[2];
886// v = unit(unit(a-b) + unit(c-b));
887// translate(b) rot(from=FWD,to=v) anchor_arrow2d();
888// }
889// stroke(path);
890function triplet(list, wrap=false) =
891 assert(is_list(list)||is_string(list), "Invalid input." )
892 assert(is_bool(wrap))
893 let(L=len(list))
894 L<3 ? [] :
895 [
896 if(wrap) [list[L-1], list[0], list[1]],
897 for (i=[0:1:L-3]) [list[i],list[i+1],list[i+2]],
898 if(wrap) [list[L-2], list[L-1], list[0]]
899 ];
900
901
902// Function: combinations()
903// Usage:
904// list = combinations(l, [n]);
905// Topics: List Handling, Iteration
906// See Also: idx(), pair(), triplet(), permutations()
907// Description:
908// Returns a list of all of the (unordered) combinations of `n` items out of the given list `l`.
909// For the list `[1,2,3,4]`, with `n=2`, this will return `[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]`.
910// For the list `[1,2,3,4]`, with `n=3`, this will return `[[1,2,3], [1,2,4], [1,3,4], [2,3,4]]`.
911// Arguments:
912// l = The list to provide permutations for.
913// n = The number of items in each combination. Default: 2
914// Example:
915// pairs = combinations([3,4,5,6]); // Returns: [[3,4],[3,5],[3,6],[4,5],[4,6],[5,6]]
916// triplets = combinations([3,4,5,6],n=3); // Returns: [[3,4,5],[3,4,6],[3,5,6],[4,5,6]]
917// Example(2D):
918// for (p=combinations(regular_ngon(n=7,d=100))) stroke(p);
919function combinations(l,n=2,_s=0) =
920 assert(is_list(l), "Invalid list." )
921 assert( is_finite(n) && n>=1 && n<=len(l), "Invalid number `n`." )
922 n==1
923 ? [for (i=[_s:1:len(l)-1]) [l[i]]]
924 : [for (i=[_s:1:len(l)-n], p=combinations(l,n=n-1,_s=i+1)) concat([l[i]], p)];
925
926
927
928// Function: permutations()
929// Usage:
930// list = permutations(l, [n]);
931// Topics: List Handling, Iteration
932// See Also: idx(), pair(), triplet(), combinations()
933// Description:
934// Returns a list of all of the (ordered) permutation `n` items out of the given list `l`.
935// For the list `[1,2,3]`, with `n=2`, this will return `[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]`
936// For the list `[1,2,3]`, with `n=3`, this will return `[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`
937// Arguments:
938// l = The list to provide permutations for.
939// n = The number of items in each permutation. Default: 2
940// Example:
941// pairs = permutations([3,4,5,6]); // // Returns: [[3,4],[3,5],[3,6],[4,3],[4,5],[4,6],[5,3],[5,4],[5,6],[6,3],[6,4],[6,5]]
942function permutations(l,n=2) =
943 assert(is_list(l), "Invalid list." )
944 assert( is_finite(n) && n>=1 && n<=len(l), "Invalid number `n`." )
945 n==1
946 ? [for (i=[0:1:len(l)-1]) [l[i]]]
947 : [for (i=idx(l), p=permutations([for (j=idx(l)) if (i!=j) l[j]], n=n-1)) concat([l[i]], p)];
948
949
950
951// Section: Changing List Structure
952
953
954// Function: list_to_matrix()
955// Usage:
956// groups = list_to_matrix(v, cnt, [dflt]);
957// Description:
958// Takes a flat list of values, and groups items in sets of `cnt` length.
959// The opposite of this is `flatten()`.
960// Topics: Matrices, List Handling
961// See Also: column(), submatrix(), hstack(), flatten(), full_flatten()
962// Arguments:
963// v = The list of items to group.
964// cnt = The number of items to put in each grouping.
965// dflt = The default value to fill in with if the list is not a multiple of `cnt` items long. Default: undef
966// Example:
967// v = [1,2,3,4,5,6];
968// a = list_to_matrix(v,2) returns [[1,2], [3,4], [5,6]]
969// b = list_to_matrix(v,3) returns [[1,2,3], [4,5,6]]
970// c = list_to_matrix(v,4,0) returns [[1,2,3,4], [5,6,0,0]]
971function list_to_matrix(v, cnt, dflt=undef) =
972 [for (i = [0:cnt:len(v)-1]) [for (j = [0:1:cnt-1]) default(v[i+j], dflt)]];
973
974
975
976// Function: flatten()
977// Usage:
978// list = flatten(l);
979// Topics: Matrices, List Handling
980// See Also: column(), submatrix(), hstack(), full_flatten()
981// Description:
982// Takes a list of lists and flattens it by one level.
983// Arguments:
984// l = List to flatten.
985// Example:
986// l = flatten([[1,2,3], [4,5,[6,7,8]]]); // returns [1,2,3,4,5,[6,7,8]]
987function flatten(l) =
988 !is_list(l)? l :
989 [for (a=l) if (is_list(a)) (each a) else a];
990
991
992// Function: full_flatten()
993// Usage:
994// list = full_flatten(l);
995// Topics: Matrices, List Handling
996// See Also: column(), submatrix(), hstack(), flatten()
997// Description:
998// Collects in a list all elements recursively found in any level of the given list.
999// The output list is ordered in depth first order.
1000// Arguments:
1001// l = List to flatten.
1002// Example:
1003// l = full_flatten([[1,2,3], [4,5,[6,7,8]]]); // returns [1,2,3,4,5,6,7,8]
1004function full_flatten(l) =
1005 !is_list(l)? l :
1006 [for (a=l) if (is_list(a)) (each full_flatten(a)) else a];
1007
1008
1009
1010// Section: Set Manipulation
1011
1012// Function: set_union()
1013// Usage:
1014// s = set_union(a, b, [get_indices]);
1015// Topics: Set Handling, List Handling
1016// See Also: set_difference(), set_intersection()
1017// Description:
1018// Given two sets (lists with unique items), returns the set of unique items that are in either `a` or `b`.
1019// If `get_indices` is true, a list of indices into the new union set are returned for each item in `b`,
1020// in addition to returning the new union set. In this case, a 2-item list is returned, `[INDICES, NEWSET]`,
1021// where INDICES is the list of indices for items in `b`, and NEWSET is the new union set.
1022// Arguments:
1023// a = One of the two sets to merge.
1024// b = The other of the two sets to merge.
1025// get_indices = If true, indices into the new union set are also returned for each item in `b`. Returns `[INDICES, NEWSET]`. Default: false
1026// Example:
1027// set_a = [2,3,5,7,11];
1028// set_b = [1,2,3,5,8];
1029// set_u = set_union(set_a, set_b);
1030// // set_u now equals [2,3,5,7,11,1,8]
1031// set_v = set_union(set_a, set_b, get_indices=true);
1032// // set_v now equals [[5,0,1,2,6], [2,3,5,7,11,1,8]]
1033function set_union(a, b, get_indices=false) =
1034 assert( is_list(a) && is_list(b), "Invalid sets." )
1035 let(
1036 found1 = search(b, a),
1037 found2 = search(b, b),
1038 c = [ for (i=idx(b))
1039 if (found1[i] == [] && found2[i] == i)
1040 b[i]
1041 ],
1042 nset = concat(a, c)
1043 )
1044 ! get_indices ? nset :
1045 let(
1046 la = len(a),
1047 found3 = search(b, c),
1048 idxs = [ for (i=idx(b))
1049 (found1[i] != [])? found1[i] : la + found3[i]
1050 ]
1051 ) [idxs, nset];
1052
1053
1054// Function: set_difference()
1055// Usage:
1056// s = set_difference(a, b);
1057// Topics: Set Handling, List Handling
1058// See Also: set_union(), set_intersection()
1059// Description:
1060// Given two sets (lists with unique items), returns the set of items that are in `a`, but not `b`.
1061// Arguments:
1062// a = The starting set.
1063// b = The set of items to remove from set `a`.
1064// Example:
1065// set_a = [2,3,5,7,11];
1066// set_b = [1,2,3,5,8];
1067// set_d = set_difference(set_a, set_b);
1068// // set_d now equals [7,11]
1069function set_difference(a, b) =
1070 assert( is_list(a) && is_list(b), "Invalid sets." )
1071 let( found = search(a, b, num_returns_per_match=1) )
1072 [ for (i=idx(a)) if(found[i]==[]) a[i] ];
1073
1074
1075// Function: set_intersection()
1076// Usage:
1077// s = set_intersection(a, b);
1078// Topics: Set Handling, List Handling
1079// See Also: set_union(), set_difference()
1080// Description:
1081// Given two sets (lists with unique items), returns the set of items that are in both sets.
1082// Arguments:
1083// a = The starting set.
1084// b = The set of items to intersect with set `a`.
1085// Example:
1086// set_a = [2,3,5,7,11];
1087// set_b = [1,2,3,5,8];
1088// set_i = set_intersection(set_a, set_b);
1089// // set_i now equals [2,3,5]
1090function set_intersection(a, b) =
1091 assert( is_list(a) && is_list(b), "Invalid sets." )
1092 let( found = search(a, b, num_returns_per_match=1) )
1093 [ for (i=idx(a)) if(found[i]!=[]) a[i] ];
1094
1095
1096
1097
1098// vim: expandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap