Interesting CS problem. Need help.

[xtrmi]

I am working on implementing the plane sweep algorithm to solve the closest points problem and it works, but about 10/1000 times I get the wrong answer. The instructions I'm following say to have an array of x coordinates sorted and use a TreeSet to sort the points inside the strip by their y coordinates. I'm getting errors when I try to add two points to the BST and they have the same Y coordinate. I've been hitting my head on the wall for a while now. Does anybody have any suggestions or hints?

[pbrockway2]

Perhaps you could post some brief code to illustrate the problem?

When I first used TreeSet I was bitten by the requirement stated in the API documentation that "the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface."

Suppose I had a TreeSet made from a comparator that just compared two points' y-coords and return zero if the y-coords were equal. What would happen when I added two distimct points with the same y-coord to the set?

import java.awt.Point;
import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSetEg {

    static Comparator<Point> yCoordComp = new Comparator<Point>() {
        public int compare(Point o1, Point o2) {
            return o1.y - o2.y;
        }
    };
	
    public static void main(String[] args) {
        SortedSet<Point> set = new TreeSet<Point>(yCoordComp);
		
        set.add(new Point(0, 42));
        set.add(new Point(666, 42));

        System.out.println("size=" + set.size());
    }
}

This may or may not be your problem. Hard to say without knowing what your problem is.