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:26:59 UTC
[07/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/internal/map/sorted/AtomicSortedMapImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/AtomicSortedMapImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/AtomicSortedMapImpl.java
new file mode 100644
index 0000000..c26c500
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/AtomicSortedMapImpl.java
@@ -0,0 +1,82 @@
+/*
+ * 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.map.sorted;
+
+import java.util.Comparator;
+import java.util.Map;
+
+import javolution.util.internal.map.AtomicMapImpl;
+import javolution.util.service.SortedMapService;
+import javolution.util.service.SortedSetService;
+
+/**
+ * An atomic view over a sorted map (copy-on-write).
+ */
+public class AtomicSortedMapImpl<K, V> extends AtomicMapImpl<K, V> implements SortedMapService<K,V> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public AtomicSortedMapImpl(SortedMapService<K, V> target) {
+ super(target);
+ }
+
+ @Override
+ public Comparator<? super K> comparator() {
+ return target().keyComparator();
+ }
+
+ @Override
+ public SortedSetService<Map.Entry<K, V>> entrySet() {
+ return new SubSortedMapImpl<K,V>(this, null, null).entrySet();
+ }
+
+
+ @Override
+ public K firstKey() {
+ return targetView().firstKey();
+ }
+
+
+ @Override
+ public SortedMapService<K, V> headMap(K toKey) {
+ return new SubSortedMapImpl<K,V>(this, null, toKey);
+ }
+
+ @Override
+ public SortedSetService<K> keySet() {
+ return new SubSortedMapImpl<K,V>(this, null, null).keySet();
+ }
+
+ @Override
+ public K lastKey() {
+ return targetView().lastKey();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedMapService<K, V>[] split(int n, boolean updateable) {
+ return new SortedMapService[] { this }; // Split not supported.
+ }
+
+ @Override
+ public SortedMapService<K, V> subMap(K fromKey, K toKey) {
+ return new SubSortedMapImpl<K,V>(this, fromKey, toKey);
+ }
+
+ @Override
+ public SortedMapService<K, V> tailMap(K fromKey) {
+ return new SubSortedMapImpl<K,V>(this, fromKey, null);
+ }
+
+ @Override
+ protected SortedMapService<K,V> targetView() {
+ return (SortedMapService<K,V>) super.targetView();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/FastSortedMapImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/FastSortedMapImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/FastSortedMapImpl.java
new file mode 100644
index 0000000..111bc1d
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/FastSortedMapImpl.java
@@ -0,0 +1,115 @@
+/*
+ * 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.map.sorted;
+
+import java.util.Iterator;
+
+import javolution.util.function.Equality;
+import javolution.util.internal.table.sorted.FastSortedTableImpl;
+
+/**
+ * A map view over a sorted table of entries.
+ */
+public class FastSortedMapImpl<K, V> extends SortedMapView<K,V> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+ private FastSortedTableImpl<Entry<K,V>> entries
+ = new FastSortedTableImpl<Entry<K,V>>(new EntryComparator());
+ private final Equality<? super K> keyComparator;
+ private final Equality<? super V> valueComparator;
+
+ public FastSortedMapImpl(final Equality<? super K> keyComparator,
+ final Equality<? super V> valueComparator) {
+ super(null);
+ this.keyComparator = keyComparator;
+ this.valueComparator = valueComparator;
+ }
+
+ @Override
+ public void clear() {
+ entries.clear();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean containsKey(Object key) {
+ return entries.contains(new MapEntryImpl<K,V>((K)key, null));
+ }
+
+ @Override
+ public K firstKey() {
+ return entries.getFirst().getKey();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public V get(Object key) {
+ int i = entries.indexOf(new MapEntryImpl<K,V>((K)key, null));
+ return (i >= 0) ? entries.get(i).getValue() : null;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return entries.isEmpty();
+ }
+
+ @Override
+ public Iterator<Entry<K, V>> iterator() {
+ return entries.iterator();
+ }
+
+ @Override
+ public Equality<? super K> keyComparator() {
+ return keyComparator;
+ }
+
+ @Override
+ public K lastKey() {
+ return entries.getLast().getKey();
+ }
+
+ @Override
+ public V put(K key, V value) {
+ MapEntryImpl<K,V> entry = new MapEntryImpl<K,V>(key, value);
+ int i = entries.positionOf(entry);
+ if (i < size()) {
+ Entry<K,V> e = entries.get(i);
+ if (keyComparator().areEqual(key, e.getKey())) { // Entry exists.
+ V previous = e.getValue();
+ e.setValue(value);
+ return previous;
+ }
+ }
+ entries.add(i, entry);
+ return null;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public V remove(Object key) {
+ int i = entries.indexOf(new MapEntryImpl<K,V>((K)key, null));
+ if (i < 0) return null;
+ Entry<K,V> e = entries.get(i);
+ V previous = e.getValue();
+ entries.remove(i);
+ return previous;
+ }
+
+ @Override
+ public int size() {
+ return entries.size();
+ }
+
+ @Override
+ public Equality<? super V> valueComparator() {
+ return valueComparator;
+ }
+
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/MapEntryImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/MapEntryImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/MapEntryImpl.java
new file mode 100644
index 0000000..5693a43
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/MapEntryImpl.java
@@ -0,0 +1,50 @@
+/*
+ * 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.map.sorted;
+
+import java.io.Serializable;
+import java.util.Map;
+
+/**
+ * The sorted map entry implementation (serializable).
+ */
+public final class MapEntryImpl<K, V> implements Map.Entry<K, V>, Serializable {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+ K key;
+ V value;
+
+ public MapEntryImpl(K key, V value) {
+ this.key = key;
+ this.value = value;
+ }
+
+ @Override
+ public K getKey() {
+ return key;
+ }
+
+ @Override
+ public V getValue() {
+ return value;
+ }
+
+ @Override
+ public V setValue(V value) {
+ V oldValue = this.value;
+ this.value = value;
+ return oldValue;
+ }
+
+ @Override
+ public String toString() {
+ return key + "=" + value;
+ }
+
+ }
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SharedSortedMapImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SharedSortedMapImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SharedSortedMapImpl.java
new file mode 100644
index 0000000..fecc094
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SharedSortedMapImpl.java
@@ -0,0 +1,107 @@
+/*
+ * 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.map.sorted;
+
+import java.util.Comparator;
+import java.util.Map;
+
+import javolution.util.internal.ReadWriteLockImpl;
+import javolution.util.internal.map.SharedMapImpl;
+import javolution.util.service.SortedMapService;
+import javolution.util.service.SortedSetService;
+
+/**
+ * A shared view over a sorted map.
+ */
+public class SharedSortedMapImpl<K, V> extends SharedMapImpl<K, V> implements SortedMapService<K,V> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public SharedSortedMapImpl(SortedMapService<K, V> target) {
+ super(target);
+ }
+
+ public SharedSortedMapImpl(SortedMapService<K, V> target, ReadWriteLockImpl lock) {
+ super(target, lock);
+ }
+
+ @Override
+ public Comparator<? super K> comparator() {
+ return target().keyComparator();
+ }
+
+ @Override
+ public SortedSetService<Map.Entry<K, V>> entrySet() {
+ return new SubSortedMapImpl<K,V>(this, null, null).entrySet();
+ }
+
+
+ @Override
+ public K firstKey() {
+ lock.readLock.lock();
+ try {
+ return target().firstKey();
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+
+ @Override
+ public SortedMapService<K, V> headMap(K toKey) {
+ return new SubSortedMapImpl<K,V>(this, null, toKey);
+ }
+
+ @Override
+ public SortedSetService<K> keySet() {
+ return new SubSortedMapImpl<K,V>(this, null, null).keySet();
+ }
+
+ @Override
+ public K lastKey() {
+ lock.readLock.lock();
+ try {
+ return target().lastKey();
+ } finally {
+ lock.readLock.unlock();
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedMapService<K,V>[] split(int n, boolean updateable) {
+ SortedMapService<K,V>[] tmp;
+ lock.readLock.lock();
+ try {
+ tmp = target().split(n, updateable);
+ } finally {
+ lock.readLock.unlock();
+ }
+ SortedMapService<K,V>[] result = new SortedMapService[tmp.length];
+ for (int i = 0; i < tmp.length; i++) {
+ result[i] = new SharedSortedMapImpl<K,V>(tmp[i], lock); // Shares the same locks.
+ }
+ return result;
+ }
+
+ @Override
+ public SortedMapService<K, V> subMap(K fromKey, K toKey) {
+ return new SubSortedMapImpl<K,V>(this, fromKey, toKey);
+ }
+
+ @Override
+ public SortedMapService<K, V> tailMap(K fromKey) {
+ return new SubSortedMapImpl<K,V>(this, fromKey, null);
+ }
+
+ @Override
+ protected SortedMapService<K,V> target() {
+ return (SortedMapService<K,V>) super.target();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SortedMapView.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SortedMapView.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SortedMapView.java
new file mode 100644
index 0000000..bb51d56
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SortedMapView.java
@@ -0,0 +1,163 @@
+/*
+ * 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.map.sorted;
+
+import java.util.Comparator;
+import java.util.Map;
+
+import javolution.util.internal.map.MapView;
+import javolution.util.internal.set.sorted.SubSortedSetImpl;
+import javolution.util.service.SortedMapService;
+import javolution.util.service.SortedSetService;
+
+/**
+ * Sorted map view implementation; can be used as root class for implementations
+ * if target is {@code null}.
+ * When possible sub-classes should forward to the actual target for the methods
+ * isEmpty, size and clear rather than using the default implementation.
+ */
+public abstract class SortedMapView<K,V> extends MapView<K,V> implements SortedMapService<K,V> {
+
+ /** Entry Set View */
+ protected class EntrySortedSet extends EntrySet implements SortedSetService<Entry<K,V>> {
+ private static final long serialVersionUID = SortedMapView.serialVersionUID;
+
+ @Override
+ public Entry<K, V> first() {
+ K key = SortedMapView.this.firstKey();
+ V value = SortedMapView.this.get(key);
+ return new MapEntryImpl<K,V>(key, value);
+ }
+
+ @Override
+ public SortedSetService<Entry<K, V>> headSet(Entry<K, V> toElement) {
+ return new SubSortedSetImpl<Entry<K, V>>(this, null, toElement);
+ }
+
+ @Override
+ public java.util.Map.Entry<K, V> last() {
+ K key = SortedMapView.this.lastKey();
+ V value = SortedMapView.this.get(key);
+ return new MapEntryImpl<K,V>(key, value);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedSetService<Entry<K, V>>[] split(int n, boolean updateable) {
+ return new SortedSetService[] { this }; // Split not supported.
+ }
+
+ @Override
+ public SortedSetService<java.util.Map.Entry<K, V>> subSet(
+ Entry<K, V> fromElement,
+ Entry<K, V> toElement) {
+ return new SubSortedSetImpl<Entry<K, V>>(this, fromElement, toElement);
+ }
+
+ @Override
+ public SortedSetService<Entry<K, V>> tailSet(Entry<K, V> fromElement) {
+ return new SubSortedSetImpl<Entry<K, V>>(this, fromElement, null);
+ }
+
+ }
+
+ /** Entry Key View */
+ protected class KeySortedSet extends KeySet implements SortedSetService<K> {
+ private static final long serialVersionUID = SortedMapView.serialVersionUID;
+
+ @Override
+ public K first() {
+ return SortedMapView.this.firstKey();
+ }
+
+ @Override
+ public SortedSetService<K> headSet(K toElement) {
+ return new SubSortedSetImpl<K>(this, null, toElement);
+ }
+
+ @Override
+ public K last() {
+ return SortedMapView.this.lastKey();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedSetService<K>[] split(int n, boolean updateable) {
+ return new SortedSetService[] { this }; // Split not supported.
+ }
+
+ @Override
+ public SortedSetService<K> subSet(K fromElement, K toElement) {
+ return new SubSortedSetImpl<K>(this, fromElement, toElement);
+ }
+
+ @Override
+ public SortedSetService<K> tailSet(K fromElement) {
+ return new SubSortedSetImpl<K>(this, fromElement, null);
+ }
+ }
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * The view constructor or root class constructor if target is {@code null}.
+ */
+ public SortedMapView(SortedMapService<K,V> target) {
+ super(target);
+ }
+
+ @Override
+ public Comparator<? super K> comparator() {
+ return keyComparator();
+ }
+
+ @Override
+ public SortedSetService<Map.Entry<K, V>> entrySet() {
+ return new EntrySortedSet();
+ }
+
+ @Override
+ public abstract K firstKey();
+
+ @Override
+ public SortedMapService<K, V> headMap(K toKey) {
+ return new SubSortedMapImpl<K,V>(this, firstKey(), toKey);
+ }
+
+ @Override
+ public SortedSetService<K> keySet() {
+ return new KeySortedSet();
+ }
+
+ @Override
+ public abstract K lastKey();
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedMapService<K, V>[] split(int n, boolean updateable) {
+ return new SortedMapService[] { this }; // Split not supported.
+ }
+
+ @Override
+ public SortedMapService<K, V> subMap(K fromKey, K toKey) {
+ return new SubSortedMapImpl<K,V>(this, fromKey, toKey);
+ }
+
+ @Override
+ public SortedMapService<K, V> tailMap(K fromKey) {
+ return new SubSortedMapImpl<K,V>(this, fromKey, lastKey());
+ }
+
+ /** Returns the actual target */
+ @Override
+ protected SortedMapService<K,V> target() {
+ return (SortedMapService<K,V>) super.target();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SubSortedMapImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SubSortedMapImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SubSortedMapImpl.java
new file mode 100644
index 0000000..59e4cbd
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/SubSortedMapImpl.java
@@ -0,0 +1,143 @@
+/*
+ * 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.map.sorted;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import javolution.util.function.Equality;
+import javolution.util.service.SortedMapService;
+
+/**
+ * A view over a portion of a sorted map.
+ */
+public class SubSortedMapImpl<K, V> extends SortedMapView<K, V> {
+
+ /** Peeking ahead iterator. */
+ private class IteratorImpl implements Iterator<Entry<K, V>> {
+
+ private boolean ahead;
+ private final Equality<? super K> cmp = keyComparator();
+ private Entry<K, V> next;
+ private final Iterator<Entry<K, V>> targetIterator = target()
+ .iterator();
+
+ @Override
+ public boolean hasNext() {
+ if (ahead) return true;
+ while (targetIterator.hasNext()) {
+ next = targetIterator.next();
+ if ((from != null) && (cmp.compare(next.getKey(), from) < 0)) continue;
+ if ((to != null) && (cmp.compare(next.getKey(), to) >= 0)) break;
+ ahead = true;
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public Entry<K, V> next() {
+ hasNext(); // Moves ahead.
+ ahead = false;
+ return next;
+ }
+
+ @Override
+ public void remove() {
+ targetIterator.remove();
+ }
+ }
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ private final K from; // Can be null.
+ private final K to; // Can be null.
+
+ public SubSortedMapImpl(SortedMapService<K, V> target, K from, K to) {
+ super(target);
+ if ((from != null) && (to != null)
+ && (keyComparator().compare(from, to) > 0)) throw new IllegalArgumentException(
+ "from: " + from + ", to: " + to); // As per SortedSet contract.
+ this.from = from;
+ this.to = to;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public boolean containsKey(Object key) {
+ Equality<? super K> cmp = keyComparator();
+ if ((from != null) && (cmp.compare((K) key, from) < 0)) return false;
+ if ((to != null) && (cmp.compare((K) key, to) >= 0)) return false;
+ return target().containsKey(key);
+ }
+
+ @Override
+ public K firstKey() {
+ if (from == null) return target().firstKey();
+ Iterator<Entry<K, V>> it = iterator();
+ if (!it.hasNext()) throw new NoSuchElementException();
+ return it.next().getKey();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public V get(Object key) {
+ Equality<? super K> cmp = keyComparator();
+ if ((from != null) && (cmp.compare((K) key, from) < 0)) return null;
+ if ((to != null) && (cmp.compare((K) key, to) >= 0)) return null;
+ return target().get(key);
+ }
+
+ @Override
+ public Iterator<Entry<K, V>> iterator() {
+ return new IteratorImpl();
+ }
+
+ @Override
+ public Equality<? super K> keyComparator() {
+ return target().keyComparator();
+ }
+
+ @Override
+ public K lastKey() {
+ if (to == null) return target().lastKey();
+ Iterator<Entry<K, V>> it = iterator();
+ if (!it.hasNext()) throw new NoSuchElementException();
+ Entry<K, V> last = it.next();
+ while (it.hasNext()) {
+ last = it.next();
+ }
+ return last.getKey();
+ }
+
+ @Override
+ public V put(K key, V value) {
+ Equality<? super K> cmp = keyComparator();
+ if ((from != null) && (cmp.compare((K) key, from) < 0)) throw new IllegalArgumentException(
+ "Key: " + key + " outside of this sub-map bounds");
+ if ((to != null) && (cmp.compare((K) key, to) >= 0)) throw new IllegalArgumentException(
+ "Key: " + key + " outside of this sub-map bounds");
+ return target().put(key, value);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public V remove(Object key) {
+ Equality<? super K> cmp = keyComparator();
+ if ((from != null) && (cmp.compare((K) key, from) < 0)) return null;
+ if ((to != null) && (cmp.compare((K) key, to) >= 0)) return null;
+ return target().remove(key);
+ }
+
+ @Override
+ public Equality<? super V> valueComparator() {
+ return target().valueComparator();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/UnmodifiableSortedMapImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/UnmodifiableSortedMapImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/UnmodifiableSortedMapImpl.java
new file mode 100644
index 0000000..60db2b2
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/map/sorted/UnmodifiableSortedMapImpl.java
@@ -0,0 +1,85 @@
+/*
+ * 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.map.sorted;
+
+import java.util.Comparator;
+import java.util.Map;
+
+import javolution.util.internal.map.UnmodifiableMapImpl;
+import javolution.util.service.SortedMapService;
+import javolution.util.service.SortedSetService;
+
+/**
+ * * An unmodifiable view over a map.
+ */
+public class UnmodifiableSortedMapImpl<K, V> extends UnmodifiableMapImpl<K, V> implements SortedMapService<K,V> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public UnmodifiableSortedMapImpl(SortedMapService<K, V> target) {
+ super(target);
+ }
+
+ @Override
+ public Comparator<? super K> comparator() {
+ return target().keyComparator();
+ }
+
+ @Override
+ public SortedSetService<Map.Entry<K, V>> entrySet() {
+ return new SubSortedMapImpl<K,V>(this, null, null).entrySet();
+ }
+
+ @Override
+ public K firstKey() {
+ return target().firstKey();
+ }
+
+ @Override
+ public SortedMapService<K, V> headMap(K toKey) {
+ return new SubSortedMapImpl<K,V>(this, null, toKey);
+ }
+
+ @Override
+ public SortedSetService<K> keySet() {
+ return new SubSortedMapImpl<K,V>(this, null, null).keySet();
+ }
+
+ @Override
+ public K lastKey() {
+ return target().lastKey();
+ }
+
+ @Override
+ public SortedMapService<K, V> subMap(K fromKey, K toKey) {
+ return new SubSortedMapImpl<K,V>(this, fromKey, toKey);
+ }
+
+
+ @Override
+ public SortedMapService<K, V> tailMap(K fromKey) {
+ return new SubSortedMapImpl<K,V>(this, fromKey, null);
+ }
+
+ @Override
+ protected SortedMapService<K,V> target() {
+ return (SortedMapService<K,V>) super.target();
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SortedMapService<K,V>[] split(int n, boolean updateable) {
+ SortedMapService<K,V>[] subTargets = target().split(n, updateable);
+ SortedMapService<K,V>[] result = new SortedMapService[subTargets.length];
+ for (int i = 0; i < subTargets.length; i++) {
+ result[i] = new UnmodifiableSortedMapImpl<K,V>(subTargets[i]);
+ }
+ return result;
+ }
+ }
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/AtomicSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/AtomicSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/AtomicSetImpl.java
new file mode 100644
index 0000000..7a94b53
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/AtomicSetImpl.java
@@ -0,0 +1,31 @@
+/*
+ * 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;
+
+import javolution.util.internal.collection.AtomicCollectionImpl;
+import javolution.util.service.SetService;
+
+/**
+ * An atomic view over a set allowing concurrent access and sequential updates.
+ */
+public class AtomicSetImpl<E> extends AtomicCollectionImpl<E> implements
+ SetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public AtomicSetImpl(SetService<E> target) {
+ super(target);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SetService<E>[] split(int n, boolean updateable) {
+ return new SetService[] { this }; // Split not supported.
+ }
+ }
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/FilteredSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/FilteredSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/FilteredSetImpl.java
new file mode 100644
index 0000000..78759da
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/FilteredSetImpl.java
@@ -0,0 +1,43 @@
+/*
+ * 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;
+
+import javolution.util.function.Predicate;
+import javolution.util.internal.collection.FilteredCollectionImpl;
+import javolution.util.service.SetService;
+
+/**
+ * A filtered view over a set.
+ */
+public class FilteredSetImpl<E> extends FilteredCollectionImpl<E> implements
+ SetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public FilteredSetImpl(SetService<E> target, Predicate<? super E> filter) {
+ super(target, filter);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SetService<E>[] split(int n, boolean updateable) {
+ SetService<E>[] subTargets = target().split(n, updateable);
+ SetService<E>[] result = new SetService[subTargets.length];
+ for (int i = 0; i < subTargets.length; i++) {
+ result[i] = new FilteredSetImpl<E>(subTargets[i], filter);
+ }
+ return result;
+ }
+
+ /** Returns the actual target */
+ @Override
+ protected SetService<E> target() {
+ return (SetService<E>) super.target();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/MappedSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/MappedSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/MappedSetImpl.java
new file mode 100644
index 0000000..83aede0
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/MappedSetImpl.java
@@ -0,0 +1,43 @@
+/*
+ * 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;
+
+import javolution.util.function.Function;
+import javolution.util.internal.collection.MappedCollectionImpl;
+import javolution.util.service.SetService;
+
+/**
+ * A mapped view over a set.
+ */
+public abstract class MappedSetImpl<E, R> extends MappedCollectionImpl<E, R>
+ implements SetService<R> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public MappedSetImpl(SetService<E> target,
+ Function<? super E, ? extends R> function) {
+ super(target, function);
+ }
+
+ @Override
+ public abstract boolean add(R r);
+
+ @Override
+ public abstract boolean contains(Object r);
+
+ @Override
+ public abstract boolean remove(Object r);
+
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SetService<R>[] split(int n, boolean updateable) {
+ return new SetService[] { this }; // Split not supported.
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/SetView.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/SetView.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/SetView.java
new file mode 100644
index 0000000..a5a81e1
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/SetView.java
@@ -0,0 +1,49 @@
+/*
+ * 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;
+
+import javolution.util.internal.collection.CollectionView;
+import javolution.util.service.SetService;
+
+/**
+ * Set view implementation; can be used as root class for implementations
+ * if target is {@code null}.
+ */
+public abstract class SetView<E> extends CollectionView<E> implements SetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ /**
+ * The view constructor or root class constructor if target is {@code null}.
+ */
+ public SetView(SetService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public abstract boolean contains(Object o);
+
+ @Override
+ public abstract boolean remove(Object o);
+
+ @Override
+ public abstract int size();
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SetService<E>[] split(int n, boolean updateable) {
+ return new SetService[] { this }; // Split not supported.
+ }
+
+ @Override
+ protected SetService<E> target() {
+ return (SetService<E>) super.target();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/SharedSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/SharedSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/SharedSetImpl.java
new file mode 100644
index 0000000..1b8e0a9
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/SharedSetImpl.java
@@ -0,0 +1,52 @@
+/*
+ * 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;
+
+import javolution.util.internal.ReadWriteLockImpl;
+import javolution.util.internal.collection.SharedCollectionImpl;
+import javolution.util.service.SetService;
+
+/**
+ * A shared view over a set allowing concurrent access and sequential updates.
+ */
+public class SharedSetImpl<E> extends SharedCollectionImpl<E> implements
+ SetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public SharedSetImpl(SetService<E> target) {
+ super(target);
+ }
+
+ public SharedSetImpl(SetService<E> target, ReadWriteLockImpl lock) {
+ super(target, lock);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SetService<E>[] split(int n, boolean updateable) {
+ SetService<E>[] tmp;
+ lock.readLock.lock();
+ try {
+ tmp = target().split(n, updateable);
+ } finally {
+ lock.readLock.unlock();
+ }
+ SetService<E>[] result = new SetService[tmp.length];
+ for (int i = 0; i < tmp.length; i++) {
+ result[i] = new SharedSetImpl<E>(tmp[i], lock); // Shares the same locks.
+ }
+ return result;
+ }
+
+ @Override
+ protected SetService<E> target() {
+ return (SetService<E>) super.target();
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/UnmodifiableSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/UnmodifiableSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/UnmodifiableSetImpl.java
new file mode 100644
index 0000000..1ff6ff6
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/UnmodifiableSetImpl.java
@@ -0,0 +1,42 @@
+/*
+ * 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;
+
+import javolution.util.internal.collection.UnmodifiableCollectionImpl;
+import javolution.util.service.SetService;
+
+/**
+ * An unmodifiable view over a set.
+ */
+public class UnmodifiableSetImpl<E> extends UnmodifiableCollectionImpl<E>
+ implements SetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public UnmodifiableSetImpl(SetService<E> target) {
+ super(target);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public SetService<E>[] split(int n, boolean updateable) {
+ SetService<E>[] subTargets = target().split(n, updateable);
+ SetService<E>[] result = new SetService[subTargets.length];
+ for (int i = 0; i < subTargets.length; i++) {
+ result[i] = new UnmodifiableSetImpl<E>(subTargets[i]);
+ }
+ return result;
+ }
+
+ @Override
+ protected SetService<E> target() {
+ return (SetService<E>) super.target();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/AtomicSortedSetImpl.java
----------------------------------------------------------------------
diff --git a/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/AtomicSortedSetImpl.java b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/AtomicSortedSetImpl.java
new file mode 100644
index 0000000..d47e5d0
--- /dev/null
+++ b/commons/marmotta-commons/src/ext/java/javolution/util/internal/set/sorted/AtomicSortedSetImpl.java
@@ -0,0 +1,62 @@
+/*
+ * 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.AtomicSetImpl;
+import javolution.util.service.SortedSetService;
+
+/**
+ * An atomic view over a sorted set allowing concurrent access and sequential updates.
+ */
+public class AtomicSortedSetImpl<E> extends AtomicSetImpl<E> implements
+ SortedSetService<E> {
+
+ private static final long serialVersionUID = 0x600L; // Version.
+
+ public AtomicSortedSetImpl(SortedSetService<E> target) {
+ super(target);
+ }
+
+ @Override
+ public E first() {
+ return targetView().first();
+ }
+
+ @Override
+ public SortedSetService<E> headSet(E toElement) {
+ return new SubSortedSetImpl<E>(this, null, toElement);
+ }
+
+ @Override
+ public E last() {
+ return targetView().last();
+ }
+
+ @Override
+ @SuppressWarnings("unchecked")
+ 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> targetView() {
+ return (SortedSetService<E>) super.targetView();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-marmotta/blob/e43574ef/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/e43574ef/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/e43574ef/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..3673004
--- /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 java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import javolution.util.function.Equality;
+import javolution.util.service.CollectionService;
+import javolution.util.service.SortedSetService;
+
+/**
+ * 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/e43574ef/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/e43574ef/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..056c149
--- /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 java.util.Collection;
+import java.util.Iterator;
+import java.util.ListIterator;
+
+import javolution.util.internal.collection.AtomicCollectionImpl;
+import javolution.util.service.TableService;
+
+/**
+ * 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/e43574ef/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..070da4d
--- /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 java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import javolution.util.function.Equality;
+
+/**
+ * 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/e43574ef/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/e43574ef/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..13cf342
--- /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 java.util.Comparator;
+
+import javolution.util.service.TableService;
+
+/**
+ * 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/e43574ef/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/e43574ef/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..bc68a16
--- /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 java.util.Collection;
+import java.util.Iterator;
+import java.util.ListIterator;
+
+import javolution.util.internal.ReadWriteLockImpl;
+import javolution.util.internal.collection.SharedCollectionImpl;
+import javolution.util.service.TableService;
+
+/**
+ * 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