You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@marmotta.apache.org by ss...@apache.org on 2013/09/06 14:27:02 UTC
[10/18] temporarily added a patched version of javolution with fast
collections, because the released version has several bugs (see
https://java.net/jira/browse/JAVOLUTION-106 and
https://java.net/jira/browse/JAVOLUTION-105)
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/FastCollection.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/FastCollection.java b/commons/marmotta-commons/src/ext/java/javolution/util/FastCollection.java
new file mode 100644
index 0000000..8160097
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/FastCollection.java
@@ -0,0 +1,715 @@
+/*
+ * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
+ * Copyright (C) 2012 - Javolution (http://javolution.org/)
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software is
+ * freely granted, provided that this notice is preserved.
+ */
+package javolution.util;
+
+import static javolution.lang.Realtime.Limit.CONSTANT;
+import static javolution.lang.Realtime.Limit.LINEAR;
+import static javolution.lang.Realtime.Limit.N_SQUARE;
+
+import java.io.IOException;
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+
+import javolution.lang.Immutable;
+import javolution.lang.Parallelizable;
+import javolution.lang.Realtime;
+import javolution.text.Cursor;
+import javolution.text.DefaultTextFormat;
+import javolution.text.TextContext;
+import javolution.text.TextFormat;
+import javolution.util.function.Consumer;
+import javolution.util.function.Equalities;
+import javolution.util.function.Equality;
+import javolution.util.function.Function;
+import javolution.util.function.Predicate;
+import javolution.util.function.Reducer;
+import javolution.util.function.Reducers;
+import javolution.util.internal.collection.AtomicCollectionImpl;
+import javolution.util.internal.collection.DistinctCollectionImpl;
+import javolution.util.internal.collection.FilteredCollectionImpl;
+import javolution.util.internal.collection.MappedCollectionImpl;
+import javolution.util.internal.collection.ParallelCollectionImpl;
+import javolution.util.internal.collection.ReversedCollectionImpl;
+import javolution.util.internal.collection.SequentialCollectionImpl;
+import javolution.util.internal.collection.SharedCollectionImpl;
+import javolution.util.internal.collection.SortedCollectionImpl;
+import javolution.util.internal.collection.UnmodifiableCollectionImpl;
+import javolution.util.service.CollectionService;
+
+/**
+ * <p> A closure-based collection supporting numerous views which can be chained.
+ * <ul>
+ * <li>{@link #atomic} - Thread-safe view for which all reads are mutex-free
+ * and collection updates (including {@link #addAll addAll}, {@link #removeIf removeIf}} are atomic.</li>
+ * <li>{@link #shared} - Thread-safe view using allowing concurrent reads based
+ * on mutex (<a href="http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock">
+ * readers-writer locks).</li>
+ * <li>{@link #parallel} - A view allowing parallel processing including {@link #update updates}.</li>
+ * <li>{@link #sequential} - View disallowing parallel processing.</li>
+ * <li>{@link #unmodifiable} - View which does not allow any modification.</li>
+ * <li>{@link #filtered filtered(filter)} - View exposing only the elements matching the specified filter.</li>
+ * <li>{@link #mapped mapped(function)} - View exposing elements through the specified mapping function.</li>
+ * <li>{@link #sorted sorted(comparator)} - View exposing elements sorted according to their natural order
+ * of using a specified comparator.</li>
+ * <li>{@link #reversed} - View exposing elements in the reverse iterative order.</li>
+ * <li>{@link #distinct} - View exposing each element only once.</li>
+ * </ul></p>
+ *
+ * <p> Unmodifiable collections are not always immutable. An {@link javolution.lang.Immutable immutable}.
+ * reference (or const reference) can only be {@link #toImmutable() obtained} when the originator
+ * guarantees that the collection source will not be modified even by himself
+ * (the value of the immutable reference being an {@link #unmodifiable unmodifiable} collection).
+ * [code]
+ * Immutable<List<String>> winners
+ * = new FastTable<String>().addAll("John Deuff", "Otto Graf", "Sim Kamil").toImmutable();
+ * // Immutability is guaranteed, no reference left on the collection source.
+ * [/code]</p>
+ *
+ * <p> Atomic collections use <a href="http://en.wikipedia.org/wiki/Copy-on-write">Copy-On-Write</a>
+ * 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 {@link #update update} operation.
+ * [code]
+ * 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, "");
+ * }
+ * }
+ * });[/code]</p>
+ * <p> The same code using closure (Java 8).
+ * [code]
+ * tokens.update((List<String> view) -> {
+ * for (int i = 0, n = view.size(); i < n; i++) {
+ * if (view.get(i) == null) view.set(i, "");
+ * }
+ * });[/code]</p>
+ *
+ * <p> Views are similar to <a href="http://lambdadoc.net/api/java/util/stream/package-summary.html">
+ * Java 8 streams</a> 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.</p>
+ * [code]
+ * FastTable<String> names = new FastTable<String>().addAll("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;
+ * }
+ * });[/code]</p>
+ *
+ * <p> 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.
+ * [code]
+ * 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;[/code]</p>
+ *
+ * <p> If a collection (or a map) is shared, derived views are also thread-safe.
+ * Similarly, if a collection is {@link #parallel parallel}, closure-based iterations
+ * on derived views are performed concurrently.
+ * [code]
+ * 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);[/code]</p>
+ *
+ * <p> With Java 8, closures are greatly simplified using lambda expressions.
+ * [code]
+ * 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.
+ * [/code]</p>
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+@Realtime
+@DefaultTextFormat(FastCollection.Format.class)
+public abstract class FastCollection<E> implements Collection<E>, Serializable {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * Default constructor.
+ */
+ protected FastCollection() {}
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Views.
+ //
+
+ /**
+ * 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 <b>thread-safe</b>
+ * (no {@link ConcurrentModificationException} possible).
+ */
+ @Parallelizable(mutexFree = true, comment = "Except for write operations, all read operations are mutex-free.")
+ public FastCollection<E> atomic() {
+ return new AtomicCollectionImpl<E>(service());
+ }
+
+ /**
+ * 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 <a href=
+ * "http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock">
+ * readers-writers locks</a> giving priority to writers.
+ * Iterators on shared collections are <b>thread-safe</b>
+ * (no {@link ConcurrentModificationException} possible).
+ */
+ @Parallelizable(mutexFree = false, comment = "Use multiple-readers/single-writer lock.")
+ public FastCollection<E> shared() {
+ return new SharedCollectionImpl<E>(service());
+ }
+
+ /**
+ * Returns a parallel collection. Closure-based operations are
+ * performed {@link javolution.context.ConcurrentContext in parallel}
+ * on {@link CollectionService#split sub-views} of this collection.
+ * The number of parallel views is equals to
+ * {@link javolution.context.ConcurrentContext#getConcurrency()
+ * concurrency}{@code + 1}.
+ *
+ * @see #perform(Consumer)
+ * @see #update(Consumer)
+ * @see #forEach(Consumer)
+ * @see #removeIf(Predicate)
+ * @see #reduce(Reducer)
+ */
+ public FastCollection<E> parallel() {
+ return new ParallelCollectionImpl<E>(service());
+ }
+
+ /**
+ * Returns a sequential view of this collection. Using this view,
+ * all closure-based iterations are performed sequentially.
+ */
+ public FastCollection<E> sequential() {
+ return new SequentialCollectionImpl<E>(service());
+ }
+
+ /**
+ * Returns an unmodifiable view over this collection. Any attempt to
+ * modify the collection through this view will result into
+ * a {@link java.lang.UnsupportedOperationException} being raised.
+ */
+ public FastCollection<E> unmodifiable() {
+ return new UnmodifiableCollectionImpl<E>(service());
+ }
+
+ /**
+ * 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.
+ */
+ public FastCollection<E> filtered(Predicate<? super E> filter) {
+ return new FilteredCollectionImpl<E>(service(), filter);
+ }
+
+ /**
+ * Returns a view exposing elements through the specified mapping function.
+ * The returned view does not allow new elements to be added.
+ */
+ public <R> FastCollection<R> mapped(
+ Function<? super E, ? extends R> function) {
+ return new MappedCollectionImpl<E, R>(service(), function);
+ }
+
+ /**
+ * Returns a view exposing elements sorted according to the
+ * collection {@link #comparator() order}.
+ */
+ public FastCollection<E> sorted() {
+ return new SortedCollectionImpl<E>(service(), comparator());
+ }
+
+ /**
+ * Returns a view exposing elements sorted according to the specified
+ * comparator.
+ */
+ public FastCollection<E> sorted(Comparator<? super E> cmp) {
+ return new SortedCollectionImpl<E>(service(), cmp);
+ }
+
+ /**
+ * Returns a view exposing elements in reverse iterative order.
+ */
+ public FastCollection<E> reversed() {
+ return new ReversedCollectionImpl<E>(service());
+ }
+
+ /**
+ * Returns a view exposing only distinct elements (it does not iterate twice
+ * over the {@link #comparator() 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.
+ */
+ public FastCollection<E> distinct() {
+ return new DistinctCollectionImpl<E>(service());
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Closure operations.
+ //
+
+ /**
+ * Executes the specified read action on this collection.
+ * That logic may be performed concurrently (on parallel views)
+ * if this collection is {@link #parallel() parallel}.
+ *
+ *
+ * @param 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 #update(Consumer)
+ */
+ @SuppressWarnings("unchecked")
+ @Realtime(limit = LINEAR)
+ public void perform(Consumer<? extends Collection<E>> action) {
+ service().perform((Consumer<CollectionService<E>>) action, service());
+ }
+
+ /**
+ * Executes the specified update action on this collection.
+ * For {@link #atomic() 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 {@link #parallel() parallel}.
+ *
+ * @param action the update action.
+ * @throws ClassCastException if the action type is not compatible with
+ * this collection (e.g. action on a {@link java.util.Set Set}
+ * and this is a {@link java.util.List List}).
+ * @see #perform(Consumer)
+ */
+ @SuppressWarnings("unchecked")
+ @Realtime(limit = LINEAR)
+ public void update(Consumer<? extends Collection<E>> action) {
+ service().update((Consumer<CollectionService<E>>) action, service());
+ }
+
+ /**
+ * Iterates over all this collection elements applying the specified
+ * consumer (convenience method). Iterations are performed concurrently
+ * if the collection is {@link #parallel() parallel}.
+ *
+ * @param consumer the functional consumer applied to the collection elements.
+ */
+ @Realtime(limit = LINEAR)
+ public void forEach(final Consumer<? super E> consumer) {
+ perform(new Consumer<Collection<E>>() {
+ public void accept(Collection<E> view) {
+ Iterator<E> it = view.iterator();
+ while (it.hasNext()) {
+ consumer.accept(it.next());
+ }
+ }
+ });
+ }
+
+ /**
+ * Removes from this collection all the elements matching the specified
+ * functional predicate (convenience method). Removals are performed
+ * concurrently if this collection is {@link #parallel() parallel} and
+ * atomically if this collection is {@link #atomic() atomic}.
+ *
+ * @param filter a predicate returning {@code true} for elements to be removed.
+ * @return {@code true} if at least one element has been removed;
+ * {@code false} otherwise.
+ */
+ @Realtime(limit = LINEAR)
+ public boolean removeIf(final Predicate<? super E> filter) {
+ final boolean[] removed = new boolean[1];
+ update(new Consumer<Collection<E>>() {
+ public void accept(Collection<E> view) {
+ Iterator<E> it = view.iterator();
+ while (it.hasNext()) {
+ if (filter.test(it.next())) {
+ it.remove(); // Ok mutable iteration.
+ removed[0] = true;
+ }
+ }
+ }
+ });
+ return removed[0];
+ }
+
+ /**
+ * 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: {@link Reducers#any},
+ * {@link Reducers#and} and {@link Reducers#or} may stop iterating
+ * early. Reduction is performed concurrently if this collection is
+ * {@link #parallel() parallel}.
+ *
+ * @param reducer the collection reducer.
+ * @return the reduction result.
+ * @see #any(Class)
+ * @see #min()
+ * @see #max()
+ */
+ @Realtime(limit = LINEAR)
+ public E reduce(Reducer<E> reducer) {
+ perform(reducer);
+ return reducer.get();
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Collection operations.
+ //
+
+ /** Adds the specified element to this collection */
+ @Override
+ @Realtime(limit = LINEAR, comment = "Could iterate the whole collection (e.g. distinct view).")
+ public boolean add(E element) {
+ return service().add(element);
+ }
+
+ /** Indicates if this collection is empty. */
+ @Override
+ @Realtime(limit = LINEAR, comment = "Could iterate the whole collection (e.g. filtered view).")
+ public boolean isEmpty() {
+ return iterator().hasNext();
+ }
+
+ /** Returns the size of this collection. */
+ @Override
+ @Realtime(limit = LINEAR, comment = "Could count the elements (e.g. filtered view).")
+ public int size() {
+ return service().size();
+ }
+
+ /** Removes all elements from this collection. */
+ @Override
+ @Realtime(limit = LINEAR, comment = "Could remove the elements one at a time.")
+ public void clear() {
+ service().clear();
+ }
+
+ /** Indicates if this collection contains the specified element. */
+ @Override
+ @Realtime(limit = LINEAR, comment = "Could search the whole collection.")
+ public boolean contains(Object searched) {
+ return service().contains(searched);
+ }
+
+ /** Removes the specified element from this collection.*/
+ @Override
+ @Realtime(limit = LINEAR, comment = "Could search the whole collection.")
+ public boolean remove(Object searched) {
+ return service().remove(searched);
+ }
+
+ /**
+ * 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.
+ */
+ @Override
+ @Realtime(limit = N_SQUARE, comment = "Sorted view iterator require sorting the elements.")
+ public Iterator<E> iterator() {
+ return service().iterator();
+ }
+
+ /** Adds all the specified elements to this collection. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public boolean addAll(final Collection<? extends E> that) {
+ return service().addAll(that);
+ }
+
+ /** Indicates if this collection contains all the specified elements. */
+ @Override
+ @Realtime(limit = N_SQUARE)
+ public boolean containsAll(Collection<?> that) {
+ return service().containsAll(that);
+ }
+
+ /** Removes all the specified element from this collection. */
+ @Override
+ @Realtime(limit = N_SQUARE)
+ public boolean removeAll(final Collection<?> that) {
+ return service().removeAll(that);
+ }
+
+ /** Removes all the elements except those in the specified collection. */
+ @Override
+ @Realtime(limit = N_SQUARE)
+ public boolean retainAll(final Collection<?> that) {
+ return service().retainAll(that);
+ }
+
+ /** Returns an array holding this collection elements. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public Object[] toArray() {
+ return service().toArray();
+ }
+
+ /**
+ * Returns the specified array holding this collection elements if
+ * enough capacity.
+ */
+ @Override
+ @Realtime(limit = LINEAR)
+ public <T> T[] toArray(final T[] array) {
+ return service().toArray(array);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Misc.
+ //
+
+ /**
+ * Returns any non-null element of the specified type (convenience method).
+ * The search is performed concurrently if this collection is
+ * {@link #parallel() parallel}.
+ *
+ * @param type the element type searched for.
+ * @return {@code reduce(Reducers.any(type))}
+ * @see Reducers#any
+ */
+ @SuppressWarnings("unchecked")
+ @Realtime(limit = LINEAR)
+ public <T extends E> T any(Class<T> type) {
+ return (T) reduce((Reducer<E>) Reducers.any(type));
+ }
+
+ /**
+ * Returns the smallest element of this collection using this
+ * collection {@link #comparator() comparator} (convenience method).
+ * Returns {@code null} if this collection is empty.
+ * The search is performed concurrently if this collection is
+ * {@link #parallel() parallel}.
+ *
+ * @return {@code reduce(Reducers.min(comparator()))}
+ * @see Reducers#min
+ */
+ @Realtime(limit = LINEAR)
+ public E min() {
+ return reduce((Reducer<E>)Reducers.min(comparator())); // Cast only necessary on JDK 1.6 !
+ }
+
+ /**
+ * Returns the largest element of this collection using this
+ * collection {@link #comparator() comparator} (convenience method).
+ * Returns {@code null} if this collection is empty.
+ * The search is performed concurrently if this collection is
+ * {@link #parallel() parallel}.
+ *
+ * @return {@code reduce(Reducers.max(comparator()))}
+ * @see Reducers#max
+ */
+ @Realtime(limit = LINEAR)
+ public E max() {
+ return reduce((Reducer<E>)Reducers.max(comparator())); // Cast only necessary on JDK 1.6 !
+ }
+
+ /**
+ * Returns this collection with the specified element added.
+ *
+ * @param elements the elements to be added.
+ * @return {@code this}
+ */
+ @Realtime(limit = LINEAR)
+ public FastCollection<E> addAll(E... elements) {
+ for (E e : elements) {
+ add(e);
+ }
+ return this;
+ }
+
+ /**
+ * Returns this collection with the specified collection's elements added
+ * in sequence.
+ */
+ @Realtime(limit = LINEAR)
+ public FastCollection<E> addAll(FastCollection<? extends E> that) {
+ addAll((Collection<? extends E>) that);
+ return this;
+ }
+
+ /**
+ * Returns the comparator uses by this collection for equality and/or
+ * ordering if this collection is sorted.
+ */
+ @Realtime(limit = CONSTANT)
+ public Equality<? super E> comparator() {
+ return service().comparator();
+ }
+
+ /**
+ * Returns an immutable reference over this collection. The immutable
+ * value is an {@link #unmodifiable() unmodifiable} view of this collection.
+ * The caller must guarantees that the original collection is never going
+ * to be updated (e.g. there is no reference left on the original collection).
+ */
+ @Realtime(limit = CONSTANT)
+ public <T extends Collection<E>> Immutable<T> toImmutable() {
+ return new Immutable<T>() {
+ @SuppressWarnings("unchecked")
+ final T value = (T) unmodifiable();
+
+ @Override
+ public T value() {
+ return value;
+ }
+ };
+ }
+
+ /**
+ * Compares the specified object with this collection for equality.
+ * This method follows the {@link Collection#equals(Object)} specification
+ * if this collection {@link #comparator comparator} is
+ * {@link Equalities#STANDARD} (default). Otherwise, only collections
+ * using the same comparator can be considered equals.
+ *
+ * @param obj the object to be compared for equality with this collection
+ * @return <code>true</code> if both collections are considered equals;
+ * <code>false</code> otherwise.
+ */
+ @Override
+ @Realtime(limit = LINEAR)
+ public boolean equals(Object obj) {
+ if(obj instanceof FastCollection) {
+ return service().equals(((FastCollection) obj).service());
+ } else {
+ return false;
+ }
+ }
+
+ /**
+ * Returns the hash code of this collection.
+ * This method follows the {@link Collection#hashCode()} specification
+ * if this collection {@link #comparator comparator} is
+ * {@link Equalities#STANDARD}.
+ *
+ * @return this collection hash code.
+ */
+ @Override
+ @Realtime(limit = LINEAR)
+ public int hashCode() {
+ return service().hashCode();
+ }
+
+ /**
+ * Returns the string representation of this collection using its
+ * default {@link TextFormat format}.
+ *
+ * @see TextContext
+ */
+ @Override
+ @Realtime(limit = LINEAR)
+ public String toString() {
+ return TextContext.getFormat(FastCollection.class).format(this);
+ }
+
+ /**
+ * Returns the service implementation of this collection (for sub-classes).
+ */
+ protected abstract CollectionService<E> service();
+
+ /**
+ * Returns the service implementation of any fast collection
+ * (for sub-classes).
+ */
+ protected static <E> CollectionService<E> serviceOf(
+ FastCollection<E> collection) {
+ return collection.service();
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Textual format.
+ //
+
+ /**
+ * Default text format for fast collections (parsing not supported).
+ * It is the format used when printing standard {@code java.util.Collection}
+ * instances except that elements are written using
+ * their current {@link TextContext TextContext} format.
+ */
+ @Parallelizable
+ public static class Format extends TextFormat<FastCollection<?>> {
+
+ @Override
+ public FastCollection<Object> parse(CharSequence csq, Cursor cursor)
+ throws IllegalArgumentException {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Appendable format(FastCollection<?> that, final Appendable dest)
+ throws IOException {
+ dest.append('[');
+ Class<?> elementType = null;
+ TextFormat<Object> format = null;
+ for (Object element : that) {
+ if (elementType == null) elementType = Void.class;
+ else dest.append(", "); // Not the first.
+ if (element == null) {
+ dest.append("null");
+ continue;
+ }
+ Class<?> cls = element.getClass();
+ if (elementType.equals(cls)) {
+ format.format(element, dest);
+ continue;
+ }
+ elementType = cls;
+ format = TextContext.getFormat(cls);
+ format.format(element, dest);
+ }
+ return dest.append(']');
+ }
+
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/FastMap.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/FastMap.java b/commons/marmotta-commons/src/ext/java/javolution/util/FastMap.java
new file mode 100644
index 0000000..852d86c
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/FastMap.java
@@ -0,0 +1,422 @@
+/*
+ * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
+ * Copyright (C) 2012 - Javolution (http://javolution.org/)
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software is
+ * freely granted, provided that this notice is preserved.
+ */
+package javolution.util;
+
+import static javolution.lang.Realtime.Limit.CONSTANT;
+import static javolution.lang.Realtime.Limit.LINEAR;
+
+import java.io.Serializable;
+import java.util.ConcurrentModificationException;
+import java.util.Map;
+import java.util.concurrent.ConcurrentMap;
+
+import javolution.lang.Immutable;
+import javolution.lang.Parallelizable;
+import javolution.lang.Realtime;
+import javolution.text.TextContext;
+import javolution.util.function.Consumer;
+import javolution.util.function.Equalities;
+import javolution.util.function.Equality;
+import javolution.util.internal.map.AtomicMapImpl;
+import javolution.util.internal.map.FastMapImpl;
+import javolution.util.internal.map.ParallelMapImpl;
+import javolution.util.internal.map.SequentialMapImpl;
+import javolution.util.internal.map.SharedMapImpl;
+import javolution.util.internal.map.UnmodifiableMapImpl;
+import javolution.util.service.CollectionService;
+import javolution.util.service.MapService;
+
+/**
+ * <p> A high-performance hash map with {@link Realtime real-time} behavior.
+ * Related to {@link FastCollection}, fast map supports various views.
+ * <ul>
+ * <li>{@link #atomic} - Thread-safe view for which all reads are mutex-free
+ * and map updates (e.g. {@link #putAll putAll}) are atomic.</li>
+ * <li>{@link #shared} - View allowing concurrent modifications.</li>
+ * <li>{@link #parallel} - A view allowing parallel processing including {@link #update updates}.</li>
+ * <li>{@link #sequential} - View disallowing parallel processing.</li>
+ * <li>{@link #unmodifiable} - View which does not allow any modifications.</li>
+ * <li>{@link #entrySet} - {@link FastSet} view over the map entries allowing
+ * entries to be added/removed.</li>
+ * <li>{@link #keySet} - {@link FastSet} view over the map keys allowing keys
+ * to be added (map entry with {@code null} value).</li>
+ * <li>{@link #values} - {@link FastCollection} view over the map values (add not supported).</li>
+ * </ul>
+ * <p> The iteration order over the map keys, values or entries is deterministic
+ * (unlike {@link java.util.HashMap}). It is either the insertion order (default)
+ * or the key order for the {@link FastSortedMap} subclass.
+ * This class permits {@code null} keys.</p>
+ *
+ * <p> Fast maps can advantageously replace any of the standard <code>java.util</code> maps.</p>
+ * [code]
+ * FastMap<Foo, Bar> hashMap = new FastMap<Foo, Bar>();
+ * FastMap<Foo, Bar> concurrentHashMap = new FastMap<Foo, Bar>().shared(); // FastMap implements ConcurrentMap interface.
+ * FastMap<Foo, Bar> linkedHashMap = new FastMap<Foo, Bar>(); // Deterministic iteration order (insertion order).
+ * FastMap<Foo, Bar> treeMap = new FastSortedMap<Foo, Bar>();
+ * FastMap<Foo, Bar> concurrentSkipListMap = new FastSortedMap<Foo, Bar>().shared();
+ * FastMap<Foo, Bar> identityHashMap = new FastMap<Foo, Bar>(Equalities.IDENTITY);[/code]</p>
+ * <p> and adds more ...
+ * [code]
+ * FastMap<Foo, Bar> atomicMap = new FastMap<Foo, Bar>().atomic(); // Mutex-free access, all updates (e.g. putAll) atomics (unlike ConcurrentHashMap).
+ * FastMap<Foo, Bar> atomicTree = new FastSortedMap<Foo, Bar>().atomic(); // Mutex-free access, all updates (e.g. putAll) atomics.
+ * FastMap<Foo, Bar> parallelMap = new FastMap<Foo, Bar>().parallel(); // Map actions (perform/update) performed concurrently.
+ * FastMap<Foo, Bar> linkedConcurrentHashMap = new FastMap<Foo, Bar>().shared(); // No equivalent in java.util !
+ * FastMap<String, Bar> lexicalHashMap = new FastMap<String, Bar>(Equalities.LEXICAL); // Allows for value retrieval using any CharSequence key.
+ * FastMap<String, Bar> fastStringHashMap = new FastMap<String, Bar>(Equalities.LEXICAL_FAST); // Same with faster hashcode calculations.
+ * ...[/code]</p>
+ *
+ * <p> Of course all views (entry, key, values) over a fast map are fast collections
+ * and allow parallel processing.
+ * [code]
+ * Consumer<Collection<String>> removeNull = new Consumer<Collection<String>>() {
+ * public void accept(Collection<String> view) {
+ * Iterator<String> it = view.iterator();
+ * while (it.hasNext()) {
+ * if (it.next() == null) it.remove();
+ * }
+ * }
+ * };
+ * FastMap<Person, String> names = ...
+ * names.values().update(removeNull); // Remove all entries with null values.
+ * names.atomic().values().update(removeNull); // Same but performed atomically.
+ * names.parallel().values().update(removeNull); // Same but performed in parallel.
+ * [/code]</p>
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle </a>
+ * @version 6.0, July 21, 2013
+ */
+@Realtime
+public class FastMap<K, V> implements Map<K, V>, ConcurrentMap<K, V>,
+ Serializable {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * Holds the actual map service implementation.
+ */
+ private final MapService<K, V> service;
+
+ /**
+ * Creates an empty fast map.
+ */
+ public FastMap() {
+ this(Equalities.STANDARD);
+ }
+
+ /**
+ * Creates an empty fast map using the specified comparator for keys
+ * equality.
+ */
+ public FastMap(Equality<? super K> keyEquality) {
+ this(keyEquality, Equalities.STANDARD);
+ }
+
+ /**
+ * Creates an empty fast map using the specified comparators for keys
+ * equality and values equality.
+ */
+ public FastMap(Equality<? super K> keyEquality,
+ Equality<? super V> valueEquality) {
+ service = new FastMapImpl<K, V>(keyEquality, valueEquality);
+ }
+
+ /**
+ * Creates a map backed up by the specified service implementation.
+ */
+ protected FastMap(MapService<K, V> service) {
+ this.service = service;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Views.
+ //
+
+ /**
+ * Returns an atomic view over this map. All operations that write
+ * or access multiple elements in the map (such as putAll(),
+ * keySet().retainAll(), ...) are atomic.
+ * Iterators on atomic collections are <b>thread-safe</b>
+ * (no {@link ConcurrentModificationException} possible).
+ */
+ @Parallelizable(mutexFree = true, comment = "Except for write operations, all read operations are mutex-free.")
+ public FastMap<K, V> atomic() {
+ return new FastMap<K, V>(new AtomicMapImpl<K, V>(service));
+ }
+
+ /**
+ * Returns a thread-safe view over this map. The shared view
+ * allows for concurrent read as long as there is no writer.
+ * The default implementation is based on <a href=
+ * "http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock">
+ * readers-writers locks</a> giving priority to writers.
+ * Iterators on shared collections are <b>thread-safe</b>
+ * (no {@link ConcurrentModificationException} possible).
+ */
+ @Parallelizable(mutexFree = false, comment = "Use multiple-readers/single-writer lock.")
+ public FastMap<K, V> shared() {
+ return new FastMap<K, V>(new SharedMapImpl<K, V>(service));
+ }
+
+ /**
+ * Returns a parallel map. Parallel maps affect closure-based operations
+ * over the map or any of its views (entry, key, values, etc.), all others
+ * operations behaving the same. Parallel maps do not require this map
+ * to be thread-safe (internal synchronization).
+ *
+ * @see #perform(Consumer)
+ * @see #update(Consumer)
+ * @see FastCollection#parallel()
+ */
+ public FastMap<K, V> parallel() {
+ return new FastMap<K, V>(new ParallelMapImpl<K, V>(service));
+ }
+
+ /**
+ * Returns a sequential view of this collection. Using this view,
+ * all closure-based iterations are performed sequentially.
+ */
+ public FastMap<K, V> sequential() {
+ return new FastMap<K, V>(new SequentialMapImpl<K, V>(service));
+ }
+
+ /**
+ * Returns an unmodifiable view over this map. Any attempt to
+ * modify the map through this view will result into
+ * a {@link java.lang.UnsupportedOperationException} being raised.
+ */
+ public FastMap<K, V> unmodifiable() {
+ return new FastMap<K, V>(new UnmodifiableMapImpl<K, V>(service));
+ }
+
+ /**
+ * Returns a set view of the keys contained in this map.
+ * The set is backed by the map, so changes to the map are
+ * reflected in the set, and vice-versa. The set supports
+ * adding new keys for which the corresponding entry value
+ * is always {@code null}.
+ */
+ public FastSet<K> keySet() {
+ return new FastSet<K>(service.keySet());
+ }
+
+ /**
+ * Returns a collection view of the values contained in this map.
+ * The collection is backed by the map, so changes to the map are
+ * reflected in the collection, and vice-versa. The collection
+ * supports removing values (hence entries) but not adding new values.
+ */
+ public FastCollection<V> values() {
+ return new FastCollection<V>() {
+ private static final long serialVersionUID = 0x600L; // Version.
+ private final CollectionService<V> serviceValues = service.values();
+
+ @Override
+ protected CollectionService<V> service() {
+ return serviceValues;
+ }
+ };
+ }
+
+ /**
+ * Returns a set view of the mappings contained in
+ * this map. The set is backed by the map, so changes to the map are
+ * reflected in the set, and vice-versa. The set
+ * support adding/removing entries. As far as the set is concerned,
+ * two entries are considered equals if they have the same keys regardless
+ * of their values.
+ */
+ public FastSet<Entry<K, V>> entrySet() {
+ return new FastSet<Entry<K, V>>(service.entrySet());
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Closures operations.
+ //
+
+ /**
+ * Executes the specified read-only action on this map.
+ * That logic may be performed concurrently on sub-maps
+ * if this map is {@link #parallel() parallel}.
+ *
+ * @param action the read-only action.
+ * @throws UnsupportedOperationException if the action tries to update
+ * this map.
+ * @throws ClassCastException if the action type is not compatible with
+ * this map (e.g. action on sorted map and this is a hash map).
+ * @see #update(Consumer)
+ */
+ @Realtime(limit = LINEAR)
+ @SuppressWarnings("unchecked")
+ public void perform(Consumer<? extends Map<K, V>> action) {
+ service().perform((Consumer<MapService<K, V>>) action, service());
+ }
+
+ /**
+ * Executes the specified update action on this map.
+ * That logic may be performed concurrently on sub-maps
+ * if this map is {@link #parallel() parallel}.
+ * For {@link #atomic() atomic} maps the update is atomic (either concurrent
+ * readers see the full result of the action or nothing).
+ *
+ * @param action the update action.
+ * @throws ClassCastException if the action type is not compatible with
+ * this map (e.g. action on sorted map and this is a hash map).
+ * @see #perform(Consumer)
+ */
+ @Realtime(limit = LINEAR)
+ @SuppressWarnings("unchecked")
+ public void update(Consumer<? extends Map<K, V>> action) {
+ service().update((Consumer<MapService<K, V>>) action, service());
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Map Interface.
+ //
+
+ /** Returns the number of entries/keys/values in this map. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public int size() {
+ return service.size();
+ }
+
+ /** Indicates if this map is empty */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean isEmpty() {
+ return service.isEmpty();
+ }
+
+ /** Indicates if this map contains the specified key. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean containsKey(Object key) {
+ return service.containsKey(key);
+ }
+
+ /** Indicates if this map contains the specified value. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public boolean containsValue(Object value) {
+ return service.containsValue(value);
+ }
+
+ /** Returns the value for the specified key. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public V get(Object key) {
+ return service.get(key);
+ }
+
+ /** Associates the specified value with the specified key. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public V put(K key, V value) {
+ return service.put(key, value);
+ }
+
+ /** Adds the specified map entries to this map. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public void putAll(Map<? extends K, ? extends V> map) {
+ service.putAll(map);
+ }
+
+ /** Removes the entry for the specified key. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public V remove(Object key) {
+ return service.remove(key);
+ }
+
+ /** Removes all this map's entries. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public void clear() {
+ service.clear();
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // ConcurrentMap Interface.
+ //
+
+ /** Associates the specified value with the specified key only if the
+ * specified key has no current mapping. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public V putIfAbsent(K key, V value) {
+ return service.putIfAbsent(key, value);
+ }
+
+ /** Removes the entry for a key only if currently mapped to a given value. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean remove(Object key, Object value) {
+ return service.remove(key, value);
+ }
+
+ /** Replaces the entry for a key only if currently mapped to a given value. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean replace(K key, V oldValue, V newValue) {
+ return service.replace(key, oldValue, newValue);
+ }
+
+ /** Replaces the entry for a key only if currently mapped to some value. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public V replace(K key, V value) {
+ return service.replace(key, value);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Misc.
+ //
+
+ /**
+ * Returns this map with the specified map's entries added.
+ */
+ public FastMap<K, V> putAll(FastMap<? extends K, ? extends V> that) {
+ putAll((Map<? extends K, ? extends V>) that);
+ return this;
+ }
+
+ /**
+ * Returns an immutable reference over this map. The immutable
+ * value is an {@link #unmodifiable() unmodifiable} view of this map
+ * for which the caller guarantees that no change will ever be made
+ * (e.g. there is no reference left to the original map).
+ */
+ public <T extends Map<K, V>> Immutable<T> toImmutable() {
+ return new Immutable<T>() {
+ @SuppressWarnings("unchecked")
+ final T value = (T) unmodifiable();
+
+ @Override
+ public T value() {
+ return value;
+ }
+ };
+ }
+
+ /** Returns the string representation of this map entries. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public String toString() {
+ return TextContext.getFormat(FastCollection.class).format(entrySet());
+ }
+
+ /**
+ * Returns this map service implementation.
+ */
+ protected MapService<K, V> service() {
+ return service;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/FastSet.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/FastSet.java b/commons/marmotta-commons/src/ext/java/javolution/util/FastSet.java
new file mode 100644
index 0000000..792173d
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/FastSet.java
@@ -0,0 +1,146 @@
+/*
+ * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
+ * Copyright (C) 2012 - Javolution (http://javolution.org/)
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software is
+ * freely granted, provided that this notice is preserved.
+ */
+package javolution.util;
+
+import static javolution.lang.Realtime.Limit.CONSTANT;
+
+import java.util.Set;
+
+import javolution.lang.Realtime;
+import javolution.util.function.Equalities;
+import javolution.util.function.Equality;
+import javolution.util.function.Predicate;
+import javolution.util.internal.map.FastMapImpl;
+import javolution.util.internal.set.AtomicSetImpl;
+import javolution.util.internal.set.FilteredSetImpl;
+import javolution.util.internal.set.SharedSetImpl;
+import javolution.util.internal.set.UnmodifiableSetImpl;
+import javolution.util.service.SetService;
+
+/**
+ * <p> A high-performance hash set with {@link Realtime real-time} behavior.</p>
+ *
+ * <p> The iteration order over the set elements is deterministic
+ * (unlike {@link java.util.HashSet}).It is either the insertion order (default)
+ * or the key order for the {@link FastSortedSet} subclass.
+ * This class permits {@code null} elements.</p>
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public class FastSet<E> extends FastCollection<E> implements Set<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * Holds the actual service implementation.
+ */
+ private final SetService<E> service;
+
+ /**
+ * Creates an empty set backed up by a {@link FastMap} and having
+ * the same real-time characteristics.
+ */
+ public FastSet() {
+ this(Equalities.STANDARD);
+ }
+
+ /**
+ * Creates an empty set backed up by a {@link FastMap} and using the
+ * specified comparator for key equality.
+ */
+ public FastSet(Equality<? super E> comparator) {
+ service = new FastMapImpl<E, Void>(comparator, Equalities.IDENTITY)
+ .keySet();
+ }
+
+ /**
+ * Creates a fast set backed up by the specified service implementation.
+ */
+ protected FastSet(SetService<E> service) {
+ this.service = service;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Views.
+ //
+
+ @Override
+ public FastSet<E> atomic() {
+ return new FastSet<E>(new AtomicSetImpl<E>(service()));
+ }
+
+ @Override
+ public FastSet<E> filtered(final Predicate<? super E> filter) {
+ return new FastSet<E>(new FilteredSetImpl<E>(service(), filter));
+ }
+
+ @Override
+ public FastSet<E> shared() {
+ return new FastSet<E>(new SharedSetImpl<E>(service()));
+ }
+
+ @Override
+ public FastSet<E> unmodifiable() {
+ return new FastSet<E>(new UnmodifiableSetImpl<E>(service()));
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Set operations new annotations.
+ //
+
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean isEmpty() {
+ return size() == 0;
+ }
+
+ @Override
+ @Realtime(limit = CONSTANT)
+ public int size() {
+ return service.size();
+ }
+
+ @Override
+ @Realtime(limit = CONSTANT)
+ public void clear() {
+ service.clear();
+ }
+
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean contains(Object obj) {
+ return service.contains(obj);
+ }
+
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean remove(Object obj) {
+ return service.remove(obj);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Misc.
+ //
+
+ @Override
+ public FastSet<E> addAll(E... elements) {
+ return (FastSet<E>) super.addAll(elements);
+ }
+
+ @Override
+ public FastSet<E> addAll(FastCollection<? extends E> that) {
+ return (FastSet<E>) super.addAll(that);
+ }
+
+ @Override
+ protected SetService<E> service() {
+ return service;
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedMap.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedMap.java b/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedMap.java
new file mode 100644
index 0000000..c971a66
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedMap.java
@@ -0,0 +1,205 @@
+/*
+ * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
+ * Copyright (C) 2012 - Javolution (http://javolution.org/)
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software is
+ * freely granted, provided that this notice is preserved.
+ */
+package javolution.util;
+
+import static javolution.lang.Realtime.Limit.LOG_N;
+
+import java.util.Comparator;
+import java.util.SortedMap;
+
+import javolution.lang.Realtime;
+import javolution.util.function.Equalities;
+import javolution.util.function.Equality;
+import javolution.util.internal.map.sorted.AtomicSortedMapImpl;
+import javolution.util.internal.map.sorted.FastSortedMapImpl;
+import javolution.util.internal.map.sorted.SharedSortedMapImpl;
+import javolution.util.internal.map.sorted.UnmodifiableSortedMapImpl;
+import javolution.util.service.SortedMapService;
+
+/**
+ * <p> A high-performance sorted map with {@link Realtime real-time} behavior.</p>
+ *
+ * <p> This map provides a total ordering based on the keys natural order or
+ * using custom {@link #FastSortedMap(Equality) comparators}.</p>
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public class FastSortedMap<K, V> extends FastMap<K, V> implements
+ SortedMap<K, V> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * Creates an empty sorted map ordered on keys natural order.
+ */
+ public FastSortedMap() {
+ this(Equalities.STANDARD);
+ }
+
+ /**
+ * Creates an empty sorted map ordered using the specified comparator
+ * for order.
+ */
+ public FastSortedMap(Equality<? super K> keyComparator) {
+ this(keyComparator, Equalities.STANDARD);
+ }
+
+ /**
+ * Creates an empty sorted map ordered using the specified key comparator
+ * for order and value comparator for values equality.
+ */
+ public FastSortedMap(Equality<? super K> keyComparator,
+ Equality<? super V> valueComparator) {
+ super(new FastSortedMapImpl<K, V>(keyComparator, valueComparator));
+ }
+
+ /**
+ * Creates a sorted map backed up by the specified service implementation.
+ */
+ protected FastSortedMap(SortedMapService<K, V> service) {
+ super(service);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Views.
+ //
+
+ @Override
+ public FastSortedMap<K, V> atomic() {
+ return new FastSortedMap<K, V>(new AtomicSortedMapImpl<K, V>(service()));
+ }
+
+ @Override
+ public FastSortedMap<K, V> shared() {
+ return new FastSortedMap<K, V>(new SharedSortedMapImpl<K, V>(service()));
+ }
+
+ @Override
+ public FastSortedMap<K, V> unmodifiable() {
+ return new FastSortedMap<K, V>(new UnmodifiableSortedMapImpl<K, V>(
+ service()));
+ }
+
+ @Override
+ public FastSortedSet<Entry<K, V>> entrySet() {
+ return new FastSortedSet<Entry<K, V>>(service().entrySet());
+ }
+
+ @Override
+ public FastSortedSet<K> keySet() {
+ return new FastSortedSet<K>(service().keySet());
+ }
+
+ /** Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive. */
+ @Override
+ public FastSortedMap<K, V> subMap(K fromKey, K toKey) {
+ return new FastSortedMap<K, V>(service().subMap(fromKey, toKey));
+ }
+
+ /** Returns a view of the portion of this map whose keys are strictly less than toKey. */
+ @Override
+ public FastSortedMap<K, V> headMap(K toKey) {
+ return new FastSortedMap<K, V>(service().subMap(firstKey(), toKey));
+ }
+
+ /** Returns a view of the portion of this map whose keys are greater than or equal to fromKey. */
+ @Override
+ public FastSortedMap<K, V> tailMap(K fromKey) {
+ return new FastSortedMap<K, V>(service().subMap(fromKey, lastKey()));
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Change in time limit behavior.
+ //
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public boolean containsKey(Object key) {
+ return super.containsKey(key);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public V get(Object key) {
+ return super.get(key);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public V put(K key, V value) {
+ return super.put(key, value);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public V remove(Object key) {
+ return super.remove(key);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public V putIfAbsent(K key, V value) {
+ return super.putIfAbsent(key, value);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public boolean remove(Object key, Object value) {
+ return super.remove(key, value);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public boolean replace(K key, V oldValue, V newValue) {
+ return super.replace(key, oldValue, newValue);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public V replace(K key, V value) {
+ return super.replace(key, value);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // SortedMap Interface.
+ //
+
+ /** Returns the first (lowest) key currently in this map. */
+ @Override
+ public K firstKey() {
+ return service().firstKey();
+ }
+
+ /** Returns the last (highest) key currently in this map. */
+ @Override
+ public K lastKey() {
+ return service().lastKey();
+ }
+
+ /** Returns the comparator used to order the keys in this map (never null). */
+ @Override
+ public Comparator<? super K> comparator() {
+ return keySet().comparator();
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Misc.
+ //
+
+ @Override
+ public FastSortedMap<K, V> putAll(FastMap<? extends K, ? extends V> that) {
+ return (FastSortedMap<K, V>) super.putAll(that);
+ }
+
+ @Override
+ protected SortedMapService<K, V> service() {
+ return (SortedMapService<K, V>) super.service();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedSet.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedSet.java b/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedSet.java
new file mode 100644
index 0000000..1d446d7
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedSet.java
@@ -0,0 +1,153 @@
+/*
+ * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
+ * Copyright (C) 2012 - Javolution (http://javolution.org/)
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software is
+ * freely granted, provided that this notice is preserved.
+ */
+package javolution.util;
+
+import static javolution.lang.Realtime.Limit.LOG_N;
+
+import java.util.SortedSet;
+
+import javolution.lang.Realtime;
+import javolution.util.function.Equalities;
+import javolution.util.function.Equality;
+import javolution.util.internal.map.sorted.FastSortedMapImpl;
+import javolution.util.internal.set.sorted.AtomicSortedSetImpl;
+import javolution.util.internal.set.sorted.SharedSortedSetImpl;
+import javolution.util.internal.set.sorted.UnmodifiableSortedSetImpl;
+import javolution.util.service.SortedSetService;
+
+/**
+ * <p> A high-performance sorted set with {@link Realtime real-time} behavior.</p>
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public class FastSortedSet<E> extends FastSet<E> implements SortedSet<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * Creates an empty sorted set ordered on elements natural order.
+ */
+ public FastSortedSet() {
+ this(Equalities.STANDARD);
+ }
+
+ /**
+ * Creates an empty sorted set ordered using the specified comparator.
+ */
+ public FastSortedSet(Equality<? super E> comparator) {
+ super(new FastSortedMapImpl<E, Void>(comparator, Equalities.IDENTITY)
+ .keySet());
+ }
+
+ /**
+ * Creates a sorted set backed up by the specified service implementation.
+ */
+ protected FastSortedSet(SortedSetService<E> service) {
+ super(service);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Views.
+ //
+
+ @Override
+ public FastSortedSet<E> atomic() {
+ return new FastSortedSet<E>(new AtomicSortedSetImpl<E>(service()));
+ }
+
+ @Override
+ public FastSortedSet<E> shared() {
+ return new FastSortedSet<E>(new SharedSortedSetImpl<E>(service()));
+ }
+
+ @Override
+ public FastSortedSet<E> unmodifiable() {
+ return new FastSortedSet<E>(new UnmodifiableSortedSetImpl<E>(service()));
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Change in time limit behavior.
+ //
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public boolean add(E e) {
+ return super.add(e);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public boolean contains(Object obj) {
+ return super.contains(obj);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public boolean remove(Object obj) {
+ return super.remove(obj);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // SortedSet Interface.
+ //
+
+ /** Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive. */
+ @Override
+ @Realtime(limit = LOG_N)
+ public FastSortedSet<E> subSet(E fromElement, E toElement) {
+ return new FastSortedSet<E>(service().subSet(fromElement, toElement));
+ }
+
+ /** Returns a view of the portion of this set whose elements are strictly less than toElement. */
+ @Override
+ @Realtime(limit = LOG_N)
+ public FastSortedSet<E> headSet(E toElement) {
+ return subSet(first(), toElement);
+ }
+
+ /** Returns a view of the portion of this set whose elements are greater than or equal to fromElement. */
+ @Override
+ @Realtime(limit = LOG_N)
+ public FastSortedSet<E> tailSet(E fromElement) {
+ return subSet(fromElement, last());
+ }
+
+ /** Returns the first (lowest) element currently in this set. */
+ @Override
+ public E first() {
+ return service().first();
+ }
+
+ /** Returns the last (highest) element currently in this set. */
+ @Override
+ public E last() {
+ return service().last();
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Misc.
+ //
+
+ @Override
+ public FastSortedSet<E> addAll(E... elements) {
+ return (FastSortedSet<E>) super.addAll(elements);
+ }
+
+ @Override
+ public FastSortedSet<E> addAll(FastCollection<? extends E> that) {
+ return (FastSortedSet<E>) super.addAll(that);
+ }
+
+ @Override
+ protected SortedSetService<E> service() {
+ return (SortedSetService<E>) super.service();
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedTable.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedTable.java b/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedTable.java
new file mode 100644
index 0000000..9151026
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/FastSortedTable.java
@@ -0,0 +1,137 @@
+/*
+ * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
+ * Copyright (C) 2012 - Javolution (http://javolution.org/)
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software is
+ * freely granted, provided that this notice is preserved.
+ */
+package javolution.util;
+
+import static javolution.lang.Realtime.Limit.LOG_N;
+import javolution.lang.Realtime;
+import javolution.util.function.Equalities;
+import javolution.util.function.Equality;
+import javolution.util.internal.table.sorted.AtomicSortedTableImpl;
+import javolution.util.internal.table.sorted.FastSortedTableImpl;
+import javolution.util.internal.table.sorted.SharedSortedTableImpl;
+import javolution.util.internal.table.sorted.UnmodifiableSortedTableImpl;
+import javolution.util.service.SortedTableService;
+
+/**
+ * <p> A high-performance sorted table with {@link Realtime real-time} behavior.
+ * Sorted table have significantly faster {@link #contains},
+ * {@link #indexOf} and {@link #remove} methods).</p>
+ *
+ * <p>This class is comparable to {@link FastSortedSet} in performance,
+ * but it allows for duplicate and implements the {@link java.util.List}
+ * interface.</p>
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public class FastSortedTable<E> extends FastTable<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * Creates an empty table sorted using its elements natural order.
+ */
+ public FastSortedTable() {
+ this(Equalities.STANDARD);
+ }
+
+ /**
+ * Creates an empty table sorted using the specified element comparator.
+ */
+ public FastSortedTable(Equality<? super E> comparator) {
+ super(new FastSortedTableImpl<E>(comparator));
+ }
+
+ /**
+ * Creates a sorted table backed up by the specified service implementation.
+ */
+ protected FastSortedTable(SortedTableService<E> service) {
+ super(service);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Views.
+ //
+
+ @Override
+ public FastSortedTable<E> atomic() {
+ return new FastSortedTable<E>(new AtomicSortedTableImpl<E>(service()));
+ }
+
+ @Override
+ public FastSortedTable<E> shared() {
+ return new FastSortedTable<E>(new SharedSortedTableImpl<E>(service()));
+ }
+
+ @Override
+ public FastSortedTable<E> unmodifiable() {
+ return new FastSortedTable<E>(new UnmodifiableSortedTableImpl<E>(
+ service()));
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Change in time limit behavior.
+ //
+
+ @Realtime(limit = LOG_N)
+ public boolean contains(Object obj) {
+ return service().contains(obj);
+ }
+
+ @Realtime(limit = LOG_N)
+ public boolean remove(Object obj) {
+ return service().remove(obj);
+ }
+
+ @Override
+ @Realtime(limit = LOG_N)
+ public int indexOf(final Object obj) {
+ return service().indexOf(obj);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Misc.
+ //
+
+ /**
+ * Adds the specified element only if not already present.
+ *
+ * @return {@code true} if the element has been added;
+ * {@code false} otherwise.
+ */
+ @Realtime(limit = LOG_N)
+ public boolean addIfAbsent(E element) {
+ return service().addIfAbsent(element);
+ }
+
+ /**
+ * Returns what would be the index of the specified element if it were
+ * to be added or the index of the specified element if already present.
+ */
+ @Realtime(limit = LOG_N)
+ public int positionOf(E element) {
+ return service().positionOf(element);
+ }
+
+ @Override
+ public FastSortedTable<E> addAll(E... elements) {
+ return (FastSortedTable<E>) super.addAll(elements);
+ }
+
+ @Override
+ public FastSortedTable<E> addAll(FastCollection<? extends E> that) {
+ return (FastSortedTable<E>) super.addAll(that);
+ }
+
+ @Override
+ protected SortedTableService<E> service() {
+ return (SortedTableService<E>) super.service();
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/FastTable.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/FastTable.java b/commons/marmotta-commons/src/ext/java/javolution/util/FastTable.java
new file mode 100644
index 0000000..1e87fb8
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/FastTable.java
@@ -0,0 +1,453 @@
+/*
+ * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
+ * Copyright (C) 2012 - Javolution (http://javolution.org/)
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software is
+ * freely granted, provided that this notice is preserved.
+ */
+package javolution.util;
+
+import static javolution.lang.Realtime.Limit.CONSTANT;
+import static javolution.lang.Realtime.Limit.LINEAR;
+import static javolution.lang.Realtime.Limit.LOG_N;
+import static javolution.lang.Realtime.Limit.N_LOG_N;
+import static javolution.lang.Realtime.Limit.N_SQUARE;
+
+import java.util.Collection;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.RandomAccess;
+
+import javolution.lang.Realtime;
+import javolution.util.function.Consumer;
+import javolution.util.function.Equalities;
+import javolution.util.function.Equality;
+import javolution.util.internal.table.AtomicTableImpl;
+import javolution.util.internal.table.FastTableImpl;
+import javolution.util.internal.table.QuickSort;
+import javolution.util.internal.table.ReversedTableImpl;
+import javolution.util.internal.table.SharedTableImpl;
+import javolution.util.internal.table.SubTableImpl;
+import javolution.util.internal.table.UnmodifiableTableImpl;
+import javolution.util.service.TableService;
+
+/**
+ * <p> A high-performance table (fractal-based) with {@link Realtime real-time}
+ * behavior.</p>
+ *
+ * <p> The fractal-based implementation ensures that add/insertion/deletion operations
+ * <b>worst</b> execution time is always in less than <i><b>O(log(size))</b></i>.
+ * For comparison {@code ArrayList.add} is in <i><b>O(size)</b></i> due to resize. </p>
+ *
+ * <a href="doc-files/FastTable-WCET.png">
+ * <img src="doc-files/FastTable-WCET.png" alt="Worst Case Execution Time" height="210" width="306" />
+ * </a>
+ *
+ * <p> Instances of this class can advantageously replace {@link java.util.ArrayList ArrayList},
+ * {@link java.util.LinkedList LinkedList} or {@link java.util.ArrayDeque ArrayDeque}
+ * in terms of adaptability, space or performance.
+ * Fast tables can be concurrently iterated / modified using their {@link #shared() shared}/{@link #atomic() atomic}
+ * views. They inherit all the fast collection views and support the {@link #subTable subTable} view over a portion of the table.
+ * [code]
+ * FastTable<String> names = new FastTable<String>().addAll("John Deuff", "Otto Graf", "Sim Kamil");
+ * names.sort(Equalities.LEXICAL_CASE_INSENSITIVE); // Sorts the names in place (different from sorted() which returns a sorted view).
+ * names.subTable(0, names.size() / 2).clear(); // Removes the first half of the table (see java.util.List.subList specification).
+ * names.filtered(str -> str.startsWith("A")).clear(); // Removes all the names starting with "A" (Java 8 notation).
+ * names.filtered(str -> str.startsWith("A")).parallel().clear(); // Same as above but performed concurrently.
+ * [/code]</p>
+ *
+ * <p> As for any {@link FastCollection fast collection}, iterations can be
+ * performed using closures.
+ * [code]
+ * FastTable<Person> persons = ...
+ * Person findWithName(final String name) {
+ * return persons.filtered(new Predicate<Person>() {
+ * public boolean test(Person person) {
+ * return (person.getName().equals(name));
+ * }
+ * }).any(Person.class);
+ * }[/code]</p>
+ *
+ * <p> The notation is shorter with Java 8.
+ * [code]
+ * Person findWithName(String name) {
+ * return persons.filtered(person -> person.getName().equals(name)).any(Person.class);
+ * }[/code]</p>
+ *
+ * <p> FastTable iteration order is the {@link #add insertion} order; specialization may
+ * have a different order, for example the iteration order of {@link FastSortedTable}
+ * is based on the table sorting order.</p>
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public class FastTable<E> extends FastCollection<E> implements List<E>,
+ Deque<E>, RandomAccess {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * Holds the actual service implementation.
+ */
+ private final TableService<E> service;
+
+ /**
+ * Creates an empty table whose capacity increments/decrements smoothly
+ * without large resize operations to best fit the table current size.
+ */
+ public FastTable() {
+ this(Equalities.STANDARD);
+ }
+
+ /**
+ * Creates an empty table using the specified comparator for element
+ * equality.
+ */
+ public FastTable(Equality<? super E> comparator) {
+ service = new FastTableImpl<E>(comparator);
+ }
+
+ /**
+ * Creates a fast table backed up by the specified service implementation.
+ */
+ protected FastTable(TableService<E> service) {
+ this.service = service;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Views.
+ //
+
+ @Override
+ public FastTable<E> atomic() {
+ return new FastTable<E>(new AtomicTableImpl<E>(service));
+ }
+
+ @Override
+ public FastTable<E> reversed() {
+ return new FastTable<E>(new ReversedTableImpl<E>(service));
+ }
+
+ @Override
+ public FastTable<E> shared() {
+ return new FastTable<E>(new SharedTableImpl<E>(service));
+ }
+
+ @Override
+ public FastTable<E> unmodifiable() {
+ return new FastTable<E>(new UnmodifiableTableImpl<E>(service));
+ }
+
+ /**
+ * Returns a view over a portion of the table (equivalent to
+ * {@link java.util.List#subList(int, int)}).
+ */
+ public FastTable<E> subTable(int fromIndex, int toIndex) {
+ return new FastTable<E>(
+ new SubTableImpl<E>(service, fromIndex, toIndex));
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Change in time limit behavior.
+ //
+
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean isEmpty() {
+ return service.isEmpty();
+ }
+
+ @Override
+ @Realtime(limit = CONSTANT)
+ public int size() {
+ return service.size();
+ }
+
+ @Override
+ @Realtime(limit = CONSTANT)
+ public void clear() {
+ service.clear();
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // List Interface.
+ //
+
+ /** Inserts the specified element at the specified position in this table. */
+ @Override
+ @Realtime(limit = LOG_N)
+ public void add(int index, E element) {
+ service.add(index, element);
+ }
+
+ /** Inserts all of the elements in the specified collection into this table
+ * at the specified position. */
+ @Override
+ @Realtime(limit = N_LOG_N)
+ public boolean addAll(final int index, Collection<? extends E> elements) {
+ return service.addAll(index, elements);
+ }
+
+ /** Removes the element at the specified position in this table. */
+ @Override
+ @Realtime(limit = LOG_N)
+ public E remove(int index) {
+ return service.remove(index);
+ }
+
+ /** Returns the element at the specified position in this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E get(int index) {
+ return service.get(index);
+ }
+
+ /** Replaces the element at the specified position in this table with the specified element. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E set(int index, E element) {
+ return service.set(index, element);
+ }
+
+ /** Returns the index of the first occurrence of the specified element in this table,
+ * or -1 if this table does not contain the element. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public int indexOf(Object element) {
+ return service.indexOf(element);
+ }
+
+ /** Returns the index of the last occurrence of the specified element in this table,
+ * or -1 if this table does not contain the element. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public int lastIndexOf(final Object element) {
+ return service.lastIndexOf(element);
+ }
+
+ /** Returns a list iterator over the elements in this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public ListIterator<E> listIterator() {
+ return service.listIterator();
+ }
+
+ /** Returns a list iterator over the elements in this table, starting
+ * at the specified position in the table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public ListIterator<E> listIterator(int index) {
+ return service.listIterator(index);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Deque Interface.
+ //
+
+ /** Inserts the specified element at the front of this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public void addFirst(E element) {
+ service.addFirst(element);
+ }
+
+ /** Inserts the specified element at the end of this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public void addLast(E element) {
+ service.addLast(element);
+ }
+
+ /** Retrieves, but does not remove, the first element of this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E getFirst() {
+ return service.getFirst();
+ }
+
+ /** Retrieves, but does not remove, the last element of this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E getLast() {
+ return service.getLast();
+ }
+
+ /** Retrieves, but does not remove, the first element of this table,
+ * or returns null if this table is empty. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E peekFirst() {
+ return service.peekFirst();
+ }
+
+ /** Retrieves, but does not remove, the last element of this table,
+ * or returns null if this table is empty. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E peekLast() {
+ return service.peekLast();
+ }
+
+ /** Retrieves and removes the first element of this table,
+ * or returns null if this table is empty. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E pollFirst() {
+ return service.pollFirst();
+ }
+
+ /** . */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E pollLast() {
+ return service.pollLast();
+ }
+
+ /** Retrieves and removes the last element of this table,
+ * or returns null if this table is empty. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E removeFirst() {
+ return service.removeFirst();
+ }
+
+ /** Retrieves and removes the last element of this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E removeLast() {
+ return service.removeLast();
+ }
+
+ /** Inserts the specified element at the front of this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean offerFirst(E e) {
+ return service.offerFirst(e);
+ }
+
+ /** Inserts the specified element at the end of this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean offerLast(E e) {
+ return service.offerLast(e);
+ }
+
+ /** Removes the first occurrence of the specified element from this table. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public boolean removeFirstOccurrence(Object o) {
+ return service.removeFirstOccurrence(o);
+ }
+
+ /** Removes the last occurrence of the specified element from this table. */
+ @Override
+ @Realtime(limit = LINEAR)
+ public boolean removeLastOccurrence(Object o) {
+ return service.removeLastOccurrence(o);
+ }
+
+ /** Inserts the specified element into the queue represented by this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public boolean offer(E e) {
+ return service.offer(e);
+ }
+
+ /** Retrieves and removes the head of the queue represented by this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E remove() {
+ return service.remove();
+ }
+
+ /** Retrieves and removes the head of the queue represented by this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E poll() {
+ return service.poll();
+ }
+
+ /** Retrieves, but does not remove, the head of the queue represented by this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E element() {
+ return service.element();
+ }
+
+ /** Retrieves, but does not remove, the head of the queue represented by this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E peek() {
+ return service.peek();
+ }
+
+ /** Pushes an element onto the stack represented by this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public void push(E e) {
+ service.push(e);
+ }
+
+ /** Pops an element from the stack represented by this table. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public E pop() {
+ return service.pop();
+ }
+
+ /** Returns an iterator over the elements in this table in reverse sequential order. */
+ @Override
+ @Realtime(limit = CONSTANT)
+ public Iterator<E> descendingIterator() {
+ return service.descendingIterator();
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Misc.
+ //
+
+ /**
+ * Sorts this table in place (quick sort).
+ */
+ @Realtime(limit = N_SQUARE)
+ public void sort() {
+ update(new Consumer<TableService<E>>() {
+ @Override
+ public void accept(TableService<E> table) {
+ QuickSort<E> qs = new QuickSort<E>(table, table.comparator());
+ qs.sort();
+ }
+ });
+ }
+
+ @Override
+ @Realtime(limit = LINEAR)
+ public FastTable<E> addAll(E... elements) {
+ return (FastTable<E>) super.addAll(elements);
+ }
+
+ @Override
+ @Realtime(limit = LINEAR)
+ public FastTable<E> addAll(FastCollection<? extends E> that) {
+ return (FastTable<E>) super.addAll(that);
+ }
+
+ /**
+ * Replaced by {@link #subTable(int, int)}. The term "List" for an
+ * interface with random access is disturbing !
+ */
+ @Override
+ @Deprecated
+ public FastTable<E> subList(int fromIndex, int toIndex) {
+ return subTable(fromIndex, toIndex);
+ }
+
+ @Override
+ protected TableService<E> service() {
+ return service;
+ }
+
+}
\ No newline at end of file