online compiler and debugger for c/c++

#include <bitset> #include <cstdint> #include <cstdlib> #include <format> #include <numeric> #include <queue> #include <ranges> #include <vector> namespace OpenXcom { template <typename T> concept arithmetic = std::integral<T> || std::floating_point<T>; // Represents a point on the grid. template<arithmetic N> struct Point { N x, y; [[nodiscard]] constexpr Point operator+(Point other) const { return Point{ x + other.x, y + other.y }; } [[nodiscard]] constexpr Point operator-(Point other) const { return Point{ x - other.x, y - other.y }; } [[nodiscard]] constexpr bool operator==(const Point& other) const = default; [[nodiscard]] constexpr bool operator!=(const Point& other) const = default; static const Point CARDINAL_DIRECTIONS[4]; }; template<arithmetic N> constexpr Point<N> Point<N>::CARDINAL_DIRECTIONS[4] = { { -1, 0 }, { +1, 0 }, { 0, -1 }, { 0, +1 } }; // represents a width/height size template<arithmetic N> struct Size { N w, h; [[nodiscard]] constexpr bool operator==(const Size& other) const = default; [[nodiscard]] constexpr bool operator!=(const Size& other) const = default; [[nodiscard]] constexpr N getArea() { return w * h; } static const Size EMPTY; }; template<arithmetic N> constexpr Size<N> Size<N>::EMPTY = { 0 }; template<arithmetic N> [[nodiscard]] constexpr Point<N> operator+(Point<N> point, Size<N> size) { return Point{ point.x + size.w - 1, point.y + size.h - 1 }; } template<arithmetic N> [[nodiscard]] constexpr Point<N> operator+(Size<N> size, Point<N> point) { return point + size; } // represents a rectangular area on the grid template<arithmetic P, arithmetic S> struct Rectangle; // represents a min/max bounding box on a grid template<arithmetic N> struct Bounds { Point<N> min, max; [[nodiscard]] constexpr bool operator==(const Bounds<N>& other) const = default; [[nodiscard]] constexpr bool operator!=(const Bounds<N>& other) const = default; // gets the size for the area defined by this GridBounds [[nodiscard]] constexpr Size<N> size() const { return (min.x <= max.x && min.y <= max.y) ? Size<N>{ .w = max.x - min.x + 1, .h = max.y - min.y + 1 } : Size<N>{ .w = 0, .h = 0 }; } // checks if a point is in bounds or not [[nodiscard]] constexpr bool inBounds(const Point<N> point) const { return (point.x >= min.x && point.x <= max.x && point.y >= min.y && point.y <= max.y); } // checks if a bounds is fully inside the bounds [[nodiscard]] constexpr bool inBounds(const Bounds<N> bounds) const { return inBounds(bounds.min) && inBounds(bounds.max); } // checks if a rectangle is fully inside the bounds template<arithmetic S> [[nodiscard]] constexpr bool inBounds(const Rectangle<N, S> rectangle) const { return inBounds(rectangle.point) && inBounds(rectangle.point + rectangle.size); } template <typename T> constexpr void validateInBounds(const T& shape) const { if (!inBounds(shape)) { throw std::out_of_range(std::format("Argument {} out of bounds {}", shape, *this)); } } static const Bounds EMPTY; }; template<arithmetic N> constexpr Bounds<N> Bounds<N>::EMPTY = { 0 }; // represents a rectangular area on the grid template<arithmetic P, arithmetic S> struct RectangleBase { Point<P> point; Size<S> size; [[nodiscard]] constexpr bool operator==(const RectangleBase& other) const = default; [[nodiscard]] constexpr bool operator!=(const RectangleBase& other) const = default; [[nodiscard]] constexpr Bounds<P> getBounds() const { return { point, point + size }; } }; template<arithmetic P, arithmetic S> struct Rectangle : RectangleBase<P, S> {}; template<std::integral P, std::integral S> struct Rectangle<P, S> : RectangleBase<P, S> { using RectangleBase<P, S>::point; using RectangleBase<P, S>::size; [[nodiscard]] std::ranges::range auto getPoints() const { return std::views::iota(0, size.w * size.h) | std::views::transform([this](int index) { std::div_t result = std::div(index, size.w); return Point<P>{ point.x + result.rem, point.y + result.quot }; }); } }; using GridPoint = Point<int>; using GridSize = Size<int>; using GridBounds = Bounds<int>; using GridRectangle = Rectangle<int, int>; // Represents an occupied space on a grid. Immutable by design. template<size_t WIDTH, size_t HEIGHT> class GridSpace { public: static constexpr std::size_t AREA = WIDTH * HEIGHT; // Area of the grid space static constexpr GridSize GRID_SIZE = { WIDTH, HEIGHT }; // The size of ths grid. static constexpr GridBounds MAX_BOUNDS = { // Maximum bounds of the grid area. .min = GridPoint{.x = 0, .y = 0 }, .max = GridPoint{.x = WIDTH - 1, .y = HEIGHT - 1}, }; static const GridSpace EMPTY; private: std::bitset<AREA> _spaces; // Gets a GridPoint from an index [[nodiscard]] constexpr static GridPoint indexToPoint(size_t index) { std::div_t result = std::div(static_cast<int>(index), WIDTH); return GridPoint{ result.rem , result.quot }; } [[nodiscard]] constexpr static size_t pointToIndex(GridPoint point) { return static_cast<size_t>(point.y * WIDTH + point.x); } // Gets a GridSpace using prevalidated points. [[nodiscard]] constexpr static GridSpace fromValididPoints(std::ranges::input_range auto&& points) { GridSpace result = GridSpace::EMPTY; SetAdaptor adaptor = SetAdaptor{result}; std::ranges::copy(points, std::back_inserter(adaptor)); return result; } struct SetAdaptor { using value_type = GridPoint; void push_back(const GridPoint point) { _gridSpace.set(point, true); } GridSpace& _gridSpace; }; constexpr void setUnvalidated(GridPoint point, bool value) { _spaces[GridSpace::pointToIndex(point)] = value; } public: // Creates a new gridspace from an unsigned long. constexpr GridSpace(uint64_t space = 0) : _spaces(space) { } // Creates a new gridspace from a bitset. constexpr GridSpace(std::bitset<AREA> space) : _spaces(space) { } // Creates a new gridspace from a vector of coordiantes [[nodiscard]] constexpr static GridSpace fromPoints(std::ranges::input_range auto&& points) { GridSpace gridSpace = GridSpace::EMPTY; for (const GridPoint point : points) { MAX_BOUNDS.validateInBounds(point); gridSpace._spaces.set(static_cast<size_t>(point.y * WIDTH + point.x)); } return gridSpace; } // Creates a new gridspace from a rectangle. [[nodiscard]] constexpr static GridSpace fromRectangle(GridPoint point, GridSize size) { return GridSpace::fromRectangle(GridRectangle{ point, size }); } [[nodiscard]] constexpr static GridSpace fromRectangle(GridRectangle rectangle) { return MAX_BOUNDS.inBounds(rectangle) && rectangle.size != GridSize::EMPTY ? GridSpace::fromValididPoints(rectangle.getPoints()) : throw std::invalid_argument(std::format("Argument {} out of bounds {}", rectangle, MAX_BOUNDS)); } // gets the value of the space at a point. [[nodiscard]] constexpr bool operator[](GridPoint point) const { MAX_BOUNDS.validateInBounds(point); return _spaces[GridSpace::pointToIndex(point)]; } // sets the value of the space at a point. constexpr void set(GridPoint point, bool value) { MAX_BOUNDS.validateInBounds(point); _spaces[GridSpace::pointToIndex(point)] = value; } [[nodiscard]] constexpr const std::bitset<AREA>& getSpaces() const { return _spaces; } // gets if any grid space is occupied. [[nodiscard]] constexpr bool any() const { return _spaces.any(); } // Gets the minimum GridBounds that can contains all occupied spaces in this grid. [[nodiscard]] constexpr GridBounds getOccupiedSpaceBounds() const { if (_spaces.none()) { return GridBounds::EMPTY; } auto occupiedPoints = getOccupiedPoints(); return std::accumulate(occupiedPoints.begin(), occupiedPoints.end(), GridSpace::MAX_BOUNDS, [](GridBounds bounds, GridPoint point) { bounds.min.x = std::min(bounds.min.x, point.x); bounds.min.y = std::min(bounds.min.y, point.y); bounds.max.x = std::max(bounds.max.x, point.x); bounds.max.y = std::max(bounds.max.y, point.y); return bounds; }); } // Gets a range of the occupied grid coordinates. [[nodiscard]] constexpr std::ranges::range auto getOccupiedPoints() const { return std::views::iota(size_t{ 0 }, AREA) | std::views::filter([&](size_t index) { return _spaces[index]; }) | std::views::transform(indexToPoint); } /** * @brief Gets the area that is connected to point in a cardinal direction. * @param point the point to check for connectivity with. * @return A GridSpace that represents the connected area. */ [[nodiscard]] constexpr GridSpace getConnectedSpace(GridPoint point) const { GridSpace visitedSpaces(0); auto isInside = [&](const GridPoint point) { return MAX_BOUNDS.inBounds(point) && (*this)[point] && !visitedSpaces[point]; }; if (!isInside(point)) { return visitedSpaces; } // early return allows the implementation logic to not worry about the out of bounds case. // standard floodfill algo std::vector<GridPoint> gridStack; gridStack.push_back(point); do { GridPoint backPoint = gridStack.back(); gridStack.pop_back(); visitedSpaces = visitedSpaces | backPoint; // filtering before we push the point saves on stack size auto addDirection = [&backPoint](const GridPoint direction) { return backPoint + direction; }; auto newPoints = GridPoint::CARDINAL_DIRECTIONS | std::views::transform(addDirection) | std::views::filter(isInside); std::ranges::copy(newPoints, std::back_inserter(gridStack)); } while (!gridStack.empty()); return visitedSpaces; } // Ands two GridSpaces together [[nodiscard]] constexpr GridSpace operator&(const GridSpace& other) const { return GridSpace(_spaces & other._spaces); } // Ors two GridSpaces together [[nodiscard]] constexpr GridSpace operator|(const GridSpace& other) const { return GridSpace(_spaces | other._spaces); } // Xors two GridSpaces together [[nodiscard]] constexpr GridSpace operator^(const GridSpace& other) const { return GridSpace(_spaces ^ other._spaces); } // flattens the given grid spaces via an OR merge [[nodiscard]] constexpr static GridSpace flatten(std::ranges::view auto& gridSpaces) { return std::accumulate(gridSpaces.begin(), gridSpaces.end(), GridSpace(0), std::bit_or<>()); } // Ors a GridSpace with a point. [[nodiscard]] constexpr GridSpace operator|(const GridPoint point) const { MAX_BOUNDS.validateInBounds(point); GridSpace result = *this; result._spaces.set(static_cast<size_t>(point.y * WIDTH + point.x)); return result; } }; template<size_t WIDTH, size_t HEIGHT> constexpr GridSpace<WIDTH, HEIGHT> GridSpace<WIDTH, HEIGHT>::EMPTY = { 0 }; using BaseGrid = GridSpace<6, 6>; } template <> struct std::formatter<OpenXcom::GridPoint> : std::formatter<std::string_view> { auto format(const OpenXcom::GridPoint point, std::format_context& ctx) const { return std::format_to(ctx.out(), "(x:{}, y:{})", point.x, point.y); } }; template <> struct std::formatter<OpenXcom::GridSize> : std::formatter<std::string_view> { auto format(const OpenXcom::GridSize size, std::format_context& ctx) const { return std::format_to(ctx.out(), "(w:{}, h:{})", size.w, size.h); } }; template <> struct std::formatter<OpenXcom::GridBounds> : std::formatter<std::string_view> { auto format(const OpenXcom::GridBounds bounds, std::format_context& ctx) const { return std::format_to(ctx.out(), "(min:{}, max:{})", bounds.min, bounds.max); } }; template <> struct std::formatter<OpenXcom::GridRectangle> : std::formatter<std::string_view> { auto format(const OpenXcom::GridRectangle rectangle, std::format_context& ctx) const { return std::format_to(ctx.out(), "(point:{}, size:{})", rectangle.point, rectangle.size); } }; template <size_t WIDTH, size_t HEIGHT> struct std::formatter<OpenXcom::GridSpace<WIDTH, HEIGHT>> : std::formatter<string_view> { auto format(const OpenXcom::GridSpace<WIDTH, HEIGHT>& gridSpace, std::format_context& ctx) const { std::format_to(ctx.out(), "GridSpace:{}\n", OpenXcom::GridSpace<WIDTH, HEIGHT>::GRID_SIZE); const auto& bitset = gridSpace.getSpaces(); for (size_t i = 0; i < bitset.size(); ++i) { std::format_to(ctx.out(), "{}", bitset[i] ? '1' : '0'); if ((i + 1) % WIDTH == 0) { std::format_to(ctx.out(), "\n"); } } return ctx.out(); } };