Collection is an efficient organiazation of data by using
arrays, lists, staks, etc ... In java, the class Collection
manages a set of classes. Iterators are used to go through a
collection from start to end.
Java collections Framwork is organized as follows:
1. Interfaces
--------------
- 1.1 Collection:
-----------------
Which has two parts:
- 1.1.1. Set: is a group of values where the duplication is
not allowed.
Example A = {1,2,4,8} is a set that inherites Collection.
Set contains:
1.1.1.1. sorted set
1.1.1.2. tree set
1.1.1.3. hash set
- 1.1.2. List: is a group of values where the duplication
is permitted.
Example A = {1,2,4,4,8} is a set that inherites Collection.
It contains:
1.1.2.1. Array list
1.1.2.2. Linked list
- 1.2 Map:
-----------
A map is a set of couples. Each couple contains two elements. The
first element is called key, and the second is the associated value
of the key. Let's write:
Map : (key, itsValue)
It contains:
1.2.1. sorted Map
1.2.2. tree Map
1.2.3. hash Map
2. Their implementations
------------------------
We do not implement from a collection interface.
The implementation is done from set and list and from Map
We implement:
from List: ArrayList and LinkedList,
from Set: hashSet and TreeSet,
from Map : hashmap and TreeMap.
3. Applications
----------------------
3.1. Collection
-----------------
public interface Collection //No impplementation, but can extends Iterable
{
// Basic Operations on an object
int size();// size of the collection
boolean isEmpty();//Empty are full?
boolean contains(Object element);// An object: Is it present in the collection?
boolean add(Object element);
boolean remove(Object element);
Iterator iterator();
int hashCode();//return the code computed for the ollection
boolean equals(Object element);//Two objects are equal?
// Operations on sets of objects
boolean containsAll(Collection c);// All the elements : Are they presents in the collection?
boolean addAll(Collection c);
boolean removeAll(Collection c);
boolean retainAll(Collection c); //As an intersection of two sets
void clear(); //clear the colection: remove all the elements.
// Array Operations
Object[] toArray();// return the elements of the collection in an array
Object[] toArray(Object a[]);
// Allow to set another array for the elements of the collection
}
The interface collection instanciates the interface Iterator.
this class allow going thru the collection:
public interface Iterator
{
boolean hasNext();//is there a next?
Object next();//points to the next element
void remove(); // retreive the current element (this)
}
Example of code:
Collection collection = ...;
Iterator iterator = collection.iterator();
while (iterator.hasNext())
{
Object element = iterator.next();
if (removalCheck(element))
{
iterator.remove();
}
}
3.2. Set
---------
Two possibles implementations:
TreeSet: The elements are sorted fromthe smallest tho the bigest,
HashSet: The elements are sorted acording to a hash method.
3.3. List
-----------
List is an orderly collection that allows duplication. This interface
is reinfoced by methods to add or to retreive elements in a certain rank.
We use also sublists ArrayList and LinkedList when elements are inserted
in the list.
public interface List extends Collection
{
// Positional Access
Object get(int index);// Return the element of the index index
Object set(int index, Object element); //Modify the element of the index index
void add(int index, Object element);
Object remove(int index); // Reove the element of the index index
boolean addAll(int index, Collection c);
// Search
int indexOf(Object o);//Search for the element and return its index
int lastIndexOf(Object o);//Search for the element and return its last index (duplication is possible)
// Iteration
ListIterator listIterator();
ListIterator listIterator(int index);
// Range- and view
List subList(int fromIndex, int toIndex);// create a sublist of a list
}
public interface ListIterator extends Iterator //ListIterator : just for lists
{
boolean hasNext();//Is there a next?
Object next();//Points to the current element (this)
boolean hasPrevious();
Object previous();
int nextIndex();//retun the next index of the current element (this)
int previousIndex();
void remove();
void set(Object o);
void add(Object o);
}
This Iterator can go through the list in the two directions
and modify (set) an element or add another element.
Example of code:
List list = ...;
ListIterator iterator = list.listIterator(list.size());
while (iterator.hasPrevious())
{
Object element = iterator.previous();
}
The sublists are extracted from the lists since fromIndex
(included) to toIndex (not included).
3.4. Map
-----------
A Map is a set of couples: (key, itsValue). For a multi-Map, we
can associate several values for a each key. Two keys can not be equals.
public interface Map
{
// Basic Operations
Object put(Object key, Object value);
Object get(Object key);
Object remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
// Bulk Operations
void putAll(Map t);
void clear();
// Collection Views
public Set keySet();
public Collection values();
public Set entrySet();
// Interface for entrySet elements
//The interface Entry can be work in the following manner:
public interface Entry
{
Object getKey();// returns the key
Object getValue();//returns the associated value
Object setValue(Object value);//to modify the value of a couple. To set a key, we have to set the couple.
}
}
Examples with iterators:
values: returns values in Collections form.
keySet and entrySet return, respectivly a (Set) of keys and
a (set) of Entry.
If m is a HashMap, values, keySet, and entrySet can be used
for iteration as follows:
// Keys
for (Iterator i = m.keySet().iterator();i.hasNext();)
System.out.println(i.next());
// Values
for (Iterator i = m.values().iterator();i.hasNext();)
System.out.println(i.next());
//Couples (key, Value)
for (Iterator i = m.keySet().iterator();i.hasNext();){
Map.Entry e = (Map.Entry) i.next();
System.out.println(e.getKey() + " ; " + e.getValue());
}
3.5. Related algorithms
------------------------
The algorithms that handle collections are presents in the class
Collection (not interface Collection). All the related methods are
defined as static.
Methods for lists:
Sort:
-------
sort(List list) ; //sort a list.
sort(List list,Comparator comp) ; //Sort a list using comparator
Shuffle:
--------
shuffle(List list) ; //Suffle the elements randomly
Handle:
--------
reverse(List list) ;
//reverse the elements fo the list
fill (List list, Object element) ;
//initialize the list with the element
Copy:
-----
copy(List dest, List src) ;
//Copy the list src in the list dest
Search:
---------
binarySearch(List list, Object element) ;
//Serach for a binary element
binarySearch(List list, Object element, Comparator comp) ;
//Serach for a binary element by using a comparator
min, max: (applied for all collections
---------
min (Collection)
max (Collection)
3.6 Interface Comparable:
--------------------------
Used to sort a list. This class has only one method: compareTo:
interface Comparable
{
int compareTo(Object obj);
}
This methods returns:
- a positif integer if an object is greater than obj
- zero if they equals
- a negative integer if an object is lesser than obj
We use this interface when we want to sort objects as Rectangles. When we want to
compare and sort in differents ways the values of primitive types (int, char,
String, double, ...), we use instead the interface Comparator. Here is an example:
interface Comparator
{
int compare(Object o1, Object o2);
boolean equals(Object object);
}
class CaseInsensitiveComparator implements Comparator
{
public int compare(Object element1,Object element2)
{
String lowerE1 = (
(String)element1).toLowerCase();
String lowerE2 = (
(String)element2).toLowerCase();
return lowerE1.compareTo(lowerE2);
}
}
All the libraries of collections are in JGL (Generic collections library).
|
