[boost] Re: Container Difference proposal

From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2002-09-09 06:18:34

"Gennadiy Rozental" <gennadiy_at_[hidden]> wrote in message
news:alf7tv$884$1_at_main.gmane.org...
> Well, in your expirience in may be used in complex diff related algorithms
> implementations. But in fact it is computing some sort of intersection
> between 2 sequences. Why should we name intersection difference. Don't you
> think it could be confusing?

I've been working on the interface and come up with something I'm pretty
happy with. The name still needs thrashing out, and I expect to have some
further constructive discussion on this in the future. But for now, what
would you say to an interface along these lines? Note that this is an
abstract of the full interface omitting the change list details.(sorry about
the formatting!)

namespace boost {

template <typename Seq>
class longest_common_subsequence : noncopyable
{
  public:
    // list of changes made to sequence1 to create sequence2
    typedef ... change_set;

  public:
    longest_common_subsequence(const Seq &first, const Seq &second);
    // note there's also a ctor taking const_iterator pairs for
    // the first and second seq

    unsigned compute_lcs(  unsigned mask,
        longest_common_subsequence<Seq>::change_set *changes);

    bool reconstruct_sequence(  const
        longest_common_subsequence<Seq>::change_set &changes,
        const Seq &original,
        Seq *reconstructed);
};

//  namespace boost

compute_lcs() will construct a change list and return the length of the
longest common subsequence. the first parameter determines what should be
included in the change list pointer to by the second parameter. If mask is
0, then changes can be NULL.

reconstruct_sequence() can be used to reconstruct the second sequence given
the first sequence and a change list created by compute_lcs() with a mask
specifying sufficient content.

This isn't quite the same as the code as I have a second template (default)
parameter to define the container type to describe the change list. However,
for the sake of clarity and succinctness I omit these details and look
forward to a future discussion.

As soon as I get some time to write some docs, I'll put the code and docs in
the sandbox. The code is pretty much done now, just some name changes to
make
;-)  and some better examples.

Regards
-- Craig