Sign in to follow this  
mfawcett

Idiom for returning unknown number of outputs?

Recommended Posts

When returning a range of unknown size, I usually use an output iterator. For instance, a pathfinding algorithm that returns all the points in the shortest path would look like:
template <typename OutputIterator>
void search(const float3 &start, const float3 &end, OutputIterator output);
This is great because the user (having more information) can use a deque, or vector, or reuse the storage from the previous call, etc... But how would one deal with the output if you were returning an unknown number of paths, each with an unknown number of points in the path? To put it in more concrete terms, I have a function that will try to calculate any number of routes that the user requests. I could easily just require them to make a vector of vectors, but I would like for the user to retain the flexibility to specify storage.
// Calculate 10 different routes from start to end.
vector<vector<float3> > paths;
multiple_route_search(start, end, 10, paths);
might be the ideal syntax, but would require multiple_route_search to specialize on lots of different container type combinations. I also thought about simply returning them all through one output iterator, just like the first example, but putting in some sort of sentinel value (like the last point repeated twice since that should not happen in a path) to signify the start of the next path, but that seems like I'm forcing too much extra work on the user for him to be able to get at each individual path, especially if he wants the 10th path out of 10. I'd love to hear people's design ideas... [Edited by - mfawcett on November 20, 2008 1:44:54 PM]

Share this post


Link to post
Share on other sites
What about simply using an extra template type to specify the storage in the OutputIterator?

template <typename OutputIterator, class Path>
void multiple_route_search(const float3 &start, const float3 &end, OutputIterator output);

typedef vector<float3> Path;
vector<Path> paths;

multiple_route_search<Path>(start, end, 10, std::back_inserter(paths));

Share this post


Link to post
Share on other sites

// sketch

routes_view view = multiple_route_search(start, end);
// ^maybe this should take a route_generator argument?

route_view_iterator vb = view.begin();
route_view_iterator ve = view.end();

// do whatever with the routes...
for ( ; vb != ve; ++vb)
{
route_iterator rb = vb->begin();
route_iterator re = vb->end();

for ( ; rb != re; ++rb)
{
float3 &point = *rb;
// ...
}
}



Incrementing a route_view_iterator would prepare a "route_generator" that a route_iterator would use to generate a route as it is incremented.

This way the user can generate as many or as few routes as needed, and look at or ignore as many points on each route as appropriate.

It may not fit your design, though. I guess it depends heavily on how easy it is for you to generate routes a step at a time...

Share this post


Link to post
Share on other sites
Quote:
Original post by the_edd
It may not fit your design, though. I guess it depends heavily on how easy it is for you to generate routes a step at a time...


Interesting, I had thought about making the user do it one step at a time but scrapped the idea eventually. The problem is that each step requires all previous information since each path generated must be some amount different from the previous paths. The output of the function should be N different paths from start to end, all differing by some amount.

i.e. give the end-user many different options to get from point A to point B.

Share this post


Link to post
Share on other sites
Quote:
Original post by mfawcett
Quote:
Original post by the_edd
It may not fit your design, though. I guess it depends heavily on how easy it is for you to generate routes a step at a time...


Interesting, I had thought about making the user do it one step at a time but scrapped the idea eventually. The problem is that each step requires all previous information since each path generated must be some amount different from the previous paths. The output of the function should be N different paths from start to end, all differing by some amount.

i.e. give the end-user many different options to get from point A to point B.


I was afraid of that :)

Well if you have to store the previous steps, you might as well let them iterate over the container you use to do so. route_iterator could be your_container::iterator.

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
What about simply using an extra template type to specify the storage in the OutputIterator?
*** Source Snippet Removed ***

I think I can already get that by using iterator_traits<OutputIterator>::value_type. I'm trying to figure out how it helps me though. Do you have more details for your proposed solution? Thanks for taking the time to think about it.

Share this post


Link to post
Share on other sites
Quote:
Original post by the_edd
I was afraid of that :)

Well if you have to store the previous steps, you might as well let them iterate over the container you use to do so. route_iterator could be your_container::iterator.


I'm not storing them in a container, the paths produced internally are basically path nodes, with a parent pointer and some other information (in open list, closed list, costs, etc). What they get back should just be the path, however, you did get me thinking. What if I just returned a bunch of iterators? The iterator could just contain a pointer to the node and the increment operator could follow the parent pointer, the dereference operator would return the point.


template <typename OutputIterator>
void multi_route_search(/*points*/, size_t num_paths, OutputIterator output);

vector<path_iterator> output; // could also be deque, list, etc...
multi_route_search(/*points*/, 10, back_inserter(output));

// Loop through each path and each path's points
for (size_t i = 0; i < output.size(); ++i)
{
for (path_iterator iter = output[i]; iter != path_iterator(); ++iter)
{
// do stuff with the point
const float3 &current = *iter;
}
}


Edit: sigh, there are major object lifetime issues with this approach - specifically, how would the iterators returned maintain a reference to the path nodes and their parents. You could use shared_ptrs for this, but then the memory allocated in multi_route_search (including all the extra stuff a node contains) remains in use until all of their path_iterators go out of scope.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this