package homework8;
import java.io.*;
import java.util.*;


public class Main {

   
    public static void main(String[] args) throws IOException {

        int numPoints = 100;
        int numDistinctPoints;
        int gridSize;
        Scanner input = new Scanner(System.in);
        boolean validInput = false;
        MyPoint [] arr;
        long tStart, tEnd;

        /* This while loop gets the user to enter
         * the number of points to be generated and
         * set numPoints to the specified integer.
         */
        while (!validInput) {
            System.out.print("Please enter the number of points: ");
            if (!input.hasNextInt()) {
                input.nextLine();
                System.out.println("That's not an integer");
            }
            else {
                numPoints = input.nextInt();
                if (numPoints <= 0 )
                    System.out.println("That integer is not positive");
                else
                    validInput = true;
            }
        }

        System.out.println("Number of points is " + numPoints);
        arr = new MyPoint[numPoints]; // array to store the generated points

        gridSize = numPoints/20 + 10;

        int x,y, shift;
        int xPlusY = 1000000;

        /* This for loop populates the array arr with points
         * p such that xPlusY <= p.x + p.y <= xPlusY + 10.
         * p.x is a random integer between 0 and gridSize.
         */
        for (int i = 0; i < numPoints; i++) {
            x = (int) (gridSize * Math.random()); //random int from 0 to gridSize
            shift = (int) (10 * Math.random()); //random int from 0 to 10
            y = xPlusY - x + shift;
            arr[i] = new MyPoint(x, y);
        }

        /* Compute the number of distinct points with
         * the aid of an ArrayList, and store the
         * answer in numDistinctPoints.
         */
        tStart = System.currentTimeMillis();
        ArrayList<MyPoint> distinctPointList = new ArrayList<MyPoint>();
        for (int i = 0; i < arr.length; i++) {
            if (!distinctPointList.contains(arr[i]))
                distinctPointList.add(arr[i]);
        }
        numDistinctPoints = distinctPointList.size();
        tEnd = System.currentTimeMillis();


        System.out.println("Number of distinct points is " + numDistinctPoints);
        System.out.println("Time taken using ArrayList: " + (tEnd - tStart));


        /* Compute the number of distinct points using
         * sorting, and store the answer in numDistinctPoints
         */
        tStart = System.currentTimeMillis();
        MyPoint [] arrCopy = arr.clone();
        Arrays.sort(arrCopy);
        Stack<MyPoint> sta = new Stack<MyPoint>();
        for (int i = 0; i < arrCopy.length; i++) {
            if (sta.empty() || (! (arrCopy[i].equals(sta.peek()) )))
                sta.push(arrCopy[i]);
        }
        numDistinctPoints = sta.size();
        tEnd = System.currentTimeMillis();

        System.out.println("Number of distinct points is " + numDistinctPoints);
        System.out.println("Time taken using Sorting: " + (tEnd - tStart));

        /*Compute the number of distinct points using
         * a HashMap, and store the answer in numDistinctPoints
         */

        
    }

     

}