How come Java's TreeSet has no get() method?

Question

What if I want to retrieve and update objects that stored in a TreeSet?

The reason I'm asking, is that I want to be able to maintain some data stracture that will store Students. I want it to be sorted (by grades - which is an instance variable of Student), and - it needs to be kept sorted even after I update one (or more) grade(s) as well.

So, after briefly looking over Java's collections, I decided to go with TreeSet and set a comparator that compares two students by their grades. problem is, I just found out that TreeSet has no get() method!

Any help and suggestions would be greatly appreciated.

Answer 1

What would you expect a get() method on a Set to do?

• Sets are not indexed, so a get(int index) makes no sense. (Use a List if you want to get elements by index).
• get(Object obj) would also not make sense, because you'd have the object that you're trying to get already.
• There is already a contains() method to check if a Set contains an object.
• You can iterate over a Set if you want to do something with all elements in the set.

Answer 2

You can retrieve the elements from the treeset by using an Iterator. You can try something like this:

Iterator<Integer> it = treeSet.iterator();

Integer current = 0;
while(it.hasNext() ) {
current = it.next();

}

Hope this helps.

Answer 3

I do have a case where I use a two TreeSets (because they are faster in searches). One of these trees is huge, and the objects in the trees are different, so I create a mock object (of Type 2, second tree) that has the fields used to sort, using data from an object from the small tree and check if there is a counterpart on the second. Now I need to check a value from the object found in the second tree to add value on a report.

Using an iterator, instead of a binary search to retrieve the object I need, defeats the purpose of using a binary tree. The second tree is 5GB plus, finding matchings with data in the first tree (200MB). I need a search strategy that makes sense for this huge amount of data, therefore I chose a Binary Search tree. Entries are unique.

Answer 4

Usually, you will not want to retrieve an element in a set when you already have it. You might to remove your element from a set, or know if it belongs to a set, thats all. Know want you want to do is to index your students by grade, so the index is the grade, not the object itself. Map is the solution.

If I were you, I would use the following structure which retrieves all students with the same grade quickly (they are sorted by grades too) :

private SortedMap<Integer,Set<Student>> _studentsByGrade = new TreeMap<Integer,Set<Student>>();

public void updateStudent(Student student, int oldGrade, int newGrade)
{
  getOrCreateContainer(oldGrade).remove(student);
  getOrCreateContainer(newGrade).add(student);
  student.setGrade(newGrade);
}

public Set<Student> getOrCreateContainer(int grade)
{
  Set<Student> set = _studentsByGrade.get(grade);
  if(set==null)
  {
    set = new HashSet<Student>();
    _studentsByGrade.put(grade, set);
  }
  return set;
}

Don't forget to overload the equals and hashcode in your Student class to make it work correctly.

You might also want to check the cqengine library if you want to perform java indexations easily and fast, but the solution presented above is just ok for your usage.

Answer 5

The TreeSet is sorted upon insertion. If you order by students' grades and modify them after being added, the items are no longer sorted (same order as before).

The TreeSet also does not use equals() to determine if an element is already added, but uses the comparator instead (same order = same item). So if two students have the same grades, only one of them is added. From Javadoc:

TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.

Instead of using TreeSet, you can use a HashSet and sort the students by grade whenever you need them (create a new List containing the students, sort it and iterate over it).

Answer 6

There is indeed no method get by reference or get by index. However, there is a simple way to build the get by reference method. This can be achieved using the method boolean contains(E input) and E ceiling(E input). In fact, according to the Javadoc of the ceiling method :

Returns the least element in this set greater than or equal to the given element, or {@code null} if there is no such element.

So if we know beforehand that the element is in the set, then a call to ceiling is guaranteed to return the element that is equal to the input.

import java.util.Comparator;
import java.util.TreeSet;

public class ExtendedTreeSet<E> extends TreeSet<E> {

  public ExtendedTreeSet(Comparator<? super E> comparator) {
    super(comparator);
  }

  public E get(E input) {
    return this.contains(input) ? this.ceiling(input) : null;
  }
}

Answer 7

You can iterate the tree to retrieve its objects. What about NavigableSet? there are methods for short distance navigation, as

E ceiling(E e) E floor(E e)
E higher(E e) E lower(E e)

Answer 8

This is the answer to the problem I found for myself but I thought there should be a get(elem) for sets, but as you know, there is not.

Here you go:

set.subSet(elem,true,elem,true).floor(elem);

This returns you the first object that equals the one you're looking for.

NOTE: elem must be equals with the element you are looking for and you get the object you want OR assign a comparator to the set that matches them as equals.

---

I was surprised nobody came up with it before.

Thumbs up needed :D

Answer 9

If it contains the exact object the floor will return the exact object which you are looking for.

if(set.contains(searchingObject)) {
   addonPartNumber =  p.floor(searchingObject);
}

Answer 10

You may also use for-each to get all elements inside TreeSet.

TreeSet<String> words = new TreeSet<String>();
for(String w : words) {
    System.out.println(w);
}

You may perform iteration to copy the unique words from TreeSet into Lists, which gives you the privilege to use get();

Hope, it helped.

Answer 11

The most efficient way to get an element by key (being the key and the value the same thing in this case) would be:

A get(A a)
{
    var res = tree.floor(a);
    if (a.compareTo(res) == 0)
    {
        return res;
    }
    return null;
}