You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@marmotta.apache.org by ja...@apache.org on 2013/11/05 11:52:50 UTC
[45/52] [partial] Reverting the erroneous merge by Sebastian
according to the instructions in INFRA-6876
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SharedSortedSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SharedSortedSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SharedSortedSetImpl.java
new file mode 100644
index 0000000..a453b17
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SharedSortedSetImpl.java
@@ -0,0 +1,88 @@
+/*
+ * 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.internal.set.sorted;
+
+import javolution.util.internal.ReadWriteLockImpl;
+import javolution.util.internal.set.SharedSetImpl;
+import javolution.util.service.SetService;
+import javolution.util.service.SortedSetService;
+
+/**
+ * A shared view over a set allowing concurrent access and sequential updates.
+ */
+public class SharedSortedSetImpl<E> extends SharedSetImpl<E> implements
+ SortedSetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public SharedSortedSetImpl(SetService<E> target) {
+ super(target);
+ }
+
+ public SharedSortedSetImpl(SortedSetService<E> target, ReadWriteLockImpl lock) {
+ super(target, lock);
+ }
+
+ @Override
+ public E first() {
+ lock.readLock.lock();
+ try {
+ return target().first();
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public SortedSetService<E> headSet(E toElement) {
+ return new SubSortedSetImpl<E>(this, null, toElement);
+ }
+
+ @Override
+ public E last() {
+ lock.readLock.lock();
+ try {
+ return target().last();
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedSetService<E>[] split(int n, boolean updateable) {
+ SortedSetService<E>[] tmp;
+ lock.readLock.lock();
+ try {
+ tmp = target().split(n, updateable);
+ } finally {
+ lock.readLock.unlock();
+ }
+ SortedSetService<E>[] result = new SortedSetService[tmp.length];
+ for (int i = 0; i < tmp.length; i++) {
+ result[i] = new SharedSortedSetImpl<E>(tmp[i], lock); // Shares the same locks.
+ }
+ return result;
+ }
+
+ @Override
+ public SortedSetService<E> subSet(E fromElement, E toElement) {
+ return new SubSortedSetImpl<E>(this, fromElement, toElement);
+ }
+
+ @Override
+ public SortedSetService<E> tailSet(E fromElement) {
+ return new SubSortedSetImpl<E>(this, fromElement, null);
+ }
+
+ @Override
+ protected SortedSetService<E> target() {
+ return (SortedSetService<E>) super.target();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SortedSetView.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SortedSetView.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SortedSetView.java
new file mode 100644
index 0000000..e932eb2
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SortedSetView.java
@@ -0,0 +1,60 @@
+/*
+ * 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.internal.set.sorted;
+
+import javolution.util.internal.set.SetView;
+import javolution.util.service.SortedSetService;
+
+/**
+ * Sorted Set view implementation; can be used as root class for implementations
+ * if target is {@code null}.
+ */
+public abstract class SortedSetView<E> extends SetView<E> implements SortedSetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * The view constructor or root class constructor if target is {@code null}.
+ */
+ public SortedSetView(SortedSetService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public abstract E first();
+
+ @Override
+ public SortedSetService<E> headSet(E toElement) {
+ return new SubSortedSetImpl<E>(this, null, toElement);
+ }
+
+ @Override
+ public abstract E last();
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedSetService<E>[] split(int n, boolean updateable) {
+ return new SortedSetService[] { this }; // Split not supported.
+ }
+
+ @Override
+ public SortedSetService<E> subSet(E fromElement, E toElement) {
+ return new SubSortedSetImpl<E>(this, fromElement, toElement);
+ }
+
+ @Override
+ public SortedSetService<E> tailSet(E fromElement) {
+ return new SubSortedSetImpl<E>(this, fromElement, null);
+ }
+
+ @Override
+ protected SortedSetService<E> target() {
+ return (SortedSetService<E>) super.target();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SubSortedSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SubSortedSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SubSortedSetImpl.java
new file mode 100644
index 0000000..d44ca86
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/SubSortedSetImpl.java
@@ -0,0 +1,144 @@
+/*
+ * 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.internal.set.sorted;
+
+import javolution.util.function.Equality;
+import javolution.util.service.CollectionService;
+import javolution.util.service.SortedSetService;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * A view over a portion of a sorted set.
+ */
+public class SubSortedSetImpl<E> extends SortedSetView<E> {
+
+ /** Peeking ahead iterator. */
+ private class IteratorImpl implements Iterator<E> {
+
+ private boolean ahead;
+ private final Equality<? super E> cmp = comparator();
+ private E next;
+ private final Iterator<E> targetIterator = target().iterator();
+
+ @Override
+ public boolean hasNext() {
+ if (ahead) return true;
+ while (targetIterator.hasNext()) {
+ next = targetIterator.next();
+ if ((from != null) && (cmp.compare(next, from) < 0)) continue;
+ if ((to != null) && (cmp.compare(next, to) >= 0)) break;
+ ahead = true;
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public E next() {
+ hasNext(); // Moves ahead.
+ ahead = false;
+ return next;
+ }
+
+ @Override
+ public void remove() {
+ targetIterator.remove();
+ }
+ }
+
+ private static final long serialVersionUID = 0x600L; // Version.
+ private final E from; // Can be null.
+ private final E to; // Can be null.
+
+ public SubSortedSetImpl(SortedSetService<E> target, E from, E to) {
+ super(target);
+ if ((from != null) && (to != null)
+ && (comparator().compare(from, to) > 0)) throw new IllegalArgumentException(
+ "from: " + from + ", to: " + to); // As per SortedSet contract.
+ this.from = from;
+ this.to = to;
+ }
+
+ @Override
+ public boolean add(E e) {
+ Equality<? super E> cmp = comparator();
+ if ((from != null) && (cmp.compare(e, from) < 0)) throw new IllegalArgumentException(
+ "Element: " + e + " outside of this sub-set bounds");
+ if ((to != null) && (cmp.compare(e, to) >= 0)) throw new IllegalArgumentException(
+ "Element: " + e + " outside of this sub-set bounds");
+ return target().add(e);
+ }
+
+ @Override
+ public Equality<? super E> comparator() {
+ return ((CollectionService<E>)target()).comparator();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean contains(Object obj) {
+ Equality<? super E> cmp = comparator();
+ if ((from != null) && (cmp.compare((E) obj, from) < 0)) return false;
+ if ((to != null) && (cmp.compare((E) obj, to) >= 0)) return false;
+ return target().contains(obj);
+ }
+
+ @Override
+ public E first() {
+ if (from == null) return target().first();
+ Iterator<E> it = iterator();
+ if (!it.hasNext()) throw new NoSuchElementException();
+ return it.next();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return iterator().hasNext();
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return new IteratorImpl();
+ }
+
+ @Override
+ public E last() {
+ if (to == null) return target().last();
+ Iterator<E> it = iterator();
+ if (!it.hasNext()) throw new NoSuchElementException();
+ E last = it.next();
+ while (it.hasNext()) {
+ last = it.next();
+ }
+ return last;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean remove(Object obj) {
+ Equality<? super E> cmp = comparator();
+ if ((from != null) && (cmp.compare((E) obj, from) < 0)) return false;
+ if ((to != null) && (cmp.compare((E) obj, to) >= 0)) return false;
+ return target().remove(obj);
+ }
+
+ @Override
+ public int size() { // Unfortunately, no choice other than counting.
+ int count = 0;
+ Iterator<E> it = iterator();
+ while (it.hasNext()) {
+ count++;
+ it.next();
+ }
+ return count;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/UnmodifiableSortedSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/UnmodifiableSortedSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/UnmodifiableSortedSetImpl.java
new file mode 100644
index 0000000..028e3ed
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/UnmodifiableSortedSetImpl.java
@@ -0,0 +1,67 @@
+/*
+ * 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.internal.set.sorted;
+
+import javolution.util.internal.set.UnmodifiableSetImpl;
+import javolution.util.service.SetService;
+import javolution.util.service.SortedSetService;
+
+/**
+ * An unmodifiable view over a set.
+ */
+public class UnmodifiableSortedSetImpl<E> extends UnmodifiableSetImpl<E>
+ implements SortedSetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public UnmodifiableSortedSetImpl(SetService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public E first() {
+ return target().first();
+ }
+
+ @Override
+ public SortedSetService<E> headSet(E toElement) {
+ return new SubSortedSetImpl<E>(this, null, toElement);
+ }
+
+ @Override
+ public E last() {
+ return target().last();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedSetService<E>[] split(int n, boolean updateable) {
+ SortedSetService<E>[] subTargets = target().split(n, updateable);
+ SortedSetService<E>[] result = new SortedSetService[subTargets.length];
+ for (int i = 0; i < subTargets.length; i++) {
+ result[i] = new UnmodifiableSortedSetImpl<E>(subTargets[i]);
+ }
+ return result;
+ }
+
+ @Override
+ public SortedSetService<E> subSet(E fromElement, E toElement) {
+ return new SubSortedSetImpl<E>(this, fromElement, toElement);
+ }
+
+ @Override
+ public SortedSetService<E> tailSet(E fromElement) {
+ return new SubSortedSetImpl<E>(this, fromElement, null);
+ }
+
+ @Override
+ protected SortedSetService<E> target() {
+ return (SortedSetService<E>) super.target();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/AtomicTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/AtomicTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/AtomicTableImpl.java
new file mode 100644
index 0000000..4ed8926
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/AtomicTableImpl.java
@@ -0,0 +1,236 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.internal.collection.AtomicCollectionImpl;
+import javolution.util.service.TableService;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.ListIterator;
+
+/**
+ * An atomic view over a table.
+ */
+public class AtomicTableImpl<E> extends AtomicCollectionImpl<E> implements
+ TableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public AtomicTableImpl(TableService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public synchronized void add(int index, E element) {
+ target().add(index, element);
+ if (!updateInProgress()) immutable = cloneTarget();
+ }
+
+ @Override
+ public synchronized boolean addAll(int index, Collection<? extends E> c) {
+ boolean changed = target().addAll(index, c);
+ if (changed && !updateInProgress()) immutable = cloneTarget();
+ return changed;
+ }
+
+ @Override
+ public synchronized void addFirst(E element) {
+ target().addFirst(element);
+ if (!updateInProgress()) immutable = cloneTarget();
+ }
+
+ @Override
+ public synchronized void addLast(E element) {
+ target().addLast(element);
+ if (!updateInProgress()) immutable = cloneTarget();
+ }
+
+ @Override
+ public Iterator<E> descendingIterator() {
+ return new ReversedTableImpl<E>(this).iterator();
+ }
+
+ @Override
+ public E element() {
+ return getFirst();
+ }
+
+ @Override
+ public E get(int index) {
+ return targetView().get(index);
+ }
+
+ @Override
+ public E getFirst() {
+ return targetView().getFirst();
+ }
+
+ @Override
+ public E getLast() {
+ return targetView().getLast();
+ }
+
+ @Override
+ public int indexOf(Object element) {
+ return targetView().indexOf(element);
+ }
+
+ @Override
+ public ListIterator<E> iterator() {
+ return listIterator(0);
+ }
+
+ @Override
+ public int lastIndexOf(Object element) {
+ return targetView().lastIndexOf(element);
+ }
+
+ @Override
+ public ListIterator<E> listIterator() {
+ return listIterator(0);
+ }
+
+ @Override
+ public ListIterator<E> listIterator(int index) {
+ return new TableIteratorImpl<E>(this, index); // Iterator view on this.
+ }
+
+ @Override
+ public boolean offer(E e) {
+ return offerLast(e);
+ }
+
+ @Override
+ public synchronized boolean offerFirst(E e) {
+ boolean changed = target().offerFirst(e);
+ if (changed && !updateInProgress()) immutable = cloneTarget();
+ return changed;
+ }
+
+ @Override
+ public synchronized boolean offerLast(E e) {
+ boolean changed = target().offerLast(e);
+ if (changed && !updateInProgress()) immutable = cloneTarget();
+ return changed;
+ }
+
+ @Override
+ public E peek() {
+ return peekFirst();
+ }
+
+ @Override
+ public E peekFirst() {
+ return targetView().peekFirst();
+ }
+
+ @Override
+ public E peekLast() {
+ return targetView().peekLast();
+ }
+
+ @Override
+ public E poll() {
+ return pollFirst();
+ }
+
+ @Override
+ public synchronized E pollFirst() {
+ E e = target().pollFirst();
+ if ((e != null) && !updateInProgress()) immutable = cloneTarget();
+ return e;
+ }
+
+ @Override
+ public synchronized E pollLast() {
+ E e = target().pollLast();
+ if ((e != null) && !updateInProgress()) immutable = cloneTarget();
+ return e;
+ }
+
+ @Override
+ public E pop() {
+ return removeFirst();
+ }
+
+ @Override
+ public void push(E e) {
+ addFirst(e);
+ }
+
+ @Override
+ public E remove() {
+ return removeFirst();
+ }
+
+ @Override
+ public synchronized E remove(int index) {
+ E e = target().remove(index);
+ if (!updateInProgress()) immutable = cloneTarget();
+ return e;
+ }
+
+ @Override
+ public synchronized E removeFirst() {
+ E e = target().removeFirst();
+ if (!updateInProgress()) immutable = cloneTarget();
+ return e;
+ }
+
+ @Override
+ public synchronized boolean removeFirstOccurrence(Object o) {
+ boolean changed = target().removeFirstOccurrence(o);
+ if (changed && !updateInProgress()) immutable = cloneTarget();
+ return changed;
+ }
+
+ @Override
+ public synchronized E removeLast() {
+ E e = target().removeLast();
+ if (!updateInProgress()) immutable = cloneTarget();
+ return e;
+ }
+
+ @Override
+ public synchronized boolean removeLastOccurrence(Object o) {
+ boolean changed = target().removeLastOccurrence(o);
+ if (changed && !updateInProgress()) immutable = cloneTarget();
+ return changed;
+ }
+
+ @Override
+ public synchronized E set(int index, E element) {
+ E e = target().set(index, element);
+ if (!updateInProgress()) immutable = cloneTarget();
+ return e;
+ }
+
+ @Override
+ public TableService<E>[] split(int n, boolean updateable) {
+ return SubTableImpl.splitOf(this, n, false); // Sub-views over this.
+ }
+
+ @Override
+ public TableService<E> subList(int fromIndex, int toIndex) {
+ return new SubTableImpl<E>(this, fromIndex, toIndex); // View on this.
+ }
+
+ /** Returns the actual target */
+ @Override
+ protected TableService<E> target() {
+ return (TableService<E>) super.target();
+ }
+
+ @Override
+ protected TableService<E> targetView() {
+ return (TableService<E>) super.targetView();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/FastTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/FastTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/FastTableImpl.java
new file mode 100644
index 0000000..dc92d09
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/FastTableImpl.java
@@ -0,0 +1,210 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.function.Equality;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * The default {@link javolution.util.FastTable FastTable} implementation
+ * based on {@link FractalTableImpl fractal tables}. The memory footprint
+ * is minimal when the table is cleared.
+ */
+public class FastTableImpl<E> extends TableView<E> {
+
+ /** Internal iterator faster than generic TableIteratorImpl. */
+ private class IteratorImpl implements Iterator<E> {
+ private int currentIndex = -1;
+ private int nextIndex;
+
+ @Override
+ public boolean hasNext() {
+ return nextIndex < size;
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ public E next() {
+ if (nextIndex >= size) throw new NoSuchElementException();
+ currentIndex = nextIndex++;
+ return (E) fractal.get(currentIndex);
+ }
+
+ @Override
+ public void remove() {
+ if (currentIndex < 0) throw new IllegalStateException();
+ FastTableImpl.this.remove(currentIndex);
+ nextIndex--;
+ currentIndex = -1;
+ }
+ }
+
+ private static final long serialVersionUID = 0x600L; // Version.
+ private transient int capacity; // Actual memory allocated is usually far less than capacity since inner fractal tables can be null.
+ private final Equality<? super E> comparator;
+ private transient FractalTableImpl fractal; // Null if empty (capacity 0)
+ private transient int size;
+
+ public FastTableImpl(Equality<? super E> comparator) {
+ super(null); // Root class.
+ this.comparator = comparator;
+ }
+
+ @Override
+ public boolean add(E element) {
+ addLast(element);
+ return true;
+ }
+
+ @Override
+ public void add(int index, E element) {
+ if ((index < 0) || (index > size)) indexError(index);
+ checkUpsize();
+ if (index >= (size >> 1)) {
+ fractal.shiftRight(element, index, size - index);
+ } else {
+ fractal.shiftLeft(element, index - 1, index);
+ fractal.offset--;
+ }
+ size++;
+ }
+
+ @Override
+ public void addFirst(E element) {
+ checkUpsize();
+ fractal.offset--;
+ fractal.set(0, element);
+ size++;
+ }
+
+ @Override
+ public void addLast(E element) {
+ checkUpsize();
+ fractal.set(size++, element);
+ }
+
+ @Override
+ public void clear() {
+ fractal = null;
+ capacity = 0;
+ size = 0;
+ }
+
+ @Override
+ public FastTableImpl<E> clone() { // Make a copy.
+ FastTableImpl<E> copy = new FastTableImpl<E>(comparator());
+ copy.addAll(this);
+ return copy;
+ }
+
+ @Override
+ public Equality<? super E> comparator() {
+ return comparator;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public E get(int index) {
+ if ((index < 0) && (index >= size)) indexError(index);
+ return (E) fractal.get(index);
+ }
+
+ @Override
+ public E getFirst() {
+ if (size == 0) emptyError();
+ return get(0);
+ }
+
+ @Override
+ public E getLast() {
+ if (size == 0) emptyError();
+ return get(size - 1);
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return new IteratorImpl();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public E remove(int index) {
+ if ((index < 0) || (index >= size)) indexError(index);
+ E removed = (E) fractal.get(index);
+ if (index >= (size >> 1)) {
+ fractal.shiftLeft(null, size - 1, size - index - 1);
+ } else {
+ fractal.shiftRight(null, 0, index);
+ fractal.offset++;
+ }
+ size--;
+ return removed;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public E removeFirst() {
+ if (size == 0) emptyError();
+ E first = (E) fractal.set(0, null);
+ fractal.offset++;
+ size--;
+ return first;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public E removeLast() {
+ if (size == 0) emptyError();
+ E last = (E) fractal.set(--size, null);
+ return last;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public E set(int index, E element) {
+ if ((index < 0) && (index >= size)) indexError(index);
+ return (E) fractal.set(index, element);
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ private void checkUpsize() {
+ if (size >= capacity) upsize();
+ }
+
+ /** For serialization support */
+ @SuppressWarnings("unchecked")
+ private void readObject(java.io.ObjectInputStream s)
+ throws java.io.IOException, ClassNotFoundException {
+ s.defaultReadObject(); // Deserialize comparator.
+ int n = s.readInt();
+ for (int i = 0; i < n; i++)
+ addLast((E) s.readObject());
+ }
+
+ private void upsize() {
+ fractal = (fractal == null) ? new FractalTableImpl() : fractal.upsize();
+ capacity = fractal.capacity();
+ }
+
+ /** For serialization support */
+ private void writeObject(java.io.ObjectOutputStream s)
+ throws java.io.IOException {
+ s.defaultWriteObject(); // Serialize comparator.
+ s.writeInt(size);
+ for (int i = 0; i < size; i++)
+ s.writeObject(fractal.get(i));
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/FractalTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/FractalTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/FractalTableImpl.java
new file mode 100644
index 0000000..66f7782
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/FractalTableImpl.java
@@ -0,0 +1,172 @@
+/*
+ * 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.internal.table;
+
+import javolution.lang.MathLib;
+
+/**
+ * A fractal-based table with fast insertion/deletion capabilities regardless
+ * of the collection size. It is based on a fractal structure with self-similar
+ * patterns at any scale (large tables have the same structure as smaller tables
+ * which have similar structure as even smaller tables and so on).
+ */
+final class FractalTableImpl {
+
+ static final int BASE_CAPACITY_MIN = 16;
+ static final int SHIFT = 8;
+ private static final int BASE_CAPACITY_MAX = 1 << SHIFT;
+
+ /** Offset value, it is the index of the first element (modulo data.length). */
+ int offset;
+
+ /** An array of data elements or fractal tables (recursion).
+ Data length varies from 2 to BASE_CAPACITY_MAX */
+ private Object[] data;
+
+ /** The index shift, zero if base table. */
+ private final int shift;
+
+ public FractalTableImpl() {
+ this.shift = 0;
+ data = new Object[BASE_CAPACITY_MIN];
+ }
+
+ public FractalTableImpl(int shift) {
+ this.shift = shift;
+ data = new Object[2];
+ }
+
+ public FractalTableImpl(int shift, Object[] data, int offset) {
+ this.shift = shift;
+ this.data = data;
+ this.offset = offset;
+ }
+
+ public int capacity() {
+ // Reports lower capacity to ensure that there is no fractal holding
+ // wrapping data (head and tail in the same fractal).
+ return (data.length - 1) << shift;
+ }
+
+ public Object get(int index) {
+ Object fractal = data[((index + offset) >> shift) & (data.length - 1)];
+ return (shift == 0) ? fractal : ((FractalTableImpl) fractal).get(index
+ + offset);
+ }
+
+ public Object set(int index, Object element) {
+ int i = ((index + offset) >> shift) & (data.length - 1);
+ if (shift != 0) return F(i).set(index + offset, element);
+ Object previous = data[i];
+ data[i] = element;
+ return previous;
+ }
+
+ /** Shifts the specified elements(]last - length, last] modulo capacity)
+ one position to the left. No shift if length (modulo capacity) is zero. */
+ public void shiftLeft(Object inserted, int last, int length) {
+ int mask = (data.length << shift) - 1;
+ int tail = (last + offset) & mask;
+ int head = (last + offset - length) & mask;
+ if (shift == 0) {
+ int n = tail - head;
+ if (head > tail) { // Wrapping
+ System.arraycopy(data, head + 1, data, head, mask - head);
+ data[mask] = data[0];
+ n = tail;
+ }
+ System.arraycopy(data, tail - n + 1, data, tail - n, n);
+ data[tail] = inserted;
+ } else if ((head <= tail) && ((head >> shift) == (tail >> shift))) { // Shift local to inner table.
+ F(head >> shift).shiftLeft(inserted, tail, length); // (no wrapping).
+ } else {
+ int low = head >> shift;
+ int high = (low != data.length - 1) ? low + 1 : 0;
+ F(low).shiftLeft(F(high).get(0), -1, mask - head);
+ while (high != (tail >> shift)) {
+ low = high;
+ high = (low != data.length - 1) ? low + 1 : 0;
+ F(low).offset++; // Full shift left.
+ F(low).set(-1, F(high).get(0));
+ }
+ F(high).shiftLeft(inserted, tail, tail);
+ }
+ }
+
+ /** Shifts the specified element ([first, first + length[ modulo capacity)
+ one position to the right. No shift if length (modulo capacity) is zero. */
+ public void shiftRight(Object inserted, int first, int length) {
+ int mask = (data.length << shift) - 1;
+ int head = (first + offset) & mask;
+ int tail = (first + offset + length) & mask;
+ if (shift == 0) {
+ int n = tail - head;
+ if (head > tail) { // Wrapping
+ System.arraycopy(data, 0, data, 1, tail);
+ data[0] = data[mask];
+ n = mask - head;
+ }
+ System.arraycopy(data, head, data, head + 1, n);
+ data[head] = inserted;
+ } else if ((head <= tail) && ((head >> shift) == (tail >> shift))) { // Shift local to inner table.
+ F(head >> shift).shiftRight(inserted, head, length); // (no wrapping).
+ } else {
+ int high = tail >> shift;
+ int low = (high != 0) ? high - 1 : data.length - 1;
+ F(high).shiftRight(F(low).get(-1), 0, tail);
+ while (low != (head >> shift)) {
+ high = low;
+ low = (high != 0) ? high - 1 : data.length - 1;
+ F(high).offset--; // Full shift right.
+ F(high).set(0, F(low).get(-1));
+ }
+ F(low).shiftRight(inserted, head, mask - head);
+ }
+ }
+
+ public FractalTableImpl upsize() {
+ if (data.length >= BASE_CAPACITY_MAX) { // Creates outer fractal.
+ FractalTableImpl table = new FractalTableImpl(shift + SHIFT);
+ copyTo(table.F(0));
+ return table;
+ } else {
+ FractalTableImpl table = new FractalTableImpl(shift,
+ new Object[data.length << 1], 0);
+ copyTo(table);
+ return table;
+ }
+ }
+
+ private FractalTableImpl allocate(int i) {
+ FractalTableImpl fractal = new FractalTableImpl(shift - SHIFT,
+ new Object[1 << SHIFT], 0);
+ data[i] = fractal;
+ return fractal;
+ }
+
+ // Copy to the specified table.
+ private void copyTo(FractalTableImpl that) {
+ int n = MathLib.min(this.data.length, that.data.length);
+ offset &= (data.length << shift) - 1; // Makes it positive.
+ int o = offset >> shift;
+ if ((o + n) > data.length) { // Wrapping.
+ int w = (o + n) - data.length;
+ n -= w;
+ System.arraycopy(data, 0, that.data, n, w);
+ }
+ System.arraycopy(data, o, that.data, 0, n);
+ that.offset = offset - (o << shift);
+ }
+
+ private FractalTableImpl F(int i) {
+ FractalTableImpl table = (FractalTableImpl) data[i];
+ return (table != null) ? table : allocate(i);
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/QuickSort.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/QuickSort.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/QuickSort.java
new file mode 100644
index 0000000..4bfd9f8
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/QuickSort.java
@@ -0,0 +1,75 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.service.TableService;
+
+import java.util.Comparator;
+
+/**
+ * A quick sort utility class.
+ * From Wikipedia Quick Sort - http://en.wikipedia.org/wiki/Quicksort
+ */
+public class QuickSort<E> {
+
+ private final Comparator<? super E> comparator;
+ private final TableService<E> table;
+
+ public QuickSort(TableService<E> table, Comparator<? super E> comparator) {
+ this.table = table;
+ this.comparator = comparator;
+ }
+
+ public void sort() {
+ int size = table.size();
+ if (size > 0) quicksort(0, table.size() - 1);
+ }
+
+ public void sort(int first, int last) {
+ if (first < last) {
+ int pivIndex = partition(first, last);
+ sort(first, (pivIndex - 1));
+ sort((pivIndex + 1), last);
+ }
+ }
+
+ // From Wikipedia Quick Sort - http://en.wikipedia.org/wiki/Quicksort
+ //
+ void quicksort(int first, int last) {
+ int pivIndex = 0;
+ if (first < last) {
+ pivIndex = partition(first, last);
+ quicksort(first, (pivIndex - 1));
+ quicksort((pivIndex + 1), last);
+ }
+ }
+
+ private int partition(int f, int l) {
+ int up, down;
+ E piv = table.get(f);
+ up = f;
+ down = l;
+ do {
+ while (comparator.compare(table.get(up), piv) <= 0 && up < l) {
+ up++;
+ }
+ while (comparator.compare(table.get(down), piv) > 0 && down > f) {
+ down--;
+ }
+ if (up < down) { // Swaps.
+ E temp = table.get(up);
+ table.set(up, table.get(down));
+ table.set(down, temp);
+ }
+ } while (down > up);
+ table.set(f, table.get(down));
+ table.set(down, piv);
+ return down;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/ReversedTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/ReversedTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/ReversedTableImpl.java
new file mode 100644
index 0000000..3e2de7d
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/ReversedTableImpl.java
@@ -0,0 +1,76 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.function.Equality;
+import javolution.util.service.TableService;
+
+/**
+ * A reverse view over a table.
+ */
+public class ReversedTableImpl<E> extends TableView<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public ReversedTableImpl(TableService<E> that) {
+ super(that);
+ }
+
+ @Override
+ public boolean add(E e) {
+ target().addFirst(e);
+ return true;
+ }
+
+ @Override
+ public void add(int index, E element) {
+ target().add(size() - index - 1, element);
+ }
+
+ @Override
+ public void clear() {
+ target().clear();
+ }
+
+ @Override
+ public Equality<? super E> comparator() {
+ return target().comparator();
+ }
+
+ @Override
+ public E get(int index) {
+ return target().get(size() - index - 1);
+ }
+
+ @Override
+ public int indexOf(Object o) {
+ return size() - target().lastIndexOf(o) - 1;
+ }
+
+ @Override
+ public int lastIndexOf(Object o) {
+ return size() - target().indexOf(o) - 1;
+ }
+
+ @Override
+ public E remove(int index) {
+ return target().remove(size() - index - 1);
+ }
+
+ @Override
+ public E set(int index, E element) {
+ return target().set(size() - index - 1, element);
+ }
+
+ @Override
+ public int size() {
+ return target().size();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/SharedTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/SharedTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/SharedTableImpl.java
new file mode 100644
index 0000000..4f77098
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/SharedTableImpl.java
@@ -0,0 +1,315 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.internal.ReadWriteLockImpl;
+import javolution.util.internal.collection.SharedCollectionImpl;
+import javolution.util.service.TableService;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.ListIterator;
+
+/**
+ * A shared view over a table allowing concurrent access and sequential updates.
+ */
+public class SharedTableImpl<E> extends SharedCollectionImpl<E> implements
+ TableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public SharedTableImpl(TableService<E> target) {
+ super(target);
+ }
+
+ public SharedTableImpl(TableService<E> target, ReadWriteLockImpl lock) {
+ super(target, lock);
+ }
+
+ @Override
+ public void add(int index, E element) {
+ lock.writeLock.lock();
+ try {
+ target().add(index, element);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public boolean addAll(int index, Collection<? extends E> c) {
+ lock.writeLock.lock();
+ try {
+ return target().addAll(index, c);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public void addFirst(E element) {
+ lock.writeLock.lock();
+ try {
+ target().addFirst(element);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public void addLast(E element) {
+ lock.writeLock.lock();
+ try {
+ target().addLast(element);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public Iterator<E> descendingIterator() {
+ return new ReversedTableImpl<E>(this).iterator(); // View on this.
+ }
+
+ @Override
+ public E element() {
+ return getFirst();
+ }
+
+ @Override
+ public E get(int index) {
+ lock.readLock.lock();
+ try {
+ return target().get(index);
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public E getFirst() {
+ lock.readLock.lock();
+ try {
+ return target().getFirst();
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public E getLast() {
+ lock.readLock.lock();
+ try {
+ return target().getLast();
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public int indexOf(Object element) {
+ lock.readLock.lock();
+ try {
+ return target().indexOf(element);
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public ListIterator<E> iterator() {
+ return target().listIterator(0);
+ }
+
+ @Override
+ public int lastIndexOf(Object element) {
+ lock.readLock.lock();
+ try {
+ return target().lastIndexOf(element);
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public ListIterator<E> listIterator() {
+ return target().listIterator(0);
+ }
+
+ @Override
+ public ListIterator<E> listIterator(int index) {
+ return new TableIteratorImpl<E>(this, index); // View on this.
+ }
+
+ @Override
+ public boolean offer(E e) {
+ return offerLast(e);
+ }
+
+ @Override
+ public boolean offerFirst(E e) {
+ lock.writeLock.lock();
+ try {
+ return target().offerFirst(e);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public boolean offerLast(E e) {
+ lock.writeLock.lock();
+ try {
+ return target().offerLast(e);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public E peek() {
+ return peekFirst();
+ }
+
+ @Override
+ public E peekFirst() {
+ lock.readLock.lock();
+ try {
+ return target().peekFirst();
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public E peekLast() {
+ lock.readLock.lock();
+ try {
+ return target().peekLast();
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public E poll() {
+ return pollFirst();
+ }
+
+ @Override
+ public E pollFirst() {
+ lock.writeLock.lock();
+ try {
+ return target().pollFirst();
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public E pollLast() {
+ lock.writeLock.lock();
+ try {
+ return target().pollLast();
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public E pop() {
+ return removeFirst();
+ }
+
+ @Override
+ public void push(E e) {
+ addFirst(e);
+ }
+
+ @Override
+ public E remove() {
+ return removeFirst();
+ }
+
+ @Override
+ public E remove(int index) {
+ lock.writeLock.lock();
+ try {
+ return target().remove(index);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public E removeFirst() {
+ lock.writeLock.lock();
+ try {
+ return target().removeFirst();
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public boolean removeFirstOccurrence(Object o) {
+ lock.writeLock.lock();
+ try {
+ return target().removeFirstOccurrence(o);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public E removeLast() {
+ lock.writeLock.lock();
+ try {
+ return target().removeLast();
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public boolean removeLastOccurrence(Object o) {
+ lock.writeLock.lock();
+ try {
+ return target().removeLastOccurrence(o);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public E set(int index, E element) {
+ lock.writeLock.lock();
+ try {
+ return target().set(index, element);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+ @Override
+ public TableService<E>[] split(int n, boolean updateable) {
+ return SubTableImpl.splitOf(this, n, false); // Sub-views over this.
+ }
+
+ @Override
+ public TableService<E> subList(int fromIndex, int toIndex) {
+ return new SubTableImpl<E>(this, fromIndex, toIndex); // View on this.
+ }
+
+ /** Returns the actual target */
+ @Override
+ protected TableService<E> target() {
+ return (TableService<E>) super.target();
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/SubTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/SubTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/SubTableImpl.java
new file mode 100644
index 0000000..682a900
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/SubTableImpl.java
@@ -0,0 +1,101 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.function.Equality;
+import javolution.util.service.TableService;
+
+/**
+ * A view over a portion of a table.
+ */
+public class SubTableImpl<E> extends TableView<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /** Splits the specified table. */
+ @SuppressWarnings("unchecked")
+ public static <E> TableService<E>[] splitOf(TableService<E> table,
+ int n, boolean updateable) {
+ if (updateable) table = new SharedTableImpl<E>(table);
+ if (n < 1) throw new IllegalArgumentException("Invalid argument n: "
+ + n);
+ TableService<E>[] subTables = new TableService[n];
+ int minSize = table.size() / n;
+ int start = 0;
+ for (int i = 0; i < n - 1; i++) {
+ subTables[i] = new SubTableImpl<E>(table, start, start + minSize);
+ start += minSize;
+ }
+ subTables[n - 1] = new SubTableImpl<E>(table, start, table.size());
+ return subTables;
+ }
+
+ protected final int fromIndex;
+ protected int toIndex;
+
+ public SubTableImpl(TableService<E> target, int from, int to) {
+ super(target);
+ if ((from < 0) || (to > target.size()) || (from > to)) throw new IndexOutOfBoundsException(
+ "fromIndex: " + from + ", toIndex: " + to + ", size(): "
+ + target.size()); // As per List.subList contract.
+ fromIndex = from;
+ toIndex = to;
+ }
+
+ @Override
+ public boolean add(E element) {
+ target().add(toIndex++, element);
+ return true;
+ }
+
+ @Override
+ public void add(int index, E element) {
+ if ((index < 0) && (index > size())) indexError(index);
+ target().add(index + fromIndex, element);
+ toIndex++;
+ }
+
+ @Override
+ public void clear() {
+ for (int i = toIndex - 1; i >= fromIndex; i--) { // Better to do it from the end (less shift).
+ target().remove(i);
+ }
+ toIndex = fromIndex;
+ }
+
+ @Override
+ public Equality<? super E> comparator() {
+ return target().comparator();
+ }
+
+ @Override
+ public E get(int index) {
+ if ((index < 0) && (index >= size())) indexError(index);
+ return target().get(index + fromIndex);
+ }
+
+ @Override
+ public E remove(int index) {
+ if ((index < 0) && (index >= size())) indexError(index);
+ toIndex--;
+ return target().remove(index + fromIndex);
+ }
+
+ @Override
+ public E set(int index, E element) {
+ if ((index < 0) && (index >= size())) indexError(index);
+ return target().set(index + fromIndex, element);
+ }
+
+ @Override
+ public int size() {
+ return toIndex - fromIndex;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/TableIteratorImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/TableIteratorImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/TableIteratorImpl.java
new file mode 100644
index 0000000..b280181
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/TableIteratorImpl.java
@@ -0,0 +1,93 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.service.TableService;
+
+import java.util.ListIterator;
+import java.util.NoSuchElementException;
+
+/**
+ * A generic iterator over a table.
+ */
+public final class TableIteratorImpl<E> implements ListIterator<E> {
+
+ private int currentIndex = -1;
+ private int end;
+ private int nextIndex;
+ private final TableService<E> table;
+
+ public TableIteratorImpl(TableService<E> table, int index) {
+ this.table = table;
+ this.nextIndex = index;
+ this.end = table.size();
+ }
+
+ @Override
+ public void add(E e) {
+ table.add(nextIndex++, e);
+ end++;
+ currentIndex = -1;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return (nextIndex < end);
+ }
+
+ @Override
+ public boolean hasPrevious() {
+ return nextIndex > 0;
+ }
+
+ @Override
+ public E next() {
+ if (nextIndex >= end) throw new NoSuchElementException();
+ currentIndex = nextIndex++;
+ return table.get(currentIndex);
+ }
+
+ @Override
+ public int nextIndex() {
+ return nextIndex;
+ }
+
+ @Override
+ public E previous() {
+ if (nextIndex <= 0) throw new NoSuchElementException();
+ currentIndex = --nextIndex;
+ return table.get(currentIndex);
+ }
+
+ @Override
+ public int previousIndex() {
+ return nextIndex - 1;
+ }
+
+ @Override
+ public void remove() {
+ if (currentIndex < 0) throw new IllegalStateException();
+ table.remove(currentIndex);
+ end--;
+ if (currentIndex < nextIndex) {
+ nextIndex--;
+ }
+ currentIndex = -1;
+ }
+
+ @Override
+ public void set(E e) {
+ if (currentIndex >= 0) {
+ table.set(currentIndex, e);
+ } else {
+ throw new IllegalStateException();
+ }
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/TableView.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/TableView.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/TableView.java
new file mode 100644
index 0000000..e377755
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/TableView.java
@@ -0,0 +1,259 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.function.Equality;
+import javolution.util.internal.collection.CollectionView;
+import javolution.util.service.TableService;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.ListIterator;
+import java.util.NoSuchElementException;
+
+/**
+ * Table view implementation; can be used as root class for implementations
+ * if target is {@code null}.
+ */
+public abstract class TableView<E> extends CollectionView<E> implements TableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * The view constructor or root class constructor if target is {@code null}.
+ */
+ public TableView(TableService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public abstract void add(int index, E element);
+
+ @Override
+ public boolean addAll(int index, Collection<? extends E> c) {
+ return subList(index, index).addAll(c);
+ }
+
+ @Override
+ public void addFirst(E element) {
+ add(0, element);
+ }
+
+ @Override
+ public void addLast(E element) {
+ add(size(), element);
+ }
+
+ @Override
+ public abstract void clear();
+
+ @Override
+ public final boolean contains(Object o) {
+ return indexOf(o) >= 0;
+ }
+
+ @Override
+ public Iterator<E> descendingIterator() {
+ return new ReversedTableImpl<E>(this).iterator();
+ }
+
+ @Override
+ public final E element() {
+ return getFirst();
+ }
+
+ @Override
+ public abstract E get(int index);
+
+ @Override
+ public E getFirst() {
+ if (size() == 0) emptyError();
+ return get(0);
+ }
+
+ @Override
+ public E getLast() {
+ if (size() == 0) emptyError();
+ return get(size() - 1);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public int indexOf(Object o) {
+ Equality<Object> cmp = (Equality<Object>) this.comparator();
+ for (int i = 0, n = size(); i < n; i++) {
+ if (cmp.areEqual(o, get(i))) return i;
+ }
+ return -1;
+ }
+
+ @Override
+ public final boolean isEmpty() {
+ return size() == 0;
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return listIterator(0);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public int lastIndexOf(Object o) {
+ Equality<Object> cmp = (Equality<Object>) this.comparator();
+ for (int i = size() - 1; i >= 0; i--) {
+ if (cmp.areEqual(o, get(i))) return i;
+ }
+ return -1;
+ }
+
+ @Override
+ public final ListIterator<E> listIterator() {
+ return listIterator(0);
+ }
+
+ @Override
+ public ListIterator<E> listIterator(int index) {
+ return new TableIteratorImpl<E>(this, index);
+ }
+
+ @Override
+ public final boolean offer(E e) {
+ return offerLast(e);
+ }
+
+ @Override
+ public final boolean offerFirst(E e) {
+ addFirst(e);
+ return true;
+ }
+
+ @Override
+ public final boolean offerLast(E e) {
+ addLast(e);
+ return true;
+ }
+
+ @Override
+ public final E peek() {
+ return peekFirst();
+ }
+
+ @Override
+ public E peekFirst() {
+ return (size() == 0) ? null : getFirst();
+ }
+
+ @Override
+ public E peekLast() {
+ return (size() == 0) ? null : getLast();
+ }
+
+ @Override
+ public final E poll() {
+ return pollFirst();
+ }
+
+ @Override
+ public E pollFirst() {
+ return (size() == 0) ? null : removeFirst();
+ }
+
+ @Override
+ public E pollLast() {
+ return (size() == 0) ? null : removeLast();
+ }
+
+ @Override
+ public final E pop() {
+ return removeFirst();
+ }
+
+ @Override
+ public final void push(E e) {
+ addFirst(e);
+ }
+
+ @Override
+ public final E remove() {
+ return removeFirst();
+ }
+
+ @Override
+ public abstract E remove(int index);
+
+ @Override
+ public final boolean remove(Object o) {
+ int i = indexOf(o);
+ if (i < 0) return false;
+ remove(i);
+ return true;
+ }
+
+ @Override
+ public E removeFirst() {
+ if (size() == 0) emptyError();
+ return remove(0);
+ }
+
+ @Override
+ public boolean removeFirstOccurrence(Object o) {
+ int i = indexOf(o);
+ if (i < 0) return false;
+ remove(i);
+ return true;
+ }
+
+ @Override
+ public E removeLast() {
+ if (size() == 0) emptyError();
+ return remove(size() - 1);
+ }
+
+ @Override
+ public boolean removeLastOccurrence(Object o) {
+ int i = lastIndexOf(o);
+ if (i < 0) return false;
+ remove(i);
+ return true;
+ }
+
+ @Override
+ public abstract E set(int index, E element);
+
+ @Override
+ public abstract int size();
+
+ @Override
+ public TableService<E>[] split(int n, boolean updateable) {
+ return SubTableImpl.splitOf(this, n, updateable); // Sub-views over this.
+ }
+
+ @Override
+ public TableService<E> subList(int fromIndex, int toIndex) {
+ return new SubTableImpl<E>(this, fromIndex, toIndex);
+ }
+
+ /** Throws NoSuchElementException */
+ protected void emptyError() {
+ throw new NoSuchElementException("Empty Table");
+ }
+
+ /** Throws IndexOutOfBoundsException */
+ protected void indexError(int index) {
+ throw new IndexOutOfBoundsException("index: " + index + ", size: "
+ + size());
+ }
+
+ /** Returns the actual target */
+ @Override
+ protected TableService<E> target() {
+ return (TableService<E>) super.target();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/UnmodifiableTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/UnmodifiableTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/UnmodifiableTableImpl.java
new file mode 100644
index 0000000..138723f
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/UnmodifiableTableImpl.java
@@ -0,0 +1,84 @@
+/*
+ * 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.internal.table;
+
+import javolution.util.function.Equality;
+import javolution.util.service.TableService;
+
+/**
+ * An unmodifiable view over a table.
+ */
+public class UnmodifiableTableImpl<E> extends TableView<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public UnmodifiableTableImpl(TableService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public boolean add(E element) {
+ throw new UnsupportedOperationException("Read-Only Collection.");
+ }
+
+ @Override
+ public void add(int index, E element) {
+ throw new UnsupportedOperationException("Unmodifiable");
+ }
+
+ @Override
+ public void clear() {
+ throw new UnsupportedOperationException("Read-Only Collection.");
+ }
+
+ @Override
+ public Equality<? super E> comparator() {
+ return target().comparator();
+ }
+
+ @Override
+ public E get(int index) {
+ return target().get(index);
+ }
+
+ @Override
+ public int indexOf(Object o) {
+ return target().indexOf(o);
+ }
+
+ @Override
+ public int lastIndexOf(Object o) {
+ return target().lastIndexOf(o);
+ }
+
+ @Override
+ public E remove(int index) {
+ throw new UnsupportedOperationException("Read-Only Collection.");
+ }
+
+ @Override
+ public E set(int index, E element) {
+ throw new UnsupportedOperationException("Read-Only Collection.");
+ }
+
+ @Override
+ public int size() {
+ return target().size();
+ }
+
+ @Override
+ public TableService<E>[] split(int n, boolean updateable) {
+ return SubTableImpl.splitOf(this, n, false); // Sub-views over this.
+ }
+
+ @Override
+ protected TableService<E> target() {
+ return (TableService<E>) super.target();
+ }
+ }
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/AtomicSortedTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/AtomicSortedTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/AtomicSortedTableImpl.java
new file mode 100644
index 0000000..3e624e4
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/AtomicSortedTableImpl.java
@@ -0,0 +1,55 @@
+/*
+ * 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.internal.table.sorted;
+
+import javolution.util.internal.table.AtomicTableImpl;
+import javolution.util.service.SortedTableService;
+import javolution.util.service.TableService;
+
+/**
+ * An atomic view over a sorted table.
+ */
+public class AtomicSortedTableImpl<E> extends AtomicTableImpl<E> implements
+ SortedTableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public AtomicSortedTableImpl(TableService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public synchronized boolean addIfAbsent(E element) {
+ boolean changed = target().addIfAbsent(element);
+ if (changed && !updateInProgress()) immutable = cloneTarget();
+ return changed;
+ }
+
+ @Override
+ public int positionOf(E element) {
+ return targetView().positionOf(element);
+ }
+
+ @Override
+ public SortedTableService<E>[] split(int n, boolean updateable) {
+ return SubSortedTableImpl.splitOf(this, n, false); // Sub-views over this.
+ }
+
+ /** Returns the actual target */
+ @Override
+ protected SortedTableService<E> target() {
+ return (SortedTableService<E>) super.target();
+ }
+
+ @Override
+ protected SortedTableService<E> targetView() {
+ return (SortedTableService<E>) super.targetView();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/FastSortedTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/FastSortedTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/FastSortedTableImpl.java
new file mode 100644
index 0000000..0fbd5ef
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/FastSortedTableImpl.java
@@ -0,0 +1,67 @@
+/*
+ * 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.internal.table.sorted;
+
+import javolution.util.function.Equality;
+import javolution.util.internal.table.FastTableImpl;
+import javolution.util.service.SortedTableService;
+
+/**
+ * The default {@link javolution.util.FastSortedTable FastSortedTable} implementation.
+ */
+public class FastSortedTableImpl<E> extends FastTableImpl<E> implements
+ SortedTableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public FastSortedTableImpl(Equality<? super E> comparator) {
+ super(comparator);
+ }
+
+ @Override
+ public boolean add(E element) {
+ add(positionOf(element), element);
+ return true;
+ }
+
+ @Override
+ public boolean addIfAbsent(E element) {
+ int i = positionOf(element);
+ if ((i < size()) && comparator().areEqual(element, get(i))) return false; // Already there.
+ add(i, element);
+ return true;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public int indexOf(Object element) {
+ int i = positionOf((E) element);
+ if (i >= size() || !comparator().areEqual(get(i), (E) element)) return -1;
+ return i;
+ }
+
+ @Override
+ public int positionOf(E element) {
+ return positionOf(element, 0, size());
+ }
+
+ @Override
+ public SortedTableService<E>[] split(int n, boolean updateable) {
+ return SubSortedTableImpl.splitOf(this, n, updateable); // Sub-views over this.
+ }
+
+ private int positionOf(E element, int start, int length) {
+ if (length == 0) return start;
+ int half = length >> 1;
+ return (comparator().compare(element, get(start + half)) <= 0) ? positionOf(
+ element, start, half) : positionOf(element, start + half + 1,
+ length - half - 1);
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SharedSortedTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SharedSortedTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SharedSortedTableImpl.java
new file mode 100644
index 0000000..8b8ebfe
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SharedSortedTableImpl.java
@@ -0,0 +1,57 @@
+/*
+ * 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.internal.table.sorted;
+
+import javolution.util.internal.table.SharedTableImpl;
+import javolution.util.service.SortedTableService;
+
+/**
+ * A shared view over a sorted table allowing concurrent access and sequential updates.
+ */
+public class SharedSortedTableImpl<E> extends SharedTableImpl<E> implements
+ SortedTableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public SharedSortedTableImpl(SortedTableService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public boolean addIfAbsent(E element) {
+ lock.writeLock.lock();
+ try {
+ return target().addIfAbsent(element);
+ } finally {
+ lock.writeLock.unlock();
+ }
+ }
+
+ @Override
+ public int positionOf(E element) {
+ lock.readLock.lock();
+ try {
+ return target().positionOf(element);
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @Override
+ public SortedTableService<E>[] split(int n, boolean updateable) {
+ return SubSortedTableImpl.splitOf(this, n, false); // Sub-views over this.
+ }
+
+ /** Returns the actual target */
+ @Override
+ protected SortedTableService<E> target() {
+ return (SortedTableService<E>) super.target();
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SortedTableView.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SortedTableView.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SortedTableView.java
new file mode 100644
index 0000000..0c212b3
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SortedTableView.java
@@ -0,0 +1,68 @@
+/*
+ * 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.internal.table.sorted;
+
+import javolution.util.internal.table.TableView;
+import javolution.util.service.SortedTableService;
+
+/**
+ * Sorted table view implementation; can be used as root class for implementations
+ * if target is {@code null}.
+ */
+public abstract class SortedTableView<E> extends TableView<E> implements
+ SortedTableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * The view constructor or root class constructor if target is {@code null}.
+ */
+ public SortedTableView(SortedTableService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public boolean addIfAbsent(E element) {
+ if (!contains(element)) return add(element);
+ return false;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public int indexOf(Object o) {
+ int i = positionOf((E) o);
+ if ((i >= size()) || !comparator().areEqual((E) o, get(i))) return -1;
+ return i;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public int lastIndexOf(Object o) {
+ int i = positionOf((E) o);
+ int result = -1;
+ while ((i < size()) && comparator().areEqual((E) o, get(i))) {
+ result = i++;
+ }
+ return result;
+ }
+
+ @Override
+ public abstract int positionOf(E element);
+
+ @Override
+ public SortedTableService<E>[] split(int n, boolean updateable) {
+ return SubSortedTableImpl.splitOf(this, n, updateable); // Sub-views over this.
+ }
+
+ @Override
+ protected SortedTableService<E> target() {
+ return (SortedTableService<E>) super.target();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SubSortedTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SubSortedTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SubSortedTableImpl.java
new file mode 100644
index 0000000..7bb9eba
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/SubSortedTableImpl.java
@@ -0,0 +1,87 @@
+/*
+ * 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.internal.table.sorted;
+
+import javolution.util.internal.table.SubTableImpl;
+import javolution.util.service.SortedTableService;
+import javolution.util.service.TableService;
+
+/**
+ * A view over a portion of a sorted table.
+ */
+public class SubSortedTableImpl<E> extends SubTableImpl<E> implements SortedTableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /** Splits the specified table. */
+ @SuppressWarnings("unchecked")
+ public static <E> SortedTableService<E>[] splitOf(SortedTableService<E> table,
+ int n, boolean updateable) {
+ if (updateable) table = new SharedSortedTableImpl<E>(table);
+ if (n < 1) throw new IllegalArgumentException("Invalid argument n: "
+ + n);
+ SortedTableService<E>[] subTables = new SortedTableService[n];
+ int minSize = table.size() / n;
+ int start = 0;
+ for (int i = 0; i < n - 1; i++) {
+ subTables[i] = new SubSortedTableImpl<E>(table, start, start + minSize);
+ start += minSize;
+ }
+ subTables[n - 1] = new SubSortedTableImpl<E>(table, start, table.size());
+ return subTables;
+ }
+
+ public SubSortedTableImpl(TableService<E> target, int from, int to) {
+ super(target, from, to);
+ }
+
+ @Override
+ public boolean addIfAbsent(E element) {
+ if (!contains(element)) return add(element);
+ return false;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public int indexOf(Object o) {
+ int i = positionOf((E) o);
+ if ((i >= size()) || !comparator().areEqual((E) o, get(i))) return -1;
+ return i;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public int lastIndexOf(Object o) {
+ int i = positionOf((E) o);
+ int result = -1;
+ while ((i < size()) && comparator().areEqual((E) o, get(i))) {
+ result = i++;
+ }
+ return result;
+ }
+
+ @Override
+ public int positionOf(E element) {
+ int i = target().positionOf(element);
+ if (i < fromIndex) return 0;
+ if (i >= toIndex) return size();
+ return i - fromIndex;
+ }
+
+ @Override
+ public SortedTableService<E>[] split(int n, boolean updateable) {
+ return SubSortedTableImpl.splitOf(this, n, updateable); // Sub-views over this.
+ }
+
+ @Override
+ protected SortedTableService<E> target() {
+ return (SortedTableService<E>) super.target();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/UnmodifiableSortedTableImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/UnmodifiableSortedTableImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/UnmodifiableSortedTableImpl.java
new file mode 100644
index 0000000..7c1efff
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/table/sorted/UnmodifiableSortedTableImpl.java
@@ -0,0 +1,46 @@
+/*
+ * 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.internal.table.sorted;
+
+import javolution.util.internal.table.UnmodifiableTableImpl;
+import javolution.util.service.SortedTableService;
+
+/**
+ * An unmodifiable view over a sorted table.
+ */
+public class UnmodifiableSortedTableImpl<E> extends UnmodifiableTableImpl<E>
+ implements SortedTableService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public UnmodifiableSortedTableImpl(SortedTableService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public boolean addIfAbsent(E element) {
+ throw new UnsupportedOperationException("Read-Only Collection.");
+ }
+
+ @Override
+ public int positionOf(E element) {
+ return target().positionOf(element);
+ }
+
+ @Override
+ public SortedTableService<E>[] split(int n, boolean updateable) {
+ return SubSortedTableImpl.splitOf(this, n, false); // Sub-views over this.
+ }
+
+ /** Returns the actual target */
+ @Override
+ protected SortedTableService<E> target() {
+ return (SortedTableService<E>) super.target();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/package-info.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/package-info.java b/commons/marmotta-commons/src/ext/java/javolution/util/package-info.java
new file mode 100644
index 0000000..697f95f
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/package-info.java
@@ -0,0 +1,32 @@
+/**
+<p> High-performance collection classes with {@link javolution.lang.Realtime
+ worst case execution time behavior} documented.</p>
+<p> Whereas Java current evolution leads to more and more classes being parts of
+ the standard library; Javolution approach is quite the opposite. It aims to
+ provide only the quintessential classes from which all others can be derived.
+ </p>
+ <img src="doc-files/architecture.png" />
+
+<h2><a name="FAQ">FAQ:</a></h2>
+<ol>
+ <li><b>Does <b>J</b>avolution provide immutable collections similar to
+ the ones provided by Scala or .NET ?</b>
+ <p> Using <b>J</b>avolution you may return an {@link javolution.lang.Immutable Immutable}
+ reference (const reference) over any object which cannot be modified including collections or maps.
+[code]
+public class UnitSystem {
+ Set<Unit> units;
+ public UnitSystem(Immutable<Set<Unit>> units) {
+ this.units = units.value(); // Defensive copy unnecessary (immutable)
+ }
+}
+...
+Immutable<Set<Unit>> unitsMKSA = new FastSet<Unit>().addAll(M, K, S, A).toImmutable();
+UnitSystem MKSA = new UnitSystem(unitsMKSA);
+[/code]</p>
+ </li>
+</ol>
+
+ */
+package javolution.util;
+
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/service/CollectionService.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/service/CollectionService.java b/commons/marmotta-commons/src/ext/java/javolution/util/service/CollectionService.java
new file mode 100644
index 0000000..f4664a8
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/service/CollectionService.java
@@ -0,0 +1,39 @@
+/*
+ * 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.service;
+
+import javolution.util.function.Equality;
+import javolution.util.function.Splittable;
+
+import java.io.Serializable;
+import java.util.Collection;
+
+/**
+ * The fundamental set of related functionalities required to implement
+ * fast collections.
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public interface CollectionService<E> extends Collection<E>,
+ Splittable<CollectionService<E>>, Serializable, Cloneable {
+
+ /**
+ * Returns a copy of this collection; updates of the copy should not
+ * impact the original.
+ */
+ CollectionService<E> clone() throws CloneNotSupportedException;
+
+ /**
+ * Returns the comparator used for element equality or order if the
+ * collection is sorted.
+ */
+ Equality<? super E> comparator();
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/service/MapService.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/service/MapService.java b/commons/marmotta-commons/src/ext/java/javolution/util/service/MapService.java
new file mode 100644
index 0000000..c4a8f91
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/service/MapService.java
@@ -0,0 +1,73 @@
+/*
+ * 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.service;
+
+import javolution.util.function.Equality;
+import javolution.util.function.Splittable;
+
+import java.io.Serializable;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.concurrent.ConcurrentMap;
+
+/**
+ * The set of related map functionalities required to implement fast maps.
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ * @see javolution.util.FastMap#FastMap()
+ */
+public interface MapService<K, V> extends
+ Map<K, V>, ConcurrentMap<K, V>, Splittable<MapService<K, V>>, Serializable, Cloneable {
+
+ /**
+ * Returns a copy of this map; updates of the copy should not
+ * impact the original.
+ */
+ MapService<K, V> clone() throws CloneNotSupportedException;
+
+
+ /**
+ * Returns a set view over the entries of this map. The set
+ * support adding/removing entries. Two entries are considered
+ * equals if they have the same key regardless of their values.
+ */
+ @Override
+ SetService<Map.Entry<K, V>> entrySet();
+
+ /**
+ * Returns an iterator over this map entries.
+ */
+ Iterator<Entry<K, V>> iterator();
+
+ /**
+ * Returns the key comparator used for key equality or order if the
+ * map is sorted.
+ */
+ Equality<? super K> keyComparator();
+
+ /**
+ * Returns a set view over the key of this map, the set support
+ * adding new key for which the value is automatically {@code null}.
+ */
+ @Override
+ SetService<K> keySet();
+
+ /**
+ * Returns the value comparator used for value equality.
+ */
+ Equality<? super V> valueComparator();
+
+ /**
+ * Returns a collection view over the values of this map, the collection
+ * support value/entry removal but not adding new values.
+ */
+ @Override
+ CollectionService<V> values();
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/service/SetService.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/service/SetService.java b/commons/marmotta-commons/src/ext/java/javolution/util/service/SetService.java
new file mode 100644
index 0000000..7d2049a
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/service/SetService.java
@@ -0,0 +1,24 @@
+/*
+ * 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.service;
+
+import java.util.Set;
+
+/**
+ * The set of related functionalities used to implement set collections.
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public interface SetService<E> extends CollectionService<E>, Set<E> {
+
+ @Override
+ SetService<E>[] split(int n, boolean updateable);
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/service/SortedMapService.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/service/SortedMapService.java b/commons/marmotta-commons/src/ext/java/javolution/util/service/SortedMapService.java
new file mode 100644
index 0000000..9febb73
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/service/SortedMapService.java
@@ -0,0 +1,41 @@
+/*
+ * 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.service;
+
+import java.util.Map;
+import java.util.SortedMap;
+
+/**
+ * The set of related functionalities used to implement sorted map.
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public interface SortedMapService<K, V> extends MapService<K, V>,
+ SortedMap<K, V> {
+
+ @Override
+ SortedSetService<Map.Entry<K, V>> entrySet();
+
+ @Override
+ SortedMapService<K, V> headMap(K toKey);
+
+ @Override
+ SortedSetService<K> keySet();
+
+ @Override
+ SortedMapService<K, V> subMap(K fromKey, K toKey);
+
+ @Override
+ SortedMapService<K, V> tailMap(K fromKey);
+
+ @Override
+ SortedMapService<K, V>[] split(int n, boolean updateable);
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/582abb5b/commons/marmotta-commons/src/ext/java/javolution/util/service/SortedSetService.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/service/SortedSetService.java b/commons/marmotta-commons/src/ext/java/javolution/util/service/SortedSetService.java
new file mode 100644
index 0000000..5028ae5
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/service/SortedSetService.java
@@ -0,0 +1,33 @@
+/*
+ * 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.service;
+
+import java.util.SortedSet;
+
+/**
+ * The set of related functionalities used to implement sorted set collections.
+ *
+ * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
+ * @version 6.0, July 21, 2013
+ */
+public interface SortedSetService<E> extends SetService<E>, SortedSet<E> {
+
+ @Override
+ SortedSetService<E> headSet(E toElement);
+
+ @Override
+ SortedSetService<E> subSet(E fromElement, E toElement);
+
+ @Override
+ SortedSetService<E> tailSet(E fromElement);
+
+ @Override
+ SortedSetService<E>[] split(int n, boolean updateable);
+
+}