diff options
Diffstat (limited to 'src/base/range_map.hh')
-rw-r--r-- | src/base/range_map.hh | 123 |
1 files changed, 120 insertions, 3 deletions
diff --git a/src/base/range_map.hh b/src/base/range_map.hh index 17ecb9290..6d3450739 100644 --- a/src/base/range_map.hh +++ b/src/base/range_map.hh @@ -52,9 +52,13 @@ class range_map i = tree.upper_bound(r); - if (i == tree.begin()) - // Nothing could match, so return end() - return tree.end(); + if (i == tree.begin()) { + if (i->first.start <= r.end && i->first.end >= r.start) + return i; + else + // Nothing could match, so return end() + return tree.end(); + } i--; @@ -126,4 +130,117 @@ class range_map }; +template <class T,class V> +class range_multimap +{ + private: + typedef std::multimap<Range<T>,V> RangeMap; + RangeMap tree; + + public: + typedef typename RangeMap::iterator iterator; + + template <class U> + std::pair<iterator,iterator> find(const Range<U> &r) + { + iterator i; + iterator j; + + i = tree.lower_bound(r); + + if (i == tree.begin()) { + if (i->first.start <= r.end && i->first.end >= r.start) + return std::make_pair<iterator, iterator>(i,i); + else + // Nothing could match, so return end() + return std::make_pair<iterator, iterator>(tree.end(), tree.end()); + } + i--; + + if (i->first.start <= r.end && i->first.end >= r.start) { + // we have at least one match + j = i; + + i--; + while (i->first.start <= r.end && i->first.end >= + r.start) { + if (i == tree.begin()) + break; + i--; + } + if (i == tree.begin() && i->first.start <= r.end && i->first.end >= + r.start) + return std::make_pair<iterator, iterator>(i,j); + i++; + return std::make_pair<iterator, iterator>(i,j); + + } + + return std::make_pair<iterator, iterator>(tree.end(), tree.end()); + } + + template <class U> + bool intersect(const Range<U> &r) + { + std::pair<iterator,iterator> p; + p = find(r); + if (p.first != tree.end()) + return true; + return false; + } + + + template <class U,class W> + iterator insert(const Range<U> &r, const W d) + { + std::pair<iterator,iterator> p; + p = find(r); + if (p.first->first.start == r.start && p.first->first.end == r.end || + p.first == tree.end()) + return tree.insert(std::make_pair<Range<T>,V>(r, d)); + else + return tree.end(); + } + + size_t erase(T k) + { + return tree.erase(k); + } + + void erase(iterator p) + { + tree.erase(p); + } + + void erase(iterator p, iterator q) + { + tree.erase(p,q); + } + + void clear() + { + tree.erase(tree.begin(), tree.end()); + } + + iterator begin() + { + return tree.begin(); + } + + iterator end() + { + return tree.end(); + } + + size_t size() + { + return tree.size(); + } + + bool empty() + { + return tree.empty(); + } +}; + #endif //__BASE_RANGE_MAP_HH__ |