TreeSet

TreeSet

The underlying data structure is balanced tree. Duplicate objects are not allowed. All elements will be inserted, according to some sorting order hence insertion is not preserve. Heterogeneous objects are not allow, violation leads ClassCastException.

Constructors:-

• TreeSet t = new TreeSet (); // natural sorting order. creates an empty TreeSet object where all the object will be inserted according to natural sorting order.
• TreeSet t = new TreeSet ( comparator c )// creates an empty TreeSet object, where all the elements are inserted according order described by comparator object.
• TreeSet t = new TreeSet ( collection c )
• TreeSet t = new TreeSet ( collection s )

import java. util. * ;
Class TreeSetDemo
public static void main (String[] args)
{
     TreeSet t = new TreeSet ();
     {    
     t. add ( "A" );
     t. add ( "B" );
     t. add ( "Z" );
     t. add ( "L" );
     t. add ( new Integer (10));// CCE
     t. add ( null ); // npe
     s.o.p ( t );
     }
}

• For the empty TreeSet has the first element null insertion is always possible. But after inserting null, if we are trying to insert any other element, we will get NullPointerException.
• For the non-empty TreeSet, if we are trying to insert null, we will get NullPointerException.

import java.util. *;
Class TreeSetDemo
{
 TreeSet t = new TreeSet (); 
{ 
      t. add ( new StringBuffer ( "A" )); 
      t. add ( new StringBuffer ( "B" ));
      t. add ( new StringBuffer ( "Z" ));
      t. add ( new StringBuffer ( "L" ));
      s.o.p ( t ); // [ A]
      }
}

• If we are depending on natural sorting order,compulsory object should be homogeneous & comparable other wise we will get ClassCastException.
• An object is said to comparable if & only if the corresponding class implements comparable interface on the above case, StringBuffer doesn’t implement comparable. Hence we get ClassCastException.
• String class & wrapper classes are comparable.

Comparable interface:-

• It is present in java lang package & contains only one method compareTo ()

Public int compareTo ( object obj )
obj 1. compareTo ( obj 2)
return
-ve if obj 1 has to com before obj 2

+ve if obj 1 has come after obj 2
O if obj 1& obj 2 are equal
Ex:-
s.o.p ( "A". compareTo ( "Z" )); // -ve
s.o.p ( "Z". compareTo ( "K" )); // +ve
s.o.p ( "A". compareTo ( "A" )); // O

• If we are depending on natural sorting order, internally JVM calls compareTo () method to places objects according to sorting order. Hence the objects should be comparable, other wise we will ClassCastException.
• Some times we have to implement our own sorting order instead of natural sorting order. We can handle this requirement by using comparator.
• comparable mean for default natural sorting order. where as comparator mean for customized sorting order.

Comparator

This interface present in java. util package. This interface defines the following two methods.

1. Public int compare: ( object obj 1, obj 2)

Returns ——> -ve if obj 1 has to come before obj 2.

+ve if obj 1 has to come after obj 2

O if obj 1& obj 2 are equal.

2. Public boolean equals ( object obj): When ever we are implementing comparator interface, compulsory we should provide implementation for compare method.Equals () method implementation is optional. because it is already available through in inheritance from object class.

Que:- Demo program to insert Integer objects in to the TreeSet, where the sorting order is de sending order?

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

TreeSet t = new TreeSet ( new MyComparator )
     {
               t. add ( 20 ) ;
               t. add ( 0 ) ;
               t. add ( 15 ) ;
               t. add ( 5 ) ;
               t. add ( 10 ) ;
               s.o.p. ( t )
       }
}

Class MyComparator implements comparator
{
public static void main (String[] args) 
        {
         Inter I 1 = ( integer ) obj 1 ;
         Inter I 2 = ( integer ) obj 2 ;
         If ( I 1< I 2 )
         return + 100 ;
         else if ( I 1 > I 2 )
         return -1 ; else return 0;
         }
}

• At line 1, if we are not passing, comparator object has argument, JVM internally calls compareTo () method, which is mean for default natural sorting order ( ascending order ) with in case o/p [ 0,5,10,15,20 ].
• if we are implementing compare method as follow then the corresponding o/ps are

Public int compare ( object obj 1, obj 2 )
{
        Integer I 1 = ( Integer ) obj 1;
        Integer I 2 = ( Integer ) obj 2;
        return I 1. compareTo ( I 2 ) ; //0,5,10,15,20 natural sorting order
        return -I 1. compareTo ( I 2 ) ;// 20,15,10,5,0 reverse
        return I 2. compareTo ( I 1 ) ;// 0,5,10,15,20
        return -I 2. compareTo ( I 1 ) ; // reverse
        return -1 ; // 10, 5,15,0,20 reverse of insertion order
        return O ; // only TreeSet insert element present & all the remaining
                     elements treated duplicates ( 20 )

• Write a program to insert String objects into the TreeSet, where the sorting order is reverse of alphabetical order.

package com.narayanatutorial.scjp;

import java.util.TreeSet;

public class TreeSetExample {

	public static void main(String[] args) {
		TreeSet t = new TreeSet (new MyComparator());
		t.add ("A");
		t.add ("z");
		t.add ("k");
		t.add ("B");
		t.add ("a");
		System.out.println(t);

	}

}

output
[z, k, a, B, A]

 

package com.narayanatutorial.scjp;

import java.util.Comparator;

public class MyComparator implements Comparator {
  public int compare(Object Obj1, Object Obj2) {
      String s1 = Obj1.toString();
      String s2 = (String)Obj2;
       return s2.compareTo(s1);
 }
}

• Write a program to insert StringBuffer Object into the TreeSet, where sorting order is alphabetical order.

package com.narayanatutorial.scjp;

import java.util.Comparator;

public class MyComparator implements Comparator {
public int compare(Object Obj1, Object Obj2) {
            String s1 = Obj1.toString();
            String s2 = Obj2.toString();
            return s1.compareTo(s2);

      }
}


package com.narayanatutorial.scjp;

import java.util.TreeSet;
public class TreeSetDemo10 {

public static void main(String[] args) {
TreeSet<StringBuffer>  t = new TreeSet<StringBuffer> ( new MyComparator());
		t.add(new StringBuffer("A"));
		t.add(new StringBuffer("Z"));
		t.add(new StringBuffer("K"));
		t.add(new StringBuffer("L"));
System.out.println(t);				
	}
}

• If we are defining our own sorting by comparator then objects needn’t be comparable [homogeneous].
• Write a program, to insert StringBuffer object into TreeSet, where the sorting order is increasing length order. if two objects having the same length then consider their alphabetical order.

package com.narayanatutorial.scjp;
* @author Narayana
public class ExonTreeSetDemo {
* @param args
*/
public static void main(String[] args) {
         TreeSet t = new TreeSet(MyComparator)
          t.add("A");
          t.add(new StringBuffer("ABC"));
          t.add(NEW StringBuffer ("AA"));
          t.add("XX");
          t.add("ABC");
          t.add("A");
          System.out.println(t);
          }
}

 

package com.narayanatutorial.scjp;
 import java.util.Comparator; 
public class MyComparator implements Comparator {
 public int compare(Object Obj1, Object Obj2)
 {
       String s1 = Obj1.toString();
       String s2 = Obj2.toString();
       int l1 = s1.length();
       int l2 = s2.length();
       else if (l1>l2)/ return +1
       else
       return s1.compareTo(s2); 
         }
} 
output
A,AA,XX,ABC,ABCD

1. If we are defining our own sorting order by comparator, then objects need not be homogeneous.
2. For defined comparable classes, natural sorting order is already available. If we want to define our sorting order we can implement by using comparator.
3. For predefined non comparable classes, there is no default natural sorting order. If we want to define sorting, compulsory we should go for comparator interface.
4. Here comparable is not the choice, because we can’t modify source code of predefined classes.
5. For our own classes,to define natural sorting order, we can go for comparable interface.
6. If we want to change the sorting, then we can go for comparator.

package com.narayanatutorial.scjp;

public class EmployeeImplementsComparable {
static int eno;
EmployeeImplementsComparable (int eno)
{
this.eno = eno;
}
public static void main(String[] args) {
return "e"+eno;

      }
}

Public int compareTo(Object 01)
{
 int en01 = thos.eno;
 int en02 = ((employee)01).eno;
  if (en01< en02)
  {
      return -1;
   }
      {
       else if ( en01> en02)
           {
             return 1;
            }
        else return 0;
      }
}

package com.narayanatutorial.scjp;

public class Employee {

public Employee(int i) {
public static void main(String[] args) 
          Employee e1 = new Employee (100);
          Employee e2 = new Employee (500);
          Employee e3 = new Employee (700);
          Employee e4 = new Employee (200);
          TreeSet t = new TReeSet ()
          System.out.println(t);
TreeSet t1 = new TreeSet (new MyComparator ());
        t1. add (e1);
        t1. add ( e2);
        t1. add ( e3);
        t1. add ( e4);
        System.out.println();
        }
}

package com.narayanatutorial.scjp;

public class MyComparable Implements Comparator {

public int compare (Object Obj1, Object Obj2) {
       Integer I1 = ((employee)obj1).eno;
       Integer I2 = ((employee)obj2).eno;
       Integer I2.I1 compareTo (I1);

}

}

comparison between comparable & comparator:-

Comparable	Comparator
Present in java. lang package. Contains only one method public int compareTo(obj 2). To define natural sorting. String class & wrapper classes implemented this interface. marker interface.	Present in java. lang package. Contain 2 methods.Compare( objects, object obj). To redefine customized sorting order. No. It isn’t marker interface.

Comparison between set implemented classes:-

Property	HasSet	LinkedHasSet	TreeSet
Data structure. Insertion order. Sorting order. Duplicate objects. Heterogeneous. Null acceptance.	HasTable. Not preserve. Not preserve. No. Allowed. Allowed (once).	Hastable + LinkedList. Preserve. Not preserve. No. allowed. Allowed (once)	Balanced Tree. Not preserve. Preserve. No. Not allowed otherwise  ClassCastException. For empty TreeSet add first element allowed. In other cases, we will get NullPointerException.