3/29 Collection Frameworks (Containers)

Administrative:

midterm - return next week
new homework posted on website
NOTE: you have to start working more diligently on the project


*******************************************
take home problems:
assume you can calculate 10 million different circuits per second thru a fully connected weighted graph. If N=100, how long will it take you to solve the TSP problem.



*****************************


framework design requirements

completeness - do what its supposed to do
adaptability- adapt to new problems or requirements
efficiency - memory, run-time, time spent programming
safety - run-time behavior
simplicity - easy to understand how it works and is used
extensibility - easily extend framework


FRAMEWORKS

1. Collection Framework (containers)
- support storing and retrieving objects

2. GUI Framework

3. Input/Output Framework


Collection Framework (Containers)

A collection is an object that contains another object.



Collection are classified based on their structures and capabilities
-bags (rarely used)
-sets (sometimes used)
-lists (used all the time)
-maps (used all the time)

Bags
-order of elements is unimportant
-repetitions are allowed
- least restrictive
-general form
- extend the collection interface

Example:

B1=[a,b,a]
B2 = [a,a,b]
B1 = B2


public class Box
{
private Object object;
public void add(Object object)
{
this.object = object;
}
public Object get() { return object; }
}

NOTE on generics
problem is you can only add Objects , what about string, cup, etc.


public class Box
{
private T t; //T stands for type
public void add(T t)
{
this.t= object;
}
public T get() { return t; }
}

Box integerBox;

to instantiate this class, use the new keyword but place between the class name and the parenthesis: integerBox = new Box();


Collection Interface

size
isEmpty
contains
add
remove
Iterator
...

Java Collection Documentation
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collection.html


Collection
-----------------------
| | |
Set List Queue
|
SortedSet


Map
|
SortedMap


Set
order of element is important
repetitions are NOT allowed


Set Interface

http://java.sun.com/j2se/1.4.2/docs/api/java/util/Set.html

List

- order is important
- repetitions are allowed

Example: L1 =<>, L2 = , L3 = ,b>

http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html


Map
-collection of key-value pairs
- don't allow duplicate pairs
-


http://java.sun.com/j2se/1.4.2/docs/api/java/util/Map.html


Implementation of sets


HashSet
-very efficient add() and contains() : O(1)
-iteration order is unpredictable

LinkedHashSet
-iteration order is predictable

TreeSet
-used red-black tree for implementation
-elements ordered in natural order or user-defined
-time complexity for add() and contains : O(logn)




Iterator Example