5

I have the following Node Class

Class Node {
    private int id;

    public int getId() {
        return this.id;
    }
}

and then create a TreeSet with the Nodes. Next I wanted to find and return a Node object based on id matching. However, every time the findNode() function is returning the next-to-next Node not the next one. I understand it is because of calling the iterator.next() twice. How can call it only once to check with the id value as well as return the object reference. I also tried with by creating a temporary Object reference but again it was the same result.

Class NodeSet {
    Set<Node> set = new TreeSet<Node>();

    public Node findNode(int id) {  
        Iterator<Node> iterator = set.iterator();
        while(iterator.hasNext()) {
            if(iterator.next().getId() == id)               
                return iterator.next();
        }

        return null;                
    }
}
Joarder Kamal
  • 1,387
  • 1
  • 20
  • 28
  • 4
    Why don't you use a Map instead of iterating? – JB Nizet Jul 23 '13 at 09:38
  • @JBNizet: could explain a little more with some example kindly? – Joarder Kamal Jul 23 '13 at 09:43
  • Create a `Map` containing the IDs as keys, and the corresponding Node as values. When you need a node with a given ID, call `Node theNode = map.get(id)`. – JB Nizet Jul 23 '13 at 09:45
  • @JBNizet, what you are suggesting is not related to TreeSet use. Map and Set are two completely different collections. – RaceBase Jul 23 '13 at 09:45
  • @Reddy: don't you think I know that? The OP wants to get nodes by their ID. That's why I suggest using a Map: it's the proper data structure for this usecase. – JB Nizet Jul 23 '13 at 09:46
  • Why reinventing the wheel and thus let a code less clean and less readable with a huge boilerplate. @JB Nizet is right, prefer using a `Map` for this simple lookup. – Mik378 Jul 23 '13 at 09:49
  • @JBNizet I got your point. Thanks for mentioning this. I was using this TreeSet inside a TreeMap. But I could have been also use another TreeMap inside the parent TreeMap as you said. I needed all the elements to be sorted !! Thanks again. – Joarder Kamal Jul 23 '13 at 09:58
  • Possible duplicate: https://stackoverflow.com/questions/7283338/getting-an-element-from-a-set – mwfearnley Jun 13 '17 at 13:24
  • That said, the "possible duplicate" is technically about Sets, not SortedSets, so the answers may not be as appropriate. – mwfearnley Jun 13 '17 at 13:36
  • What's astonishing to me is that there is no "find" or "get" method in TreeSet/SortedSet. I mean they have every other operation like ceiling, floor, higher, and lower, but not a method for equals to the comparator. Is there some reason this doesn't exist? I mean come on man.... – deltamind106 May 31 '22 at 16:50

3 Answers3

24

Edit: The solution proposed here is logarithmic (unlike the accepted answer) and hence is much faster when the number of nodes in a treeset is large.

There is no get method in the Set interface which the class TreeSet implements. Keeping in mind that there exists a complete ordering between the elements of a treeset, a three line hack is as follows:

Object search(TreeSet treeset, Object key) {
    Object ceil  = treeset.ceiling(key); // least elt >= key
    Object floor = treeset.floor(key);   // highest elt <= key
    return ceil == floor? ceil : null; 
}
Debasis
  • 3,680
  • 1
  • 20
  • 23
  • I think that the second `treeset.ceiling(key)` should be replaced by `treeset.floor(key)` – Julien Bourdon Nov 11 '15 at 18:55
  • 4
    Yes, I think that would be correct. I'd also say it would actually be better to just use `floor` and `compareTo`, to save doing two searches. Apart from that, this is the only answer to suggest a logarithmic time solution, so it gets my vote. – mwfearnley Jun 13 '17 at 13:41
  • 1
    this is definitely the best answer, with O(log(n)) complexity unlike linear solutions proposed above. – Abdennacer Lachiheb Jul 15 '17 at 12:58
  • How can we jump from one Object in TreeSet to the next one in order in O(1)? – Nathan B Feb 15 '22 at 10:55
  • @NathanB https://stackoverflow.com/questions/36100224/accessing-next-element-in-treeset-in-java – Debasis Feb 21 '22 at 11:18
9
Class NodeSet {
    Set<Node> set = new TreeSet<Node>();

    public Node findNode(int id) {  
        Iterator<Node> iterator = set.iterator();
        while(iterator.hasNext()) {
            Node node = iterator.next();
            if(node.getId() == id)             
                return node;
        }

        return null;                
    }
}
RaceBase
  • 18,428
  • 47
  • 141
  • 202
  • I've already mentioned "I also tried with by creating a temporary Object reference but again it was the same result." – Joarder Kamal Jul 23 '13 at 09:41
  • I would say, check again what you are expecting. This is correct and works pretty well for what you asked. If you are not getting what you want means, it's your design or logical flaw. – RaceBase Jul 23 '13 at 09:43
  • thanks for telling me to check again. There was small bug in the print() function I was using to debug !! The actual code was a bit messy and didn't able to grab the mistake at the first time. thanks again. – Joarder Kamal Jul 23 '13 at 09:48
  • 6
    This find algorithm uses a linear search -- the advantage of using a `TreeSet` is that search can be done in logarithmic time! You probably want to use a `TreeMap`. – wcochran Dec 07 '15 at 19:22
5

The issue happens here:

        while(iterator.hasNext()) {
            if(iterator.next().getId() == id)               
                return iterator.next();
        }

You call twice iterator.next in the same loop explaining the "next-to-next" issue.

Make a local variable to still reach the same element or better: use the for loop if you have jdk >= 5:

for(Node node: set) {
   if(node.getId() == id) 
     return node;
}

As @JB Nizet suggests in his comment above, a simple Map already implements your code logic by essence, and thus would better fit than a TreeSet and manual check.
More precisely, a TreeMapsorted on Nodes would be relevant. (since it sounds you need the order aspect)

Mik378
  • 21,881
  • 15
  • 82
  • 180