package ru.ifmo.nds.domtree;

import ru.ifmo.nds.NonDominatedSorting;

public final class NoPresort extends NonDominatedSorting {
    private Node[] nodes;
    private Node[] rankMergeArray;
    private final boolean useRecursiveMerge;

    public NoPresort(int maximumPoints, int maximumDimension, boolean useRecursiveMerge) {
        super(maximumPoints, maximumDimension);
        nodes = new Node[maximumPoints];
        rankMergeArray = new Node[maximumPoints];
        this.useRecursiveMerge = useRecursiveMerge;
        for (int i = 0; i < maximumPoints; ++i) {
            nodes[i] = new Node(i);
        }
    }

    @Override
    protected void closeImpl() {
        nodes = null;
        rankMergeArray = null;
    }

    @Override
    public String getName() {
        return "Dominance Tree (no presort, " + (useRecursiveMerge ? "recursive merge" : "sequential merge") + ")";
    }

    private static Node merge(Node a, Node b) {
        if (a == null) {
            return b;
        }

        assert b != null;

        Node aPrev = null;
        for (Node aCurr = a; aCurr != null; ) {
            boolean aRemoved = false;
            for (Node bPrev = null, bCurr = b; bCurr != null; ) {
                int compare = Node.dominanceComparison(aCurr, bCurr);
                if (compare > 0) {
                    Node aDel = aCurr;
                    aCurr = aCurr.next;
                    if (aPrev == null) {
                        a = aCurr;
                    } else {
                        aPrev.next = aCurr;
                    }
                    aDel.next = null;
                    bCurr.child = merge(bCurr.child, aDel);
                    aRemoved = true;
                    break;
                } else if (compare < 0) {
                    Node bDel = bCurr;
                    bCurr = bCurr.next;
                    if (bPrev == null) {
                        b = bCurr;
                    } else {
                        bPrev.next = bCurr;
                    }
                    bDel.next = null;
                    aCurr.child = merge(aCurr.child, bDel);
                } else {
                    bPrev = bCurr;
                    bCurr = bCurr.next;
                }
            }
            if (!aRemoved) {
                aPrev = aCurr;
                aCurr = aCurr.next;
            }
        }
        if (a == null) {
            return b;
        } else {
            aPrev.next = b;
            return a;
        }
    }

    @Override
    protected void sortChecked(double[][] points, int[] ranks, int maximalMeaningfulRank) {
        int n = points.length;
        for (int i = 0; i < n; ++i) {
            Node.initialize(nodes[i], points[i]);
        }
        Node tree = mergeAllRecursively(nodes, 0, n);
        for (int rank = 0; tree != null; ++rank) {
            int rankMergeCount = rankAndPutChildrenToMergeArray(tree, ranks, rank);
            tree = mergeAll(rankMergeArray, rankMergeCount, useRecursiveMerge);
        }
    }

    private int rankAndPutChildrenToMergeArray(Node tree, int[] ranks, int rank) {
        int rankMergeCount = 0;
        while (tree != null) {
            ranks[tree.index] = rank;
            if (tree.child != null) {
                rankMergeArray[rankMergeCount] = tree.child;
                ++rankMergeCount;
            }
            tree = tree.next;
        }
        return rankMergeCount;
    }

    private static Node mergeAll(Node[] array, int size, boolean useRecursiveMerge) {
        if (size == 0) {
            return null;
        }
        if (useRecursiveMerge) {
            return mergeAllRecursively(array, 0, size);
        } else {
            Node rv = array[0];
            for (int i = 1; i < size; ++i) {
                rv = merge(rv, array[i]);
            }
            return rv;
        }
    }

    private static Node mergeAllRecursively(Node[] array, int from, int until) {
        if (from + 1 == until) {
            return array[from];
        } else {
            int mid = (from + until) >>> 1;
            return merge(mergeAllRecursively(array, from, mid), mergeAllRecursively(array, mid, until));
        }
    }
}
