TreeSet

Question

I have a TreeSet<Floor> object which stores floors to be visited by an elevator. Floor is an abstract class which is extended by concrete floor class e.x FloorOne, FloorTwo etc. As per the logic my TreeSet<Floor> should store only one instance of each Floor subtype but instead I am able to insert multiple instances of each subtypes. Floor class implements Comparable so I can sort floors in TreeSet<Floor> as per their number. Below is the code for class Floor

public abstract class Floor implements Comparable<Floor>{

    protected int floorNo;
    public abstract void floorVisited();
    public int getFloorNo() {
        return floorNo;
    }   
    @Override
    public int compareTo(Floor floor) {
        return this.getFloorNo() > floorButton.getFloorNo() ? 1 : -1;
    }
}

Code for one of the subtype:

public class FloorOne extends Floor{

    public FloorOne(){
        floorNo = 1;
    } 
    @Override
    public void floorVisited() {
        System.out.println("Floor No. " + floorNo + " was visited");
    }
}

adding floors to TreeSet<Floor> by calling addFloor() method of ElevatorController.

controller.addFloor(new FloorFour());
controller.addFloor(new FloorFour());
controller.addFloor(new FloorTwo());

addFloor() method in ElevatorController.

private TreeSet<Floor> travelUpwards;
private TreeSet<Floor> travelDownwards;

public void addFloor(Floor floor) {

    if (floor.getFloorNo() > currentFloor.getFloorNo()) {
        travelUpwards.add(floor);
    } else if (floor.getFloorNo() < currentFloor.getFloorNo()) {
        travelDownwards.add(floor);
    }
}

Output I'm getting is:

Floor No. 2 was visited
Floor No. 4 was visited
Floor No. 4 was visited

As per my understanding a new instance of object FloorFour is created when I call addFloor(new FloorFour()) and that is why TreeSet<Floor> do not consider them as duplicate. But is there a way I can stop insertion of same floor more than once.

Your compareTo method is wrong. You should return the difference between the floors — DeiAndrei, Sep 26 '14 at 11:42
Using a Set to store a data structure so obviously ordered as floors of a building doesn't seem like a good idea to me... — Alexis Dufrenoy, Sep 26 '14 at 11:42
Your comparator does not correctly handle the case where floor numbers are equal — Chris, Sep 26 '14 at 11:44
@AlexisDufrenoy @assylias - assylias, I wanted your opinion on this too. I considered `TreeSet` and `PriorityQueue`, because I need some natural ordering for floors in `UpwaredTravel' and `DownwardTravel` lists. The reason I chose `TreeSet` is because it does not allow duplicate entries which would otherwise be a great overhead as every time someone request a floor, we will have to check the respective list if it already has a request for that floor. In case of `PriorityQueue` this overhead was the reason for picking `TreeSet` over `PriorityQueue`. what you guys think could be a better pick. — Meena Chaudhary, Sep 26 '14 at 19:02
@MeenaChaudhary Why not a List? Your lift is like an index on a sorted list of floors... — Alexis Dufrenoy, Sep 27 '14 at 07:53
@AlexisDufrenoy for two reasons. First, `Lists` do not allow natural ordering so we have to call `Collections.sort(list)` every time a floor is added. And secondly, `Lists` allow duplicate elements hence will have to check list to make sure each floor is added only once. which is a overhead. — Meena Chaudhary, Sep 30 '14 at 07:48
@MeenaChaudhary: You're wrong about the ordering. The Java API defines a List as "an ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list". Which means if you add a floor on top of the others (hence, at the end of the list), you have the guarantee it's where you will find it. The elements keep the order you define. You're right about the duplicates, though. — Alexis Dufrenoy, Sep 30 '14 at 08:06

score 2 · Answer 1 · answered Sep 26 '14 at 11:48

2

Having a correct implementation of the compareTo() method would probably solve your problem.

@Override
public int compareTo(Floor floor) {
    return this.getFloorNo() - floor.getFloorNo();
}

answered Sep 26 '14 at 11:48

DeiAndrei

947
6
16

6

Although unlikely in this example, the subtraction could overflow. `return Integer.compare(this.getFloorNo(), floor.getFloorNo());` does not overflow. – assylias Sep 26 '14 at 11:51
http://stackoverflow.com/questions/2728793/java-integer-compareto-why-use-comparison-vs-subtraction for details. – Joe Sep 26 '14 at 11:53

score 2 · Answer 2 · answered Sep 26 '14 at 11:48

@Override
public int compareTo(Floor floor) {
    return this.getFloorNo() > floorButton.getFloorNo() ? 1 : -1;
}

This can never return zero, so it will never indicate that two floors are equal. You should ensure you return zero when they are equal, rather than -1.

score 2 · Answer 3 · answered Sep 26 '14 at 12:07

Your compareTo method is wrong - it never allows floors to be "equal", and thus breaks the general contract of Java's compareTo method.

Since the floor number is an int, instead of reinventing the wheel, you should just use java.lang.Integer.compare(int, int):

@Override
public int compareTo(Floor floor) {
    return Integer.compare(this.getFloorNo(), floor.getFloorNo());
}

3 Answers3