/*
 * Name: Owen Sullivan
 * Date Submitted: 10/24/22
 * Lab Section: 006
 * Assignment Name: Lab 6: Finding the Closest Pair of Points
*/

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct point {
  
    double x;
    double y;

};

double calcDistance(const struct point &p1, const struct point &p2);
double minDistance(const vector<double> &distances);
double adjCellDistance(const vector<vector<vector<struct point>>> &plane,
                       const int &topXPos, const int &topYPos,
                       const int &topPoint, const int &xPos,
                       const int &yPos);
double closestPair(string filename);

// int main() {
    
//     double min;
//     string filename;
    
//     cout << "File with list of points within unit square: ";
//     cin >> filename;
    
//     min = closestPair(filename);
    
//     cout << setprecision(16);
//     cout << "Distance between closest pair of points: " << min << endl;
    
//     return 0;

// }

double calcDistance(const struct point &p1, const struct point &p2) {

    // Use the distance formula to calculate the difference between
    // the two points passed to the function
    return sqrt(pow((p2.x - p1.x), 2) + pow((p2.y - p1.y), 2));

}

double minDistance(const vector<double> &distances) {

    // Set minimumDistance to the maximum value for a double,
    // to make sure the minimum check isn't comparing against
    // zero to start
    double minimumDistance = numeric_limits<double>::max();

    // Loop through values in vector
    for (double dist : distances) {

        // If value isn't zero, find the minimum between
        // the value and the current minimumDistance
        if (dist != 0.0) {

            minimumDistance = min(minimumDistance, dist);

        }

    }

    return minimumDistance;

}

double adjCellDistance(const vector<vector<vector<struct point>>> &plane,
                       const int &topXPos, const int &topYPos,
                       const int &topPoint, const int &xPos,
                       const int &yPos) {

    double adjCellDistance = 0.0;
    
    // Loop through coordinate pairs in cell
    for (int cellPoint = 0; cellPoint < plane.at(xPos).at(yPos).size(); cellPoint++) {

        // If the current coordinate pair (pertaining to the loop through pairs in a given x,y cell) is
        // the same as the current coordinate pair (pertaining to the loop through pairs in same cell)
        if ((plane.at(topXPos).at(topYPos).at(topPoint).x != plane.at(xPos).at(yPos).at(cellPoint).x)
        && (plane.at(topXPos).at(topYPos).at(topPoint).y != plane.at(xPos).at(yPos).at(cellPoint).y)) {

            // Call calcDistance to get the distance between coordinate pairs
            double currentDistance = calcDistance(plane.at(topXPos).at(topYPos).at(topPoint), 
                                                    plane.at(xPos).at(yPos).at(cellPoint));

            // If the calculated distance is less than the smallest
            // distance for coordinate pairs in the same cell or
            // this is the first pair in the cell, update the
            // smallest distance for the same cell
            if (currentDistance < adjCellDistance || cellPoint == 0) {

                adjCellDistance = currentDistance;

            }

        }

    }

    return adjCellDistance;

}

double closestPair(string filename) {

    // Open file using file name passed as function argument
    ifstream inFile(filename);

    // Read the number of points from the input file
    int numPoints;
    inFile >> numPoints;

    // Create a vector to store matching pairs of points, read
    // from file
    vector<vector<double>> points(numPoints);

    // Loop through the number of points
    for (int point = 0; point < numPoints; point++) {

        double x;
        double y;
        
        // Read the current pair of points
        inFile >> x;
        inFile >> y;

        // Push the current pair of points to the points vector
        points.at(point).push_back(x);
        points.at(point).push_back(y);

    }

    // Calculate b as the number of rows and columns in the coordinate plane
    // by taking the square root of the number of points and rounding down
    // 
    // This solution is best because it will always scale proportionately, 
    // regardless of the number of points
    int b = floor(sqrt(numPoints));
    // Calculate interval used in determining x and y plane positions by
    // dividing 1 by b
    double interval = 1 / (double)b;

    // Create a 2D vector of point objects, initializing sizes of x and y
    // vectors using b
    vector<vector<vector<struct point>>> plane(b, vector<vector<struct point>>(b));

    // Loop through the number of points
    for (int currentPoint = 0; currentPoint < numPoints; currentPoint++) {

        // Calculate the x and y plane positions by dividing the current
        // point by the interval calculated earlier, then rouding down
        double xPos = floor(points.at(currentPoint).at(0) / interval);
        double yPos = floor(points.at(currentPoint).at(1) / interval);

        // Create a point object with the contents of the current matching
        // coordinate pair
        struct point point = {points.at(currentPoint).at(0), points.at(currentPoint).at(1)};

        // Push the newly-created point object to the plane vector at the
        // calculated x and y plane positions (casted to int from double for
        // indexing)
        plane.at((int)xPos).at((int)yPos).push_back(point);

    }

    double smallestDistance = 0.0;

    // Loop through x coordinates in plane
    for (int xPos = 0; xPos < plane.size(); xPos++) {

        // Loop through y coordinates in plane
        for (int yPos = 0; yPos < plane.at(xPos).size(); yPos++) {

            // Loop through coordinate pairs in current cell
            for (int currentPoint = 0; currentPoint < plane.at(xPos).at(yPos).size(); currentPoint++) {

                double sameCellDistance = 0.0;
                double topDistance = 0.0;
                double topLeftDistance = 0.0;
                double topRightDistance = 0.0;
                double bottomDistance = 0.0;
                double bottomLeftDistance = 0.0;
                double bottomRightDistance = 0.0;
                double leftDistance = 0.0;
                double rightDistance = 0.0;

                sameCellDistance = adjCellDistance(plane, xPos, yPos, currentPoint, xPos, yPos);

                // Check that checking 1 less than yPos doesn't go out
                // of bounds
                if (yPos - 1 >= 0) {

                    topDistance = adjCellDistance(plane, xPos, yPos, currentPoint, xPos, (yPos - 1));

                }

                // Check that checking 1 less than yPos and 1 less than xPos
                // doesn't go out of bounds
                if (yPos - 1 >= 0 && xPos - 1 >= 0) {

                    topLeftDistance = adjCellDistance(plane, xPos, yPos, currentPoint, (xPos - 1), (yPos - 1));

                }

                // Check that checking 1 less than yPos and 1 more than xPos
                // doesn't go out of bounds
                if (yPos - 1 >= 0 && xPos + 1 < b) {

                    topRightDistance = adjCellDistance(plane, xPos, yPos, currentPoint, (xPos + 1), (yPos - 1));

                }

                // Check that checking 1 more than yPos doesn't go out
                // of bounds
                if (yPos + 1 < b) {

                    bottomDistance = adjCellDistance(plane, xPos, yPos, currentPoint, xPos, (yPos + 1));

                }

                // Check that checking 1 more than yPos and 1 less than xPos
                // doesn't go out of bounds
                if (yPos + 1 < b && xPos - 1 >= 0) {

                    bottomLeftDistance = adjCellDistance(plane, xPos, yPos, currentPoint, (xPos - 1), (yPos + 1));

                }

                // Check that checking 1 more than yPos and 1 more than xPos
                // doesn't go out of bounds
                if (yPos + 1 < b && xPos + 1 < b) {

                    bottomRightDistance = adjCellDistance(plane, xPos, yPos, currentPoint, (xPos + 1), (yPos + 1));

                }

                // Check that checking 1 less than xPos doesn't go out
                // of bounds
                if (xPos - 1 >= 0) {

                    leftDistance = adjCellDistance(plane, xPos, yPos, currentPoint, (xPos - 1), yPos);

                }

                // Check that checking 1 more than xPos doesn't go out
                // of bounds
                if (xPos + 1 < b) {

                    rightDistance = adjCellDistance(plane, xPos, yPos, currentPoint, (xPos + 1), yPos);

                }

                // Assemble a vector of each minimum distance across nearby cells
                vector<double> distances{sameCellDistance, topDistance, topLeftDistance, topRightDistance,
                                         bottomDistance, bottomLeftDistance, bottomRightDistance, leftDistance,
                                         rightDistance};

                // Call minDistance to find the smallest distance across
                // nearby cells
                double minimumDistance = minDistance(distances);

                // If the minimum distance for the pairs in the current y
                // coordinate is less than the overall smallest distance or the
                // smallest distance has not yet been set, set smallestDistance
                // to the current minimum distance
                if (minimumDistance < smallestDistance || smallestDistance == 0.0) {

                    smallestDistance = minimumDistance;

                }

            }

        }

    }

    return smallestDistance;

}