Java TreeSet - Walking Techie

Blog about Java programming, Design Pattern, and Data Structure.

Wednesday, December 14, 2016

Java TreeSet

TreeSet is a part of collection framework and is present in java.util package. Java TreeSet is popular implementation of Set interface. Java TreeSet extends AbstractSet and implements the NavigableSet, Cloneable, and java.io.Serializable interfaces. It creates a collection that uses a tree for storage. Objects are stored in sorted, ascending order according to the natural order. Optionally, you can construct a TreeSet with a constructor that lets you give the collection your own rules for what the order should be (rather than relying on the ordering defined by the elements' class) by using a Comparable or Comparator. Access and retrieval times are quite fast, which makes TreeSet an excellent choice when storing large amounts of sorted information that must be found quickly. TreeSet might not be used when our application has requirement of modification of set in terms of frequent addition of elements.

The TreeSet is a generic class that has this declaration:

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable

Here, E specifies the type of objects that the set will hold.

  • Java TreeSet inherits AbstractSet class and implements NavigableSet interface.
  • Java TreeSet does not allows duplicate entries.
  • Java TreeSet does not allow null element.
  • Java TreeSet can not be used for primitive types, like int, char, etc. We need to use wrapper classes.
  • Java TreeSet is not synchronized.
  • Java TreeSet is not thread-safe. You can get thread-safe TreeSet using SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...)) method at the cost of performance.
  • The iterator return by java TreeSet's Iterator() method is fail-fast. If the set structure is modified after creating the iterator in any other way except the iterator remove method, it will throw ConcurrentModificationException.

Java TreeSet constructors

There are four constructors in Java TreeSet.

Constructor Description
public TreeSet(SortedSet<E> s) Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set. If the iif the specified sorted set is null, it will throw NullPointerException.
public TreeSet() Constructs a new empty tree set, sorted according to the natural ordering of its elements. All elements inserted into the set must implement the Comparable interface.
public TreeSet(Comparator<? extends E> comparator) Constructs a new empty tree set, sorted according to the specified comparator. All elements inserted into the set must be mutually comparable by the specified comparator. If comparator is null Comparable natural ordering of the elements will be used.
public TreeSet(Collection<? extends E> c) Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements. All elements inserted into the set must implement the Comparable interface.

Below is a simple code snippet showing Java TreeSet constructors.

//default TreeSet constructor
Set<String> set=new TreeSet<String>();

//TreeSet constructor with SortedSet parameter
Set<String> wordSet=new TreeSet<String>(set);

//TreeSet constructor with comparator parameter
class MyComparator implements Comparator<String>{

 @Override
 public int compare(String o1, String o2) {
   return o1.compareToIgnoreCase(o2);
 }
}
MyComparator comparator = new MyComparator();
Set<String> set1= new TreeSet<String>(comparator);

//TreeSet with specified collection
List<String> list=new LinkedList<String>();
list.add("Nokia");
list.add("Samsung");
list.add("MI");
list.add("Zenfone");
Set<String> set2= new TreeSet<String>(list);

Java TreeSet methods

Method Description
public int size() Returns the number of elements in the invoking set.
public boolean isEmpty() Returns true if the invoking set contains no elements.
public boolean contains(Object obj) Returns true if the invoking set contains the specified element. It will throw ClassCastException if the specified object cannot be compared with the elements currently in the set. It will throw NullPointerException if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements.
public Object clone() Returns a shallow copy of the invoking TreeSet instance.(The elements themselves are not copied.)
public boolean add(E e) Adds the specified element to this set if it is not already present. If this set already contains the element, the call leaves the set unchanged and returns false. It will throw ClassCastException if the specified object cannot be compared with the elements currently in the set. It will throw NullPointerException if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements.
public boolean remove(Object obj) Removes the specified element from this set, if it is present. If the set does not contain the element, it is unchanged. It will throw ClassCastException if the specified object cannot be compared with the elements currently in the set. It will throw NullPointerException if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements.
public void clear() Removes all of the elements from this set. The set will be empty after this call returns.
public Iterator<E> iterator() Returns an iterator over the elements in this set in ascending order.
public Iterator<E> descendingIterator() Returns an iterator over the elements in this set in descending order.
public NavigableSet<E> descendingSet() Returns a reverse order view of the elements contained in this set. The descending set is backed by this set, so changes to the set are reflected in the descending set, and vice-versa. If either set is modified while an iteration over either set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined.
public boolean addAll(Collection<? extends E> c) Adds all of the elements in the specified collection to this set. It will throw ClassCastException if the specified object cannot be compared with the elements currently in the set. It will throw NullPointerException if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements.
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) Returns a view of the portion of this set whose elements range from fromElement to toElement. If fromElement and toElement are equal, the returned set is empty unless fromInclusive and toInclusive are both true. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports. The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.
public SortedSet<E> subSet(E fromElement, E toElement) Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive. (If fromElement and toElement are equal, the returned set is empty.) The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports. The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.
public NavigableSet<E> headSet(E toElement, boolean inclusive) Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports. The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.
public SortedSet<E> headSet(E toElement) Returns a view of the portion of this set whose elements are strictly less than toElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports. The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports. The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.
public SortedSet<E> tailSet(E fromElement) Returns a view of the portion of this set whose elements are greater than or equal to fromElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports. The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.
public Comparator<? super E> comparator() Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
public E first() Returns the first (lowest) element currently in this set. It will throw NoSuchElementException if this set is empty.
public E last() Returns the last (highest) element currently in this set. It will throw NoSuchElementException if this set is empty
public E lower(E e) Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
public E floor(E e) Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
public E ceiling(E e) Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
public E higher(E e) Returns the least element in this set strictly greater than the given element, or null if there is no such element.
public E pollFirst() Retrieves and removes the first (lowest) element, or returns null if this set is empty.
public E pollLast() Retrieves and removes the last (highest) element, or returns null if this set is empty.
public Spliterator<E> spliterator() Creates a late-binding and fail-fast Spliterator over the elements in this set. This is introduced in Java 8.

Java TreeSet Example

Java TreeSet common operations

Here we will see an example of commonly used method of TreeSet.

package com.walking.techie;

import java.util.Set;
import java.util.TreeSet;

public class TreeSetDemo {
 public static void main(String[] args) {
  TreeSet<Integer> numbers = new TreeSet<Integer>();

  // Add elements in TreeSet
  numbers.add(10);
  numbers.add(20);
  numbers.add(30);

  System.out.println("Elements of numbers set " + numbers);

  // size of TreeSet numbers
  System.out.println("Size of numbers set is " + numbers.size());

  // check set numbers contain 20
  System.out.println("numbers set contain element 20 ?:  " + numbers.contains(20));

  // creating odd numbers set
  Set<Integer> oddNumbers = new TreeSet<Integer>();
  oddNumbers.add(5);
  oddNumbers.add(25);
  oddNumbers.add(9);

  // appending odd numbers set to numbers set
  numbers.addAll(oddNumbers);
  System.out.println("numbers set after appending odd numbers set " + numbers);

  // first method call
  System.out.println("First(lowest) element in numbers set " + numbers.first());

  // last method call
  System.out.println("Last(highest) element in numbers set " + numbers.last());

  // lower method call
  System.out.println("Just lower element than 20 in numbers set " + numbers.lower(new Integer(20)));

  // floor method call
  System.out.println("Floor of element 20 in numbers set " + numbers.floor(new Integer(20)));

  // ceiling method call
  System.out.println("Ceiling of element 24 in numbers set " + numbers.ceiling(new Integer(24)));

  // higher method call
  System.out.println("Just higher element than 20 in numbers set " + numbers.higher(new Integer(20)));

  // pollFirst method call
  System.out.println("Retrieve and renoves the first (lowest) element from numbers set " + numbers.pollFirst());

  // pollLast method call
  System.out.println("Retrieve and removes the last (highest) element from numbers set " + numbers.pollLast());

  // clear method to empty the odd numbers set
  oddNumbers.clear();
  System.out.println("odd numbers set " + oddNumbers);

  // isEmpty method
  System.out.println("Is odd numbers set empty? " + oddNumbers.isEmpty());

  // remove Integer Object 5
  boolean isRemoved = numbers.remove(new Integer(5));
  System.out.println("element 5 removed ? " + isRemoved + ", numbers set contains " + numbers);
  // removeAll example
  oddNumbers.add(13);
  oddNumbers.add(25);
  oddNumbers.add(9);
  numbers.removeAll(oddNumbers);
  System.out.println("numbers elements after removeAll call " + numbers);

  numbers.add(25);
  numbers.add(9);

  // retainAll example
  oddNumbers.add(25);
  oddNumbers.add(11);
  oddNumbers.add(9);

  numbers.retainAll(oddNumbers);
  System.out.println("numbers elements after retainAll operation is " + numbers);
 }
}

Output of above program is shown below:

Elements of numbers set [10, 20, 30]
Size of numbers set is 3
numbers set contain element 20 ?:  true
numbers set after appending odd numbers set [5, 9, 10, 20, 25, 30]
First(lowest) element in numbers set 5
Last(highest) element in numbers set 30
Just lower element than 20 in numbers set 10
Floor of element 20 in numbers set 20
Ceiling of element 24 in numbers set 25
Just higher element than 20 in numbers set 25
Retrieve and renoves the first (lowest) element from numbers set 5
Retrieve and removes the last (highest) element from numbers set 30
odd numbers set []
Is odd numbers set empty? true
element 5 removed ? false, numbers set contains [9, 10, 20, 25]
numbers elements after removeAll call [10, 20]
numbers elements after retainAll operation is [9, 25]

Java TreeSet removeIf

The removeIf method was added in Java 8 and available in Collection interface.This method will remove all of the elements in the set which will satisfy the given predicate. Below is the program of TreeSet removeIf example.

package com.walking.techie;

import java.util.Set;
import java.util.TreeSet;
import java.util.function.Predicate;

public class TreeSetRemoveIfDemo {

 public static void main(String[] args) {
  Set<Integer> numbers = new TreeSet<Integer>();

  // add numbers from 1 to 10 in set
  for (int i = 1; i <= 10; i++) {
   numbers.add(i);
  }
  Predicate<Integer> filter = new TreeSetRemoveIfDemo().new EvenPredicate<Integer>();

  // set before removeIf operation
  System.out.println("Numbers set " + numbers);

  numbers.removeIf(filter);
  System.out.println("Numbers set after removeIf call " + numbers);
 }

 private class EvenPredicate<T> implements Predicate<Integer> {

  @Override
  public boolean test(Integer t) {
   return t % 2 == 0;
  }
 }
}

Output of above program is shown below:

Numbers set [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Numbers set after removeIf call [1, 3, 5, 7, 9]

Java TreeSet Iterator

Java TreeSet iterator is fail-fast, so iterator will throw java.util.ConcurrentModificationException if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

package com.walking.techie;

import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetIteratorDemo {

 public static void main(String[] args) {
  Set<Integer> numbers = new TreeSet<Integer>();
  numbers.add(23);
  numbers.add(34);
  numbers.add(13);
  numbers.add(2);
  numbers.add(28);
  System.out.print("Elements of numbers set [");

  // traversal over set using iterator
  Iterator<Integer> iterator = numbers.iterator();
  while (iterator.hasNext()) {
   int number = iterator.next();
   System.out.print(number + " ");
  }
  System.out.println("]");

  // ConcurrentModificationException
  iterator = numbers.iterator();
  while (iterator.hasNext()) {
   int number = iterator.next();
   System.out.print(number + " ");
   if (number == 28) {
    System.out.println();
    numbers.add(12); // throw ConcurrentModificationException
   }
  }
 }
}

Output of above program is shown below:

Elements of numbers set [2 13 23 28 34 ]
2 13 23 28
Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.TreeMap$PrivateEntryIterator.nextEntry(TreeMap.java:1211)
 at java.util.TreeMap$KeyIterator.next(TreeMap.java:1265)
 at com.walking.techie.TreeSetIteratorDemo.main(TreeSetIteratorDemo.java:29)

Java TreeSet to Array Example

Here is example to convert a set into Array and Array into set. Sometimes we need to convert array into set and vice-versa.

package com.walking.techie;

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetToArray {

 public static void main(String[] args) {
  Set<String> phone = new TreeSet<String>();
  phone.add("Nokia");
  phone.add("Samsung");
  phone.add("MI");
  phone.add("Zenfone");
  System.out.println("Set of phone " + phone);

  // convert set to Array
  String[] array1 = new String[phone.size()];
  phone.toArray(array1);
  System.out.println("Elements of Array1 " + Arrays.toString(array1));

  Object[] array2 = new Object[phone.size()];
  array2 = phone.toArray();
  System.out.println("Elements of Array2 " + Arrays.toString(array2));

  // convert array to set
  Set<String> set = new TreeSet<String>(Arrays.asList(array1));
  System.out.println("Elements of set " + set);
 }
}

Output of above program is shown below:

Set of phone [MI, Nokia, Samsung, Zenfone]
Elements of Array1 [MI, Nokia, Samsung, Zenfone]
Elements of Array2 [MI, Nokia, Samsung, Zenfone]
Elements of set [MI, Nokia, Samsung, Zenfone]

Java TreeSet to List Example

List and Set both are different from each others, but sometimes we need List from Set and vice-versa.

package com.walking.techie;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetToList {

 public static void main(String[] args) {
  Set<String> phone = new TreeSet<String>();
  phone.add("Nokia");
  phone.add("Samsung");
  phone.add("MI");
  phone.add("Zenfone");
  System.out.println("Set of phone " + phone);

  // convert set to list
  List<String> phoneList = new ArrayList<String>(phone);
  System.out.println("Elements of phoneList " + phoneList);

  // convert list to set
  Set<String> phoneSet = new TreeSet<String>(phoneList);
  System.out.println("Elements of set " + phoneSet);
 }
}
Output

Output of above program is shown below:

Set of phone [MI, Nokia, Samsung, Zenfone]
Elements of phoneList [MI, Nokia, Samsung, Zenfone]
Elements of set [MI, Nokia, Samsung, Zenfone]

2 comments :

  1. I appreciate that you produced this wonderful article to help us get more knowledge about this topic. I know, it is not an easy task to write such a big article in one day, I've tried that and I've failed. But, here you are, trying the big task and finishing it off and getting good comments and ratings. That is one hell of a job done!

    informatica mdm online training

    apache spark online training

    angularjs online training

    devops online training

    aws online training

    ReplyDelete