diff options
author | 2018-11-02 14:13:07 +0900 | |
---|---|---|
committer | 2018-11-02 14:13:07 +0900 | |
commit | 30d24cbc67ef416672a3386b10be8fe6711c65d7 (patch) | |
tree | ecc8813e6742661e1521d6399d04cc4abc54587f /include/mapbox | |
parent | ae47635e56c4af4d816a76e5186e945768543679 (diff) |
use mapbox as navigation
Diffstat (limited to 'include/mapbox')
-rw-r--r-- | include/mapbox/cheap_ruler.hpp | 358 | ||||
-rw-r--r-- | include/mapbox/geometry.hpp | 13 | ||||
-rw-r--r-- | include/mapbox/geometry/box.hpp | 34 | ||||
-rw-r--r-- | include/mapbox/geometry/envelope.hpp | 33 | ||||
-rw-r--r-- | include/mapbox/geometry/feature.hpp | 81 | ||||
-rw-r--r-- | include/mapbox/geometry/for_each_point.hpp | 45 | ||||
-rw-r--r-- | include/mapbox/geometry/geometry.hpp | 53 | ||||
-rw-r--r-- | include/mapbox/geometry/line_string.hpp | 21 | ||||
-rw-r--r-- | include/mapbox/geometry/multi_line_string.hpp | 21 | ||||
-rw-r--r-- | include/mapbox/geometry/multi_point.hpp | 21 | ||||
-rw-r--r-- | include/mapbox/geometry/multi_polygon.hpp | 21 | ||||
-rw-r--r-- | include/mapbox/geometry/point.hpp | 35 | ||||
-rw-r--r-- | include/mapbox/geometry/point_arithmetic.hpp | 119 | ||||
-rw-r--r-- | include/mapbox/geometry/polygon.hpp | 31 | ||||
-rw-r--r-- | include/mapbox/optional.hpp | 74 | ||||
-rw-r--r-- | include/mapbox/recursive_wrapper.hpp | 122 | ||||
-rw-r--r-- | include/mapbox/variant.hpp | 1013 | ||||
-rw-r--r-- | include/mapbox/variant_io.hpp | 45 | ||||
-rw-r--r-- | include/mapbox/variant_visitor.hpp | 38 |
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 |