Java - How to use Comparator?

Both TreeSet and TreeMap store elements in sorted order. However, it is the comparator that defines precisely what sorted order means.

The Comparator interface defines two methods: compare( ) and equals( ). The compare( ) method, shown here, compares two elements for order:

The compare Method:

int compare(Object obj1, Object obj2)

obj1 and obj2 are the objects to be compared. This method returns zero if the objects are equal. It returns a positive value if obj1 is greater than obj2. Otherwise, a negative value is returned.

By overriding compare( ), you can alter the way that objects are ordered. For example, to sort in reverse order, you can create a comparator that reverses the outcome of a comparison.

The equals Method:

The equals( ) method, shown here, tests whether an object equals the invoking comparator:

boolean equals(Object obj)

obj is the object to be tested for equality. The method returns true if obj and the invoking object are both Comparator objects and use the same ordering. Otherwise, it returns false.

Overriding equals( ) is unnecessary, and most simple comparators will not do so.

Example:

class Dog implements Comparator<Dog>, Comparable<Dog>{
   private String name;
   private int age;
   Dog(){
   }

   Dog(String n, int a){
      name = n;
      age = a;
   }

   public String getDogName(){
      return name;
   }

   public int getDogAge(){
      return age;
   }

   // Overriding the compareTo method
   public int compareTo(Dog d){
      return (this.name).compareTo(d.name);
   }

   // Overriding the compare method to sort the age 
   public int compare(Dog d, Dog d1){
      return d.age - d1.age;
   }
}

public class Example{

   public static void main(String args[]){
      // Takes a list o Dog objects
      List<Dog> list = new ArrayList<Dog>();

      list.add(new Dog("Shaggy",3));
      list.add(new Dog("Lacy",2));
      list.add(new Dog("Roger",10));
      list.add(new Dog("Tommy",4));
      list.add(new Dog("Tammy",1));
      Collections.sort(list);// Sorts the array list

      for(Dog a: list)//printing the sorted list of names
         System.out.print(a.getDogName() + ", ");

      // Sorts the array list using comparator
      Collections.sort(list, new Dog());
      System.out.println(" ");
      for(Dog a: list)//printing the sorted list of ages
         System.out.print(a.getDogName() +"  : "+
		 a.getDogAge() + ", ");
   }
}

This would produce following result:

Lacy, Roger, Shaggy, Tammy, Tommy,
Tammy  : 1, Lacy  : 2, Shaggy  : 3, Tommy  : 4, Roger  : 10,

Note: Sorting of the Arrays class is as the same as the Collections.

Java - How to use Iterator?

Often, you will want to cycle through the elements in a collection. For example, you might want to display each element.

The easiest way to do this is to employ an iterator, which is an object that implements either the Iterator or the ListIterator interface.

Iterator enables you to cycle through a collection, obtaining or removing elements. ListIterator extends Iterator to allow bidirectional traversal of a list, and the modification of elements.

Before you can access a collection through an iterator, you must obtain one. Each of the collection classes provides an iterator( ) method that returns an iterator to the start of the collection. By using this iterator object, you can access each element in the collection, one element at a time.

In general, to use an iterator to cycle through the contents of a collection, follow these steps:

• Obtain an iterator to the start of the collection by calling the collection's iterator( ) method.
• Set up a loop that makes a call to hasNext( ). Have the loop iterate as long as hasNext( ) returns true.
• Within the loop, obtain each element by calling next( ).

For collections that implement List, you can also obtain an iterator by calling ListIterator.

The Methods Declared by Iterator:

SN	Methods with Description
1	boolean hasNext( ) Returns true if there are more elements. Otherwise, returns false.
2	Object next( ) Returns the next element. Throws NoSuchElementException if there is not a next element.
3	void remove( ) Removes the current element. Throws IllegalStateException if an attempt is made to call remove( ) that is not preceded by a call to next( ).

The Methods Declared by ListIterator:

SN	Methods with Description
1	void add(Object obj) Inserts obj into the list in front of the element that will be returned by the next call to next( ).
2	boolean hasNext( ) Returns true if there is a next element. Otherwise, returns false.
3	boolean hasPrevious( ) Returns true if there is a previous element. Otherwise, returns false.
4	Object next( ) Returns the next element. A NoSuchElementException is thrown if there is not a next element.
5	int nextIndex( ) Returns the index of the next element. If there is not a next element, returns the size of the list.
6	Object previous( ) Returns the previous element. A NoSuchElementException is thrown if there is not a previous element.
7	int previousIndex( ) Returns the index of the previous element. If there is not a previous element, returns -1.
8	void remove( ) Removes the current element from the list. An IllegalStateException is thrown if remove( ) is called before next( ) or previous( ) is invoked.
9	void set(Object obj) Assigns obj to the current element. This is the element last returned by a call to either next( ) or previous( ).

Example:

Here is an example demonstrating both Iterator and ListIterator. It uses an ArrayList object, but the general principles apply to any type of collection.

Of course, ListIterator is available only to those collections that implement the List interface.

import java.util.*;

public class IteratorDemo {

   public static void main(String args[]) {
      // Create an array list
      ArrayList al = new ArrayList();
      // add elements to the array list
      al.add("C");
      al.add("A");
      al.add("E");
      al.add("B");
      al.add("D");
      al.add("F");

      // Use iterator to display contents of al
      System.out.print("Original contents of al: ");
      Iterator itr = al.iterator();
      while(itr.hasNext()) {
         Object element = itr.next();
         System.out.print(element + " ");
      }
      System.out.println();
      
	  // Modify objects being iterated
      ListIterator litr = al.listIterator();
      while(litr.hasNext()) {
         Object element = litr.next();
         litr.set(element + "+");
      }
      System.out.print("Modified contents of al: ");
      itr = al.iterator();
      while(itr.hasNext()) {
         Object element = itr.next();
         System.out.print(element + " ");
      }
      System.out.println();

      // Now, display the list backwards
      System.out.print("Modified list backwards: ");
      while(litr.hasPrevious()) {
         Object element = litr.previous();
         System.out.print(element + " ");
       }
       System.out.println();
    }
}

This would produce following result:

Original contents of al: C A E B D F
Modified contents of al: C+ A+ E+ B+ D+ F+
Modified list backwards: F+ D+ B+ E+ A+ C+

Java - The Collection Algorithms

The collections framework defines several algorithms that can be applied to collections and maps.

These algorithms are defined as static methods within the Collections class. Several of the methods can throw a ClassCastException, which occurs when an attempt is made to compare incompatible types, or an UnsupportedOperationException, which occurs when an attempt is made to modify an unmodifiable collection.

The methods defined in collection framework's algorithm are summarized in the following table:

SN	Methods with Description
1	static int binarySearch(List list, Object value, Comparator c) Searches for value in list ordered according to c. Returns the position of value in list, or -1 if value is not found
2	static int binarySearch(List list, Object value) Searches for value in list. The list must be sorted. Returns the position of value in list, or -1 if value is not found.
3	static void copy(List list1, List list2) Copies the elements of list2 to list1.
4	static Enumeration enumeration(Collection c) Returns an enumeration over c.
5	static void fill(List list, Object obj) Assigns obj to each element of list.
6	static int indexOfSubList(List list, List subList) Searches list for the first occurrence of subList. Returns the index of the first match, or .1 if no match is found.
7	static int lastIndexOfSubList(List list, List subList) Searches list for the last occurrence of subList. Returns the index of the last match, or .1 if no match is found.
8	static ArrayList list(Enumeration enum) Returns an ArrayList that contains the elements of enum.
9	static Object max(Collection c, Comparator comp) Returns the maximum element in c as determined by comp.
10	static Object max(Collection c) Returns the maximum element in c as determined by natural ordering. The collection need not be sorted.
11	static Object min(Collection c, Comparator comp) Returns the minimum element in c as determined by comp. The collection need not be sorted.
12	static Object min(Collection c) Returns the minimum element in c as determined by natural ordering.
13	static List nCopies(int num, Object obj) Returns num copies of obj contained in an immutable list. num must be greater than or equal to zero.
14	static boolean replaceAll(List list, Object old, Object new) Replaces all occurrences of old with new in list. Returns true if at least one replacement occurred. Returns false, otherwise.
15	static void reverse(List list) Reverses the sequence in list.
16	static Comparator reverseOrder( ) Returns a reverse comparator
17	static void rotate(List list, int n) Rotates list by n places to the right. To rotate left, use a negative value for n.
18	static void shuffle(List list, Random r) Shuffles (i.e., randomizes) the elements in list by using r as a source of random numbers.
19	static void shuffle(List list) Shuffles (i.e., randomizes) the elements in list.
20	static Set singleton(Object obj) Returns obj as an immutable set. This is an easy way to convert a single object into a set.
21	static List singletonList(Object obj) Returns obj as an immutable list. This is an easy way to convert a single object into a list.
22	static Map singletonMap(Object k, Object v) Returns the key/value pair k/v as an immutable map. This is an easy way to convert a single key/value pair into a map.
23	static void sort(List list, Comparator comp) Sorts the elements of list as determined by comp.
24	static void sort(List list) Sorts the elements of list as determined by their natural ordering.
25	static void swap(List list, int idx1, int idx2) Exchanges the elements in list at the indices specified by idx1 and idx2.
26	static Collection synchronizedCollection(Collection c) Returns a thread-safe collection backed by c.
27	static List synchronizedList(List list) Returns a thread-safe list backed by list.
28	static Map synchronizedMap(Map m) Returns a thread-safe map backed by m.
29	static Set synchronizedSet(Set s) Returns a thread-safe set backed by s.
30	static SortedMap synchronizedSortedMap(SortedMap sm) Returns a thread-safe sorted set backed by sm.
31	static SortedSet synchronizedSortedSet(SortedSet ss) Returns a thread-safe set backed by ss.
32	static Collection unmodifiableCollection(Collection c) Returns an unmodifiable collection backed by c.
33	static List unmodifiableList(List list) Returns an unmodifiable list backed by list.
34	static Map unmodifiableMap(Map m) Returns an unmodifiable map backed by m.
35	static Set unmodifiableSet(Set s) Returns an unmodifiable set backed by s.
36	static SortedMap unmodifiableSortedMap(SortedMap sm) Returns an unmodifiable sorted map backed by sm.
37	static SortedSet unmodifiableSortedSet(SortedSet ss) Returns an unmodifiable sorted set backed by ss.

Example:

Following is the example which demonstrate various algorithms.

import java.util.*;

public class AlgorithmsDemo {

   public static void main(String args[]) {
      // Create and initialize linked list
      LinkedList ll = new LinkedList();
      ll.add(new Integer(-8));
      ll.add(new Integer(20));
      ll.add(new Integer(-20));
      ll.add(new Integer(8));
      
      // Create a reverse order comparator
      Comparator r = Collections.reverseOrder();
      // Sort list by using the comparator
      Collections.sort(ll, r);
      // Get iterator
      Iterator li = ll.iterator();
      System.out.print("List sorted in reverse: ");
      while(li.hasNext()){
         System.out.print(li.next() + " ");
      }
      System.out.println();
      Collections.shuffle(ll);
      // display randomized list
      li = ll.iterator();
      System.out.print("List shuffled: ");
      while(li.hasNext()){
         System.out.print(li.next() + " ");
      }
      System.out.println();
      System.out.println("Minimum: " + Collections.min(ll));
      System.out.println("Maximum: " + Collections.max(ll));
   }
}

This would produce following result:

List sorted in reverse: 20 8 -8 -20
List shuffled: 20 -20 8 -8
Minimum: -20
Maximum: 20