# Treetset Contains, Remove Not Working

#### Thanhpv

##### New Member
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)
);
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)));
}
//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
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
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.