
Boost : 
Subject: [boost] [algorithm] Interface for longest_increasing_subsequence (proposal)
From: Curdeius Curdeius (curdeius_at_[hidden])
Date: 20140817 12:54:04
Hi all,
I want to propose a new algorithm to Boost.Algorithm: a wellknown 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 13.
Thank you in advance for all the comments, corrections etc.
Regards,
Marek Kurdej
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk