As you remember from the Lesson 3.0 the root of the
Collections
framework in Java is the
Collections
interface. Collection might support different operations
Collections does not provide an implementation for each of the many type of collections. Instead it provides subinterfaces for subgroups of collections
kju
)
All general purpose implementation have constructors that take a
Collection
object.
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
for-each
construct
/*
for (Object o : collection)
System.out.println(o);
*/
Collection<Integer> collection = new TreeSet<Integer>();
//do work on the collection
for (Integer collection_element: collection) {
System.out.println(collection_element);
}
for (Iterator iterator = collection.iterator(); iterator.hasNext();) {
Integer integer = (Integer) iterator.next();
}
Iterators abstract the concept of iteration implementing the following (simple) interface
public interface Iterator<E> {
boolean hasNext(); // returns true if the iteration has more elements,
E next(); //returns the next element in the iteration
void remove(); //optional, removes the last element that was returned by next
}
IMPORTANT
when you need to iterate and modify the collection at the same time
Iterator
is the only way to do it without triggering any
undefined behavior
.
For instance, imagine if you need to remove elements greater than 5 from a Collection of Integers.
One way to do it is:
for (Iterator iterator = collection.iterator(); iterator.hasNext();) {
Integer integer = (Integer) iterator.next();
if(integer > 5)
iterator.remove();
}
Note that the previous example is nothing but a
filter
which can be abstracted Easily using
Collections
static void filter(Collection<?> c) {
for (Iterator<?> it = c.iterator(); it.hasNext(); )
if (!cond(it.next()))
it.remove();
}
cond
is a function with signature
bool(final T)
;
- Aggregate Operations
Since Java 8 all
Collections
provides support for
streams
.
A stream is simply a
sequence
of elements. Stream’s element are not stored anywhere (a stream is not a data structure). Think about them as flux of data on which you can perform a number of
pipelined
operations.
For instance here is how to write the filter we have seen before using streams.
al= al.stream()
.filter(element -> element>=5)
.collect(Collectors.toList());
}
This shows how to pipeline multiple operations.
al= al.stream()
.filter(element -> element>=5)
.map(element -> element*7)
.map(e -> e> 70 ? e%70 : e )
.collect(Collectors.toList());
Note that filter-map is a very common pattern! Whenever possible use streams because they end up in better code quality and ofter in increased performance because of the capability of parallel processing of streams.
Streams allow reduction to be performed very elegantly. Imagine you want to find the sum of a List. Using streams we will have something like:
Integer sumal = al.stream()
.reduce(0, (a,b)->a+b);
reduce is a very powerful patter. It Allows to reduce a Collection to a another type using a binary operation .
Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction. The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited. Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ. Two Set instances are equal if they contain the same elements.
Java provides three implementations of Sets.
- TreeSet (Red Black Tree - 2-balanced binary Search Tree)
- HashSet (Hash Table)
- LinkedHashSet. HashSet
Imagine for a second you want to filter duplicate elements from a Collection. Using
Set
and stream:
Set noduplicates= collection.stream().
collect(Collectors.toSet());
Besides basic Collection operations, queues provide additional insertion, removal, and inspection operations.
public interface Queue<E> extends Collection<E> {
E element();
boolean offer(E e);
E peek();
E poll();
E remove();
}
A common Queue variant is the
PriorityQueue
which removes elements in a sorted manner. Elements with higher priority first.
As an example, we will show how to
sort
a Collection of Integers.
List<Integer> al = new ArrayList<>();
for(int i=0;i<20;i++)
al.add(i);
al= al.stream()
.filter(element -> element>=5)
.map(element -> element*7)
.map(e -> e> 70 ? e%70 : e )
.collect(Collectors.toList());
System.out.println(al);
Queue<Integer> queue = new PriorityQueue(al);
al.clear();
while (!queue.isEmpty())
al.add(queue.remove());
System.out.println(al);
Note
that this sorting method has a name and is called
heap sort
.
When the priority queue is implemented using a
log(n)
access data structure
heap sort
has optimal complexity
nlog(n)
.
A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. It models the mathematical function abstraction. The Map interface includes methods for basic operations (such as put, get, remove, containsKey, containsValue, size, and empty), bulk operations (such as putAll and clear), and collection views (such as keySet, entrySet, and values).
Stream in Java brings
functional programming
into Java.
Functional programming is
different
from imperative programming.
unsigned int sum=0;
for(int i=0;i<100;i++){
sum+=i;
}
vs
sum[1..100]
For those interested in Functional Programming I suggest to read more about Haskell (which is one of the most popular FP languages out there). For a computer science it is mandatory to know more about this.
Read here:
http://learnyouahaskell.com/
Functional programming is heavily based on a pretty abstract and new branch of mathematics named
category theory
. One of the concept in this theory is the
Monad
.
A Monad represents a computation a series of steps and the semantic of chaining operations that operate on the monad itself together.
java streams
in full use.
Streams can be created from
Collections
easily using the
stream()
method exposed by the
Collection
interface.
The stream can be also created from regular objects using the
static
method from
Stream
.
Consider the following:
int a,b,c;
//init abc
Stream.of(a,b,c)
.average()
.ifPresent(System.out::println);
Stream
is a stream of
Object
(java class
Object
) but there are many specializations of
stream
for different types.
IntStream
for instance is a stream made for working with integers.
IntStream.range(1, 4)
.forEach(System.out::println);
Specialized streams works as normal stream but they also expose specialized methods (
IntStream
provides
sum()
for instance).
It means that any stream operations is really performed only when the result of the operation is required.
Consider the following:
Stream.of("d2", "a2", "b1", "b3", "c")
.filter(s -> {
System.out.prinln("filter: " + s);
return true;
});
When executed this code does not print anything at all on the console simply because the stream is never required to be printed on the console! This mean also that filtering operation does not really take place at all unless some of the values of the stream are used at later time in the program.
IntStream.range(1, 10)
.filter(s -> {
if(s>5){
System.out.println(s+ " is good");
return true;
}
else
System.out.println(s+ " isn't good");
return false;
})
.forEach(s -> System.out.println("forEach: " + s));
produces
1 isn't good
2 isn't good
3 isn't good
4 isn't good
5 isn't good
6 is good
forEach: 6
7 is good
forEach: 7
8 is good
forEach: 8
9 is good
forEach: 9
Elements are processed vertically. It means that a single element is completely processed before moving to the next one.
Why is that? Because this can actually reduce the number of performed operation in some case:
IntStream.range(1, 100)
.filter(s -> {
if(s>5){
System.out.println(s+ " is good");
return true;
}
else
System.out.println(s+ " isn't good");
return false;
})
.map(e -> {return e*e;})
.anyMatch(e -> {
System.out.println("match"+e);
return e>36;
});
1 isn't good
2 isn't good
3 isn't good
4 isn't good
5 isn't good
6 is good
match36
7 is good
match49
Elements from 1 to 99 are not processed at all!
Some operations can’t process element without processing the others! Think about sorting for instance. You can’t sort a stream without looking at all elements of the stream.
For that kind of operation, the order of execution is horizontal.
One you create a stream any attempt in reusing it will raise an exception!
IllegalStateException
.
Stream<String> stream =
Stream.of("d2", "a2", "b1", "b3", "c")
.filter(s -> s.startsWith("a"));
stream.anyMatch(s -> true); // ok
stream.noneMatch(s -> true); // exception. 2nd use!
In order to avoid setting up the same stream more than once you can use a
Supplier<Stream>
. It exposes a
get()
function which creates a brand new stream (and already setted up) for use.
Supplier<Stream<String>> streamSupplier =
() -> Stream.of("d2", "a2", "b1", "b3", "c")
.filter(s -> s.startsWith("a"));
streamSupplier.get().anyMatch(s -> true); // ok
streamSupplier.get().noneMatch(s -> true); // ok
public class IGPEList<E extends Object> implements List<E>{
public static int DEF_SIZE = 10;
Object[] array;
private int size=0;
IGPEList(){
}
IGPEList(final int capacity){
array = new Object[capacity];
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size==0;
}
@SuppressWarnings("unchecked")
@Override
public boolean contains(Object o) {
return
Arrays.stream(array)
.filter(el -> {
return ((E)o).equals(el);
})
.findAny()
.isPresent();
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private int idx=0;
Object fst = array[idx];
@Override
public boolean hasNext() {
return idx < size()-1;
}
@SuppressWarnings("unchecked")
@Override
public E next() {
fst = array[idx++];
return (E)fst;
}
};
}
@Override
public Object[] toArray() {
return Arrays.stream(array)
.toArray();
}
@SuppressWarnings("unchecked")
@Override
public <T> T[] toArray(T[] a) {
T[] array2 = (T[])toArray();
return array2;
}
@Override
public boolean add(E e) {
if(size > array.length)
resize(array.length*IGPEList.DEF_MULTIPLIER);
array[size++] = e;
}
@Override
public boolean remove(Object o) {
final int idx = indexOf(o);
if( idx != -1){
final int LIMIT = array.length/4;
if(LIMIT > DEF_SIZE && size < LIMIT){
resize(array.length/2);
}
}
}
private void resize(int i) {
// TODO Auto-generated method stub
}
@Override
public boolean containsAll(Collection<?> c) {
}
...