Issue with "remove" method

[mgrutten]

Some contents of the tree are unexpectedly disappearing during repeated calls to "remove". I have a simple example:

    private static class SimpleXY {
        private final double x;
        private final double y;

        public SimpleXY(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public double getX() {
            return x;
        }

        public double getY() {
            return y;
        }
    }

    private static class SimpleDistance implements DistanceFunction<SimpleXY> {

        @Override
        public double getDistance(SimpleXY pos1, SimpleXY pos2) {
            double xDiff = pos1.getX() - pos2.getX();
            double yDiff = pos1.getY() - pos2.getY();
            return Math.sqrt(xDiff * xDiff + yDiff * yDiff);
        }
    }


    @Test
    void testRemove() {

        int nodeSize = 2;
        int numEntries = 4;
        List<SimpleXY> simpleXYList = new ArrayList<>(numEntries);
        Random random = new Random(0);

        for (int i = 0; i < numEntries; ++i) {
            simpleXYList.add(new SimpleXY(random.nextDouble(), random.nextDouble()));
        }

        final VPTree<SimpleXY, SimpleXY> vpTree = new VPTree<>(new SimpleDistance(),
                new SamplingMedianDistanceThresholdSelectionStrategy<>(
                        SamplingMedianDistanceThresholdSelectionStrategy.DEFAULT_NUMBER_OF_SAMPLES),
                nodeSize, simpleXYList);

        for (final SimpleXY s : simpleXYList) {
            System.out.println(vpTree.size());

            if (!vpTree.remove(s)) {
                throw new RuntimeException("Entry not removed");
            }
        }

    }

which has the following output:

4
0

java.lang.RuntimeException: Entry not removed

[mgrutten]

I think I found the bug. In the anneal method, where one of the children is empty, these lines

            if (closerSize == 0 || fartherSize == 0) {
                // One of the child nodes has become empty, and needs to be pruned.
                this.points = new ArrayList<>(closerSize + fartherSize);
                this.addAllPointsToCollection(this.points);

mean that the test for this.points == null in addAllPointsToCollection fails. Something like this works

            if (closerSize == 0 || fartherSize == 0) {
                // One of the child nodes has become empty, and needs to be pruned.
                ArrayList<E> children = new ArrayList<>(closerSize + fartherSize);
                this.addAllPointsToCollection(children);
                this.points = children;

[jchambers]

I think you're right and will follow up shortly.

It's funny—I was actually thinking the other day that the "anneal" process is so complicated and inefficient that it really ought to change or go away. A challenge for another time, though.

[mgrutten]

Thanks!

"anneal" would be a lot simpler if you didn't need to worry about points being removed from the tree.

Just to make things a bit more complicated ... I was thinking a bit more about the pruning logic. It's possible that a new vantage point could be chosen in that step? When you construct the tree every vantage point is one of the points inserted into the tree. That won't be the case when you start removing things?