Opened 14 years ago

Closed 13 years ago

#247 closed request (fixed)

IteratorWeighted: Design and implementation

Reported by: Peter Owned by: Peter
Priority: major Milestone: yat 0.4
Component: utility Version: trunk
Keywords: Cc:

Description (last modified by Jari Häkkinen)

relates to Iterator (#244) needed for ticket:246

Questions:

  1. Should we inherit from Iterator
  1. How to provide (data weight). Either have a) functions data(void) and weight(void) or b) operator* returns std::pair<double, double>

Change History (24)

comment:1 Changed 14 years ago by Peter

Description: modified (diff)

This ticket was marked as needed for ticket:246

comment:2 Changed 14 years ago by Markus Ringnér

I think it should have an iterator_category of a type that inherits from std::random_access_iterator_tag because it is a random access iterator with extra functionality. In this way std things can be made to work, but we can also separate weighted from unweighted functions in yat by using std::iterator_traits. This will be very valuable in for example our distances where a general function now can call separate functions for weighted and unweighted implementations based on the trait of the iterator.

Regarding 1: If we see no clear argument for inheritance let us not do it. 2: operator* should perhaps return data*weight because then std::sort will sort on this (after all this is what operator() returns currently in the weighted lookups).

comment:3 Changed 14 years ago by Peter

I agree. No inheritence. operator* returns same as DataLookup1D::operator().

DataLookup1D is constant though so sorting them makes no sense.

comment:4 in reply to:  3 Changed 14 years ago by Markus Ringnér

Replying to peter:

I agree. No inheritence. operator* returns same as DataLookup1D::operator().

DataLookup1D is constant though so sorting them makes no sense.

Before we decide on operator* we should perhaps check if any std algorithms makes sense on either data*weight or pair<data,weight> and go for the one that makes sense with most algorithms (and change operator() accordingly)?

comment:5 Changed 14 years ago by Peter

Ok, lets say that you create a mutable vector_weighted and want use this Iterator1DWeighted. Ok, std::sort is perhaps not the most elucidation example, so take std::copy instead. If you wanna be able to copy from one iterator to another returning data*weight is out of question since all information is not there.

OTOH returning a pair<data, weight> is not a better solution. And we can not return a simple reference (like in non-weighted case). So some kind of proxy class, but we know how it ended for vector<bool>...

comment:6 Changed 14 years ago by Markus Ringnér

Owner: changed from Jari Häkkinen to Markus Ringnér

comment:7 Changed 14 years ago by Markus Ringnér

Resolution: fixed
Status: newclosed

In [890] this was implemented as utility::IteratorWeighted? with operator* returning data*weight and with data(void) and weight(void).

comment:8 Changed 14 years ago by Peter

Resolution: fixed
Status: closedreopened

I don't like operator* returning data*weight. I would rather see pair<data, weight>. The thing is that operator* is what can be accessed in algorithms, and by returning data*weight we are hiding information. If we return the complete pair instead we allow users to build a functor to use in finding e.g. a data point with weight==0 or data>2.71.

Also if someone wanna use the template to create a mutable iterator operator= must work on the return type. In other words:

*mutable_vector_weighted.begin() = *data_lookup1d_weighted.begin()

From the single data*weight it is impossible to recreate <data, weight>.

comment:9 in reply to:  8 Changed 14 years ago by Markus Ringnér

Replying to peter:

I don't like operator* returning data*weight. I would rather see pair<data, weight>.

I does not matter to me. A pair is fine with me. I only followed what you said above: operator* should return whatever operator() returns. However, if operator() is changed to return a pair there is almost no need for an IteratorWeighted?: this could then be solved with an ordinary iterator and its return_type. But I think we need a different iterator_trait for iterators to weighted classes so we can call the appropriate algorithms. So perhaps an IteratorWeighted? that inherits from Iterator (but no functions are virtual at all), IteratorWeighted? only changes the typdef to an weighted_random_access_iterator_tag.

comment:10 Changed 14 years ago by Peter

Owner: changed from Markus Ringnér to Peter
Status: reopenednew

Ok, I'll change it so it returns a pair instead.

To merge IteratorWeighted? into Iterator, I think we should open a new ticket for.

comment:11 Changed 14 years ago by Peter

Status: newassigned

comment:12 Changed 14 years ago by Peter

I found that changing IteratorWeighted we should also change DataLookupWeighted1D as you said, but then it makes sense to also change MatrixLookupWeighted.

However MatrixLookupWeighted is inherited from DataLookup in which double operator() is declared virtual, which implies a conflict.

So we can't change in MatrixLookupWeighted. Should we still go for a change in IteratorWeighted and DataLookupWeighted1D`???

comment:13 in reply to:  12 Changed 14 years ago by Markus Ringnér

Replying to peter:

I found that changing IteratorWeighted we should also change DataLookupWeighted1D as you said, but then it makes sense to also change MatrixLookupWeighted.

However MatrixLookupWeighted is inherited from DataLookup in which double operator() is declared virtual, which implies a conflict.

So we can't change in MatrixLookupWeighted. Should we still go for a change in IteratorWeighted and DataLookupWeighted1D`???

If we cannot change MatrixLookupWeighted? we should not change DataLookupWeighted1D as any difference between operator() in the two will lead to confusion at some point. We could of course have another function that is virtual and produces data*weight for both of them.

If we want IteratorWeighted? to return a pair, I do not think we should keep it but let DataLookupWeighted1D have an iterator typdef as utility::Iterator<const std:pair<double,double>, const DataLookupWeighted1D>, and make some consistent changes to 1D and 2D lookups to allow for this. It seems weird to have an entire iterator implementation just because of operator() choices.

comment:14 Changed 14 years ago by Peter

I suggest the following:

MatrixLookupWeighted::operator() must return a double (due to inheritance). To avoid confusion DataLookupWeighted1D should return corresponding double (it is a lookup into MatrixLookupWeighted)

Then we introduce a new function in both classes that returns a pair<double, double> data_weight(size_t row, size_t col) and correspondingly for 1D case.

In IteratorWeighted? we let operator* return this std::pair, which implies the implementation is different from the one in Iterator

   return container_->operator()(index_);

but rather

   return container_->data_weight(index_);

comment:15 Changed 14 years ago by Markus Ringnér

OK, let us do it this way (changing operator() in the weighted lookups would have messed up a lot of code).

Then the only thing remaining is the names ... Remember IteratorWeighted? has a template return_type so it will work on any container with a member function data not only a data that returns something with a (data,weight) interpretation.

comment:16 Changed 14 years ago by Peter

Hm, data_weight seems logical it DataLookupWeighted1D but in IteratorWeighted it seems a bit weird. But what should we name the function? I first thought about pair, but that makes no sense because returned class could be any class (or type).

This is annoying, and even more annoying is that IteratorWeighted and Iterator are almost identical. What is the difference? The only difference, I can see is how operator* is implemented. Iterator returns container_->operator(index_) and IteratorWeighted returns container_->some_function(index_). Could one lift out this difference?

comment:17 Changed 14 years ago by Markus Ringnér

To do this in Iterator I think you would have to templatize Iterator on a pointer to a member function. To do it outside Iterator we would have to make a new virtual function with the same name everywhere (in all lookups etc; remember virtual functions can have different return tyoes).

Another thing, I am confused about Iterator being templatized on return_type while value_type (and the dependent typedefs) is set to double. Could we not avoid return_type?

comment:18 Changed 14 years ago by Peter

If we should merge the IteratorWeighted? into Iterator, we should probably wait till they have matured a bit more.

comment:19 in reply to:  18 Changed 14 years ago by Markus Ringnér

Replying to peter:

If we should merge the IteratorWeighted? into Iterator, we should probably wait till they have matured a bit more.

I agree.

In the future when things are mature, maybe this can be solved with iterator adapters? I have no idea if this would work for this. But the std uses e.g.

vector<int>::iterator pos;
vector<int>::reverse_iterator rpos(pos);

where reverse_iterator is an adapter that redefine the increment and decrement operators. So maybe one could have an adapter that turns an iterator into a weighted iterator by redefining operator* ?

comment:20 Changed 14 years ago by Markus Ringnér

Summary: Iterator1DWeightedIteratorWeighted: Design and implementation

comment:21 Changed 14 years ago by Peter

I was thinking of something similar to what markus describe in comment:ticket:251:19

Default operator* returns (*container_)(index_) and then one can specialize for special containers such as DataLookupWeighted1D

comment:22 Changed 13 years ago by Jari Häkkinen

Description: modified (diff)

comment:23 Changed 13 years ago by Peter

I think we should not merge Iterator and IteratorWeighted?. We want IteratorWeighted? to have an extended iterface with functions data and weight that should be faster than calling through operator*.

Operator* should return a const pair<double, double> so that all information about the data point is returned and can be used in algorithms. This pair must be created on the fly and therefore is also functions data and weight provided.

Possibly we could store an Iterator as a member and use its functionality for the arithmetic, which implies future changes only need to be implemneted in one place. OTOH it seems like waste of time right now to recode IteratorWeighted? when it already works.

comment:24 Changed 13 years ago by Peter

Resolution: fixed
Status: assignedclosed

IteratorWeighted? is removed. Functionality instead using Iterator with IteratorPolicyWeighted?. The Policy takes care of everything related to operator* and such whereas Iterator take care of the arithmetics.

Note: See TracTickets for help on using tickets.