Collections_FrameWork_Part1

Array

• An Array is an Indexed Collection of Fixed Number of Homogeneous Data Elements.

• The Main Advantage of Arrays is we can Represent Multiple Values by using a Single Variable so that the Readability of the Code will be Improved.

Limitations Of Object Type Arrays:

• Arrays are Fixed in Size that is Once we created an Array there is No Chance of Increasing OR Decreasing Size based on Our Requirement. Hence to Use Arrays Concept Compulsory we should Know the Size in Advance which May Not be Possible Always.

• Arrays can Hold Only Homogeneous Data Type Elements.

Eg:

We can Resolve this Problem by using Object Type Arrays.

• Object[] a = new Object[10000]; 
• a[0] = new Student(); √
• a[1] = new Customer(); √

• Arrays Concept is Not implemented based on Some Standard Data Structure Hence Readymade Methods Support is Not Available. Hence for Every Requirement we have to write the Code Explicitly which Increases Complexity of the Programming.

To Overcome the Above Problems of Arrays we should go for Collections.

Advantages Of Collections:

• Collections are Growable in Nature. That is based on Our Requirement we canIncrease OR Decrease the Size.

• Collections can Hold Both Homogeneous and Heterogeneous Elements.

• Every Collection Class is implemented based on Some Standard Data Structure.Hence for

• Every Requirement Readymade Method Support is Available. Being a Programmer we have to Use those Methods and we are Not Responsible to Provide Implementation

Differences Between Arrays And Collections:

Arrays

• Arrays are Fixed in Size.

• With Respect to Memory Arrays are Not Recommended to Use.

• With Respect to Performance Arrays are Recommended to Use.

• Arrays can Hold Only Homogeneous Data Elements.

• Arrays can Hold Both Primitives and Objects.

• Arrays Concept is Not implemented based on Some Standard Data Structure. Hence Readymade Method Support is Not Available.

Collections

• Collections are Growable in Nature.

• With Respect to Memory Collections are Recommended to Use.

• With Respect to Performance Collections are Not Recommended to Use.

• Collections can Hold Both Homogeneous and Heterogeneous Elements.

• Collections can Hold Only Objects but Not Primitives.

• For every Collection class underlying Data Structure is Available Hence Readymade Method Support is Available for Every Requirement.

Collection

• If we want to Represent a Group of Individual Objects as a Single Entity then we should go for Collection.

• Collection Frame Work:

• It defines Several Classes and Interfaces which can be used to Represent a Group of Objects as a Single Entity.

9 Key Interfaces Of Collection Framework:

• 1. Collection(I) 
• 2. List(I)
• 3. Set(I)
• 4. SortedSet(I)
• 5. NavigableSet(I) 
• 6. Queue(I)
• 7. Map(I)
• 8. SortedMap(I)
• 9. NavigableMap(I)

1. Collection(I)

• If we want to Represent a Group of Individual Objects as a Single Entity then we should go for Collections.

• Collection Interface is considered as Root Interface of Collection Framework.

• Collection Interface defines the Most Common Methodswhich are Applicable for anyCollection Object.

Difference Between Collection (I) and Collections (C):

• Collection is an Interface which can be used to Represent a Group of Individual Objects as a Single Entity.

• Whereas Collections is an Utility Class Present in java.util Package to Define Several Utility Methods for Collection Objects.

Note: 

• There is No Concrete Class which implements Collection Interface Directly. 

      

2. List(I)

• It is the Child Interface of Collection.

• If we want to Represent a Group of Individual Objects as a Single Entity where.Duplicates are allowed and Insertion Order Preserved. Then we should go for List.

Note: 

• In 1.2 Version onwards Vector and Stack Classes are re-engineered to Implement List Interface.

3. Set(I)

• It is the Child Interface of the Collection. Stack (C)

• If we want to Represent a Group of Individual Objects as a Single Entity where Duplicates are Not allowed and Insertion Order won't be Preserved. Then we should go for Set Interface.

4. SortedSet(I)

• It is the Child Interface of Set.

• If we want to Represent a Group of Individual Objects Without Duplicates According to Some Sorting Order then we should go for SortedSet. 

5. NavigableSet(I)

• It is the Child Interface of SortedSet.

• It defines Several Methods for Navigation Purposes. 

6. Queue(I)

• It is the Child Interface of Collection.

• If we want to Represent a Group of Individual Objects Prior to Processing then we should go for Queue.

• Eg: Before sending a Mail we have to Store All MailID’s in Some Data Structure and in which Order we added MailID’s in the Same Order Only Mails should be delivered (FIFO). For this Requirement Queue is Best Suitable. 

Note:

• All the Above Interfaces (Collection, List , Set, SortedSet, NavigableSet,and Queue) Meant for representing a Group of Individual Objects.

• If we want to Represent a Group of Key - Value Pairs then we should go for Map.

7. Map(I)

• Map is Not Child Interface of Collection.

• If we want to Represent a Group of Objects as Key- Value Pairs then we should go for Map Interface.

• Duplicate Keys are Not allowed but Values can be Duplicated.

8. SortdMap(I)

• It is the Child Interface of Map.

• If we want to Represent a Group of Objects as Key- Value Pairs according to Some Sorting Order of Keys then we should go for SortedMap.

• Sorting should be Based on Key but Not Based on Value.

8. NavigableMap(I)

• It is the Child Interface of SortedMap.

• It Defines Several Methods for Navigation Purposes. 

Note : In Collection Framework the following are Legacy Classes. 

• Enumeration (I) TreeMap (I)
• Dictionary (Abstract Class)
• Vector (Concrete Class)
• Stack (Concrete Class)
• Hashtable (Concrete Class)
• Properties (Concrete Class)

1. Collection Interface

• If we want to Represent a Group of Individual Objects as a Single Entity then we should go for Collection Interface.

Methods:

• Collection Interface defines the Most Common Methods which are Applicable for any Collection Objects.

The following is the List of the Methods Present Inside Collection Interface.

• 1) boolean add(Object o)
• 2) booleanaddAll(Collection c)
• 3) boolean remove(Object o)
• 4) booleanremoveAll(Collection c)
• 5) booleanretainAll(Collection c): 
• To Remove All Objects Except those Present in c.
• 6) void clear()
• 7) boolean contains(Object o)
• 8) booleancontainsAll(Collection c)         
• 9) booleanisEmpty() 
• 10) int size()
• 11) Object[] toArray() 
• 12) Iterator iterator()

Note:

• There is No Concrete Class which implements Collection Interface Directly.
• There is No Direct Method in Collection Interface to get Objects.

2. List Interface

• It is the Child Interface of Collection.

• If we want to Represent a Group of Individual Objects where Duplicates are allowed and Insertion Order Preserved. Then  we should go for List.

• We can Preserve Insertion Order and we can Differentiate Duplicate Object by usingIndex. Hence Index will Play Very Important Role in List.

Methods:

List Interface Defines the following Specific Methods.

• void add(int index, Object o)
• boolean addAll(int index, Collection c)
• Object get(int index)
• Object remove(int index)
• Object set(int index, Object new):
• To Replace the Element Present at specified Index with provided Object and Returns Old Object.
• int indexOf(Object o):Returns Index of 1st Occurrence of 'o'
• int lastIndexOf(Object o)
• List IteratorlistIterator();

2.1 ArrayList (I)

• The Underlying Data Structure for ArrayList is Resizable Array ORGrowable Array.

• Duplicate Objects are allowed.

• Insertion Order is Preserved.

• Heterogeneous Objects are allowed (Except TreeSet and TreeMap Everywhere Heterogeneous Objects are allowed).

• null Insertion is Possible.

Constructors:

1) ArrayList l = new ArrayList();

• Creates an Empty ArrayList Object with Default Initial Capacity 10.

• If ArrayList Reaches its Max Capacity then a New ArrayList Object will be Created with

•  New Capacity = (Current Capacity * 3/2)+1

2) ArrayList l = new ArrayList(intinitialCapacity);

•   Creates an Empty ArrayList Object with specified Initial Capacity.

3) ArrayList l = new ArrayList(Collection c);

•   Creates an EqualentArrayList Object for the given Collection Object.

This Constructor Meant for Inter Conversion between Collection Objects. :

import java.util.ArrayList; 
classArrayListDemo {
  public static void main(String[] args){ 
    ArrayList l = new ArrayList();
    l.add("A");
    l.add(10);
    l.add("A");
    l.add(null);
    
    System.out.println(l); //[A, 10, A, null]
    l.remove(2);
    
    System.out.println(l); //[A, 10, null]
    l.add(2,"M");
    l.add("N");
    
    System.out.println(l); //[A, 10, M, null, N]
    } 
  }

• Usually we can Use Collections to Hold and Transfer Data (Objects) form One Location to Another Location.

• To Provide Support for this Requirement Every Collection Class Implements Serializable and Cloneable Interfaces.

• ArrayList and Vector Classes Implements RandomAccess Interface. So that we can Access any Random Element with the Same Speed.

• RandomAccess Interface Present in java.utilPackage and it doesn't contain any Methods. Hence it is a Marker Interface.

Hence ArrayList is Best Suitable if Our Frequent Operation is Retrieval Operation. 

ArrayList l1 = new ArrayList();
LinkedList l2 = new LinkedList();
System.out.println(l1 instanceofSerializable); //true 
System.out.println(l2 instanceofCloneable); //true 
System.out.println(l1 instanceofRandomAccess); //true 
System.out.println(l2 instanceofRandomAccess); //false

Differences between ArrayList and Vector: 

ArrayList

• Every Method Present Inside ArrayListis Non – Synchronized.

• Relatively Performance is High because Threads are Not required to Wait. Introduced in 1.2 Version and it is Non – Legacy.

• Introduced in 1.2 Version and it is Non – Legacy

• At a Time Multiple Threads are allow to Operate on ArrayList Simultaneously and Hence ArrayList Object is Not Thread Safe.

Vector

• Every Method Present in Vector is Synchronized.

• Relatively Performance is Low because Threads are required to Wait.

• Introduced in 1.0 Version and it is Legacy.

• At a Time Only One Thread is allow to Operate on Vector Object and Hence Vector Object is Always Thread Safe.

How to get Synchronized Version of ArrayList Object?

• By Default ArrayList Object is Non- Synchronized but we can get Synchronized Version ArrayList Object by using the following Method of Collections Class.

• public static List synchronizedList(List l)

   ArrayListal = new ArrayList ();
      List l = Collections.synchronizedList(al);
            |                                 |
Synchronized Version        Non - Synchronized Version

• Similarly we can get Synchronized Version of Set and Map Objects by using the following Methods of Collection.

• public static Set synchronizedSet(Set s) 

• public static Map synchronizedMap(Map m) 

• ArrayList is the Best Choice if we want to Perform Retrieval Operation Frequently.

• But ArrayList is Worst Choice if Our Frequent Operation is Insertion OR Deletion in the

• Middle. Because it required Several Shift Operations Internally. 

2.2 LinkedList (I)

• The Underlying Data Structure is Double LinkedList.

• Insertion Order is Preserved.

• Duplicate Objects are allowed.

• Heterogeneous Objects are allowed.

• null Insertion is Possible.

• Implements Serializable and Cloneable Interfaces but Not RandomAccessInterface.

• Best Choice if Our Frequent Operation is InsertionOR Deletion in the Middle.

• Worst Choice if Our Frequent Operation is Retrieval.

Constructors:

1) LinkedList l = new LinkedList(); 

    Creates an Empty LinkedList Object.

2) LinkedList l = new LinkedList(Collection c);

    Creates an Equivalent LinkedList Object for the given Collection.

Methods:

• Usually, we can Use LinkedList to Implement Stacks and Queues. To Provide Support for this Requirement LinkedList Class Defines the following 6 Specific Methods.

• void addFirst(Object o)
• void addLast(Object o)
• Object getFirst()
• Object getLast()
• Object removeFirst()
• Object removeLast()

import java.util.LinkedList; 
classLinkedListDemo {
  public static void main(String[] args) {
     LinkedList l = new LinkedList();
     l.add("Veer");
     l.add(30);
     l.add(null);
     l.add("Veer");
     l.set(0, "Software");
     l.add(0,"Venky");
     l.removeLast();
     l.addFirst("CCC");
     System.out.println(l); //[CCC, Venky, Software, 30, null]
  } 
}

2.3 Vector (I)

• The Underlying Data Structure is Resizable Array ORGrowable Array.

• Insertion Order is Preserved.

• Duplicate Objects are allowed.

• Heterogeneous Objects are allowed.

• null Insertion is Possible.

• Implements Serializable, Cloneable and RandomAccess interfaces.

• Every Method Present Inside Vector is Synchronized and Hence Vector Object is Thread Safe.

• Vector is the Best Choice if Our Frequent Operation is Retrieval.

• Worst Choice if Our Frequent Operation is Insertion OR Deletion in the Middle.

Constructors:

1) Vector v = new Vector();       

• Creates an Empty Vector Object with Default Initial Capacity 10.    

• Once Vector Reaches its Max Capacity then a New Vector Object will be Created with

• New Capacity = Current Capacity * 2

2) Vector v = new Vector(intinitialCapacity);

3) Vector v = new Vector(intinitialCapacity, intincrementalCapacity);

4) Vector v = new Vector(Collection c); 

Methods:

1) To Add Elements:

•     add(Object o)Collection
•     add(int index, Object o) -> List
•     addElement(Object o) -> Vector

2) To Remove Elements:

•     remove(Object o) -> Collection 
•     removeElement(Object o) -> Vector
•     remove(int index) -> List
•     removeElementAt(int index)-> Vector
•     clear() -> Collection
•     removeAllElements() ->Vector

3) To Retrive Elements:

•     Object get(int index) -> List
•     Object elementAt(int index) -> Vector
•     Object firstElement() -> Vector
•     Object lastElement()-> Vector

4) Some Other Methods:

•     int size()
•     int capacity()
•     Enumeration element()

import java.util.Vector; 
classVectorDemo {
  public static void main(String[] args) { 
    Vector v = new Vector();
    System.out.println(v.capacity()); //10 
    for(int i = 1; i<=10; i++) {
      v.addElement(i);
    }
    System.out.println(v.capacity()); //10 
    v.addElement("A");
    
    System.out.println(v.capacity()); //20 
    System.out.println(v); //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, A]
  } 
}

2.3.1 Stack:

•   It is the Child Class of Vector.
•   It is a Specially Designed Class for Last In First Out (LIFO) Order.

Constructor:

•   Stack s = new Stack(); 

Methods:

• Object push(Object o); To Insert an Object into the Stack.
• Object pop(); To Remove and Return Top of the Stack.
• Object peek(); Ro Return Top of the Stack without Removal.
• boolean empty(); Returns true if Stack is Empty
• int search(Object o);Returns Offset if the Element is Available Otherwise Returns -1.

import java.util.Stack; 
classStackDemo {
  public static void main(String[] args) { 
    Stack s = new Stack();
    s.push("A");
    s.push("B");
    s.push("C");
    System.out.println(s); //[A, B, C] 
    System.out.println(s.search("A")); //3 
    System.out.println(s.search("Z")); //-1
  } 
}

Output

 

The 3 Cursors of Java:

• If we want to get Objects One by One from the Collection then we should go for Cursors.

• There are 3 Types of Cursors Available in Java.

• Enumeration 
• Iterator
• ListIterator

1. Enumeration:

•    We can Use Enumeration to get Objects One by One from the Collection.

•    We can Create Enumeration Object by using elements().

•       public Enumeration elements();

•   Eg:Enumeration e = v.elements(); //v is Vector Object.

Methods:

• public booleanhasMoreElements();
• public Object nextElement();

import java.util.*; 
classEnumerationDemo {
  public static void main(String[] args) { 
    Vector v = new Vector();
    for(int i=0; i<=10; i++) { 
      v.addElement(i);
    }
  System.out.println(v); 
  Enumeration e = v.elements(); 
  while(e.hasMoreElements()) {
    Integer I = (Integer)e.nextElement(); 
    if(I%2 == 0){
      System.out.println(I);
    }
  } 
}

Output

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 0
2
4
6
8
10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Limitations of Enumeration:

• Enumeration Concept is Applicable Only for Legacy Classes and it is Not a Universal Cursor.

• By using Enumeration we can Perform Read Operation and we can't Perform Remove Operation. 

• To Overcome Above Limitations we should go for Iterator.

2. Iterator:

• We can Use Iterator to get Objects One by One from Collection.

• We can Apply Iterator Concept for any Collection Object. Hence it is Universal Cursor.

• By using Iterator we can Able to Perform Both Read and Remove Operations.

• We can Create Iterator Object by using iterator() of Collection Interface.

•   public Iterator iterator();

• Eg:Iterator itr = c.iterator(); //c Means any Collection Object.

Methods:

• public booleanhasNext()
• public Object next()
• public void remove()

import java.util.*; 
classIteratorDemo {
 public static void main(String[] args) { 
  ArrayList l = new ArrayList();
  for (int i=0; i<=10; i++) { 
    l.add(i);
  }
  System.out.println(l); 
  Iterator itr = l.iterator(); 
  while(itr.hasNext()) {
    Integer I = (Integer)itr.next(); 
    if(I%2 == 0)
      System.out.println(I);
    else
      itr.remove();
  }
  System.out.println(l);
 }
}

Output

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
0
2
4
6
8
10
[0, 2, 4, 6, 8, 10]

Limitations:

• By using Enumeration and Iterator we can Move Only towards Forward Direction and we can’t Move Backward Direction. That is these are Single Direction Cursors but NotBi- Direction.

• By using Iterator we can Perform Only Read and Remove Operations and we can't Perform Addition of New Objects and Replacing Existing Objects.

• To Overcome these Limitations we should go for ListIterator.

3) ListIterator:

• ListIterator is the Child Interface of Iterator.

• By using ListIterator we can Move Either to the Forward Direction OR to the Backward Direction. That is it is a Bi-Directional Cursor.

• By using ListIterator we can Able to Perform Addition of New Objects andReplacing existing Objects. In Addition to Read and Remove Operations.

• We can Create ListIterator Object by using listIterator().
•   publicListIteratorlistIterator();
• Eg:ListIteratorltr = l.listIterator(); //l is Any List Object

Methods:

• ListIteratoris the Child Interface of Iterator and Hence All Iterator Methods by Default Available to the ListIterator.

          Iterator (I)
              ^
              |
              |
         ListIterator (I)

• ListIteratorDefines the following 9 Methods.
• Forward Direction
• Iterator (I)
• ListIterator (I)
• publicbooleanhasNext() 
• public Object next() 
• public int nextIndex()

• Backward Direction
• public boolean hasPrevious() 
• public Object previous() 
• public int previousIndex()

• public void remove()
• public void set(Object new) 
• public void add(Object new)

import java.util.*; 
classListIteratorDemo {
  public static void main(String[] args) { 
    LinkedList l = new LinkedList();
    l.add("Baala"); 
    l.add("Venki");
    l.add("Chiru");
    l.add("Naag"); 
    System.out.println(l); 
    ListIteratorltr = l.listIterator(); 
    while(ltr.hasNext()) {
    String s = (String)ltr.next(); 
      if(s.equals("Venki"))
        ltr.remove(); 
      if(s.equals("Naag"))
        ltr.add("Chaitu"); 
      if(s.equals("Chiru"))
        ltr.add("Charan");
  } 
  System.out.println(l);
}

Output:

    [Baala, Venki, Chiru, Naag]
    [Baala, Chiru, Charan, Naag, Chaitu]

Note: 

• The Most Powerful Cursor is ListIterator. But its Limitation is, it is Applicable Only for List Objects.

Comparison Table of 3 Cursors:

Internal Implementation of Cursors:

 import java.util.*; 
classCursorDemo {
  public static void main(String args[]) { 
    Vector v = new Vector();
    Enumeration e = v.elements();
    Iterator itr = v.iterator();
    ListIteratorlitr = v.listIterator(); 
    System.out.println(e.getClass().getName()); 
    System.out.println(itr.getClass().getName()); 
    System.out.println(litr.getClass().getName());
}

Output
    java.util.Vector$1 
    java.util.Vector$Itr 
    java.util.Vector$ListItr

3 Set (I)

• It is the Child Interface of Collection.

• If we want to Represent a Group of Individual Objects as a Single Entity where Duplicates are Not allowed and Insertion Order is Not Preserved then we should go for Set.

• Set Interface doesn't contain any New Methods and Hence we have to Use Only

• Collection Interface Methods 

3.1 HashSet:

• The Underlying Data Structure is Hashtable. (1.2 V)

• Insertion Order is Not Preserved and it isBased on hashCode of the Objects.

• Duplicate Objects are Not Allowed. If we are trying to Insert Duplicate Objects then we won't get any CLoinmkpeidleHTasihmSetO(RC)Runtime ErrorN.advidg(a)bSleimSeptly(I)Returns false.

• null Insertion is Pos(s1ib.4leV.) (1.6 V)

• Heterogeneous objects are allowed.

• HashSet implements Serializable and Cloneable Interfaces but Not RandomAccess. TreeSet (C)

• If Our Frequent Operation is Search Operation, then HashSet is the Best Choice. (1.2 V)

Constructors:

1) HashSet h = new HashSet();

• Creates an Empty HashSet Object with Default Initial Capacity 16 and Default Fill Ratio : 0.75.

2) HashSet h = new HashSet(intinitialCapacity);

• Creates an Empty HashSet Object with specified Initial Capacity and Default Fill Ratio : 0.75.

3) HashSet h = new HashSet(intinitialCapacity, float fillRatio);

4) HashSet h = new HashSet(Collection c);

Load Factor:

• Fill Ratio 0.75 Means After Filling 75% Automatically a New HashSet Object will be Created. This Factor is Called Fill RatioORLoad Factor.

Import java.util.*; 
classHashSetDemo {
  public static void main(String[] args) { 
    HashSet h = new HashSet();
    h.add("B");
    h.add("C");
    h.add("D");
    h.add("Z");
    h.add(null);
    h.add(10);
    System.out.println(h.add("Z")); //false
    System.out.println(h); //[null, D, B, C, 10, Z]
  }
}

3.1.1 LinkedHashSet:

• It is the Child Class of HashSet. 

• It is Exactly Same as HashSet Except the following Differences.

HashSet

• The Underlying Data Structure is Hashtable.
• Insertion Order is Not Preserved
• Introduced in 1.2 Version.

LinkedHashSet

• The Underlying Data Structure is a Combination of LinkedList and Hashtable.
• Insertion Order will be Preserved.
• Introduced in 1.4 Version.

• In the Above Example if we Replace HashSet with LinkedHashSet then Output is false
• [B, C, D, Z, null, 10]
• That is Insertion Order is Preserved.

Note: 

• In General we can UseLinkedHashSetandLinkedHashMapto Develop Cache Based Applications where Duplicates are Not Allowed and Insertion Order Must be Preserved.

3.1.2 SortedSet:

• It is the Child Interface of Set.

• If we want to Represent a Group of Individual Objects without Duplicates and all Objects will be Inserted According to Some Sorting Order, then we should go for SortedSet.

• The Sorting can be Either Default Natural Sorting OR Customized Sorting Order.

• For String Objects Default Natural Sorting is Alphabetical Order.

• For Numbers Default Natural Sorting is Ascending Order.

Methods:

• Object first(); Returns 1st Element of the SortedSet.
• Object last(); Returns Last Element of the SortedSet.
• SortedSetheadSet(Object obj);
•   Returns SortedSet whose Elements are < Object.
• SortedSettailSet(Object obj);
•   Returns SortedSet whose Elements are >= Object. 
• SortedSetsubSet(Object obj1, Object obj2);
•   Returns SortedSet whose Elements are >= obj1 and <obj2.
• Comparator comparator();

•   Returns Comparator Object that Describes Underlying SortingTechnique. 
•   If we are using Default Natural Sorting Order then we will get null.

3.2.2. TreeSet:

• The Underlying Data Structure is Balanced Tree.

• Insertion Order is Not Preserved and it is Based on Some Sorting Order.

• Heterogeneous Objects are Not Allowed. If we are trying to Insert we will get Runtime Exception Saying ClassCastException.

• Duplicate Objects are Not allowed.

• null Insertion is Possible (Only Once).

• Implements Serializable and Cloneable Interfaces but Not RandomAccess Interface.

Constructors:

1) TreeSet t = new TreeSet();

• Creates an Empty TreeSet Object where all Elements will be Inserted According to Default Natural Sorting Order.

2) TreeSet t = new TreeSet(Comparator c);

• Creates an Empty TreeSet Object where all Elements will be Inserted According to Customized Sorting Order which is described by Comparator Object.

3) TreeSet t = new TreeSet(Collection c);

4) TreeSet t = new TreeSet(SortedSet s);

import java.util.TreeSet; 
class TreeSetDemo {
  public static void main(String[] args) { 
    TreeSet t = new TreeSet();
    t.add("A"); 
    t.add("a"); 
    t.add("B"); 
    t.add("Z"); 
    t.add("L");
    t.add(new Integer(10));
    t.add(null);//RE: Exception in thread "main" java.lang.NullPointerException 
    System.out.println(t); //[A, B, L, Z, a]
  } 
}

null Acceptance:

• For Empty TreeSet as the 1st Element null Insertion is Possible. But after inserting that null if we are trying to Insert any Element we will get NullPointerException.

• For Non- Empty TreeSet if we are trying to Insert null we will get NullPointerException.

import java.util.TreeSet; 
classTreeSetDemo {
  public static void main(String[] args) { 
    TreeSet t = new TreeSet();
    t.add(new StringBuffer("A")); 
    t.add(new StringBuffer("Z")); 
    t.add(new StringBuffer("L")); 
    t.add(new StringBuffer("B")); 
    System.out.println(t);
  } 
}

Output

• RE: Exception in thread "main" java.lang.ClassCastException: java.lang.StringBuffer cannot be cast to java.lang.Comparable

Note:

• If we are Depending on Default Natural Sorting Order Compulsory Objects should be Homogeneous and Comparable. Otherwise 

• we will get RE: ClassCastException.

• An object is said to be Comparable if and only if corresponding class implements Comparable interface.

• All Wrapper Classes, String Class Already Implements Comparable Interface. But StringBuffer Class doesn't Implement Comparable Interface.

• Hence we are ClassCastException in the Above Example.

Comparable (I):

• Comparable Interface Present in java.lang Package and it contains Only One Method compareTo().
•   publicintcompareTo(Object o);

• Wheneverwe are Depending on Default Natural Sorting Order and if we are trying to Insert Elements then Internally JVM will Call compareTo() to IdentifySorting Order.

       Eg:

Note: 

• If we are Not satisfied with Default Natural Sorting Order OR if Default

• Natural Sorting Order is Not Already Available then we can Define Our Own Sorting by using  Comparator Object.

• Comparable Meant for Default Natural Sorting Order whereas Comparator Meant for Customized Sorting Order

  

Comparator (I):

• This Interface Present in java.util Package.

Methods: 

•   It contains 2 Methods compare() and equals(). 

Write a Program to Insert Integer Objects into the TreeSet where Sorting Order is Descending Order:

• At Line 1 if we are Not Passing Comparator Object as an Argument then Internally JVM will Call compareTo(). Which is Meant for Default Natural Sorting Order (Ascending Order). In this Case the Output is [0, 5, 10, 15, 20].

• At Line 1 if we are Passing Comparator Object then JVM will Call compare() Instead of compareTo(). Which is Meant for Customized Sorting (Descending Order). In this Case the Ouput is [20, 15, 10, 5, 0].

Various Possible Implementations of compare():

public int compare(Object obj1, Object obj2) { 
  Integer I1 = (Integer)obj1;
  Integer I2 = (Integer)obj2;
  return I1.compareTo(I2); //[0, 5, 10, 15, 20] Ascending Order
  return -I1.compareTo(I2); //[20, 15, 10, 5.0] Descending Order
  return I2.compareTo(I1); //[20, 15, 10, 5.0]
  return -I2.compareTo(I1); //[0, 5, 10, 15, 20]
  return +1; //[10, 0, 15, 5, 20, 20] Insertion Order
  return -1; //[20, 20, 5, 15, 0, 10] Reverse of Insertion Order
  return 0; //[10] Only 1st Inserted Element Present And All Remaining Elements Treated as Duplicates
}

Write a Program to Insert String Objects into the TreeSet where the Sorting Order is of Reverse of Alphabetical Order:

import java.util.*; 
class TreeSetDemo {
  public static void main(String[] args) {
    TreeSet t = new TreeSet(new MyComparator()); 
    t.add("Roja");
    t.add("Sobha Rani");
    t.add("Raja Kumari");
    t.add("Ganga Bhavani");
    t.add("Ramulamma");
    System.out.println(t);
  } 
}
class MyComparator implements Comparator { 
  public int compare(Object obj1, Object obj2) {
     String s1 = obj1.toString();
     String s2 = (String)obj2;
     return s2.compareTo(s1);
     //[Sobha Rani, Roja, Ramulamma, Raja Kumari, Ganga Bhavani] 
     //return -s1.compareTo(s2);//vVaalildid
  }
}

Write a Program to Insert StringBuffer Objects into the TreeSet where Sorting Order is Alphabetical Order:

importjava.util.*; 
class TreeSetDemo {
  public static void main(String[] args) {
    TreeSet t = new TreeSet(new MyComparator1()); 
    t.add(new StringBuffer("A"));
    t.add(new StringBuffer("Z"));
    t.add(new StringBuffer("K"));
    t.add(new StringBuffer("L")); 
    System.out.println(t);
  } 
}
class MyComparator1 implements Comparator {
  public int compare(Object obj1, Object obj2) {
    String s1 = obj1.toString();
    String s2 = obj2.toString();
    return s1.compareTo(s2); //[A, K, L, Z]
  } 
}

Write a Program to Insert String and StringBuffer Objects into the TreeSet where Sorting Order is Increasing Length Order. If 2 Objects having Same Length then Consider their Alphabetical Order:

importjava.util.*; 
class TreeSetDemo {
  public static void main(String[] args) {
    TreeSet t = new TreeSet(new MyComparator()); 
    t.add("A");
    t.add(new StringBuffer("ABC"));
    t.add(new StringBuffer("AA"));
    t.add("XX");
    t.add("ABCE");
    t.add("A");
    System.out.println(t);
  } 
}
classMyComparator implements Comparator { 
  publicint compare(Object obj1, Object obj2) {
    String s1 = obj1.toString(); 
    String s2 = obj2.toString(); int i1 = s1.length();
    int i2 = s2.length();
    
    if(i1 < i2)
      return -1;
    else if(i1 > i2)
      return 1;
    else 
      return s1.compareTo(s2); //[A, AA, XX, ABC, ABCE]
  } 
}

Note:

• If we are Depending on Default Natural Sorting Order Compulsory Objects should be Homogeneous and Comparable Otherwise we will get RE: ClassCastException.

• If we defining Our Own Sorting by Comparator then Objects Need Not be Homogeneous and Comparable. That is we can Add Heterogeneous Non Comparable Objects to the TreeSet.

When we go for Comparable and When we go for Comparator: Comparable Vs Comparator:

• For Predefined Comparable Classes (Like String) Default Natural Sorting Order is Already Available. If we are Not satisfied with that we can Define Our Own Sorting by Comparator Object.

• For Predefine Non- Comparable Classes (Like StringBuffer) Default Natural Sorting Order is Not Already Available. If we want to Define Our Own Sorting we can Use Comparator Object.

• For Our Own Classes (Like Employee) the Person who is writing Employee Class he is Responsible to Define Default Natural Sorting Order by implementing Comparable Interface.

• The Person who is using Our Own Class if he is Not satisfied with Default Natural Sorting Order he can Define his Own Sorting by using Comparator Object.

• If he is satisfied with Default Natural Sorting Order then he can Use Directly Our Class.

Write a Program to Insert Employee Objects into the TreeSet where DNSO is Based on Ascending Order of EmployeeId and Customized Sorting Order is Based on Alphabetical Order of Names:

import java.util.*;
class Employee implements Comparable {
  String name;
  inte id;
  Employee(String name, inteid) {
    this.name = name;
    this.eid = eid; 
  }
  public String toString() { return name+"-----"+eid;} publicintcompareTo(Object obj) {
    int eid1 = this.eid;
    Employee e = (Employee)obj;
    int eid2 = e.eid;
    if(eid1 < eid2) 
      return -1;
    else if(eid1 > eid2) 
      return 1; 
    else 
      return 0;
  } 
}
class CompComp {
  public static void main(String[] args) {
    Employee e1 = new Employee("Nag", 100); 
    Employee e2 = new Employee("Bala", 200); 
    Employee e3 = new Employee("Chiru", 50); 
    Employee e4 = new Employee("Venki", 150); 
    Employee e5 = new Employee("Nag", 100); 
    
    TreeSet t = new TreeSet();
    t.add(e1);
    t.add(e2);
    t.add(e3);
    t.add(e4);
    t.add(e5);
    System.out.println(t);
    TreeSet t1 = new TreeSet(new MyComparator()); t1.add(e1);
    t1.add(e2);
    t1.add(e3);
    t1.add(e4);
    t1.add(e5); 
    System.out.println(t1);
  } 
}
class MyComparator implements Comparator {
  public int compare(Object obj1, Object obj2) { 
    Employee e1 = (Employee) obj1;
    Employee e2 = (Employee) obj2;
    String s1 = e1.name;
    String s2 = e2.name;    
    return s1.compareTo(s2);
  }
}

Output

  [Chiru-----50, Nag-----100, Venki-----150, Bala-----200]
  [Bala-----200, Chiru-----50, Nag-----100, Venki-----150]

4. Map (I)

• Map is Not Child Interface of Collection.

• If we want to Represent a Group of Objects as Key- Value Pairs then we should go for Map.

• Both Keys and Values are Objects Only.

• Duplicate Keys are Not allowed. But Values can be Duplicated.

• Each Key- Value Pair is Called an Entry.

Methods

Map Interface Defines the following Methods

• Object put(Object key, Object value);
• void putAll(Map m)
• Object get(Object key)
• Object remove(Object key)
• boolean containsKey(Object key)
• boolean containsValue(Object value)
• boolean isEmpty()
• int size()
• void clear()
• Set keySet()
• Collection values()
• Set entrySet()

Entry (I):

• Each Key- Value Pair is Called One Entry.

• Without existing Map Object there is No Chance of existing Entry Object.

• Hence Interface Entry is Define Inside Map Interface.

interface Map{ 
      interface Entry{
        Object getKey()
        Object getValue()
        Object setValue(Object new)
    } 
  }

Differences between and HashMap and Hashtable:

HashMap

• No Method Present in HashMap is Synchronized.
• Relatively Performance is High.
• null is allowed for Both Keys and Values.
• Introduced in 1.2 Version and it is Non – Legacy.
• At a Time Multiple Threads are allowed to Operate on HashMap Object simultaneously and Hence it is Not Thread Safe.

Hashtable

• Every Method Present in Hashtable is Synchronized.
• Relatively Performance is Low.
• null is Not allowed for Both Keys and Values. Otherwise we will get NPE. 
• Introduced in 1.0 Version and it is Legacy.
• At a Time Only One Thread is allowed to Operate on the Hashtable Object and Hence it is Thread Safe.

How to get Synchronized Version of HashMap:

• By Default HashMap is Non- Synchronized. But we can get Synchronized Version of HashMap by using synchronizedMap() of Collections Class.

Constructors:

• HashMap m = new HashMap();

•   Creates an Empty HashMap Object with Default Initial Capacity 16 and Default Fill Ratio 0.75

• HashMap m = new HashMap(intinitialcapacity);

• HashMap m = new HashMap(intinitialcapacity, float fillRatio);

• HashMap m = new HashMap(Map m);

import java.util.*; 
class HashMapDemo {
  public static void main(String[] args) { 
    HashMap m = new HashMap();
    m.put("Chiru", 700);
    m.put("Bala", 800);
    m.put("Venki", 200);
    m.put("Nag", 500); 
    System.out.println(m);
    System.out.println(m.put("Chiru", 1000)); 
    Set s = m.keySet();
    System.out.println(s); 
    Collection c = m.values(); 
    System.out.println(c); 
    Set s1 = m.entrySet(); 
    System.out.println(s1); 
    Iterator itr = s1.iterator(); 
    while(itr.hasNext()) {
      Map.Entry m1 = (Map.Entry)itr.next(); 
      System.out.println(m1.getKey()+"....."+m1.getValue()); 
      if(m1.getKey().equals("Nag")) {
        m1.setValue(10000);
      } 
    }
    System.out.println(m);
  } 
}

Output

{Chiru=700, Venki=200, Nag=500, Bala=800} 
700
[Chiru, Venki, Nag, Bala]
[1000, 200, 500, 800]
[Chiru=1000, Venki=200, Nag=500, Bala=800] 
Chiru.....1000
Venki.....200
Nag.....500
Bala.....800
{Chiru=1000, Venki=200, Nag=10000, Bala=800}

4.1 LinkedHashMap:

• It is the Child Class of HashMap.
• It is Exactly Same as HashMap Except the following Differeces.

 HashMap

• The Underlying Data Structure is Hashtable.
• Insertion is Not Preserved. Introduced in 1.2 Version.
• Introduced in 1.2 Version.

LinkedHashMap

• The Underlying Data Structure is Combination of Hashtable and LinkedList.
• Insertion Order is Preserved. 
• Introduced in 1.4 Version.

In the Above Example if we Replace HashMap with LinkedHashMap then Output is

{Chiru=700, Bala=800, Venki=200, Nag=500} 
700
[Chiru, Bala, Venki, Nag]
[1000, 800, 200, 500]
[Chiru=1000, Bala=800, Venki=200, Nag=500] 
Chiru.....1000
Bala.....800
Venki.....200
Nag.....500
{Chiru=1000, Bala=800, Venki=200, Nag=10000}

That is Insertion Order is Preserved.

Note: 

•  In General we can Use LinkedHashSet and LinkedHashMap for developing Cache Based Applications where Duplicates are Not Allowed. But Insertion Order Must be Preserved.

4.2 IdentityHashMap:

• It is Exactly Same as HashMap Except the following Difference.

• In HashMap JVM will Use .equals() to Identify Duplicate Keys, which is Meant for ContentComparision.

• In IdentityHashMap JVM will Use == Operator to Identify Duplicate Keys, which is Meant for Reference Comparison.

import java.util.HashMap; 
class IdentityHashMapDemo {
  public static void main(String[] args) { 
    HashMap m = new HashMap();
    Integer I1 = new Integer(10);
    Integer I2 = new Integer(10); 
    m.put(I1,"Pawan"); 
    m.put(I2,"Kalyan"); 
    System.out.println(m); //{10=Kalyan}
  }
}

• If we Replace HashMap with IdentityHashMap in the Above Application then Output is  
• {10=Pawan, 10=Kalyan}.
• Because I1 and I2 are Not Duplicate as I1 == I2 Returns false.

What is the Difference between == Operator and .equls()?

• In General we can Use == Operator for Reference Comparison whereas .equals() for Content  Comparison.

4.2.3WeakHashMap:

• It is Exactly Same as HashMap Except the following Difference.

• In Case of HashMap, HashMap Dominates Garbage Collector. That is if Object doesn’t have any Reference Still it is Not Eligible for Garbage Collector if it is associated with HashMap.

• But In Case of WeakHashMap if an Object doesn't contain any References then it is Always Eligible for GC Even though it is associated with WeakHashMap. That is Garbage Collector Dominates WeakHashMap.

import java.util.HashMap; 
class WeakHashMapDemo {
  public static void main(String[] args) throws InterruptedException { 
    HashMap m = new HashMap();
    Temp t = new Temp(); 
    m.put(t, "Cloud");
    System.out.println(m); t = null;
    System.gc(); 
    Thread.sleep(5000); 
    System.out.println(m);
  } 
}
class Temp {
  public String toString() {
    return "temp";
  }
  public void finalize() {
    System.out.println("finalize() Called");
  } 
}

Output
  {temp=Cloud} 
  {temp=Cloud}

• If we ReplaceHashMap with WeakHashMap then the Output is:
• {temp=Veer} 
• finalize() Called {} 

4.2.4 SortedMap:

• It is the Child Interface of Map.
• If we want to Represent a Group of Key - Value Pairs According Some Sorting Order of Keys then we should go for SortedMap.

Methods:

SortedMapDefines the following Specific Methods.

• Object firstKey();
• Object lastKey();
• SortedMapheadMap(Object key)
• SortedMaptailMap(Object key)
• SortedMapsubMap(Object key1, Object key2)
• Comparator comparator()

4.2.5 TreeMap:

• The Underlying Data Structure is Red -Black Tree.

• Duplicate Keys are Not Allowed. But Values can be Duplicated.

• Insertion Order is Not Preserved and it is Based on Some Sorting Order of Keys.

• If we are depending on Default Natural Sorting Order then the Keys should be Homogeneous and Comparable. Otherwise we will get Runtime Exception Saying ClassCastException.

• If we defining Our Own Sorting by Comparator then Keys can be Heterogeneous and Non- Comparable.

• But there are No Restrictions on Values. They can be Heterogeneous and Non- Comparable.

null Acceptance:

• For Empty TreeMap as the 1st Entry with null Key is Allowed. But After inserting that Entry if we are trying to Insert any Other Entry we will get RE: NullPointerException.

• For Non- Empty TreeMap if we are trying to Insert null Entry then we will get Runtime Exception Saying NullPointerException.

• There are No Restrictions on null Values.

Constructors:

• 1) TreeMap t = new TreeMap(); For Default Natural Sorting Order.
• 2) TreeMap t = new TreeMap(Comparator c); 
• For Customized Sorting Order.
• 3) TreeMap t = new TreeMap(SortedMap m); 
• Inter Conversion between Map Objects.
• 4) TreeMap t = new TreeMap(Map m);

Example on Natural Sorting:

import java.util.TreeMap;
class TreeMapDemo {
    public static void main(String[] args) {
      TreeMap m = new TreeMap(); 
      m.put(100, "ZZZ"); 
      m.put(103, "YYY"); 
      m.put(101, "XXX"); 
      m.put(104, 106);
      m.put(107, null);
      m.put("FFF", "XXX");
      m.put(null, "XXX"); //RE: Exception in thread "main" java.lang.NullPointerException 
      System.out.println(m); //{100=ZZZ, 101=XXX, 103=YYY, 104=106, 107=null}
    }
}

4.2.6 Hashtable:

• The Underlying Data Structure for Hashtable is Hashtable Only.

• Duplicate Keys are Not Allowed. But Values can be Duplicated.

• Insertion Order is Not Preserved and it is Based on Hashcode of the Keys.

• Heterogeneous Objects are Allowed for Both Keys and Values.

• null Insertion is Not Possible for Both Key and Values. Otherwise we will get Runtime Exception Saying NullPointerException.

• Every Method Present in Hashtable is Synchronized and Hence Hashtable Object is Thread Safe.

Constructors:

• Hashtable h = new Hashtable();
• Creates an Empty Hashtable Object with Default Initial Capacity 11 and Default Fill Ratio 0.75.
• Hashtable h = new Hashtable(intinitialcapacity);
• Hashtable h = new Hashtable(intinitialcapacity, float fillRatio);
• Hashtable h = new Hashtable(Map m);

import java.util.Hashtable; 
class HashtableDemo {
  public static void main(String[] args) { 
    Hashtable h = new Hashtable();
    h.put(new Temp(5), "A");
    h.put(new Temp(2), "B");
    h.put(new Temp(6), "C");
    h.put(new Temp(15), "D");
    h.put(new Temp(23), "E");
    h.put(new Temp(16), "F");
    h.put("Veer",null); //RE: java.lang.NullPointerException 
    System.out.println(h); //{6=C, 16=F, 5=A, 15=D, 2=B, 23=E}
  }
} 
class Temp {
  int i;
  Team(int i){
    this.i = i;
  }
  public int hasCode(){
   return i;
  }
  public String toString(){
    return i + "";
  }
}

Output: 

4.2.7 Properties

• It is the ChTeilmd pC(lianstsi)o{f Hashtable. 7 From Top To Bottom

• In Our Program itfhaisn.yi t=hii;ng which Changes Frequently (Like Database User Name,

• To Overcome this Problem we have to Con2figure S2u=chBType of Propertiesin Properties File.

• The MainAdvantageinthisApproachisif1athere23is=aEChangeinPropertiesFile,toReflect

• We can Use Properties Object to Hold Properties which are coming from Properties File. 

 Constructor:

•   Properties p = new Properties();

Methods:  

• public String getProperty(String pname);

• To Get the Value associated with specified Property.

• public String setProperty(String pname, String pvalue); 

• To Set a New Property.

• public Enumeration propertyNames();

• It Returns All Property Names.

• public void load(InputStream is); 

• To Load Properties from Properties File into Java Properties Object.

• public void store(OutputStreamos, String comment);

• To Store Properties from Java Properties Object into Properties File.

Eg: Pseudo Code

import java.util.*; 
import java.io.*; 
class PropertiesDemo {
  public static void main(String[] args) throws Exception {
    Properties p = new Properties();
    FileInputStreamfis = new FileInputStream("db.properties"); 
    p.load(fis);
    String url = p.getProperty("url");
    String user = p.getProperty("user");
    String pwd = p.getProperty("pwd");
    Connection con = DriverManager.getConnection(url,user,pwd); 
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  } 
}

5. Queue Interface 

• Queue is a Child Interface of Collection.

• If we want to Represent a Group of Individual Objects Prior to processing then we should go for Queue.

• From 1.5 Version onwards LinkedListalso implements Queue Interface.

• Usually Queue follows FIFO Order. But Based on Our Requirement we can Implement Our Own Priorities Also (PriorityQueue)

• LinkedList based Implementation of Queue always follows FIFO Order.

Eg:

•  Before sending a Mail we have to Store all Mail IDs in Some Data Structure and for the 1st Inserted Mail ID Mail should be Sent 1st.For this Requirement Queue is the Best Choice.

Methods:

• boolean offer(Object o); 
• To Add an Object into the Queue.

• Object peek();
• To Return Head Element of the Queue.
• If Queue is Empty then this Method Returns null.

• Object element();
• To Return Head Element of the Queue.
• if Queue is Empty then this Methodraises RE: NoSuchElementException

• Object poll();
• To Remove and Return Head Element of the Queue.  If Queue is Empty then this Method Returns null.

• Object remove();
• To Remove and Return Head Element of the Queue.
• If Queue is Empty then this Method raise RE: NoSuchElementException.

5.1 PriorityQueue:

• This is a Data Structure which can be used to Represent a Group of Individual Objects Prior to processing according to Some Priority.

• The Priority Order can be Either Default Natural Sorting Order OR Customized Sorting Order specified by Comparator Object.

• If we are Depending on Natural Sorting Order then the Objects should be Homogeneous and Comparable otherwise we will get ClassCastException.

• If we are defining Our Own Sorting by Comparator then the Objects Need Not beHomogeneous and Comparable.

• Duplicate objects are Not Allowed.

• Insertion Order is Not Preserved and it is Based on Some Priority.

• null Insertion is Not Possible Even as 1st Element Also.

Constructors:

• PriorityQueue q = new PriorityQueue();
• Creates an Empty PriorityQueue with Default Initial Capacity 11 and all Objects will be Inserted according to Default Natural Sorting Order.
• PriorityQueue q = new PriorityQueue(intinitialcapacity);
• PriorityQueue q = new PriorityQueue(intinitialcapacity, Comparator c);
• PriorityQueue q = new PriorityQueue(SortedSet s);
• PriorityQueue q = new PriorityQueue(Collection c);

import java.util.PriorityQueue; 
class PriorityQueueDemo {
  public static void main(String[] args) {
    PriorityQueue q = new PriorityQueue();
    System.out.println(q.peek()); //null
    System.out.println(q.element()); // java.util.NoSuchElementException 
    for(int i=0; i<=10; i++) {
      q.offer(i); 
    }
    System.out.println(q); //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
    System.out.println(q.poll()); //0 
    System.out.println(q); //[1, 3, 2, 7, 4, 5, 6, 10, 8, 9]
  }
 }

Note: 

• Some Operating Systems won't Provide Proper Support for PriorityQueues.

import java.util.*; 
class PriorityQueueDemo {
  public static void main(String[] args) {
    PriorityQueue q = new PriorityQueue(15, new MyComparator()); 
    q.offer("A");
    q.offer("Z");
    q.offer("L");
    q.offer("B");
    System.out.println(q); //[Z, B, L, A]
  } 
}
classMyComparator implements Comparator { 
  public int compare(Object obj1, Object obj2) {
    String s1 = (String)obj1; 
    String s2 = obj2.toString(); 
    return s2.compareTo(s1);
  }
}

5.2 NavigableSet (I):

• It is the Child Interface of SortedSet. 

Methods:

• It Defines Several Methods for Navigation Purposes.
• floor(e); 
• It Returns Highest Element which is <=e.
• lower(e); 
• It Returns Highest Element which is <e.
• ceiling(e); 
• It Returns Lowest Element which is >=e.
• higher(e); 
• It Returns Lowest Element which is >e.
• pollFirst(); 
• Remove and Return 1st Element.
• pollLast(); 
• Remove and Return Last Element.
• descendingSet(); 
• It Returns NavigableSet in Reverse Order.

import java.util.TreeSet; 
class NavigableSetDemo {
  public static void main(String[] args) { 
    TreeSet<Integer> t = new TreeSet<Integer>(); t.add(1000);
    t.add(2000);
    t.add(3000);
    t.add(4000);
    t.add(5000);
    System.out.println(t); 
    System.out.println(t.ceiling(2000));
    System.out.println(t.higher(2000)); 
    System.out.println(t.floor(3000)); 
    System.out.println(t.lower(3000)); 
    System.out.println(t.pollFirst()); 
    System.out.println(t.pollLast()); 
    System.out.println(t.descendingSet()); 
    System.out.println(t);
  } 
}
}

Output:

• [1000, 2000, 3000, 4000, 5000] 
• 2000
• 3000
• 3000
• 2000
• 1000
• 5000
• [4000, 3000, 2000] 
• [2000, 3000, 4000]

5.2.3 NavigableMap:

• It is the Child Interface of SortedMap. 

Methods:

• floorKey(e)
• lowerKey(e)
• ceilingKey(e)
• higherKey(e)
• pollFirstEntry() 
• pollLastEntry() 
• descendingMap()

import java.util.TreeMap; 
class NavigableMapDemo {
  public static void main(String[] args) {
    TreeMap<String, String> t = new TreeMap<String, String>();
    t.put("b", "Banana"); 
    t.put("c", "Cat"); 
    t.put("a", "Apple"); 
    t.put("d", "Dog"); 
    t.put("g", "Gun");
    
    System.out.println(t); 
    System.out.println(t.ceilingKey("c")); 
    System.out.println(t.higherKey("e")); 
    System.out.println(t.floorKey("e")); 
    System.out.println(t.lowerKey("e")); 
    System.out.println(t.pollFirstEntry()); 
    System.out.println(t.pollLastEntry()); 
    System.out.println(t.descendingMap()); 
    System.out.println(t);
 } 
}

Output:

{a=Apple, b=Banana, c=Cat, d=Dog, g=Gun} c
g
d
d
a=Apple
g=Gun
{d=Dog, c=Cat, b=Banana} {b=Banana, c=Cat, d=Dog}

Utility Classes

• Collections 
• Arrays

Collections (C):

• Collections Class is an Utility Class Present in java.util Package to Define Several Utility Methods for Collection Objects.

To Sort Elements of List:

Collections Class Defines the following Methods for this Purpose.

1) public static void sort(List l);

• To Sort Based on Default Natural Sorting Order.

• In this Case Compulsory List should contain Only Homogeneous andComparable Objects. Otherwise we will get Runtime Exception Saying ClassCastException.

• List should Not contain null Otherwise we will get NullPointerException.

2) public static void sort(List l, Comparator c);

•     To Sort Based on Customized Sorting Order.

Program: 

• To Sort Elements of List According to Natural Sorting Order.

import java.util.*; 
class CollectionsSortDemo {
  public static void main(String args[]) { 
    ArrayList al = new ArrayList(); 
    al.add("Z");
    al.add("A");
    al.add("K");
    al.add("N");
 al.add(new Integer(10)); //RE: Exception in thread "main" j    ava.lang.ClassCastException: java.lang.String cannot be  cast to java.lang.Integer
    al.add(null); //RE: Exception in thread "main" java.lang.NullPointerException 
    System.out.println("Before Sorting:"+al); //Before Sorting:[Z, A, K, N] Collections.sort(al);
    System.out.println("After Sorting:"+al); //After Sorting:[A, K, N, Z]
  }
}

Program: 

• To Sort Elements of List According to Customized Sorting Order.

import java.util.*; 
class CollectionsSortDemo {
  public static void main(String args[]) {
    ArrayList al = new ArrayList(); 
    al.add("Z");
    al.add("A"); 
    al.add("K");
    al.add("N");
    System.out.println("Before Sorting:"+al); //Before Sorting:[Z, A, K, N] 
    Collections.sort(al, new MyComparator());
    System.out.println("After Sorting:"+al); //After Sorting: [Z, N, K, A]
  }
}
classMyComparator implements Comparator {
  public int compare(Object obj1, Object obj2) { 
    String s1 = (String)obj1;
    String s2 = obj2.toString(); 
    return s2.compareTo(s1);
  } 
}

Searching Elements of List:

1) public static intbinarySearch(List l, Object target);

• If we are Sorting List According to Natural Sorting Order then we have to Use this Method.

2) public static intbinarySearch(List l, Object target, Comparator c);

• If we are Sorting List according to Comparator then we have to Use this Method.

Conclusions:

• Internally the Above Search Methods will Use Binary Search Algorithm.

• Before performing Search Operation Compulsory List should be Sorted. Otherwise we will get Unpredictable Results.

• Successful Search Returns Index.

• Unsuccessful Search Returns Insertion Point.

• Insertion Point is the Location where we can Insertthe Target Element in the SortedList.

• If the List is Sorted according to Comparator then at the Time of Search Operation Also we should Pass the Same Comparator Object. Otherwise we will get Unpredictable Results.

Program: 

• To Search Elements of List According to Natural Sorting Order.

import java.util.*; 
class CollectionsSearchDemo {
  public static void main(String args[]) { 
    ArrayList al = new ArrayList(); al.add("Z");
    al.add("A");
    al.add("M");
    al.add("K");
    al.add("a");
    System.out.println(al); //[Z, A, M, K, a] 
    Collections.sort(al);
    System.out.println(al); //[A, K, M, Z, a] 
    System.out.println(Collections.binarySearch(al, "Z")); //3
    System.out.println(Collections.binarySearch(al, "J")); //-2 
  }
}

Program: 

• To Search Elements of List According to Customized Sorting Order

Note: For the List of n Elements

• Successful Result Range: 0 To n-1
• Unsuccessful Result Range: -(n+1) To -1
• Total Result Range: -(n+1) To n-1

Eg: For the List of 3 Elements

• Range of Successful Search: 0 To 2
• Range of Unsuccessful Search: -4 To -1
• Total Result Range: -4 To 2

Reversing the Elements of List:public static void reverse(List l);

Program: To Reverse Elements of List

import java.util.*; 
class CollectionsReverseDemo {
  public static void main(String args[]) { 
    ArrayList al = new ArrayList(); al.add(15);
    al.add(0);
    al.add(20);
    al.add(10);
    al.add(5);
    System.out.println(al); //[15, 0, 20, 10, 5] 
    Collections.sort(al); 
    System.out.println(al); //[0, 5, 10, 15, 20] }
  }
}

reverse() Vs reverseOrder():

• We can Use reverse() to Reverse Order of Elements of List.
• We can Use reverseOrder() to get Reversed Comparator.

Arrays

• Arrays Class is an Utility Class to Define Several Utility Methods for Array Objects.

• Sorting Elements of Array:
• 1) public static void sort(primitive[] p); 
• To Sort According to Natural Sorting Order.
• 2) public static void sort(Object[] o); 
• To Sort According to Natural Sorting Order.
• Comparator c1 = Collecctions.reverseOrder(Comparator c); Descending Order Ascending Order      
• 3) public static void sort(Object[] o, Comparator c);
• To Sort According to Customized Sorting Order.

Note:

• For Object Type Arrays we can Sort According to Natural Sorting Order OR Customized Sorting Order.
• But we can Sort primitive[] Only Based on Natural Sorting.

Program: To Sort Elements of Array

Searching the Elements of Array:

• 1) public static intbinarySearch(primitive[] p, primitive target);
•   If the Primitive Array Sorted According to Natural Sorting Order then we have to Use this Method.
• 2) public static intbinarySearch(Object[] a, Object target);
•   If the Object Array Sorted According to Natural Sorting Order then we have to Use this Method.
• 3) public static intbinarySearch(Object[] a, Object target, Comparator c);
•   If the Object Array Sorted According to Comparator then we have to Use this Method.

Note: 

• All Rules of Array Class binarySearch() are Exactly Same as Collections Class binarySearch().

Program: To Search Elements of Array

import java.util.Arrays; 
import java.util.Comparator; 
import static java.util.Arrays.*;
class ArraysSearchDemo {
  public static void main(String args[]) {
    int[] a = {10, 5, 20, 11, 6};
    Arrays.sort(a); //Sort By Natural Order 
    System.out.println(Arrays.binarySearch(a, 6)); //1 
    System.out.println(Arrays.binarySearch(a, 14)); //-5
    
    String[] s = {"A", "Z", "B"};
    Arrays.sort(s); 
    System.out.println(binarySearch(s, "Z")); //2 
    System.out.println(binarySearch(s, "S")); //-3
    
    Arrays.sort(s, new MyComparator()); 
    System.out.println(binarySearch(s, "Z", new MyComparator())); //0 
    System.out.println(binarySearch(s, "S", new MyComparator())); //-2 
    System.out.println(binarySearch(s, "N")); //-4
  }
}
classMyComparator implements Comparator { 
  public int compare(Object obj1, Object obj2) {
    String s1 = obj1.toString();
    String s2 = obj2.toString(); 
  return s2.compareTo(s1);
  }
}

Conversion of Array to List:

• Arrays Class contains asList() for this -> public static List asList(Object[] a);

• Strictly Speaking this Method won't Create an Independent List Object, Just we are Viewingexisting Array in List Form.

• By using Array Reference if we Perform any Change Automatically that Change will be reflected to List Reference.

• Similarly by using List Reference if we Perform any Change Automatically that Change will be reflected to Array.

• By using List Reference if we aretrying to Perform any Operation which Varies the Size then we will get Runtime Exception Saying UnsuportedOperationException.

• Eg:

•    l.add("K");//RE: UnsuportedOperationException 
•    l.remove(1);//RE: UnsuportedOperationException 
•    l.set(1, "K"); √

• By using List Reference if we are trying to Replace with Heterogeneous Objects then we will get Runtime Exception Saying  ArrayStoreException.

Program: To View Array in List Form

import java.util.*; 
class ArraysAsListDemo {
  public static void main(String args[]) {
    String[] s = {"A", "Z", "B"}; 
    List l = Arrays.asList(s);
    System.out.println(l); //[A, Z, B]
    
    s[0] = "K"; 
    System.out.println(l); //[K, Z, B]
    
    l.set(1, "L");
    
    for (String s1 : s ) 
      System.out.println(s1); //K L B
    
    l.add("Veer"); //RE: java.lang.UnsupportedOperationException
    l.remove(2); //RE: java.lang.UnsupportedOperationException
    l.set(1, new Integer[10]); //RE: java.lang.ArrayStoreException:[Ljava.lang.Integer; }
  }
}