diff options
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.h')
-rw-r--r-- | Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.h | 110 |
1 files changed, 110 insertions, 0 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.h b/Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.h new file mode 100644 index 00000000000..34be8486fb2 --- /dev/null +++ b/Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.h @@ -0,0 +1,110 @@ +/************************************************************************* +** NumericRanges.h ** +** ** +** This file is part of dvisvgm -- the DVI to SVG converter ** +** Copyright (C) 2005-2015 Martin Gieseking <martin.gieseking@uos.de> ** +** ** +** This program is free software; you can redistribute it and/or ** +** modify it under the terms of the GNU General Public License as ** +** published by the Free Software Foundation; either version 3 of ** +** the License, or (at your option) any later version. ** +** ** +** This program is distributed in the hope that it will be useful, but ** +** WITHOUT ANY WARRANTY; without even the implied warranty of ** +** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** +** GNU General Public License for more details. ** +** ** +** You should have received a copy of the GNU General Public License ** +** along with this program; if not, see <http://www.gnu.org/licenses/>. ** +*************************************************************************/ + +#ifndef DVISVGM_NUMERICRANGES_H +#define DVISVGM_NUMERICRANGES_H + +#include <algorithm> +#include <list> +#include <utility> + +template <class T> +class NumericRanges +{ + public: + typedef std::pair<T,T> Range; + typedef std::list<Range> Container; + typedef typename Container::iterator Iterator; + typedef typename Container::const_iterator ConstIterator; + + public: + void addRange (T value) {addRange(value, value);} + void addRange (T first, T last); + bool valueExists (T value) const; + size_t size () const {return _ranges.size();} + ConstIterator begin () const {return _ranges.begin();} + ConstIterator end () const {return _ranges.end();} + const Container& ranges () const {return _ranges;} + + protected: + static bool isLess (const Range &r1, const Range &r2) {return r1.first < r2.first;} + + private: + Container _ranges; +}; + + +/** Adds a numeric range to the collection. + * @param[in] first left bound of new range + * @param[in] last right bound of new range */ +template <class T> +void NumericRanges<T>::addRange (T first, T last) { + if (first > last) + std::swap(first, last); + typename Container::iterator it = _ranges.begin(); + while (it != _ranges.end() && first > it->first+1 && first > it->second+1) + ++it; + if (it == _ranges.end() || last < it->first-1 || first > it->second+1) + it = _ranges.insert(it, Range(first, last)); + else if ((first < it->first && last >= it->first-1) || (first <= it->second+1 && last > it->second)) { + it->first = std::min(it->first, first); + it->second = std::max(it->second, last); + } + // merge adjacent ranges + if (it != _ranges.end()) { + typename Container::iterator l = it; + typename Container::iterator r = it; + if (l == _ranges.begin()) + l = _ranges.end(); + else + --l; + ++r; + bool l_modified = false; + bool r_modified = false; + if (l != _ranges.end() && l->second >= it->first-1) { + l->first = std::min(l->first, it->first); + l->second = std::max(l->second, it->second); + l_modified = true; + } + if (r != _ranges.end() && r->first <= it->second+1) { + r->first = std::min(r->first, it->first); + r->second = std::max(r->second, it->second); + r_modified = true; + } + if (l_modified || r_modified) { + _ranges.erase(it); + if (l_modified && r_modified && l->second >= r->first-1) { + l->first = std::min(l->first, r->first); + l->second = std::max(l->second, r->second); + _ranges.erase(r); + } + } + } +} + + +template <class T> +bool NumericRanges<T>::valueExists (T value) const { + ConstIterator it = std::lower_bound(_ranges.begin(), _ranges.end(), Range(value, 0), &isLess); + return (it != _ranges.end() && it->first <= value && it->second >= value); +} + + +#endif |