src/main/java/com/thealgorithms/divideandconquer/SkylineAlgorithm.java - master - NikolayIvkin/TheAlgorithms

src/main/java/com/thealgorithms/divideandconquer/SkylineAlgorithm.java
184 строки6 KB
acbin
style: format code (#4212)
09 июн 2023, 13:52
09 июн 2023, 13:5200282ef
package com.thealgorithms.divideandconquer;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author dimgrichr
 * <p>
 * Space complexity: O(n) Time complexity: O(nlogn), because it is a divide and
 * conquer algorithm
 */
public class SkylineAlgorithm {

    private ArrayList<Point> points;

    /**
     * Main constructor of the application. ArrayList points gets created, which
     * represents the sum of all edges.
     */
    public SkylineAlgorithm() {
        points = new ArrayList<>();
    }

    /**
     * @return points, the ArrayList that includes all points.
     */
    public ArrayList<Point> getPoints() {
        return points;
    }

    /**
     * The main divide and conquer, and also recursive algorithm. It gets an
     * ArrayList full of points as an argument. If the size of that ArrayList is
     * 1 or 2, the ArrayList is returned as it is, or with one less point (if
     * the initial size is 2 and one of it's points, is dominated by the other
     * one). On the other hand, if the ArrayList's size is bigger than 2, the
     * function is called again, twice, with arguments the corresponding half of
     * the initial ArrayList each time. Once the flashback has ended, the
     * function produceFinalSkyLine gets called, in order to produce the final
     * skyline, and return it.
     *
     * @param list, the initial list of points
     * @return leftSkyLine, the combination of first half's and second half's
     * skyline
     * @see Point
     */
    public ArrayList<Point> produceSubSkyLines(ArrayList<Point> list) {
        // part where function exits flashback
        int size = list.size();
        if (size == 1) {
            return list;
        } else if (size == 2) {
            if (list.get(0).dominates(list.get(1))) {
                list.remove(1);
            } else {
                if (list.get(1).dominates(list.get(0))) {
                    list.remove(0);
                }
            }
            return list;
        }

        // recursive part of the function
        ArrayList<Point> leftHalf = new ArrayList<>();
        ArrayList<Point> rightHalf = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            if (i < list.size() / 2) {
                leftHalf.add(list.get(i));
            } else {
                rightHalf.add(list.get(i));
            }
        }
        ArrayList<Point> leftSubSkyLine = produceSubSkyLines(leftHalf);
        ArrayList<Point> rightSubSkyLine = produceSubSkyLines(rightHalf);

        // skyline is produced
        return produceFinalSkyLine(leftSubSkyLine, rightSubSkyLine);
    }

    /**
     * The first half's skyline gets cleared from some points that are not part
     * of the final skyline (Points with same x-value and different y=values.
     * The point with the smallest y-value is kept). Then, the minimum y-value
     * of the points of first half's skyline is found. That helps us to clear
     * the second half's skyline, because, the points of second half's skyline
     * that have greater y-value of the minimum y-value that we found before,
     * are dominated, so they are not part of the final skyline. Finally, the
     * "cleaned" first half's and second half's skylines, are combined,
     * producing the final skyline, which is returned.
     *
     * @param left the skyline of the left part of points
     * @param right the skyline of the right part of points
     * @return left the final skyline
     */
    public ArrayList<Point> produceFinalSkyLine(ArrayList<Point> left, ArrayList<Point> right) {
        // dominated points of ArrayList left are removed
        for (int i = 0; i < left.size() - 1; i++) {
            if (left.get(i).x == left.get(i + 1).x && left.get(i).y > left.get(i + 1).y) {
                left.remove(i);
                i--;
            }
        }

        // minimum y-value is found
        int min = left.get(0).y;
        for (int i = 1; i < left.size(); i++) {
            if (min > left.get(i).y) {
                min = left.get(i).y;
                if (min == 1) {
                    i = left.size();
                }
            }
        }

        // dominated points of ArrayList right are removed
        for (int i = 0; i < right.size(); i++) {
            if (right.get(i).y >= min) {
                right.remove(i);
                i--;
            }
        }

        // final skyline found and returned
        left.addAll(right);
        return left;
    }

    public static class Point {

        private int x;
        private int y;

        /**
         * The main constructor of Point Class, used to represent the 2
         * Dimension points.
         *
         * @param x the point's x-value.
         * @param y the point's y-value.
         */
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        /**
         * @return x, the x-value
         */
        public int getX() {
            return x;
        }

        /**
         * @return y, the y-value
         */
        public int getY() {
            return y;
        }

        /**
         * Based on the skyline theory, it checks if the point that calls the
         * function dominates the argument point.
         *
         * @param p1 the point that is compared
         * @return true if the point wich calls the function dominates p1 false
         * otherwise.
         */
        public boolean dominates(Point p1) {
            // checks if p1 is dominated
            return ((this.x < p1.x && this.y <= p1.y) || (this.x <= p1.x && this.y < p1.y));
        }
    }

    /**
     * It is used to compare the 2 Dimension points, based on their x-values, in
     * order get sorted later.
     */
    class XComparator implements Comparator<Point> {

        @Override
        public int compare(Point a, Point b) {
            return Integer.compare(a.x, b.x);
        }
    }
}