base/range.hh

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