ublas: vector<>::upper_bound()

From: Kresimir Fresl (fresl_at_[hidden])
Date: 2002-03-09 07:45:22

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).

As a concrete example:
--------------------------------------------------------------------------
     typedef std::map<std::size_t, double> sp_vec_t;
     typedef sp_vec_t::value_type v_t;
     typedef sp_vec_t::iterator it_t;

     sp_vec_t sv;
     for (int i = 0; i < 8; ++i)  sv.insert (v_t (i, 0.1 * i));
     // sv = { (0: 0.0), (1: 0.1), ... , (7: 0.7) }

     it_t lb = sv.lower_bound (3);
     it_t ub = sv.upper_bound (3);
     std::cout << lb->first << ": " << lb->second << " | "
                    << ub->first << ": " << ub->second << std::endl;
--------------------------------------------------------------------------
The output is: `3: 0.3 | 4: 0.4'.

In other words, `[lb, ub)' is *non-empty* range and

     for (it_t i = lb; i != ub; ++i)
        std::cout << i -> first << ": " << i -> second << std::endl;

prints:  `3: 0.3'.

But the output of:
--------------------------------------------------------------------------
     typedef numerics::vector<double> vct_t;
     typedef vct_t::iterator it_t;

     vct_t v (8);
     for (std::size_t i = 0; i < 8; ++i)  v[i] = 0.1* i;

     it_t lb = v.lower_bound (3);
     it_t ub = v.upper_bound (3);
     std::cout << lb.index() << ": " << *lb << " | "
                    << ub.index() << ": " << *ub << std::endl;
--------------------------------------------------------------------------
is:  `3: 0.3 | 3: 0.3',  ie.  `[lb, ub)' is now  an *empty* range
and

     for (it_t i = lb; i != ub; ++i)
        std::cout << i.index() << ": " << *i << std::endl;

prints nothing.

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''.

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));
      }

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<>').

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'.

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>'.