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
  50     find(const Range<U> &r)
  51     {
  52         iterator i;
  53
  54         i = tree.upper_bound(r);
  55
  56         if (i == tree.begin()) {
  57             if (i->first.start <= r.end && i->first.end >= r.start)
  58                 return i;
  59             else
  60                 // Nothing could match, so return end()
  61                 return tree.end();
  62         }
  63
  64         i--;
  65
  66         if (i->first.start <= r.end && i->first.end >= r.start)
  67             return i;
  68
  69         return tree.end();
  70     }
  71
  72     template <class U>
  73     const iterator
  74     find(const U &r)
  75     {
  76         return find(RangeSize(r, 1));
  77     }
  78
  79     template <class U>
  80     bool
  81     intersect(const Range<U> &r)
  82     {
  83         iterator i;
  84         i = find(r);
  85         if (i != tree.end())
  86             return true;
  87         return false;
  88     }
  89
  90
  91     template <class U,class W>
  92     iterator
  93     insert(const Range<U> &r, const W d)
  94     {
  95         if (intersect(r))
  96             return tree.end();
  97
  98         return tree.insert(std::make_pair<Range<T>,V>(r, d)).first;
  99     }
 100
 101     size_t
 102     erase(T k)
 103     {
 104         return tree.erase(k);
 105     }
 106
 107     void
 108     erase(iterator p)
 109     {
 110         tree.erase(p);
 111     }
 112
 113     void
 114     erase(iterator p, iterator q)
 115     {
 116         tree.erase(p,q);
 117     }
 118
 119     void
 120     clear()
 121     {
 122         tree.erase(tree.begin(), tree.end());
 123     }
 124
 125     iterator
 126     begin()
 127     {
 128         return tree.begin();
 129     }
 130
 131     iterator
 132     end()
 133     {
 134         return tree.end();
 135     }
 136
 137     size_t
 138     size()
 139     {
 140         return tree.size();
 141     }
 142
 143     bool
 144     empty()
 145     {
 146         return tree.empty();
 147     }
 148 };
 149
 150
 151 template <class T,class V>
 152 class range_multimap
 153 {
 154   private:
 155     typedef std::multimap<Range<T>,V> RangeMap;
 156     RangeMap tree;
 157
 158   public:
 159     typedef typename RangeMap::iterator iterator;
 160
 161     template <class U>
 162     std::pair<iterator,iterator> find(const Range<U> &r)
 163     {
 164         iterator i;
 165         iterator j;
 166
 167         i = tree.lower_bound(r);
 168
 169         if (i == tree.begin()) {
 170           if (i->first.start <= r.end && i->first.end >= r.start)
 171                 return std::make_pair<iterator, iterator>(i,i);
 172           else
 173             // Nothing could match, so return end()
 174             return std::make_pair<iterator, iterator>(tree.end(), tree.end());
 175         }
 176         i--;
 177
 178         if (i->first.start <= r.end && i->first.end >= r.start) {
 179             // we have at least one match
 180             j = i;
 181
 182             i--;
 183             while (i->first.start <= r.end && i->first.end >=
 184                     r.start) {
 185                 if (i == tree.begin())
 186                     break;
 187                 i--;
 188             }
 189             if (i == tree.begin() && i->first.start <= r.end && i->first.end >=
 190                                         r.start)
 191                 return std::make_pair<iterator, iterator>(i,j);
 192             i++;
 193             return std::make_pair<iterator, iterator>(i,j);
 194
 195         }
 196
 197         return std::make_pair<iterator, iterator>(tree.end(), tree.end());
 198     }
 199
 200     template <class U>
 201     bool
 202     intersect(const Range<U> &r)
 203     {
 204         std::pair<iterator,iterator> p;
 205         p = find(r);
 206         if (p.first != tree.end())
 207             return true;
 208         return false;
 209     }
 210
 211
 212     template <class U,class W>
 213     iterator
 214     insert(const Range<U> &r, const W d)
 215     {
 216         std::pair<iterator,iterator> p;
 217         p = find(r);
 218         if (p.first->first.start == r.start && p.first->first.end == r.end ||
 219                 p.first == tree.end())
 220             return tree.insert(std::make_pair<Range<T>,V>(r, d));
 221         else
 222             return tree.end();
 223     }
 224
 225     size_t
 226     erase(T k)
 227     {
 228         return tree.erase(k);
 229     }
 230
 231     void
 232     erase(iterator p)
 233     {
 234         tree.erase(p);
 235     }
 236
 237     void
 238     erase(iterator p, iterator q)
 239     {
 240         tree.erase(p,q);
 241     }
 242
 243     void
 244     clear()
 245     {
 246         tree.erase(tree.begin(), tree.end());
 247     }
 248
 249     iterator
 250     begin()
 251     {
 252         return tree.begin();
 253     }
 254
 255     iterator
 256     end()
 257     {
 258         return tree.end();
 259     }
 260
 261     size_t
 262     size()
 263     {
 264         return tree.size();
 265     }
 266
 267     bool
 268     empty()
 269     {
 270         return tree.empty();
 271     }
 272 };
 273
 274 #endif //__BASE_RANGE_MAP_HH__