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.

Java Collections #1

I know its kind of weird to DIRECTLY start with java collections, since it is considered as an advance topic in Core Java. So beginners in Java or newbies might get a little uncomfortable while reading this post. Apologies for that ! I will try to make this as simple and easy and comfortable (... :) ...ha ha !) as possible. To remind you.....yes you ! .....dear Reader ! ... these are only my observations and findings. So my posts are open for discussions. Java Collections:- The guys who developed this awesome technology, ...i guess they were quiet smart enough to create a separate package to contain collections. I mean the idea to create this, came out of the need for ready to use codes for storing data (...well known as data structures.) They must have written a lot of programs for data structures like Linked list, Array list, Hash Map etc., ...and that too with many functionalities like sorting, adding , searching etc., Of course, these functionalities are required when you work with data structures. So this package => "java.util" contains all the classes and the interfaces that are required to work with the collections package. Classes representing data structures like arrays, lists, trees, sets, are a part of the collection framework. In other words the classes that provide these data structures belong to the family of Collection .... "Collection" interface, therefore is the first and the only ancestor of this family. Following is the family tree that represents Collections family :-



It can be seen from the above diagram that, "Collection" is the top-most parent of the family. The major implementations like "ArrayList" , "Vector", "LinkedList" ...etc., are the children of "Collection" interface. Let us understand this hierarchy first. The children at the first level are "List" and "Set". These are also interfaces, and hence are not concrete implementations. Since, "List" interface is the child of the "Collection" interface ... using the OOPS language we can also say that "List" is A "Collection".

List:-
List is A Collection
List is an ordered Collection
That means the elements are inserted one after another sequentially.
It allows duplicate elements to be inserted in the collection.

Set:-
Set is A Collection
Set cannot contain duplicate element.
Set allows at the most one null element only.
The Set does not have a specific implementation like the List has (...ordered collection)
Set can be implemented as a Tree or HashTable also! (Tree and HashTable are also data structures but little more complex compared to linked list, array list etc.,)

Now, since these are only the interfaces, implementation wise they are void... i.e., these interfaces only describe the contract that all the implementing classes must honor. These interfaces do not provide any implementation or logic related to that data structure. Now in order, to traverse through ordered collection like "List" they have also provided controls, like "Iterator". Using "Iterator" interface or the child of "Iterator" (...known as "ListIterator") we can safely access the elements in the "List" or any of its implementations.

Now, the top most parent "Collection" interfaces has given pure abstract contracts that must be implemented by any class that implements this Interface. Let us take a look at these contracts that are mostly required when we work with collections :-

add(Object o)
addAll(Collection c)
clear()
contains(Object o)
containsAll(Collection c)
remove(Object o)
removeAll(Collections c)
retainAll(Collection c)
size()
toArray()
toArray(Object[] o)

Majority of these contracts are implemented in the concrete classes that implement the "Collection" interface. For example, we will see the implementing classes like "ArrayList" , "Vector", "LinkedList".

ArrayList:-

add(Object o)
addAll(Collection c)
clear()
contains(Object o)

remove(Object o)

size()
toArray()
toArray(Object[] o)

As you can see majority of the contracts that the "Collection" Interface mentions are honored by the "ArrayList" class. Implementations for contracts like (containsAll(), removeAll(), retainAll() are not honored! ). Let us take a look at other class, "Vector".

Vector:-
add(Object o)
addAll(Collection c)
clear()
contains(Object o)
containsAll(Collection c)
remove(Object o)
removeAll(Collections c)
retainAll(Collection c)
size()
toArray()
toArray(Object[] o)

All the contracts are honored by this class ! :) .... Vector is pretty honest and humble it seems ! :) Now, take a look at the class => LinkedList

LinkedList:-
add(Object o)
addAll(Collection c)
clear()
contains(Object o)

remove(Object o)

size()
toArray()
toArray(Object[] o)

As can be seen, even LinkedList honors majority of the contracts that the "Collection" interface has mentioned.

Thus, by now it must have occured to you, how intelligently the Java guys have designed this package. Imagine this situation, you like Vectors a lot ! ... because of its dynamically growing quality and easy to add elements functionality. And lets say you also want the elements to be arranged and linked sequentially as a linked list, in that case, you can create a vector,... go on adding elements into it and pass it as a "Collection" to an empty "LinkedList" object using the function addAll(Collection c) function. Isn't it great ! This is where you will get to see the MAGIC OF INHERITANCE and POLYMORPHISM.

So, even if you know certain contracts that i have mentioned above, you can work with any damn implementaion of the Collection interface since it will somehow have to honor those contracts.

I think this is sufficient for today. In the next post i will discuss about some classes and few programs that i have worked upon.

Till then have a good day ....dear Reader ! :)

Thanking you
Omkar Patkar

About Myself :- Omkar Patkar

Hello freinds,

Before i start my blog, a brief introduction about myself. Myself, Omkar Patkar, am a Software Engineer in Java Technology. Its only been one year and six months of IT industry experience that i have. Out of my every day's experience while working in the java technology, i come across certain things, that i want to note down somewhere ....Of course, some people already might know these things, ... where as some people might not know. In my free time i also, work on few Java programs. I want to note my findings somewhere. It struck to me that i can create blogs where in i can record my findings in the form of articles. You can use my blogs as a reference OR as a topic of debate / discussion etc., Well thats about me and what my blogs are going to be ! ... So lets get started ! :)


Thanks and Regards

Omkar Patkar