RE: [boost] Re: Longest Common Subsequence

From: Rozental, Gennadiy (Gennadiy_at_[hidden])
Date: 2002-09-17 14:28:37

> A brief discussion over the class or function interface has 
> already taken
> place on the list. I concluded that the class interface was 
> preferable and
> Baptiste Lepilleur provided a nice justification for it. "it keeps the
> algorithm interface as simple as possible and mesh very well 
> with existing
> STL algorithm. It makes it less clumsy to add functions to extend the
> interface, and allows
> for automatic type deduction. It also keep the algorithm 
> apart from sugar
> coat functions like apply_diff ".

[...]
> The output of the LCS algorithm was difficult. I opted for the mask to
> determine was is required and a container to receive the 
> requested results
> as a good solution, but admit it is not necessarily the best.
> 
> The use of a user-defined predicate to process the result set 
> on a callback
> is an interesting approach. However, I think your suggestion 
> of a binary
> predicate that is passed elements contained in both original 
> sequences (ie.
> elements of the subsequence) is too limited. The user would 
> have to do a lot
> of within the predicate it track the changes if they were 
> interested in the
> elements removed from the first or added to the second, in 
> repect of the
> other. The 'change list' approach that I adopted works well 
> in all three
> situations.

You seems could not get my point. Changes list is only one form of output
user may want from LCS algorithm. What If I just want elements of second
sequence that belongs to LCS? 
   While designing generoc algorithm you should not think too much about the
data structure. You are trying to formalize the algorithm. And if
abstraction os good it will work on any data structures.

In the code you pesented the only idea that qualify to be a generic
algorithm is LCS algorithm itself. Everything else is just an example
application.

In any case you never ever should mix several independent algorithms in one
bottle. ALgorithm interface is always only one function. It does not require
classes. In fact there could be some C++ specific technical issues in which
case you opt to use functors that look like a class but in essence it's
still pure function interface with some type information attached.
  In your case there is:
1. generic LCS algorithm implementation
2. specific application of the LCS algorithm that produce result in form of
change_list and allows to apply this result to reconstruct one sequence from
another.

Again IMHO only part 1 qualify as generic algorithm. Second is just specific
application that could belong to, let say, examples section.
 
Regards,

Gennadiy.