Skip to content

Latest commit

 

History

History
227 lines (190 loc) · 13.8 KB

std_algorithm_status.md

File metadata and controls

227 lines (190 loc) · 13.8 KB
Raw

OpenSCAD Algorithm Implementation Status (C++ STL based)

List of STL Algorithms pulled from cppreference.com

Key

Status Description
✔️ DONE
✅ TODO
❌# Not Applicable to OpenSCAD (with numbered note)
❓# Unsure if applicable (with numbered note)
➕ Bonus Implemented in std library style, but not a native STL function

Non-modifying sequence operations

Status Function Name Description
➕ end returns last or len(v) if last undefined, similar to container::end() iterator.
✔️ all_of checks if a predicate is true for all of the elements in a range
✔️ any_of checks if a predicate is true for any of the elements in a range
✔️ none_of checks if a predicate is true for none of the elements in a range
✔️ for_each
✔️ for_each_n applies a function object to the first n elements of a sequence
✔️ count
✔️ count_if returns the number of elements satisfying specific criteria
✔️ mismatch finds the first position where two ranges differ
✔️ find
✔️ find_if
✔️ find_if_not finds the first element satisfying specific criteria
➕ contains like find, but return boolean instead of index
✔️ find_end finds the last sequence of elements in a certain range
✔️ find_first_of searches for any one of a set of elements
✔️ adjacent_find finds the first two adjacent items that are equal (or satisfy a given predicate)
✔️ search searches for a range of elements
✔️ search_n searches a range for a number of consecutive copies of an element

Modifying sequence operations

Status Function Name Description
✔️ copy
✔️ copy_if copies a range of elements to a new location
✔️ copy_n copies a number of elements to a new location
✔️ copy_backward copies a range of elements in backwards order
❌1 move moves a range of elements to a new location
❌1 move_backward moves a range of elements to a new location in backwards order
✔️ fill copy-assigns the given value to every element in a range
✔️ fill_n copy-assigns the given value to N elements in a range
✔️ transform applies a function to a range of elements, storing results in a destination range
➕ transform2 applies a function to a range of elements, storing results in a destination range
✔️ generate assigns the results of successive function calls to every element in a range
✔️ generate_n assigns the results of successive function calls to N elements in a range
✔️ remove
✔️ remove_if removes elements satisfying specific criteria
✔️ remove_copy
✔️ remove_copy_if copies a range of elements omitting those that satisfy specific criteria
✔️ replace
✔️ replace_if replaces all values satisfying specific criteria with another value
✔️ replace_copy
✔️ replace_copy_if copies a range, replacing elements satisfying specific criteria with another value
❌ swap swaps the values of two objects
✔️ swap_ranges swaps two ranges of elements
✔️ iter_swap swaps the elements pointed to by two iterators
✔️ reverse reverses the order of elements in a range
✔️ reverse_copy creates a copy of a range that is reversed
✔️ rotate rotates the order of elements in a range
✔️ rotate_copy copies and rotate a range of elements
❓ shift_left
❓ shift_right shifts elements in a range
❌ random_shuffle
✅ shuffle randomly re-orders elements in a range
✅ sample selects n random elements from a sequence
✔️ unique removes consecutive duplicate elements in a range
✅ unique_copy creates a copy of some range of elements that contains no consecutive duplicates

Partitioning operations

Status Function Name Description
✅ is_partitioned determines if the range is partitioned by the given predicate
❌2 partition divides a range of elements into two groups
✅ partition_copy copies a range dividing the elements into two groups
✔️ stable_partition divides elements into two groups while preserving their relative order
✅ partition_point locates the partition point of a partitioned range

Sorting operations

Status Function Name Description
✅ is_sorted checks whether a range is sorted into ascending order
✅ is_sorted_until finds the largest sorted subrange
✅ sort sorts a range into ascending order
✅ partial_sort sorts the first N elements of a range
✅ partial_sort_copy copies and partially sorts a range of elements
❓2 stable_sort sorts a range of elements while preserving order between equal elements
✅ nth_element partially sorts the given range making sure that it is partitioned by the given element

Binary search operations (on sorted ranges)

Status Function Name Description
✔️ lower_bound returns an iterator to the first element not less than the given value
✔️ upper_bound returns an iterator to the first element greater than a certain value
✔️ binary_search determines if an element exists in a certain range
✅ equal_range returns range of elements matching a specific key

Other operations on sorted ranges

Status Function Name Description
✅ merge merges two sorted ranges
❓1 inplace_merge merges two ordered ranges in-place

Set operations (on sorted ranges)

Status Function Name Description
✅ includes returns true if one set is a subset of another
✅ set_difference computes the difference between two sets
✅ set_intersection computes the intersection of two sets
✅ set_symmetric_difference computes the symmetric difference between two sets
✅ set_union computes the union of two sets

Heap operations

Status Function Name Description
❓3 is_heap checks if the given range is a max heap
❓3 is_heap_until finds the largest subrange that is a max heap
❓3 make_heap creates a max heap out of a range of elements
❓3 push_heap adds an element to a max heap
❓3 pop_heap removes the largest element from a max heap
❓3 sort_heap turns a max heap into a range of elements sorted in ascending order

Minimum/maximum operations

Status Function Name Description
✔️ max returns the greater of the given values
✔️ max_element returns the largest element in a range
✔️ min returns the smaller of the given values
✔️ min_element returns the smallest element in a range
✔️ minmax returns the smaller and larger of two elements
✔️ minmax_element returns the smallest and the largest elements in a range
✔️ clamp clamps a value between a pair of boundary values

Comparison operations

Status Function Name Description
✅ equal determines if two sets of elements are the same
✅ lexicographical_compare returns true if one range is lexicographically less than another
✅ lexicographical_compare_three_way compares two ranges using three-way comparison

Permutation operations

Status Function Name Description
✅ is_permutation determines if a sequence is a permutation of another sequence
✅ next_permutation generates the next greater lexicographic permutation of a range of elements
✅ prev_permutation generates the next smaller lexicographic permutation of a range of elements

Numeric operations

Status Function Name Description
✅ iota fills a range with successive increments of the starting value
✔️ accumulate sums up a range of elements
✅ inner_product computes the inner product of two ranges of elements
✅ adjacent_difference computes the differences between adjacent elements in a range
✅ partial_sum computes the partial sum of a range of elements
❌4 reduce similar to std::accumulate, except out of order
✅ exclusive_scan similar to std::partial_sum, excludes the ith input element from the ith sum
✅ inclusive_scan similar to std::partial_sum, includes the ith input element in the ith sum
✅ transform_reduce applies a functor, then reduces out of order
✅ transform_exclusive_scan applies a functor, then calculates exclusive scan
✅ transform_inclusive_scan applies a functor, then calculates inclusive scan

Operations on uninitialized memory

Status Function Name Description
❌5 uninitialized_copy copies a range of objects to an uninitialized area of memory
❌5 uninitialized_copy_n copies a number of objects to an uninitialized area of memory
❌5 uninitialized_fill copies an object to an uninitialized area of memory, defined by a range
❌5 uninitialized_fill_n copies an object to an uninitialized area of memory, defined by a start and a count
❌5 uninitialized_move moves a range of objects to an uninitialized area of memory
❌5 uninitialized_move_n moves a number of objects to an uninitialized area of memory
❌5 uninitialized_default_construct constructs objects by default-initialization in an uninitialized area of memory, defined by a range
❌5 uninitialized_default_construct_n constructs objects by default-initialization in an uninitialized area of memory, defined by a start and a count
❌5 uninitialized_value_construct constructs objects by value-initialization in an uninitialized area of memory, defined by a range
❌5 uninitialized_value_construct_n constructs objects by value-initialization in an uninitialized area of memory, defined by a start and a count
❌5 destroy_at destroys an object at a given address
❌5 destroy destroys a range of objects
❌5 destroy_n destroys a number of objects in a range

C library

Status Function Name Description
❓6 qsort sorts a range of elements with unspecified type
❓7 bsearch searches an array for an element of unspecified type

Totals:

Count Type
52 DONE
34 TODO
19 Not Applicable
12 Unsure
117 Total STL algos
3 Bonus

Notes

  1. OpenSCAD doesn't differentiate between copy and move (everything is copy due to immutability)

  2. Don't think there is a way to benefit from unstable version in OpenSCAD so "stable_" is already implied

  3. Not sure if heap type operations can be implemented in such a way that is efficient/worth using?

  4. Don't think there would be any difference between reduce and accumulate for OpenSCAD. Choose one name?

    Also, fold exists under "Common higher-order function" (not STL based), but might want to call that reduce?

  5. No low-level memory management in OpenSCAD

  6. Don't think we can do quicksort efficiently since every swap requires a whole new list (mergesort makes most sense?)

  7. Don't think there'd be any significant difference between bsearch and binary_search given that we just use indices not iterators or pointers