Treetset Contains, Remove Not Working

Thanhpv

New Member
30/3/18
15
4
3
34
Chào các bạn.
Mình có Class Segment như sau, kèm theo SegmentTest.

Code:
setTest()
không passed trong khi
Code:
setTest2()
passed. Điều này làm mình bối rối lần mấy hrs rồi mà chưa hiểu vì sao? Ai đó có thể xem giúp mình với.

Code:
public interface Point extends Comparable {
 
void setX(double value);
 
void setY(double value);
 
void setZ(double value);
 
double getX();
 
double getY();
 
double getZ();
 
default void set(double x, double y, double z) {
setX(x);
setY(y);
setZ(z);
}
 
default void set(double x, double y) {
setX(x);
setY(y);
}
 
 
 
default boolean equals2D(Point other) {
if (getX() != other.getX()) {
return false;
}
if (getY() != other.getY()) {
return false;
}
return true;
}
 
default boolean equals3D(Vector3d other) {
return (getX() == other.getX()) && (getY() == other.getY()) &&
((getZ() == other.getZ()) ||
(Double.isNaN(getZ()) && Double.isNaN(other.getZ())));
}
 
@Override
default int compareTo(Point other) {
 
if (getX() < other.getX()) return (-1);
if (getX() > other.getX()) return 1;
if (getY() < other.getY()) return (-1);
if (getY() > other.getY()) return 1;
return 0;
}
 
 
 
 
Point clone();
 
/**
* Check if 3 points is clockwise
*
* @param a
* @param b
* @param c
* @return > 0 if clockwise
* < 0 if counter clockwise
* 0 if collinear
*/
static double cw(Point a, Point b, Point c) {
return (b.getX() - a.getX()) * (c.getY() - a.getY()) - (c.getX() - a.getX()) * (b.getY() - a.getY());
 
}
 
// is a-b-c collinear?
static boolean collinear(Point a, Point b, Point c) {
return cw(a, b, c) == 0;
}
 
// return Euclidean distance between this point and that point
default double distanceTo(Point that) {
if (that == null) return Double.POSITIVE_INFINITY;
double dx = this.getX() - that.getX();
double dy = this.getY() - that.getY();
return Math.hypot(dx, dy);
}
 
 
}
Implementation của Point:


Code:
public class PointImpl implements Point {
 
private double x, y, z;
 
public PointImpl(double x, double y){
this(x, y, 0);
}
 
public PointImpl(double x, double y, double z){
this.x = x;
this.y = y;
this.z = z;
}
 
@Override
public void setX(double value) {
x = value;
}
 
@Override
public void setY(double value) {
y = value;
}
 
@Override
public void setZ(double value) {
z = value;
}
 
@Override
public double getX() {
return x;
}
 
@Override
public double getY() {
return y;
}
 
@Override
public double getZ() {
return z;
}
 
@Override
public Point clone() {
return new PointImpl(x, y, z);
 
}
 
 
 
public String toString(){
return "("+ getX() + ", "+getY() + ", "+getZ()+")";
}
 
 
}
Code:
/**
* Line segment of two points.
*/
public class Segment implements Comparable<Segment> {
private Point start;
private Point end;
private double value;
public Point getStart() {
return start;
}
public void setStart(Point start) {
this.start = start;
}
public Point getEnd() {
return end;
}
public void setEnd(Point end) {
this.end = end;
}
 
/**
* Checking if two segments hasIntersects, including degeneracies of parallel and end points hasIntersects.
*
* @param other
* @return
*/
public boolean hasIntersects(Segment b) {
Segment a = this;
 
if (Point.cw(a.getStart(), a.getEnd(), b.getStart()) * Point.cw(a.getStart(), a.getEnd(), b.getEnd()) > 0.0)
return false;
if (Point.cw(b.getStart(), b.getEnd(), a.getStart()) * Point.cw(b.getStart(), b.getEnd(), a.getEnd()) > 0.0)
return false;
//Check for case two segments are collinear
return !(
Math.min(b.getStart().getX(), b.getEnd().getX()) > Math.max(a.getStart().getX(), a.getEnd().getX())
|| Math.max(b.getStart().getX(), b.getEnd().getX()) < Math.min(a.getStart().getX(), a.getEnd().getX())
);
}
/**
* Check if two segments hasIntersects at an interior point of both.
*
* @param b
* @return
*/
public boolean hasInteriorIntersects(Segment b) {
Segment a = this;
if (Point.cw(a.getStart(), a.getEnd(), b.getStart()) * Point.cw(a.getStart(), a.getEnd(), b.getEnd()) >= 0.0)
return false;
if (Point.cw(b.getStart(), b.getEnd(), a.getStart()) * Point.cw(b.getStart(), b.getEnd(), a.getEnd()) >= 0.0)
return false;
return true;
}
public Point intersects(Segment seg) {
Point a = getStart();
Point b = getEnd();
Point c = seg.getStart();
Point d = seg.getEnd();
if (a.equals2D(c))
return a.clone();
if (a.equals2D(d))
return a.clone();
if (b.equals2D(c))
return b.clone();
if (b.equals2D(d))
return b.clone();
double r = ((a.getY() - c.getY()) * (d.getX() - c.getX()) - (a.getX() - c.getX()) * (d.getY() - c.getY()))
/ ((b.getX() - a.getX()) * (d.getY() - c.getY()) - (b.getY() - a.getY()) * (d.getX() - c.getX()));
double s = ((a.getY() - c.getY()) * (b.getX() - a.getX()) - (a.getX() - c.getX()) * (b.getY() - a.getY()))
/ ((b.getX() - a.getX()) * (d.getY() - c.getY()) - (b.getY() - a.getY()) * (d.getX() - c.getX()));
 
if (r <= 1 && r >= 0 && s <= 1 && s >= 0) {
double x = a.getX() + r * (b.getX() - a.getX());
double y = a.getY() + r * (b.getY() - a.getY());
return new PointImpl(x, y, 0);
}
return null;
}
 
public Segment(Point p1, Point p2) {
if (p1.compareTo(p2) == -1) {
start = p1;
end = p2;
} else {
start = p2;
end = p1;
}
this.value = first().getY();
}
public Point first() {
return start;
}
public Point second() {
return end;
}
public void calculateValue(double xPos) {
double x1 = this.first().getX();
double y1 = this.first().getY();
double x2 = this.second().getX();
double y2 = this.second().getY();
this.value = y1 + (((y2 - y1) / (x2 - x1)) * (xPos - x1));
}
public void setValue(double value) {
this.value = value;
}
public double getValue() {
return this.value;
}
@Override
public int compareTo(Segment s2) {
if (this.equals(s2))
return 0;
if (getValue() < s2.getValue()) {
return (-1);
}
if (getValue() > s2.getValue()) {
return 1;
} else
return -1;
}
public Segment clone() {
return new Segment(getStart().clone(), getEnd().clone());
}
@Override
public boolean equals(Object ob) {
if (!(ob instanceof Segment))
return false;
if (super.equals(ob))
return true;
Segment seg = (Segment) ob;
if (seg.first().equals2D(first()) && seg.second().equals2D(second()))
return true;
return false;
}
 
}
Code:
import org.junit.Assert;
import org.junit.Test;
import java.util.TreeSet;
import java.util.Random;
public class SegmentTest {
@Test
public void structureTest() {
Point p1, p2;
Segment seg1 = new Segment(
p1 = new PointImpl(0, 0, 0),
p2 = new PointImpl(100, 100, 0)
);
Assert.assertTrue(seg1.equals(seg1));
Assert.assertTrue(seg1.equals(seg1.clone()));
Assert.assertTrue(seg1.compareTo(seg1) == 0);
Assert.assertTrue(seg1.compareTo(seg1.clone()) == 0);
Assert.assertTrue(seg1.first().equals(p1));
Assert.assertTrue(seg1.second().equals(p2));
Point p3 = Vector3d.xy(0, 100);
Point p4 = Vector3d.xy(100, 0);
Segment seg2 = new Segment(
p3,
p4
);
Assert.assertTrue(seg2.first().equals(p3));
Assert.assertTrue(seg2.second().equals(p4));
Assert.assertFalse(seg1.equals(seg2));
 
}
@Test
public void checkInteriorIntersect() {
Point p1, p2;
Segment seg1 = new Segment(
p1 = new PointImpl(0, 0, 0),
p2 = new PointImpl(100, 100, 0)
);
Segment seg2 = new Segment(
new PointImpl(0, 100, 0),
new PointImpl(100, 0, 0)
);
Segment seg3 = new Segment(
p2,
new PointImpl(100, 0, 0)
);
Segment seg4 = new Segment(
new PointImpl(101, 101, 0),
new PointImpl(150, 150, 0)
);
Segment seg5 = new Segment(
new PointImpl(100, 100, 0),
new PointImpl(150, 150, 0)
);
Segment seg6 = new Segment(
p1 = new PointImpl(0, 10, 0),
p2 = new PointImpl(100, 110, 0)
);
Segment seg7 = new Segment(
p1 = new PointImpl(-10, -10, 0),
p2 = new PointImpl(110, 110, 0)
);
//Interior intersect
Assert.assertTrue(seg1.hasInteriorIntersects(seg2));
//Two segments on same place
Assert.assertFalse(seg1.hasInteriorIntersects(seg1.clone()));
//Intersects at end points
Assert.assertFalse(seg1.hasInteriorIntersects(seg3));
//Collinear but not hasIntersects
Assert.assertFalse(seg1.hasInteriorIntersects(seg4));
//Collinear and hasIntersects at end point
Assert.assertFalse(seg1.hasInteriorIntersects(seg5));
//Parallel without any common point.
Assert.assertFalse(seg1.hasInteriorIntersects(seg6));
//A segment lines on an other.
Assert.assertFalse(seg1.hasInteriorIntersects(seg7));
}
 
@Test
public void checkIntersect() {
Point p1, p2;
Segment seg1 = new Segment(
p1 = new PointImpl(0, 0, 0),
p2 = new PointImpl(100, 100, 0)
);
Segment seg2 = new Segment(
new PointImpl(0, 100, 0),
new PointImpl(100, 0, 0)
);
Segment seg3 = new Segment(
p2,
new PointImpl(100, 0, 0)
);
Segment seg4 = new Segment(
new PointImpl(101, 101, 0),
new PointImpl(150, 150, 0)
);
Segment seg5 = new Segment(
new PointImpl(100, 100, 0),
new PointImpl(150, 150, 0)
);
Segment seg6 = new Segment(
new PointImpl(0, 10, 0),
new PointImpl(100, 110, 0)
);
Segment seg7 = new Segment(
new PointImpl(-10, -10, 0),
new PointImpl(110, 110, 0)
);
//Interior intersect
Assert.assertTrue(seg1.hasIntersects(seg2));
//Two segments on same place
Assert.assertTrue(seg1.hasIntersects(seg1.clone()));
//Intersects at end points
Assert.assertTrue(seg1.hasIntersects(seg3));
//Collinear but not hasIntersects
Assert.assertFalse(seg1.hasIntersects(seg4));
//Collinear and hasIntersects at end point
Assert.assertTrue(seg1.hasIntersects(seg5));
//Parallel without any common point.
Assert.assertFalse(seg1.hasIntersects(seg6));
//A segment lines on an other.
Assert.assertTrue(seg1.hasIntersects(seg7));
Assert.assertTrue(seg1.intersects(seg2).equals2D(new PointImpl(50, 50, 0)));
Assert.assertTrue(seg1.intersects(seg3).equals2D(p2));
Assert.assertTrue(seg1.intersects(seg5).equals2D(new PointImpl(100, 100, 0)));
Assert.assertNull(seg1.intersects(seg4));
}
@Test
public void setTest(){
TreeSet<Segment> STATUS = new TreeSet<>();
Segment seg1 = new Segment(
new PointImpl(0, 0),
new PointImpl(100, 100)
);
Segment seg2 = new Segment(
new PointImpl(0, 100),
new PointImpl(100, 0)
);
Segment seg3 = new Segment(
new PointImpl(-20, 0),
new PointImpl(-50, 100)
);
Segment seg4 = new Segment(
new PointImpl(120, 0),
new PointImpl(150, 150)
);
STATUS.add(seg1);
STATUS.add(seg2);
STATUS.add(seg3);
STATUS.add(seg4);
for (Segment s : STATUS) {
System.out.println(s);
}
Assert.assertTrue(STATUS.contains(seg2));
Assert.assertTrue(STATUS.remove(seg2));
Assert.assertFalse(STATUS.contains(seg2));
}
@Test
public void setTest2() {
TreeSet STATUS = new TreeSet<>();
double min = -190;
double max = 850;
Segment[] s = new Segment[100];
for( int i = 0; i < 100; i++) {
s[i] = new Segment(new PointImpl(rand(min, max), rand(min, max)), new PointImpl(rand(min, max), rand(min, max)));
STATUS.add(s[i]);
}
//contain test
for( int i = 0; i < 100; i++) {
Assert.assertTrue(STATUS.contains(s[i]));
}
//Remove test
for( int i = 20; i < 40; i++) {
STATUS.remove(s[i]);
Assert.assertFalse(STATUS.contains(s[i]));
}
Assert.assertTrue(STATUS.size() == 80);
 
}
private static double rand(double range_min, double range_max) {
Random r = new Random();
return range_min + (r.nextDouble() * (range_max - range_min));
}
 
}
 

Joe

Thành viên VIP
21/1/13
2,686
1,243
113
Your codes are incomplete and contain NON-STANDARD APIs which cause problems for those who want to verify your codes.
Examples: classes of junit or the method:
PHP:
  symbol:   method xy(int,int)
  location: class Vector3d
Further, the clone method should be an implementation of Cloneable interface. Example:
PHP:
public class PointImpl implements Point, Cloneable {
  ...
  public PointImpl clone() throws CloneNotSupportedException { 
	return (PointImpl) super.clone();
  }
  ...
 
Sửa lần cuối:

Thanhpv

New Member
30/3/18
15
4
3
34
Your codes are incomplete and contain NON-STANDARD APIs which cause problems for those who want to verify your codes.
Examples: classes of junit or the method:
PHP:
  symbol:   method xy(int,int)
  location: class Vector3d
Further, the clone method should be an implementation of Cloneable interface. Example:
PHP:
public class PointImpl implements Point, Cloneable {
  ...
  public PointImpl clone() throws CloneNotSupportedException {
	return (PointImpl) super.clone();
  }
  ...
Many thanks, Joe.

I am sorry. I tried to remove Vector3d to simplify the test case but still missed it here.
The problem was my implementation of Comparable interface. The method equals(ob) and compareTo(ob) argued.
Fixed already.

Glad to see you around.
 
  • Like
Reactions: Joe