1//////////////////////////////////////////////////////////////////////
2// LibFile: comparisons.scad
3// Functions for comparisons with lists, ordering and sorting
4// Includes:
5// include <BOSL2/std.scad>
6// FileGroup: Data Management
7// FileSummary: Comparisons and sorting.
8// FileFootnotes: STD=Included in std.scad
9//////////////////////////////////////////////////////////////////////
10
11
12// Section: List comparison operations
13
14// Function: approx()
15// Synopsis: Returns true if two values are equal to within a small epsilon value.
16// Topics: Comparisons
17// See Also: all_zero(), all_nonzero()
18// Usage:
19// test = approx(a, b, [eps])
20// Description:
21// Compares two numbers, vectors, or matrices. Returns true if they are closer than `eps` to each other.
22// Results are undefined if `a` and `b` are of different types, or if vectors or matrices contain non-numbers.
23// Arguments:
24// a = First value.
25// b = Second value.
26// eps = The maximum allowed difference between `a` and `b` that will return true. Defaults to 1e-9.
27// Example:
28// test1 = approx(-0.3333333333,-1/3); // Returns: true
29// test2 = approx(0.3333333333,1/3); // Returns: true
30// test3 = approx(0.3333,1/3); // Returns: false
31// test4 = approx(0.3333,1/3,eps=1e-3); // Returns: true
32// test5 = approx(PI,3.1415926536); // Returns: true
33// test6 = approx([0,0,sin(45)],[0,0,sqrt(2)/2]); // Returns: true
34function approx(a,b,eps=EPSILON) =
35 a == b? is_bool(a) == is_bool(b) :
36 is_num(a) && is_num(b)? abs(a-b) <= eps :
37 is_list(a) && is_list(b) && len(a) == len(b)? (
38 [] == [
39 for (i=idx(a))
40 let(aa=a[i], bb=b[i])
41 if(
42 is_num(aa) && is_num(bb)? abs(aa-bb) > eps :
43 !approx(aa,bb,eps=eps)
44 ) 1
45 ]
46 ) : false;
47
48
49// Function: all_zero()
50// Synopsis: Returns true if the value(s) given are aproximately zero.
51// Topics: Comparisons, List Handling
52// See Also: approx(), all_zero(), all_nonzero()
53// Usage:
54// x = all_zero(x, [eps]);
55// Description:
56// Returns true if its argument is approximately zero, to within `eps`.
57// If passed a list returns true if all its entries are approximately equal to zero.
58// Otherwise, returns false.
59// Arguments:
60// x = The value to check.
61// eps = The maximum allowed variance. Default: `EPSILON` (1e-9)
62// Example:
63// a = all_zero(0); // Returns: true.
64// b = all_zero(1e-3); // Returns: false.
65// c = all_zero([0,0,0]); // Returns: true.
66// d = all_zero([0,0,1e-3]); // Returns: false.
67function all_zero(x, eps=EPSILON) =
68 is_finite(x)? abs(x)<eps :
69 is_vector(x) && [for (xx=x) if(abs(xx)>eps) 1] == [];
70
71
72// Function: all_nonzero()
73// Synopsis: Returns true if the value(s) given are not aproximately zero.
74// Topics: Comparisons, List Handling
75// See Also: approx(), all_zero(), all_nonzero()
76// Usage:
77// test = all_nonzero(x, [eps]);
78// Description:
79// Returns true if its argument is finite and different from zero by `eps`.
80// If passed a list returns true if all the entries of the list are finite numbers that are different from zero by `eps`.
81// Otherwise, returns false.
82// Arguments:
83// x = The value to check.
84// eps = The maximum allowed variance. Default: `EPSILON` (1e-9)
85// Example:
86// a = all_nonzero(0); // Returns: false.
87// b = all_nonzero(1e-3); // Returns: true.
88// c = all_nonzero([0,0,0]); // Returns: false.
89// d = all_nonzero([0,0,1e-3]); // Returns: false.
90// e = all_nonzero([1e-3,1e-3,1e-3]); // Returns: true.
91function all_nonzero(x, eps=EPSILON) =
92 is_finite(x)? abs(x)>eps :
93 is_vector(x) && [for (xx=x) if(abs(xx)<eps) 1] == [];
94
95
96// Function: all_positive()
97// Synopsis: Returns true if the value(s) given are greater than zero.
98// Topics: Comparisons, List Handling
99// See Also: approx(), all_zero(), all_nonzero(), all_negative(), all_nonpositive(), all_nonnegative()
100// Usage:
101// test = all_positive(x,[eps]);
102// Description:
103// Returns true if the argument is finite and greater than zero, within epsilon tolerance if desired.
104// If passed a list returns true if all the entries are finite positive numbers.
105// Otherwise, returns false.
106// Arguments:
107// x = The value to check.
108// eps = Tolerance. Default: 0
109// Example:
110// a = all_positive(-2); // Returns: false.
111// b = all_positive(0); // Returns: false.
112// c = all_positive(2); // Returns: true.
113// d = all_positive([0,0,0]); // Returns: false.
114// e = all_positive([0,1,2]); // Returns: false.
115// f = all_positive([3,1,2]); // Returns: true.
116// g = all_positive([3,-1,2]); // Returns: false.
117function all_positive(x,eps=0) =
118 is_finite(x)? x>eps :
119 is_vector(x) && [for (xx=x) if(xx<=0) 1] == [];
120
121
122// Function: all_negative()
123// Synopsis: Returns true if the value(s) given are less than zero.
124// Topics: Comparisons, List Handling
125// See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_nonpositive(), all_nonnegative()
126// Usage:
127// test = all_negative(x, [eps]);
128// Description:
129// Returns true if the argument is finite and less than zero, within epsilon tolerance if desired.
130// If passed a list, returns true if all the elements are finite negative numbers.
131// Otherwise, returns false.
132// Arguments:
133// x = The value to check.
134// eps = tolerance. Default: 0
135// Example:
136// a = all_negative(-2); // Returns: true.
137// b = all_negative(0); // Returns: false.
138// c = all_negative(2); // Returns: false.
139// d = all_negative([0,0,0]); // Returns: false.
140// e = all_negative([0,1,2]); // Returns: false.
141// f = all_negative([3,1,2]); // Returns: false.
142// g = all_negative([3,-1,2]); // Returns: false.
143// h = all_negative([-3,-1,-2]); // Returns: true.
144function all_negative(x, eps=0) =
145 is_finite(x)? x<-eps :
146 is_vector(x) && [for (xx=x) if(xx>=-eps) 1] == [];
147
148
149// Function: all_nonpositive()
150// Synopsis: Returns true if the value(s) given are less than or equal to zero.
151// Topics: Comparisons, List Handling
152// See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_negative(), all_nonpositive(), all_nonnegative()
153// Usage:
154// all_nonpositive(x, [eps]);
155// Description:
156// Returns true if its argument is finite and less than or equal to zero.
157// If passed a list, returns true if all the elements are finite non-positive numbers.
158// Otherwise, returns false.
159// Arguments:
160// x = The value to check.
161// eps = tolerance. Default: 0
162// Example:
163// a = all_nonpositive(-2); // Returns: true.
164// b = all_nonpositive(0); // Returns: true.
165// c = all_nonpositive(2); // Returns: false.
166// d = all_nonpositive([0,0,0]); // Returns: true.
167// e = all_nonpositive([0,1,2]); // Returns: false.
168// f = all_nonpositive([3,1,2]); // Returns: false.
169// g = all_nonpositive([3,-1,2]); // Returns: false.
170// h = all_nonpositive([-3,-1,-2]); // Returns: true.
171function all_nonpositive(x,eps=0) =
172 is_num(x)? x<=eps :
173 is_vector(x) && [for (xx=x) if(xx>eps) 1] == [];
174
175
176// Function: all_nonnegative()
177// Synopsis: Returns true if the value(s) given are greater than or equal to zero.
178// Topics: Comparisons, List Handling
179// See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_negative(), all_nonpositive(), all_nonnegative()
180// Usage:
181// all_nonnegative(x, [eps]);
182// Description:
183// Returns true if the finite number passed to it is greater than or equal to zero.
184// If passed a list, returns true if all the elements are finite non-negative numbers.
185// Otherwise, returns false.
186// Arguments:
187// x = The value to check.
188// eps = tolerance. Default: 0
189// Example:
190// a = all_nonnegative(-2); // Returns: false.
191// b = all_nonnegative(0); // Returns: true.
192// c = all_nonnegative(2); // Returns: true.
193// d = all_nonnegative([0,0,0]); // Returns: true.
194// e = all_nonnegative([0,1,2]); // Returns: true.
195// f = all_nonnegative([0,-1,-2]); // Returns: false.
196// g = all_nonnegative([3,1,2]); // Returns: true.
197// h = all_nonnegative([3,-1,2]); // Returns: false.
198// i = all_nonnegative([-3,-1,-2]); // Returns: false.
199function all_nonnegative(x,eps=0) =
200 is_num(x)? x>=-eps :
201 is_vector(x) && [for (xx=x) if(xx<-eps) 1] == [];
202
203
204// Function: all_equal()
205// Synopsis: Returns true if all items in a list are approximately equal to each other.
206// Topics: Comparisons, List Handling
207// See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_negative(), all_nonpositive(), all_nonnegative()
208// Usage:
209// b = all_equal(vec, [eps]);
210// Description:
211// Returns true if all of the entries in vec are equal to each other, or approximately equal to each other if eps is set.
212// Arguments:
213// vec = vector to check
214// eps = Set to tolerance for approximate equality. Default: 0
215function all_equal(vec,eps=0) =
216 eps==0 ? [for(v=vec) if (v!=vec[0]) v] == []
217 : [for(v=vec) if (!approx(v,vec[0],eps)) v] == [];
218
219
220
221// Function: are_ends_equal()
222// Synopsis: Returns true if the first and last items in a list are approximately equal.
223// Topics: Comparisons, List Handling
224// See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_negative(), all_nonpositive(), all_nonnegative()
225// Usage:
226// are_ends_equal(list, [eps]);
227// Description:
228// Returns true if the first and last points in the given list are equal to within epsilon.
229// Arguments:
230// list = list to check
231// eps = Tolerance for approximate equality. Default: `EPSILON` (1e-9)
232function are_ends_equal(list, eps=EPSILON) =
233 assert(is_list(list) && len(list)>0, "Must give a nonempty list")
234 approx(list[0], list[len(list)-1], eps=eps);
235
236
237// Function: is_increasing()
238// Synopsis: Returns true if exery item in a list is greater than the previous item.
239// Topics: Comparisons, List Handling
240// See Also: max_index(), min_index(), is_increasing(), is_decreasing()
241// Usage:
242// bool = is_increasing(list, [strict]);
243// Description:
244// Returns true if the list is (non-strictly) increasing, or strictly increasing if `strict=true`.
245// The list can be a list of any items that OpenSCAD can compare, or it can be a string which will be
246// evaluated character by character.
247// Arguments:
248// list = list (or string) to check
249// strict = set to true to test that list is strictly increasing. Default: false
250// Example:
251// a = is_increasing([1,2,3,4]); // Returns: true
252// b = is_increasing([1,3,2,4]); // Returns: false
253// c = is_increasing([1,3,3,4]); // Returns: true
254// d = is_increasing([1,3,3,4],strict=true); // Returns: false
255// e = is_increasing([4,3,2,1]); // Returns: false
256function is_increasing(list,strict=false) =
257 assert(is_list(list)||is_string(list))
258 strict ? len([for (p=pair(list)) if(p.x>=p.y) true])==0
259 : len([for (p=pair(list)) if(p.x>p.y) true])==0;
260
261
262// Function: is_decreasing()
263// Synopsis: Returns true if exery item in a list is less than the previous item.
264// Topics: Comparisons, List Handling
265// See Also: max_index(), min_index(), is_increasing(), is_decreasing()
266// Usage:
267// bool = is_decreasing(list, [strict]);
268// Description:
269// Returns true if the list is (non-strictly) decreasing, or strictly decreasing if `strict=true`.
270// The list can be a list of any items that OpenSCAD can compare, or it can be a string which will be
271// evaluated character by character.
272// Arguments:
273// list = list (or string) to check
274// strict = set to true to test that list is strictly decreasing. Default: false
275// Example:
276// a = is_decreasing([1,2,3,4]); // Returns: false
277// b = is_decreasing([4,2,3,1]); // Returns: false
278// c = is_decreasing([4,3,2,1]); // Returns: true
279function is_decreasing(list,strict=false) =
280 assert(is_list(list)||is_string(list))
281 strict ? len([for (p=pair(list)) if(p.x<=p.y) true])==0
282 : len([for (p=pair(list)) if(p.x<p.y) true])==0;
283
284
285
286
287function _type_num(x) =
288 is_undef(x)? 0 :
289 is_bool(x)? 1 :
290 is_num(x)? 2 :
291 is_nan(x)? 3 :
292 is_string(x)? 4 :
293 is_list(x)? 5 : 6;
294
295
296// Function: compare_vals()
297// Synopsis: Compares two values, possibly of different type.
298// Topics: Comparisons, List Handling
299// See Also: approx(), is_increasing(), is_decreasing()
300// Usage:
301// test = compare_vals(a, b);
302// Description:
303// Compares two values. Lists are compared recursively.
304// Returns a negative value if a<b. Returns a positive value if a>b. Returns 0 if a==b.
305// If types are not the same, then undef < bool < nan < num < str < list < range.
306// Arguments:
307// a = First value to compare.
308// b = Second value to compare.
309function compare_vals(a, b) =
310 (a==b)? 0 :
311 let(t1=_type_num(a), t2=_type_num(b)) (t1!=t2)? (t1-t2) :
312 is_list(a)? compare_lists(a,b) :
313 is_nan(a)? 0 :
314 (a<b)? -1 : (a>b)? 1 : 0;
315
316
317// Function: compare_lists()
318// Synopsis: Compares two lists of values, possibly of different type.
319// Topics: Comparisons, List Handling
320// See Also: compare_vals(), approx(), is_increasing(), is_decreasing()
321// Usage:
322// test = compare_lists(a, b)
323// Description:
324// Compare contents of two lists using `compare_vals()`.
325// Returns a negative number if `a`<`b`.
326// Returns 0 if `a`==`b`.
327// Returns a positive number if `a`>`b`.
328// Arguments:
329// a = First list to compare.
330// b = Second list to compare.
331function compare_lists(a, b) =
332 a==b? 0 :
333 let(
334 cmps = [
335 for (i = [0:1:min(len(a),len(b))-1])
336 let( cmp = compare_vals(a[i],b[i]) )
337 if (cmp!=0) cmp
338 ]
339 )
340 cmps==[]? (len(a)-len(b)) : cmps[0];
341
342
343
344// Section: Finding the index of the minimum or maximum of a list
345
346
347// Function: min_index()
348// Synopsis: Returns the index of the minimal value in the given list.
349// Topics: List Handling
350// See Also: max_index(), is_increasing(), is_decreasing()
351// Usage:
352// idx = min_index(vals);
353// idxlist = min_index(vals, all=true);
354// Description:
355// Returns the index of the first occurrence of the minimum value in the given list.
356// If `all` is true then returns a list of all indices where the minimum value occurs.
357// Arguments:
358// vals = vector of values
359// all = set to true to return indices of all occurences of the minimum. Default: false
360// Example:
361// a = min_index([5,3,9,6,2,7,8,2,1]); // Returns: 8
362// b = min_index([5,3,9,6,2,7,8,2,7],all=true); // Returns: [4,7]
363function min_index(vals, all=false) =
364 assert( is_vector(vals), "Invalid or list of numbers.")
365 all ? search(min(vals),vals,0) : search(min(vals), vals)[0];
366
367
368// Function: max_index()
369// Synopsis: Returns the index of the minimal value in the given list.
370// Topics: List Handling
371// See Also: min_index(), is_increasing(), is_decreasing()
372// Usage:
373// idx = max_index(vals);
374// idxlist = max_index(vals, all=true);
375// Description:
376// Returns the index of the first occurrence of the maximum value in the given list.
377// If `all` is true then returns a list of all indices where the maximum value occurs.
378// Arguments:
379// vals = vector of values
380// all = set to true to return indices of all occurences of the maximum. Default: false
381// Example:
382// max_index([5,3,9,6,2,7,8,9,1]); // Returns: 2
383// max_index([5,3,9,6,2,7,8,9,1],all=true); // Returns: [2,7]
384function max_index(vals, all=false) =
385 assert( is_vector(vals) && len(vals)>0 , "Invalid or empty list of numbers.")
386 all ? search(max(vals),vals,0) : search(max(vals), vals)[0];
387
388
389// Section: Dealing with duplicate list entries
390
391
392// Function: find_approx()
393// Synopsis: Finds the indexes of the item(s) in the given list that are aproximately the given value.
394// Topics: List Handling
395// See Also: in_list()
396// Usage:
397// idx = find_approx(val, list, [start=], [eps=]);
398// indices = find_approx(val, list, all=true, [start=], [eps=]);
399// Description:
400// Finds the first item in `list` that matches `val` to within `eps` tolerance, returning the index. Returns `undef` if there is no match.
401// If `all=true` then returns all the items that agree within `eps` and returns the empty list if no such items exist.
402// Arguments:
403// val = The value to search for.
404// list = The list to search.
405// ---
406// start = The index to start searching from. Default: 0
407// all = If true, returns a list of all matching item indices. Default: false
408// eps = The maximum allowed floating point rounding error for numeric comparisons. Default: EPSILON (1e-9)
409// Example:
410// find_approx(3,[4,5,3.01,2,2.99], eps=0.1); // Returns 2
411// find_approx(9,[4,5,3.01,2,2.99], eps=0.1); // Returns undef
412// find_approx(3,[4,5,3.01,2,2.99], all=true, eps=0.1); // Returns [2,4]
413// find_approx(9,[4,5,3.01,2,2.99], all=true, eps=0.1); // Returns []
414function find_approx(val, list, start=0, all=false, eps=EPSILON) =
415 all ? [for (i=[start:1:len(list)-1]) if (approx(val, list[i], eps=eps)) i]
416 : __find_approx(val, list, eps=eps, i=start);
417
418function __find_approx(val, list, eps, i=0) =
419 i >= len(list)? undef :
420 approx(val, list[i], eps=eps)
421 ? i
422 : __find_approx(val, list, eps=eps, i=i+1);
423
424
425
426// Function: deduplicate()
427// Synopsis: Returns a list with all consecutive duplicate values removed.
428// Topics: List Handling
429// See Also: deduplicate_indexed()
430// Usage:
431// list = deduplicate(list, [closed], [eps]);
432// Description:
433// Removes consecutive duplicate items in a list.
434// When `eps` is zero, the comparison between consecutive items is exact.
435// Otherwise, when all list items and subitems are numbers, the comparison is within the tolerance `eps`.
436// Unlike `unique()` only consecutive duplicates are removed and the list is *not* sorted.
437// If `closed` is set to true then the first and last entries in `list` are treated as adjacent,
438// so all trailing items that match `list[0]` are dropped.
439// Arguments:
440// list = The list to deduplicate.
441// closed = If true, treats first and last list entry as adjacent. Default: false
442// eps = The maximum tolerance between items. Default: EPSILON
443// Example:
444// a = deduplicate([8,3,4,4,4,8,2,3,3,8,8]); // Returns: [8,3,4,8,2,3,8]
445// b = deduplicate(closed=true, [8,3,4,4,4,8,2,3,3,8,8]); // Returns: [8,3,4,8,2,3]
446// c = deduplicate("Hello"); // Returns: "Helo"
447// d = deduplicate([[3,4],[7,2],[7,1.99],[1,4]],eps=0.1); // Returns: [[3,4],[7,2],[1,4]]
448// e = deduplicate([[7,undef],[7,undef],[1,4],[1,4+1e-12]],eps=0); // Returns: [[7,undef],[1,4],[1,4+1e-12]]
449function deduplicate(list, closed=false, eps=EPSILON) =
450 assert(is_list(list)||is_string(list))
451 let(
452 l = len(list),
453 end = l-(closed?0:1)
454 )
455 is_string(list) ? str_join([for (i=[0:1:l-1]) if (i==end || list[i] != list[(i+1)%l]) list[i]]) :
456 eps==0 ? [for (i=[0:1:l-1]) if (i==end || list[i] != list[(i+1)%l]) list[i]] :
457 [for (i=[0:1:l-1]) if (i==end || !approx(list[i], list[(i+1)%l], eps)) list[i]];
458
459
460// Function: deduplicate_indexed()
461// Synopsis: Takes a list of indices into a list of values, and returns a list of indices whose values are not consecutively the same.
462// Topics: List Handling
463// See Also: deduplicate()
464// Usage:
465// new_idxs = deduplicate_indexed(list, indices, [closed], [eps]);
466// Description:
467// Given a list, and a list of indices, removes consecutive indices corresponding to list values that are equal
468// or approximately equal.
469// Arguments:
470// list = The list that the indices index into.
471// indices = The list of indices to deduplicate.
472// closed = If true, drops trailing indices if their list value matches the list value corresponding to the first index.
473// eps = The maximum difference to allow between numbers or vectors.
474// Example:
475// a = deduplicate_indexed([8,6,4,6,3], [1,4,3,1,2,2,0,1]); // Returns: [1,4,3,2,0,1]
476// b = deduplicate_indexed([8,6,4,6,3], [1,4,3,1,2,2,0,1], closed=true); // Returns: [1,4,3,2,0]
477// c = deduplicate_indexed([[7,undef],[7,undef],[1,4],[1,4],[1,4+1e-12]],eps=0); // Returns: [0,2,4]
478function deduplicate_indexed(list, indices, closed=false, eps=EPSILON) =
479 assert(is_list(list)||is_string(list), "Improper list or string.")
480 indices==[]? [] :
481 assert(is_vector(indices), "Indices must be a list of numbers.")
482 let(
483 ll = len(list),
484 l = len(indices),
485 end = l-(closed?0:1)
486 ) [
487 for (i = [0:1:l-1]) let(
488 idx1 = indices[i],
489 idx2 = indices[(i+1)%l],
490 a = assert(idx1>=0,"Bad index.")
491 assert(idx1<len(list),"Bad index in indices.")
492 list[idx1],
493 b = assert(idx2>=0,"Bad index.")
494 assert(idx2<len(list),"Bad index in indices.")
495 list[idx2],
496 eq = (a == b)? true :
497 (a*0 != b*0) || (eps==0)? false :
498 is_num(a) || is_vector(a) ? approx(a, b, eps=eps)
499 : false
500 )
501 if (i==end || !eq) indices[i]
502 ];
503
504
505
506
507// Function: list_wrap()
508// Synopsis: Returns a list whose last value is the same as the first.
509// Topics: List Handling, Paths
510// See Also: list_unwrap(), deduplicate()
511// Usage:
512// list_wrap(path, [eps]);
513// Description:
514// Force a list to wrap around so that its last point is equal to its first point: if the first and last entries are equal, simply returns the list unchanged.
515// Otherwise returns the list with the first point duplicated at the end of the list. Comparisons are done to the tolerance `eps`. Lists of length 0 or
516// 1 are returned unchanged.
517// Arguments:
518// list = list to unwrap
519// eps = epsilon for comparison. Default: EPSILON (1e-9)
520
521function list_wrap(list, eps=EPSILON) =
522 assert(is_list(list))
523 len(list)<2 || are_ends_equal(list,eps=eps)? list : [each list, list[0]];
524
525
526function cleanup_path(list,eps=EPSILON) =
527 echo("***** Function cleanup_path() has been replaced by list_unwrap() and will be removed in a future version *****")
528 list_unwrap(list,eps);
529
530function close_path(list,eps=EPSILON) =
531 echo("***** Function close_path() has been replaced by list_wrap() and will be removed in a future version *****")
532 list_wrap(list,eps);
533
534// Function: list_unwrap()
535// Synopsis: Removes the last item of a list if its first and last values are equal.
536// Topics: List Handling, Paths
537// See Also: list_wrap(), deduplicate()
538// Usage:
539// list_unwrap(list, [eps]);
540// Description:
541// If a list's last point matches its first point then delete the last point. Inverse operation to {{list_wrap()}}. Note that if the first/last points
542// are repeated then the output may still have the first point equal to the last point. Comparisons are done to the tolerance `eps`. If the list has
543// length 0 or 1 it is returned unchanged.
544// Arguments:
545// list = list to unwrap
546// eps = epsilon for comparison. Default: EPSILON (1e-9)
547function list_unwrap(list, eps=EPSILON) =
548 assert(is_list(list))
549 len(list)>=2 && are_ends_equal(list,eps=eps)? [for (i=[0:1:len(list)-2]) list[i]] : list;
550
551
552
553// Function: unique()
554// Synopsis: Returns a sorted list with all duplicates removed.
555// Topics: List Handling
556// See Also: shuffle(), sort(), sortidx(), unique_count()
557// Usage:
558// ulist = unique(list);
559// Description:
560// Given a string or a list returns the sorted string or the sorted list with all repeated items removed.
561// The sorting order of non homogeneous lists is the function `sort` order.
562// Arguments:
563// list = The list to process.
564// Example:
565// sorted = unique([5,2,8,3,1,3,8,7,5]); // Returns: [1,2,3,5,7,8]
566// sorted = unique("axdbxxc"); // Returns: "abcdx"
567// sorted = unique([true,2,"xba",[1,0],true,[0,0],3,"a",[0,0],2]); // Returns: [true,2,3,"a","xba",[0,0],[1,0]]
568function unique(list) =
569 assert(is_list(list)||is_string(list), "Invalid input." )
570 is_string(list)? str_join(unique([for (x = list) x])) :
571 len(list)<=1? list :
572 is_homogeneous(list,1) && ! is_list(list[0])
573 ? _unique_sort(list)
574 : let( sorted = sort(list))
575 [
576 for (i=[0:1:len(sorted)-1])
577 if (i==0 || (sorted[i] != sorted[i-1]))
578 sorted[i]
579 ];
580
581function _unique_sort(l) =
582 len(l) <= 1 ? l :
583 let(
584 pivot = l[floor(len(l)/2)],
585 equal = [ for(li=l) if( li==pivot) li ],
586 lesser = [ for(li=l) if( li<pivot ) li ],
587 greater = [ for(li=l) if( li>pivot) li ]
588 )
589 concat(
590 _unique_sort(lesser),
591 equal[0],
592 _unique_sort(greater)
593 );
594
595
596// Function: unique_count()
597// Synopsis: Returns a sorted list of unique items with counts.
598// Topics: List Handling
599// See Also: shuffle(), sort(), sortidx(), unique()
600// Usage:
601// sorted_counts = unique_count(list);
602// Description:
603// Returns `[sorted,counts]` where `sorted` is a sorted list of the unique items in `list` and `counts` is a list such
604// that `count[i]` gives the number of times that `sorted[i]` appears in `list`.
605// Arguments:
606// list = The list to analyze.
607// Example:
608// sorted = unique([5,2,8,3,1,3,8,3,5]); // Returns: [ [1,2,3,5,8], [1,1,3,2,2] ]
609function unique_count(list) =
610 assert(is_list(list) || is_string(list), "Invalid input." )
611 list == [] ? [[],[]] :
612 is_homogeneous(list,1) && ! is_list(list[0])
613 ? let( sorted = _group_sort(list) )
614 [ [for(s=sorted) s[0] ], [for(s=sorted) len(s) ] ]
615 : let(
616 list = sort(list),
617 ind = [0, for(i=[1:1:len(list)-1]) if (list[i]!=list[i-1]) i]
618 )
619 [ select(list,ind), deltas( concat(ind,[len(list)]) ) ];
620
621
622
623// Section: Sorting
624
625
626// returns true for valid index specifications idx in the interval [imin, imax)
627// note that idx can't have any value greater or EQUAL to imax
628// this allows imax=INF as a bound to numerical lists
629function _valid_idx(idx,imin,imax) =
630 is_undef(idx)
631 || ( is_finite(idx)
632 && ( is_undef(imin) || idx>=imin )
633 && ( is_undef(imax) || idx< imax ) )
634 || ( is_list(idx)
635 && ( is_undef(imin) || min(idx)>=imin )
636 && ( is_undef(imax) || max(idx)< imax ) )
637 || ( is_range(idx)
638 && ( is_undef(imin) || (idx[1]>0 && idx[0]>=imin ) || (idx[1]<0 && idx[0]<=imax ) )
639 && ( is_undef(imax) || (idx[1]>0 && idx[2]<=imax ) || (idx[1]<0 && idx[2]>=imin ) ) );
640
641// idx should be an index of the arrays l[i]
642function _group_sort_by_index(l,idx) =
643 len(l) == 0 ? [] :
644 len(l) == 1 ? [l] :
645 let(
646 pivot = l[floor(len(l)/2)][idx],
647 equal = [ for(li=l) if( li[idx]==pivot) li ],
648 lesser = [ for(li=l) if( li[idx]< pivot) li ],
649 greater = [ for(li=l) if( li[idx]> pivot) li ]
650 )
651 concat(
652 _group_sort_by_index(lesser,idx),
653 [equal],
654 _group_sort_by_index(greater,idx)
655 );
656
657
658function _group_sort(l) =
659 len(l) == 0 ? [] :
660 len(l) == 1 ? [l] :
661 let(
662 pivot = l[floor(len(l)/2)],
663 equal = [ for(li=l) if( li==pivot) li ],
664 lesser = [ for(li=l) if( li< pivot) li ],
665 greater = [ for(li=l) if( li> pivot) li ]
666 )
667 concat(
668 _group_sort(lesser),
669 [equal],
670 _group_sort(greater)
671 );
672
673
674// Sort a vector of scalar values with the native comparison operator
675// all elements should have the same type.
676function _sort_scalars(arr) =
677 len(arr)<=1 ? arr :
678 let(
679 pivot = arr[floor(len(arr)/2)],
680 lesser = [ for (y = arr) if (y < pivot) y ],
681 equal = [ for (y = arr) if (y == pivot) y ],
682 greater = [ for (y = arr) if (y > pivot) y ]
683 )
684 concat( _sort_scalars(lesser), equal, _sort_scalars(greater) );
685
686
687// lexical sort of a homogeneous list of vectors
688// uses native comparison operator
689function _sort_vectors(arr, _i=0) =
690 len(arr)<=1 || _i>=len(arr[0]) ? arr :
691 let(
692 pivot = arr[floor(len(arr)/2)][_i],
693 lesser = [ for (entry=arr) if (entry[_i] < pivot ) entry ],
694 equal = [ for (entry=arr) if (entry[_i] == pivot ) entry ],
695 greater = [ for (entry=arr) if (entry[_i] > pivot ) entry ]
696 )
697 concat(
698 _sort_vectors(lesser, _i ),
699 _sort_vectors(equal, _i+1 ),
700 _sort_vectors(greater, _i ) );
701
702
703// lexical sort of a homogeneous list of vectors by the vector components with indices in idxlist
704// all idxlist indices should be in the range of the vector dimensions
705// idxlist must be undef or a simple list of numbers
706// uses native comparison operator
707function _sort_vectors(arr, idxlist, _i=0) =
708 len(arr)<=1 || ( is_list(idxlist) && _i>=len(idxlist) ) || _i>=len(arr[0]) ? arr :
709 let(
710 k = is_list(idxlist) ? idxlist[_i] : _i,
711 pivot = arr[floor(len(arr)/2)][k],
712 lesser = [ for (entry=arr) if (entry[k] < pivot ) entry ],
713 equal = [ for (entry=arr) if (entry[k] == pivot ) entry ],
714 greater = [ for (entry=arr) if (entry[k] > pivot ) entry ]
715 )
716 concat(
717 _sort_vectors(lesser, idxlist, _i ),
718 _sort_vectors(equal, idxlist, _i+1),
719 _sort_vectors(greater, idxlist, _i ) );
720
721
722// sorting using compare_vals(); returns indexed list when `indexed==true`
723function _sort_general(arr, idx=undef, indexed=false) =
724 (len(arr)<=1) ? arr :
725 ! indexed && is_undef(idx)
726 ? _lexical_sort(arr)
727 : let( labeled = is_undef(idx) ? [for(i=idx(arr)) [i,arr[i]]]
728 : [for(i=idx(arr)) [i, for(j=idx) arr[i][j]]],
729 arrind = _indexed_sort(labeled))
730 indexed
731 ? arrind
732 : [for(i=arrind) arr[i]];
733
734// lexical sort using compare_vals()
735function _lexical_sort(arr) =
736 len(arr)<=1? arr :
737 let( pivot = arr[floor(len(arr)/2)] )
738 let(
739 lesser = [ for (entry=arr) if (compare_vals(entry, pivot) <0 ) entry ],
740 equal = [ for (entry=arr) if (compare_vals(entry, pivot)==0 ) entry ],
741 greater = [ for (entry=arr) if (compare_vals(entry, pivot) >0 ) entry ]
742 )
743 concat(_lexical_sort(lesser), equal, _lexical_sort(greater));
744
745
746// given a list of pairs, return the first element of each pair of the list sorted by the second element of the pair
747// the sorting is done using compare_vals()
748function _indexed_sort(arrind) =
749 arrind==[] ? [] : len(arrind)==1? [arrind[0][0]] :
750 let( pivot = arrind[floor(len(arrind)/2)][1] )
751 let(
752 lesser = [ for (entry=arrind) if (compare_vals(entry[1], pivot) <0 ) entry ],
753 equal = [ for (entry=arrind) if (compare_vals(entry[1], pivot)==0 ) entry[0] ],
754 greater = [ for (entry=arrind) if (compare_vals(entry[1], pivot) >0 ) entry ]
755 )
756 concat(_indexed_sort(lesser), equal, _indexed_sort(greater));
757
758
759// Function: sort()
760// Synopsis: Returns a sorted list.
761// Topics: List Handling
762// See Also: shuffle(), sortidx(), unique(), unique_count(), group_sort()
763// Usage:
764// slist = sort(list, [idx]);
765// Description:
766// Sorts the given list in lexicographic order. The sort is stable, meaning equivalent items will not change order.
767// If the input is a homogeneous simple list or a homogeneous
768// list of vectors (see function is_homogeneous), the sorting method uses the native comparison operator and is faster.
769// When sorting non homogeneous list the elements are compared with `compare_vals`, with types ordered according to
770// `undef < boolean < number < string < list`. Comparison of lists is recursive.
771// When comparing vectors, homogeneous or not, the parameter `idx` may be used to select the components to compare.
772// Note that homogeneous lists of vectors may contain mixed types provided that for any two list elements
773// list[i] and list[j] satisfies type(list[i][k])==type(list[j][k]) for all k.
774// Strings are allowed as any list element and are compared with the native operators although no substring
775// comparison is possible.
776// Arguments:
777// list = The list to sort.
778// idx = If given, do the comparison based just on the specified index, range or list of indices.
779// Example:
780// // Homogeneous lists
781// l1 = [45,2,16,37,8,3,9,23,89,12,34];
782// sorted1 = sort(l1); // Returns [2,3,8,9,12,16,23,34,37,45,89]
783// l2 = [["oat",0], ["cat",1], ["bat",3], ["bat",2], ["fat",3]];
784// sorted2 = sort(l2); // Returns: [["bat",2],["bat",3],["cat",1],["fat",3],["oat",0]]
785// // Non-homegenous list
786// l3 = [[4,0],[7],[3,9],20,[4],[3,1],[8]];
787// sorted3 = sort(l3); // Returns: [20,[3,1],[3,9],[4],[4,0],[7],[8]]
788function sort(list, idx=undef) =
789 assert(is_list(list)||is_string(list), "Invalid input." )
790 is_string(list)? str_join(sort([for (x = list) x],idx)) :
791 !is_list(list) || len(list)<=1 ? list :
792 is_homogeneous(list,1)
793 ? let(size = list_shape(list[0]))
794 size==0 ? _sort_scalars(list)
795 : len(size)!=1 ? _sort_general(list,idx)
796 : is_undef(idx) ? _sort_vectors(list)
797 : assert( _valid_idx(idx) , "Invalid indices.")
798 _sort_vectors(list,[for(i=idx) i])
799 : _sort_general(list,idx);
800
801
802// Function: sortidx()
803// Synopsis: Returns a list of sorted indices into a list.
804// Topics: List Handling
805// See Also: shuffle(), sort(), group_sort(), unique(), unique_count()
806// Usage:
807// idxlist = sortidx(list, [idx]);
808// Description:
809// Given a list, sort it as function `sort()`, and returns
810// a list of indexes into the original list in that sorted order.
811// The sort is stable, so equivalent items will not change order.
812// If you iterate the returned list in order, and use the list items
813// to index into the original list, you will be iterating the original
814// values in sorted order.
815// Arguments:
816// list = The list to sort.
817// idx = If given, do the comparison based just on the specified index, range or list of indices.
818// Example:
819// lst = ["d","b","e","c"];
820// idxs = sortidx(lst); // Returns: [1,3,0,2]
821// ordered = select(lst, idxs); // Returns: ["b", "c", "d", "e"]
822// Example:
823// lst = [
824// ["foo", 88, [0,0,1], false],
825// ["bar", 90, [0,1,0], true],
826// ["baz", 89, [1,0,0], false],
827// ["qux", 23, [1,1,1], true]
828// ];
829// idxs1 = sortidx(lst, idx=1); // Returns: [3,0,2,1]
830// idxs2 = sortidx(lst, idx=0); // Returns: [1,2,0,3]
831// idxs3 = sortidx(lst, idx=[1,3]); // Returns: [3,0,2,1]
832function sortidx(list, idx=undef) =
833 assert(is_list(list)||is_string(list), "Invalid list." )
834 is_homogeneous(list,1)
835 ? let(
836 size = list_shape(list[0]),
837 aug = ! (size==0 || len(size)==1) ? 0 // for general sorting
838 : [for(i=[0:len(list)-1]) concat(i,list[i])], // for scalar or vector sorting
839 lidx = size==0? [1] : // scalar sorting
840 len(size)==1
841 ? is_undef(idx) ? [for(i=[0:len(list[0])-1]) i+1] // vector sorting
842 : [for(i=idx) i+1] // vector sorting
843 : 0 // just to signal
844 )
845 assert( ! ( size==0 && is_def(idx) ),
846 "The specification of `idx` is incompatible with scalar sorting." )
847 assert( _valid_idx(idx) , "Invalid indices." )
848 lidx!=0
849 ? let( lsort = _sort_vectors(aug,lidx) )
850 [for(li=lsort) li[0] ]
851 : _sort_general(list,idx,indexed=true)
852 : _sort_general(list,idx,indexed=true);
853
854
855
856
857// Function: group_sort()
858// Synopsis: Returns a sorted list of groups of values.
859// Topics: List Handling
860// See Also: group_data(), shuffle(), sort(), sortidx(), unique(), unique_count()
861// Usage:
862// ulist = group_sort(list,[idx]);
863// Description:
864// Given a list of numbers, sorts the list into a sequence of lists, where each list contains any repeated values.
865// If there are no repeated values the output will be a list of singleton lists.
866// If you apply {{flatten()}} to the output, the result will be a simple sorted list.
867// .
868// When the input is a list of lists, the sorting is done based on index `idx` of the entries in `list`.
869// In this case, `list[i][idx]` must be a number for every `i`, and the entries in `list` are grouped
870// together in the output if they match at index `idx`. This function can be used to group together
871// items that are tagged with the same index.
872// Arguments:
873// list = The list to sort.
874// idx = If input is a list of lists, index to sort on. Default: 0.
875// Example:
876// sorted = group_sort([5,2,8,3,1,3,8,7,5]); // Returns: [[1],[2],[3,3],[5,5],[7],[8,8]]
877// // Next example returns: [ [[2,"b"],[2,"e"]], [[3,"d"]], [[5,"a"],[5,"c"]] ]
878// sorted2 = group_sort([[5,"a"],[2,"b"], [5,"c"], [3,"d"], [2,"e"] ], idx=0);
879function group_sort(list, idx) =
880 assert(is_list(list), "Input should be a list." )
881 assert(is_undef(idx) || (is_int(idx) && idx>=0) , "Invalid index." )
882 len(list)<=1 ? [list] :
883 is_vector(list)? assert(is_undef(idx),"Cannot give idx with a vector input") _group_sort(list) :
884 let( idx = default(idx,0) )
885 assert( [for(entry=list) if(!is_list(entry) || len(entry)<idx || !is_num(entry[idx]) ) 1]==[],
886 "Some entry of the list is a list shorter than `idx` or the indexed entry of it is not a number.")
887 _group_sort_by_index(list,idx);
888
889
890
891// Function: group_data()
892// Synopsis: Groups list data by integer group numbers.
893// Topics: List Handling
894// See Also: group_sort(), shuffle(), sort(), sortidx(), unique(), unique_count()
895// Usage:
896// groupings = group_data(groups, values);
897// Description:
898// Given a list of integer group numbers, and an equal-length list of values,
899// returns a list of groups with the values sorted into the corresponding groups.
900// Ie: if you have a groups index list of [2,3,2] and values of ["A","B","C"], then
901// the values "A" and "C" will be put in group 2, and "B" will be in group 3.
902// Groups that have no values grouped into them will be an empty list. So the
903// above would return [[], [], ["A","C"], ["B"]]
904// Arguments:
905// groups = A list of integer group index numbers.
906// values = A list of values to sort into groups.
907// Example:
908// groups = group_data([1,2,0], ["A","B","C"]); // Returns [["B"],["C"],["A"]]
909// Example:
910// groups = group_data([1,3,1], ["A","B","C"]); // Returns [[],["A","C"],[],["B"]]
911function group_data(groups, values) =
912 assert(all_integer(groups) && all_nonnegative(groups))
913 assert(is_list(values))
914 assert(len(groups)==len(values),
915 "The groups and values arguments should be lists of matching length.")
916 let( sorted = _group_sort_by_index([for(i=idx(groups))[groups[i],values[i]]],0) )
917 // retrieve values and insert []
918 [
919 for (i = idx(sorted))
920 let(
921 a = i==0? 0 : sorted[i-1][0][0]+1,
922 g0 = sorted[i]
923 )
924 each [
925 for (j = [a:1:g0[0][0]-1]) [],
926 [for (g1 = g0) g1[1]]
927 ]
928 ];
929
930
931// Function: list_smallest()
932// Synopsis: Returns the `k` smallest values in the list, in arbitrary order.
933// Topics: List Handling
934// See Also: group_sort(), shuffle(), sort(), sortidx(), unique(), unique_count()
935// Usage:
936// small = list_smallest(list, k)
937// Description:
938// Returns a set of the k smallest items in list in arbitrary order. The items must be
939// mutually comparable with native OpenSCAD comparison operations. You will get "undefined operation"
940// errors if you provide invalid input.
941// Arguments:
942// list = list to process
943// k = number of items to return
944function list_smallest(list, k) =
945 assert(is_list(list))
946 assert(is_int(k) && k>=0, "k must be nonnegative")
947 let(
948 v = list[rand_int(0,len(list)-1,1)[0]],
949 smaller = [for(li=list) if(li<v) li ],
950 equal = [for(li=list) if(li==v) li ]
951 )
952 len(smaller) == k ? smaller :
953 len(smaller)<k && len(smaller)+len(equal) >= k ? [ each smaller, for(i=[1:k-len(smaller)]) v ] :
954 len(smaller) > k ? list_smallest(smaller, k) :
955 let( bigger = [for(li=list) if(li>v) li ] )
956 concat(smaller, equal, list_smallest(bigger, k-len(smaller) -len(equal)));
957
958
959
960// vim: expandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap