diff options
Diffstat (limited to 'base')
| -rw-r--r-- | base/range.cc | 83 | ||||
| -rw-r--r-- | base/range.hh | 418 |
2 files changed, 346 insertions, 155 deletions
diff --git a/base/range.cc b/base/range.cc new file mode 100644 index 000000000..0a4876e89 --- /dev/null +++ b/base/range.cc @@ -0,0 +1,83 @@ +/* + * Copyright (c) 2003 The Regents of The University of Michigan + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "base/intmath.hh" +#include "base/range.hh" +#include "base/str.hh" + +using namespace std; + +template <class T> +bool +__x_parse_range(const std::string &str, T &start, T &end) +{ + std::vector<std::string> values; + tokenize(values, str, ':'); + + T thestart, theend; + + if (values.size() != 2) + return false; + + std::string s = values[0]; + std::string e = values[1]; + + if (!to_number(s, thestart)) + return false; + + bool increment = (e[0] == '+'); + if (increment) + e = e.substr(1); + + if (!to_number(e, theend)) + return false; + + if (increment) + theend += thestart; + + start = thestart; + end = theend; + + return true; +} + +#define RANGE_PARSE(type) \ +template<> bool \ +__parse_range(const std::string &s, type &start, type &end) \ +{ return __x_parse_range(s, start, end); } + +RANGE_PARSE(unsigned long long); +RANGE_PARSE(signed long long); +RANGE_PARSE(unsigned long); +RANGE_PARSE(signed long); +RANGE_PARSE(unsigned int); +RANGE_PARSE(signed int); +RANGE_PARSE(unsigned short); +RANGE_PARSE(signed short); +RANGE_PARSE(unsigned char); +RANGE_PARSE(signed char); diff --git a/base/range.hh b/base/range.hh index 3443bf246..34bd34136 100644 --- a/base/range.hh +++ b/base/range.hh @@ -29,232 +29,340 @@ #ifndef __RANGE_HH__ #define __RANGE_HH__ -#include <assert.h> +#include <cassert> +#include <string> -#include "base/intmath.hh" -#include "base/str.hh" +template <class T> +bool __parse_range(const std::string &s, T &start, T &end); -template<class T> -class Range +template <class T> +struct Range { private: - bool valid; + /** + * @param s range string + * Ranges are in the following format: + * <range> := {<start_val>}:{<end>} + * <end> := <end_val> | +<delta> + */ + void + parse(const std::string &s) + { + if (!__parse_range(s, start, end)) + invalidate(); + } public: T start; T end; public: - Range() {} + Range() + { + invalidate(); + } + + template <class U> + Range(const Range<U> &r) + : start(r.start), end(r.end) + {} - Range(const Range &r) { operator=(r); } + template <class U> + Range(const std::pair<U, U> &r) + : start(r.first), end(r.second) + {} - Range(const T &s, const T &e) - : start(s), end(e) + Range(const std::string &s) { - valid = (start <= end); + parse(s); } - Range(const std::string &s) { valid = parse(s); } + template <class U> + const Range<T> &operator=(const Range<U> &r) + { + start = r.start; + end = r.end; + return *this; + } - ~Range() {} + template <class U> + const Range<T> &operator=(const std::pair<U, U> &r) + { + start = r.first; + end = r.second; + return *this; + } - int compare(const T &p); - bool parse(const std::string &s); - const Range &operator=(const Range &r); + const Range &operator=(const std::string &s) + { + parse(s); + return *this; + } - bool isValid() const { return valid; } + void invalidate() { start = 0; end = 0; } + bool size() const { return end - start; } + bool valid() const { return start < end; } }; - template<class T> -inline int -Range<T>::compare(const T &p) +inline std::ostream & +operator<<(std::ostream &o, const Range<T> &r) { - assert(isValid()); - - if (p < start) - return -1; - else if (p > end) - return 1; - else - return 0; + // don't currently support output of invalid ranges + assert(r.valid()); + o << r.start << ":" << r.end; + return o; } -// Parse a range string +//////////////////////////////////////////////////////////////////////// // -// Ranges are in the following format: -// <range> := {<start_val>}:{<end>} -// <end> := <end_val> | +<delta> -template<class T> +// Range to Range Comparisons +// + +/** + * @param range1 is a range. + * @param range2 is a range. + * @return if range1 and range2 are identical. + */ +template<class T, class U> inline bool -Range<T>::parse(const std::string &str) +operator==(const Range<T> &range1, const Range<U> &range2) { - std::vector<std::string> values; - tokenize(values, str, ':'); - - T thestart, theend; - - if (values.size() != 2) - return false; - - std::string s = values[0]; - std::string e = values[1]; - - if (!to_number(s, thestart)) - return false; - - bool increment = (e[0] == '+'); - if (increment) - e = e.substr(1); - - if (!to_number(e, theend)) - return false; - - if (increment) - theend += thestart; - - start = thestart; - end = theend; - - if (start > end) - return false; - - return true; + assert(range1.valid() && range2.valid()); + return range1.start == range2.start && range1.end == range2.end; } - -template<class T> -inline const Range<T> & -Range<T>::operator=(const Range<T> &r) +/** + * @param range1 is a range. + * @param range2 is a range. + * @return if range1 and range2 are not identical. + */ +template<class T, class U> +inline bool +operator!=(const Range<T> &range1, const Range<U> &range2) { - if (this != &r) { - start = r.start; - end = r.end; - - valid = r.valid; - } - else { - valid = false; - } + assert(range1.valid() && range2.valid()); + return range1.start != range2.start || range1.end != range2.end; +} - return *this; +/** + * @param range1 is a range. + * @param range2 is a range. + * @return if range1 is less than range2 and does not overlap range1. + */ +template<class T, class U> +inline bool +operator<(const Range<T> &range1, const Range<U> &range2) +{ + assert(range1.valid() && range2.valid()); + return range1.end <= range2.start; } -template<class T> -inline std::ostream & -operator<<(std::ostream &o, const Range<T> &r) +/** + * @param range1 is a range. + * @param range2 is a range. + * @return if range1 is less than range2. range1 may overlap range2, + * but not extend beyond the end of range2. + */ +template<class T, class U> +inline bool +operator<=(const Range<T> &range1, const Range<U> &range2) { - // don't currently support output of invalid ranges - assert(r.isValid()); - o << r.start << ":" << r.end; - return o; + assert(range1.valid() && range2.valid()); + return range1.start <= range2.start && range1.end <= range2.end; } -////////////////////////////////////////// -// -// Compare two ranges -// -template<class T> +/** + * @param range1 is a range. + * @param range2 is a range. + * @return if range1 is greater than range2 and does not overlap range2. + */ +template<class T, class U> inline bool -operator==(const Range<T> &l, const Range<T> &r) +operator>(const Range<T> &range1, const Range<U> &range2) { - // ranges must both be valid to be equal - return (l.isValid() && r.isValid() && - (l.start == r.start) && (l.end == r.end)); + assert(range1.valid() && range2.valid()); + return range1.start >= range2.end; } -template<class T> +/** + * @param range1 is a range. + * @param range2 is a range. + * @return if range1 is greater than range2. range1 may overlap range2, + * but not extend beyond the beginning of range2. + */ +template<class T, class U> inline bool -operator!=(const Range<T> &l, const Range<T> &r) +operator>=(const Range<T> &range1, const Range<U> &range2) { - // for symmetry with ==, an invalid range is not equal to any other - return (!l.isValid() || !r.isValid() || - (l.start != r.start) || (l.end != r.end)); + assert(range1.valid() && range2.valid()); + return range1.start >= range2.start && range1.end >= range2.end; } -////////////////////////////////////////// -// -// Compare position to a range -// -// - 'pos == range' indicates that position pos is within the given range. -// This test always returns false if the range is invalid. -// -// - 'pos < range' and 'pos > range' indicate that the position is -// before the start of or after the end of the range, respectively. -// The range must be valid for these comparisons to be made. -// -// All other comparisons do the obvious thing based on these definitions. +//////////////////////////////////////////////////////////////////////// // +// Position to Range Comparisons // -// -// Basic comparisons -// -template<class T> +/** + * @param pos position compared to the range. + * @param range range compared against. + * @return indicates that position pos is within the range. + */ +template<class T, class U> inline bool -operator==(const T &pos, const Range<T> &range) -{ return range.isValid() && pos >= range.start && pos <= range.end; } +operator==(const T &pos, const Range<U> &range) +{ + assert(range.valid()); + return pos >= range.start && pos < range.end; +} -template<class T> +/** + * @param pos position compared to the range. + * @param range range compared against. + * @return indicates that position pos is not within the range. + */ +template<class T, class U> inline bool -operator<(const T &pos, const Range<T> &range) -{ assert(range.isValid()); return pos < range.start; } +operator!=(const T &pos, const Range<U> &range) +{ + assert(range.valid()); + return pos < range.start || pos >= range.end; +} -template<class T> +/** + * @param pos position compared to the range. + * @param range range compared against. + * @return indicates that position pos is below the range. + */ +template<class T, class U> inline bool -operator>(const T &pos, const Range<T> &range) -{ assert(range.isValid()); return pos > range.end; } +operator<(const T &pos, const Range<U> &range) +{ + assert(range.valid()); + return pos < range.start; +} -// -// Derived comparisons -// -template<class T> +/** + * @param pos position compared to the range. + * @param range range compared against. + * @return indicates that position pos is below or in the range. + */ +template<class T, class U> inline bool -operator<=(const T &pos, const Range<T> &range) -{ assert(range.isValid()); return pos <= range.end; } +operator<=(const T &pos, const Range<U> &range) +{ + assert(range.valid()); + return pos < range.end; +} -template<class T> +/** + * @param pos position compared to the range. + * @param range range compared against. + * @return indicates that position pos is above the range. + */ +template<class T, class U> inline bool -operator>=(const T &pos, const Range<T> &range) -{ assert(range.isValid()); return pos >= range.start; } +operator>(const T &pos, const Range<U> &range) +{ + assert(range.valid()); + return pos >= range.end; +} -template<class T> +/** + * @param pos position compared to the range. + * @param range range compared against. + * @return indicates that position pos is above or in the range. + */ +template<class T, class U> inline bool -operator!=(const T &pos, const Range<T> &range) -{ return !(pos == range); } +operator>=(const T &pos, const Range<U> &range) +{ + assert(range.valid()); + return pos >= range.start; +} +//////////////////////////////////////////////////////////////////////// // -// Define symmetric comparisons based on above +// Range to Position Comparisons (for symmetry) // -template<class T> + +/** + * @param range range compared against. + * @param pos position compared to the range. + * @return indicates that position pos is within the range. + */ +template<class T, class U> inline bool -operator>(const Range<T> &range, const T &pos) -{ return pos < range; } +operator==(const Range<T> &range, const U &pos) +{ + assert(range.valid()); + return pos >= range.start && pos < range.end; +} -template<class T> +/** + * @param range range compared against. + * @param pos position compared to the range. + * @return indicates that position pos is not within the range. + */ +template<class T, class U> inline bool -operator<(const Range<T> &range, const T &pos) -{ return pos > range; } +operator!=(const Range<T> &range, const U &pos) +{ + assert(range.valid()); + return pos < range.start || pos >= range.end; +} -template<class T> +/** + * @param range range compared against. + * @param pos position compared to the range. + * @return indicates that position pos is above the range. + */ +template<class T, class U> inline bool -operator<=(const Range<T> &range, const T &pos) -{ return pos >= range; } +operator<(const Range<T> &range, const U &pos) +{ + assert(range.valid()); + return range.end <= pos; +} -template<class T> +/** + * @param range range compared against. + * @param pos position compared to the range. + * @return indicates that position pos is above or in the range. + */ +template<class T, class U> inline bool -operator>=(const Range<T> &range, const T &pos) -{ return pos <= range; } +operator<=(const Range<T> &range, const U &pos) +{ + assert(range.valid()); + return range.start <= pos; +} -template<class T> +/** + * @param range range compared against. + * @param pos position compared to the range. + * 'range > pos' indicates that position pos is below the range. + */ +template<class T, class U> inline bool -operator==(const Range<T> &range, const T &pos) -{ return (pos == range); } +operator>(const Range<T> &range, const U &pos) +{ + assert(range.valid()); + return range.start > pos; +} -template<class T> +/** + * @param range range compared against. + * @param pos position compared to the range. + * 'range >= pos' indicates that position pos is below or in the range. + */ +template<class T, class U> inline bool -operator!=(const Range<T> &range, const T &pos) -{ return (pos != range); } +operator>=(const Range<T> &range, const U &pos) +{ + assert(range.valid()); + return range.end > pos; +} #endif // __RANGE_HH__ |