mmn 15 q3

//TODO: add time and space comlexity to all methods in all classes
//TODO: remove
package Mavo2020.Playground;

/**
 * Represent a polygon
 */
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
     * O(?)
     */
    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 ++;
        }

        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
     * O(?)
     */
    public Point highestVertex() {
        int len = this.listLength();
        if (len == 0)
            return null;
        if(len == 1)
            return this._head.getPoint();

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

    /**
     * creates a string representation of the polygon
     * @return the representation string of the polygon
     * O(?)
     */
    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
     * O(?)
     */
    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
     * O(?)
     */
    public double calcArea() {
        int len = this.listLength();

        if (len < 3)
            return 0;

        double totalSum = 0, sumA = 0, sumB = 0, xa, ya, xb, yb;

        PointNode pointer = this._head, next = this._head;
        while(pointer.getNext() != null) {
            next = pointer.getNext();
            /*xa = pointer.getPoint().getX();
            ya = next.getPoint().getY();
            yb = pointer.getPoint().getY();
            xb = next.getPoint().getX();*/
            sumA = pointer.getPoint().getX() * next.getPoint().getY();
            sumB = pointer.getPoint().getY() * next.getPoint().getX();
            totalSum += sumA - sumB;
            pointer = next;
        }
        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
     * O(?)
     */
    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
     * O(?)
     */
    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
     * O(?)
     */
    public Point getNextVertex(Point p) {
        int len = this.listLength();

        if(len == 0)
            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
     * O(?)
     */
    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 = currentY, 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);
        blockRect.addVertex(topRight, 2);
        blockRect.addVertex(bottomRight, 3);
        blockRect.addVertex(bottomLeft, 4);

        return blockRect;
    }

    //return the length of the list
    private int listLength() {
        int len = 0;
        PointNode temp = this._head;
        while(temp != null) {
            temp = temp.getNext();
            len++;
        }

        return len;
    }
}