[boost] Re: Container Difference proposal

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

"Rozental, Gennadiy" <Gennadiy_at_[hidden]> wrote in message
news:1373D6342FA1D4119A5100E029437F6401169E1A_at_clifford.devo.ilx.com...
>
> 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
{
    private:
    std::size_t  rec_num_;  // record number
    record_type  type_;     // record type (see enum above)
    const T     &data_;     // record data

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

    // 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
{
    public:
    // 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
    BOOST_STATIC_ASSERT((boost::is_same<Res::value_type,

lcs_change<Seq::value_type> *>::value));
[snip]
};

> 3. STL algorithms are iterator based, not sequence based. WE should keep
it
> 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
user.

> 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