src/base/range_map.hh

   1 /*
   2  * Copyright (c) 2006 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Ali Saidi
  29  */
  30
  31 #ifndef __BASE_RANGE_MAP_HH__
  32 #define __BASE_RANGE_MAP_HH__
  33
  34 #include "base/range.hh"
  35
  36 #include <map>
  37
  38 template <class T,class V>
  39 class range_map
  40 {
  41   private:
  42     typedef std::map<Range<T>,V> RangeMap;
  43     RangeMap tree;
  44
  45   public:
  46     typedef typename RangeMap::iterator iterator;
  47
  48     template <class U>
  49     const iterator find(const Range<U> &r)
  50     {
  51         iterator i;
  52
  53         i = tree.upper_bound(r);
  54
  55         if (i == tree.begin()) {
  56             if (i->first.start <= r.end && i->first.end >= r.start)
  57                 return i;
  58             else
  59                 // Nothing could match, so return end()
  60                 return tree.end();
  61         }
  62
  63         i--;
  64
  65         if (i->first.start <= r.end && i->first.end >= r.start)
  66             return i;
  67
  68         return tree.end();
  69     }
  70
  71     template <class U>
  72     bool intersect(const Range<U> &r)
  73     {
  74         iterator i;
  75         i = find(r);
  76         if (i != tree.end())
  77             return true;
  78         return false;
  79     }
  80
  81
  82     template <class U,class W>
  83     iterator insert(const Range<U> &r, const W d)
  84     {
  85         if (intersect(r))
  86             return tree.end();
  87
  88         return tree.insert(std::make_pair<Range<T>,V>(r, d)).first;
  89     }
  90
  91     size_t erase(T k)
  92     {
  93         return tree.erase(k);
  94     }
  95
  96     void erase(iterator p)
  97     {
  98         tree.erase(p);
  99     }
 100
 101     void erase(iterator p, iterator q)
 102     {
 103         tree.erase(p,q);
 104     }
 105
 106     void clear()
 107     {
 108         tree.erase(tree.begin(), tree.end());
 109     }
 110
 111     iterator begin()
 112     {
 113         return tree.begin();
 114     }
 115
 116     iterator end()
 117     {
 118         return tree.end();
 119     }
 120
 121     size_t size()
 122     {
 123         return tree.size();
 124     }
 125
 126     bool empty()
 127     {
 128         return tree.empty();
 129     }
 130 };
 131
 132
 133 template <class T,class V>
 134 class range_multimap
 135 {
 136   private:
 137     typedef std::multimap<Range<T>,V> RangeMap;
 138     RangeMap tree;
 139
 140   public:
 141     typedef typename RangeMap::iterator iterator;
 142
 143     template <class U>
 144     std::pair<iterator,iterator> find(const Range<U> &r)
 145     {
 146         iterator i;
 147         iterator j;
 148
 149         i = tree.lower_bound(r);
 150
 151         if (i == tree.begin()) {
 152           if (i->first.start <= r.end && i->first.end >= r.start)
 153                 return std::make_pair<iterator, iterator>(i,i);
 154           else
 155             // Nothing could match, so return end()
 156             return std::make_pair<iterator, iterator>(tree.end(), tree.end());
 157         }
 158         i--;
 159
 160         if (i->first.start <= r.end && i->first.end >= r.start) {
 161             // we have at least one match
 162             j = i;
 163
 164             i--;
 165             while (i->first.start <= r.end && i->first.end >=
 166                     r.start) {
 167                 if (i == tree.begin())
 168                     break;
 169                 i--;
 170             }
 171             if (i == tree.begin() && i->first.start <= r.end && i->first.end >=
 172                                         r.start)
 173                 return std::make_pair<iterator, iterator>(i,j);
 174             i++;
 175             return std::make_pair<iterator, iterator>(i,j);
 176
 177         }
 178
 179         return std::make_pair<iterator, iterator>(tree.end(), tree.end());
 180     }
 181
 182     template <class U>
 183     bool intersect(const Range<U> &r)
 184     {
 185         std::pair<iterator,iterator> p;
 186         p = find(r);
 187         if (p.first != tree.end())
 188             return true;
 189         return false;
 190     }
 191
 192
 193     template <class U,class W>
 194     iterator insert(const Range<U> &r, const W d)
 195     {
 196         std::pair<iterator,iterator> p;
 197         p = find(r);
 198         if (p.first->first.start == r.start && p.first->first.end == r.end ||
 199                 p.first == tree.end())
 200             return tree.insert(std::make_pair<Range<T>,V>(r, d));
 201         else
 202             return tree.end();
 203     }
 204
 205     size_t erase(T k)
 206     {
 207         return tree.erase(k);
 208     }
 209
 210     void erase(iterator p)
 211     {
 212         tree.erase(p);
 213     }
 214
 215     void erase(iterator p, iterator q)
 216     {
 217         tree.erase(p,q);
 218     }
 219
 220     void clear()
 221     {
 222         tree.erase(tree.begin(), tree.end());
 223     }
 224
 225     iterator begin()
 226     {
 227         return tree.begin();
 228     }
 229
 230     iterator end()
 231     {
 232         return tree.end();
 233     }
 234
 235     size_t size()
 236     {
 237         return tree.size();
 238     }
 239
 240     bool empty()
 241     {
 242         return tree.empty();
 243     }
 244 };
 245
 246 #endif //__BASE_RANGE_MAP_HH__