package ru.ifmo.nds.ndt;

public abstract class TreeRankNode {
    public abstract TreeRankNode add(double[] point, int rank, Split split, int splitThreshold);

    public abstract int evaluateRank(double[] point, int rank, Split split, int M);

    public abstract int getMaxRank();

    public static final TreeRankNode EMPTY = new EmptyRankNode();

    private static class EmptyRankNode extends TreeRankNode {
        @Override
        public TreeRankNode add(double[] point, int rank, Split split, int splitThreshold) {
            return new TerminalRankNode().add(point, rank, split, splitThreshold);
        }

        @Override
        public int evaluateRank(double[] point, int rank, Split split, int M) {
            return rank;
        }

        @Override
        public int getMaxRank() {
            return -1;
        }
    }

    private static class TerminalRankNode extends TreeRankNode {
        private int size;
        private double[][] points;
        private int[] ranks;
        int maxRank;

        private TerminalRankNode() {
            this.points = null;
            this.size = 0;
            this.ranks = null;
        }

        @Override
        public TreeRankNode add(double[] point, int rank, Split split, int splitThreshold) {
            if (points == null) {
                points = new double[splitThreshold][];
                ranks = new int[splitThreshold];
            }
            if (size == points.length) {
                if (split == null) {
                    // если мы находимся в терминальной в смысле split вершине, то bucket size всегда = 1
                    // то есть будем работаеть только с points[0] и ranks[0]
                    // TODO почему нельзя сразу, если split == null?

                    points[size - 1] = point;
                    ranks[size - 1] = Math.max(ranks[size - 1], rank);
                    maxRank = Math.max(maxRank, rank);

                    return this;
                }
                TerminalRankNode weak = new TerminalRankNode();
                TerminalRankNode good = new TerminalRankNode();
                // actually, nulls are perfect here,
                // but we will not hurt the hearts of those who suffered from NPE
                Split weakSplit = split.weak, goodSplit = split.good;
                int obj = split.coordinate;
                double median = split.value;
                for (int i = 0; i < size; ++i) {
                    if (points[i][obj] < median) {
                        good.add(points[i], ranks[i], goodSplit, splitThreshold);
                    } else {
                        weak.add(points[i], ranks[i], weakSplit, splitThreshold);
                    }
                }
                TreeRankNode rv = new BranchingRankNode(good, weak);
                return rv.add(point, rank, split, splitThreshold);
            } else {
                points[size] = point;
                ranks[size] = rank;
                size++;
                maxRank = Math.max(maxRank, rank);

                return this;
            }
        }

        @Override
        public int evaluateRank(double[] point, int rank, Split split, int M) {
            if (getMaxRank() < rank) {
                return rank;
            }

            pointLoop:
            for (int i = 0; i < size; ++i) { // TODO возможно поменять порядок обхода
                double[] current = points[i];
                if (this.ranks[i] + 1 < rank) {
                    continue;
                }
                // objective 0 is not compared since points are presorted.

                for (int o = M - 1; o > 0; --o) {
                    if (current[o] > point[o]) {
                        continue pointLoop;
                    }
                }

                rank = Math.max(this.ranks[i] + 1, rank);
            }
            return rank;
        }

        @Override
        public int getMaxRank() {
            return maxRank;
        }
    }

    private static class BranchingRankNode extends TreeRankNode {
        private TreeRankNode good, weak;
        private int maxRank;

        private BranchingRankNode(TreeRankNode good, TreeRankNode weak) {
            this.weak = weak;
            this.good = good;
            this.maxRank = Math.max(good.getMaxRank(), weak.getMaxRank());
        }

        @Override
        public TreeRankNode add(double[] point, int rank, Split split, int splitThreshold) {
            maxRank = Math.max(rank, maxRank);
            if (point[split.coordinate] >= split.value) {
                weak = weak.add(point, rank, split.weak, splitThreshold);
            } else {
                good = good.add(point, rank, split.good, splitThreshold);
            }
            return this;
        }

        @Override
        public int evaluateRank(double[] point, int rank, Split split, int M) {
            if (getMaxRank() < rank) {
                return rank;
            }

            int resultRank = -1;
            if (weak != null && point[split.coordinate] >= split.value) {
                resultRank = weak.evaluateRank(point, rank, split.weak, M);
            }

            if (good != null) {
                resultRank = good.evaluateRank(point, Math.max(resultRank, rank), split.good, M);
            }

            return Math.max(resultRank, rank);
        }

        @Override
        public int getMaxRank() {
            return maxRank;
        }
    }
}

@@ -1747,16 +1747,271 @@
  null?%0A%0A
+                    // TODO %D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F %D0%BD%D1%83%D0%B6%D0%BD%D0%B0 ?%0A                    points%5B0%5D = point;%0A                    ranks%5B0%5D = Math.max(ranks%5B0%5D, rank);%0A                    maxRank = Math.max(maxRank, rank);%0A                    size = 1;%0A                    //%0A%0A//
         
@@ -2040,32 +2040,34 @@
 e - 1%5D = point;%0A
+//
                 
@@ -2113,32 +2113,34 @@
 ze - 1%5D, rank);%0A
+//
                 

Add small optimisation