/**
* Sandeep Desai s_desai@hotmail.com http://www.thedesai.net
*
* Collections.java
* Sample program to demonstrate Java 1.4 Collections features
*
* Book Reference: Thinking in Java 3rd Ed
**/
/**
* JDK 1.0 Collections
* Vector, Hashtable methods are synchronized (slow)
*
* New JDK 1.2 Collections (not synchronized)
*
* Collection holds objects only
* Set cannot have duplicates, List can have duplicates
* Map is a Hash Table (Associative Array)
* Collections can be ordered (store/retreive in specific order) or sorted
* In inheritance tree below leaf level items are class
* everything else is interface
* Note Collection interface and Collections class different
*
* Collection can be ordered, retrieval order should match insert order
* i.e iterate over the collection in a specific order
* Collection can be sorted by natural order
*
* java.util.Collections class provides methods to
* sort, binary search, get synchronized list, min, max, rotate,
* get immutable list
*
* equals(null) should not throw nullpointer exception it should return false
* hashcode maybe negative
*
*
* +Collection
* |
* +---+Set
* | |
* | +--HashSet (provides constant time performance, can have null keys)
* | +--LinkedHashSet (ordered set)
* | +--+SortedSet (Interface)
* | +--TreeSet
* |
* +---+List
* |
* +--Vector (old Java 1.0 synchronized)
* +--ArrayList
* +--LinkedList (doubly linked list methods add/remove first/last)
*
* +Map
* |
* +---Hashtable (old Java 1.0 synchronized) extends abstract class Dictionary
* +---HashMap (can have null values and null keys)
* +---LinkedHashMap (ordered HashMap) (retrieve entries in order inserted)
* + (has accessOrder parameter for LRU or MRU)
* +---IdentityHashMap (compares using == instead of equals, violates HashMap contract)
* +---WeakHashMap (key removed when not in use)
* +---+SortedMap
* |
* +--TreeMap
*
*
* interface Collection
* return true if collection changed for methods below
* add(Object o) remove(Object o)
* addAll(Collection c), removeAll(Collection c)
*
* clear()
* boolean contains(Object obj)
* boolean containsAll(Collection c)
* boolean isEmpty()
* Iterator iterator()
* retainAll(Collection c) // true if collection changed
* int size()
* Object[] toArray()
*
* interface Set extends Collection // no methods added
*
* interface List extends Collection
* get(int index) indexOf(Object o)
*
* interface Iterator
* hasNext(), next() , remove()
*
* interface ListIterator extends Iterator
* hasPrevious() previous() nextIndex() previousIndex set(Object o)
*
*
* Map does not implement Collection.
* Dictionary is a class, not an interface.
* Collection is an Interface where as Collections is a helper class.
* .equals() returns false if the object types are different.
* It does not raise a compiler error for null
**/
import java.util.*;
public class JavaCollections {
public static void arrays() {
int[] a1 = new int[2];
Person[] as = new Person[2];
as[0] = new Person("one", 11); // holds reference to String object
as[1] = new Person("two", 12);
// initialize all array elements to 1, fill available for all
// primitive data types and objects
Arrays.fill(a1, 1);
int[] a2 = new int[2];
boolean b = Arrays.equals(a1, a2); // Are two arrays equal
String[] s1 = { "zaa", "bar", "foo" };
String[] s2 = new String[3];
// make copy of array makes a shallow copy and copies references only
System.arraycopy(s1, 0, s2, 0, 3);
Arrays.sort(s1, new StringComparator());
Arrays.sort(as); // throw exception ???
// sort using the comparator in Person
Arrays.sort(as, new Person("temp", 1));
// binary search on a sorted array, returns >= 0 if found
// or negative number which is index where element could be inserted
int index = Arrays.binarySearch(s1, "bar"); // returns 2
index = Arrays.binarySearch(s1, "car"); // returns -2
List list = Arrays.asList(s1); // Convert array to collection
}
public static Person[] getPersons()
{
return new Person[] {
new Person("one", 11),
new Person("two", 12),
new Person("three", 13) };
}
// legacy collection objects since Java 1.0 are Vector, Hashtable, Stack
public static void vector() {
Vector v = new Vector();
v.add("one"); v.add("two"); v.add("three");
for (Iterator it = v.iterator(); it.hasNext();) {
String s = (String) it.next();
if (s.equals("two"))
it.remove();
}
System.out.println(v);
v.removeAllElements();
}
public static void hashTable() {
Hashtable h = new Hashtable();
// Associate any two objects in a key-value pair
h.put(new Person("one", 11), "a"); // we put a string here
Object two = new Person("two", 12);
h.put(two, new Person("b", 13)); // we put an object here
h.put("three", "c");
h.put(new Integer(4), "d"); // for primitive data type use wrapper
for (Enumeration en = h.keys(); en.hasMoreElements(); ) {
Object key = en.nextElement();
Object value = h.get(key);
}
}
public static void stack() {
Stack s = new Stack();
s.push("a");
s.push("b");
String b = (String) s.pop();
s.clear();
}
// Collections added in Java 1.2 should be used instead of legacy
// collections Vector, Hashtable, Stack
public static void collection(Collection coll) {
System.out.println("in collection");
Person[] pa = getPersons();
coll.add(pa[0]);
coll.add(pa[1]);
coll.remove(pa[0]);
boolean b = coll.contains(pa[1]); // calls Person.equals()
int size = coll.size();
for (Iterator iter = coll.iterator(); iter.hasNext(); )
{
Person p = (Person) iter.next();
iter.remove();
}
//Person[] p2 = (Person[]) coll.toArray(); throws exception
coll.clear(); // remove all elements
}
// Set implements Collection no duplicates allowed
public static void set(Set set) {
System.out.println("in set");
Person[] pa = getPersons();
set.add(pa[0]);
set.add(pa[1]);
// will call Person.hashCode() to determine that this is a duplicate
set.add(pa[0]);
System.out.println("set size=" + set.size());
}
public static void linkedHashSet() {
LinkedHashSet lhs = new LinkedHashSet();
set(lhs);
lhs.iterator();
}
public static void main(String[] argv) {
arrays();
vector();
hashTable();
stack();
ArrayList al = new ArrayList();
collection(al);
// HashSet is a set backed by a Hash table
HashSet hs = new HashSet();
set(hs);
LinkedHashSet lhs = new LinkedHashSet();
set(lhs);
linkedHashSet();
}
}
/**
* Comparator is a Strategy Pattern
*/
class StringComparator implements Comparator {
public int compare(Object o1, Object o2) {
String s1 = (String)o1;
String s2 = (String)o2;
return s1.toLowerCase().compareTo(s2.toLowerCase());
}
} ///:~
// simple Person object to illustrate usage of collections
// and to show that if an object uses the Set or Map collection it
// should implement equals and hashCode
class Person implements Comparable, Comparator, Cloneable {
private String name;
private int age;
public Person(String name, int age) { this.name = name; this.age = age; }
/**
* we just use the String.equals, your object should implement equals
* on your rules
* The equals method implements an equivalence relation on non-null
* object references:
* It is reflexive: for any non-null reference value x,
* x.equals(x) should return true.
* It is symmetric: for any non-null reference values x and y,
* x.equals(y) should return true if and only if y.equals(x) returns true.
* It is transitive: for any non-null reference values x, y, and z,
* if x.equals(y) returns true and y.equals(z) returns true,
* then x.equals(z) should return true.
* It is consistent: for any non-null reference values x and y,
* multiple invocations of x.equals(y) consistently return true or
* consistently return false, provided no information used in equals
* comparisons on the objects is modified.
* For any non-null reference value x, x.equals(null) should return false
**/
public boolean equals(Object obj)
{
System.out.println("in Person.equals");
if (obj instanceof Person) // if obj is null instanceof returns false
{
Person person = (Person) obj;
return person.name.equals(name) && person.age == age;
}
else return false;
}
/**
* From interface Comparator
* Compares its two arguments for order. Returns a negative integer, zero, or
* a positive integer as the first argument is less than, equal to,
* or greater than the second.
* The implementor must ensure that
* sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.
* (This implies that compare(x, y) must throw an exception if and
* only if compare(y, x) throws an exception.)
* The implementor must also ensure that the relation is transitive:
* ((compare(x, y)>0) && (compare(y, z)>0))
* implies compare(x, z)>0. Finally, the implementer must ensure that
* compare(x, y)==0 implies
* that sgn(compare(x, z))==sgn(compare(y, z)) for all z.
* It is generally the case, but not strictly required
* that (compare(x, y)==0) == (x.equals(y)).
* Generally speaking, any comparator that violates this condition should
* clearly indicate this fact.
**/
public int compare(Object o1, Object o2) {
Person p1 = (Person) o1;
Person p2 = (Person) o2;
int ret = p1.getName().compareTo(p2.getName());
if (ret == 0 && p1.getAge() != p2.getAge())
ret = p1.getAge() < p2.getAge() ? -1 : 1;
return ret;
}
/**
* from interface Comparable
* Called by Arrays.sort()
* @param o
* @return
*/
public int compareTo(Object o)
{
Person p = (Person) o;
int ret = p.getName().compareTo(getName());
if (ret == 0 && p.getAge() != getAge())
ret = p.getAge() < getAge() ? -1 : 1;
return ret;
}
/**
* The general contract of hashCode is:
* Whenever it is invoked on the same object more than once during an execution
* of a Java application, the hashCode method must consistently return the same
* integer, provided no information used in equals comparisons on the object is
* modified. This integer need not remain consistent from one execution of an
* application to another execution of the same application.
* **********************
* If two objects are equal according to the equals(Object) method, then calling
* the hashCode method on each of the two objects must produce the same integer
* result.
* **********************
* It is not required that if two objects are unequal according to the
* equals(java.lang.Object) method, then calling the hashCode method on each of
* the two objects must produce distinct integer results. However, the programmer
* should be aware that producing distinct integer results for unequal objects
* may improve the performance of hashtables.
* x.equals(y) == true then x.hashCode() == y.hashCode()
* x.hashCode() == y.hashCode() then x.equals(y) can be true (not required
* x.hashCode() != y.hashCode() then x.equals(y) == false
* Use algorithm from Effective Java
* public int hashCode() { return 1776; } // valid but ineffecient hashCode
* do not use transient variables for serialized objects
*/
public int hashCode() {
System.out.println("in Person.hashCode");
int result = 17; // start with some random number
result = 37 * result + name.hashCode();
result = 37 * result + age;
// for boolean b == true ? 1 : 0;
return result;
}
/**
* Create copy of Person
* x.clone != x
* x.clone().equals(x)
* @return copy of this object
* @throws java.lang.CloneNotSupportedException
*/
public Object clone() throws CloneNotSupportedException
{
Person p = (Person) super.clone();
p.name = name;
p.age = age;
return p;
}
public String getName() { return name; }
public int getAge() { return age; }
public String toString() { return "name=" + name + ",age=" + age; }
}