summaryrefslogtreecommitdiffstats
path: root/include/mapbox
diff options
context:
space:
mode:
authorwanglu <wang_lu@dl.cn.nexty-ele.com>2019-03-25 09:42:49 +0800
committerwanglu <wang_lu@dl.cn.nexty-ele.com>2019-03-25 09:52:02 +0800
commit4a8b7a6301e4b093c99329d0a16fbee6c535f312 (patch)
treefe9f589e1723e8f173b50dfa617374042f4cf7a7 /include/mapbox
parentfb539bbd9f7b36d26cd56fe09b804e18b3b3d984 (diff)
Change-Id: I0866a7d9ffa347c0935b4d00259ad1a74cd00d6e Signed-off-by: wanglu <wang_lu@dl.cn.nexty-ele.com>
Diffstat (limited to 'include/mapbox')
-rw-r--r--include/mapbox/cheap_ruler.hpp358
-rw-r--r--include/mapbox/geometry.hpp13
-rw-r--r--include/mapbox/geometry/box.hpp34
-rw-r--r--include/mapbox/geometry/envelope.hpp33
-rw-r--r--include/mapbox/geometry/feature.hpp81
-rw-r--r--include/mapbox/geometry/for_each_point.hpp45
-rw-r--r--include/mapbox/geometry/geometry.hpp53
-rw-r--r--include/mapbox/geometry/line_string.hpp21
-rw-r--r--include/mapbox/geometry/multi_line_string.hpp21
-rw-r--r--include/mapbox/geometry/multi_point.hpp21
-rw-r--r--include/mapbox/geometry/multi_polygon.hpp21
-rw-r--r--include/mapbox/geometry/point.hpp35
-rw-r--r--include/mapbox/geometry/point_arithmetic.hpp119
-rw-r--r--include/mapbox/geometry/polygon.hpp31
-rw-r--r--include/mapbox/optional.hpp74
-rw-r--r--include/mapbox/recursive_wrapper.hpp122
-rw-r--r--include/mapbox/variant.hpp1013
-rw-r--r--include/mapbox/variant_io.hpp45
-rw-r--r--include/mapbox/variant_visitor.hpp38
19 files changed, 2178 insertions, 0 deletions
diff --git a/include/mapbox/cheap_ruler.hpp b/include/mapbox/cheap_ruler.hpp
new file mode 100644
index 0000000..ae82706
--- /dev/null
+++ b/include/mapbox/cheap_ruler.hpp
@@ -0,0 +1,358 @@
+#pragma once
+
+#include <mapbox/geometry.hpp>
+
+#include <cmath>
+#include <cstdint>
+#include <limits>
+#include <tuple>
+#include <utility>
+
+namespace mapbox {
+namespace cheap_ruler {
+
+using box = geometry::box<double>;
+using line_string = geometry::line_string<double>;
+using linear_ring = geometry::linear_ring<double>;
+using multi_line_string = geometry::multi_line_string<double>;
+using point = geometry::point<double>;
+using polygon = geometry::polygon<double>;
+
+class CheapRuler {
+public:
+ enum Unit {
+ Kilometers,
+ Miles,
+ NauticalMiles,
+ Meters,
+ Metres = Meters,
+ Yards,
+ Feet,
+ Inches
+ };
+
+ //
+ // A collection of very fast approximations to common geodesic measurements. Useful
+ // for performance-sensitive code that measures things on a city scale. Point coordinates
+ // are in the [x = longitude, y = latitude] form.
+ //
+ explicit CheapRuler(double latitude, Unit unit = Kilometers) {
+ double m = 0.;
+
+ switch (unit) {
+ case Kilometers:
+ m = 1.;
+ break;
+ case Miles:
+ m = 1000. / 1609.344;
+ break;
+ case NauticalMiles:
+ m = 1000. / 1852.;
+ break;
+ case Meters:
+ m = 1000.;
+ break;
+ case Yards:
+ m = 1000. / 0.9144;
+ break;
+ case Feet:
+ m = 1000. / 0.3048;
+ break;
+ case Inches:
+ m = 1000. / 0.0254;
+ break;
+ }
+
+ auto cos = std::cos(latitude * M_PI / 180.);
+ auto cos2 = 2. * cos * cos - 1.;
+ auto cos3 = 2. * cos * cos2 - cos;
+ auto cos4 = 2. * cos * cos3 - cos2;
+ auto cos5 = 2. * cos * cos4 - cos3;
+
+ // multipliers for converting longitude and latitude
+ // degrees into distance (http://1.usa.gov/1Wb1bv7)
+ kx = m * (111.41513 * cos - 0.09455 * cos3 + 0.00012 * cos5);
+ ky = m * (111.13209 - 0.56605 * cos2 + 0.0012 * cos4);
+ }
+
+ static CheapRuler fromTile(uint32_t y, uint32_t z) {
+ double n = M_PI * (1. - 2. * (y + 0.5) / std::pow(2., z));
+ double latitude = std::atan(0.5 * (std::exp(n) - std::exp(-n))) * 180. / M_PI;
+
+ return CheapRuler(latitude);
+ }
+
+ //
+ // Given two points of the form [x = longitude, y = latitude], returns the distance.
+ //
+ double distance(point a, point b) {
+ auto dx = (a.x - b.x) * kx;
+ auto dy = (a.y - b.y) * ky;
+
+ return std::sqrt(dx * dx + dy * dy);
+ }
+
+ //
+ // Returns the bearing between two points in angles.
+ //
+ double bearing(point a, point b) {
+ auto dx = (b.x - a.x) * kx;
+ auto dy = (b.y - a.y) * ky;
+
+ if (!dx && !dy) {
+ return 0.;
+ }
+
+ auto bearing = std::atan2(-dy, dx) * 180. / M_PI + 90.;
+
+ if (bearing > 180.) {
+ bearing -= 360.;
+ }
+
+ return bearing;
+ }
+
+ //
+ // Returns a new point given distance and bearing from the starting point.
+ //
+ point destination(point origin, double dist, double bearing) {
+ auto a = (90. - bearing) * M_PI / 180.;
+
+ return offset(origin, std::cos(a) * dist, std::sin(a) * dist);
+ }
+
+ //
+ // Returns a new point given easting and northing offsets from the starting point.
+ //
+ point offset(point origin, double dx, double dy) {
+ return point(origin.x + dx / kx, origin.y + dy / ky);
+ }
+
+ //
+ // Given a line (an array of points), returns the total line distance.
+ //
+ double lineDistance(const line_string& points) {
+ double total = 0.;
+
+ for (unsigned i = 0; i < points.size() - 1; ++i) {
+ total += distance(points[i], points[i + 1]);
+ }
+
+ return total;
+ }
+
+ //
+ // Given a polygon (an array of rings, where each ring is an array of points),
+ // returns the area.
+ //
+ double area(polygon poly) {
+ double sum = 0.;
+
+ for (unsigned i = 0; i < poly.size(); ++i) {
+ auto& ring = poly[i];
+
+ for (unsigned j = 0, len = ring.size(), k = len - 1; j < len; k = j++) {
+ sum += (ring[j].x - ring[k].x) * (ring[j].y + ring[k].y) * (i ? -1. : 1.);
+ }
+ }
+
+ return (std::abs(sum) / 2.) * kx * ky;
+ }
+
+ //
+ // Returns the point at a specified distance along the line.
+ //
+ point along(const line_string& line, double dist) {
+ double sum = 0.;
+
+ if (dist <= 0.) {
+ return line[0];
+ }
+
+ for (unsigned i = 0; i < line.size() - 1; ++i) {
+ auto p0 = line[i];
+ auto p1 = line[i + 1];
+ auto d = distance(p0, p1);
+
+ sum += d;
+
+ if (sum > dist) {
+ return interpolate(p0, p1, (dist - (sum - d)) / d);
+ }
+ }
+
+ return line[line.size() - 1];
+ }
+
+ //
+ // Returns a pair of the form <point, index> where point is closest point on the line from
+ // the given point and index is the start index of the segment with the closest point.
+ //
+ std::pair<point, unsigned> pointOnLine(const line_string& line, point p) {
+ auto result = _pointOnLine(line, p);
+
+ return std::make_pair(std::get<0>(result), std::get<1>(result));
+ }
+
+ //
+ // Returns a part of the given line between the start and the stop points (or their closest
+ // points on the line).
+ //
+ line_string lineSlice(point start, point stop, const line_string& line) {
+ constexpr auto getPoint = [](auto tuple) { return std::get<0>(tuple); };
+ constexpr auto getIndex = [](auto tuple) { return std::get<1>(tuple); };
+ constexpr auto getT = [](auto tuple) { return std::get<2>(tuple); };
+
+ auto p1 = _pointOnLine(line, start);
+ auto p2 = _pointOnLine(line, stop);
+
+ if (getIndex(p1) > getIndex(p2) || (getIndex(p1) == getIndex(p2) && getT(p1) > getT(p2))) {
+ auto tmp = p1;
+ p1 = p2;
+ p2 = tmp;
+ }
+
+ line_string slice = { getPoint(p1) };
+
+ auto l = getIndex(p1) + 1;
+ auto r = getIndex(p2);
+
+ if (line[l] != slice[0] && l <= r) {
+ slice.push_back(line[l]);
+ }
+
+ for (unsigned i = l + 1; i <= r; ++i) {
+ slice.push_back(line[i]);
+ }
+
+ if (line[r] != getPoint(p2)) {
+ slice.push_back(getPoint(p2));
+ }
+
+ return slice;
+ };
+
+ //
+ // Returns a part of the given line between the start and the stop points
+ // indicated by distance along the line.
+ //
+ line_string lineSliceAlong(double start, double stop, const line_string& line) {
+ double sum = 0.;
+ line_string slice;
+
+ for (unsigned i = 0; i < line.size() - 1; ++i) {
+ auto p0 = line[i];
+ auto p1 = line[i + 1];
+ auto d = distance(p0, p1);
+
+ sum += d;
+
+ if (sum > start && slice.size() == 0) {
+ slice.push_back(interpolate(p0, p1, (start - (sum - d)) / d));
+ }
+
+ if (sum >= stop) {
+ slice.push_back(interpolate(p0, p1, (stop - (sum - d)) / d));
+ return slice;
+ }
+
+ if (sum > start) {
+ slice.push_back(p1);
+ }
+ }
+
+ return slice;
+ };
+
+ //
+ // Given a point, returns a bounding box object ([w, s, e, n])
+ // created from the given point buffered by a given distance.
+ //
+ box bufferPoint(point p, double buffer) {
+ auto v = buffer / ky;
+ auto h = buffer / kx;
+
+ return box(
+ point(p.x - h, p.y - v),
+ point(p.x + h, p.y + v)
+ );
+ }
+
+ //
+ // Given a bounding box, returns the box buffered by a given distance.
+ //
+ box bufferBBox(box bbox, double buffer) {
+ auto v = buffer / ky;
+ auto h = buffer / kx;
+
+ return box(
+ point(bbox.min.x - h, bbox.min.y - v),
+ point(bbox.max.x + h, bbox.max.y + v)
+ );
+ }
+
+ //
+ // Returns true if the given point is inside in the given bounding box, otherwise false.
+ //
+ bool insideBBox(point p, box bbox) {
+ return p.x >= bbox.min.x &&
+ p.x <= bbox.max.x &&
+ p.y >= bbox.min.y &&
+ p.y <= bbox.max.y;
+ }
+
+ static point interpolate(point a, point b, double t) {
+ double dx = b.x - a.x;
+ double dy = b.y - a.y;
+
+ return point(a.x + dx * t, a.y + dy * t);
+ }
+
+private:
+ std::tuple<point, unsigned, double> _pointOnLine(const line_string& line, point p) {
+ double minDist = std::numeric_limits<double>::infinity();
+ double minX = 0., minY = 0., minI = 0., minT = 0.;
+
+ for (unsigned i = 0; i < line.size() - 1; ++i) {
+ auto t = 0.;
+ auto x = line[i].x;
+ auto y = line[i].y;
+ auto dx = (line[i + 1].x - x) * kx;
+ auto dy = (line[i + 1].y - y) * ky;
+
+ if (dx != 0. || dy != 0.) {
+ t = ((p.x - x) * kx * dx + (p.y - y) * ky * dy) / (dx * dx + dy * dy);
+
+ if (t > 1) {
+ x = line[i + 1].x;
+ y = line[i + 1].y;
+
+ } else if (t > 0) {
+ x += (dx / kx) * t;
+ y += (dy / ky) * t;
+ }
+ }
+
+ dx = (p.x - x) * kx;
+ dy = (p.y - y) * ky;
+
+ auto sqDist = dx * dx + dy * dy;
+
+ if (sqDist < minDist) {
+ minDist = sqDist;
+ minX = x;
+ minY = y;
+ minI = i;
+ minT = t;
+ }
+ }
+
+ return std::make_tuple(point(minX, minY), minI, minT);
+ }
+
+ double ky;
+ double kx;
+};
+
+} // namespace cheap_ruler
+} // namespace mapbox
diff --git a/include/mapbox/geometry.hpp b/include/mapbox/geometry.hpp
new file mode 100644
index 0000000..e232453
--- /dev/null
+++ b/include/mapbox/geometry.hpp
@@ -0,0 +1,13 @@
+#pragma once
+
+#include <mapbox/geometry/point.hpp>
+#include <mapbox/geometry/line_string.hpp>
+#include <mapbox/geometry/polygon.hpp>
+#include <mapbox/geometry/multi_point.hpp>
+#include <mapbox/geometry/multi_line_string.hpp>
+#include <mapbox/geometry/multi_polygon.hpp>
+#include <mapbox/geometry/geometry.hpp>
+#include <mapbox/geometry/feature.hpp>
+#include <mapbox/geometry/point_arithmetic.hpp>
+#include <mapbox/geometry/for_each_point.hpp>
+#include <mapbox/geometry/envelope.hpp>
diff --git a/include/mapbox/geometry/box.hpp b/include/mapbox/geometry/box.hpp
new file mode 100644
index 0000000..bf81b70
--- /dev/null
+++ b/include/mapbox/geometry/box.hpp
@@ -0,0 +1,34 @@
+#pragma once
+
+#include <mapbox/geometry/point.hpp>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T>
+struct box
+{
+ using point_type = point<T>;
+
+ constexpr box(point_type const& min_, point_type const& max_)
+ : min(min_), max(max_)
+ {}
+
+ point_type min;
+ point_type max;
+};
+
+template <typename T>
+constexpr bool operator==(box<T> const& lhs, box<T> const& rhs)
+{
+ return lhs.min == rhs.min && lhs.max == rhs.max;
+}
+
+template <typename T>
+constexpr bool operator!=(box<T> const& lhs, box<T> const& rhs)
+{
+ return lhs.min != rhs.min || lhs.max != rhs.max;
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/envelope.hpp b/include/mapbox/geometry/envelope.hpp
new file mode 100644
index 0000000..8603583
--- /dev/null
+++ b/include/mapbox/geometry/envelope.hpp
@@ -0,0 +1,33 @@
+#pragma once
+
+#include <mapbox/geometry/box.hpp>
+#include <mapbox/geometry/for_each_point.hpp>
+
+#include <limits>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename G, typename T = typename G::coordinate_type>
+box<T> envelope(G const& geometry)
+{
+ using limits = std::numeric_limits<T>;
+
+ T min_t = limits::has_infinity ? -limits::infinity() : limits::min();
+ T max_t = limits::has_infinity ? limits::infinity() : limits::max();
+
+ point<T> min(max_t, max_t);
+ point<T> max(min_t, min_t);
+
+ for_each_point(geometry, [&] (point<T> const& point) {
+ if (min.x > point.x) min.x = point.x;
+ if (min.y > point.y) min.y = point.y;
+ if (max.x < point.x) max.x = point.x;
+ if (max.y < point.y) max.y = point.y;
+ });
+
+ return box<T>(min, max);
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/feature.hpp b/include/mapbox/geometry/feature.hpp
new file mode 100644
index 0000000..3bdd484
--- /dev/null
+++ b/include/mapbox/geometry/feature.hpp
@@ -0,0 +1,81 @@
+#pragma once
+
+#include <mapbox/geometry/geometry.hpp>
+
+#include <mapbox/variant.hpp>
+
+#include <cstdint>
+#include <string>
+#include <vector>
+#include <unordered_map>
+#include <experimental/optional>
+
+namespace mapbox {
+namespace geometry {
+
+struct value;
+
+struct null_value_t
+{
+ constexpr null_value_t() {}
+ constexpr null_value_t(std::nullptr_t) {}
+};
+
+constexpr bool operator==(const null_value_t&, const null_value_t&) { return true; }
+constexpr bool operator!=(const null_value_t&, const null_value_t&) { return false; }
+
+constexpr null_value_t null_value = null_value_t();
+
+// Multiple numeric types (uint64_t, int64_t, double) are present in order to support
+// the widest possible range of JSON numbers, which do not have a maximum range.
+// Implementations that produce `value`s should use that order for type preference,
+// using uint64_t for positive integers, int64_t for negative integers, and double
+// for non-integers and integers outside the range of 64 bits.
+using value_base = mapbox::util::variant<null_value_t, bool, uint64_t, int64_t, double, std::string,
+ mapbox::util::recursive_wrapper<std::vector<value>>,
+ mapbox::util::recursive_wrapper<std::unordered_map<std::string, value>>>;
+
+struct value : value_base
+{
+ using value_base::value_base;
+};
+
+using property_map = std::unordered_map<std::string, value>;
+
+// The same considerations and requirement for numeric types apply as for `value_base`.
+using identifier = mapbox::util::variant<uint64_t, int64_t, double, std::string>;
+
+template <class T>
+struct feature
+{
+ using coordinate_type = T;
+ using geometry_type = mapbox::geometry::geometry<T>; // Fully qualified to avoid GCC -fpermissive error.
+
+ geometry_type geometry;
+ property_map properties {};
+ std::experimental::optional<identifier> id {};
+};
+
+template <class T>
+constexpr bool operator==(feature<T> const& lhs, feature<T> const& rhs)
+{
+ return lhs.id == rhs.id && lhs.geometry == rhs.geometry && lhs.properties == rhs.properties;
+}
+
+template <class T>
+constexpr bool operator!=(feature<T> const& lhs, feature<T> const& rhs)
+{
+ return !(lhs == rhs);
+}
+
+template <class T, template <typename...> class Cont = std::vector>
+struct feature_collection : Cont<feature<T>>
+{
+ using coordinate_type = T;
+ using feature_type = feature<T>;
+ using container_type = Cont<feature_type>;
+ using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/for_each_point.hpp b/include/mapbox/geometry/for_each_point.hpp
new file mode 100644
index 0000000..44d6e77
--- /dev/null
+++ b/include/mapbox/geometry/for_each_point.hpp
@@ -0,0 +1,45 @@
+#pragma once
+
+#include <mapbox/geometry/geometry.hpp>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename Point, typename F>
+auto for_each_point(Point&& point, F&& f)
+ -> decltype(point.x, point.y, void())
+{
+ f(std::forward<Point>(point));
+}
+
+template <typename Container, typename F>
+auto for_each_point(Container&& container, F&& f)
+ -> decltype(container.begin(), container.end(), void());
+
+template <typename...Types, typename F>
+void for_each_point(mapbox::util::variant<Types...> const& geom, F&& f)
+{
+ mapbox::util::variant<Types...>::visit(geom, [&] (auto const& g) {
+ for_each_point(g, f);
+ });
+}
+
+template <typename...Types, typename F>
+void for_each_point(mapbox::util::variant<Types...> & geom, F&& f)
+{
+ mapbox::util::variant<Types...>::visit(geom, [&] (auto & g) {
+ for_each_point(g, f);
+ });
+}
+
+template <typename Container, typename F>
+auto for_each_point(Container&& container, F&& f)
+ -> decltype(container.begin(), container.end(), void())
+{
+ for (auto& e: container) {
+ for_each_point(e, f);
+ }
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/geometry.hpp b/include/mapbox/geometry/geometry.hpp
new file mode 100644
index 0000000..a3970bf
--- /dev/null
+++ b/include/mapbox/geometry/geometry.hpp
@@ -0,0 +1,53 @@
+#pragma once
+
+#include <mapbox/geometry/point.hpp>
+#include <mapbox/geometry/line_string.hpp>
+#include <mapbox/geometry/polygon.hpp>
+#include <mapbox/geometry/multi_point.hpp>
+#include <mapbox/geometry/multi_line_string.hpp>
+#include <mapbox/geometry/multi_polygon.hpp>
+
+#include <mapbox/variant.hpp>
+
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct geometry_collection;
+
+template <typename T>
+using geometry_base = mapbox::util::variant<point<T>,
+ line_string<T>,
+ polygon<T>,
+ multi_point<T>,
+ multi_line_string<T>,
+ multi_polygon<T>,
+ geometry_collection<T>>;
+
+template <typename T>
+struct geometry : geometry_base<T>
+{
+ using coordinate_type = T;
+ using geometry_base<T>::geometry_base;
+
+ /*
+ * The default constructor would create a point geometry with default-constructed coordinates;
+ * i.e. (0, 0). Since this is not particularly useful, and could hide bugs, it is disabled.
+ */
+ geometry() = delete;
+};
+
+template <typename T, template <typename...> class Cont>
+struct geometry_collection : Cont<geometry<T>>
+{
+ using coordinate_type = T;
+ using geometry_type = geometry<T>;
+ using container_type = Cont<geometry_type>;
+ using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/line_string.hpp b/include/mapbox/geometry/line_string.hpp
new file mode 100644
index 0000000..6d811ce
--- /dev/null
+++ b/include/mapbox/geometry/line_string.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/point.hpp>
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct line_string : Cont<point<T> >
+{
+ using coordinate_type = T;
+ using point_type = point<T>;
+ using container_type = Cont<point_type>;
+ using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/multi_line_string.hpp b/include/mapbox/geometry/multi_line_string.hpp
new file mode 100644
index 0000000..07a7a1d
--- /dev/null
+++ b/include/mapbox/geometry/multi_line_string.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/line_string.hpp>
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct multi_line_string : Cont<line_string<T>>
+{
+ using coordinate_type = T;
+ using line_string_type = line_string<T>;
+ using container_type = Cont<line_string_type>;
+ using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/multi_point.hpp b/include/mapbox/geometry/multi_point.hpp
new file mode 100644
index 0000000..a3c73cf
--- /dev/null
+++ b/include/mapbox/geometry/multi_point.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/point.hpp>
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct multi_point : Cont<point<T>>
+{
+ using coordinate_type = T;
+ using point_type = point<T>;
+ using container_type = Cont<point_type>;
+ using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/multi_polygon.hpp b/include/mapbox/geometry/multi_polygon.hpp
new file mode 100644
index 0000000..ad230a0
--- /dev/null
+++ b/include/mapbox/geometry/multi_polygon.hpp
@@ -0,0 +1,21 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/polygon.hpp>
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct multi_polygon : Cont<polygon<T>>
+{
+ using coordinate_type = T;
+ using polygon_type = polygon<T>;
+ using container_type = Cont<polygon_type>;
+ using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/point.hpp b/include/mapbox/geometry/point.hpp
new file mode 100644
index 0000000..0cba499
--- /dev/null
+++ b/include/mapbox/geometry/point.hpp
@@ -0,0 +1,35 @@
+#pragma once
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T>
+struct point
+{
+ using coordinate_type = T;
+
+ constexpr point()
+ : x(), y()
+ {}
+ constexpr point(T x_, T y_)
+ : x(x_), y(y_)
+ {}
+
+ T x;
+ T y;
+};
+
+template <typename T>
+constexpr bool operator==(point<T> const& lhs, point<T> const& rhs)
+{
+ return lhs.x == rhs.x && lhs.y == rhs.y;
+}
+
+template <typename T>
+constexpr bool operator!=(point<T> const& lhs, point<T> const& rhs)
+{
+ return !(lhs == rhs);
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/point_arithmetic.hpp b/include/mapbox/geometry/point_arithmetic.hpp
new file mode 100644
index 0000000..3940e5b
--- /dev/null
+++ b/include/mapbox/geometry/point_arithmetic.hpp
@@ -0,0 +1,119 @@
+#pragma once
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T>
+constexpr point<T> operator+(point<T> const& lhs, point<T> const& rhs)
+{
+ return point<T>(lhs.x + rhs.x, lhs.y + rhs.y);
+}
+
+template <typename T>
+constexpr point<T> operator+(point<T> const& lhs, T const& rhs)
+{
+ return point<T>(lhs.x + rhs, lhs.y + rhs);
+}
+
+template <typename T>
+constexpr point<T> operator-(point<T> const& lhs, point<T> const& rhs)
+{
+ return point<T>(lhs.x - rhs.x, lhs.y - rhs.y);
+}
+
+template <typename T>
+constexpr point<T> operator-(point<T> const& lhs, T const& rhs)
+{
+ return point<T>(lhs.x - rhs, lhs.y - rhs);
+}
+
+template <typename T>
+constexpr point<T> operator*(point<T> const& lhs, point<T> const& rhs)
+{
+ return point<T>(lhs.x * rhs.x, lhs.y * rhs.y);
+}
+
+template <typename T>
+constexpr point<T> operator*(point<T> const& lhs, T const& rhs)
+{
+ return point<T>(lhs.x * rhs, lhs.y * rhs);
+}
+
+template <typename T>
+constexpr point<T> operator/(point<T> const& lhs, point<T> const& rhs)
+{
+ return point<T>(lhs.x / rhs.x, lhs.y / rhs.y);
+}
+
+template <typename T>
+constexpr point<T> operator/(point<T> const& lhs, T const& rhs)
+{
+ return point<T>(lhs.x / rhs, lhs.y / rhs);
+}
+
+template <typename T>
+constexpr point<T>& operator+=(point<T>& lhs, point<T> const& rhs)
+{
+ lhs.x += rhs.x;
+ lhs.y += rhs.y;
+ return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator+=(point<T>& lhs, T const& rhs)
+{
+ lhs.x += rhs;
+ lhs.y += rhs;
+ return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator-=(point<T>& lhs, point<T> const& rhs)
+{
+ lhs.x -= rhs.x;
+ lhs.y -= rhs.y;
+ return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator-=(point<T>& lhs, T const& rhs)
+{
+ lhs.x -= rhs;
+ lhs.y -= rhs;
+ return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator*=(point<T>& lhs, point<T> const& rhs)
+{
+ lhs.x *= rhs.x;
+ lhs.y *= rhs.y;
+ return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator*=(point<T>& lhs, T const& rhs)
+{
+ lhs.x *= rhs;
+ lhs.y *= rhs;
+ return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator/=(point<T>& lhs, point<T> const& rhs)
+{
+ lhs.x /= rhs.x;
+ lhs.y /= rhs.y;
+ return lhs;
+}
+
+template <typename T>
+constexpr point<T>& operator/=(point<T>& lhs, T const& rhs)
+{
+ lhs.x /= rhs;
+ lhs.y /= rhs;
+ return lhs;
+}
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/geometry/polygon.hpp b/include/mapbox/geometry/polygon.hpp
new file mode 100644
index 0000000..99a66aa
--- /dev/null
+++ b/include/mapbox/geometry/polygon.hpp
@@ -0,0 +1,31 @@
+#pragma once
+
+// mapbox
+#include <mapbox/geometry/point.hpp>
+
+// stl
+#include <vector>
+
+namespace mapbox {
+namespace geometry {
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct linear_ring : Cont<point<T>>
+{
+ using coordinate_type = T;
+ using point_type = point<T>;
+ using container_type = Cont<point_type>;
+ using container_type::container_type;
+};
+
+template <typename T, template <typename...> class Cont = std::vector>
+struct polygon : Cont<linear_ring<T>>
+{
+ using coordinate_type = T;
+ using linear_ring_type = linear_ring<T>;
+ using container_type = Cont<linear_ring_type>;
+ using container_type::container_type;
+};
+
+} // namespace geometry
+} // namespace mapbox
diff --git a/include/mapbox/optional.hpp b/include/mapbox/optional.hpp
new file mode 100644
index 0000000..d84705c
--- /dev/null
+++ b/include/mapbox/optional.hpp
@@ -0,0 +1,74 @@
+#ifndef MAPBOX_UTIL_OPTIONAL_HPP
+#define MAPBOX_UTIL_OPTIONAL_HPP
+
+#pragma message("This implementation of optional is deprecated. See https://github.com/mapbox/variant/issues/64.")
+
+#include <type_traits>
+#include <utility>
+
+#include <mapbox/variant.hpp>
+
+namespace mapbox {
+namespace util {
+
+template <typename T>
+class optional
+{
+ static_assert(!std::is_reference<T>::value, "optional doesn't support references");
+
+ struct none_type
+ {
+ };
+
+ variant<none_type, T> variant_;
+
+public:
+ optional() = default;
+
+ optional(optional const& rhs)
+ {
+ if (this != &rhs)
+ { // protect against invalid self-assignment
+ variant_ = rhs.variant_;
+ }
+ }
+
+ optional(T const& v) { variant_ = v; }
+
+ explicit operator bool() const noexcept { return variant_.template is<T>(); }
+
+ T const& get() const { return variant_.template get<T>(); }
+ T& get() { return variant_.template get<T>(); }
+
+ T const& operator*() const { return this->get(); }
+ T operator*() { return this->get(); }
+
+ optional& operator=(T const& v)
+ {
+ variant_ = v;
+ return *this;
+ }
+
+ optional& operator=(optional const& rhs)
+ {
+ if (this != &rhs)
+ {
+ variant_ = rhs.variant_;
+ }
+ return *this;
+ }
+
+ template <typename... Args>
+ void emplace(Args&&... args)
+ {
+ variant_ = T{std::forward<Args>(args)...};
+ }
+
+ void reset() { variant_ = none_type{}; }
+
+}; // class optional
+
+} // namespace util
+} // namespace mapbox
+
+#endif // MAPBOX_UTIL_OPTIONAL_HPP
diff --git a/include/mapbox/recursive_wrapper.hpp b/include/mapbox/recursive_wrapper.hpp
new file mode 100644
index 0000000..4ffcbd7
--- /dev/null
+++ b/include/mapbox/recursive_wrapper.hpp
@@ -0,0 +1,122 @@
+#ifndef MAPBOX_UTIL_RECURSIVE_WRAPPER_HPP
+#define MAPBOX_UTIL_RECURSIVE_WRAPPER_HPP
+
+// Based on variant/recursive_wrapper.hpp from boost.
+//
+// Original license:
+//
+// Copyright (c) 2002-2003
+// Eric Friedman, Itay Maman
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <cassert>
+#include <utility>
+
+namespace mapbox {
+namespace util {
+
+template <typename T>
+class recursive_wrapper
+{
+
+ T* p_;
+
+ void assign(T const& rhs)
+ {
+ this->get() = rhs;
+ }
+
+public:
+ using type = T;
+
+ /**
+ * Default constructor default initializes the internally stored value.
+ * For POD types this means nothing is done and the storage is
+ * uninitialized.
+ *
+ * @throws std::bad_alloc if there is insufficient memory for an object
+ * of type T.
+ * @throws any exception thrown by the default constructur of T.
+ */
+ recursive_wrapper()
+ : p_(new T){}
+
+ ~recursive_wrapper() noexcept { delete p_; }
+
+ recursive_wrapper(recursive_wrapper const& operand)
+ : p_(new T(operand.get())) {}
+
+ recursive_wrapper(T const& operand)
+ : p_(new T(operand)) {}
+
+ recursive_wrapper(recursive_wrapper&& operand)
+ : p_(new T(std::move(operand.get()))) {}
+
+ recursive_wrapper(T&& operand)
+ : p_(new T(std::move(operand))) {}
+
+ inline recursive_wrapper& operator=(recursive_wrapper const& rhs)
+ {
+ assign(rhs.get());
+ return *this;
+ }
+
+ inline recursive_wrapper& operator=(T const& rhs)
+ {
+ assign(rhs);
+ return *this;
+ }
+
+ inline void swap(recursive_wrapper& operand) noexcept
+ {
+ T* temp = operand.p_;
+ operand.p_ = p_;
+ p_ = temp;
+ }
+
+ recursive_wrapper& operator=(recursive_wrapper&& rhs) noexcept
+ {
+ swap(rhs);
+ return *this;
+ }
+
+ recursive_wrapper& operator=(T&& rhs)
+ {
+ get() = std::move(rhs);
+ return *this;
+ }
+
+ T& get()
+ {
+ assert(p_);
+ return *get_pointer();
+ }
+
+ T const& get() const
+ {
+ assert(p_);
+ return *get_pointer();
+ }
+
+ T* get_pointer() { return p_; }
+
+ const T* get_pointer() const { return p_; }
+
+ operator T const&() const { return this->get(); }
+
+ operator T&() { return this->get(); }
+
+}; // class recursive_wrapper
+
+template <typename T>
+inline void swap(recursive_wrapper<T>& lhs, recursive_wrapper<T>& rhs) noexcept
+{
+ lhs.swap(rhs);
+}
+} // namespace util
+} // namespace mapbox
+
+#endif // MAPBOX_UTIL_RECURSIVE_WRAPPER_HPP
diff --git a/include/mapbox/variant.hpp b/include/mapbox/variant.hpp
new file mode 100644
index 0000000..fb0f77e
--- /dev/null
+++ b/include/mapbox/variant.hpp
@@ -0,0 +1,1013 @@
+#ifndef MAPBOX_UTIL_VARIANT_HPP
+#define MAPBOX_UTIL_VARIANT_HPP
+
+#include <cassert>
+#include <cstddef> // size_t
+#include <new> // operator new
+#include <stdexcept> // runtime_error
+#include <string>
+#include <tuple>
+#include <type_traits>
+#include <typeinfo>
+#include <utility>
+#include <functional>
+
+#include <mapbox/recursive_wrapper.hpp>
+#include <mapbox/variant_visitor.hpp>
+
+// clang-format off
+// [[deprecated]] is only available in C++14, use this for the time being
+#if __cplusplus <= 201103L
+# ifdef __GNUC__
+# define MAPBOX_VARIANT_DEPRECATED __attribute__((deprecated))
+# elif defined(_MSC_VER)
+# define MAPBOX_VARIANT_DEPRECATED __declspec(deprecated)
+# else
+# define MAPBOX_VARIANT_DEPRECATED
+# endif
+#else
+# define MAPBOX_VARIANT_DEPRECATED [[deprecated]]
+#endif
+
+
+#ifdef _MSC_VER
+// https://msdn.microsoft.com/en-us/library/bw1hbe6y.aspx
+# ifdef NDEBUG
+# define VARIANT_INLINE __forceinline
+# else
+# define VARIANT_INLINE //__declspec(noinline)
+# endif
+#else
+# ifdef NDEBUG
+# define VARIANT_INLINE //inline __attribute__((always_inline))
+# else
+# define VARIANT_INLINE __attribute__((noinline))
+# endif
+#endif
+// clang-format on
+
+// Exceptions
+#if defined( __EXCEPTIONS) || defined( _MSC_VER)
+#define HAS_EXCEPTIONS
+#endif
+
+#define VARIANT_MAJOR_VERSION 1
+#define VARIANT_MINOR_VERSION 1
+#define VARIANT_PATCH_VERSION 0
+
+#define VARIANT_VERSION (VARIANT_MAJOR_VERSION * 100000) + (VARIANT_MINOR_VERSION * 100) + (VARIANT_PATCH_VERSION)
+
+namespace mapbox {
+namespace util {
+
+// XXX This should derive from std::logic_error instead of std::runtime_error.
+// See https://github.com/mapbox/variant/issues/48 for details.
+class bad_variant_access : public std::runtime_error
+{
+
+public:
+ explicit bad_variant_access(const std::string& what_arg)
+ : runtime_error(what_arg) {}
+
+ explicit bad_variant_access(const char* what_arg)
+ : runtime_error(what_arg) {}
+
+}; // class bad_variant_access
+
+template <typename R = void>
+struct MAPBOX_VARIANT_DEPRECATED static_visitor
+{
+ using result_type = R;
+
+protected:
+ static_visitor() {}
+ ~static_visitor() {}
+};
+
+namespace detail {
+
+static constexpr std::size_t invalid_value = std::size_t(-1);
+
+template <typename T, typename... Types>
+struct direct_type;
+
+template <typename T, typename First, typename... Types>
+struct direct_type<T, First, Types...>
+{
+ static constexpr std::size_t index = std::is_same<T, First>::value
+ ? sizeof...(Types)
+ : direct_type<T, Types...>::index;
+};
+
+template <typename T>
+struct direct_type<T>
+{
+ static constexpr std::size_t index = invalid_value;
+};
+
+#if __cpp_lib_logical_traits >= 201510L
+
+using std::disjunction;
+
+#else
+
+template <typename...>
+struct disjunction : std::false_type {};
+
+template <typename B1>
+struct disjunction<B1> : B1 {};
+
+template <typename B1, typename B2>
+struct disjunction<B1, B2> : std::conditional<B1::value, B1, B2>::type {};
+
+template <typename B1, typename... Bs>
+struct disjunction<B1, Bs...> : std::conditional<B1::value, B1, disjunction<Bs...>>::type {};
+
+#endif
+
+template <typename T, typename... Types>
+struct convertible_type;
+
+template <typename T, typename First, typename... Types>
+struct convertible_type<T, First, Types...>
+{
+ static constexpr std::size_t index = std::is_convertible<T, First>::value
+ ? disjunction<std::is_convertible<T, Types>...>::value ? invalid_value : sizeof...(Types)
+ : convertible_type<T, Types...>::index;
+};
+
+template <typename T>
+struct convertible_type<T>
+{
+ static constexpr std::size_t index = invalid_value;
+};
+
+template <typename T, typename... Types>
+struct value_traits
+{
+ using value_type = typename std::remove_const<typename std::remove_reference<T>::type>::type;
+ static constexpr std::size_t direct_index = direct_type<value_type, Types...>::index;
+ static constexpr bool is_direct = direct_index != invalid_value;
+ static constexpr std::size_t index = is_direct ? direct_index : convertible_type<value_type, Types...>::index;
+ static constexpr bool is_valid = index != invalid_value;
+ static constexpr std::size_t tindex = is_valid ? sizeof...(Types)-index : 0;
+ using target_type = typename std::tuple_element<tindex, std::tuple<void, Types...>>::type;
+};
+
+template <typename T, typename R = void>
+struct enable_if_type
+{
+ using type = R;
+};
+
+template <typename F, typename V, typename Enable = void>
+struct result_of_unary_visit
+{
+ using type = typename std::result_of<F(V&)>::type;
+};
+
+template <typename F, typename V>
+struct result_of_unary_visit<F, V, typename enable_if_type<typename F::result_type>::type>
+{
+ using type = typename F::result_type;
+};
+
+template <typename F, typename V, typename Enable = void>
+struct result_of_binary_visit
+{
+ using type = typename std::result_of<F(V&, V&)>::type;
+};
+
+template <typename F, typename V>
+struct result_of_binary_visit<F, V, typename enable_if_type<typename F::result_type>::type>
+{
+ using type = typename F::result_type;
+};
+
+template <std::size_t arg1, std::size_t... others>
+struct static_max;
+
+template <std::size_t arg>
+struct static_max<arg>
+{
+ static const std::size_t value = arg;
+};
+
+template <std::size_t arg1, std::size_t arg2, std::size_t... others>
+struct static_max<arg1, arg2, others...>
+{
+ static const std::size_t value = arg1 >= arg2 ? static_max<arg1, others...>::value : static_max<arg2, others...>::value;
+};
+
+template <typename... Types>
+struct variant_helper;
+
+template <typename T, typename... Types>
+struct variant_helper<T, Types...>
+{
+ VARIANT_INLINE static void destroy(const std::size_t type_index, void* data)
+ {
+ if (type_index == sizeof...(Types))
+ {
+ reinterpret_cast<T*>(data)->~T();
+ }
+ else
+ {
+ variant_helper<Types...>::destroy(type_index, data);
+ }
+ }
+
+ VARIANT_INLINE static void move(const std::size_t old_type_index, void* old_value, void* new_value)
+ {
+ if (old_type_index == sizeof...(Types))
+ {
+ new (new_value) T(std::move(*reinterpret_cast<T*>(old_value)));
+ }
+ else
+ {
+ variant_helper<Types...>::move(old_type_index, old_value, new_value);
+ }
+ }
+
+ VARIANT_INLINE static void copy(const std::size_t old_type_index, const void* old_value, void* new_value)
+ {
+ if (old_type_index == sizeof...(Types))
+ {
+ new (new_value) T(*reinterpret_cast<const T*>(old_value));
+ }
+ else
+ {
+ variant_helper<Types...>::copy(old_type_index, old_value, new_value);
+ }
+ }
+};
+
+template <>
+struct variant_helper<>
+{
+ VARIANT_INLINE static void destroy(const std::size_t, void*) {}
+ VARIANT_INLINE static void move(const std::size_t, void*, void*) {}
+ VARIANT_INLINE static void copy(const std::size_t, const void*, void*) {}
+};
+
+template <typename T>
+struct unwrapper
+{
+ static T const& apply_const(T const& obj) { return obj; }
+ static T& apply(T& obj) { return obj; }
+};
+
+template <typename T>
+struct unwrapper<recursive_wrapper<T>>
+{
+ static auto apply_const(recursive_wrapper<T> const& obj)
+ -> typename recursive_wrapper<T>::type const&
+ {
+ return obj.get();
+ }
+ static auto apply(recursive_wrapper<T>& obj)
+ -> typename recursive_wrapper<T>::type&
+ {
+ return obj.get();
+ }
+};
+
+template <typename T>
+struct unwrapper<std::reference_wrapper<T>>
+{
+ static auto apply_const(std::reference_wrapper<T> const& obj)
+ -> typename std::reference_wrapper<T>::type const&
+ {
+ return obj.get();
+ }
+ static auto apply(std::reference_wrapper<T>& obj)
+ -> typename std::reference_wrapper<T>::type&
+ {
+ return obj.get();
+ }
+};
+
+template <typename F, typename V, typename R, typename... Types>
+struct dispatcher;
+
+template <typename F, typename V, typename R, typename T, typename... Types>
+struct dispatcher<F, V, R, T, Types...>
+{
+ VARIANT_INLINE static R apply_const(V const& v, F&& f)
+ {
+ if (v.template is<T>())
+ {
+ return f(unwrapper<T>::apply_const(v.template get_unchecked<T>()));
+ }
+ else
+ {
+ return dispatcher<F, V, R, Types...>::apply_const(v, std::forward<F>(f));
+ }
+ }
+
+ VARIANT_INLINE static R apply(V& v, F&& f)
+ {
+ if (v.template is<T>())
+ {
+ return f(unwrapper<T>::apply(v.template get_unchecked<T>()));
+ }
+ else
+ {
+ return dispatcher<F, V, R, Types...>::apply(v, std::forward<F>(f));
+ }
+ }
+};
+
+template <typename F, typename V, typename R, typename T>
+struct dispatcher<F, V, R, T>
+{
+ VARIANT_INLINE static R apply_const(V const& v, F&& f)
+ {
+ return f(unwrapper<T>::apply_const(v.template get_unchecked<T>()));
+ }
+
+ VARIANT_INLINE static R apply(V& v, F&& f)
+ {
+ return f(unwrapper<T>::apply(v.template get_unchecked<T>()));
+ }
+};
+
+template <typename F, typename V, typename R, typename T, typename... Types>
+struct binary_dispatcher_rhs;
+
+template <typename F, typename V, typename R, typename T0, typename T1, typename... Types>
+struct binary_dispatcher_rhs<F, V, R, T0, T1, Types...>
+{
+ VARIANT_INLINE static R apply_const(V const& lhs, V const& rhs, F&& f)
+ {
+ if (rhs.template is<T1>()) // call binary functor
+ {
+ return f(unwrapper<T0>::apply_const(lhs.template get_unchecked<T0>()),
+ unwrapper<T1>::apply_const(rhs.template get_unchecked<T1>()));
+ }
+ else
+ {
+ return binary_dispatcher_rhs<F, V, R, T0, Types...>::apply_const(lhs, rhs, std::forward<F>(f));
+ }
+ }
+
+ VARIANT_INLINE static R apply(V& lhs, V& rhs, F&& f)
+ {
+ if (rhs.template is<T1>()) // call binary functor
+ {
+ return f(unwrapper<T0>::apply(lhs.template get_unchecked<T0>()),
+ unwrapper<T1>::apply(rhs.template get_unchecked<T1>()));
+ }
+ else
+ {
+ return binary_dispatcher_rhs<F, V, R, T0, Types...>::apply(lhs, rhs, std::forward<F>(f));
+ }
+ }
+};
+
+template <typename F, typename V, typename R, typename T0, typename T1>
+struct binary_dispatcher_rhs<F, V, R, T0, T1>
+{
+ VARIANT_INLINE static R apply_const(V const& lhs, V const& rhs, F&& f)
+ {
+ return f(unwrapper<T0>::apply_const(lhs.template get_unchecked<T0>()),
+ unwrapper<T1>::apply_const(rhs.template get_unchecked<T1>()));
+ }
+
+ VARIANT_INLINE static R apply(V& lhs, V& rhs, F&& f)
+ {
+ return f(unwrapper<T0>::apply(lhs.template get_unchecked<T0>()),
+ unwrapper<T1>::apply(rhs.template get_unchecked<T1>()));
+ }
+};
+
+template <typename F, typename V, typename R, typename T, typename... Types>
+struct binary_dispatcher_lhs;
+
+template <typename F, typename V, typename R, typename T0, typename T1, typename... Types>
+struct binary_dispatcher_lhs<F, V, R, T0, T1, Types...>
+{
+ VARIANT_INLINE static R apply_const(V const& lhs, V const& rhs, F&& f)
+ {
+ if (lhs.template is<T1>()) // call binary functor
+ {
+ return f(unwrapper<T1>::apply_const(lhs.template get_unchecked<T1>()),
+ unwrapper<T0>::apply_const(rhs.template get_unchecked<T0>()));
+ }
+ else
+ {
+ return binary_dispatcher_lhs<F, V, R, T0, Types...>::apply_const(lhs, rhs, std::forward<F>(f));
+ }
+ }
+
+ VARIANT_INLINE static R apply(V& lhs, V& rhs, F&& f)
+ {
+ if (lhs.template is<T1>()) // call binary functor
+ {
+ return f(unwrapper<T1>::apply(lhs.template get_unchecked<T1>()),
+ unwrapper<T0>::apply(rhs.template get_unchecked<T0>()));
+ }
+ else
+ {
+ return binary_dispatcher_lhs<F, V, R, T0, Types...>::apply(lhs, rhs, std::forward<F>(f));
+ }
+ }
+};
+
+template <typename F, typename V, typename R, typename T0, typename T1>
+struct binary_dispatcher_lhs<F, V, R, T0, T1>
+{
+ VARIANT_INLINE static R apply_const(V const& lhs, V const& rhs, F&& f)
+ {
+ return f(unwrapper<T1>::apply_const(lhs.template get_unchecked<T1>()),
+ unwrapper<T0>::apply_const(rhs.template get_unchecked<T0>()));
+ }
+
+ VARIANT_INLINE static R apply(V& lhs, V& rhs, F&& f)
+ {
+ return f(unwrapper<T1>::apply(lhs.template get_unchecked<T1>()),
+ unwrapper<T0>::apply(rhs.template get_unchecked<T0>()));
+ }
+};
+
+template <typename F, typename V, typename R, typename... Types>
+struct binary_dispatcher;
+
+template <typename F, typename V, typename R, typename T, typename... Types>
+struct binary_dispatcher<F, V, R, T, Types...>
+{
+ VARIANT_INLINE static R apply_const(V const& v0, V const& v1, F&& f)
+ {
+ if (v0.template is<T>())
+ {
+ if (v1.template is<T>())
+ {
+ return f(unwrapper<T>::apply_const(v0.template get_unchecked<T>()),
+ unwrapper<T>::apply_const(v1.template get_unchecked<T>())); // call binary functor
+ }
+ else
+ {
+ return binary_dispatcher_rhs<F, V, R, T, Types...>::apply_const(v0, v1, std::forward<F>(f));
+ }
+ }
+ else if (v1.template is<T>())
+ {
+ return binary_dispatcher_lhs<F, V, R, T, Types...>::apply_const(v0, v1, std::forward<F>(f));
+ }
+ return binary_dispatcher<F, V, R, Types...>::apply_const(v0, v1, std::forward<F>(f));
+ }
+
+ VARIANT_INLINE static R apply(V& v0, V& v1, F&& f)
+ {
+ if (v0.template is<T>())
+ {
+ if (v1.template is<T>())
+ {
+ return f(unwrapper<T>::apply(v0.template get_unchecked<T>()),
+ unwrapper<T>::apply(v1.template get_unchecked<T>())); // call binary functor
+ }
+ else
+ {
+ return binary_dispatcher_rhs<F, V, R, T, Types...>::apply(v0, v1, std::forward<F>(f));
+ }
+ }
+ else if (v1.template is<T>())
+ {
+ return binary_dispatcher_lhs<F, V, R, T, Types...>::apply(v0, v1, std::forward<F>(f));
+ }
+ return binary_dispatcher<F, V, R, Types...>::apply(v0, v1, std::forward<F>(f));
+ }
+};
+
+template <typename F, typename V, typename R, typename T>
+struct binary_dispatcher<F, V, R, T>
+{
+ VARIANT_INLINE static R apply_const(V const& v0, V const& v1, F&& f)
+ {
+ return f(unwrapper<T>::apply_const(v0.template get_unchecked<T>()),
+ unwrapper<T>::apply_const(v1.template get_unchecked<T>())); // call binary functor
+ }
+
+ VARIANT_INLINE static R apply(V& v0, V& v1, F&& f)
+ {
+ return f(unwrapper<T>::apply(v0.template get_unchecked<T>()),
+ unwrapper<T>::apply(v1.template get_unchecked<T>())); // call binary functor
+ }
+};
+
+// comparator functors
+struct equal_comp
+{
+ template <typename T>
+ bool operator()(T const& lhs, T const& rhs) const
+ {
+ return lhs == rhs;
+ }
+};
+
+struct less_comp
+{
+ template <typename T>
+ bool operator()(T const& lhs, T const& rhs) const
+ {
+ return lhs < rhs;
+ }
+};
+
+template <typename Variant, typename Comp>
+class comparer
+{
+public:
+ explicit comparer(Variant const& lhs) noexcept
+ : lhs_(lhs) {}
+ comparer& operator=(comparer const&) = delete;
+ // visitor
+ template <typename T>
+ bool operator()(T const& rhs_content) const
+ {
+ T const& lhs_content = lhs_.template get_unchecked<T>();
+ return Comp()(lhs_content, rhs_content);
+ }
+
+private:
+ Variant const& lhs_;
+};
+
+// hashing visitor
+struct hasher
+{
+ template <typename T>
+ std::size_t operator()(const T& hashable) const
+ {
+ return std::hash<T>{}(hashable);
+ }
+};
+
+} // namespace detail
+
+struct no_init
+{
+};
+
+template <typename... Types>
+class variant
+{
+ static_assert(sizeof...(Types) > 0, "Template parameter type list of variant can not be empty");
+ static_assert(!detail::disjunction<std::is_reference<Types>...>::value, "Variant can not hold reference types. Maybe use std::reference_wrapper?");
+
+private:
+ static const std::size_t data_size = detail::static_max<sizeof(Types)...>::value;
+ static const std::size_t data_align = detail::static_max<alignof(Types)...>::value;
+public:
+ struct adapted_variant_tag;
+ using types = std::tuple<Types...>;
+private:
+ using first_type = typename std::tuple_element<0, types>::type;
+ using data_type = typename std::aligned_storage<data_size, data_align>::type;
+ using helper_type = detail::variant_helper<Types...>;
+
+ std::size_t type_index;
+ data_type data;
+
+public:
+ VARIANT_INLINE variant() noexcept(std::is_nothrow_default_constructible<first_type>::value)
+ : type_index(sizeof...(Types)-1)
+ {
+ static_assert(std::is_default_constructible<first_type>::value, "First type in variant must be default constructible to allow default construction of variant");
+ new (&data) first_type();
+ }
+
+ VARIANT_INLINE variant(no_init) noexcept
+ : type_index(detail::invalid_value) {}
+
+ // http://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers
+ template <typename T, typename Traits = detail::value_traits<T, Types...>,
+ typename Enable = typename std::enable_if<Traits::is_valid && !std::is_same<variant<Types...>, typename Traits::value_type>::value>::type >
+ VARIANT_INLINE variant(T&& val) noexcept(std::is_nothrow_constructible<typename Traits::target_type, T&&>::value)
+ : type_index(Traits::index)
+ {
+ new (&data) typename Traits::target_type(std::forward<T>(val));
+ }
+
+ VARIANT_INLINE variant(variant<Types...> const& old)
+ : type_index(old.type_index)
+ {
+ helper_type::copy(old.type_index, &old.data, &data);
+ }
+
+ VARIANT_INLINE variant(variant<Types...>&& old) noexcept(std::is_nothrow_move_constructible<types>::value)
+ : type_index(old.type_index)
+ {
+ helper_type::move(old.type_index, &old.data, &data);
+ }
+
+private:
+ VARIANT_INLINE void copy_assign(variant<Types...> const& rhs)
+ {
+ helper_type::destroy(type_index, &data);
+ type_index = detail::invalid_value;
+ helper_type::copy(rhs.type_index, &rhs.data, &data);
+ type_index = rhs.type_index;
+ }
+
+ VARIANT_INLINE void move_assign(variant<Types...>&& rhs)
+ {
+ helper_type::destroy(type_index, &data);
+ type_index = detail::invalid_value;
+ helper_type::move(rhs.type_index, &rhs.data, &data);
+ type_index = rhs.type_index;
+ }
+
+public:
+ VARIANT_INLINE variant<Types...>& operator=(variant<Types...>&& other)
+ {
+ move_assign(std::move(other));
+ return *this;
+ }
+
+ VARIANT_INLINE variant<Types...>& operator=(variant<Types...> const& other)
+ {
+ copy_assign(other);
+ return *this;
+ }
+
+ // conversions
+ // move-assign
+ template <typename T>
+ VARIANT_INLINE variant<Types...>& operator=(T&& rhs) noexcept
+ {
+ variant<Types...> temp(std::forward<T>(rhs));
+ move_assign(std::move(temp));
+ return *this;
+ }
+
+ // copy-assign
+ template <typename T>
+ VARIANT_INLINE variant<Types...>& operator=(T const& rhs)
+ {
+ variant<Types...> temp(rhs);
+ copy_assign(temp);
+ return *this;
+ }
+
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<T, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE bool is() const
+ {
+ return type_index == detail::direct_type<T, Types...>::index;
+ }
+
+ template <typename T,typename std::enable_if<
+ (detail::direct_type<recursive_wrapper<T>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE bool is() const
+ {
+ return type_index == detail::direct_type<recursive_wrapper<T>, Types...>::index;
+ }
+
+ VARIANT_INLINE bool valid() const
+ {
+ return type_index != detail::invalid_value;
+ }
+
+ template <typename T, typename... Args>
+ VARIANT_INLINE void set(Args&&... args)
+ {
+ helper_type::destroy(type_index, &data);
+ type_index = detail::invalid_value;
+ new (&data) T(std::forward<Args>(args)...);
+ type_index = detail::direct_type<T, Types...>::index;
+ }
+
+ // get_unchecked<T>()
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<T, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T& get_unchecked()
+ {
+ return *reinterpret_cast<T*>(&data);
+ }
+
+#ifdef HAS_EXCEPTIONS
+ // get<T>()
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<T, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T& get()
+ {
+ if (type_index == detail::direct_type<T, Types...>::index)
+ {
+ return *reinterpret_cast<T*>(&data);
+ }
+ else
+ {
+ throw bad_variant_access("in get<T>()");
+ }
+ }
+#endif
+
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<T, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T const& get_unchecked() const
+ {
+ return *reinterpret_cast<T const*>(&data);
+ }
+
+#ifdef HAS_EXCEPTIONS
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<T, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T const& get() const
+ {
+ if (type_index == detail::direct_type<T, Types...>::index)
+ {
+ return *reinterpret_cast<T const*>(&data);
+ }
+ else
+ {
+ throw bad_variant_access("in get<T>()");
+ }
+ }
+#endif
+
+ // get_unchecked<T>() - T stored as recursive_wrapper<T>
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<recursive_wrapper<T>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T& get_unchecked()
+ {
+ return (*reinterpret_cast<recursive_wrapper<T>*>(&data)).get();
+ }
+
+#ifdef HAS_EXCEPTIONS
+ // get<T>() - T stored as recursive_wrapper<T>
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<recursive_wrapper<T>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T& get()
+ {
+ if (type_index == detail::direct_type<recursive_wrapper<T>, Types...>::index)
+ {
+ return (*reinterpret_cast<recursive_wrapper<T>*>(&data)).get();
+ }
+ else
+ {
+ throw bad_variant_access("in get<T>()");
+ }
+ }
+#endif
+
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<recursive_wrapper<T>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T const& get_unchecked() const
+ {
+ return (*reinterpret_cast<recursive_wrapper<T> const*>(&data)).get();
+ }
+
+#ifdef HAS_EXCEPTIONS
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<recursive_wrapper<T>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T const& get() const
+ {
+ if (type_index == detail::direct_type<recursive_wrapper<T>, Types...>::index)
+ {
+ return (*reinterpret_cast<recursive_wrapper<T> const*>(&data)).get();
+ }
+ else
+ {
+ throw bad_variant_access("in get<T>()");
+ }
+ }
+#endif
+
+ // get_unchecked<T>() - T stored as std::reference_wrapper<T>
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<std::reference_wrapper<T>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T& get_unchecked()
+ {
+ return (*reinterpret_cast<std::reference_wrapper<T>*>(&data)).get();
+ }
+
+#ifdef HAS_EXCEPTIONS
+ // get<T>() - T stored as std::reference_wrapper<T>
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<std::reference_wrapper<T>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T& get()
+ {
+ if (type_index == detail::direct_type<std::reference_wrapper<T>, Types...>::index)
+ {
+ return (*reinterpret_cast<std::reference_wrapper<T>*>(&data)).get();
+ }
+ else
+ {
+ throw bad_variant_access("in get<T>()");
+ }
+ }
+#endif
+
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<std::reference_wrapper<T const>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T const& get_unchecked() const
+ {
+ return (*reinterpret_cast<std::reference_wrapper<T const> const*>(&data)).get();
+ }
+
+#ifdef HAS_EXCEPTIONS
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<std::reference_wrapper<T const>, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE T const& get() const
+ {
+ if (type_index == detail::direct_type<std::reference_wrapper<T const>, Types...>::index)
+ {
+ return (*reinterpret_cast<std::reference_wrapper<T const> const*>(&data)).get();
+ }
+ else
+ {
+ throw bad_variant_access("in get<T>()");
+ }
+ }
+#endif
+
+ // This function is deprecated because it returns an internal index field.
+ // Use which() instead.
+ MAPBOX_VARIANT_DEPRECATED VARIANT_INLINE std::size_t get_type_index() const
+ {
+ return type_index;
+ }
+
+ VARIANT_INLINE int which() const noexcept
+ {
+ return static_cast<int>(sizeof...(Types)-type_index - 1);
+ }
+
+ template <typename T, typename std::enable_if<
+ (detail::direct_type<T, Types...>::index != detail::invalid_value)>::type* = nullptr>
+ VARIANT_INLINE static constexpr int which() noexcept
+ {
+ return static_cast<int>(sizeof...(Types)-detail::direct_type<T, Types...>::index - 1);
+ }
+
+ // visitor
+ // unary
+ template <typename F, typename V, typename R = typename detail::result_of_unary_visit<F, first_type>::type>
+ auto VARIANT_INLINE static visit(V const& v, F&& f)
+ -> decltype(detail::dispatcher<F, V, R, Types...>::apply_const(v, std::forward<F>(f)))
+ {
+ return detail::dispatcher<F, V, R, Types...>::apply_const(v, std::forward<F>(f));
+ }
+ // non-const
+ template <typename F, typename V, typename R = typename detail::result_of_unary_visit<F, first_type>::type>
+ auto VARIANT_INLINE static visit(V& v, F&& f)
+ -> decltype(detail::dispatcher<F, V, R, Types...>::apply(v, std::forward<F>(f)))
+ {
+ return detail::dispatcher<F, V, R, Types...>::apply(v, std::forward<F>(f));
+ }
+
+ // binary
+ // const
+ template <typename F, typename V, typename R = typename detail::result_of_binary_visit<F, first_type>::type>
+ auto VARIANT_INLINE static binary_visit(V const& v0, V const& v1, F&& f)
+ -> decltype(detail::binary_dispatcher<F, V, R, Types...>::apply_const(v0, v1, std::forward<F>(f)))
+ {
+ return detail::binary_dispatcher<F, V, R, Types...>::apply_const(v0, v1, std::forward<F>(f));
+ }
+ // non-const
+ template <typename F, typename V, typename R = typename detail::result_of_binary_visit<F, first_type>::type>
+ auto VARIANT_INLINE static binary_visit(V& v0, V& v1, F&& f)
+ -> decltype(detail::binary_dispatcher<F, V, R, Types...>::apply(v0, v1, std::forward<F>(f)))
+ {
+ return detail::binary_dispatcher<F, V, R, Types...>::apply(v0, v1, std::forward<F>(f));
+ }
+
+ // match
+ // unary
+ template <typename... Fs>
+ auto VARIANT_INLINE match(Fs&&... fs) const
+ -> decltype(variant::visit(*this, ::mapbox::util::make_visitor(std::forward<Fs>(fs)...)))
+ {
+ return variant::visit(*this, ::mapbox::util::make_visitor(std::forward<Fs>(fs)...));
+ }
+ // non-const
+ template <typename... Fs>
+ auto VARIANT_INLINE match(Fs&&... fs)
+ -> decltype(variant::visit(*this, ::mapbox::util::make_visitor(std::forward<Fs>(fs)...)))
+ {
+ return variant::visit(*this, ::mapbox::util::make_visitor(std::forward<Fs>(fs)...));
+ }
+
+ ~variant() noexcept // no-throw destructor
+ {
+ helper_type::destroy(type_index, &data);
+ }
+
+ // comparison operators
+ // equality
+ VARIANT_INLINE bool operator==(variant const& rhs) const
+ {
+ assert(valid() && rhs.valid());
+ if (this->which() != rhs.which())
+ {
+ return false;
+ }
+ detail::comparer<variant, detail::equal_comp> visitor(*this);
+ return visit(rhs, visitor);
+ }
+
+ VARIANT_INLINE bool operator!=(variant const& rhs) const
+ {
+ return !(*this == rhs);
+ }
+
+ // less than
+ VARIANT_INLINE bool operator<(variant const& rhs) const
+ {
+ assert(valid() && rhs.valid());
+ if (this->which() != rhs.which())
+ {
+ return this->which() < rhs.which();
+ }
+ detail::comparer<variant, detail::less_comp> visitor(*this);
+ return visit(rhs, visitor);
+ }
+ VARIANT_INLINE bool operator>(variant const& rhs) const
+ {
+ return rhs < *this;
+ }
+ VARIANT_INLINE bool operator<=(variant const& rhs) const
+ {
+ return !(*this > rhs);
+ }
+ VARIANT_INLINE bool operator>=(variant const& rhs) const
+ {
+ return !(*this < rhs);
+ }
+};
+
+// unary visitor interface
+// const
+template <typename F, typename V>
+auto VARIANT_INLINE apply_visitor(F&& f, V const& v) -> decltype(V::visit(v, std::forward<F>(f)))
+{
+ return V::visit(v, std::forward<F>(f));
+}
+
+// non-const
+template <typename F, typename V>
+auto VARIANT_INLINE apply_visitor(F&& f, V& v) -> decltype(V::visit(v, std::forward<F>(f)))
+{
+ return V::visit(v, std::forward<F>(f));
+}
+
+// binary visitor interface
+// const
+template <typename F, typename V>
+auto VARIANT_INLINE apply_visitor(F&& f, V const& v0, V const& v1) -> decltype(V::binary_visit(v0, v1, std::forward<F>(f)))
+{
+ return V::binary_visit(v0, v1, std::forward<F>(f));
+}
+
+// non-const
+template <typename F, typename V>
+auto VARIANT_INLINE apply_visitor(F&& f, V& v0, V& v1) -> decltype(V::binary_visit(v0, v1, std::forward<F>(f)))
+{
+ return V::binary_visit(v0, v1, std::forward<F>(f));
+}
+
+// getter interface
+
+#ifdef HAS_EXCEPTIONS
+template <typename ResultType, typename T>
+auto get(T& var)->decltype(var.template get<ResultType>())
+{
+ return var.template get<ResultType>();
+}
+#endif
+
+template <typename ResultType, typename T>
+ResultType& get_unchecked(T& var)
+{
+ return var.template get_unchecked<ResultType>();
+}
+
+#ifdef HAS_EXCEPTIONS
+template <typename ResultType, typename T>
+auto get(T const& var)->decltype(var.template get<ResultType>())
+{
+ return var.template get<ResultType>();
+}
+#endif
+
+template <typename ResultType, typename T>
+ResultType const& get_unchecked(T const& var)
+{
+ return var.template get_unchecked<ResultType>();
+}
+} // namespace util
+} // namespace mapbox
+
+// hashable iff underlying types are hashable
+namespace std {
+template <typename... Types>
+struct hash< ::mapbox::util::variant<Types...>> {
+ std::size_t operator()(const ::mapbox::util::variant<Types...>& v) const noexcept
+ {
+ return ::mapbox::util::apply_visitor(::mapbox::util::detail::hasher{}, v);
+ }
+};
+}
+
+#endif // MAPBOX_UTIL_VARIANT_HPP
diff --git a/include/mapbox/variant_io.hpp b/include/mapbox/variant_io.hpp
new file mode 100644
index 0000000..1456cc5
--- /dev/null
+++ b/include/mapbox/variant_io.hpp
@@ -0,0 +1,45 @@
+#ifndef MAPBOX_UTIL_VARIANT_IO_HPP
+#define MAPBOX_UTIL_VARIANT_IO_HPP
+
+#include <iosfwd>
+
+#include <mapbox/variant.hpp>
+
+namespace mapbox {
+namespace util {
+
+namespace detail {
+// operator<< helper
+template <typename Out>
+class printer
+{
+public:
+ explicit printer(Out& out)
+ : out_(out) {}
+ printer& operator=(printer const&) = delete;
+
+ // visitor
+ template <typename T>
+ void operator()(T const& operand) const
+ {
+ out_ << operand;
+ }
+
+private:
+ Out& out_;
+};
+}
+
+// operator<<
+template <typename CharT, typename Traits, typename... Types>
+VARIANT_INLINE std::basic_ostream<CharT, Traits>&
+operator<<(std::basic_ostream<CharT, Traits>& out, variant<Types...> const& rhs)
+{
+ detail::printer<std::basic_ostream<CharT, Traits>> visitor(out);
+ apply_visitor(visitor, rhs);
+ return out;
+}
+} // namespace util
+} // namespace mapbox
+
+#endif // MAPBOX_UTIL_VARIANT_IO_HPP
diff --git a/include/mapbox/variant_visitor.hpp b/include/mapbox/variant_visitor.hpp
new file mode 100644
index 0000000..481eb65
--- /dev/null
+++ b/include/mapbox/variant_visitor.hpp
@@ -0,0 +1,38 @@
+#ifndef MAPBOX_UTIL_VARIANT_VISITOR_HPP
+#define MAPBOX_UTIL_VARIANT_VISITOR_HPP
+
+namespace mapbox {
+namespace util {
+
+template <typename... Fns>
+struct visitor;
+
+template <typename Fn>
+struct visitor<Fn> : Fn
+{
+ using type = Fn;
+ using Fn::operator();
+
+ visitor(Fn fn) : Fn(fn) {}
+};
+
+template <typename Fn, typename... Fns>
+struct visitor<Fn, Fns...> : Fn, visitor<Fns...>
+{
+ using type = visitor;
+ using Fn::operator();
+ using visitor<Fns...>::operator();
+
+ visitor(Fn fn, Fns... fns) : Fn(fn), visitor<Fns...>(fns...) {}
+};
+
+template <typename... Fns>
+visitor<Fns...> make_visitor(Fns... fns)
+{
+ return visitor<Fns...>(fns...);
+}
+
+} // namespace util
+} // namespace mapbox
+
+#endif // MAPBOX_UTIL_VARIANT_VISITOR_HPP