Re: ublas: vector<>::upper_bound()

From: jhrwalter (walter_at_[hidden])
Date: 2002-03-10 09:05:24

--- In boost_at_y..., Kresimir Fresl <fresl_at_g...> wrote:
> 
> IMHO the current definition/implementation of
> `numerics::vector<>::upper_bound()' is wrong [1,2].
> 
> I think that semantics of `numerics::vector<>::upper_bound()'
> should be identical to that of `std::map<>::upper_bound()' [3],
> which ``returns an iterator pointing to the first element with key
> *greater* than k'' (where `k' is given argument).
 
That's not what we need for the iterators, IMO. May be upper_bound
()/lower_bound() are bad names.
 
[examples snipped]
 
> There is currently no difference between
> `vector<>::upper_bound()' and `vector<>::lower_bound()'.
> Both behave as `std::map<>::lower_bound()' which ``returns
> an iterator pointing to the first element with key not less than 
k''.

Yes.
 
The names lower_bound()/upper_bound() clearly stem from std::map. 
These member are essential for the iterators of binary operation 
expression templates: given two unit vectors uv1 (2, 0) (= [1, 0]) 
and uv2 (2, 1) (= [0, 1])  the following should hold:
 
(uv1 + uv2).lower_bound (0).index () == 0, whereas the internally 
used iterators it1/it2 of uv1/uv2 give it1.index() == 0 and it2.index
() == 1.
(uv1 + uv2).upper_bound (0).index () == 1, whereas the internally 
used iterators it1/it2 of uv1/uv2 give it1.index() == 0 and it2.index
() == 1.
 
> Definition of `numerics::vector<>::upper_bound()' should be
> something like
> 
>       iterator upper_bound (size_type i) { return find (i+1); }
> 
> I am not quite sure how this will reflect to `vector<>::end()'.
> It should be changed because of the current definition of
> `vector<>::find()' [which is `return iterator (*this, i);'
> or `return iterator (*this, data_.begin () + i);' ], but *not* into:
> 
>       iterator end () { return upper_bound (size_-1); }
> 
> because size_ (which is unsigned integer) can be 0.
> Maybe to
> 
>       iterator end () { return lower_bound (size_); }
> 
> Similarly, `unit_vector<>::upper_bound()' should be:
> 
>       const_iterator upper_bound (size_type i) const {
>             return const_iterator (*this, std::min (i+1, index_+1));
>       }
> 

OTOH do you know a better name for the existing beasts?
 
> 
> Sincerely,
> 
> fres
> 
> 
> [1] And also of `numerics::unit_vector<>::upper_bound()'
> and `numerics::sparse_vector<>::upper_bound()' and,
> I am afraid, of `upper_boundD()' in various matrix classes.
> 
> [2] `find()', `lower_bound()' and `upper_bound()' are listed
> in interface of `numerics::vector<>' in docs, but I didn't find
> their description (AFAIK functions `find()' etc. are described
> only in docs for `compressed_array<>'; their descriptions are
> similar to those for `std::map<>').

Yep. I'm not sure, if these members aren't an implementation detail 
only.
 
> Some history: I first noticed that something was wrong
> with `unit_vector<>::upper_bound()':
> 
> --------------------------------------------------------------------
---------
>      numerics::vector<double> v (8);
>      for (std::size_t i = 0; i < 8; ++i)  v[i] = i;
>      // v = { 0, 1, 2, 3, 4, 5, 6, 7 }
>      numerics::unit_vector<double> uv (n, 3);
>      // uv = { 0, 0, 0, 1, 0, 0, 0, 0 }
>      std::cout << numerics::inner_prod (v, uv) << std::endl;
> --------------------------------------------------------------------
----------
> 
> And the result is ... `0' instead of `3'.

Sorry, that's a bug in the implementation of 
unit_vector<>::upper_bound. It has to read:
 
const_iterator upper_bound (size_type i) const {
       // return const_iterator (*this, std::min (i + 1, index_));
       return const_iterator (*this, std::min (i, index_ + 1));
}
 
> There was a long way to go ;o), but finally I arrived to
> `Packed bidirectional specialization' of
> `vector_scalar_binary<>::evaluate()' in `vector_et.h'.
> 
> Its arguments are `v.begin(), v.end(), uv.begin(), uv.end()',
> but [uv.begin(), uv.end()) is an empty range.
> 
> And `unit_vector<>::end()' is defined/implemeted in terms of
> `unit_vector<>::upper_bound()'. QED ;o)
> 
> [3] After all, `std::map<std::size_t, T>' can be used as
> StorageType in `numerics::sparse_vector<T, StorageType>'.
 
Thanks for your effort.
 
Joerg