https://leanpub.com/discretemathematicalalgorithmanddatastructures
Java Collection framework provides three major interfaces, which have all the qualities of being important and worthy of note. Comparison plays a great role in sorting or shuffling algorithm. In the like manner, iteration is also very important.
We are going to see a few code snippets where these three interfaces ( Comparator, Comparable and Iterator ) are implemented.
To get elements in sorted order, we can use TreeSet and TreeMap from Java Collection Framework; but, it is the Comparator or the Comparable interface that precisely defines what sorted order means.
Implementing the Comparator and Comparable interfaces, we can have objects that encapsulate ordering. Watch the next code snippet:
package fun.sanjibsinha.chapter7.collection;
/**
* How Comparator and Comparable interfaces are implemented by a class
* to sort String and Integer data types provided by List and
* ArrayList data structures
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
class Account implements Comparator<Account>, Comparable<Account> {
private String accountHoldersName;
private int accountNumber;
Account() {
}
Account(String name, int number) {
accountHoldersName = name;
accountNumber = number;
}
public void setAccountHoldersName(String accountHoldersName) {
this.accountHoldersName = accountHoldersName;
}
public String getAccountHoldersName() {
return accountHoldersName;
}
public void setAccountNumber(int accountNumber) {
this.accountNumber = accountNumber;
}
public int getAccountNumber() {
return accountNumber;
}
/**
* overriding the compareTo() method to sort the name
* @param account
* @return
*/
public int compareTo(Account account) {
return (this.accountHoldersName).compareTo(account.accountHoldersName);
}
/**
* overriding the compare() method to sort the account number
* @param account
* @param anotherAccount
* @return
*/
public int compare(Account account, Account anotherAccount) {
return account.accountNumber - anotherAccount.accountNumber;
}
}
public class ComparatorInterfaceExample {
public static void main(String[] args) {
// list of account object
List<Account> listOfAccounts = new ArrayList<Account>();
listOfAccounts.add(new Account("Sanjib", 203));
listOfAccounts.add(new Account("Json", 205));
listOfAccounts.add(new Account("John", 201));
listOfAccounts.add(new Account("Hicky", 204));
listOfAccounts.add(new Account("Amubrata", 202));
// sorting the ArrayList
Collections.sort(listOfAccounts);
/**
* printing the sorted names
*/
System.out.println("Printing the sorted names of account holders: ");
for(Account account: listOfAccounts){
System.out.print(account.getAccountHoldersName() + ", ");
}
/**
* sorting the ArrayList with the help of comparator
*/
Collections.sort(listOfAccounts, new Account());
System.out.println(" ");
/**
* sorting based on account numbers
*/
System.out.println("Printing the names of account holders based on sorted account" +
" numbers in ascending numbers: ");
for(Account account: listOfAccounts)
System.out.print(account.getAccountHoldersName() + " : "
+ account.getAccountNumber() + ", ");
}
}First of all, we have sorted the names of the account holders; in similar fashion, we have printed the names of account holders based on sorted account numbers in ascending numbers.
Printing the sorted names of account holders:
Amubrata, Hicky, John, Json, Sanjib,
Printing the names of account holders based on sorted account numbers in ascending numbers:
John : 201, Amubrata : 202, Sanjib : 203, Hicky : 204, Json : 205,
Process finished with exit code 0What will happen if inadvertently someone adds a negative account number? Therefore, for the second part of the code where we have implemented Comparator interface method compare(), we should write the logic in this way.
public int compare(Account account, Account anotherAccount) {
/**
* Don't do it unless you're absolutely
* sure no one will ever have a negative account number!
*/
//return account.accountNumber - anotherAccount.accountNumber;
/**
* this is more logical approach
*/
return (account.accountNumber < anotherAccount.accountNumber ? -1 :
(account.accountNumber == anotherAccount.accountNumber ? 0 : 1));
}
Printing the sorted names of account holders:
Amubrata, Hicky, John, Json, Sanjib,
Printing the names of account holders based on sorted account numbers in ascending numbers:
John : 201, Amubrata : 202, Sanjib : 203, Hicky : 204, Json : 205,
Process finished with exit code 0Now, our code is more protected. Why we need to take such protections? It is little bit theoretical and this book is not about only Java Collection Framework. Yet, it is good to know that if an integer is a large positive integer and another integer is a large negative integer, then their subtraction will return a negative integer. To represent the difference of two arbitrary signed integers, a signed integer type is not big enough.
When we implement Comparable or Comparator interfaces, we need to maintain the technical restrictions.
If we want to compare two elements, especially for that type of algorithm, implementing the Comparable interface is always the better choice.
package fun.sanjibsinha.chapter7.collection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
class City implements Comparable<City>{
private String name;
City(String name){
if (name == null){
throw new NullPointerException();
}
this.name = name;
}
public String displayName(){
return name;
}
public String toString(){
return name;
}
@Override
public int compareTo(City city) {
int lastCompare = name.compareTo(city.name);
return (lastCompare != 0 ? lastCompare : name.compareTo(city.name));
}
}
public class ComparableInterfaceExample {
public static void main(String[] args) {
City cityNames[] = {
new City("Berlin"),
new City("Kolkata"),
new City("Munich"),
new City("Paris"),
new City("Mew York"),
};
List<City> names = Arrays.asList(cityNames);
Collections.sort(names);
System.out.println("The city names in ascending order: ");
System.out.println(names.toString());
}
}
We can get the city names in ascending order. For the algorithm that is related to sorting and comparing, it is a good choice in Java Collection framework.
The city names in ascending order:
[Berlin, Kolkata, Mew York, Munich, Paris]
Process finished with exit code 0Finally we will curtain the Java Collection framework with iteration. It is also a very important part of algorithm and data structure. Java Collection framework handles it quite well by implementing the Iterator interface.
package fun.sanjibsinha.chapter7.collection;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;
/**
* An Iterator is an object that enables you to traverse through a collection
* public interface Iterator<E> {
* boolean hasNext();
* E next();
* void remove(); //optional
* }
* An Iterator object implements either Iterator, or ListIterator interface
*/
public class IteratorInterfaceExample {
public static void main(String[] args) {
/**
* creating an ArrayList that will use iterator object
*/
ArrayList arrayList = new ArrayList();
/**
* adding some city names to the array list
*/
arrayList.add("Calcutta");
arrayList.add("Allahabad");
arrayList.add("Edinburgh");
arrayList.add("Berlin");
arrayList.add("Detroit");
arrayList.add("Fujiyama");
/**
* we can use iterator to display all the city names now
*/
System.out.print("The city names as entered in the list : ");
Iterator itratorObject = arrayList.iterator();
while(itratorObject.hasNext()) {
Object element = itratorObject.next();
System.out.print(element + ", ");
}
System.out.println();
/**
* ListIterator object can implement the ListIterator interface
*/
ListIterator listIterator = arrayList.listIterator();
System.out.print("Now we can cycle through the city names forward through listIterator : ");
System.out.println();
while(listIterator.hasNext()) {
Object element = listIterator.next();
listIterator.set(element);
System.out.println(element);
}
System.out.print("Now we can cycle through the city names forward through iterator : ");
itratorObject = arrayList.iterator();
while(itratorObject.hasNext()) {
Object element = itratorObject.next();
System.out.print(element + ", ");
}
System.out.println();
System.out.print("Now we can cycle through the city names forward through listIterator : ");
while(listIterator.hasPrevious()) {
Object element = listIterator.previous();
System.out.print(element + ", ");
}
System.out.println();
}
}To traverse through a collection of elements, we need iteration; and, to do that we need an iterator object that implements the Iterator interface.
The city names as entered in the list : Calcutta, Allahabad, Edinburgh, Berlin, Detroit, Fujiyama,
Now we can cycle through the city names forward through listIterator :
Calcutta
Allahabad
Edinburgh
Berlin
Detroit
Fujiyama
Now we can cycle through the city names forward through iterator : Calcutta, Allahabad, Edinburgh, Berlin, Detroit, Fujiyama,
Now we can cycle through the city names forward through listIterator : Fujiyama, Detroit, Berlin, Edinburgh, Allahabad, Calcutta,
Process finished with exit code 0When we want to iterate through the elements in a collection, and display each element, the easiest way is shown above. Employing an iterator object is the best solution to such algorithmic problems. The iterator object either implements the Iterator interface, or implements ListIterator interface.
Sanjib Sinha 