[boost] [algorithm] Interface for longest_increasing_subsequence (proposal)

Subject: [boost] [algorithm] Interface for longest_increasing_subsequence (proposal)
From: Curdeius Curdeius (curdeius_at_[hidden])
Date: 2014-08-17 12:54:04

Hi all,

I want to propose a new algorithm to Boost.Algorithm: a well-known longest
increasing subsequence
<https://en.wikipedia.org/wiki/Longest_increasing_subsequence> (LIS for
short).
Just for a short info: given a sequence like ( 7 )( 2 )( 8 )( 1 )( 3 )( 4
)( 10 )( 6 )( 9 )( 5 ), the result will be a subsequence ( 1 )( 3 )( 4 )( 6
)( 9 ).
The proposed algorithm has O(n log n) time and O(n) complexity, where n -
sequence length.

I have created a pull request https://github.com/boostorg/algorithm/pull/7.

I have however some questions.
I am not sure what should be the exposed interface.
For the moment, I propose (I base it on the existing interface from
algorithm/searching functions):

   - class longest_increasing_subsequence with methods
   - operator()
      - *compute_length* (a better name may be needed)
   - free function longest_increasing_subsequence_length returning the
   length of the LIS and taking as arguments:
   - a pair of iterators (first, last)
      - or a range
      - and (optionally) a comparison predicate
   - *free function longest_increasing_subsequence_search taking the same
   arguments as _length function and an Output Iterator or a tag.*
   - free function make_longest_increasing_subsequence taking a range and
   optionally a comparison predicate and returning
   corresponding longest_increasing_subsequence object

The problematic part is the
underlined longest_increasing_subsequence_search function and the way in
which I should return the resulting LIS.
I see possibilities like the following:

   1. taking an OutputIterator argument:
       the best for me, generic and the most flexible solution, but there
   is a performance hit as we cannot reserve the memory for the output LIS.
   2. returning a container with the subsequence, e.g.
   std::vector<value_type>:
       no performance hit with small objects or if the user needs a vector
   of values. However, not really generic as the user would be obliged to use
   a vector (in the aforementioned example).
   3. returning a container with iterators, e.g. std::vector<InputIter>:
       good if a container of iterators is acceptable, it has a benefit of
   avoiding possibly expensive copies of sequence elements. As 2., not really
   generic.
   4. -taking a container as an argument:
       the worst solution in my eyes, there is no way nice way to write
   generic code that handles all containers.

I have coded possibilities 1-3.

Thank you in advance for all the comments, corrections etc.

Regards,
Marek Kurdej