Re: [boost] Container Difference proposal

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-09-05 19:59:42

This looks like it would be a cool addition to the sequence_algo library
that's growing in the boost-sandbox. Craig, why don't you send me your
sourceforge ID so I can give you CVS permissions.

On Wed, 4 Sep 2002, Craig Henderson wrote:

> 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
>
>
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

----------------------------------------------------------------------
 Jeremy Siek                          http://www.osl.iu.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------