Boost logo

Boost :

From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2002-09-09 14:59:38

"Rozental, Gennadiy" <Gennadiy_at_[hidden]> wrote in message
> In most part I disagree with what you proposing here.
> 1. These are two different algorithms and no need to mix them.

I've been thinking along similar lines. I am thinking of moving the core
implementation into the boost::detail (or boost::detail::lcs?) namespace and
providing global template functions to compute_lcs() and apply_changes(). A
problem with this is that template functions cannot take default template
parameters - See (2) below.

> 2. What is change_set is it some special type?

No, it's just a container that the algorithm populates with the changes. The
actual definition is:

template<typename T>
class lcs_change : boost::noncopyable
    std::size_t rec_num_; // record number
    record_type type_; // record type (see enum above)
    const T &data_; // record data

    // ctor just stores the data
    lcs_change(std::size_t rec_num, record_type type, const T &data)
        : rec_num_(rec_num),

    // empty dtor
    ~lcs_change() { }

    // public accessors
    std::size_t rec_num(void) const { return rec_num_; }
    record_type type(void) const { return type_; }
    const T &data(void) const { return data_; }

template<typename Seq, typename Res=std::list< lcs_change<Seq::value_type>
*> >
class longest_common_subsequence : boost::noncopyable
    // define a typedef for the difference results
    typedef Res change_set;

    // if you get a compilation error here then the result type you
    // have specified as the second parameter is the wrong type

lcs_change<Seq::value_type> *>::value));

> 3. STL algorithms are iterator based, not sequence based. WE should keep
> that way

Absolutely. There are two ctors, one takes const_iterator pairs for the two
sequences, the second takes the two sequence objects by const reference
simply for convenience. If there is opposition to this addition, there is no
problem in removing this ctor, I just like to provide a flexibility to the

> 4. Why are you using pointers and not a references?

I like to use a const reference for input parameters and a pointer for
output parameters, and place in the input parameters before the output
parameters. This makes for a clean interface which provides more information
to the user about the use of parameters.

> 5. How could I obtain changes to pass as a first argument ot second
> algorithm if you don't return them?

I do! They are returned in the second parameter of the compute_lcs() method.

> 6. Why do e need class at all?

Possibly not :-) See (1) above.

> Here how I invision it
> template<typename InIt1, typename InIt2, typename OutIt >
> void
> longest_common_subsequence( InIt1 first_begin, InIt1 first_end,
> InIt2 second_begin,
> OutIt& res_begin );
> template<typename InIt, typename DiffIt, typename OutIt >
> void
> apply_diff( InIt input_begin, InIt input_end, InIt diff_begin, OutIt
> res_begin );

Yep, pretty much my though if I get rid of the class.

It looks like we are fairly close on our thoughts here. Thanks for your
interest and all your comments. Like I said, I'll put the code and docs in
the sandbox asap. Any more thoughts, ideas or comments, please post them :-)

-- Craig

Boost list run by bdawes at, gregod at, cpdaniel at, john at