=====================================================
 582484 Algorithm Libraries
=====================================================

--------------------
Exercise 1 solutions
--------------------


These algorithms will be used later:

      **find.hpp**


      .. include:: find.hpp
         :literal:

1. int_range_iterator

   .. include:: teht1.cpp
      :literal:

2. smooth_iterator

   .. include:: teht2.cpp
      :literal:

3. a) Even if type T is different than the type A of the values in 
      the sequence, the algorithm still works if the operator!=(A, T)
      is defined. That is to say, we can compare objects of types A and T
      with each other. For example, it is allowed to do comparison
      between ints and floats, like this: 4 != 5.0.

   b) We can use iterator traits to extract the true value type
      of the sequence. In question 2 this type was float. If this
      type is used as the third parameter, the call ``find(begin, end, 2);``
      would still work. Even though the function find expects
      float as its third parameter, the integer 2 is ok since it is
      implicitly converted to a float.

      If we try to use an illegal parameter, the two versions
      of find give different kind of error message. This is demonstrated
      by the following code.


      .. include:: teht3.cpp
         :literal:

      First version complains that the expression "\*begin != value"
      is not valid.
      The second version complains that the type A is not the
      value type of the sequence (should be 'char').

      In other words, 

	 ``std::string::iterator i = ::find(text.begin(), text.end(), a);``

      works when 

         ``std::string::iterator i = text.begin();``
	 ``while (*i != text.end() && *i != a) ++i;``

      works (in the sense that above is both syntactically and semantically
      correct).

      But the second version is more restricted, in addition to the above
      it also requires that the type of a can be converted to (or
      is the same as) the value type of the sequence.


      Also note the qualified name ::find. Otherwise there would
      be ambiguity in choosing between the *find* I provided and 
      the *find* algorithm of the STL (which probably comes from
      the <string> header). This ambiguity is due to `Koenig lookup`_.


4. a) 

   .. include:: teht4.cpp
      :literal:


   b) If we assume that the two sequences have the same length,
      we only need to compare when we are at the end of one of the
      sequences. This is a bit more efficient. 

      Note that we can implement the four iterators version in terms
      of the three iterators version. We can also do this vice versa,
      but then we would lose the possibility of optimisation.

      The STL algorithm *copy* uses three iterators instead of four.
      (Actually, copy cannot be implemented in general with four
      iterators, since the second sequence can be specified
      with an output iterator. And for output iterators comparison
      operators need not be defined. Check out the requirements of
      copy algorithm.) 
      So, using three iterators
      form is consistent with other STL algorithms too.

      STL prefers to be simplistic, consistent, generic and efficient 
      instead of user friendly (at least in this case).

.. _Koenig lookup: http://en.wikipedia.org/wiki/Koenig_lookup