Java Collections # 3

Hi Guys,

As i said earlier in this post we will take a look at the other part of the java collection. And this other part of the java collections family is "Set". Refer to the figure availabe in the post Java Collections # 1 !

In this episode we will take a look at Set and its implementations. Sets contains unique elements. That means duplicates are not allowed.
Although some implementations might not allow even null, those implementations that allow null, they will allow ONLY one null.
Set is an interface. Following is the list of classes that implement the interface directly or indirectly :-

HashSet
LinkedHashSet
TreeSet

Following program will demonstrate to you, the ordering of the elements in the concrete class :-
-------------------------------------------
Listing #2
-------------------------------------------
package dev.data.workSpace.projects.scjp.section9.set;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;


public class SetExampleTester {

/**
* Omkar
*
* 15 Jun, 2007
* 9:43:56 AM
* SetExampleTester
* main
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

Set set ;
HashSet hashSet = new HashSet();
LinkedHashSet linkedHashSet = new LinkedHashSet();
TreeSet treeSet = new TreeSet();

// Setting the reference of Hashset to Set.
set = hashSet;
/*set.add("Omkar");
set.add("maria");
set.add("MariA");
set.add("Patkar");
set.add("Sharapova");
set.add("OMKAR");*/
set.add(new Integer(12));
set.add(new Integer(-12));
set.add(new Integer(34));
set.add(new Integer(-67));
set.add(new Integer(990));
set.add(new Integer(0));

System.out.println("set "+set);
System.out.println("Thus the elements in the HashSet are not in any particular order.\n");

// Setting the reference of Hashset to LinkedHashSet.
set = linkedHashSet ;
/*set.add("Omkar");
set.add("maria");
set.add("MariA");
set.add("Patkar");
set.add("Sharapova");
set.add("OMKAR");*/
set.add(new Integer(12));
set.add(new Integer(-12));
set.add(new Integer(34));
set.add(new Integer(-67));
set.add(new Integer(990));
set.add(new Integer(0));

System.out.println("set "+set);
System.out.println("Thus the order of elements in the treeset is same as the insertion order.\n");

// Setting the reference of Hashset to TreeSet.
set = treeSet ;
/*set.add("Omkar");
set.add("maria");
set.add("MariA");
set.add("Patkar");
set.add("Sharapova");
set.add("OMKAR");*/
set.add(new Integer(12));
set.add(new Integer(-12));
set.add(new Integer(34));
set.add(new Integer(-67));
set.add(new Integer(990));
set.add(new Integer(0));

System.out.println("set "+set);
System.out.println("Thus the order of elements in the treeset is sorted.");


}

}



-------------------------------------------------------------
The output of this program is as follows :-
-------------------------------------------------------------
set [0, 34, 990, -12, -67, 12]
Thus the elements in the HashSet are not in any particular order.

set [12, -12, 34, -67, 990, 0]
Thus the order of elements in the treeset is same as the insertion order.

set [-67, -12, 0, 12, 34, 990]
Thus the order of elements in the treeset is sorted.

-------------------------------------------------------------


Thus the output of the program itself demonstrates for the ordering of the elements in these classes.

Since we have seen the core functionality that Collection interface provides,....we will not get into the details of how Set implementations honor these contracts... after all sets are also, collections ! :)

But Here in sets there is an additional functionality that we should discuss here!
And that functionality is subset functionality ! Remember, ONLY "SortedSet" and its implementation have this funcionality !

We will take a look at following program that will illustrate how the subset functionality is implemented. For this we take example of TreeSet in our program
-------------------------------------------
Listing #3
-------------------------------------------
package dev.data.workSpace.projects.scjp.section9.set;

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

public class SetExampleTesterTree1 {

/**
* Omkar
* 2 Jul, 2007
* 8:24:33 PM
* SetExampleTesterTree1
* main
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeSet treeSet = new TreeSet();
/*treeSet.add(new Integer(12));
treeSet.add(new Integer(-12));
treeSet.add(new Integer(34));
treeSet.add(new Integer(-67));
treeSet.add(new Integer(990));
treeSet.add(new Integer(0));*/
treeSet.add("omkar");
treeSet.add("anant");
treeSet.add("patkar");
treeSet.add("java");
treeSet.add("sun");
treeSet.add("microsystem");
treeSet.add("technology");
treeSet.add("open source");
treeSet.add("micosoft sucks !");
treeSet.add("c# is copy of java");


System.out.println("treeSet "+treeSet);

Set subRightSet = treeSet.subSet("java","sun");
System.out.println("subset "+subRightSet+" ... This subset is a \"half-open range\" subset ---> From Right hand side!");
Set subLeftSet = treeSet.subSet("java"+"\0","sun");
System.out.println("subset "+subLeftSet+" ... This subset is a \"open range\" subset ---> From Left hand side!");
Set fullCloseSubSet = treeSet.subSet("java","sun"+"\0");
System.out.println("subset "+fullCloseSubSet+" ... This subset is a \"closed range\" subset !");

treeSet = new TreeSet();
treeSet.add(new Integer(1));
treeSet.add(new Integer(12));
treeSet.add(new Integer(31));
treeSet.add(new Integer(45));
treeSet.add(new Integer(-91));
treeSet.add(new Integer(867));
treeSet.add(new Integer(432));
treeSet.add(new Integer(75));
treeSet.add(new Integer(21));
treeSet.add(new Integer(1091));


System.out.println("\n\n "+treeSet);
subRightSet = treeSet.subSet(new Integer(21),new Integer(432));
System.out.println("subset "+subRightSet+" ... This subset is a \"half-open range\" subset ---> From Right hand side!");
subLeftSet = treeSet.subSet(new Integer(22),new Integer(432));
System.out.println("subset "+subLeftSet+" ... This subset is a \"open range\" subset ---> From Left hand side!");
fullCloseSubSet = treeSet.subSet(new Integer(21),new Integer(433));
System.out.println("subset "+fullCloseSubSet+" ... This subset is a \"closed range\" subset !");

}

}

-------------------------------------------

And the output of the program is :-

treeSet [anant, c# is copy of java, java, micosoft sucks !, microsystem, omkar, open source, patkar, sun, technology]
subset [java, micosoft sucks !, microsystem, omkar, open source, patkar] ... This subset is a "half-open range" subset ---> From Right hand side!
subset [micosoft sucks !, microsystem, omkar, open source, patkar] ... This subset is a "open range" subset ---> From Left hand side!
subset [java, micosoft sucks !, microsystem, omkar, open source, patkar, sun] ... This subset is a "closed range" subset !


[-91, 1, 12, 21, 31, 45, 75, 432, 867, 1091]
subset [21, 31, 45, 75] ... This subset is a "half-open range" subset ---> From Right hand side!
subset [31, 45, 75] ... This subset is a "open range" subset ---> From Left hand side!
subset [21, 31, 45, 75, 432] ... This subset is a "closed range" subset !

-------------------------------------------

Now let us try to understand how the subSet() function works, and subsequently why we got such a result :-

subSet() function returns a SortedSet with the lower value inclusive and the higher value exclusive. This is called as half-open range ! Therefore when we say :-

treeSet.subSet("java","sun"); ... then,

out of the set => [anant, c# is copy of java, java, micosoft sucks !, microsystem, omkar, open source, patkar, sun, technology]

a subset as [java, micosoft sucks !, microsystem, omkar, open source, patkar] is obtained ...as u can see the lower value "java" is included in the subset and the higher value "sun" is not included !

But lets say we want to include the higher value also,...then what do we do ?
For that we have used something like this :-

treeSet.subSet("java","sun"+"\0");

because of this now the subset that is returned will contain both "java" and "sun" how was this possible ? .... For that we need to understand how the subSet() function works ! When we specify two arguments to this function, then this function uses these arguments to return a subset as follows :-
The first argument is taken and checked if this argument is greater than or equal to any element in the sorted set. If an element is found... then that element will be the first element in the subset that will be returned .... now an element is searched in the original list such that the element is less than the second argument that we have provided. If an element is found then that element will be the last element of the subset that will be returned.

Therefore now u know when we called the function like this :-

treeSet.subSet("java","sun");

at that time an element "java" was found which is greater than equal to the first argument and hence the subset that is returned contains this element as the first element. Now, an element "patkar" is obtained that is less than "sun" and hence this element becomes the last element of the subset that is returned. Hence this subset is half open subset as it does not include the higher value i.e., "sun".

NOTE :- The comparisons that took place for these objects of type String were lexicographical which means "java" is lexicographically less than "sun".

So why use only "\0" to include the higher value ?

Well, based upon the discussion in the above paragraph, when the elements in the set are compared to the second argument an element "sun" is found which is lexicographically less than "sun"+"\0" ...i.e., "sun\0". That means the second argument could have been any string that starts with "sun" and ends with any thing ! .... Therefore if u provide, String like "sunoja" OR "sun23" OR "sunny" as the second argument it would have given the same result with "sun\0" as the second argument !

hmmm.... ! So what are we achieving by calling :-

treeSet.subSet("java"+"\0","sun");

Again, the same FUNDA ! elements in the set are searched to see if there is any element that is greater than or equal to the 1st argument that is "java"+"\0" ...i.e., "java\0". Now, there is an element "java" in the set, but it is lexicographically less than "java\0"...therefore it is automatically excluded from the subSet that will be returned. The element next to "java" in the set is "microsoft sucks!" which is lexicographically greater than or equal to "java\0" ...and hence it is selected as the starting element of the subSet that is returned.
So if u observe now the subset that is returned neither includes the lower value nor the higher value that we had specified as two arguments in the subSet() function. Such a range is called as the Closed range !

I know i know ,....this seemingly simple thing subSet() is looking so complex because of this Lexicographical thing. And that is the reason why i have included the example of subSet using Integers. I thought that playing with numbers will be always easy compared to playing with the Strings. Just go through the listing and the output,...and soon the funda of subSet will be understood by you.

functions like tailSet(), headSet() are also based upon similar principle.

Well thats enough for today, in the next episode we will meet another family which claims to be a distant relative of Collections - yes ! ..ladies and gentlemen stay tuned for next episode of the new family of Collections - "The Map" family !

Thanks and Regards
Omkar Patkar.

Java Collections #2

Hi Guys,

Welcome back, this is second episode on Java collections. In this episode we are going to take a look at a program based on the collections. :-

-------------------------------------------
Listing #1
-------------------------------------------
package dev.data.workSpace.projects.scjp.section9;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

public class ListExampleTester {

/**
* Omkar
* 15 Jun, 2007
* 9:43:56 AM
* ListExampleTester
* main
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

ListExample listExample = new ListExample();

Vector vector = new Vector(10,3);
LinkedList linkedList = new LinkedList();
vector.add(new Integer(2));
vector.add(new Integer(23));
vector.add(new Integer(-2121));
vector.add(new Integer(92));
vector.add(new Integer(0));
vector.add(new Integer(-654));
vector.add(new Integer(13));
vector.add(new Integer(9876));

System.out.println("The Vector now contains the following elements :-");
System.out.println("vector "+vector);
System.out.println("Initially the list is empty :-");
System.out.println("linkedList "+linkedList);

System.out.println("Now the Vector elements are added into the empty list using the \"addAll()\" function");
linkedList.addAll(vector);
System.out.println("After adding all the elements to the linked list the contents of the list are :-");
System.out.println("linkedList "+linkedList);

System.out.println("Clearing the vector ...");
vector.clear();

Collections.sort(linkedList);
System.out.println("Now the linked list looks something like this after sorting");
System.out.println("linkedList "+linkedList);

System.out.println("Now filling the vector again from the sortelist similary by using the \"addAll()\" function.");
vector.addAll(linkedList);
System.out.println("now the vector looks like this :-");

System.out.println("Now the vector looks like this ");
System.out.println("vector "+vector);

System.out.println("Creating an unmodfiable list from the vector");
LinkedList linkedList2 = new LinkedList();

linkedList2.addAll(Collections.unmodifiableCollection(vector));
System.out.println("The new list looks something like this ");
System.out.println(linkedList2);

linkedList2.add(0,new Integer(010));
System.out.println("Adding one element to the unmodifiable list, this list looks something like this ");
System.out.println(linkedList2);

List list = Collections.unmodifiableList(vector);
System.out.println("Above list was not unmodifiable,..But following list is unmodifiable list ");
System.out.println(list);


// Following line will throw a java.lang.UnsupportedOperationException since we cannot modify a un-modifiable list.
// list.add(new Integer(9999));
// System.out.println(list);
// System.out.println("Following line show what will removeAll() method return when it is called on an unmodifiable list.");
// System.out.println("list.removeAll()"+list.removeAll(list));



System.out.println("linkedList2.removeAll() "+linkedList2.removeAll(linkedList2)); // Will print "true"
System.out.println("linkedList2.removeAll() "+linkedList2.removeAll(linkedList2)); // Will print "false"
// Following line will throw a Exception
//linkedList2.add("Omkar");
//linkedList2.add("Patkar");
//linkedList2.add("is ");
//linkedList2.add("gr8");
//linkedList2.add("guy !");
//linkedList2.addAll(Collections.unmodifiableCollection(vector));
//System.out.println("Unsorted "+linkedList2);
//Collections.sort(linkedList2);
//System.out.println("Sorted "+linkedList2);


}

}

-------------------------------------------------------------
The output of this program is as follows :-
-------------------------------------------------------------
The Vector now contains the following elements :-
vector [2, 23, -2121, 92, 0, -654, 13, 9876]
Initially the list is empty :-
linkedList []
Now the Vector elements are added into the empty list using the "addAll()" function
After adding all the elements to the linked list the contents of the list are :-
linkedList [2, 23, -2121, 92, 0, -654, 13, 9876]
Clearing the vector ...
Now the linked list looks something like this after sorting
linkedList [-2121, -654, 0, 2, 13, 23, 92, 9876]
Now filling the vector again from the sortelist similary by using the "addAll()" function.
now the vector looks like this :-
vector [-2121, -654, 0, 2, 13, 23, 92, 9876]
Creating an unmodfiable list from the vector
The new list looks something like this
[-2121, -654, 0, 2, 13, 23, 92, 9876]
Adding one element to the unmodifiable list, this list looks something like this
[8, -2121, -654, 0, 2, 13, 23, 92, 9876]
Above list was not unmodifiable,..But following list is unmodifiable list
[-2121, -654, 0, 2, 13, 23, 92, 9876]
linkedList2.removeAll() true
linkedList2.removeAll() false
-------------------------------------------------------------


===================================
This program demonstrates following observations :-
===================================

1. linkedList2.addAll(Collections.unmodifiableCollection(vector)); will not make the linkedList2 as the unmodifiable list because, the linkedList2 was created as LinkedList linkedList2 = new LinkedList(); and here by default list is MODIFIABLE only the elements inserted into this by default modifiable list were obtained from Collections.unmodifiableList()...but this does not make the list unmodifiable.
2. Once the Collection obtained is unmodifiable, then the collection can only be read, and things like updates, inserts, deletes will not work.
3. Consider a modifiable List object. It contains few elements. When removeAll() is called on this list object for the first time then the removeAll() method returns a "true". An immediate call of "removeAll()" on the same empty list will return "false".
   This is because, the removeAll() method returns false when called on an empty collection.
4. The difference between the "clear()" and the "removeAll()" method, is that former has return type as void and the later has the return type as boolean indicating if the removeAll operation was done properly or not.
5. Adding of Heterogenous objects that is objects of different types, is possible for a given collection. But performing operations like sorting is not possible, since the objects belonging to different types have nothing in common to compare with while sorting.
   

===================================

As you can see i have used a utitlity class available in this Collection framework. The name of the class is "Collections". This class provides many, utitlity methods like sorting....that i have used in the example.

So this was just about one part of the collections, i.e., the List and its subclasses. In my next post we will try to explore the other part of Collections framework.

Thanks and Regards
Omkar Patkar.