Tuesday 28 February 2012

TreeSet in Java with Examples

In TreeSet the elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.
Objects that implement Comparable interface can be used as the element in TreeSet.Use the following constructors for it.
  • public TreeSet()
  • public TreeSet(Collection<? extends E> c)
  • public TreeSet(SortedSet<E> s)
The Comparable interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

You can also create a TreeSet according to the specified comparator.Use the following constructor for it.
  • public TreeSet(Comparator<? super E> comparator)
If the specified comparator is null, the natural ordering of the elements will be used.


Comparable Interface

public interface Comparable<T>

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.
Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this interface can be used as keys in a sorted map or elements in a sorted set, without the need to specify a comparator.
The natural ordering for a class C is said to be consistent with equals if and only if (e1.compareTo((Object)e2) == 0) has the same boolean value as e1.equals((Object)e2) for every e1 ande2 of class C. Note that null is not an instance of any class, and e.compareTo(null)
should throw a NullPointerException even though e.equals(null) returns false.

compareTo

public int compareTo(T o)

Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

TreeSet using Comparable Interface
Find the code given below
import java.util.*;
public class Main {
public static void main(String args[]) {
TreeSet<Student> treeset = new TreeSet<Student>();
treeset.add(new Student(10));
treeset.add(new Student(11));
System.out.println(treeset);
}
}
class Student {
int rollno;
public Student(int rollno) {
this.rollno = rollno;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Student) {
Student temp = (Student) obj;
return (temp.rollno == this.rollno);
}
return false;
}

@Override
public int hashCode() {
return rollno;
}
public String toString() {
return String.valueOf(rollno); }
}

The output is

Exception in thread "main" java.lang.ClassCastException: Student cannot be cast to java.lang.Comparable
at java.util.TreeMap.put(TreeMap.java:559)
at java.util.TreeSet.add(TreeSet.java:255)
at Main.main(Main.java:9)
The reason is that, treeset elements does't implement the Comparable interface.

Let us try with Student class implemented the Comparable interface.

import java.util.*;
public class Main {
 public static void main(String args[]) {

 TreeSet<Student> treeset = new TreeSet<Student>();

 treeset.add(new Student(10));
 treeset.add(new Student(11));
 System.out.println(treeset);

 }
}

class Student implements Comparable<Student> {
 int rollno;
 public Student(int rollno) {
 this.rollno = rollno;
 }
 public boolean equals(Student obj) {

 if (obj!=null) {
 Student temp = (Student) obj;
 return (temp.rollno == this.rollno);
 }
 return false; }
 @Override
 public int hashCode() {
 return rollno; }
 @Override
 public int compareTo(Student arg0) {
 if (arg0 != null) {
 if (this.rollno > arg0.rollno)
 return 1;
 else if (this.rollno < arg0.rollno)
 return -1;
 else
 return 0;
 } else
 throw new NullPointerException();
 }
 public String toString() {
 return String.valueOf(rollno);
 }
}

The output is
[10, 11]

You can see that elements are ordered in the ascending order.
 
 TreeSet using Comparator Interface



import java.util.*;
  public class Main {
  public static void main(String args[]) {
 MySort mysort = new MySort();
 TreeSet<Student> treeset = new TreeSet<Student>(mysort);
 treeset.add(new Student(10));
 treeset.add(new Student(11));
 System.out.println(treeset);
 }
 }
 class Student {
 int rollno;
 public Student(int rollno) {
 this.rollno = rollno;
 }
 public boolean equals(Student obj) {
 if (obj != null) {
 Student temp = (Student) obj;
 return (temp.rollno == this.rollno);
 }
 return false;
 }
  @Override
 public int hashCode() {
 return rollno;
 }
 public String toString() {
 return String.valueOf(rollno);
 }
 }
  class MySort implements Comparator<Student> {
 
 @Override
 public int compare(Student o1, Student o2) {
 if (o1 != null && o2 != null) {
 if (o1.rollno > o2.rollno)
 return 1;
 else if (o1.rollno < o2.rollno)
 return -1;
 else
 return 0;
 } else
 throw new NullPointerException();
 } }

The output is

[10, 11]

The treeset elements are ordered in the ascending order.

No comments:

Post a Comment