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