Functions for comparisons with lists, ordering and sorting

To use, add the following lines to the beginning of your file:

include <BOSL2/std.scad>

1. Section: List comparison operations

   • approx() – Returns true if two values are equal to within a small epsilon value.
   • all_zero() – Returns true if the value(s) given are aproximately zero.
   • all_nonzero() – Returns true if the value(s) given are not aproximately zero.
   • all_positive() – Returns true if the value(s) given are greater than zero.
   • all_negative() – Returns true if the value(s) given are less than zero.
   • all_nonpositive() – Returns true if the value(s) given are less than or equal to zero.
   • all_nonnegative() – Returns true if the value(s) given are greater than or equal to zero.
   • all_equal() – Returns true if all items in a list are approximately equal to each other.
   • are_ends_equal() – Returns true if the first and last items in a list are approximately equal.
   • is_increasing() – Returns true if every item in a list is greater than the previous item.
   • is_decreasing() – Returns true if exery item in a list is less than the previous item.
   • compare_vals() – Compares two values, possibly of different type.
   • compare_lists() – Compares two lists of values, possibly of different type.

2. Section: Finding the index of the minimum or maximum of a list

   • min_index() – Returns the index of the minimal value in the given list.
   • max_index() – Returns the index of the minimal value in the given list.

3. Section: Dealing with duplicate list entries

   • find_approx() – Finds the indexes of the item(s) in the given list that are aproximately the given value.
   • deduplicate() – Returns a list with all consecutive duplicate values removed.
   • deduplicate_indexed() – Takes a list of indices into a list of values, and returns a list of indices whose values are not consecutively the same.
   • list_wrap() – Returns a list whose last value is the same as the first.
   • list_unwrap() – Removes the last item of a list if its first and last values are equal.
   • unique() – Returns a sorted list with all duplicates removed.
   • unique_count() – Returns a sorted list of unique items with counts.

4. Section: Sorting

   • sort() – Returns a sorted list.
   • sortidx() – Returns a list of sorted indices into a list.
   • group_sort() – Returns a sorted list of groups of values.
   • group_data() – Groups list data by integer group numbers.
   • list_smallest() – Returns the k smallest values in the list, in arbitrary order.

Synopsis: Returns true if two values are equal to within a small epsilon value.

Topics: Comparisons

See Also: all_zero(), all_nonzero()

Usage:

• test = approx(a, b, [eps])

Description:

Compares two numbers, vectors, or matrices. Returns true if they are closer than eps to each other. Results are undefined if a and b are of different types, or if vectors or matrices contain non-numbers.

Arguments:

Example 1:

include <BOSL2/std.scad>
test1 = approx(-0.3333333333,-1/3);  // Returns: true
test2 = approx(0.3333333333,1/3);    // Returns: true
test3 = approx(0.3333,1/3);          // Returns: false
test4 = approx(0.3333,1/3,eps=1e-3); // Returns: true
test5 = approx(PI,3.1415926536);     // Returns: true
test6 = approx([0,0,sin(45)],[0,0,sqrt(2)/2]);  // Returns: true

Synopsis: Returns true if the value(s) given are aproximately zero.

Topics: Comparisons, List Handling

See Also: approx(), all_nonzero()

Usage:

• x = all_zero(x, [eps]);

Description:

Returns true if its argument is approximately zero, to within eps. If passed a list returns true if all its entries are approximately equal to zero. Otherwise, returns false.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = all_zero(0);  // Returns: true.
b = all_zero(1e-3);  // Returns: false.
c = all_zero([0,0,0]);  // Returns: true.
d = all_zero([0,0,1e-3]);  // Returns: false.

Synopsis: Returns true if the value(s) given are not aproximately zero.

Topics: Comparisons, List Handling

See Also: approx(), all_zero()

Usage:

• test = all_nonzero(x, [eps]);

Description:

Returns true if its argument is finite and different from zero by eps. If passed a list returns true if all the entries of the list are finite numbers that are different from zero by eps. Otherwise, returns false.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = all_nonzero(0);  // Returns: false.
b = all_nonzero(1e-3);  // Returns: true.
c = all_nonzero([0,0,0]);  // Returns: false.
d = all_nonzero([0,0,1e-3]);  // Returns: false.
e = all_nonzero([1e-3,1e-3,1e-3]);  // Returns: true.

Synopsis: Returns true if the value(s) given are greater than zero.

Topics: Comparisons, List Handling

See Also: approx(), all_zero(), all_nonzero(), all_negative(), all_nonpositive(), all_nonnegative()

Usage:

• test = all_positive(x,[eps]);

Description:

Returns true if the argument is finite and greater than zero, within epsilon tolerance if desired. If passed a list returns true if all the entries are finite positive numbers. Otherwise, returns false.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = all_positive(-2);  // Returns: false.
b = all_positive(0);  // Returns: false.
c = all_positive(2);  // Returns: true.
d = all_positive([0,0,0]);  // Returns: false.
e = all_positive([0,1,2]);  // Returns: false.
f = all_positive([3,1,2]);  // Returns: true.
g = all_positive([3,-1,2]);  // Returns: false.

Synopsis: Returns true if the value(s) given are less than zero.

Topics: Comparisons, List Handling

See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_nonpositive(), all_nonnegative()

Usage:

• test = all_negative(x, [eps]);

Description:

Returns true if the argument is finite and less than zero, within epsilon tolerance if desired. If passed a list, returns true if all the elements are finite negative numbers. Otherwise, returns false.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = all_negative(-2);  // Returns: true.
b = all_negative(0);  // Returns: false.
c = all_negative(2);  // Returns: false.
d = all_negative([0,0,0]);  // Returns: false.
e = all_negative([0,1,2]);  // Returns: false.
f = all_negative([3,1,2]);  // Returns: false.
g = all_negative([3,-1,2]);  // Returns: false.
h = all_negative([-3,-1,-2]);  // Returns: true.

Synopsis: Returns true if the value(s) given are less than or equal to zero.

Topics: Comparisons, List Handling

See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_negative(), all_nonnegative()

Usage:

• all_nonpositive(x, [eps]);

Description:

Returns true if its argument is finite and less than or equal to zero. If passed a list, returns true if all the elements are finite non-positive numbers. Otherwise, returns false.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = all_nonpositive(-2);  // Returns: true.
b = all_nonpositive(0);  // Returns: true.
c = all_nonpositive(2);  // Returns: false.
d = all_nonpositive([0,0,0]);  // Returns: true.
e = all_nonpositive([0,1,2]);  // Returns: false.
f = all_nonpositive([3,1,2]);  // Returns: false.
g = all_nonpositive([3,-1,2]);  // Returns: false.
h = all_nonpositive([-3,-1,-2]);  // Returns: true.

Synopsis: Returns true if the value(s) given are greater than or equal to zero.

Topics: Comparisons, List Handling

See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_negative(), all_nonpositive()

Usage:

• all_nonnegative(x, [eps]);

Description:

Returns true if the finite number passed to it is greater than or equal to zero. If passed a list, returns true if all the elements are finite non-negative numbers. Otherwise, returns false.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = all_nonnegative(-2);  // Returns: false.
b = all_nonnegative(0);  // Returns: true.
c = all_nonnegative(2);  // Returns: true.
d = all_nonnegative([0,0,0]);  // Returns: true.
e = all_nonnegative([0,1,2]);  // Returns: true.
f = all_nonnegative([0,-1,-2]);  // Returns: false.
g = all_nonnegative([3,1,2]);  // Returns: true.
h = all_nonnegative([3,-1,2]);  // Returns: false.
i = all_nonnegative([-3,-1,-2]);  // Returns: false.

Synopsis: Returns true if all items in a list are approximately equal to each other.

Topics: Comparisons, List Handling

See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_negative(), all_nonpositive(), all_nonnegative()

Usage:

• b = all_equal(vec, [eps]);

Description:

Returns true if all of the entries in vec are equal to each other, or approximately equal to each other if eps is set.

Arguments:

Synopsis: Returns true if the first and last items in a list are approximately equal.

Topics: Comparisons, List Handling

See Also: approx(), all_zero(), all_nonzero(), all_positive(), all_negative(), all_nonpositive(), all_nonnegative()

Usage:

• are_ends_equal(list, [eps]);

Description:

Returns true if the first and last points in the given list are equal to within epsilon.

Arguments:

Synopsis: Returns true if every item in a list is greater than the previous item.

Topics: Comparisons, List Handling

See Also: max_index(), min_index(), is_decreasing()

Usage:

• bool = is_increasing(list, [strict]);

Description:

Returns true if the list is (non-strictly) increasing, or strictly increasing if strict=true. The list can be a list of any items that OpenSCAD can compare, or it can be a string which will be evaluated character by character.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = is_increasing([1,2,3,4]);  // Returns: true
b = is_increasing([1,3,2,4]);  // Returns: false
c = is_increasing([1,3,3,4]);  // Returns: true
d = is_increasing([1,3,3,4],strict=true);  // Returns: false
e = is_increasing([4,3,2,1]);  // Returns: false

Synopsis: Returns true if exery item in a list is less than the previous item.

Topics: Comparisons, List Handling

See Also: max_index(), min_index(), is_increasing()

Usage:

• bool = is_decreasing(list, [strict]);

Description:

Returns true if the list is (non-strictly) decreasing, or strictly decreasing if strict=true. The list can be a list of any items that OpenSCAD can compare, or it can be a string which will be evaluated character by character.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = is_decreasing([1,2,3,4]);  // Returns: false
b = is_decreasing([4,2,3,1]);  // Returns: false
c = is_decreasing([4,3,2,1]);  // Returns: true

Synopsis: Compares two values, possibly of different type.

Topics: Comparisons, List Handling

See Also: approx(), is_increasing(), is_decreasing()

Usage:

• test = compare_vals(a, b);

Description:

Compares two values. Lists are compared recursively. Returns a negative value if a<b. Returns a positive value if a>b. Returns 0 if a==b. If types are not the same, then undef < bool < nan < num < str < list < range.

Arguments:

Synopsis: Compares two lists of values, possibly of different type.

Topics: Comparisons, List Handling

See Also: compare_vals(), approx(), is_increasing(), is_decreasing()

Usage:

• test = compare_lists(a, b)

Description:

Compare contents of two lists using compare_vals(). Returns a negative number if a<b. Returns 0 if a==b. Returns a positive number if a>b.

Arguments:

Synopsis: Returns the index of the minimal value in the given list.

Topics: List Handling

See Also: max_index(), is_increasing(), is_decreasing()

Usage:

• idx = min_index(vals);
• idxlist = min_index(vals, all=true);

Description:

Returns the index of the first occurrence of the minimum value in the given list. If all is true then returns a list of all indices where the minimum value occurs.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = min_index([5,3,9,6,2,7,8,2,1]); // Returns: 8
b = min_index([5,3,9,6,2,7,8,2,7],all=true); // Returns: [4,7]

Synopsis: Returns the index of the minimal value in the given list.

Topics: List Handling

See Also: min_index(), is_increasing(), is_decreasing()

Usage:

• idx = max_index(vals);
• idxlist = max_index(vals, all=true);

Description:

Returns the index of the first occurrence of the maximum value in the given list. If all is true then returns a list of all indices where the maximum value occurs.

Arguments:

Example 1:

include <BOSL2/std.scad>
max_index([5,3,9,6,2,7,8,9,1]); // Returns: 2
max_index([5,3,9,6,2,7,8,9,1],all=true); // Returns: [2,7]

Synopsis: Finds the indexes of the item(s) in the given list that are aproximately the given value.

Topics: List Handling

See Also: in_list()

Usage:

• idx = find_approx(val, list, [start=], [eps=]);
• indices = find_approx(val, list, all=true, [start=], [eps=]);

Description:

Finds the first item in list that matches val to within eps tolerance, returning the index. Returns undef if there is no match. If all=true then returns all the items that agree within eps and returns the empty list if no such items exist.

Arguments:

Example 1:

include <BOSL2/std.scad>
find_approx(3,[4,5,3.01,2,2.99], eps=0.1);  // Returns 2
find_approx(9,[4,5,3.01,2,2.99], eps=0.1);  // Returns undef
find_approx(3,[4,5,3.01,2,2.99], all=true, eps=0.1);  // Returns [2,4]
find_approx(9,[4,5,3.01,2,2.99], all=true, eps=0.1);  // Returns []

Synopsis: Returns a list with all consecutive duplicate values removed.

Topics: List Handling

See Also: deduplicate_indexed()

Usage:

• list = deduplicate(list, [closed], [eps]);

Description:

Removes consecutive duplicate items in a list. When eps is zero, the comparison between consecutive items is exact. Otherwise, when all list items and subitems are numbers, the comparison is within the tolerance eps. Unlike unique() only consecutive duplicates are removed and the list is not sorted. If closed is set to true then the first and last entries in list are treated as adjacent, so all trailing items that match list[0] are dropped.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = deduplicate([8,3,4,4,4,8,2,3,3,8,8]);  // Returns: [8,3,4,8,2,3,8]
b = deduplicate(closed=true, [8,3,4,4,4,8,2,3,3,8,8]);  // Returns: [8,3,4,8,2,3]
c = deduplicate("Hello");  // Returns: "Helo"
d = deduplicate([[3,4],[7,2],[7,1.99],[1,4]],eps=0.1);  // Returns: [[3,4],[7,2],[1,4]]
e = deduplicate([[7,undef],[7,undef],[1,4],[1,4+1e-12]],eps=0);    // Returns: [[7,undef],[1,4],[1,4+1e-12]]

Synopsis: Takes a list of indices into a list of values, and returns a list of indices whose values are not consecutively the same.

Topics: List Handling

See Also: deduplicate()

Usage:

• new_idxs = deduplicate_indexed(list, indices, [closed], [eps]);

Description:

Given a list, and a list of indices, removes consecutive indices corresponding to list values that are equal or approximately equal.

Arguments:

Example 1:

include <BOSL2/std.scad>
a = deduplicate_indexed([8,6,4,6,3], [1,4,3,1,2,2,0,1]);  // Returns: [1,4,3,2,0,1]
b = deduplicate_indexed([8,6,4,6,3], [1,4,3,1,2,2,0,1], closed=true);  // Returns: [1,4,3,2,0]
c = deduplicate_indexed([[7,undef],[7,undef],[1,4],[1,4],[1,4+1e-12]],eps=0);    // Returns: [0,2,4]

Synopsis: Returns a list whose last value is the same as the first.

Topics: List Handling, Paths

See Also: list_unwrap(), deduplicate()

Usage:

• list_wrap(path, [eps]);

Description:

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. 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 1 are returned unchanged.

Arguments:

Synopsis: Removes the last item of a list if its first and last values are equal.

Topics: List Handling, Paths

See Also: list_wrap(), deduplicate()

Usage:

• list_unwrap(list, [eps]);

Description:

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 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 length 0 or 1 it is returned unchanged.

Arguments:

Synopsis: Returns a sorted list with all duplicates removed.

Topics: List Handling

See Also: shuffle(), sort(), sortidx(), unique_count()

Usage:

• ulist = unique(list);

Description:

Given a string or a list returns the sorted string or the sorted list with all repeated items removed. The sorting order of non homogeneous lists is the function sort order.

Arguments:

Example 1:

include <BOSL2/std.scad>
sorted = unique([5,2,8,3,1,3,8,7,5]);  // Returns: [1,2,3,5,7,8]
sorted = unique("axdbxxc");  // Returns: "abcdx"
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]]

Synopsis: Returns a sorted list of unique items with counts.

Topics: List Handling

See Also: shuffle(), sort(), sortidx(), unique()

Usage:

• sorted_counts = unique_count(list);

Description:

Returns [sorted,counts] where sorted is a sorted list of the unique items in list and counts is a list such that count[i] gives the number of times that sorted[i] appears in list.

Arguments:

Example 1:

include <BOSL2/std.scad>
sorted = unique([5,2,8,3,1,3,8,3,5]);  // Returns: [ [1,2,3,5,8], [1,1,3,2,2] ]

Synopsis: Returns a sorted list.

Topics: List Handling

See Also: shuffle(), sortidx(), unique(), unique_count(), group_sort()

Usage:

• slist = sort(list, [idx]);

Description:

Sorts the given list in lexicographic order. The sort is stable, meaning equivalent items will not change order. If the input is a homogeneous simple list or a homogeneous list of vectors (see function is_homogeneous), the sorting method uses the native comparison operator and is faster. When sorting non homogeneous list the elements are compared with compare_vals, with types ordered according to undef < boolean < number < string < list. Comparison of lists is recursive. When comparing vectors, homogeneous or not, the parameter idx may be used to select the components to compare. Note that homogeneous lists of vectors may contain mixed types provided that for any two list elements list[i] and list[j] satisfies type(list[i][k])==type(list[j][k]) for all k. Strings are allowed as any list element and are compared with the native operators although no substring comparison is possible.

Arguments:

Example 1:

include <BOSL2/std.scad>
// Homogeneous lists
l1 = [45,2,16,37,8,3,9,23,89,12,34];
sorted1 = sort(l1);  // Returns [2,3,8,9,12,16,23,34,37,45,89]
l2 = [["oat",0], ["cat",1], ["bat",3], ["bat",2], ["fat",3]];
sorted2 = sort(l2); // Returns: [["bat",2],["bat",3],["cat",1],["fat",3],["oat",0]]
// Non-homegenous list
l3 = [[4,0],[7],[3,9],20,[4],[3,1],[8]];
sorted3 = sort(l3); // Returns: [20,[3,1],[3,9],[4],[4,0],[7],[8]]

Synopsis: Returns a list of sorted indices into a list.

Topics: List Handling

See Also: shuffle(), sort(), group_sort(), unique(), unique_count()

Usage:

• idxlist = sortidx(list, [idx]);

Description:

Given a list, sort it as function sort(), and returns a list of indexes into the original list in that sorted order. The sort is stable, so equivalent items will not change order. If you iterate the returned list in order, and use the list items to index into the original list, you will be iterating the original values in sorted order.

Arguments:

Example 1:

include <BOSL2/std.scad>
lst = ["d","b","e","c"];
idxs = sortidx(lst);  // Returns: [1,3,0,2]
ordered = select(lst, idxs);   // Returns: ["b", "c", "d", "e"]

Example 2:

include <BOSL2/std.scad>
lst = [
    ["foo", 88, [0,0,1], false],
    ["bar", 90, [0,1,0], true],
    ["baz", 89, [1,0,0], false],
    ["qux", 23, [1,1,1], true]
];
idxs1 = sortidx(lst, idx=1); // Returns: [3,0,2,1]
idxs2 = sortidx(lst, idx=0); // Returns: [1,2,0,3]
idxs3 = sortidx(lst, idx=[1,3]); // Returns: [3,0,2,1]

Synopsis: Returns a sorted list of groups of values.

Topics: List Handling

See Also: group_data(), shuffle(), sort(), sortidx(), unique(), unique_count()

Usage:

• ulist = group_sort(list,[idx]);

Description:

Given a list of numbers, sorts the list into a sequence of lists, where each list contains any repeated values. If there are no repeated values the output will be a list of singleton lists. If you apply flatten() to the output, the result will be a simple sorted list.

When the input is a list of lists, the sorting is done based on index idx of the entries in list. In this case, list[i][idx] must be a number for every i, and the entries in list are grouped together in the output if they match at index idx. This function can be used to group together items that are tagged with the same index.

Arguments:

Example 1:

include <BOSL2/std.scad>
sorted = group_sort([5,2,8,3,1,3,8,7,5]);  // Returns: [[1],[2],[3,3],[5,5],[7],[8,8]]
// Next example returns: [ [[2,"b"],[2,"e"]], [[3,"d"]], [[5,"a"],[5,"c"]] ]
sorted2 = group_sort([[5,"a"],[2,"b"], [5,"c"], [3,"d"], [2,"e"] ], idx=0);

Synopsis: Groups list data by integer group numbers.

Topics: List Handling

See Also: group_sort(), shuffle(), sort(), sortidx(), unique(), unique_count()

Usage:

• groupings = group_data(groups, values);

Description:

Given a list of integer group numbers, and an equal-length list of values, returns a list of groups with the values sorted into the corresponding groups. Ie: if you have a groups index list of [2,3,2] and values of ["A","B","C"], then the values "A" and "C" will be put in group 2, and "B" will be in group 3. Groups that have no values grouped into them will be an empty list. So the above would return [[], [], ["A","C"], ["B"]]

Arguments:

Example 1:

include <BOSL2/std.scad>
groups = group_data([1,2,0], ["A","B","C"]);  // Returns [["B"],["C"],["A"]]

Example 2:

include <BOSL2/std.scad>
groups = group_data([1,3,1], ["A","B","C"]);  // Returns [[],["A","C"],[],["B"]]

Synopsis: Returns the k smallest values in the list, in arbitrary order.

Topics: List Handling

See Also: group_sort(), shuffle(), sort(), sortidx(), unique(), unique_count()

Usage:

• small = list_smallest(list, k)

Description:

Returns a set of the k smallest items in list in arbitrary order. The items must be mutually comparable with native OpenSCAD comparison operations. You will get "undefined operation" errors if you provide invalid input.

Arguments: