# Difference between revisions of "To Do List"

SeanParent (Talk | contribs) (→Goals) |
SeanParent (Talk | contribs) (→Non-Mutating Algorithms) |
||

Line 62: | Line 62: | ||

We should try to adapt binary search algorithms such as upper bound and lower bound to work on sets and multisets. | We should try to adapt binary search algorithms such as upper bound and lower bound to work on sets and multisets. | ||

− | + | ===Finding and Counting=== | |

− | + | ||

− | Finding and Counting | + | |

Extending find() - also provide find_not() and count_if_not() and count_not(). | Extending find() - also provide find_not() and count_if_not() and count_not(). | ||

Line 75: | Line 73: | ||

And find_n(), count_n() for all versions. | And find_n(), count_n() for all versions. | ||

− | |||

− | |||

----- | ----- |

## Revision as of 20:56, 17 October 2007

## Contents |

## Goals

We are now in a mode of completing the core of ASL (defined to be roughly the libraries which make of the property model and layout libraries as well as anything which is complete enough to warrant inclusion).

To that end, we are reviewing all of the libraries and for each one determining:

1) Is it used and/or useful and worth being completed. If not it will either be removed all together or partitioned into the platform libraries for later consideration.

2) What is necessary to complete the space to create a completed body of work.

We are working to restructure the documentation to include the "final" set of libraries and to flesh out the documentation, test cases, and in some cases, the code.

## Non-Mutating Algorithms

Order Selection Networks - Rework pin, min, max, median_3, median_5, select_ith_n

Review chapter from book (4)

For each provide a comparison based, const, and non-const versions.

Go to how many elements?

Definitions: select_ith_n: return the ith element in non-descending order out of n elements.

The network is minimal in the worst case if it does the minimum number of comparisons in the worst case and minimal in the average case if it does the minimum number of comparisons on average.

The selection network is stable if the retuned element is selected out of n elements stably soreted in non-decending order (we do not do sorting).

A selection network from partially ordered inputs is a selection network where a certain partial ordering of the elements is already determined.

[We need to develop a naming convention for paritial ordering.]

Question - do we provide sorting networks?

Replace bound_if() with partition_point()

Write a proper partition() (ordering and for forward iterator), partition_point_n(), and is_partitioned.

Make cautionary note about wrapped standard algorithms.

non_strict_order_partition(range, element, strict_weak_ordering) arranges it so that elements are not greater followed by elements which are not less.

Pull count_min/max_element. Replace with two passes - max_element(), count().

Binary searches

Write a better binary_search which returns lower_bound() if exists else last.

Write an adaptor for is_in_sorted_range - set_member?

find_first_of_set() - becomes find_if with adaptor.

We should try to adapt binary search algorithms such as upper bound and lower bound to work on sets and multisets.

### Finding and Counting

Extending find() - also provide find_not() and count_if_not() and count_not(). exists, none, all?

Check what other adobe/STL algorithms take unary predicates (partition_not?).

Versions of find and count need to take a binary predicate - see find_match().

And find_n(), count_n() for all versions.

Versions of for_each for_each_value() - rename of for_each_position() for_each_value_n() for_each_n()

Sorting Group is_sorted sorted() rename to sorted_run()

mismatch() gets grouped with equal() and search() Add mismatch_n().

Look at reduce accumulate and related functions - do we keepr reduce_balanced()?

## Mutating Algorithms

-- copy family

Try to simply use the name copy() for copy_bound() - etc.

Add bounded forms of other functions, i.e. swap_ranges.

Also applies to find and count

copy I I 0 copy_b I I F F copy_n I n O copy_b I I O n copy_b I n F F copy_b I F F

I I n F F

--- tranform_if replaces filter by splitting the function object.

transform_if_not.

Also add _if forms for other functions.

Also have copy_if and copy_if_not (as replacement of remove). --- Explore iota and fit more into the copy notation.

With a value for increment - ---

It looks like remove_runs and mutate_runs are not used - remove them.

---

Add a reverse group and add reverse_until.

---

Remove the pair return from rotate and simply return m'

---

## Notes

Check to see which intrinsics (like multiply returning long result) are in C99