javolution.util

Class FastCollection<E>

java.lang.Object

javolution.util.FastCollection<E>

All Implemented Interfaces:

Serializable, Iterable<E>, Collection<E>

Direct Known Subclasses:

FastSet, FastTable

@Realtime
@DefaultTextFormat(value=FastCollection.Text.class)
public abstract class FastCollection<E>
extends Object
implements Collection<E>, Serializable

A closure-based collection supporting numerous views which can be chained.

• atomic() - Thread-safe view for which all reads are mutex-free and collection updates (including addAll, removeIf} are atomic.
• shared() - Thread-safe view using allowing concurrent reads based on mutex ( readers-writer locks).
• parallel() - A view allowing parallel processing including updates.
• sequential() - View disallowing parallel processing.
• unmodifiable() - View which does not allow any modification.
• filtered(filter) - View exposing only the elements matching the specified filter.
• mapped(function) - View exposing elements through the specified mapping function.
• comparator(comparator) - View using the specified comparator for element equality and order.
• sorted() - View exposing elements sorted according to the collection comparator.
• reversed() - View exposing elements in the reverse iterative order.
• distinct() - View exposing each element only once.

Unmodifiable collections are not always constant. Constant/immutable collections can be obtained from collection specializations.

 ConstantTable<String>> winners = ConstantTable.of("John Deuff", "Otto Graf", "Sim Kamil");
     // Immutability is guaranteed by construction (no reference left on the array source).
 

Atomic collections use Copy-On-Write optimizations in order to provide mutex-free read access. Only writes operations are mutually exclusive. Collections can be optimized to not require the full copy during write operations (e.g. immutable parts don't need to be copied). Still, when multiple updates are performed, it is beneficial to group them into one single update operation.

 FastTable<String> tokens = new FastTable<String>().atomic();
 ...
 // Replace null with "" in tokens. If tokens is atomic the update is atomic.
 // If tokens is parallel, the update is also performed concurrently !
 tokens.update(new Consumer<List<String>>() {  
     public void accept(List<String> view) {
         for (int i=0, n = view.size(); i < n; i++)
             if (view.get(i) == null) view.set(i, "");
         }
     }
 });

The same code using closure (Java 8).

  tokens.update((List<String> view) -> {
      for (int i = 0, n = view.size(); i < n; i++) {
          if (view.get(i) == null) view.set(i, "");
      }
  });

Views are similar to Java 8 streams except that views are themselves collections (virtual collections) and actions on a view can impact the original collection. Collection views are nothing "new" since they already existed in the original java.util collection classes (e.g. List.subList(...), Map.keySet(), Map.values()). Javolution extends to this concept and allows views to be chained which addresses the concern of class proliferation.

 FastTable<String> names = FastTable.of("Oscar Thon", "Eva Poret", "Paul Auchon");
 boolean found = names.comparator(Equalities.LEXICAL_CASE_INSENSITIVE).contains("LUC SURIEUX"); 
 names.subTable(0, n).clear(); // Removes the n first names (see java.util.List.subList).
 names.distinct().add("Guy Liguili"); // Adds "Guy Liguili" only if not already present.
 names.filtered(isLong).clear(); // Removes all the persons with long names.
 names.filtered(isLong).parallel().clear(); // Same as above but performed concurrently !
 ...
 Predicate<CharSequence> isLong = new Predicate<CharSequence>() { 
     public boolean test(CharSequence csq) {
         return csq.length() > 16; 
     }
 });

Views can of course be used to perform "stream" oriented filter-map-reduce operations with the same benefits: Parallelism support, excellent memory characteristics (no caching and cost nothing to create), etc.

 String anyLongName = names.filtered(isLong).any(String.class); // Returns any long name.
 int nbrChars = names.mapped(toLength).reduce(Reducers.sum()); // Returns the total number of characters.
 int maxLength = names.mapped(toLength).parallel().max(); // Finds the longest name in parallel.
 ...
 Function<CharSequence, Integer> toLength = new Function<CharSequence, Integer>() {
    public Integer apply(CharSequence csq) {
        return csq.length(); 
    }
 });
    
 // JDK Class.getEnclosingMethod using Javolution's views and Java 8 (to be compared with the current 20 lines implementation !).
 Method matching = new FastTable<Method>().addAll(enclosingInfo.getEnclosingClass().getDeclaredMethods())
     .filtered(m -> Equalities.STANDARD.areEqual(m.getName(), enclosingInfo.getName())
     .filtered(m -> Equalities.ARRAY.areEqual(m.getParameterTypes(), parameterClasses))
     .filtered(m -> Equalities.STANDARD.areEqual(m.getReturnType(), returnType))
     .any(Method.class);
 if (matching == null) throw new InternalError("Enclosing method not found");
 return matching;

If a collection (or a map) is shared, derived views are also thread-safe. Similarly, if a collection is parallel, closure-based iterations on derived views are performed concurrently.

 FastTable<Person> persons = new FastTable<Person>().parallel();
 ...
 // Since persons is parallel, the search is done concurrently.
 Person john = persons.filtered(new Predicate<Person>() { 
     public boolean test(Person person) {
         return person.getName().equals("John");
     }
 }).any(Person.class);

With Java 8, closures are greatly simplified using lambda expressions.

 Person john = persons.filtered(person -> person.getName().equals("John")).any(Person.class); // Same as above.
 tasks.parallel().forEach(task -> task.run());
 names.sorted().reversed().forEach(str -> System.out.println(str)); // Prints names in reverse alphabetical order. 
 

Version:

6.0, July 21, 2013

Author:

Jean-Marie Dautelle

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	FastCollection.Text Default text format for fast collections (parsing not supported).

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	FastCollection() Default constructor.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(E element) Adds the specified element to this collection
boolean	addAll(Collection<? extends E> that) Adds all the specified elements to this collection.
<T extends E> T	any(Class<T> type) Returns any non-null element of the specified type (convenience method).
FastCollection<E>	atomic() Returns an atomic view over this collection.
void	clear() Removes all elements from this collection.
Equality<? super E>	comparator() Returns the comparator used by this collection for element equality and/or ordering if this collection is sorted.
FastCollection<E>	comparator(Comparator<? super E> cmp) Returns a view using the specified comparator for element equality and sorting.
boolean	contains(Object searched) Indicates if this collection contains the specified element.
boolean	containsAll(Collection<?> that) Indicates if this collection contains all the specified elements.
FastCollection<E>	distinct() Returns a view exposing only distinct elements (it does not iterate twice over the same elements).
boolean	equals(Object obj) Compares the specified object with this collection for equality.
FastCollection<E>	filtered(Predicate<? super E> filter) Returns a view exposing only the elements matching the specified filter.
void	forEach(Consumer<? super E> consumer) Iterates over all this collection elements applying the specified consumer (convenience method).
int	hashCode() Returns the hash code of this collection.
boolean	isEmpty() Indicates if this collection is empty.
Iterator<E>	iterator() Returns an iterator over this collection elements.
<R> FastCollection<R>	mapped(Function<? super E,? extends R> function) Returns a view exposing elements through the specified mapping function.
E	max() Returns the largest element of this collection using this collection comparator (convenience method).
E	min() Returns the smallest element of this collection using this collection comparator (convenience method).
FastCollection<E>	parallel() Returns a parallel collection.
void	perform(Consumer<? extends Collection<E>> action) Executes the specified read action on this collection.
E	reduce(Reducer<E> reducer) Performs a reduction of the elements of this collection using the specified reducer.
boolean	remove(Object searched) Removes the specified element from this collection.
boolean	removeAll(Collection<?> that) Removes all the specified element from this collection.
boolean	removeIf(Predicate<? super E> filter) Removes from this collection all the elements matching the specified functional predicate (convenience method).
boolean	retainAll(Collection<?> that) Removes all the elements except those in the specified collection.
FastCollection<E>	reversed() Returns a view exposing elements in reverse iterative order.
FastCollection<E>	sequential() Returns a sequential view of this collection.
protected abstract CollectionService<E>	service() Returns the service implementation of this collection (for sub-classes).
protected static <E> CollectionService<E>	serviceOf(FastCollection<E> collection) Returns the service implementation of any fast collection (for sub-classes).
FastCollection<E>	shared() Returns a thread-safe view over this collection.
int	size() Returns the size of this collection.
FastCollection<E>	sorted() Returns a view exposing elements sorted according to this collection comparator().
FastCollection<E>	sorted(Comparator<? super E> cmp) Returns a view exposing elements sorted according to the specified comparator (convenience method).
Object[]	toArray() Returns an array holding this collection elements.
<T> T[]	toArray(T[] array) Returns the specified array holding this collection elements if enough capacity.
String	toString() Returns the string representation of this collection using its default format.
FastCollection<E>	unmodifiable() Returns an unmodifiable view over this collection.
void	update(Consumer<? extends Collection<E>> action) Executes the specified update action on this collection.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

FastCollection

protected FastCollection()

Default constructor.

Method Detail

atomic

@Parallelizable(mutexFree=true,
                comment="Except for write operations, all read operations are mutex-free.")
public FastCollection<E> atomic()

Returns an atomic view over this collection. All operations that write or access multiple elements in the collection (such as addAll(), retainAll()) are atomic. Iterators on atomic collections are thread-safe (no ConcurrentModificationException possible).

shared

@Parallelizable(mutexFree=false,
                comment="Use multiple-readers/single-writer lock.")
public FastCollection<E> shared()

Returns a thread-safe view over this collection. The shared view allows for concurrent read as long as there is no writer. The default implementation is based on readers-writers locks giving priority to writers. Iterators on shared collections are thread-safe (no ConcurrentModificationException possible).

parallel

public FastCollection<E> parallel()

Returns a parallel collection. Closure-based operations are performed in parallel on sub-views of this collection. The number of parallel views is equals to concurrency+ 1.

See Also:

perform(Consumer), update(Consumer), forEach(Consumer), removeIf(Predicate), reduce(Reducer)

sequential

public FastCollection<E> sequential()

Returns a sequential view of this collection. Using this view, all closure-based iterations are performed sequentially.

unmodifiable

public FastCollection<E> unmodifiable()

Returns an unmodifiable view over this collection. Any attempt to modify the collection through this view will result into a UnsupportedOperationException being raised.

filtered

public FastCollection<E> filtered(Predicate<? super E> filter)

Returns a view exposing only the elements matching the specified filter. Adding elements not matching the specified filter has no effect. If this collection is initially empty, using a filtered view to add new elements ensure that this collection has only elements satisfying the filter predicate.

mapped

public <R> FastCollection<R> mapped(Function<? super E,? extends R> function)

Returns a view exposing elements through the specified mapping function. The returned view does not allow new elements to be added.

comparator

public FastCollection<E> comparator(Comparator<? super E> cmp)

Returns a view using the specified comparator for element equality and sorting.

See Also:

contains(Object), remove(Object), sorted(), distinct()

sorted

public FastCollection<E> sorted()

Returns a view exposing elements sorted according to this collection comparator().

See Also:

comparator(), comparator(Comparator)

sorted

public FastCollection<E> sorted(Comparator<? super E> cmp)

Returns a view exposing elements sorted according to the specified comparator (convenience method).

Returns:

comparator(cmp).sorted()

reversed

public FastCollection<E> reversed()

Returns a view exposing elements in reverse iterative order.

distinct

public FastCollection<E> distinct()

Returns a view exposing only distinct elements (it does not iterate twice over the same elements). Adding elements already in the collection through this view has no effect. If this collection is initially empty, using a distinct view to add new elements ensures that this collection has no duplicate.

perform

@Realtime(limit=LINEAR)
public void perform(Consumer<? extends Collection<E>> action)

Executes the specified read action on this collection. That logic may be performed concurrently (on parallel views) if this collection is parallel.

Parameters:

action - the read-only action.

Throws:

ClassCastException - if the action type is not compatible with this collection (e.g. action on set and this is a list).

See Also:

update(Consumer)

update

@Realtime(limit=LINEAR)
public void update(Consumer<? extends Collection<E>> action)

Executes the specified update action on this collection. For atomic collections the update is atomic (either concurrent readers see the full result of the action or nothing). The update may be performed concurrently (through parallel views) if this collection is parallel.

Parameters:

action - the update action.

Throws:

ClassCastException - if the action type is not compatible with this collection (e.g. action on a Set and this is a List).

See Also:

perform(Consumer)

forEach

@Realtime(limit=LINEAR)
public void forEach(Consumer<? super E> consumer)

Iterates over all this collection elements applying the specified consumer (convenience method). Iterations are performed concurrently if the collection is parallel.

Parameters:

consumer - the functional consumer applied to the collection elements.

removeIf

@Realtime(limit=LINEAR)
public boolean removeIf(Predicate<? super E> filter)

Removes from this collection all the elements matching the specified functional predicate (convenience method). Removals are performed concurrently if this collection is parallel and atomically if this collection is atomic.

Parameters:

filter - a predicate returning true for elements to be removed.

Returns:

true if at least one element has been removed; false otherwise.

reduce

@Realtime(limit=LINEAR)
public E reduce(Reducer<E> reducer)

Performs a reduction of the elements of this collection using the specified reducer. This may not involve iterating over all the collection elements, for example the reducers: Reducers.any(java.lang.Class<? extends E>), Reducers.and() and Reducers.or() may stop iterating early. Reduction is performed concurrently if this collection is parallel.

Parameters:

reducer - the collection reducer.

Returns:

the reduction result.

See Also:

any(Class), min(), max()

add

@Realtime(limit=LINEAR,
          comment="Could iterate the whole collection (e.g. distinct view).")
public boolean add(E element)

Adds the specified element to this collection

Specified by:

add in interface Collection<E>

isEmpty

@Realtime(limit=LINEAR,
          comment="Could iterate the whole collection (e.g. filtered view).")
public boolean isEmpty()

Indicates if this collection is empty.

Specified by:

isEmpty in interface Collection<E>

size

@Realtime(limit=LINEAR,
          comment="Could count the elements (e.g. filtered view).")
public int size()

Returns the size of this collection.

Specified by:

size in interface Collection<E>

clear

@Realtime(limit=LINEAR,
          comment="Could remove the elements one at a time.")
public void clear()

Removes all elements from this collection.

Specified by:

clear in interface Collection<E>

contains

@Realtime(limit=LINEAR,
          comment="Could search the whole collection.")
public boolean contains(Object searched)

Indicates if this collection contains the specified element.

Specified by:

contains in interface Collection<E>

remove

@Realtime(limit=LINEAR,
          comment="Could search the whole collection.")
public boolean remove(Object searched)

Removes the specified element from this collection.

Specified by:

remove in interface Collection<E>

iterator

@Realtime(limit=N_SQUARE,
          comment="Sorted view iterator require sorting the elements.")
public Iterator<E> iterator()

Returns an iterator over this collection elements. For shared/atomic collections the iterator is immune to concurrent modifications. In other words the elements iterated over may or may not reflect the current state of the collection.

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

addAll

@Realtime(limit=LINEAR)
public boolean addAll(Collection<? extends E> that)

Adds all the specified elements to this collection.

Specified by:

addAll in interface Collection<E>

containsAll

@Realtime(limit=N_SQUARE)
public boolean containsAll(Collection<?> that)

Indicates if this collection contains all the specified elements.

Specified by:

containsAll in interface Collection<E>

removeAll

@Realtime(limit=N_SQUARE)
public boolean removeAll(Collection<?> that)

Removes all the specified element from this collection.

Specified by:

removeAll in interface Collection<E>

retainAll

@Realtime(limit=N_SQUARE)
public boolean retainAll(Collection<?> that)

Removes all the elements except those in the specified collection.

Specified by:

retainAll in interface Collection<E>

toArray

@Realtime(limit=LINEAR)
public Object[] toArray()

Returns an array holding this collection elements.

Specified by:

toArray in interface Collection<E>

toArray

@Realtime(limit=LINEAR)
public <T> T[] toArray(T[] array)

Returns the specified array holding this collection elements if enough capacity.

Specified by:

toArray in interface Collection<E>

any

@Realtime(limit=LINEAR)
public <T extends E> T any(Class<T> type)

Returns any non-null element of the specified type (convenience method). The search is performed concurrently if this collection is parallel.

Parameters:

type - the element type searched for.

Returns:

reduce(Reducers.any(type))

See Also:

Reducers.any(java.lang.Class<? extends E>)

min

@Realtime(limit=LINEAR)
public E min()

Returns the smallest element of this collection using this collection comparator (convenience method). Returns null if this collection is empty. The search is performed concurrently if this collection is parallel.

Returns:

reduce(Reducers.min(comparator()))

See Also:

Reducers.min(java.util.Comparator<? super E>)

max

@Realtime(limit=LINEAR)
public E max()

Returns the largest element of this collection using this collection comparator (convenience method). Returns null if this collection is empty. The search is performed concurrently if this collection is parallel.

Returns:

reduce(Reducers.max(comparator()))

See Also:

Reducers.max(java.util.Comparator<? super E>)

comparator

@Realtime(limit=CONSTANT)
public Equality<? super E> comparator()

Returns the comparator used by this collection for element equality and/or ordering if this collection is sorted. The comparator is used by methods such as contains(Object) or remove(Object) but it is ignored when comparing collections for equality.

equals

@Realtime(limit=LINEAR)
public boolean equals(Object obj)

Compares the specified object with this collection for equality. This method follows the Collection.equals(Object) specification regardless of the collection's comparator. For example, two sorted sets using distinct comparators are considered equals as long as they both hold the same elements.

Specified by:

equals in interface Collection<E>

Overrides:

equals in class Object

Parameters:

obj - the object to be compared for equality with this collection

Returns:

true if this collection is considered equals to the one specified; false otherwise.

hashCode

@Realtime(limit=LINEAR)
public int hashCode()

Returns the hash code of this collection. This method always follows the Collection.hashCode() specification regardless of the collection's comparator.

Specified by:

hashCode in interface Collection<E>

Overrides:

hashCode in class Object

Returns:

this collection hash code.

toString

@Realtime(limit=LINEAR)
public String toString()

Returns the string representation of this collection using its default format.

Overrides:

toString in class Object

See Also:

TextContext

service

protected abstract CollectionService<E> service()

Returns the service implementation of this collection (for sub-classes).

serviceOf

protected static <E> CollectionService<E> serviceOf(FastCollection<E> collection)

Returns the service implementation of any fast collection (for sub-classes).