1 files changed, 109 insertions, 0 deletions
diff --git a/dviware/dvisvgm/src/NumericRanges.hpp b/dviware/dvisvgm/src/NumericRanges.hpp
new file mode 100644
index 0000000000..c51f1eba73
--- /dev/null
+++ b/dviware/dvisvgm/src/NumericRanges.hpp
@@ -0,0 +1,109 @@
+/*************************************************************************
+** NumericRanges.hpp                                                    **
+**                                                                      **
+** This file is part of dvisvgm -- a fast DVI to SVG converter          **
+** Copyright (C) 2005-2019 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:
+		using Range = std::pair<T,T>;
+		using Container = std::list<Range>;
+		using ConstIterator = typename Container::const_iterator;
+
+	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 {
+	auto 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