#include <QApplication>
#include <QGraphicsView>
#include <QGraphicsScene>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <chrono>
#include <cmath>
#include <unordered_map>
#include "Point.h"

// constants
static const int SCENE_WIDTH = 512;
static const int SCENE_HEIGHT = 512;

void render_points(QGraphicsScene* scene, const vector<Point>& points) {
    for(const auto& point : points) {
        point.draw(scene);
    }
}

void render_line(QGraphicsScene* scene, const Point& p1, const Point& p2) {
    p1.lineTo(scene, p2);
}

/*
 * Return whether v1 contains v2.
 */
template <typename T>
bool vec_contains_vec(const vector<T>& v1, const vector<T>& v2) {
    if (v2.size() == 0) {
        return true;
    }
    int i1 = 0;
    int i2 = 0;
    while (i1 < v1.size()) {
        if (v1[i1] == v2[i2]) {
            i2++;
            if (i2 == v2.size()) {
                return true;
            }
        } else {
            i2 = 0;
        }
        i1++;
    }
    return false;
}

/*
 * Return whether inner is contained in some vector before itself in outer.
 */
template <typename T>
bool contained_in_before(const vector<vector<T>>& outer, int index) {
    for (int i = 0; i < index; i++) {
        if (vec_contains_vec(outer[i], outer[index])) {
            return true;
        }
    }
    return false;
}

int main(int argc, char *argv[]) {
    QApplication a(argc, argv);

    // open file
    string filename = "grid6x6.txt";

    ifstream input;
    input.open(filename);

    // the vector of points
    vector<Point> points;

    // read points from file
    int N;
    int x;
    int y;

    input >> N;

    for (int i = 0; i < N; ++i) {
        input >> x >> y;
        points.push_back(Point(x, y));
    }
    input.close();

    // setup graphical window
    QGraphicsView *view = new QGraphicsView();
    QGraphicsScene *scene = new QGraphicsScene(0, 0, SCENE_WIDTH, SCENE_HEIGHT);
    view->setScene(scene);
    // draw points to screen all at once
    render_points(scene, points);
    view->scale(1, -1); //screen y-axis is inverted
    view->resize(view->sizeHint());
    view->setWindowTitle("Fast Pattern Recognition");

    sort(points.begin(), points.end());
    auto begin = chrono::high_resolution_clock::now();

    // these contain indexes since points can't be compared
    vector<vector<int>> lines;  // all lines we want to draw
    vector<pair<double, int>> angles;  // for each point, the angle to every other point

    for (int p1 = 0; p1 < N-1; p1++) {
        angles.clear();
        for (int p2 = p1 + 1; p2 < N; p2++) {
            double angle = points.at(p1).slopeTo(points.at(p2));
            angles.push_back({ angle, p2 });
        }
        sort(angles.begin(), angles.end());
        vector<int> line = { p1, 1 };
        for (int i = 2; i < angles.size(); i++) {
            double prev_angle = angles[i - 1].first;
            if (angles[i].first == prev_angle) {
                line.push_back(angles[i].second);
            } else {
                if (line.size() >= 4) {
                    lines.push_back(line);
                }
                line.clear();
                line.push_back(p1);
                line.push_back(angles[i].second);
            }
        }
        if (line.size() >= 4) {
            lines.push_back(line);
        }
    }

    for (int i = 0; i < lines.size();) {
        if (contained_in_before(lines, i)) {
            lines.erase(lines.begin() + i);
        } else {
            i++;
        }
    }

    for (const auto& line : lines) {
        render_line(scene, points.at(line.front()), points.at(line.back()));
    }
    cout << lines.size() << " draws" << endl;

    vector<int> v1 = {1, 2, 3};
    vector<int> v2 = {2, 3};
    vector<int> v3 = {3};
    vector<int> v4 = {2, 3, 4};
    cout << vec_contains_vec(v1, v2) << " "
         << vec_contains_vec(v2, v1) << " "
         << vec_contains_vec(v1, v3) << " "
         << vec_contains_vec(v1, v4) << endl;

    vector<vector<int>> outer = {{1,2,3}, {2,3}, {3,4}};
    cout << contained_in_before(outer, 0) << " "
         << contained_in_before(outer, 1) << " "
         << contained_in_before(outer, 2) << endl;

    auto end = chrono::high_resolution_clock::now();
    cout << "Computing line segments took "
         << std::chrono::duration_cast<chrono::milliseconds>(end - begin).count()
         << " milliseconds." << endl;

    view->show();
    return a.exec(); // start Qt event loop
}