From 36be1ed32ac9a554f0b11fcc13b5699e717b81f2 Mon Sep 17 00:00:00 2001 From: jbzdarkid Date: Sat, 9 Nov 2019 13:39:10 -0800 Subject: Functioning solver/validator (at least for mazes) --- Source/Panel.cpp | 387 - Source/Panel.h | 96 - Source/Puzzle.cpp | 402 + Source/Puzzle.h | 142 + Source/Solver.cpp | 76 + Source/Solver.h | 16 + Source/Source.vcxproj | 9 +- Source/Validator.cpp | 97 + Source/Validator.h | 27 + Source/json.hpp | 20274 ------------------------------------------------ 10 files changed, 766 insertions(+), 20760 deletions(-) delete mode 100644 Source/Panel.cpp delete mode 100644 Source/Panel.h create mode 100644 Source/Puzzle.cpp create mode 100644 Source/Puzzle.h create mode 100644 Source/Solver.cpp create mode 100644 Source/Solver.h create mode 100644 Source/Validator.cpp create mode 100644 Source/Validator.h delete mode 100644 Source/json.hpp (limited to 'Source') diff --git a/Source/Panel.cpp b/Source/Panel.cpp deleted file mode 100644 index b204a28..0000000 --- a/Source/Panel.cpp +++ /dev/null @@ -1,387 +0,0 @@ -#include "Panel.h" -#include "Memory.h" - -#pragma warning (disable:26451) -#pragma warning (disable:26812) - -PuzzleSerializer::PuzzleSerializer(const std::shared_ptr& memory) : _memory(memory) {} - -Puzzle PuzzleSerializer::ReadPuzzle(int id) { - Puzzle p; - p.width = 2 * _memory->ReadPanelData(id, GRID_SIZE_X, 1)[0] - 1; - p.height = 2 * _memory->ReadPanelData(id, GRID_SIZE_Y, 1)[0] - 1; - if (p.width < 0 || p.height < 0) return p; // @Error: Grid size should be always positive? Looks like the starting panels break this rule, though. - p.grid.resize(p.width); - for (auto& row : p.grid) row.resize(p.height); - - ReadIntersections(p, id); - ReadDecorations(p, id); - - return p; -} - -void PuzzleSerializer::ReadIntersections(Puzzle& p, int id) { - int numIntersections = _memory->ReadPanelData(id, NUM_DOTS, 1)[0]; - std::vector intersectionFlags = _memory->ReadArray(id, DOT_FLAGS, numIntersections); - int numConnections = _memory->ReadPanelData(id, NUM_CONNECTIONS, 1)[0]; - std::vector connections_a = _memory->ReadArray(id, DOT_CONNECTION_A, numConnections); - std::vector connections_b = _memory->ReadArray(id, DOT_CONNECTION_B, numConnections); - std::vector intersectionLocations = _memory->ReadArray(id, DOT_POSITIONS, numIntersections*2); - - // @Cleanup: Change defaults? - for (int x=0; x x2) x--; - else if (y1 < y2) y--; - else if (y1 > y2) y++; - p.grid[x][y].gap = Cell::Gap::NONE; - } - - // This iterates bottom-top, left-right - int i = 0; - for (;; i++) { - int flags = intersectionFlags[i]; - auto [x, y] = loc_to_xy(p, i); - if (y < 0) break; - if (flags & Flags::IS_STARTPOINT) { - p.grid[x][y].start = true; - } - p.grid[x][y].dot = FlagsToDot(flags); - if (flags & Flags::IS_FULL_GAP) { - p.grid[x][y].gap = Cell::Gap::FULL; - } - } - - // Iterate the remaining intersections (endpoints, dots, gaps) - for (; i < numIntersections; i++) { - int location = FindConnection(i, connections_a, connections_b); - if (location == -1) continue; // @Error: Unable to find connection point - // (x1, y1) location of this intersection - // (x2, y2) location of the connected intersection - float x1 = intersectionLocations[2*i]; - float y1 = intersectionLocations[2*i+1]; - float x2 = intersectionLocations[2*location]; - float y2 = intersectionLocations[2*location+1]; - auto [x, y] = loc_to_xy(p, location); - - if (intersectionFlags[i] & Flags::IS_ENDPOINT) { - // Our x coordinate is less than the target's - if (x1 < x2) p.grid[x][y].end = Cell::Dir::LEFT; - else if (x1 > x2) p.grid[x][y].end = Cell::Dir::RIGHT; - // Note that Y coordinates are reversed: 0.0 (bottom) 1.0 (top) - else if (y1 < y2) p.grid[x][y].end = Cell::Dir::DOWN; - else if (y1 > y2) p.grid[x][y].end = Cell::Dir::UP; - } else if (intersectionFlags[i] & Flags::HAS_DOT) { - if (x1 < x2) x--; - else if (x1 > x2) x++; - else if (y1 < y2) y++; - else if (y1 > y2) y--; - p.grid[x][y].dot = FlagsToDot(intersectionFlags[i]); - } else if (intersectionFlags[i] & Flags::HAS_NO_CONN) { - if (x1 < x2) x--; - else if (x1 > x2) x++; - else if (y1 < y2) y++; - else if (y1 > y2) y--; - p.grid[x][y].gap = Cell::Gap::BREAK; - } - } -} - -void PuzzleSerializer::ReadDecorations(Puzzle& p, int id) { - int numDecorations = _memory->ReadPanelData(id, NUM_DECORATIONS, 1)[0]; - std::vector decorations = _memory->ReadArray(id, DECORATIONS, numDecorations); - if (numDecorations > 0) p.hasDecorations = true; - - for (int i=0; i(); - p.grid[x][y].decoration = d; - d->type = static_cast(decorations[i] & 0xFF00); - switch(d->type) { - case Shape::Poly: - case Shape::RPoly: - case Shape::Ylop: - d->polyshape = decorations[i] & 0xFFFF0000; - break; - case Shape::Triangle: - d->count = decorations[i] & 0x000F0000; - break; - } - d->color = static_cast(decorations[i] & 0xF); - } -} - -void PuzzleSerializer::WritePuzzle(const Puzzle& p, int id) { - _memory->WritePanelData(id, GRID_SIZE_X, {(p.width + 1)/2}); - _memory->WritePanelData(id, GRID_SIZE_Y, {(p.height + 1)/2}); - - WriteIntersections(p, id); - if (p.hasDecorations) WriteDecorations(p, id); - - _memory->WritePanelData(id, NEEDS_REDRAW, {1}); -} - -void PuzzleSerializer::WriteIntersections(const Puzzle& p, int id) { - std::vector intersectionLocations; - std::vector intersectionFlags; - std::vector connections_a; - std::vector connections_b; - - float min = 0.1f; - float max = 0.9f; - float width_interval = (max - min) / (p.width/2); - float height_interval = (max - min) / (p.height/2); - float horiz_gap_size = width_interval / 2; - float verti_gap_size = height_interval / 2; - - // TODO: Compute HAS_NO_CONN / HAS_HORIZ_CONN / HAS_VERTI_CONN in this loop. - // @Cleanup: If I write directly to locations, then I can simplify this gross loop iterator. - // int numIntersections = (p.width / 2 + 1) * (p.height / 2 + 1); - // Grided intersections - for (int y=p.height-1; y>=0; y-=2) { - for (int x=0; x 0 && p.grid[x][y-1].gap == Cell::Gap::NONE) { - connections_a.push_back(xy_to_loc(p, x, y-2)); - connections_b.push_back(xy_to_loc(p, x, y)); - } - // Left connection - if (x > 0 && p.grid[x-1][y].gap == Cell::Gap::NONE) { - connections_a.push_back(xy_to_loc(p, x-2, y)); - connections_b.push_back(xy_to_loc(p, x, y)); - } - } - } - - // Endpoints - for (int x=0; x(intersectionFlags.size())); // This endpoint - - float xPos = min + (x/2) * width_interval; - float yPos = max - (y/2) * height_interval; - switch (p.grid[x][y].end) { - case Cell::Dir::LEFT: - xPos -= .05f; - break; - case Cell::Dir::RIGHT: - xPos += .05f; - break; - case Cell::Dir::UP: - yPos += .05f; // Y position goes from 0 (bottom) to 1 (top), so this is reversed. - break; - case Cell::Dir::DOWN: - yPos -= .05f; - break; - } - intersectionLocations.push_back(xPos); - intersectionLocations.push_back(yPos); - intersectionFlags.push_back(Flags::IS_ENDPOINT); - } - } - - // Dots - for (int x=0; x(intersectionFlags.size()); // This endpoint - - connections_a.push_back(other_connection); - connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint - break; - } - } - // Add this dot to the end - float xPos = min + (x/2.0f) * width_interval; - float yPos = max - (y/2.0f) * height_interval; - intersectionLocations.push_back(xPos); - intersectionLocations.push_back(yPos); - - int flags = Flags::HAS_DOT; - switch (p.grid[x][y].dot) { - case Cell::Dot::BLACK: - break; - case Cell::Dot::BLUE: - flags |= DOT_IS_BLUE; - break; - case Cell::Dot::YELLOW: - flags |= DOT_IS_ORANGE; - break; - case Cell::Dot::INVISIBLE: - flags |= DOT_IS_INVISIBLE; - break; - } - intersectionFlags.push_back(flags); - } - } - - // Gaps - for (int x=0; x(intersectionFlags.size())); // This endpoint - intersectionLocations.push_back(xPos); - intersectionLocations.push_back(yPos + verti_gap_size / 2); - intersectionFlags.push_back(Flags::HAS_NO_CONN | Flags::HAS_VERTI_CONN); - - connections_a.push_back(xy_to_loc(p, x, y+1)); - connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint - intersectionLocations.push_back(xPos); - intersectionLocations.push_back(yPos - verti_gap_size / 2); - intersectionFlags.push_back(Flags::HAS_NO_CONN | Flags::HAS_VERTI_CONN); - } else if (y%2 == 0) { // Horizontal gap - connections_a.push_back(xy_to_loc(p, x-1, y)); - connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint - intersectionLocations.push_back(xPos - horiz_gap_size / 2); - intersectionLocations.push_back(yPos); - intersectionFlags.push_back(Flags::HAS_NO_CONN | Flags::HAS_HORIZ_CONN); - - connections_a.push_back(xy_to_loc(p, x+1, y)); - connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint - intersectionLocations.push_back(xPos + horiz_gap_size / 2); - intersectionLocations.push_back(yPos); - intersectionFlags.push_back(Flags::HAS_NO_CONN | Flags::HAS_HORIZ_CONN); - } - } - } - - _memory->WritePanelData(id, NUM_DOTS, {static_cast(intersectionFlags.size())}); - _memory->WriteArray(id, DOT_POSITIONS, intersectionLocations); - _memory->WriteArray(id, DOT_FLAGS, intersectionFlags); - _memory->WritePanelData(id, NUM_CONNECTIONS, {static_cast(connections_a.size())}); - _memory->WriteArray(id, DOT_CONNECTION_A, connections_a); - _memory->WriteArray(id, DOT_CONNECTION_B, connections_b); -} - -void PuzzleSerializer::WriteDecorations(const Puzzle& p, int id) { - std::vector decorations; - for (int y=p.height-2; y>0; y-=2) { - for (int x=1; xcolor | d->type | d->count | d->polyshape); - } else { - decorations.push_back(0); - } - } - } - - _memory->WritePanelData(id, NUM_DECORATIONS, {static_cast(decorations.size())}); - _memory->WriteArray(id, DECORATIONS, decorations); -} - -std::tuple PuzzleSerializer::loc_to_xy(const Puzzle& p, int location) const { - int height2 = (p.height - 1) / 2; - int width2 = (p.width + 1) / 2; - - int x = 2 * (location % width2); - int y = 2 * (height2 - location / width2); - return {x, y}; -} - -int PuzzleSerializer::xy_to_loc(const Puzzle& p, int x, int y) const { - int height2 = (p.height - 1) / 2; - int width2 = (p.width + 1) / 2; - - int rowsFromBottom = height2 - y/2; - return rowsFromBottom * width2 + x/2; -} - -std::tuple PuzzleSerializer::dloc_to_xy(const Puzzle& p, int location) const { - int height2 = (p.height - 3) / 2; - int width2 = (p.width - 1) / 2; - - int x = 2 * (location % width2) + 1; - int y = 2 * (height2 - location / width2) + 1; - return {x, y}; -} - -int PuzzleSerializer::xy_to_dloc(const Puzzle& p, int x, int y) const { - int height2 = (p.height - 3) / 2; - int width2 = (p.width - 1) / 2; - - int rowsFromBottom = height2 - (y - 1)/2; - return rowsFromBottom * width2 + (x - 1)/2; -} - -Cell::Dot PuzzleSerializer::FlagsToDot(int flags) const { - if (!(flags & Flags::HAS_DOT)) return Cell::Dot::NONE; - if (flags & Flags::DOT_IS_BLUE) { - return Cell::Dot::BLUE; - } else if (flags & Flags::DOT_IS_ORANGE) { - return Cell::Dot::YELLOW; - } else if (flags & Flags::DOT_IS_INVISIBLE) { - return Cell::Dot::INVISIBLE; - } else { - return Cell::Dot::BLACK; - } -} - -int PuzzleSerializer::FindConnection(int i, const std::vector& connections_a, const std::vector& connections_b) const { - for (int j=0; j -#include - -class Memory; - -enum Shape { - Stone = 0x100, - Star = 0x200, - Poly = 0x400, - Eraser = 0x500, - Triangle = 0x600, - RPoly = 0x1000, - Ylop = 0x2000, -}; - -enum Color { - Black = 0x1, - White = 0x2, - Gray = 0x3, - Purple = 0x4, - Green = 0x5, - Cyan = 0x6, - Pink = 0x7, - Yellow = 0x8, - Blue = 0x9, - Orange = 0xA, -}; - -struct Decoration { - Shape type; - Color color; - int polyshape = 0; - // For triangles only - int count = 0; -}; - -struct Cell { - bool start = false; - enum class Dir {NONE, LEFT, RIGHT, UP, DOWN}; - Dir end = Dir::NONE; - std::shared_ptr decoration = nullptr; - enum class Dot {NONE, BLACK, BLUE, YELLOW, INVISIBLE}; - Dot dot = Dot::NONE; - enum class Gap {NONE, BREAK, FULL}; - Gap gap = Gap::NONE; -}; - -struct Puzzle { - int16_t height; - int16_t width; - bool hasDecorations = false; - std::vector> grid; - - enum class Symmetry {NONE, X, Y, XY}; - Symmetry sym = Symmetry::NONE; - bool pillar = false; -}; - -class PuzzleSerializer { -public: - PuzzleSerializer(const std::shared_ptr& memory); - Puzzle ReadPuzzle(int id); - void WritePuzzle(const Puzzle& p, int id); - -private: - // @Bug: Blue and orange are swapped? - enum Flags { - IS_ENDPOINT = 0x1, - IS_STARTPOINT = 0x2, - IS_FULL_GAP = 0x8, - HAS_DOT = 0x20, - DOT_IS_BLUE = 0x100, - DOT_IS_ORANGE = 0x200, - DOT_IS_INVISIBLE = 0x1000, - HAS_NO_CONN = 0x100000, - HAS_VERTI_CONN = 0x200000, - HAS_HORIZ_CONN = 0x400000, - }; - - void ReadIntersections(Puzzle& p, int id); - void ReadDecorations(Puzzle& p, int id); - void WriteIntersections(const Puzzle& p, int id); - void WriteDecorations(const Puzzle& p, int id); - - std::tuple loc_to_xy(const Puzzle& p, int location) const; - int xy_to_loc(const Puzzle& p, int x, int y) const; - // Decoration location - std::tuple dloc_to_xy(const Puzzle& p, int location) const; - int xy_to_dloc(const Puzzle& p, int x, int y) const; - Cell::Dot FlagsToDot(int flags) const; - // Iterate connection lists for another location which is connected to us; return that other location. - int FindConnection(int i, const std::vector& connections_a, const std::vector& connections_b) const; - - std::shared_ptr _memory; -}; diff --git a/Source/Puzzle.cpp b/Source/Puzzle.cpp new file mode 100644 index 0000000..ee4c2e8 --- /dev/null +++ b/Source/Puzzle.cpp @@ -0,0 +1,402 @@ +#include "Puzzle.h" +#include "Memory.h" + +#pragma warning (disable:26451) +#pragma warning (disable:26812) + +PuzzleSerializer::PuzzleSerializer(const std::shared_ptr& memory) : _memory(memory) {} + +Puzzle PuzzleSerializer::ReadPuzzle(int id) { + Puzzle p; + p.width = 2 * _memory->ReadPanelData(id, GRID_SIZE_X, 1)[0] - 1; + p.height = 2 * _memory->ReadPanelData(id, GRID_SIZE_Y, 1)[0] - 1; + if (p.width < 0 || p.height < 0) return p; // @Error: Grid size should be always positive? Looks like the starting panels break this rule, though. + p.grid.resize(p.width); + for (auto& row : p.grid) row.resize(p.height); + + ReadIntersections(p, id); + ReadDecorations(p, id); + + return p; +} + +void PuzzleSerializer::ReadIntersections(Puzzle& p, int id) { + int numIntersections = _memory->ReadPanelData(id, NUM_DOTS, 1)[0]; + std::vector intersectionFlags = _memory->ReadArray(id, DOT_FLAGS, numIntersections); + int numConnections = _memory->ReadPanelData(id, NUM_CONNECTIONS, 1)[0]; + std::vector connections_a = _memory->ReadArray(id, DOT_CONNECTION_A, numConnections); + std::vector connections_b = _memory->ReadArray(id, DOT_CONNECTION_B, numConnections); + std::vector intersectionLocations = _memory->ReadArray(id, DOT_POSITIONS, numIntersections*2); + + // @Cleanup: Change defaults? + for (int x=0; x x2) x--; + else if (y1 < y2) y--; + else if (y1 > y2) y++; + p.grid[x][y].gap = Cell::Gap::NONE; + } + + // This iterates bottom-top, left-right + int i = 0; + for (;; i++) { + int flags = intersectionFlags[i]; + auto [x, y] = loc_to_xy(p, i); + if (y < 0) break; + if (flags & Flags::IS_STARTPOINT) { + p.grid[x][y].start = true; + } + p.grid[x][y].dot = FlagsToDot(flags); + if (flags & Flags::IS_FULL_GAP) { + p.grid[x][y].gap = Cell::Gap::FULL; + } + } + + // Iterate the remaining intersections (endpoints, dots, gaps) + for (; i < numIntersections; i++) { + int location = FindConnection(i, connections_a, connections_b); + if (location == -1) continue; // @Error: Unable to find connection point + // (x1, y1) location of this intersection + // (x2, y2) location of the connected intersection + float x1 = intersectionLocations[2*i]; + float y1 = intersectionLocations[2*i+1]; + float x2 = intersectionLocations[2*location]; + float y2 = intersectionLocations[2*location+1]; + auto [x, y] = loc_to_xy(p, location); + + if (intersectionFlags[i] & Flags::IS_ENDPOINT) { + // Our x coordinate is less than the target's + if (x1 < x2) p.grid[x][y].end = Cell::Dir::LEFT; + else if (x1 > x2) p.grid[x][y].end = Cell::Dir::RIGHT; + // Note that Y coordinates are reversed: 0.0 (bottom) 1.0 (top) + else if (y1 < y2) p.grid[x][y].end = Cell::Dir::DOWN; + else if (y1 > y2) p.grid[x][y].end = Cell::Dir::UP; + } else if (intersectionFlags[i] & Flags::HAS_DOT) { + if (x1 < x2) x--; + else if (x1 > x2) x++; + else if (y1 < y2) y++; + else if (y1 > y2) y--; + p.grid[x][y].dot = FlagsToDot(intersectionFlags[i]); + } else if (intersectionFlags[i] & Flags::HAS_ONE_CONN) { + if (x1 < x2) x--; + else if (x1 > x2) x++; + else if (y1 < y2) y++; + else if (y1 > y2) y--; + p.grid[x][y].gap = Cell::Gap::BREAK; + } + } +} + +void PuzzleSerializer::ReadDecorations(Puzzle& p, int id) { + int numDecorations = _memory->ReadPanelData(id, NUM_DECORATIONS, 1)[0]; + std::vector decorations = _memory->ReadArray(id, DECORATIONS, numDecorations); + if (numDecorations > 0) p.hasDecorations = true; + + for (int i=0; i(); + p.grid[x][y].decoration = d; + d->type = static_cast(decorations[i] & 0xFF00); + switch(d->type) { + case Type::Poly: + case Type::RPoly: + case Type::Ylop: + d->polyshape = decorations[i] & 0xFFFF0000; + break; + case Type::Triangle: + d->count = decorations[i] & 0x000F0000; + break; + } + d->color = static_cast(decorations[i] & 0xF); + } +} + +void PuzzleSerializer::WritePuzzle(const Puzzle& p, int id) { + _memory->WritePanelData(id, GRID_SIZE_X, {(p.width + 1)/2}); + _memory->WritePanelData(id, GRID_SIZE_Y, {(p.height + 1)/2}); + + WriteIntersections(p, id); + if (p.hasDecorations) WriteDecorations(p, id); + + _memory->WritePanelData(id, NEEDS_REDRAW, {1}); +} + +void PuzzleSerializer::WriteIntersections(const Puzzle& p, int id) { + std::vector intersectionLocations; + std::vector intersectionFlags; + std::vector connections_a; + std::vector connections_b; + + float min = 0.1f; + float max = 0.9f; + float width_interval = (max - min) / (p.width/2); + float height_interval = (max - min) / (p.height/2); + float horiz_gap_size = width_interval / 2; + float verti_gap_size = height_interval / 2; + + // @Cleanup: If I write directly to locations, then I can simplify this gross loop iterator. + // int numIntersections = (p.width / 2 + 1) * (p.height / 2 + 1); + // Grided intersections + for (int y=p.height-1; y>=0; y-=2) { + for (int x=0; x 0 && p.grid[x][y-1].gap == Cell::Gap::NONE) { + connections_a.push_back(xy_to_loc(p, x, y-2)); + connections_b.push_back(xy_to_loc(p, x, y)); + flags |= Flags::HAS_VERTI_CONN; + numConnections++; + } + // Top connection + if (y < p.height - 1 && p.grid[x][y+1].gap == Cell::Gap::NONE) { + flags |= Flags::HAS_VERTI_CONN; + numConnections++; + } + // Left connection + if (x > 0 && p.grid[x-1][y].gap == Cell::Gap::NONE) { + connections_a.push_back(xy_to_loc(p, x-2, y)); + connections_b.push_back(xy_to_loc(p, x, y)); + flags |= Flags::HAS_HORIZ_CONN; + numConnections++; + } + // Right connection + if (x < p.width - 1 && p.grid[x+1][y].gap == Cell::Gap::NONE) { + flags |= Flags::HAS_HORIZ_CONN; + numConnections++; + } + if (numConnections == 1) flags |= HAS_ONE_CONN; + intersectionFlags.push_back(flags); + } + } + + // Endpoints + for (int x=0; x(intersectionFlags.size())); // This endpoint + + float xPos = min + (x/2) * width_interval; + float yPos = max - (y/2) * height_interval; + switch (p.grid[x][y].end) { + case Cell::Dir::LEFT: + xPos -= .05f; + break; + case Cell::Dir::RIGHT: + xPos += .05f; + break; + case Cell::Dir::UP: + yPos += .05f; // Y position goes from 0 (bottom) to 1 (top), so this is reversed. + break; + case Cell::Dir::DOWN: + yPos -= .05f; + break; + } + intersectionLocations.push_back(xPos); + intersectionLocations.push_back(yPos); + intersectionFlags.push_back(Flags::IS_ENDPOINT); + } + } + + // Dots + for (int x=0; x(intersectionFlags.size()); // This endpoint + + connections_a.push_back(other_connection); + connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint + break; + } + } + // Add this dot to the end + float xPos = min + (x/2.0f) * width_interval; + float yPos = max - (y/2.0f) * height_interval; + intersectionLocations.push_back(xPos); + intersectionLocations.push_back(yPos); + + int flags = Flags::HAS_DOT; + switch (p.grid[x][y].dot) { + case Cell::Dot::BLACK: + break; + case Cell::Dot::BLUE: + flags |= DOT_IS_BLUE; + break; + case Cell::Dot::YELLOW: + flags |= DOT_IS_ORANGE; + break; + case Cell::Dot::INVISIBLE: + flags |= DOT_IS_INVISIBLE; + break; + } + intersectionFlags.push_back(flags); + } + } + + // Gaps + for (int x=0; x(intersectionFlags.size())); // This endpoint + intersectionLocations.push_back(xPos); + intersectionLocations.push_back(yPos + verti_gap_size / 2); + intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_VERTI_CONN); + + connections_a.push_back(xy_to_loc(p, x, y+1)); + connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint + intersectionLocations.push_back(xPos); + intersectionLocations.push_back(yPos - verti_gap_size / 2); + intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_VERTI_CONN); + } else if (y%2 == 0) { // Horizontal gap + connections_a.push_back(xy_to_loc(p, x-1, y)); + connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint + intersectionLocations.push_back(xPos - horiz_gap_size / 2); + intersectionLocations.push_back(yPos); + intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_HORIZ_CONN); + + connections_a.push_back(xy_to_loc(p, x+1, y)); + connections_b.push_back(static_cast(intersectionFlags.size())); // This endpoint + intersectionLocations.push_back(xPos + horiz_gap_size / 2); + intersectionLocations.push_back(yPos); + intersectionFlags.push_back(Flags::HAS_ONE_CONN | Flags::HAS_HORIZ_CONN); + } + } + } + + _memory->WritePanelData(id, NUM_DOTS, {static_cast(intersectionFlags.size())}); + _memory->WriteArray(id, DOT_POSITIONS, intersectionLocations); + _memory->WriteArray(id, DOT_FLAGS, intersectionFlags); + _memory->WritePanelData(id, NUM_CONNECTIONS, {static_cast(connections_a.size())}); + _memory->WriteArray(id, DOT_CONNECTION_A, connections_a); + _memory->WriteArray(id, DOT_CONNECTION_B, connections_b); +} + +void PuzzleSerializer::WriteDecorations(const Puzzle& p, int id) { + std::vector decorations; + for (int y=p.height-2; y>0; y-=2) { + for (int x=1; xcolor | d->type | d->count | d->polyshape); + } else { + decorations.push_back(0); + } + } + } + + _memory->WritePanelData(id, NUM_DECORATIONS, {static_cast(decorations.size())}); + _memory->WriteArray(id, DECORATIONS, decorations); +} + +std::tuple PuzzleSerializer::loc_to_xy(const Puzzle& p, int location) const { + int height2 = (p.height - 1) / 2; + int width2 = (p.width + 1) / 2; + + int x = 2 * (location % width2); + int y = 2 * (height2 - location / width2); + return {x, y}; +} + +int PuzzleSerializer::xy_to_loc(const Puzzle& p, int x, int y) const { + int height2 = (p.height - 1) / 2; + int width2 = (p.width + 1) / 2; + + int rowsFromBottom = height2 - y/2; + return rowsFromBottom * width2 + x/2; +} + +std::tuple PuzzleSerializer::dloc_to_xy(const Puzzle& p, int location) const { + int height2 = (p.height - 3) / 2; + int width2 = (p.width - 1) / 2; + + int x = 2 * (location % width2) + 1; + int y = 2 * (height2 - location / width2) + 1; + return {x, y}; +} + +int PuzzleSerializer::xy_to_dloc(const Puzzle& p, int x, int y) const { + int height2 = (p.height - 3) / 2; + int width2 = (p.width - 1) / 2; + + int rowsFromBottom = height2 - (y - 1)/2; + return rowsFromBottom * width2 + (x - 1)/2; +} + +Cell::Dot PuzzleSerializer::FlagsToDot(int flags) const { + if (!(flags & Flags::HAS_DOT)) return Cell::Dot::NONE; + if (flags & Flags::DOT_IS_BLUE) { + return Cell::Dot::BLUE; + } else if (flags & Flags::DOT_IS_ORANGE) { + return Cell::Dot::YELLOW; + } else if (flags & Flags::DOT_IS_INVISIBLE) { + return Cell::Dot::INVISIBLE; + } else { + return Cell::Dot::BLACK; + } +} + +int PuzzleSerializer::FindConnection(int i, const std::vector& connections_a, const std::vector& connections_b) const { + for (int j=0; j +#include + +class Memory; + +enum Type { + Stone = 0x100, + Square = Stone, // @Deprecated + Star = 0x200, + Poly = 0x400, + Eraser = 0x500, + Nega = Eraser, // @Deprecated + Triangle = 0x600, + RPoly = 0x1000, // @Cleanup! + Ylop = 0x2000, +}; + +enum Color { + Black = 0x1, + White = 0x2, + Gray = 0x3, + Purple = 0x4, + Green = 0x5, + Cyan = 0x6, + Pink = 0x7, + Yellow = 0x8, + Blue = 0x9, + Orange = 0xA, +}; + +struct Decoration { + Type type; + Color color; + int polyshape = 0; + // For triangles only + int count = 0; +}; + + +struct Cell { + inline static Cell Undefined() { + Cell c; + c.undefined = true; + return c; + } + bool undefined = false; + + bool start = false; + enum class Dir {NONE, LEFT, RIGHT, UP, DOWN}; + Dir end = Dir::NONE; + std::shared_ptr decoration = nullptr; + enum class Dot {NONE, BLACK, BLUE, YELLOW, INVISIBLE}; + Dot dot = Dot::NONE; + enum class Gap {NONE, BREAK, FULL}; + Gap gap = Gap::NONE; + + // Line color + enum class Color {NONE, BLACK, BLUE, YELLOW}; + Color color = Color::NONE; +}; + +struct Negation {}; +struct Pos {int x; int y;}; + +struct Puzzle { + int16_t height; + int16_t width; + bool hasDecorations = false; + + enum class Symmetry {NONE, X, Y, XY}; + Symmetry sym = Symmetry::NONE; + bool pillar = false; + + inline Cell GetCell(int x, int y) const { + x = Mod(x); + if (!SafeCell(x, y)) return Cell::Undefined(); + return grid[x][y]; + } + inline Cell::Color GetLine(int x, int y) const { + return grid[x][y].color; + } + // @TODO: + Pos GetSymmetricalPos(int x, int y); + + bool valid; + std::vector negations; + std::vector invalidElements; + +// private: + std::vector> grid; + +private: + inline int Mod(int x) const { + if (!pillar) return x; + return (x + width * height * 2) % width; + } + + inline bool SafeCell(int x, int y) const { + if (x < 0 || x >= width) return false; + if (y < 0 || y >= height) return false; + return true; + } +}; + +class PuzzleSerializer { +public: + PuzzleSerializer(const std::shared_ptr& memory); + Puzzle ReadPuzzle(int id); + void WritePuzzle(const Puzzle& p, int id); + +private: + // @Bug: Blue and orange are swapped? + enum Flags { + IS_ENDPOINT = 0x1, + IS_STARTPOINT = 0x2, + IS_FULL_GAP = 0x8, + HAS_DOT = 0x20, + DOT_IS_BLUE = 0x100, + DOT_IS_ORANGE = 0x200, + DOT_IS_INVISIBLE = 0x1000, + HAS_ONE_CONN = 0x100000, + HAS_VERTI_CONN = 0x200000, + HAS_HORIZ_CONN = 0x400000, + }; + + void ReadIntersections(Puzzle& p, int id); + void ReadDecorations(Puzzle& p, int id); + void WriteIntersections(const Puzzle& p, int id); + void WriteDecorations(const Puzzle& p, int id); + + std::tuple loc_to_xy(const Puzzle& p, int location) const; + int xy_to_loc(const Puzzle& p, int x, int y) const; + // Decoration location + std::tuple dloc_to_xy(const Puzzle& p, int location) const; + int xy_to_dloc(const Puzzle& p, int x, int y) const; + Cell::Dot FlagsToDot(int flags) const; + // Iterate connection lists for another location which is connected to us; return that other location. + int FindConnection(int i, const std::vector& connections_a, const std::vector& connections_b) const; + + std::shared_ptr _memory; +}; diff --git a/Source/Solver.cpp b/Source/Solver.cpp new file mode 100644 index 0000000..244bfb2 --- /dev/null +++ b/Source/Solver.cpp @@ -0,0 +1,76 @@ +#include "Solver.h" +#include "Puzzle.h" +#include "Validator.h" + +std::vector Solver::Solve(Puzzle& p) { + std::vector solutions; + // var start = (new Date()).getTime() + for (int x = 0; x < p.width; x++) { + for (int y = 0; y < p.height; y++) { + Cell cell = p.grid[x][y]; + if (cell.start) { + SolveLoop(p, x, y, solutions); + } + } + } + // var end = (new Date()).getTime() + // console.info('Solved', puzzle, 'in', (end-start)/1000, 'seconds') + return solutions; +} + +void Solver::SolveLoop(Puzzle& p, int x, int y, std::vector& solutions) { + // Stop trying to solve once we reach our goal + if (solutions.size() >= MAX_SOLUTIONS) return; + Cell cell = p.GetCell(x, y); + if (cell.undefined) return; + if (cell.gap != Cell::Gap::NONE) return; + + if (p.sym == Puzzle::Symmetry::NONE) { + if (cell.color != Cell::Color::NONE) return; // Collided with ourselves + p.grid[x][y].color = Cell::Color::BLACK; // Otherwise, mark this cell as visited + } else { + /* + // Get the symmetrical position, and try coloring it + auto sym = p.GetSymmetricalPos(x, y); + Cell::Color oldColor = p.GetLine(sym.x, sym.y); + p.grid[sym.x][sym.y].color = Cell::Color::YELLOW; + + // Collided with ourselves or our reflection + if (cell.color != Cell::Color::NONE) { + p.grid[sym.x, sym.y].color = oldColor; + return; + } + p.grid[x][y].color = Cell::Color::BLUE; // Otherwise, mark this cell as visited + */ + } + + if (cell.end != Cell::Dir::NONE) { + // Reached an endpoint, validate solution and keep going -- there may be other endpoints + Validator::Validate(p); + if (p.valid) { + Puzzle clone = p; + solutions.push_back(clone); + } + } + + // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles + // Extend path left and right + if (y % 2 == 0) { + SolveLoop(p, x - 1, y, solutions); + SolveLoop(p, x + 1, y, solutions); + } + // Extend path up and down + if (x % 2 == 0) { + SolveLoop(p, x, y - 1, solutions); + SolveLoop(p, x, y + 1, solutions); + } + + // Tail recursion: Back out of this cell + p.grid[x][y].color = Cell::Color::NONE; + if (p.sym != Puzzle::Symmetry::NONE) { + /* + auto sym = p.GetSymmetricalPos(x, y); + p.grid[sym.x][sym.y].color = Cell::Color::NONE; + */ + } +} diff --git a/Source/Solver.h b/Source/Solver.h new file mode 100644 index 0000000..8a021ac --- /dev/null +++ b/Source/Solver.h @@ -0,0 +1,16 @@ +#pragma once +#include + +#ifndef MAX_SOLUTIONS +#define MAX_SOLUTIONS 10000 +#endif + +struct Puzzle; +class Solver { +public: + static std::vector Solve(Puzzle& p); + +private: + static void SolveLoop(Puzzle& p, int x, int y, std::vector& solutions); +}; + diff --git a/Source/Source.vcxproj b/Source/Source.vcxproj index 0fed93c..92aa9d7 100644 --- a/Source/Source.vcxproj +++ b/Source/Source.vcxproj @@ -158,19 +158,22 @@ - - + + + - + + + diff --git a/Source/Validator.cpp b/Source/Validator.cpp new file mode 100644 index 0000000..82d6779 --- /dev/null +++ b/Source/Validator.cpp @@ -0,0 +1,97 @@ +#include "Validator.h" +#include "Puzzle.h" + +void Validator::Validate(Puzzle& p) { + // console.log('Validating', puzzle); + p.valid = true; // Assume valid until we find an invalid element + p.invalidElements.clear(); + p.negations.clear(); + + bool puzzleHasSymbols = false; + bool puzzleHasStart = false; + bool puzzleHasEnd = false; + // Validate gap failures as an early exit. + for (int x = 0; x < p.width; x++) { + for (int y = 0; y < p.height; y++) { + Cell cell = p.grid[x][y]; + auto decoration = cell.decoration; + if (decoration) { + if (decoration->type == Type::Stone || + decoration->type == Type::Star || + decoration->type == Type::Nega || + decoration->type == Type::Poly || + decoration->type == Type::Ylop) { + puzzleHasSymbols = true; + continue; + } + if (decoration->type == Type::Triangle) { + int actualCount = 0; + if (p.GetLine(x - 1, y) != Cell::Color::NONE) actualCount++; + if (p.GetLine(x + 1, y) != Cell::Color::NONE) actualCount++; + if (p.GetLine(x, y - 1) != Cell::Color::NONE) actualCount++; + if (p.GetLine(x, y + 1) != Cell::Color::NONE) actualCount++; + if (decoration->count != actualCount) { + // console.log('Triangle at grid['+x+']['+y+'] has', actualCount, 'borders') + p.invalidElements.emplace_back(Pos{x, y}); + } + } + } + if (cell.gap != Cell::Gap::NONE && cell.color != Cell::Color::NONE) { + // console.log('Gap at', x, y, 'is covered') + p.valid = false; + } + if (cell.dot != Cell::Dot::NONE) { + if (cell.color == Cell::Color::NONE) { + // console.log('Dot at', x, y, 'is not covered') + p.invalidElements.emplace_back(Pos{x, y}); + } else if (cell.color == Cell::Color::BLUE && cell.dot == Cell::Dot::YELLOW) { + // console.log('Yellow dot at', x, y, 'is covered by blue line') + p.valid = false; + } else if (cell.color == Cell::Color::YELLOW && cell.dot == Cell::Dot::BLUE) { + // console.log('Blue dot at', x, y, 'is covered by yellow line') + p.valid = false; + } + } + if (cell.color != Cell::Color::NONE) { + if (cell.start == true) puzzleHasStart = true; + if (cell.end != Cell::Dir::NONE) puzzleHasEnd = true; + } + } + } + if (!puzzleHasStart || !puzzleHasEnd) { + // console.log('There is no covered start or endpoint') + p.valid = false; + } + + // Perf optimization: We can skip computing regions if the grid has no symbols. + if (!puzzleHasSymbols) { // No additional symbols, and we already checked dots & gaps + p.valid &= (p.invalidElements.size() == 0); + } else { // Additional symbols, so we need to discard dots & divide them by region + /* + p.invalidElements.clear(); + std::vector regions = p.GetRegions(); + // console.log('Found', regions.length, 'regions'); + // console.debug(regions); + + for (const Region& region : regions) { + std::string key = region.grid.ToString(); + auto regionData = puzzle.regionCache[key]; + if (regionData == undefined) { + console.log('Cache miss for region', region, 'key', key); + regionData = _regionCheckNegations(puzzle, region); + // Entirely for convenience + regionData.valid = (regionData.invalidElements.size() == 0) + // console.log('Region valid:', regionData.valid); + + if (!DISABLE_CACHE) { + p.regionCache[key] = regionData; + } + } + p.negations = p.negations.concat(regionData.negations); + p.invalidElements = p.invalidElements.concat(regionData.invalidElements); + p.valid = p.valid && regionData.valid; + } + */ + } + // console.log('Puzzle has', puzzle.invalidElements.length, 'invalid elements') +} diff --git a/Source/Validator.h b/Source/Validator.h new file mode 100644 index 0000000..cddc293 --- /dev/null +++ b/Source/Validator.h @@ -0,0 +1,27 @@ +#pragma once +#include +#include + +#ifndef NEGATIONS_CANCEL_NEGATIONS +#define NEGATIONS_CANCEL_NEGATIONS true +#endif + +#ifndef SIMPLE_POLYOMINOS +#define SIMPLE_POLYOMINOS true +#endif + +#ifndef DISABLE_CACHE +#define DISABLE_CACHE false +#endif + +struct Region{}; +struct Puzzle; +struct Pos; +class Validator { +public: + static void Validate(Puzzle& p); + +private: + static void RegionCheckNegations(Puzzle& p, const Region& r); + static std::vector RegionCheck(Puzzle& p, const Region& r); +}; diff --git a/Source/json.hpp b/Source/json.hpp deleted file mode 100644 index 1e7cf51..0000000 --- a/Source/json.hpp +++ /dev/null @@ -1,20274 +0,0 @@ -/* - __ _____ _____ _____ - __| | __| | | | JSON for Modern C++ -| | |__ | | | | | | version 3.4.0 -|_____|_____|_____|_|___| https://github.com/nlohmann/json - -Licensed under the MIT License . -SPDX-License-Identifier: MIT -Copyright (c) 2013-2018 Niels Lohmann . - -Permission is hereby granted, free of charge, to any person obtaining a copy -of this software and associated documentation files (the "Software"), to deal -in the Software without restriction, including without limitation the rights -to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all -copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -SOFTWARE. -*/ - -#ifndef NLOHMANN_JSON_HPP -#define NLOHMANN_JSON_HPP - -#define NLOHMANN_JSON_VERSION_MAJOR 3 -#define NLOHMANN_JSON_VERSION_MINOR 4 -#define NLOHMANN_JSON_VERSION_PATCH 0 - -#include // all_of, find, for_each -#include // assert -#include // and, not, or -#include // nullptr_t, ptrdiff_t, size_t -#include // hash, less -#include // initializer_list -#include // istream, ostream -#include // iterator_traits, random_access_iterator_tag -#include // accumulate -#include // string, stoi, to_string -#include // declval, forward, move, pair, swap - -// #include -#ifndef NLOHMANN_JSON_FWD_HPP -#define NLOHMANN_JSON_FWD_HPP - -#include // int64_t, uint64_t -#include // map -#include // allocator -#include // string -#include // vector - -/*! -@brief namespace for Niels Lohmann -@see https://github.com/nlohmann -@since version 1.0.0 -*/ -namespace nlohmann -{ -/*! -@brief default JSONSerializer template argument - -This serializer ignores the template arguments and uses ADL -([argument-dependent lookup](https://en.cppreference.com/w/cpp/language/adl)) -for serialization. -*/ -template -struct adl_serializer; - -template class ObjectType = - std::map, - template class ArrayType = std::vector, - class StringType = std::string, class BooleanType = bool, - class NumberIntegerType = std::int64_t, - class NumberUnsignedType = std::uint64_t, - class NumberFloatType = double, - template class AllocatorType = std::allocator, - template class JSONSerializer = - adl_serializer> -class basic_json; - -/*! -@brief JSON Pointer - -A JSON pointer defines a string syntax for identifying a specific value -within a JSON document. It can be used with functions `at` and -`operator[]`. Furthermore, JSON pointers are the base for JSON patches. - -@sa [RFC 6901](https://tools.ietf.org/html/rfc6901) - -@since version 2.0.0 -*/ -template -class json_pointer; - -/*! -@brief default JSON class - -This type is the default specialization of the @ref basic_json class which -uses the standard template types. - -@since version 1.0.0 -*/ -using json = basic_json<>; -} // namespace nlohmann - -#endif - -// #include - - -// This file contains all internal macro definitions -// You MUST include macro_unscope.hpp at the end of json.hpp to undef all of them - -// exclude unsupported compilers -#if !defined(JSON_SKIP_UNSUPPORTED_COMPILER_CHECK) - #if defined(__clang__) - #if (__clang_major__ * 10000 + __clang_minor__ * 100 + __clang_patchlevel__) < 30400 - #error "unsupported Clang version - see https://github.com/nlohmann/json#supported-compilers" - #endif - #elif defined(__GNUC__) && !(defined(__ICC) || defined(__INTEL_COMPILER)) - #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) < 40800 - #error "unsupported GCC version - see https://github.com/nlohmann/json#supported-compilers" - #endif - #endif -#endif - -// disable float-equal warnings on GCC/clang -#if defined(__clang__) || defined(__GNUC__) || defined(__GNUG__) - #pragma GCC diagnostic push - #pragma GCC diagnostic ignored "-Wfloat-equal" -#endif - -// disable documentation warnings on clang -#if defined(__clang__) - #pragma GCC diagnostic push - #pragma GCC diagnostic ignored "-Wdocumentation" -#endif - -// allow for portable deprecation warnings -#if defined(__clang__) || defined(__GNUC__) || defined(__GNUG__) - #define JSON_DEPRECATED __attribute__((deprecated)) -#elif defined(_MSC_VER) - #define JSON_DEPRECATED __declspec(deprecated) -#else - #define JSON_DEPRECATED -#endif - -// allow to disable exceptions -#if (defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)) && !defined(JSON_NOEXCEPTION) - #define JSON_THROW(exception) throw exception - #define JSON_TRY try - #define JSON_CATCH(exception) catch(exception) - #define JSON_INTERNAL_CATCH(exception) catch(exception) -#else - #define JSON_THROW(exception) std::abort() - #define JSON_TRY if(true) - #define JSON_CATCH(exception) if(false) - #define JSON_INTERNAL_CATCH(exception) if(false) -#endif - -// override exception macros -#if defined(JSON_THROW_USER) - #undef JSON_THROW - #define JSON_THROW JSON_THROW_USER -#endif -#if defined(JSON_TRY_USER) - #undef JSON_TRY - #define JSON_TRY JSON_TRY_USER -#endif -#if defined(JSON_CATCH_USER) - #undef JSON_CATCH - #define JSON_CATCH JSON_CATCH_USER - #undef JSON_INTERNAL_CATCH - #define JSON_INTERNAL_CATCH JSON_CATCH_USER -#endif -#if defined(JSON_INTERNAL_CATCH_USER) - #undef JSON_INTERNAL_CATCH - #define JSON_INTERNAL_CATCH JSON_INTERNAL_CATCH_USER -#endif - -// manual branch prediction -#if defined(__clang__) || defined(__GNUC__) || defined(__GNUG__) - #define JSON_LIKELY(x) __builtin_expect(!!(x), 1) - #define JSON_UNLIKELY(x) __builtin_expect(!!(x), 0) -#else - #define JSON_LIKELY(x) x - #define JSON_UNLIKELY(x) x -#endif - -// C++ language standard detection -#if (defined(__cplusplus) && __cplusplus >= 201703L) || (defined(_HAS_CXX17) && _HAS_CXX17 == 1) // fix for issue #464 - #define JSON_HAS_CPP_17 - #define JSON_HAS_CPP_14 -#elif (defined(__cplusplus) && __cplusplus >= 201402L) || (defined(_HAS_CXX14) && _HAS_CXX14 == 1) - #define JSON_HAS_CPP_14 -#endif - -/*! -@brief macro to briefly define a mapping between an enum and JSON -@def NLOHMANN_JSON_SERIALIZE_ENUM -@since version 3.4.0 -*/ -#define NLOHMANN_JSON_SERIALIZE_ENUM(ENUM_TYPE, ...) \ - template \ - inline void to_json(BasicJsonType& j, const ENUM_TYPE& e) \ - { \ - static_assert(std::is_enum::value, #ENUM_TYPE " must be an enum!"); \ - static const std::pair m[] = __VA_ARGS__; \ - auto it = std::find_if(std::begin(m), std::end(m), \ - [e](const std::pair& ej_pair) -> bool \ - { \ - return ej_pair.first == e; \ - }); \ - j = ((it != std::end(m)) ? it : std::begin(m))->second; \ - } \ - template \ - inline void from_json(const BasicJsonType& j, ENUM_TYPE& e) \ - { \ - static_assert(std::is_enum::value, #ENUM_TYPE " must be an enum!"); \ - static const std::pair m[] = __VA_ARGS__; \ - auto it = std::find_if(std::begin(m), std::end(m), \ - [j](const std::pair& ej_pair) -> bool \ - { \ - return ej_pair.second == j; \ - }); \ - e = ((it != std::end(m)) ? it : std::begin(m))->first; \ - } - -// Ugly macros to avoid uglier copy-paste when specializing basic_json. They -// may be removed in the future once the class is split. - -#define NLOHMANN_BASIC_JSON_TPL_DECLARATION \ - template class ObjectType, \ - template class ArrayType, \ - class StringType, class BooleanType, class NumberIntegerType, \ - class NumberUnsignedType, class NumberFloatType, \ - template class AllocatorType, \ - template class JSONSerializer> - -#define NLOHMANN_BASIC_JSON_TPL \ - basic_json - -// #include - - -#include // not -#include // size_t -#include // conditional, enable_if, false_type, integral_constant, is_constructible, is_integral, is_same, remove_cv, remove_reference, true_type - -namespace nlohmann -{ -namespace detail -{ -// alias templates to reduce boilerplate -template -using enable_if_t = typename std::enable_if::type; - -template -using uncvref_t = typename std::remove_cv::type>::type; - -// implementation of C++14 index_sequence and affiliates -// source: https://stackoverflow.com/a/32223343 -template -struct index_sequence -{ - using type = index_sequence; - using value_type = std::size_t; - static constexpr std::size_t size() noexcept - { - return sizeof...(Ints); - } -}; - -template -struct merge_and_renumber; - -template -struct merge_and_renumber, index_sequence> - : index_sequence < I1..., (sizeof...(I1) + I2)... > {}; - -template -struct make_index_sequence - : merge_and_renumber < typename make_index_sequence < N / 2 >::type, - typename make_index_sequence < N - N / 2 >::type > {}; - -template<> struct make_index_sequence<0> : index_sequence<> {}; -template<> struct make_index_sequence<1> : index_sequence<0> {}; - -template -using index_sequence_for = make_index_sequence; - -// dispatch utility (taken from ranges-v3) -template struct priority_tag : priority_tag < N - 1 > {}; -template<> struct priority_tag<0> {}; - -// taken from ranges-v3 -template -struct static_const -{ - static constexpr T value{}; -}; - -template -constexpr T static_const::value; -} // namespace detail -} // namespace nlohmann - -// #include - - -#include // not -#include // numeric_limits -#include // false_type, is_constructible, is_integral, is_same, true_type -#include // declval - -// #include - -// #include - -// #include - - -#include - -// #include - - -namespace nlohmann -{ -namespace detail -{ -template struct make_void -{ - using type = void; -}; -template using void_t = typename make_void::type; -} // namespace detail -} // namespace nlohmann - - -// http://en.cppreference.com/w/cpp/experimental/is_detected -namespace nlohmann -{ -namespace detail -{ -struct nonesuch -{ - nonesuch() = delete; - ~nonesuch() = delete; - nonesuch(nonesuch const&) = delete; - void operator=(nonesuch const&) = delete; -}; - -template class Op, - class... Args> -struct detector -{ - using value_t = std::false_type; - using type = Default; -}; - -template class Op, class... Args> -struct detector>, Op, Args...> -{ - using value_t = std::true_type; - using type = Op; -}; - -template