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