views:

1270

answers:

5

I'm looking for a container that maps from a double to object pointers. However, each key is simply a range of doubles that would correspond to that object.

For example, there could be a key/value pair that's <(0.0 3.0), ptr>, or <(3.5 10.0), ptr2>

container[1.0] should return ptr, container[3.0] should also return ptr, and container[-1.0] should be undefined.

Is there any object with similar behaviour by default or will I have to implement it myself?

Edit

Here's the actual code that I've written, it might be easier to debug/offer advice on it.

// Behavior: A range is defined mathematically as (min, max]

class dblRange
{
public:
    double min;
    double max;

    dblRange(double min, double max)
    {
     this->min = min;
     this->max = max;
    };

    dblRange(double val)
    {
     this->min = val;
     this->max = val;
    };

    int compare(const dblRange rhs)
    {
     // 1 if this > rhs
     // 0 if this == rhs
     //-1 if this < rhs
     if (rhs.min == rhs.max && min == max)
     {
      /*if (min > rhs.min)
       return 1;
      else if (min == rhs.min)
       return 0;
      else
       return -1;*/
      throw "You should not be comparing values like this. :(\n";
     }
     else if (rhs.max == rhs.min)
     {
      if (min > rhs.min) 
       return 1;
      else if (min <= rhs.min && max > rhs.min)
       return 0;
      else // (max <= rhs.min)
       return -1;
     }
     else if (min == max)
     {
      if (min >= rhs.max)
       return 1;
      else if (min < rhs.max && min >= rhs.min)
       return 0;
      else // if (min < rhs.min
       return -1;
     }

     // Check if the two ranges are equal:
     if (rhs.min == min && rhs.max == max)
     {
      return 0;
     }
     else if (rhs.min < min && rhs.max <= min)
     {
      // This is what happens if rhs is fully lower than this one.
      return 1;
     }
     else if (rhs.min > min && rhs.min >= max)
     {
      return -1;
     }
     else
     {
      // This means there's an undefined case. Ranges are overlapping, 
      // so comparisons don't work quite nicely.

      throw "Ranges are overlapping weirdly. :(\n";
     }
    };

    int compare(const dblRange rhs) const
    {
     // 1 if this > rhs
     // 0 if this == rhs
     //-1 if this < rhs
     if (rhs.min == rhs.max && min == max)
     {
      /*if (min > rhs.min)
       return 1;
      else if (min == rhs.min)
       return 0;
      else
       return -1;*/
      throw "You should not be comparing values like this. :(\n";
     }
     else if (rhs.max == rhs.min)
     {
      if (min > rhs.min) 
       return 1;
      else if (min <= rhs.min && max > rhs.min)
       return 0;
      else // (max <= rhs.min)
       return -1;
     }
     else if (min == max)
     {
      if (min >= rhs.max)
       return 1;
      else if (min < rhs.max && min >= rhs.min)
       return 0;
      else // if (min < rhs.min
       return -1;
     }

     // Check if the two ranges are equal:
     if (rhs.min == min && rhs.max == max)
     {
      return 0;
     }
     else if (rhs.min < min && rhs.max <= min)
     {
      // This is what happens if rhs is fully lower than this one.
      return 1;
     }
     else if (rhs.min > min && rhs.min >= max)
     {
      return -1;
     }
     else
     {
      // This means there's an undefined case. Ranges are overlapping, 
      // so comparisons don't work quite nicely.

      throw "Ranges are overlapping weirdly. :(\n";
     }
    };

    bool operator== (const dblRange rhs ) {return (*this).compare(rhs)==0;};
    bool operator== (const dblRange rhs ) const {return (*this).compare(rhs)==0;};
    bool operator!= (const dblRange rhs ) {return (*this).compare(rhs)!=0;};
    bool operator!= (const dblRange rhs ) const {return (*this).compare(rhs)!=0;};
    bool operator< (const dblRange rhs ) {return (*this).compare(rhs)<0;};
    bool operator< (const dblRange rhs ) const {return (*this).compare(rhs)<0;};
    bool operator> (const dblRange rhs ) {return (*this).compare(rhs)>0;};
    bool operator> (const dblRange rhs ) const {return (*this).compare(rhs)>0;};
    bool operator<= (const dblRange rhs ) {return (*this).compare(rhs)<=0;};
    bool operator<= (const dblRange rhs ) const {return (*this).compare(rhs)<=0;};
    bool operator>= (const dblRange rhs ) {return (*this).compare(rhs)>=0;};
    bool operator>= (const dblRange rhs ) const {return (*this).compare(rhs)>=0;};

};

Right now I'm having trouble having the map accept a double as a key, even though the comparison operators are defined.

Here's some driving code that I'm using to test if it would work:

std::map<dblRange, int> map;
map[dblRange(0,1)] = 1;
map[dblRange(1,4)] = 2;
map[dblRange(4,5)] = 3;

map[3.0] = 4;
+4  A: 

Create a class DoubleRange to store the double range, and implement the comparison operators on it. That way, std::map will do the rest for you, with the DoubleRange class as the key.

Daniel Earwicker
So, more specifically, what would each comparison mean? Would operator== with a single double check whether the double is in the range?
Andrei Krotkov
The operators need to compare DoubleRanges with each other.
Daniel Earwicker
How would you access the map based on a single double then?
Andrei Krotkov
You'd give DoubleRange a constructor that takes a single double and assigns it to both ends of the range, and make == return true if one range overlaps with another (the keys stored in the map would need to be non-overlapping).
Daniel Earwicker
myMap[5.3] would cause the compiler to construct a temporary DoubleRange from the 5.3 value, allowing the lookup to work.
Daniel Earwicker
Alex Martelli
Indeed - but if you're going to define a type representing a range that can be compared with other ranges, you may as well think carefully about what each standard comparison operation should mean.
Daniel Earwicker
Daniel Earwicker
That's clever. I was trying to compare against a double, but it didn't seem to want to work.
Andrei Krotkov
You should be careful with this approach, defining < like this could lead to infinite loops or unexpected overwriting if your ranges are overlapping (and since these are floating point, if your endpoints aren't exactly representable, you might have overlapping boundaries even if you don't expect it)
Todd Gardner
Very good point. Is there a way to force the program to use the comparison against double instead of having a special case of min==max?
Andrei Krotkov
I've posted the code as an edit instead of an answer.
Andrei Krotkov
A: 

One approach would be to calculate the "break points" before hand:

typedef vector< tuple<double, double, foo*> > collisionlist_t;
const collisionlist_t vec;
vec.push_back(make_tuple(0.0, 3.0, ptr));
vec.push_back(make_tuple(3.5, 10.0, ptr2));
// sort 
std::map<double, foo*> range_lower_bounds;
for(collisionlist_t::const_iterator curr(vec.begin()), end(vec.end()); curr!=end; ++curr)
{
    /* if ranges are potentially overlapping, put some code here to handle it */
    range_lower_bounds[curr->get<0>()] = curr->get<2>();
    range_lower_bounds[curr->get<1>()] = NULL;
}

double x = // ...
std::map<double, foo*>::const_iterator citer = range_lower_bounds.lower_bound(x);
Todd Gardner
I considered this approach, but I'd like to make a much more intuitive approach, as seen by my driving code. If I can get that to work correctly, I'd prefer it.
Andrei Krotkov
+1  A: 

I mostly agree with Earwicker in that you can define a range. Now, I am in favor of implementing operators with the real meaning (do what basic types do: two ranges compare equal if both ranges ARE equal). Then you can use the third map parameter to pass it a comparison functor (or function) that solves your particular problem with this map.

// Generic range, can be parametrized for any type (double, float, int...)
template< typename T >
class range
{
public:
    typedef T value_type;

    range( T const & center ) : min_( center ), max_( center ) {}
    range( T const & min, T const & max )
        : min_( min ), max_( max ) {}
    T min() const { return min_; }
    T max() const { return max_; }
private:
    T min_;
    T max_;
};

// Detection of outside of range to the left (smaller values):
//
// a range lhs is left (smaller) of another range if both lhs.min() and lhs.max() 
// are smaller than rhs.min().
template <typename T>
struct left_of_range : public std::binary_function< range<T>, range<T>, bool >
{
    bool operator()( range<T> const & lhs, range<T> const & rhs ) const
    {
        return lhs.min() < rhs.min()
            && lhs.max() <= rhs.min();
    }
};
int main()
{
    typedef std::map< range<double>, std::string, left_of_range<double> > map_type;

    map_type integer; // integer part of a decimal number:

    integer[ range<double>( 0.0, 1.0 ) ] = "zero";
    integer[ range<double>( 1.0, 2.0 ) ] = "one";
    integer[ range<double>( 2.0, 3.0 ) ] = "two";
    // ...

    std::cout << integer[ range<double>( 0.5 ) ] << std::endl; // zero
    std::cout << integer[ range<double>( 1.0 ) ] << std::endl; // one
    std::cout << integer[ 1.5 ] << std::endl; // one, again, implicit conversion kicks in
}

You must be careful with equality and comparisons among double values. Different ways of getting to the same value (in the real world) can yield slightly different floating point results.

David Rodríguez - dribeas
Very elegant answer!
Andrei Krotkov
A: 

Another suggestion: Use a mathematical transform to map the index from REAL to INT which can be directly compared.

If these ranges are multiple and dense there's also a structure known as an "interval tree" which may help.

Brian
A: 

Are the intervals open or closed or half open? I will assumed closed. Note that the intervals cannot overlap by the definition of a map. You will also need splitting rules for when one inserts an over lapping interval. the rules need to decide where the split takes place and must take into account floating point epsilon.

this implementation uses map::lower_bound and does NOT use a class as the domain of the map

map::lower_bound returns an iterator to the first element in a map with a key value that is equal to or greater than that of a specified key. (ie the least key greater than or equal to K. An unfortunate choice of STL method names as it is the least upper bound of K.)

template <class codomain>
class RangeMap : private std::map<double,std::pair<double,codomain>{
public:
    typedef double domain;
    typedef std::map<double,std::pair<double,codomain>:: super;
    typename super::value_type value_type;
protected:
    static domain& lower(const value_type& v){
        return v.first;
    }

    static domain& upper(const value_type& v){
        return v.second.first;
    }

    static codomain& v(const value_type& v){
        return v.second.second;
    }

public:

    static const domain& lower(const value_type& v){
        return v.first;
    }
    static const domain& upper(const value_type& v){
        return v.second.first;
    }
    static const codomain& v(const value_type& v){
        return v.second.second;
    }


    static bool is_point(const value_type& vf) {
        return lower(v) == upper(v);
    }

    static bool is_in(const domain& d,const value_type& vf) {
        return (lower(v) <= d) && (d <= upper(v));
    }


    const_iterator greatest_lower_bound(const domain& d)const {
        const_iterator j = super::lower_bound(d);
        if(j!=end() && j->first==d) return j;//d is the lh side of the closed interval
                                             //remember j->first >= d because it was lower but its the first
        if(j==begin()) return end();//d < all intervals
        --j;                        //back up
        return j;
    }
    const_iterator find(domain& d) {
        const_iterator j = greatest_lower_bound(d);
        if (is_in(j,d)) return j;
        return end();
    }
    iterator greatest_lower_bound(const domain& d) {
        iterator j = super::lower_bound(d);
        if(j!=end() && j->first==d) return j;//d is the lh side of the closed interval
                                             //remember j->first >= d because it was lower but its the first
        if(j==begin()) return end();//d < all intervals
        --j;                        //back up
        return j;
    }
    const_iterator find(domain& d) const{
        iterator j = greatest_lower_bound(d);
        if (is_in(j,d)) return j;
        return end();
    }  //so much for find(d) 
    iterator find(domain& d){
        iterator j = greatest_lower_bound(d);
        if (is_in(j,d)) return j;
        return end();
    }  //so much for find(d) 

     struct overlap: public std::exception{
     };
     bool erase(const double lhep,const double rhep);
     //you have a lot of work regarding splitting intervals erasing when overlapped
     //but that can all be done with erase, and insert below. 
     //erase may need to split too
     std::pair<iterator,bool>
     split_and_or_erase_intervals(const double lhep,
                                  const double rhep, 
                                  const codomain& cd);
     //the insert method - note the addition of the overwrtite 
     std::pair<iterator,bool>
     insert(const double lhep,const double rhep,const codomain& cd,bool overwrite_ok){
          if( find(lhep)!=end() || find(rhep)!=end() ) {
              if(overwrite_ok){
                 return split_and_or_erase_intervals(const double lhep,
                                                     const double rhep, 
                                                     const codomain& cd);
              }
              throw overlap();
          }
          return insert(value_type(lhep,pair<double,codomain>(rhep,cd)));
     }
 };
pgast