summaryrefslogtreecommitdiff
path: root/Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.hpp')
-rw-r--r--Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.hpp109
1 files changed, 109 insertions, 0 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.hpp b/Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.hpp
new file mode 100644
index 00000000000..c87eddf054f
--- /dev/null
+++ b/Build/source/texk/dvisvgm/dvisvgm-src/src/NumericRanges.hpp
@@ -0,0 +1,109 @@
+/*************************************************************************
+** NumericRanges.hpp **
+** **
+** This file is part of dvisvgm -- a fast DVI to SVG converter **
+** Copyright (C) 2005-2017 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 NUMERICRANGES_HPP
+#define NUMERICRANGES_HPP
+
+#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::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;}
+
+ 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),
+ [](const Range &r1, const Range &r2) {
+ return r1.first < r2.first;
+ });
+ return (it != _ranges.end() && it->first <= value && it->second >= value);
+}
+
+
+#endif