Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

Thread: Collections.binarySearch returns wrong index

  1. #1
    Junior Member
    Join Date
    Feb 2013
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Collections.binarySearch returns wrong index

      final static public Point diagPoint = new Point("308.540978536647", "204.89781897342627");
     
      /**
       * compare points by x,y
       */
      public static final Comparator<Point> pointComp = new Comparator<Point>()
      {
        public int compare(Point p1, Point p2)
        {
          if ((p1.compareToXY(diagPoint) == 0) || (p1.compareToXY(diagPoint) == 0))
          {
            App.diagnose("pointComp result " + p1.compareToXY(p2) + " when compare p1 " + p1 + " to p2 " + p2);
          }
          return p1.compareToXY(p2);    
        }
      };
     
      public Surface3d(Site site, TreeSet<ITriangle> unusedTriangles) throws UnexpectedException
      {
          TreeSet<Point> groundPoints = new TreeSet<Point>(pointComp);
     
          // A. for each point in unusedTriangles, save p into groundPoints
     
          for (ITriangle triangle: unusedTriangles)
          {
            Point[] points = triangle.getPoints();
            for (Point p: points)
            {
              boolean diag = (p.compareToXY(diagPoint) == 0);
              if (diag)
              {
                App.diagnose("checking diagPoint " + p.toXYString() + " in " + triangle);
              }
              if (! groundPoints.contains(p))
              {
                if (diag)
                {
                  App.diagnose("add to groundPoints diagPoint " + p.toXYString());
                }
                groundPoints.add(p);
              }
            } // end for each point in triangle
          } // end for each triangle in roof
     
          // B. for each unusedTriangle get index of each point
          ArrayList<Point> sortedGroundPoints = new ArrayList<>(groundPoints);
     
          for (ITriangle triangle: unusedTriangles)
          {
            Point[] points = triangle.getPoints();
            for (Point p: points)
            {
              int index = Collections.binarySearch(sortedGroundPoints, p, pointComp);
     
              if (index < 0)
              {
                index = -index - 1;
                Point near = null;
                for (int nearIndex = index-10;nearIndex<= index;nearIndex++)
                {
                  if (nearIndex >= 0)
                  {
                    near = sortedGroundPoints.get(nearIndex);
                    App.diagnose("compare diag " + diagPoint.toXYString() + " to nearIndex " + nearIndex + " " + near.toXYString());
                    if (near.compareToXY(diagPoint) == 0)
                    {
                      break;
                    }
                    else
                    {
                      near = null;
                    }
                  }
                }
                throw new UnexpectedException("In groundPoints, at index " + index + " can not find " + p + " from " + triangle + " near " + near); //$NON-NLS-1$
              }
              p = sortedGroundPoints.get(index);
              // groundTriangleIndexBuff.put(index); // save index into TriangleIndexBuff
              // more code saving p into vertexBuff, calculating normals, etc
            }
          }
      }

    Output:
    Surface3d.java(1916) add to groundPoints diagPoint -12445, X=308.540978536647, Y=204.89781897342627
    Surface3d.java(88) pointComp result 1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16499, X=249.456506, Y=307.105268, Z=202.22098700393
    Surface3d.java(88) pointComp result 1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16508, X=301.927425, Y=516.152892, Z=203
    Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16211, X=314.0301017547257, Y=283.1977886190188, Z=204.22315265408673
    Surface3d.java(88) pointComp result 1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16257, X=307.809813, Y=288.475484, Z=203.979338
    Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16244, X=310.643037, Y=273.667287, Z=204
    Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -15278, X=308.540913, Y=239.446042, Z=206.38019490565
    Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -14617, X=308.5409603760091, Y=214.39787824126483, Z=0
    Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -13111, X=308.5409671623528, Y=210.8478560735622, Z=0
    Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -13102, X=308.54097175030347, Y=208.44784106983346, Z=0
    Surface3d.java(1910) checking diagPoint -12423, X=308.540978536647, Y=204.89781897342627 in Contour.ITriangle p1 -12423, p2 -12421, p3 -12422
    Surface3d.java(88) pointComp result 1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16499, X=249.456506, Y=307.105268, Z=202.22098700393
    Surface3d.java(88) pointComp result 1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16508, X=301.927425, Y=516.152892, Z=203
    Surface3d.java(88) pointComp result -1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16211, X=314.0301017547257, Y=283.1977886190188, Z=204.22315265408673
    Surface3d.java(88) pointComp result 1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16257, X=307.809813, Y=288.475484, Z=203.979338
    Surface3d.java(88) pointComp result -1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16244, X=310.643037, Y=273.667287, Z=204
    Surface3d.java(88) pointComp result -1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -14617, X=308.5409603760091, Y=214.39787824126483, Z=0
    Surface3d.java(88) pointComp result -1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -13102, X=308.54097175030347, Y=208.44784106983346, Z=0
    Surface3d.java(88) pointComp result 0 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -12445, X=308.540978536647, Y=204.89781897342627, Z=0
    Surface3d.java(1976) compare diag -30818, X=308.540978536647, Y=204.89781897342627 to nearIndex 301 -11371, X=308.54100531484664, Y=190.8808392888774
    Surface3d.java(1976) compare diag -30818, X=308.540978536647, Y=204.89781897342627 to nearIndex 302 -12439, X=308.540998, Y=194.716293
    Surface3d.java(1976) compare diag -30818, X=308.540978536647, Y=204.89781897342627 to nearIndex 303 -12445, X=308.540978536647, Y=204.89781897342627

    View3D.makeUnusedSurface unexpectedException
    java.rmi.UnexpectedException: In groundPoints, at index 311 can not find -12445, X=308.540978536647, Y=204.89781897342627, Z=207.55448524554507914 from Contour.ITriangle p1 -12447, p2 -12445, p3 -12446 near -12445, X=308.540978536647, Y=204.89781897342627, Z=207.55448524554507914
    at com.neighborhoodinnovations.ThreeD.Surface3d.<init >(Surface3d.java:1987)
    ... more printStackTrace output cut

    Note that Point.pointCompXY returns the correct result. However Collections.binarySearch seems to be ignoring that result.

    Also note that this code seems to work correctly 99.95 percent of the time. Only in this one data set (so far) am I experiencing a problem.

    I am willing to share more code if needed. Any suggestions for further diagnostics?


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,189
    Thanks
    49
    Thanked 2,172 Times in 2,145 Posts

    Default Re: Collections.binarySearch returns wrong index

    Can you make a small, complete program that compiles, executes and shows the problem?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    476
    Thanks
    0
    Thanked 92 Times in 77 Posts

    Default Re: Collections.binarySearch returns wrong index

    I just want to point out, that this line:
    if ((p1.compareToXY(diagPoint) == 0) || (p1.compareToXY(diagPoint) == 0))
    does not look quite right since you are checking for the very same thing twice. I guess this is a typo and it might reveal other errors in your code somewhere, but I am not sure.


    Other then that, it might also be, that your equals and hashCode methods are not synced, and thus your SortedCollection is not set up correctly.

  4. #4
    Junior Member
    Join Date
    Feb 2013
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Collections.binarySearch returns wrong index

    You are correct, it should be

    if ((p1.compareToXY(diagPoint) == 0) || (p2.compareToXY(diagPoint) == 0))

    but that only means I got less diagnostics than what I wanted.

    The equals and compareToXY code are synced. Since I am not using Hash* methods, why would I worry about hashCode?

  5. #5
    Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    476
    Thanks
    0
    Thanked 92 Times in 77 Posts

    Default Re: Collections.binarySearch returns wrong index

    Because the Object API clearly states that hashCode and equals must be synced (when equals returns true, hashCodes must be equal as well). If they are not the behavior of several standard classes is not well defined.
    Furthermore the behavior of Comparators must also be synced with the equals method and return 0 when equals would return true.

  6. #6
    Junior Member
    Join Date
    Feb 2013
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Collections.binarySearch returns wrong index

    The problem is in the data, where points are very close together, but the comparison method only was accurate to 6 decimal places. After upping the accuracy to 9 decimal places, everything sorted correctly and there were no problems.

Similar Threads

  1. Replies: 5
    Last Post: December 1st, 2013, 07:56 PM
  2. Remove at index method for singly linked list... what's wrong?
    By EDale in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2013, 09:12 PM
  3. Replies: 3
    Last Post: August 26th, 2013, 04:41 PM
  4. binarySearch troubles
    By pottsiex5 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 4th, 2011, 11:09 AM
  5. getTimeInMillis() from the Calendar class returns wrong values
    By 16mydream in forum Java Theory & Questions
    Replies: 2
    Last Post: February 16th, 2011, 12:29 PM