
Boost : 
From: Baptiste Lepilleur (blepctc_at_[hidden])
Date: 20020905 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 shorthanded
> // 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk