Re: [boost] Container Difference proposal

From: Baptiste Lepilleur (blepctc_at_[hidden])
Date: 2002-09-05 17:24:15

Hi Craig,

I would suggest slighty changing your example. I'm not familar with the
Longest Common Subsequence
algorithm and looking at your example I was falsely lead to believe that
(possibly):
- the input sequence need to be sorted
- the matched element needed to be at the same position in the input
sequences

Giving a quick look at the page the pointed to, it does not seems to be the
case (only the relative order seems to matter). From what I understood, LCS
is a "diff" algorithm. It's equivalent to a combination of set_intersect and
set_difference on two sorted sequence, right ?

Beyond the count of inserted and deleted elements, do we also get access to
what was deleted, inserted ?

Still have to look deeper into what that algorithm can do, but it looks
promising.

On the practial side, wouldn't it be simpler is compute_lcs() returned 0 if
there was no common sequence ? (this avoid dealing with a special case).

Baptiste.

----- Original Message -----
From: "Craig Henderson" <cdm.henderson_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Wednesday, September 04, 2002 8:20 PM
Subject: [boost] Container Difference proposal

> Is there any interest in adding an algorithm to the Boost libraries to
> compute the difference between containers of objects?
>
> I have written a template implementation of the Longest Common Subsequence
> algorithm as described by David Eppstein at
> http://www1.ics.uci.edu/~eppstein/161/960229.html and would like to work
on
> incorporating it into Boost if there is enough interest.
>
>
> By way of an example, the following will find the difference between two
> numeric arrays.
>
> int main(int, char **)
> {
>     typedef boost::array<size_t, 8> array_t;
>
>     array_t data1 = { 1, 3, 5, 7, 9, 11, 13, 15 };
>     array_t data2 = { 2, 3, 5, 8, 9, 11, 13, 15 };
>     array_t::const_iterator it;
>
>     for (it=data1.begin(); it !=data1.end(); ++it)
>         std::cout << *it << "  ";
>     std::cout << std::endl;
>     for (it=data2.begin(); it !=data2.end(); ++it)
>         std::cout << *it << "  ";
>     std::cout << std::endl;
>
>     // create a typedef first so that we can use a short-handed
>     // version later
>     typedef cmp::compare< cmp::data_source<size_t> > compare_t;
>     compare_t compare(data1.begin(), data1.end(), data2.begin(),
> data2.end());
>
>     signed                lcs;
>     compare_t::result_set seq;
>
>     // process the data sources
>     if ((lcs = compare.compute_lcs(&seq, cmp::REMOVE | cmp::KEEP |
> cmp::INSERT)) != -1)
>     {
>         std::cout << "Comparing numeric array" << std::endl
>                   << "Lowest Common Subsequence length is " << lcs <<
> std::endl;
>
>         compare_t::result_set::iterator it  = seq.begin();
>         compare_t::result_set::iterator ite = seq.end();
>         for (; it != ite; ++it)
>         {
>             compare_t::result_set::value_type res = *it;
>             if (res->type() == cmp::REMOVE)
>                 std::cout << "DEL: " << res->data() << std::endl;
>             else if (res->type() == cmp::INSERT)
>                 std::cout << "INS: " << res->data() << std::endl;
>         }
>         seq.erase(seq.begin(), seq.end());
>     }
>
>     return 0;
> }
>
>
>
> Expected output:
>
> 1  3  5  7  9  11  13  15
> 2  3  5  8  9  11  13  15
> Comparing numeric array
> Lowest Common Subsequence length is 6
> DEL: 1
> INS: 2
> DEL: 7
> INS: 8