base/range.hh

   1 /*
   2  * Copyright (c) 2002-2004 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
  29 #ifndef __BASE_RANGE_HH__
  30 #define __BASE_RANGE_HH__
  31
  32 #include <cassert>
  33 #include <string>
  34
  35 /**
  36  * @param s range string
  37  * EndExclusive Ranges are in the following format:
  38  *    <range> := {<start_val>}:{<end>}
  39  *    <start>   := <end_val> | +<delta>
  40  */
  41 template <class T>
  42 bool __parse_range(const std::string &s, T &start, T &end);
  43
  44 template <class T>
  45 struct Range
  46 {
  47     T start;
  48     T end;
  49
  50     Range() { invalidate(); }
  51
  52     template <class U>
  53     Range(const std::pair<U, U> &r)
  54         : start(r.first), end(r.second)
  55     {}
  56
  57     template <class U>
  58     Range(const Range<U> &r)
  59         : start(r.start), end(r.end)
  60     {}
  61
  62     Range(const std::string &s)
  63     {
  64         if (!__parse_range(s, start, end))
  65             invalidate();
  66     }
  67
  68     template <class U>
  69     const Range<T> &operator=(const Range<U> &r)
  70     {
  71         start = r.start;
  72         end = r.end;
  73         return *this;
  74     }
  75
  76     template <class U>
  77     const Range<T> &operator=(const std::pair<U, U> &r)
  78     {
  79         start = r.first;
  80         end = r.second;
  81         return *this;
  82     }
  83
  84     const Range &operator=(const std::string &s)
  85     {
  86         if (!__parse_range(s, start, end))
  87             invalidate();
  88         return *this;
  89     }
  90
  91     void invalidate() { start = 1; end = 0; }
  92     T size() const { return end - start + 1; }
  93     bool valid() const { return start < end; }
  94 };
  95
  96 template <class T>
  97 inline std::ostream &
  98 operator<<(std::ostream &o, const Range<T> &r)
  99 {
 100     o << '[' << r.start << "," << r.end << ']';
 101     return o;
 102 }
 103
 104 template <class T>
 105 inline Range<T>
 106 RangeEx(T start, T end)
 107 { return std::make_pair(start, end - 1); }
 108
 109 template <class T>
 110 inline Range<T>
 111 RangeIn(T start, T end)
 112 { return std::make_pair(start, end); }
 113
 114 template <class T, class U>
 115 inline Range<T>
 116 RangeSize(T start, U size)
 117 { return std::make_pair(start, start + size - 1); }
 118
 119 ////////////////////////////////////////////////////////////////////////
 120 //
 121 // Range to Range Comparisons
 122 //
 123
 124 /**
 125  * @param range1 is a range.
 126  * @param range2 is a range.
 127  * @return if range1 and range2 are identical.
 128  */
 129 template <class T, class U>
 130 inline bool
 131 operator==(const Range<T> &range1, const Range<U> &range2)
 132 {
 133     return range1.start == range2.start && range1.end == range2.end;
 134 }
 135
 136 /**
 137  * @param range1 is a range.
 138  * @param range2 is a range.
 139  * @return if range1 and range2 are not identical.
 140  */
 141 template <class T, class U>
 142 inline bool
 143 operator!=(const Range<T> &range1, const Range<U> &range2)
 144 {
 145     return range1.start != range2.start || range1.end != range2.end;
 146 }
 147
 148 /**
 149  * @param range1 is a range.
 150  * @param range2 is a range.
 151  * @return if range1 is less than range2 and does not overlap range1.
 152  */
 153 template <class T, class U>
 154 inline bool
 155 operator<(const Range<T> &range1, const Range<U> &range2)
 156 {
 157     return range1.start < range2.start;
 158 }
 159
 160 /**
 161  * @param range1 is a range.
 162  * @param range2 is a range.
 163  * @return if range1 is less than range2.  range1 may overlap range2,
 164  * but not extend beyond the end of range2.
 165  */
 166 template <class T, class U>
 167 inline bool
 168 operator<=(const Range<T> &range1, const Range<U> &range2)
 169 {
 170     return range1.start <= range2.start;
 171 }
 172
 173 /**
 174  * @param range1 is a range.
 175  * @param range2 is a range.
 176  * @return if range1 is greater than range2 and does not overlap range2.
 177  */
 178 template <class T, class U>
 179 inline bool
 180 operator>(const Range<T> &range1, const Range<U> &range2)
 181 {
 182     return range1.start > range2.start;
 183 }
 184
 185 /**
 186  * @param range1 is a range.
 187  * @param range2 is a range.
 188  * @return if range1 is greater than range2.  range1 may overlap range2,
 189  * but not extend beyond the beginning of range2.
 190  */
 191 template <class T, class U>
 192 inline bool
 193 operator>=(const Range<T> &range1, const Range<U> &range2)
 194 {
 195     return range1.start >= range2.start;
 196 }
 197
 198 ////////////////////////////////////////////////////////////////////////
 199 //
 200 // Position to Range Comparisons
 201 //
 202
 203 /**
 204  * @param pos position compared to the range.
 205  * @param range range compared against.
 206  * @return indicates that position pos is within the range.
 207  */
 208 template <class T, class U>
 209 inline bool
 210 operator==(const T &pos, const Range<U> &range)
 211 {
 212     return pos >= range.start && pos <= range.end;
 213 }
 214
 215 /**
 216  * @param pos position compared to the range.
 217  * @param range range compared against.
 218  * @return indicates that position pos is not within the range.
 219  */
 220 template <class T, class U>
 221 inline bool
 222 operator!=(const T &pos, const Range<U> &range)
 223 {
 224     return pos < range.start || pos > range.end;
 225 }
 226
 227 /**
 228  * @param pos position compared to the range.
 229  * @param range range compared against.
 230  * @return indicates that position pos is below the range.
 231  */
 232 template <class T, class U>
 233 inline bool
 234 operator<(const T &pos, const Range<U> &range)
 235 {
 236     return pos < range.start;
 237 }
 238
 239 /**
 240  * @param pos position compared to the range.
 241  * @param range range compared against.
 242  * @return indicates that position pos is below or in the range.
 243  */
 244 template <class T, class U>
 245 inline bool
 246 operator<=(const T &pos, const Range<U> &range)
 247 {
 248     return pos <= range.end;
 249 }
 250
 251 /**
 252  * @param pos position compared to the range.
 253  * @param range range compared against.
 254  * @return indicates that position pos is above the range.
 255  */
 256 template <class T, class U>
 257 inline bool
 258 operator>(const T &pos, const Range<U> &range)
 259 {
 260     return pos > range.end;
 261 }
 262
 263 /**
 264  * @param pos position compared to the range.
 265  * @param range range compared against.
 266  * @return indicates that position pos is above or in the range.
 267  */
 268 template <class T, class U>
 269 inline bool
 270 operator>=(const T &pos, const Range<U> &range)
 271 {
 272     return pos >= range.start;
 273 }
 274
 275 ////////////////////////////////////////////////////////////////////////
 276 //
 277 // Range to Position Comparisons (for symmetry)
 278 //
 279
 280 /**
 281  * @param range range compared against.
 282  * @param pos position compared to the range.
 283  * @return indicates that position pos is within the range.
 284  */
 285 template <class T, class U>
 286 inline bool
 287 operator==(const Range<T> &range, const U &pos)
 288 {
 289     return pos >= range.start && pos <= range.end;
 290 }
 291
 292 /**
 293  * @param range range compared against.
 294  * @param pos position compared to the range.
 295  * @return indicates that position pos is not within the range.
 296  */
 297 template <class T, class U>
 298 inline bool
 299 operator!=(const Range<T> &range, const U &pos)
 300 {
 301     return pos < range.start || pos > range.end;
 302 }
 303
 304 /**
 305  * @param range range compared against.
 306  * @param pos position compared to the range.
 307  * @return indicates that position pos is above the range.
 308  */
 309 template <class T, class U>
 310 inline bool
 311 operator<(const Range<T> &range, const U &pos)
 312 {
 313     return range.end < pos;
 314 }
 315
 316 /**
 317  * @param range range compared against.
 318  * @param pos position compared to the range.
 319  * @return indicates that position pos is above or in the range.
 320  */
 321 template <class T, class U>
 322 inline bool
 323 operator<=(const Range<T> &range, const U &pos)
 324 {
 325     return range.start <= pos;
 326 }
 327
 328 /**
 329  * @param range range compared against.
 330  * @param pos position compared to the range.
 331  * 'range > pos' indicates that position pos is below the range.
 332  */
 333 template <class T, class U>
 334 inline bool
 335 operator>(const Range<T> &range, const U &pos)
 336 {
 337     return range.start > pos;
 338 }
 339
 340 /**
 341  * @param range range compared against.
 342  * @param pos position compared to the range.
 343  * 'range >= pos' indicates that position pos is below or in the range.
 344  */
 345 template <class T, class U>
 346 inline bool
 347 operator>=(const Range<T> &range, const U &pos)
 348 {
 349     return range.end >= pos;
 350 }
 351
 352 #endif // __BASE_RANGE_HH__