ממן 15 שאלה 3

//TODO: add time and space comlexity to all methods in all classes
//TODO: remove
package YY11_LISTS.MMN15;
/**
 * Represent a polygon
 * Author: Ness Bokobza, 03696225
 * Version: 23/6/20
 */
public class Polygon {
    private PointNode _head;

    public Polygon() {
        this._head = null;
    }

    /**
     * Adds a new PointNode to the Polygon list
     * @param p the new point
     * @param pos the wanted position of the new node
     * @return true if the node added successfully
     * Time complexity: O(n)
     * Space complexity: O(1)
     */
    public boolean addVertex(Point p, int pos) {
        int polyLen = this.listLength();
        int count;
        PointNode pointer, next, prev;

        if(p == null)
            return false;
        //if position if higher then the list length + 1 or its smaller then 1
        if(pos > polyLen + 1 || pos < 1)
            return false;

        //if list is empty
        if (this._head == null) {
            this._head = new PointNode(p);
            return true;
        }
        // if position is higher then the current list length (but no more then 1)
        if (pos > polyLen) {
            pointer = this._head;
            while(pointer.getNext() != null)
                pointer = pointer.getNext();
            prev = pointer;
            pointer = new PointNode(p);
            prev.setNext(pointer);
            return true;
        }

        // if position is already taken - push the new point there, and push the rest of the list forward
        count = 1;
        prev = this._head;
        while(count < pos -1) {
            prev = prev.getNext();
            count ++;
        }
        if(count == 1) {
            next = this._head;
            this._head = new PointNode(p);
            this._head.setNext(next);
            next.setNext(null);
        } else {
            pointer = new PointNode(p);
            next = prev.getNext();
            prev.setNext(pointer);
            pointer.setNext(next);
        }

        return true;
    }

    /**
     * Finds the highest point in the y axis of the polygon list
     * @return the highest point in the list
     * Time complexity: O(n)
     * Space complexity: O(1)
     */
    public Point highestVertex() {
        int len = this.listLength();
        if (len == 0)
            return null;
        if(len == 1)
            return this._head.getPoint();

        PointNode pointer = this._head;
        Point highest = this._head.getPoint();
        while(pointer != null) {
            if(pointer.getPoint().getY() > highest.getY())
                highest = pointer.getPoint();
            pointer = pointer.getNext();
        }
        return new Point(highest);
    }

    /**
     * creates a string representation of the polygon
     * @return the representation string of the polygon
     * Time complexity: O(n)
     * Space complexity: O(1)
     */
    public String toString() {
        int len = this.listLength();
        if(len == 0)
            return "The polygon has 0 vertices.";
        else {
            PointNode pointer = this._head;
            String str = "The polygon has " + len + " vertices:\n(";
            while (pointer != null) {
                str += pointer.getPoint().toString();
                //add "," to all items except the last one
                str += pointer.getNext() == null ? "" : ",";
                pointer = pointer.getNext();
            }
            str += ")";
            return str;
        }
    }

    /**
     * Calculates the perimeter of the polygon
     * @return the perimeter of the polygon
     * Time complexity: O(n)
     * Space complexity: O(1)
     */
    public double calcPerimeter() {
        int len = this.listLength();
        double perimeter = 0;

        if(len == 0 || len == 1)
            return 0;

        if(len == 2)
            return _head.getPoint().distance(_head.getNext().getPoint());

        PointNode pointer = this._head, next = this._head;
        while(pointer.getNext() != null) {
            next = pointer.getNext();
            perimeter += pointer.getPoint().distance(next.getPoint());
            pointer = pointer.getNext();
        }
        perimeter += pointer.getPoint().distance(this._head.getPoint());
        return perimeter;
    }

    /**
     * calculates the area of the polygon
     * @return the area of the polygon
     * Time complexity: O(n)
     * Space complexity: O(1)
     */
    public double calcArea() {
        int len = this.listLength();

        if (len < 3)
            return 0;

        double totalSum = 0, sumA, sumB;

        PointNode pointer = this._head, next;
        while(pointer.getNext() != null) {
            next = pointer.getNext();
            sumA = pointer.getPoint().getX() * next.getPoint().getY();
            sumB = pointer.getPoint().getY() * next.getPoint().getX();
            totalSum += sumA - sumB;
            pointer = next;
        }
        //drawing the last line from the last point of pointer and back to the _head point
        next = this._head;
        sumA = pointer.getPoint().getX() * next.getPoint().getY();
        sumB = pointer.getPoint().getY() * next.getPoint().getX();
        totalSum += sumA -sumB;
        totalSum /= 2;
        return totalSum < 0 ? totalSum * -1 : totalSum;
    }

    /**
     * Check if this polygon's area is bigger the the other polygon's area
     * @param other the other polygon
     * @return true if this polygon's area is bigger then the other polygon's area
     * Time complexity: O(n) - because this method use the calcArea method, and its complexity is O(n)
     * Space complexity: O(1)
     */
    public boolean isBigger(Polygon other) {
        return this.calcArea() > other.calcArea();
    }

    /**
     * finds a vertex in the polygon
     * @param p the wanted vertex
     * @return the vertex's number in the list if it is found, and -1 if not
     * Time complexity: O(n)
     * Space complexity: O(1)
     */
    public int findVertex(Point p) {
        int len = this.listLength(), idx = 1;
        PointNode pointer = this._head;

        if(len == 0)
            return -1;

        while(pointer != null) {
            if(pointer.getPoint().equals(p))
                return idx;
            pointer = pointer.getNext();
            idx ++;
        }
        return -1;
    }

    /**
     * Finds the point that comes after the wanted vertex
     * @param p the wanted vertex
     * @return the next point after p if found
     * Time complexity: O(n)
     * Space complexity: O(1)
     */
    public Point getNextVertex(Point p) {
        int len = this.listLength();

        if(len == 0 || p == null)
            return null;
        if(len == 1 && this._head.getPoint().equals(p))
            return new Point(this._head.getPoint());

        PointNode pointer = this._head;
        while(pointer != null) {
            if(pointer.getPoint().equals(p))
                //if pointer is the last item in list, return a copy of the head's point
                //else return the copy of pointer's point
                return pointer.getNext() == null ? new Point(this._head.getPoint()) : new Point(pointer.getNext().getPoint());
            pointer = pointer.getNext();
        }
        //if point didn't found return null
        return null;
    }

    /**
     * Creates a rectangle polygon that surrounds and block our polygon
     * @return a rectangle polygon that surrounds and block our polygon
     * Time complexity: O(n)
     * Space complexity: O(1)
     */
    public Polygon getBoundingBox() {
        int len = this.listLength();
        if(len < 3)
            return null;

        PointNode pointer = this._head;
        double currentX = pointer.getPoint().getX();
        double currentY = pointer.getPoint().getY();
        //those points are the 4 points of the rectangle
        double highestX = currentX, lowestX = currentX, highestY = currentY, lowestY = currentY;

        while(pointer != null) {
            currentX = pointer.getPoint().getX();
            currentY = pointer.getPoint().getY();

            //searching for the lowest and highest X
            if(currentX > highestX)
                highestX = currentX;
            else if(currentX < lowestX)
                lowestX = currentX;

            //searching for the lowest and highest Y
            if(currentY > highestY)
                highestY = currentY;
            else if(currentY < lowestY)
                lowestY = currentY;

            pointer = pointer.getNext();
        }
        //the top points of the rectangle
        Point topLeft = new Point(lowestX, highestY), topRight = new Point(highestX, highestY);
        //the bottom points of the rectangle
        Point bottomLeft = new Point(lowestX, lowestY), bottomRight = new Point(highestX, lowestY);

        //creating the new rectangle polygon
        Polygon blockRect = new Polygon();
        blockRect.addVertex(topLeft, 1); //O(n)
        blockRect.addVertex(topRight, 2); //O(n)
        blockRect.addVertex(bottomRight, 3); //O(n)
        blockRect.addVertex(bottomLeft, 4); // O(n)

        return blockRect;
    }

    //return the length of the list
    //Time complexity: O(n)
    //Space complexity: O(1)
    private int listLength() {
        int len = 0;
        PointNode temp = this._head;
        while(temp != null) {
            temp = temp.getNext();
            len++;
        }

        return len;
    }

    public static void main(String[] args) {
        Point p1 = new Point(2,1);
        Point p2 = new Point(5,0);
        Point p3 = new Point(7,5);
        Point p4 = new Point(4,6);
        Point p5 = new Point(1,4);

        PointNode pn1 = new PointNode(p1);
        Polygon pl = new Polygon();
        Polygon pl2 = new Polygon();

        pl.addVertex(p1, 1);
        pl.addVertex(p3, 2);
        pl.addVertex(p4, 3);
        pl.addVertex(p5, 4);
        pl.addVertex(p2, 2);


        p1 = new Point(-3,-2);
        p2 = new Point(-1, 4);
        p3 = new Point(6, 1);
        p4 = new Point(3, 10);
        p5 = new Point(-4, 9);
        pl2.addVertex(p1, 1);
        pl2.addVertex(p2, 2);
        pl2.addVertex(p3, 3);
        pl2.addVertex(p4, 4);
        pl2.addVertex(p5, 5);
        System.out.println(pl2.calcPerimeter());
        System.out.println(pl2.calcArea());

    }
}