Re: [boost] string_algo Formal Review

From: Pavol Droba (droba_at_[hidden])
Date: 2003-10-21 15:22:23

Hi,

Following the complaints about some missing information about the string_algo
library, pointed out by Beman, I'd like to explain here in more detail the
concepts used in the library.

InputContainerConcepts
----------------------

Unlike the STL algorithm library, which is iterator-oriented, string_algo library
has adopted a Container as a basic concept used for arguments. 

However, STL specification of a container if too strong. On many places, a simplified
version of the Container concept is sufficient. 
We use the name InputContainer for it. 

Definition:

InputContainerConcept:
{

/////// types

         typedef ... value_type;
         typedef ... size_type;
         typedef ... iterator;
         typedef ... const_iterator;
         typedef ... difference_type;

////// operations

         iterator begin();
         const_iterator begin() const;
         iterator end();
         const_iterator end() const;
         
          size_type size();
         bool empty();
};

These properties are exactly the properties the STD Container concept,
except of construction/destuction method, and swap.

This concept allows to access the values contained in the container, without altering
the state of the container itself. It means, the it is not possible to change,
what elemnts are containd by this container.
It is sufficient for those arguments in algorithms with are not altered (i.e. immutable arguments)

container_traits, one of the core facilities defined in theis library, wraps this concept,
and allows to access some of legacy C structure (C-arrays and string) using this interface.

iterator_range also implements this concept for a pair of iterators.

In the string_algo library, a container satifying this concept can be used as any non-result
argument (i.e. the argument, whose type is not used as a result).

Algorithm variants
------------------

All trasformation algorithms in the library comes in three variants. Two "copy" variants
and one inplace, mutating the input.

1. The inplace variant uses the input as a result. In general, the algorithms require,
   that this type satisfies the SequenceConcept (Std 23.2). Operations like insert, erase 
        are required.

2. Copy variant, that returns the copy of the modyfied input. This variant also uses the same type
   as input for the result. For all algorithms, SeqeuenceConcept is sufficient, however for some
   of them, standard ContainerConcept (Std 23.1) is sufficient. In addition to InputContainer,
   there is a need for a construction, because the new copy of the container is required.

        It has been proposed during this review by Pavel Vozenilek to use sequence trait (another facility for this
   library) to optimize behaviour of this variant. Now it seems possible, that this would
        also allow, to ease the requierements on the input type and use the additional feature, only when 
        they will be available.

3. Copy variant, that copies to output to an output iterator. This variant has the least requirements.
        Because, the input type is not used for the result, the input need to only satisfy InputContainer
   requirements. This variant has the same level of generality as algorithms in STL.

Pavol