http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/HashTreePMap.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/HashTreePMap.java b/modules/core/src/main/java/org/pcollections/HashTreePMap.java deleted file mode 100644 index 7a8071b..0000000 --- a/modules/core/src/main/java/org/pcollections/HashTreePMap.java +++ /dev/null @@ -1,52 +0,0 @@ -package org.pcollections; - -import java.util.*; -import java.util.Map.*; - - -/** - * A static convenience class for creating efficient persistent maps. - * <p/> - * This class simply creates HashPMaps backed by IntTreePMaps. - * - * @author harold - */ -public final class HashTreePMap { - private static final HashPMap<Object, Object> EMPTY - = HashPMap.empty(IntTreePMap.<PSequence<Entry<Object, Object>>>empty()); - - // not instantiable (or subclassable): - private HashTreePMap() { - } - - /** - * @param <K> - * @param <V> - * @return an empty map - */ - @SuppressWarnings("unchecked") - public static <K, V> HashPMap<K, V> empty() { - return (HashPMap<K, V>) EMPTY; - } - - /** - * @param <K> - * @param <V> - * @param key - * @param value - * @return empty().plus(key, value) - */ - public static <K, V> HashPMap<K, V> singleton(final K key, final V value) { - return HashTreePMap.<K, V>empty().plus(key, value); - } - - /** - * @param <K> - * @param <V> - * @param map - * @return empty().plusAll(map) - */ - public static <K, V> HashPMap<K, V> from(final Map<? extends K, ? extends V> map) { - return HashTreePMap.<K, V>empty().plusAll(map); - } -}
http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/HashTreePSet.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/HashTreePSet.java b/modules/core/src/main/java/org/pcollections/HashTreePSet.java deleted file mode 100644 index e33e01e..0000000 --- a/modules/core/src/main/java/org/pcollections/HashTreePSet.java +++ /dev/null @@ -1,46 +0,0 @@ -package org.pcollections; - -import java.util.*; - - -/** - * A static convenience class for creating efficient persistent sets. - * <p/> - * This class simply creates MapPSets backed by HashTreePMaps. - * - * @author harold - */ -public final class HashTreePSet { - private static final MapPSet<Object> EMPTY = MapPSet.from(HashTreePMap.empty()); - - // not instantiable (or subclassable): - private HashTreePSet() { - } - - /** - * @param <E> - * @return an empty set - */ - @SuppressWarnings("unchecked") - public static <E> MapPSet<E> empty() { - return (MapPSet<E>) EMPTY; - } - - /** - * @param <E> - * @param e - * @return empty().plus(e) - */ - public static <E> MapPSet<E> singleton(final E e) { - return HashTreePSet.<E>empty().plus(e); - } - - /** - * @param <E> - * @param list - * @return empty().plusAll(map) - */ - public static <E> MapPSet<E> from(final Collection<? extends E> list) { - return HashTreePSet.<E>empty().plusAll(list); - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/IntTree.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/IntTree.java b/modules/core/src/main/java/org/pcollections/IntTree.java deleted file mode 100644 index 5d2335a..0000000 --- a/modules/core/src/main/java/org/pcollections/IntTree.java +++ /dev/null @@ -1,320 +0,0 @@ -package org.pcollections; - -import java.util.*; -import java.util.Map.*; - - -/** - * A non-public utility class for persistent balanced tree maps with integer keys. - * <p/> - * To allow for efficiently increasing all keys above a certain value or decreasing - * all keys below a certain value, the keys values are stored relative to their parent. - * This makes this map a good backing for fast insertion and removal of indices in a - * vector. - * <p/> - * This implementation is thread-safe except for its iterators. - * <p/> - * Other than that, this tree is based on the Glasgow Haskell Compiler's Data.Map implementation, - * which in turn is based on "size balanced binary trees" as described by: - * <p/> - * Stephen Adams, "Efficient sets: a balancing act", - * Journal of Functional Programming 3(4):553-562, October 1993, - * http://www.swiss.ai.mit.edu/~adams/BB/. - * <p/> - * J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", - * SIAM journal of computing 2(1), March 1973. - * - * @param <V> - * @author harold - */ -class IntTree<V> { - // marker value: - static final IntTree<Object> EMPTYNODE = new IntTree<Object>(); - private static final int OMEGA = 5; - private static final int ALPHA = 2; - private final long key; // we use longs so relative keys can express all ints - // (e.g. if this has key -10 and right has 'absolute' key MAXINT, - // then its relative key is MAXINT+10 which overflows) - // there might be some way to deal with this based on left-verse-right logic, - // but that sounds like a mess. - private final V value; // null value means this is empty node - private final IntTree<V> left, right; - private final int size; - - private IntTree() { - if (EMPTYNODE != null) - throw new RuntimeException("empty constructor should only be used once"); - size = 0; - - key = 0; - value = null; - left = null; - right = null; - } - - private IntTree(final long key, final V value, final IntTree<V> left, final IntTree<V> right) { - this.key = key; - this.value = value; - this.left = left; - this.right = right; - size = 1 + left.size + right.size; - } - - // rebalance a tree that is off-balance by at most 1: - private static <V> IntTree<V> rebalanced(final long key, final V value, - final IntTree<V> left, final IntTree<V> right) { - if (left.size + right.size > 1) { - if (left.size >= OMEGA * right.size) { // rotate to the right - IntTree<V> ll = left.left, lr = left.right; - if (lr.size < ALPHA * ll.size) // single rotation - return new IntTree<V>(left.key + key, left.value, - ll, - new IntTree<V>(-left.key, value, - lr.withKey(lr.key + left.key), - right) - ); - else { // double rotation: - IntTree<V> lrl = lr.left, lrr = lr.right; - return new IntTree<V>(lr.key + left.key + key, lr.value, - new IntTree<V>(-lr.key, left.value, - ll, - lrl.withKey(lrl.key + lr.key)), - new IntTree<V>(-left.key - lr.key, value, - lrr.withKey(lrr.key + lr.key + left.key), - right) - ); - } - } - else if (right.size >= OMEGA * left.size) { // rotate to the left - IntTree<V> rl = right.left, rr = right.right; - if (rl.size < ALPHA * rr.size) // single rotation - return new IntTree<V>(right.key + key, right.value, - new IntTree<V>(-right.key, value, - left, - rl.withKey(rl.key + right.key)), - rr - ); - else { // double rotation: - IntTree<V> rll = rl.left, rlr = rl.right; - return new IntTree<V>(rl.key + right.key + key, rl.value, - new IntTree<V>(-right.key - rl.key, value, - left, - rll.withKey(rll.key + rl.key + right.key)), - new IntTree<V>(-rl.key, right.value, - rlr.withKey(rlr.key + rl.key), - rr) - ); - } - } - } - // otherwise already balanced enough: - return new IntTree<V>(key, value, left, right); - } - - private IntTree<V> withKey(final long newKey) { - if (size == 0 || newKey == key) return this; - return new IntTree<V>(newKey, value, left, right); - } - - Iterator<Entry<Integer, V>> iterator() { - return new EntryIterator<V>(this); - } - - int size() { - return size; - } - - boolean containsKey(final long key) { - if (size == 0) - return false; - if (key < this.key) - return left.containsKey(key - this.key); - if (key > this.key) - return right.containsKey(key - this.key); - // otherwise key==this.key: - return true; - } - - V get(final long key) { - if (size == 0) - return null; - if (key < this.key) - return left.get(key - this.key); - if (key > this.key) - return right.get(key - this.key); - // otherwise key==this.key: - return value; - } - - IntTree<V> plus(final long key, final V value) { - if (size == 0) - return new IntTree<V>(key, value, this, this); - if (key < this.key) - return rebalanced(left.plus(key - this.key, value), right); - if (key > this.key) - return rebalanced(left, right.plus(key - this.key, value)); - // otherwise key==this.key, so we simply replace this, with no effect on balance: - if (value == this.value) - return this; - return new IntTree<V>(key, value, left, right); - } - - IntTree<V> minus(final long key) { - if (size == 0) - return this; - if (key < this.key) - return rebalanced(left.minus(key - this.key), right); - if (key > this.key) - return rebalanced(left, right.minus(key - this.key)); - - // otherwise key==this.key, so we are killing this node: - - if (left.size == 0) // we can just become right node - // make key 'absolute': - return right.withKey(right.key + this.key); - if (right.size == 0) // we can just become left node - return left.withKey(left.key + this.key); - - // otherwise replace this with the next key (i.e. the smallest key to the right): - - // TODO have minNode() instead of minKey to avoid having to call get() - // TODO get node from larger subtree, i.e. if left.size>right.size use left.maxNode() - // TODO have faster minusMin() instead of just using minus() - - long newKey = right.minKey() + this.key; - //(right.minKey() is relative to this; adding this.key makes it 'absolute' - // where 'absolute' really means relative to the parent of this) - - V newValue = right.get(newKey - this.key); - // now that we've got the new stuff, take it out of the right subtree: - IntTree<V> newRight = right.minus(newKey - this.key); - - // lastly, make the subtree keys relative to newKey (currently they are relative to this.key): - newRight = newRight.withKey((newRight.key + this.key) - newKey); - // left is definitely not empty: - IntTree<V> newLeft = left.withKey((left.key + this.key) - newKey); - - return rebalanced(newKey, newValue, newLeft, newRight); - } - - /** - * Changes every key k>=key to k+delta. - * <p/> - * This method will create an _invalid_ tree if delta<0 - * and the distance between the smallest k>=key in this - * and the largest j<key in this is |delta| or less. - * <p/> - * In other words, this method must not result in any change - * in the order of the keys in this, since the tree structure is - * not being changed at all. - */ - IntTree<V> changeKeysAbove(final long key, final int delta) { - if (size == 0 || delta == 0) - return this; - - if (this.key >= key) - // adding delta to this.key changes the keys of _all_ children of this, - // so we now need to un-change the children of this smaller than key, - // all of which are to the left. note that we still use the 'old' relative key...: - return new IntTree<V>(this.key + delta, value, left.changeKeysBelow(key - this.key, -delta), right); - - // otherwise, doesn't apply yet, look to the right: - IntTree<V> newRight = right.changeKeysAbove(key - this.key, delta); - if (newRight == right) return this; - return new IntTree<V>(this.key, value, left, newRight); - } - - /** - * Changes every key k<key to k+delta. - * <p/> - * This method will create an _invalid_ tree if delta>0 - * and the distance between the largest k<key in this - * and the smallest j>=key in this is delta or less. - * <p/> - * In other words, this method must not result in any overlap or change - * in the order of the keys in this, since the tree _structure_ is - * not being changed at all. - */ - IntTree<V> changeKeysBelow(final long key, final int delta) { - if (size == 0 || delta == 0) - return this; - - if (this.key < key) - // adding delta to this.key changes the keys of _all_ children of this, - // so we now need to un-change the children of this larger than key, - // all of which are to the right. note that we still use the 'old' relative key...: - return new IntTree<V>(this.key + delta, value, left, right.changeKeysAbove(key - this.key, -delta)); - - // otherwise, doesn't apply yet, look to the left: - IntTree<V> newLeft = left.changeKeysBelow(key - this.key, delta); - if (newLeft == left) return this; - return new IntTree<V>(this.key, value, newLeft, right); - } - - // min key in this: - private long minKey() { - if (left.size == 0) - return key; - // make key 'absolute' (i.e. relative to the parent of this): - return left.minKey() + this.key; - } - - private IntTree<V> rebalanced(final IntTree<V> newLeft, final IntTree<V> newRight) { - if (newLeft == left && newRight == right) - return this; // already balanced - return rebalanced(key, value, newLeft, newRight); - } - - ////entrySet().iterator() IMPLEMENTATION //// - // TODO make this a ListIterator? - private static final class EntryIterator<V> implements Iterator<Entry<Integer, V>> { - private PStack<IntTree<V>> stack = ConsPStack.empty(); //path of nonempty nodes - private int key = 0; // note we use _int_ here since this is a truly absolute key - - EntryIterator(final IntTree<V> root) { - gotoMinOf(root); - } - - public boolean hasNext() { - return stack.size() > 0; - } - - public Entry<Integer, V> next() { - IntTree<V> node = stack.get(0); - final Entry<Integer, V> result = new SimpleImmutableEntry<Integer, V>(key, node.value); - - // find next node. - // we've already done everything smaller, - // so try least larger node: - - if (node.right.size > 0) // we can descend to the right - gotoMinOf(node.right); - - else // can't descend to the right -- try ascending to the right - while (true) { // find current node's least larger ancestor, if any - key -= node.key; // revert to parent's key - stack = stack.subList(1); // climb up to parent - // if parent was larger than child or there was no parent, we're done: - if (node.key < 0 || stack.size() == 0) - break; - // otherwise parent was smaller -- try its parent: - node = stack.get(0); - } - - return result; - } - - public void remove() { - throw new UnsupportedOperationException(); - } - - // extend the stack to its least non-empty node: - private void gotoMinOf(IntTree<V> node) { - while (node.size > 0) { - stack = stack.plus(node); - key += node.key; - node = node.left; - } - } - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/IntTreePMap.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/IntTreePMap.java b/modules/core/src/main/java/org/pcollections/IntTreePMap.java deleted file mode 100644 index 3c90527..0000000 --- a/modules/core/src/main/java/org/pcollections/IntTreePMap.java +++ /dev/null @@ -1,165 +0,0 @@ -package org.pcollections; - -import java.util.*; - - -/** - * An efficient persistent map from integer keys to non-null values. - * <p/> - * Iteration occurs in the integer order of the keys. - * <p/> - * This implementation is thread-safe (assuming Java's AbstractMap and AbstractSet are thread-safe), - * although its iterators may not be. - * <p/> - * The balanced tree is based on the Glasgow Haskell Compiler's Data.Map implementation, - * which in turn is based on "size balanced binary trees" as described by: - * <p/> - * Stephen Adams, "Efficient sets: a balancing act", - * Journal of Functional Programming 3(4):553-562, October 1993, - * http://www.swiss.ai.mit.edu/~adams/BB/. - * <p/> - * J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", - * SIAM journal of computing 2(1), March 1973. - * - * @param <V> - * @author harold - */ -public final class IntTreePMap<V> extends AbstractMap<Integer, V> implements PMap<Integer, V> { - //// STATIC FACTORY METHODS //// - private static final IntTreePMap<Object> EMPTY = new IntTreePMap<Object>(IntTree.EMPTYNODE); - //// PRIVATE CONSTRUCTORS //// - private final IntTree<V> root; - //// REQUIRED METHODS FROM AbstractMap //// - // this cache variable is thread-safe, since assignment in Java is atomic: - private Set<Entry<Integer, V>> entrySet = null; - - // not externally instantiable (or subclassable): - private IntTreePMap(final IntTree<V> root) { - this.root = root; - } - - /** - * @param <V> - * @return an empty map - */ - @SuppressWarnings("unchecked") - public static <V> IntTreePMap<V> empty() { - return (IntTreePMap<V>) EMPTY; - } - - /** - * @param <V> - * @param key - * @param value - * @return empty().plus(key, value) - */ - public static <V> IntTreePMap<V> singleton(final Integer key, final V value) { - return IntTreePMap.<V>empty().plus(key, value); - } - - /** - * @param <V> - * @param map - * @return empty().plusAll(map) - */ - @SuppressWarnings("unchecked") - public static <V> IntTreePMap<V> from(final Map<? extends Integer, ? extends V> map) { - if (map instanceof IntTreePMap) - return (IntTreePMap<V>) map; //(actually we only know it's IntTreePMap<? extends V>) - // but that's good enough for an immutable - // (i.e. we can't mess someone else up by adding the wrong type to it) - return IntTreePMap.<V>empty().plusAll(map); - } - - private IntTreePMap<V> withRoot(final IntTree<V> root) { - if (root == this.root) return this; - return new IntTreePMap<V>(root); - } - - //// UNINHERITED METHODS OF IntTreePMap //// - IntTreePMap<V> withKeysChangedAbove(final int key, final int delta) { - // TODO check preconditions of changeKeysAbove() - // TODO make public? - return withRoot(root.changeKeysAbove(key, delta)); - } - - IntTreePMap<V> withKeysChangedBelow(final int key, final int delta) { - // TODO check preconditions of changeKeysAbove() - // TODO make public? - return withRoot(root.changeKeysBelow(key, delta)); - } - - @Override - public Set<Entry<Integer, V>> entrySet() { - if (entrySet == null) - entrySet = new AbstractSet<Entry<Integer, V>>() { - // REQUIRED METHODS OF AbstractSet // - @Override - public int size() { // same as Map - return IntTreePMap.this.size(); - } - - @Override - public Iterator<Entry<Integer, V>> iterator() { - return root.iterator(); - } - - // OVERRIDDEN METHODS OF AbstractSet // - @Override - public boolean contains(final Object e) { - if (!(e instanceof Entry)) - return false; - V value = get(((Entry<?, ?>) e).getKey()); - return value != null && value.equals(((Entry<?, ?>) e).getValue()); - } - }; - return entrySet; - } - - - //// OVERRIDDEN METHODS FROM AbstractMap //// - @Override - public int size() { - return root.size(); - } - - @Override - public boolean containsKey(final Object key) { - if (!(key instanceof Integer)) - return false; - return root.containsKey((Integer) key); - } - - @Override - public V get(final Object key) { - if (!(key instanceof Integer)) - return null; - return root.get((Integer) key); - } - - - //// IMPLEMENTED METHODS OF PMap//// - public IntTreePMap<V> plus(final Integer key, final V value) { - return withRoot(root.plus(key, value)); - } - - public IntTreePMap<V> minus(final Object key) { - if (!(key instanceof Integer)) return this; - return withRoot(root.minus((Integer) key)); - } - - public IntTreePMap<V> plusAll(final Map<? extends Integer, ? extends V> map) { - IntTree<V> root = this.root; - for (Entry<? extends Integer, ? extends V> entry : map.entrySet()) - root = root.plus(entry.getKey(), entry.getValue()); - return withRoot(root); - } - - public IntTreePMap<V> minusAll(final Collection<?> keys) { - IntTree<V> root = this.root; - for (Object key : keys) - if (key instanceof Integer) - root = root.minus((Integer) key); - return withRoot(root); - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/MapPBag.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/MapPBag.java b/modules/core/src/main/java/org/pcollections/MapPBag.java deleted file mode 100644 index 2ef5eb6..0000000 --- a/modules/core/src/main/java/org/pcollections/MapPBag.java +++ /dev/null @@ -1,143 +0,0 @@ -package org.pcollections; - -import java.util.*; -import java.util.Map.*; - - -/** - * A map-backed persistent bag. - * <p/> - * If the backing map is thread-safe, then this implementation is thread-safe - * (assuming Java's AbstractCollection is thread-safe), although its iterators - * may not be. - * - * @param <E> - * @author harold - */ -public final class MapPBag<E> extends AbstractCollection<E> implements PBag<E> { -//// STATIC FACTORY METHODS //// - - //// PRIVATE CONSTRUCTORS //// - private final PMap<E, Integer> map; - private final int size; - // not instantiable (or subclassable): - private MapPBag(final PMap<E, Integer> map, final int size) { - this.map = map; - this.size = size; - } - - /** - * @param <E> - * @param map - * @return a PBag backed by an empty version of map, i.e. by map.minusAll(map.keySet()) - */ - public static <E> MapPBag<E> empty(final PMap<E, Integer> map) { - return new MapPBag<E>(map.minusAll(map.keySet()), 0); - } - - //// PRIVATE STATIC UTILITIES //// - private static int size(final PMap<?, Integer> map) { - int size = 0; - for (Integer n : map.values()) - size += n; - return size; - } - - //// REQUIRED METHODS FROM AbstractCollection //// - @Override - public int size() { - return size; - } - - @Override - public Iterator<E> iterator() { - final Iterator<Entry<E, Integer>> i = map.entrySet().iterator(); - return new Iterator<E>() { - private E e; - private int n = 0; - - public boolean hasNext() { - return n > 0 || i.hasNext(); - } - - public E next() { - if (n == 0) { // finished with current element - Entry<E, Integer> entry = i.next(); - e = entry.getKey(); - n = entry.getValue(); - } - n--; - return e; - } - - public void remove() { - throw new UnsupportedOperationException(); - } - }; - } - - //// OVERRIDDEN METHODS OF AbstractCollection //// - @Override - public boolean contains(final Object e) { - return map.containsKey(e); - } - - @Override - public int hashCode() { - int hashCode = 0; - for (E e : this) - hashCode += e.hashCode(); - return hashCode; - } - - @SuppressWarnings("unchecked") - @Override - public boolean equals(Object that) { - if (!(that instanceof PBag)) - return false; - if (!(that instanceof MapPBag)) { - // make that into a MapPBag: - // TODO this is INEFFICIENT - MapPBag<Object> empty = (MapPBag<Object>) this.minusAll(this); - that = empty.plusAll((PBag<?>) that); - } - return this.map.equals(((MapPBag<?>) that).map); - } - - //// IMPLEMENTED METHODS OF PSet //// - public MapPBag<E> plus(final E e) { - return new MapPBag<E>(map.plus(e, count(e) + 1), size + 1); - } - - @SuppressWarnings("unchecked") - public MapPBag<E> minus(final Object e) { - int n = count(e); - if (n == 0) - return this; - if (n == 1) // remove from map - return new MapPBag<E>(map.minus(e), size - 1); - // otherwise just decrement count: - return new MapPBag<E>(map.plus((E) e, n - 1), size - 1); - } - - public MapPBag<E> plusAll(final Collection<? extends E> list) { - MapPBag<E> bag = this; - for (E e : list) bag = bag.plus(e); - return bag; - } - - public MapPBag<E> minusAll(final Collection<?> list) { - // removes _all_ elements found in list, i.e. counts are irrelevant: - PMap<E, Integer> map = this.map.minusAll(list); - return new MapPBag<E>(map, size(map)); // (completely recomputes size) - } - - //// PRIVATE UTILITIES //// - // TODO should this be part of PBag? - @SuppressWarnings("unchecked") - private int count(final Object o) { - if (!contains(o)) return 0; - // otherwise o must be an E: - return map.get((E) o); - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/MapPSet.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/MapPSet.java b/modules/core/src/main/java/org/pcollections/MapPSet.java deleted file mode 100644 index 0e78eb8..0000000 --- a/modules/core/src/main/java/org/pcollections/MapPSet.java +++ /dev/null @@ -1,101 +0,0 @@ -package org.pcollections; - -import java.util.*; - - -/** - * A map-backed persistent set. - * <p/> - * If the backing map is thread-safe, then this implementation is thread-safe - * (assuming Java's AbstractSet is thread-safe), although its iterators - * may not be. - * - * @param <E> - * @author harold - */ -public final class MapPSet<E> extends AbstractSet<E> implements PSet<E> { -//// STATIC FACTORY METHODS //// - - //// PRIVATE CONSTRUCTORS //// - private final PMap<E, Object> map; - - // not instantiable (or subclassable): - private MapPSet(final PMap<E, Object> map) { - this.map = map; - } - - /** - * @param <E> - * @param map - * @return a PSet with the elements of map.keySet(), backed by map - */ - @SuppressWarnings("unchecked") - public static <E> MapPSet<E> from(final PMap<E, ?> map) { - return new MapPSet<E>((PMap<E, Object>) map); - } - - /** - * @param <E> - * @param map - * @param e - * @return from(map).plus(e) - */ - public static <E> MapPSet<E> from(final PMap<E, ?> map, E e) { - return from(map).plus(e); - } - - /** - * @param <E> - * @param map - * @param list - * @return from(map).plusAll(list) - */ - public static <E> MapPSet<E> from(final PMap<E, ?> map, final Collection<? extends E> list) { - return from(map).plusAll(list); - } - - //// REQUIRED METHODS FROM AbstractSet //// - @Override - public Iterator<E> iterator() { - return map.keySet().iterator(); - } - - @Override - public int size() { - return map.size(); - } - - - //// OVERRIDDEN METHODS OF AbstractSet //// - @Override - public boolean contains(final Object e) { - return map.containsKey(e); - } - - public MapPSet<E> plus(final E e) { - if (contains(e)) return this; - return new MapPSet<E>(map.plus(e, In.IN)); - } - - public MapPSet<E> minus(final Object e) { - if (!contains(e)) return this; - return new MapPSet<E>(map.minus(e)); - } - - public MapPSet<E> plusAll(final Collection<? extends E> list) { - PMap<E, Object> map = this.map; - for (E e : list) - map = map.plus(e, In.IN); - return from(map); - } - - public MapPSet<E> minusAll(final Collection<?> list) { - PMap<E, Object> map = this.map.minusAll(list); - return from(map); - } - - //// IMPLEMENTED METHODS OF PSet //// - private static enum In { - IN - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/OrderedPSet.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/OrderedPSet.java b/modules/core/src/main/java/org/pcollections/OrderedPSet.java deleted file mode 100644 index 48ea3bc..0000000 --- a/modules/core/src/main/java/org/pcollections/OrderedPSet.java +++ /dev/null @@ -1,85 +0,0 @@ -package org.pcollections; - -import java.util.*; - -public class OrderedPSet<E> extends AbstractSet<E> implements POrderedSet<E> { - private static final OrderedPSet<Object> EMPTY = new OrderedPSet<Object>( - Empty.set(), Empty.vector()); - private PSet<E> contents; - private PVector<E> order; - - private OrderedPSet(PSet<E> c, PVector<E> o) { - contents = c; - order = o; - } - - @SuppressWarnings("unchecked") - public static <E> OrderedPSet<E> empty() { - return (OrderedPSet<E>) EMPTY; - } - - @SuppressWarnings("unchecked") - public static <E> OrderedPSet<E> from(final Collection<? extends E> list) { - if (list instanceof OrderedPSet) - return (OrderedPSet<E>) list; - return OrderedPSet.<E>empty().plusAll(list); - } - - public static <E> OrderedPSet<E> singleton(final E e) { - return OrderedPSet.<E>empty().plus(e); - } - - @Override - public OrderedPSet<E> plus(E e) { - if (contents.contains(e)) - return this; - return new OrderedPSet<E>(contents.plus(e), order.plus(e)); - } - - @Override - public OrderedPSet<E> plusAll(Collection<? extends E> list) { - OrderedPSet<E> s = this; - for (E e : list) { - s = s.plus(e); - } - return s; - } - - @Override - public OrderedPSet<E> minus(Object e) { - if (!contents.contains(e)) - return this; - return new OrderedPSet<E>(contents.minus(e), order.minus(e)); - } - - @Override - public OrderedPSet<E> minusAll(Collection<?> list) { - OrderedPSet<E> s = this; - for (Object e : list) { - s = s.minus(e); - } - return s; - } - - @Override - public Iterator<E> iterator() { - return order.iterator(); - } - - @Override - public int size() { - return contents.size(); - } - - @Override - public E get(int index) { - return order.get(index); - } - - @Override - public int indexOf(Object o) { - if (!contents.contains(o)) - return -1; - return order.indexOf(o); - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/PBag.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/PBag.java b/modules/core/src/main/java/org/pcollections/PBag.java deleted file mode 100644 index 5377244..0000000 --- a/modules/core/src/main/java/org/pcollections/PBag.java +++ /dev/null @@ -1,23 +0,0 @@ -package org.pcollections; - -import java.util.*; - -/** - * An unordered collection allowing duplicate elements. - * - * @param <E> - * @author harold - */ -public interface PBag<E> extends PCollection<E> { - //@Override - public PBag<E> plus(E e); - - //@Override - public PBag<E> plusAll(Collection<? extends E> list); - - //@Override - public PBag<E> minus(Object e); - - //@Override - public PBag<E> minusAll(Collection<?> list); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/PCollection.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/PCollection.java b/modules/core/src/main/java/org/pcollections/PCollection.java deleted file mode 100644 index 40cca8d..0000000 --- a/modules/core/src/main/java/org/pcollections/PCollection.java +++ /dev/null @@ -1,56 +0,0 @@ -package org.pcollections; - -import java.util.*; - -/** - * An immutable, persistent collection of non-null elements of type E. - * - * @param <E> - * @author harold - */ -public interface PCollection<E> extends Collection<E> { - - /** - * @param e non-null - * @return a collection which contains e and all of the elements of this - */ - public PCollection<E> plus(E e); - - /** - * @param list contains no null elements - * @return a collection which contains all of the elements of list and this - */ - public PCollection<E> plusAll(Collection<? extends E> list); - - /** - * @param e - * @return this with a single instance of e removed, if e is in this - */ - public PCollection<E> minus(Object e); - - /** - * @param list - * @return this with all elements of list completely removed - */ - public PCollection<E> minusAll(Collection<?> list); - - // TODO public PCollection<E> retainingAll(Collection<?> list); - - @Deprecated - boolean add(E o); - - @Deprecated - boolean remove(Object o); - - @Deprecated - boolean addAll(Collection<? extends E> c); - - @Deprecated - boolean removeAll(Collection<?> c); - - @Deprecated - boolean retainAll(Collection<?> c); - - @Deprecated - void clear(); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/PMap.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/PMap.java b/modules/core/src/main/java/org/pcollections/PMap.java deleted file mode 100644 index a541128..0000000 --- a/modules/core/src/main/java/org/pcollections/PMap.java +++ /dev/null @@ -1,49 +0,0 @@ -package org.pcollections; - -import java.util.*; - -/** - * An immutable, persistent map from non-null keys of type K to non-null values of type V. - * - * @param <K> - * @param <V> - * @author harold - */ -public interface PMap<K, V> extends Map<K, V> { - /** - * @param key non-null - * @param value non-null - * @return a map with the mappings of this but with key mapped to value - */ - public PMap<K, V> plus(K key, V value); - - /** - * @param map - * @return this combined with map, with map's mappings used for any keys in both map and this - */ - public PMap<K, V> plusAll(Map<? extends K, ? extends V> map); - - /** - * @param key - * @return a map with the mappings of this but with no value for key - */ - public PMap<K, V> minus(Object key); - - /** - * @param keys - * @return a map with the mappings of this but with no value for any element of keys - */ - public PMap<K, V> minusAll(Collection<?> keys); - - @Deprecated - V put(K k, V v); - - @Deprecated - V remove(Object k); - - @Deprecated - void putAll(Map<? extends K, ? extends V> m); - - @Deprecated - void clear(); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/POrderedSet.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/POrderedSet.java b/modules/core/src/main/java/org/pcollections/POrderedSet.java deleted file mode 100644 index 940dcfa..0000000 --- a/modules/core/src/main/java/org/pcollections/POrderedSet.java +++ /dev/null @@ -1,25 +0,0 @@ -package org.pcollections; - -import java.util.*; - -/** - * Like {@link org.pcollections.PSet} but preserves insertion order. Persistent equivalent of - * {@link java.util.LinkedHashSet}. - * - * @param <E> - * @author Tassilo Horn <h...@uni-koblenz.de> - */ -public interface POrderedSet<E> extends PSet<E> { - - public POrderedSet<E> plus(E e); - - public POrderedSet<E> plusAll(Collection<? extends E> list); - - public POrderedSet<E> minus(Object e); - - public POrderedSet<E> minusAll(Collection<?> list); - - E get(int index); - - int indexOf(Object o); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/PQueue.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/PQueue.java b/modules/core/src/main/java/org/pcollections/PQueue.java deleted file mode 100644 index 3c3389f..0000000 --- a/modules/core/src/main/java/org/pcollections/PQueue.java +++ /dev/null @@ -1,38 +0,0 @@ -/** - * - */ -package org.pcollections; - -import java.util.*; - -/** - * A persistent queue. - * - * @author mtklein - */ -public interface PQueue<E> extends PCollection<E>, Queue<E> { - // TODO i think PQueue should extend PSequence, - // even though the methods will be inefficient -- H - - /* Guaranteed to stay as a PQueue, i.e. guaranteed-fast methods */ - public PQueue<E> minus(); - - public PQueue<E> plus(E e); - - public PQueue<E> plusAll(Collection<? extends E> list); - - - /* May switch to other PCollection, i.e. may-be-slow methods */ - public PCollection<E> minus(Object e); - - public PCollection<E> minusAll(Collection<?> list); - - @Deprecated - boolean offer(E o); - - @Deprecated - E poll(); - - @Deprecated - E remove(); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/PSequence.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/PSequence.java b/modules/core/src/main/java/org/pcollections/PSequence.java deleted file mode 100644 index b7367cf..0000000 --- a/modules/core/src/main/java/org/pcollections/PSequence.java +++ /dev/null @@ -1,73 +0,0 @@ -package org.pcollections; - -import java.util.*; - -/** - * An immutable, persistent indexed collection. - * - * @param <E> - * @author harold - */ -public interface PSequence<E> extends PCollection<E>, List<E> { - - //@Override - public PSequence<E> plus(E e); - - //@Override - public PSequence<E> plusAll(Collection<? extends E> list); - - /** - * @param i - * @param e - * @return a sequence consisting of the elements of this with e replacing the element at index i. - * @throws IndexOutOfBOundsException if i<0 || i>=this.size() - */ - public PSequence<E> with(int i, E e); - - /** - * @param i - * @param e non-null - * @return a sequence consisting of the elements of this with e inserted at index i. - * @throws IndexOutOfBOundsException if i<0 || i>this.size() - */ - public PSequence<E> plus(int i, E e); - - /** - * @param i - * @param list - * @return a sequence consisting of the elements of this with list inserted at index i. - * @throws IndexOutOfBOundsException if i<0 || i>this.size() - */ - public PSequence<E> plusAll(int i, Collection<? extends E> list); - - /** - * Returns a sequence consisting of the elements of this without the first occurrence of e. - */ - //@Override - public PSequence<E> minus(Object e); - - //@Override - public PSequence<E> minusAll(Collection<?> list); - - /** - * @param i - * @return a sequence consisting of the elements of this with the element at index i removed. - * @throws IndexOutOfBOundsException if i<0 || i>=this.size() - */ - public PSequence<E> minus(int i); - - //@Override - public PSequence<E> subList(int start, int end); - - @Deprecated - boolean addAll(int index, Collection<? extends E> c); - - @Deprecated - E set(int index, E element); - - @Deprecated - void add(int index, E element); - - @Deprecated - E remove(int index); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/PSet.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/PSet.java b/modules/core/src/main/java/org/pcollections/PSet.java deleted file mode 100644 index 52f1314..0000000 --- a/modules/core/src/main/java/org/pcollections/PSet.java +++ /dev/null @@ -1,23 +0,0 @@ -package org.pcollections; - -import java.util.*; - -/** - * An immutable, persistent set, containing no duplicate elements. - * - * @param <E> - * @author harold - */ -public interface PSet<E> extends PCollection<E>, Set<E> { - //@Override - public PSet<E> plus(E e); - - //@Override - public PSet<E> plusAll(Collection<? extends E> list); - - //@Override - public PSet<E> minus(Object e); - - //@Override - public PSet<E> minusAll(Collection<?> list); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/PStack.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/PStack.java b/modules/core/src/main/java/org/pcollections/PStack.java deleted file mode 100644 index 0e75c5c..0000000 --- a/modules/core/src/main/java/org/pcollections/PStack.java +++ /dev/null @@ -1,51 +0,0 @@ -package org.pcollections; - -import java.util.*; - -/** - * An immutable, persistent stack. - * - * @param <E> - * @author harold - */ -public interface PStack<E> extends PSequence<E> { - - /** - * Returns a stack consisting of the elements of this with e prepended. - */ - //@Override - public PStack<E> plus(E e); - - /** - * Returns a stack consisting of the elements of this with list prepended in reverse. - */ - //@Override - public PStack<E> plusAll(Collection<? extends E> list); - - //@Override - public PStack<E> with(int i, E e); - - //@Override - public PStack<E> plus(int i, E e); - - //@Override - public PStack<E> plusAll(int i, Collection<? extends E> list); - - //@Override - public PStack<E> minus(Object e); - - //@Override - public PStack<E> minusAll(Collection<?> list); - - //@Override - public PStack<E> minus(int i); - - //@Override - public PStack<E> subList(int start, int end); - - /** - * @param start - * @return subList(start, this.size()) - */ - public PStack<E> subList(int start); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/PVector.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/PVector.java b/modules/core/src/main/java/org/pcollections/PVector.java deleted file mode 100644 index b098393..0000000 --- a/modules/core/src/main/java/org/pcollections/PVector.java +++ /dev/null @@ -1,45 +0,0 @@ -package org.pcollections; - -import java.util.*; - -/** - * An immutable, persistent list. - * - * @param <E> - * @author harold - */ -public interface PVector<E> extends PSequence<E> { - - /** - * Returns a vector consisting of the elements of this with e appended. - */ - //@Override - public PVector<E> plus(E e); - - /** - * Returns a vector consisting of the elements of this with list appended. - */ - //@Override - public PVector<E> plusAll(Collection<? extends E> list); - - //@Override - public PVector<E> with(int i, E e); - - //@Override - public PVector<E> plus(int i, E e); - - //@Override - public PVector<E> plusAll(int i, Collection<? extends E> list); - - //@Override - public PVector<E> minus(Object e); - - //@Override - public PVector<E> minusAll(Collection<?> list); - - //@Override - public PVector<E> minus(int i); - - //@Override - public PVector<E> subList(int start, int end); -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/SimpleImmutableEntry.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/SimpleImmutableEntry.java b/modules/core/src/main/java/org/pcollections/SimpleImmutableEntry.java deleted file mode 100644 index d5bbbf3..0000000 --- a/modules/core/src/main/java/org/pcollections/SimpleImmutableEntry.java +++ /dev/null @@ -1,146 +0,0 @@ -package org.pcollections; - -import java.util.Map.*; - - -/** - * (Taken from Java 6 code, so pcollections can be Java 5-compatible.) - * <p/> - * An Entry maintaining an immutable key and value. This class - * does not support method <tt>setValue</tt>. This class may be - * convenient in methods that return thread-safe snapshots of - * key-value mappings. - * - * @since 1.6 - */ -/*public*/ final class SimpleImmutableEntry<K, V> - implements Entry<K, V>, java.io.Serializable { - private static final long serialVersionUID = 7138329143949025153L; - - private final K key; - private final V value; - - /** - * Creates an entry representing a mapping from the specified - * key to the specified value. - * - * @param key the key represented by this entry - * @param value the value represented by this entry - */ - public SimpleImmutableEntry(K key, V value) { - this.key = key; - this.value = value; - } - - /** - * Creates an entry representing the same mapping as the - * specified entry. - * - * @param entry the entry to copy - */ - public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) { - this.key = entry.getKey(); - this.value = entry.getValue(); - } - - /** - * Utility method for SimpleEntry and SimpleImmutableEntry. - * Test for equality, checking for nulls. - */ - private static boolean eq(Object o1, Object o2) { - return o1 == null ? o2 == null : o1.equals(o2); - } - - /** - * Returns the key corresponding to this entry. - * - * @return the key corresponding to this entry - */ - public K getKey() { - return key; - } - - /** - * Returns the value corresponding to this entry. - * - * @return the value corresponding to this entry - */ - public V getValue() { - return value; - } - - /** - * Replaces the value corresponding to this entry with the specified - * value (optional operation). This implementation simply throws - * <tt>UnsupportedOperationException</tt>, as this class implements - * an <i>immutable</i> map entry. - * - * @param value new value to be stored in this entry - * @return (Does not return) - * @throws UnsupportedOperationException always - */ - public V setValue(V value) { - throw new UnsupportedOperationException(); - } - - /** - * Compares the specified object with this entry for equality. - * Returns {@code true} if the given object is also a map entry and - * the two entries represent the same mapping. More formally, two - * entries {@code e1} and {@code e2} represent the same mapping - * if<pre> - * (e1.getKey()==null ? - * e2.getKey()==null : - * e1.getKey().equals(e2.getKey())) - * && - * (e1.getValue()==null ? - * e2.getValue()==null : - * e1.getValue().equals(e2.getValue()))</pre> - * This ensures that the {@code equals} method works properly across - * different implementations of the {@code Map.Entry} interface. - * - * @param o object to be compared for equality with this map entry - * @return {@code true} if the specified object is equal to this map - * entry - * @see #hashCode - */ - @Override - public boolean equals(Object o) { - if (!(o instanceof Entry)) - return false; - Entry<?, ?> e = (Entry<?, ?>) o; - return eq(key, e.getKey()) && eq(value, e.getValue()); - } - - /** - * Returns the hash code value for this map entry. The hash code - * of a map entry {@code e} is defined to be: <pre> - * (e.getKey()==null ? 0 : e.getKey().hashCode()) ^ - * (e.getValue()==null ? 0 : e.getValue().hashCode())</pre> - * This ensures that {@code e1.equals(e2)} implies that - * {@code e1.hashCode()==e2.hashCode()} for any two Entries - * {@code e1} and {@code e2}, as required by the general - * contract of {@link Object#hashCode}. - * - * @return the hash code value for this map entry - * @see #equals - */ - @Override - public int hashCode() { - return (key == null ? 0 : key.hashCode()) ^ - (value == null ? 0 : value.hashCode()); - } - - /** - * Returns a String representation of this map entry. This - * implementation returns the string representation of this - * entry's key followed by the equals character ("<tt>=</tt>") - * followed by the string representation of this entry's value. - * - * @return a String representation of this map entry - */ - @Override - public String toString() { - return key + "=" + value; - } -} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/TreePVector.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/pcollections/TreePVector.java b/modules/core/src/main/java/org/pcollections/TreePVector.java deleted file mode 100644 index 996931a..0000000 --- a/modules/core/src/main/java/org/pcollections/TreePVector.java +++ /dev/null @@ -1,155 +0,0 @@ -package org.pcollections; - -import java.util.*; -import java.util.Map.*; - - -/** - * A persistent vector of non-null elements. - * <p/> - * This implementation is backed by an IntTreePMap and - * supports logarithmic-time querying, setting, insertion, - * and removal. - * <p/> - * This implementation is thread-safe (assuming Java's AbstractList is thread-safe) - * although its iterators may not be. - * - * @param <E> - * @author harold - */ -public class TreePVector<E> extends AbstractList<E> implements PVector<E> { - //// STATIC FACTORY METHODS //// - private static final TreePVector<Object> EMPTY = new TreePVector<Object>(IntTreePMap.empty()); - //// PRIVATE CONSTRUCTORS //// - private final IntTreePMap<E> map; - - private TreePVector(final IntTreePMap<E> map) { - this.map = map; - } - - /** - * @param <E> - * @return an empty vector - */ - @SuppressWarnings("unchecked") - public static <E> TreePVector<E> empty() { - return (TreePVector<E>) EMPTY; - } - - /** - * @param <E> - * @param e - * @return empty().plus(e) - */ - public static <E> TreePVector<E> singleton(final E e) { - return TreePVector.<E>empty().plus(e); - } - - /** - * @param <E> - * @param list - * @return empty().plusAll(list) - */ - @SuppressWarnings("unchecked") - public static <E> TreePVector<E> from(final Collection<? extends E> list) { - if (list instanceof TreePVector) - return (TreePVector<E>) list; //(actually we only know it's TreePVector<? extends E>) - // but that's good enough for an immutable - // (i.e. we can't mess someone else up by adding the wrong type to it) - return TreePVector.<E>empty().plusAll(list); - } - - //// REQUIRED METHODS FROM AbstractList //// - @Override - public int size() { - return map.size(); - } - - @Override - public E get(final int index) { - if (index < 0 || index >= size()) - throw new IndexOutOfBoundsException(); - return map.get(index); - } - - - //// OVERRIDDEN METHODS FROM AbstractList //// - @Override - public Iterator<E> iterator() { - return map.values().iterator(); - } - - @Override - public TreePVector<E> subList(final int start, final int end) { - final int size = size(); - if (start < 0 || end > size || start > end) - throw new IndexOutOfBoundsException(); - if (start == end) - return empty(); - if (start == 0) { - if (end == size) return this; - // remove from end: - return this.minus(size - 1).subList(start, end); - } - // remove from start: - return this.minus(0).subList(start - 1, end - 1); - } - - - ////IMPLEMENTED METHODS OF PVector //// - public TreePVector<E> plus(final E e) { - return new TreePVector<E>(map.plus(size(), e)); - } - - public TreePVector<E> plus(final int i, final E e) { - if (i < 0 || i > size()) - throw new IndexOutOfBoundsException(); - return new TreePVector<E>(map.withKeysChangedAbove(i, 1).plus(i, e)); - } - - public TreePVector<E> minus(final Object e) { - for (Entry<Integer, E> entry : map.entrySet()) - if (entry.getValue().equals(e)) - return minus((int) entry.getKey()); - return this; - } - - public TreePVector<E> minus(final int i) { - if (i < 0 || i >= size()) - throw new IndexOutOfBoundsException(); - return new TreePVector<E>(map.minus(i).withKeysChangedAbove(i, -1)); - } - - public TreePVector<E> plusAll(final Collection<? extends E> list) { - TreePVector<E> result = this; - for (E e : list) - result = result.plus(e); - return result; - } - - public TreePVector<E> minusAll(final Collection<?> list) { - TreePVector<E> result = this; - for (Object e : list) - result = result.minus(e); - return result; - } - - public TreePVector<E> plusAll(int i, final Collection<? extends E> list) { - if (i < 0 || i > size()) - throw new IndexOutOfBoundsException(); - if (list.size() == 0) - return this; - IntTreePMap<E> map = this.map.withKeysChangedAbove(i, list.size()); - for (E e : list) - map = map.plus(i++, e); - return new TreePVector<E>(map); - } - - public PVector<E> with(final int i, final E e) { - if (i < 0 || i >= size()) - throw new IndexOutOfBoundsException(); - IntTreePMap<E> map = this.map.plus(i, e); - if (map == this.map) return this; - return new TreePVector<E>(map); - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/resources/META-INF/classnames.properties ---------------------------------------------------------------------- diff --git a/modules/core/src/main/resources/META-INF/classnames.properties b/modules/core/src/main/resources/META-INF/classnames.properties index 68765df..7b3c730 100644 --- a/modules/core/src/main/resources/META-INF/classnames.properties +++ b/modules/core/src/main/resources/META-INF/classnames.properties @@ -1618,5 +1618,3 @@ org.jdk8.backport.ConcurrentLinkedHashMap$WriteThroughEntry org.jdk8.backport.LongAdder org.jdk8.backport.Striped64 org.jdk8.backport.ThreadLocalRandom8 -org.pcollections.MapPSet$In -org.pcollections.SimpleImmutableEntry http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/test/java/org/apache/ignite/lang/GridImmutableCollectionsPerfomanceTest.java ---------------------------------------------------------------------- diff --git a/modules/core/src/test/java/org/apache/ignite/lang/GridImmutableCollectionsPerfomanceTest.java b/modules/core/src/test/java/org/apache/ignite/lang/GridImmutableCollectionsPerfomanceTest.java deleted file mode 100644 index fe8334f..0000000 --- a/modules/core/src/test/java/org/apache/ignite/lang/GridImmutableCollectionsPerfomanceTest.java +++ /dev/null @@ -1,120 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.ignite.lang; - -import org.apache.ignite.internal.util.typedef.internal.*; -import org.pcollections.*; - -import java.util.*; - -/** - * - */ -public class GridImmutableCollectionsPerfomanceTest { - /** */ - private static final Random RND = new Random(); - - /** */ - private static final int ITER_CNT = 100000; - - /** - * @param args Args. - */ - public static void main(String[] args) { - for (int i = 0; i < 20; i++) { - for (int j = 0; j < 5; j++) { - // testArrayList(); - - testPVector(); - - testPVectorRemove(); - } - } - } - - /** - * - */ - private static void testArrayList() { - System.gc(); - - Collection<Integer> list = new ArrayList<>(); - - long start = U.currentTimeMillis(); - - for (int i = 0; i < ITER_CNT; i++) { - Integer[] arr = new Integer[list.size() + 1]; - - list.toArray(arr); - - arr[arr.length - 1] = RND.nextInt(100000); - - Collection<Integer> cp = Arrays.asList(arr); - - assert cp.size() - 1 == list.size(); - - list = cp; - } - - assert list.size() == ITER_CNT; - - System.out.println("Array list time: " + (U.currentTimeMillis() - start)); - } - - /** - * - */ - private static void testPVector() { - System.gc(); - - long start = U.currentTimeMillis(); - - TreePVector<Integer> list = TreePVector.empty(); - - for (int i = 0; i < ITER_CNT; i++) { - TreePVector<Integer> cp = list.plus(RND.nextInt(100000)); - - assert cp.size() - 1 == list.size(); - - list = cp; - } - - assert list.size() == ITER_CNT; - - System.out.println("testPVector time: " + (U.currentTimeMillis() - start)); - } - - /** - * - */ - private static void testPVectorRemove() { - System.gc(); - - long start = U.currentTimeMillis(); - - TreePVector<Integer> list = TreePVector.empty(); - - for (int i = 0; i < ITER_CNT; i++) - list = list.plus(RND.nextInt(100)); - - for (int i = 0; i < ITER_CNT; i++) - list = list.minus(new Integer(RND.nextInt(100))); - - System.out.println("testPVectorRemove time: " + (U.currentTimeMillis() - start)); - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/test/java/org/apache/ignite/lang/utils/GridPCollectionsTest.java ---------------------------------------------------------------------- diff --git a/modules/core/src/test/java/org/apache/ignite/lang/utils/GridPCollectionsTest.java b/modules/core/src/test/java/org/apache/ignite/lang/utils/GridPCollectionsTest.java deleted file mode 100644 index 3dee9b7..0000000 --- a/modules/core/src/test/java/org/apache/ignite/lang/utils/GridPCollectionsTest.java +++ /dev/null @@ -1,54 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.ignite.lang.utils; - -import org.apache.ignite.testframework.junits.common.*; -import org.pcollections.*; - -/** - * - */ -public class GridPCollectionsTest extends GridCommonAbstractTest { - /** - * - */ - public void testPvector() { - PVector<Integer> vector = TreePVector.empty(); - - for (int i = 0; i < 10; i++) - vector = vector.plus(i); - - assert vector.size() == 10; - - for (int i = 0; i < 10; i++) - assert vector.contains(i); - - for (int i = 0; i < 5; i++) - vector = vector.minus(new Integer(i)); - - assert vector.size() == 5; - - for (int i = 0; i < 10; i++) - assert !vector.contains(i) || i >= 5; - - for (int i = 0; i < 10; i++) - vector = vector.minus(new Integer(i)); - - assert vector.isEmpty(); - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/test/java/org/apache/ignite/lang/utils/GridTrieMapSelfTest.java ---------------------------------------------------------------------- diff --git a/modules/core/src/test/java/org/apache/ignite/lang/utils/GridTrieMapSelfTest.java b/modules/core/src/test/java/org/apache/ignite/lang/utils/GridTrieMapSelfTest.java deleted file mode 100644 index f6d8121..0000000 --- a/modules/core/src/test/java/org/apache/ignite/lang/utils/GridTrieMapSelfTest.java +++ /dev/null @@ -1,242 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.ignite.lang.utils; - -import com.romix.scala.collection.concurrent.*; -import org.apache.ignite.internal.util.lang.*; -import org.apache.ignite.internal.util.typedef.*; -import org.apache.ignite.lang.*; -import org.apache.ignite.testframework.junits.common.*; -import org.jdk8.backport.*; -import org.jetbrains.annotations.*; - -import java.util.*; -import java.util.concurrent.*; -import java.util.concurrent.atomic.*; -import java.util.concurrent.locks.*; - -/** - * Tests for {@code TrieMap}. - */ -public class GridTrieMapSelfTest extends GridCommonAbstractTest { - /** */ - private static final int OPS_CNT = 1000000; - - /** */ - private static final int MAIN_ITER_CNT = 5; - - /** */ - private static final int THREAD_CNT = Runtime.getRuntime().availableProcessors(); - - /** */ - private Map<Integer,Integer> map; - - /** - * @throws Exception If failed. - */ - @SuppressWarnings("unchecked") - public void testOpsSpeed() throws Exception { - info("Test operations without clone: "); - - for (int i = 0; i < MAIN_ITER_CNT; i++) { - map = new TrieMap<>(); - - info("Trie map ops time: " + runOps(OPS_CNT, THREAD_CNT, null)); - - map = new ConcurrentHashMap8<>(); - - info("New map ops time: " + runOps(OPS_CNT, THREAD_CNT, null)); - - map = new ConcurrentHashMap<>(); - - info("Jdk6 map ops time: " + runOps(OPS_CNT, THREAD_CNT, null)); - } - - info("Test operations with clone: "); - - for (int i = 0; i < MAIN_ITER_CNT; i++) { - map = new TrieMap<>(); - - info("Trie map ops time: " + runOps(OPS_CNT, THREAD_CNT, new C1<Map, Map>() { - @Override public Map apply(Map e) { - return ((TrieMap)e).readOnlySnapshot(); - } - })); - - map = new ConcurrentHashMap8<>(); - - info("New map ops time: " + runOps(OPS_CNT, THREAD_CNT, new C1<Map, Map>() { - @Override public Map apply(Map e) { - return new ConcurrentHashMap8(e); - } - })); - - map = new ConcurrentHashMap<>(); - - info("Jdk6 map ops time: " + runOps(OPS_CNT, THREAD_CNT, new C1<Map, Map>() { - @Override public Map apply(Map e) { - return new ConcurrentHashMap(e); - } - })); - } - } - - /** - * - */ - public void _testClear() { - new TrieMap<>().clear(); - } - - /** - * @param iterCnt Iterations count. - * @param threadCnt Threads count. - * @param cloner Cloner. - * @return Time taken. - * @throws Exception If failed. - */ - private long runOps(final int iterCnt, int threadCnt, @Nullable final IgniteClosure<Map, Map> cloner) - throws Exception { - long start = System.currentTimeMillis(); - - final ReadWriteLock lock = cloner != null ? new ReentrantReadWriteLock() : null; - final GridTuple<Integer> lower = F.t(0); - final AtomicBoolean cloneGuard = cloner != null ? new AtomicBoolean() : null; - - multithreaded(new Callable<Object>() { - @SuppressWarnings("TooBroadScope") - @Override public Object call() throws Exception { - boolean clone = cloneGuard != null && cloneGuard.compareAndSet(false, true); - - ThreadLocalRandom8 rnd = ThreadLocalRandom8.current(); - - for (int i = 0; i < iterCnt; i++) { - int lowerBound; - - readLock(lock); - - try { - lowerBound = lower.get(); - - // Put random. - map.put(rnd.nextInt(lowerBound, lowerBound + 10000), 0); - - // Read random. - map.get(rnd.nextInt(lowerBound, lowerBound + 10000)); - - // Remove random. - map.remove(rnd.nextInt(lowerBound, lowerBound + 10000)); - } - finally { - readUnlock(lock); - } - - if (clone && i % 1000 == 0) { - Map map0; - - writeLock(lock); - - try { - map0 = cloner.apply(map); - - lower.set(lowerBound + 20000); - } - finally { - writeUnlock(lock); - } - - for (Object o : map0.keySet()) { - int j = (Integer)o; - - assert j <= lowerBound + 10000; - } - } - } - - return null; - } - }, threadCnt); - - return System.currentTimeMillis() - start; - } - - /** - * @param lock Lock. - */ - @SuppressWarnings("LockAcquiredButNotSafelyReleased") - private void readLock(@Nullable ReadWriteLock lock) { - if (lock == null) - return; - - lock.readLock().lock(); - } - - /** - * @param lock Lock. - */ - private void readUnlock(@Nullable ReadWriteLock lock) { - if (lock == null) - return; - - lock.readLock().unlock(); - } - - /** - * @param lock Lock. - */ - @SuppressWarnings("LockAcquiredButNotSafelyReleased") - private void writeLock(@Nullable ReadWriteLock lock) { - lock.writeLock().lock(); - } - - /** - * @param lock Lock. - */ - private void writeUnlock(@Nullable ReadWriteLock lock) { - lock.writeLock().unlock(); - } - - /** - * @throws Exception If failed. - */ - @SuppressWarnings("ResultOfObjectAllocationIgnored") - public void testCreationTime() throws Exception { - for (int i = 0; i < 5; i++) { - long now = System.currentTimeMillis(); - - for (int j = 0; j < 1000000; j++) - new TrieMap<Integer, Integer>(); - - info("Trie map creation time: " + (System.currentTimeMillis() - now)); - - now = System.currentTimeMillis(); - - for (int j = 0; j < 1000000; j++) - new ConcurrentHashMap8<Integer, Integer>(); - - info("New map creation time: " + (System.currentTimeMillis() - now)); - - now = System.currentTimeMillis(); - - for (int j = 0; j < 1000000; j++) - new ConcurrentHashMap<Integer, Integer>(); - - info("Jdk6 map creation time: " + (System.currentTimeMillis() - now)); - } - } -} http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/pom.xml ---------------------------------------------------------------------- diff --git a/pom.xml b/pom.xml index d2e42eb..6883e8b 100644 --- a/pom.xml +++ b/pom.xml @@ -581,10 +581,8 @@ <exclude>**/keystore/*.pfx</exclude><!--bin-files--> <!--special excludes--> <exclude>DEVNOTES.txt</exclude> - <exclude>src/main/java/com/romix/scala/**</exclude><!--Apache License, Version 2.0 (Copyright)--> <exclude>src/main/java/org/apache/ignite/internal/util/offheap/unsafe/GridOffHeapSnapTreeMap.java</exclude><!--Stanford University license--> <exclude>src/main/java/org/apache/ignite/internal/util/snaptree/*.java</exclude><!--Stanford University license--> - <exclude>src/main/java/org/pcollections/**</exclude><!--MIT license--> <exclude>src/main/java/org/jdk8/backport/*.java</exclude> <exclude>src/test/java/org/apache/ignite/p2p/p2p.properties</exclude><!--test depends on file content--> <exclude>src/test/resources/log/ignite.log.tst</exclude><!--test resource--> @@ -951,7 +949,7 @@ <link>http://hadoop.apache.org/docs/current/api/</link> </links> <stylesheetfile>${basedir}/assembly/docfiles/javadoc.css</stylesheetfile> - <excludePackageNames>com.*:org.jetbrains.*:org.pcollections:*.jdk8:*.tests:*.tools:*.typedef:*.examples:*.client:*.kernal:*.internal:*.util:*.dr:*.spi.discovery.tcp.messages:*.spi.discovery.tcp.internal:*.spi.deployment.uri.scanners:*.spi.deployment.uri.tasks:*.spi.indexing.h2.opt:org.apache.ignite.portables:org.apache.ignite.yardstick:org.apache.ignite.schema.*:org.apache.ignite.codegen</excludePackageNames> + <excludePackageNames>com.*:org.jetbrains.*:*.jdk8:*.tests:*.tools:*.typedef:*.examples:*.client:*.kernal:*.internal:*.util:*.dr:*.spi.discovery.tcp.messages:*.spi.discovery.tcp.internal:*.spi.deployment.uri.scanners:*.spi.deployment.uri.tasks:*.spi.indexing.h2.opt:org.apache.ignite.portables:org.apache.ignite.yardstick:org.apache.ignite.schema.*:org.apache.ignite.codegen</excludePackageNames> <groups> <group> <title>Common Grid APIs</title>
