Re: [boost] Algorithms and Formal Reviews

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-01-10 19:01:48

On Wed, 10 Jan 2001, Beman Dawes wrote:

> I've been thinking about sequence algorithms because of several recent 
> boost postings, and string algorithms because I've seen several nice onces 
> recently.   See below for a string algorithm example (by Jens Maurer).

Sounds like there may be types of algorithms.  Maybe more than one
"library" would be needed.  What is the difference between an algorithm
and a useful snippet?

> The Boost Formal Review procedure works pretty well for whole libraries, 
> and would presumably work well if someone submitted a whole library of 
> algorithms.
> 
> But what happens if someone just has one or two neat algorithms to 
> submit?  Neither the submitter nor the boost membership is going to want to 
> go through a whole Formal Review just for one or two algorithms, 
> particularly if they are only five or ten lines of code each.

Good point.

> One way to smooth the process would be to have a Boost Algorithms Policy 
> which defines what algorithms are acceptable and what aren't.  Appoint a 
> couple of people as moderators of the Boost Algorithms Library (with CVS 
> write access).  They will act as permanent Review Managers + library 
> maintainers.  They would check that submissions meet the Algorithms Policy, 
> and then (?) to ensure sufficient peer-review.  Once the algorithms 
> moderators agree the algorithm is accepted, they can move it into the 
> library with a minimum of fuss.
> 
> (?) might be something like stick the algorithm in a queue to give people 
> time to look at it and comment.

That sounds good.  An announcement that some algorithms are ready for
review.  Accept is the default with no action required.  Complaints
should be handled.

> // replace the first instance of name in s with value
> void replace(std::string & s,
> 	     const std::string & name, const std::string & value)
> {
>    std::string::size_type p = s.find(name);
>    if(p != std::string::npos)
>      s.replace(p, name.length(), value);
> }

Is this an algorithm or a function on string.  Is there a general
stl like algorithm in there?  It would need to be a _copy type
because algorithms can't modify the container if all they have is
iterators.

template <class Fiter1, class Fiter2, class Iiter, class Oiter>
void replace_first_copy (Fiter1 first1, Fiter1 last1,
      Fiter2 first2, Fiter2 last2, Iiter first3, Iiter last3, Oiter res) {
   Fiter1 pos(search(first1, last1, first2, last2));
   copy(first1, pos, res);
   if (pos != last1) {
      copy(first3, last3, res);
      advance(pos, distance(first2, last2));
      copy(pos, last1, res);
      }
   }

How about algorithms templated on containers?  That would open the
door for many different ideas.  Much different from the stl style.
Erase_if is of that type.

template <class Con1, class Con2, class Con3>
void replace_first (Con1& c1, Con2 const& c2, Con3 const& c3) {
   typename Con1::iterator pos =
         search(c1.begin(), c1.end(), c2.begin(), c2.end());
   if (pos != c1.end()) {
      typename Con1::iterator last = pos;
      advance(last, c2.size());
      pos = c1.erase(pos, last);
      c1.insert(pos, c3.begin(), c3.end());
      }
   }

Is the original above a specialization of this?  Should it be for
basic_string<> rather than string?

Just some food for thought on what "algorithm" means.

John