ignite-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sboi...@apache.org
Subject [20/50] [abbrv] incubator-ignite git commit: # IGNITE-515 removed pcollection and romix.
Date Mon, 23 Mar 2015 17:30:50 GMT
http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/com/romix/scala/collection/concurrent/TrieMap.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/com/romix/scala/collection/concurrent/TrieMap.java b/modules/core/src/main/java/com/romix/scala/collection/concurrent/TrieMap.java
deleted file mode 100644
index b709632..0000000
--- a/modules/core/src/main/java/com/romix/scala/collection/concurrent/TrieMap.java
+++ /dev/null
@@ -1,1826 +0,0 @@
-/*
- Copyright (C) Roman Levenstein. All Rights Reserved.
-
- Licensed 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 com.romix.scala.collection.concurrent;
-
-import com.romix.scala.*;
-
-import java.util.*;
-import java.util.concurrent.*;
-import java.util.concurrent.atomic.*;
-
-/**
- * This is a port of Scala's TrieMap class from the Scala Collections library.
- *
- * @param <K>
- * @param <V>
- * @author Roman Levenstein <romixlev@gmail.com>
- */
-@SuppressWarnings({"unchecked", "rawtypes", "unused"})
-public class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {
-    /**
-     * Only used for ctrie serialization.
-     */
-    // @SerialVersionUID(0L - 7237891413820527142L)
-    private static long TrieMapSerializationEnd = 0L - 7237891413820527142L;
-    /**
-     * EntrySet
-     */
-    private final EntrySet entrySet = new EntrySet();
-    AtomicReferenceFieldUpdater<INodeBase, MainNode> inodeupdater = AtomicReferenceFieldUpdater.newUpdater(INodeBase.class, MainNode.class, "mainnode");
-
-    // static class MangledHashing<K> extends Hashing<K> {
-    // int hash(K k) {
-    // return util.hashing.byteswap32(k);
-    // }
-    // }
-    private Object r;
-    private AtomicReferenceFieldUpdater<TrieMap, Object> rtupd;
-    private Hashing<K> hashf;
-    private Equiv<K> ef;
-    private Hashing<K> hashingobj;
-    private Equiv<K> equalityobj;
-    private AtomicReferenceFieldUpdater<TrieMap, Object> rootupdater;
-    private volatile Object root;
-
-    TrieMap(final Object r, final AtomicReferenceFieldUpdater<TrieMap, Object> rtupd, final Hashing<K> hashf, final Equiv<K> ef) {
-        this.r = r;
-        this.rtupd = rtupd;
-        this.hashf = hashf;
-        this.ef = ef;
-        this.hashingobj = (hashf instanceof Default) ? hashf : hashf;
-        equalityobj = ef;
-        rootupdater = rtupd;
-        root = r;
-    }
-
-    public TrieMap(final Hashing<K> hashf, final Equiv<K> ef) {
-        this(INode.newRootNode(), AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root"), hashf, ef);
-    }
-
-    public TrieMap() {
-        this(new Default<K>(), Equiv.universal);
-    }
-
-    public static <K, V> TrieMap<K, V> empty() {
-        return new TrieMap<K, V>();
-    }
-
-    Hashing<K> hashing() {
-        return hashingobj;
-    }
-
-    Equiv<K> equality() {
-        return equalityobj;
-    }
-
-    final boolean CAS_ROOT(Object ov, Object nv) {
-        return rootupdater.compareAndSet(this, ov, nv);
-    }
-
-    // FIXME: abort = false by default
-    final INode<K, V> readRoot(boolean abort) {
-        return RDCSS_READ_ROOT(abort);
-    }
-
-    final INode<K, V> readRoot() {
-        return RDCSS_READ_ROOT(false);
-    }
-
-    final INode<K, V> RDCSS_READ_ROOT() {
-        return RDCSS_READ_ROOT(false);
-    }
-
-    final INode<K, V> RDCSS_READ_ROOT(boolean abort) {
-        Object r = /* READ */root;
-        if (r instanceof INode)
-            return (INode<K, V>) r;
-        else if (r instanceof RDCSS_Descriptor) {
-            return RDCSS_Complete(abort);
-        }
-        throw new RuntimeException("Should not happen");
-    }
-
-    private final INode<K, V> RDCSS_Complete(final boolean abort) {
-        while (true) {
-            Object v = /* READ */root;
-            if (v instanceof INode)
-                return (INode<K, V>) v;
-            else if (v instanceof RDCSS_Descriptor) {
-                RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
-                INode<K, V> ov = desc.old;
-                MainNode<K, V> exp = desc.expectedmain;
-                INode<K, V> nv = desc.nv;
-
-                if (abort) {
-                    if (CAS_ROOT(desc, ov))
-                        return ov;
-                    else {
-                        // return RDCSS_Complete (abort);
-                        // tailrec
-                        continue;
-                    }
-                }
-                else {
-                    MainNode<K, V> oldmain = ov.gcasRead(this);
-                    if (oldmain == exp) {
-                        if (CAS_ROOT(desc, nv)) {
-                            desc.committed = true;
-                            return nv;
-                        }
-                        else {
-                            // return RDCSS_Complete (abort);
-                            // tailrec
-                            continue;
-                        }
-                    }
-                    else {
-                        if (CAS_ROOT(desc, ov))
-                            return ov;
-                        else {
-                            // return RDCSS_Complete (abort);
-                            // tailrec
-                            continue;
-
-                        }
-                    }
-                }
-            }
-
-            throw new RuntimeException("Should not happen");
-        }
-    }
-
-    private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
-        RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<K, V>(ov, expectedmain, nv);
-        if (CAS_ROOT(ov, desc)) {
-            RDCSS_Complete(false);
-            return /* READ */desc.committed;
-        }
-        else
-            return false;
-    }
-
-    private void inserthc(final K k, final int hc, final V v) {
-        while (true) {
-            INode<K, V> r = RDCSS_READ_ROOT();
-            if (!r.rec_insert(k, v, hc, 0, null, r.gen, this)) {
-                // inserthc (k, hc, v);
-                // tailrec
-                continue;
-            }
-            break;
-        }
-    }
-
-    private Option<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
-        while (true) {
-            INode<K, V> r = RDCSS_READ_ROOT();
-
-            Option<V> ret = r.rec_insertif(k, v, hc, cond, 0, null, r.gen, this);
-            if (ret == null) {
-                // return insertifhc (k, hc, v, cond);
-                // tailrec
-                continue;
-            }
-            else
-                return ret;
-        }
-    }
-
-    private Object lookuphc(final K k, final int hc) {
-        while (true) {
-            INode<K, V> r = RDCSS_READ_ROOT();
-            Object res = r.rec_lookup(k, hc, 0, null, r.gen, this);
-            if (res == INodeBase.RESTART) {
-                // return lookuphc (k, hc);
-                // tailrec
-                continue;
-            }
-            else
-                return res;
-        }
-    }
-
-    /* internal methods */
-
-    // private void writeObject(java.io.ObjectOutputStream out) {
-    // out.writeObject(hashf);
-    // out.writeObject(ef);
-    //
-    // Iterator it = iterator();
-    // while (it.hasNext) {
-    // val (k, v) = it.next();
-    // out.writeObject(k);
-    // out.writeObject(v);
-    // }
-    // out.writeObject(TrieMapSerializationEnd);
-    // }
-    //
-    // private TrieMap readObject(java.io.ObjectInputStream in) {
-    // root = INode.newRootNode();
-    // rootupdater = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class,
-    // Object.class, "root");
-    //
-    // hashingobj = in.readObject();
-    // equalityobj = in.readObject();
-    //
-    // Object obj = null;
-    // do {
-    // obj = in.readObject();
-    // if (obj != TrieMapSerializationEnd) {
-    // K k = (K)obj;
-    // V = (V)in.readObject();
-    // update(k, v);
-    // }
-    // } while (obj != TrieMapSerializationEnd);
-    // }
-
-    private Option<V> removehc(final K k, final V v, final int hc) {
-        while (true) {
-            INode<K, V> r = RDCSS_READ_ROOT();
-            Option<V> res = r.rec_remove(k, v, hc, 0, null, r.gen, this);
-            if (res != null)
-                return res;
-            else {
-                // return removehc (k, v, hc);
-                // tailrec
-                continue;
-            }
-        }
-    }
-
-    public String string() {
-        // RDCSS_READ_ROOT().string(0);
-        return "Root";
-    }
-
-    final boolean isReadOnly() {
-        return rootupdater == null;
-    }
-
-    final boolean nonReadOnly() {
-        return rootupdater != null;
-    }
-
-    /**
-     * Returns a snapshot of this TrieMap. This operation is lock-free and
-     * linearizable.
-     * <p/>
-     * The snapshot is lazily updated - the first time some branch in the
-     * snapshot or this TrieMap are accessed, they are rewritten. This means
-     * that the work of rebuilding both the snapshot and this TrieMap is
-     * distributed across all the threads doing updates or accesses subsequent
-     * to the snapshot creation.
-     */
-
-    final public TrieMap<K, V> snapshot() {
-        while (true) {
-            INode<K, V> r = RDCSS_READ_ROOT();
-            final MainNode<K, V> expmain = r.gcasRead(this);
-            if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this)))
-                return new TrieMap<K, V>(r.copyToGen(new Gen(), this), rootupdater, hashing(), equality());
-            else {
-                // return snapshot ();
-                // tailrec
-                continue;
-            }
-        }
-    }
-
-    /**
-     * Returns a read-only snapshot of this TrieMap. This operation is lock-free
-     * and linearizable.
-     * <p/>
-     * The snapshot is lazily updated - the first time some branch of this
-     * TrieMap are accessed, it is rewritten. The work of creating the snapshot
-     * is thus distributed across subsequent updates and accesses on this
-     * TrieMap by all threads. Note that the snapshot itself is never rewritten
-     * unlike when calling the `snapshot` method, but the obtained snapshot
-     * cannot be modified.
-     * <p/>
-     * This method is used by other methods such as `size` and `iterator`.
-     */
-    final public TrieMap<K, V> readOnlySnapshot() {
-        // Is it a snapshot of a read-only snapshot?
-        if (!nonReadOnly())
-            return this;
-
-        while (true) {
-            INode<K, V> r = RDCSS_READ_ROOT();
-            MainNode<K, V> expmain = r.gcasRead(this);
-            if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this)))
-                return new TrieMap<K, V>(r, null, hashing(), equality());
-            else {
-                // return readOnlySnapshot ();
-                continue;
-            }
-        }
-    }
-
-    final public void clear() {
-        while (true) {
-            INode<K, V> r = RDCSS_READ_ROOT();
-            if (!RDCSS_ROOT(r, r.gcasRead(this), INode.<K, V>newRootNode())) {
-                continue;
-            }
-            else {
-                return;
-            }
-        }
-    }
-
-    // @inline
-    int computeHash(K k) {
-        return hashingobj.hash(k);
-    }
-
-    final V lookup(K k) {
-        int hc = computeHash(k);
-//        return (V) lookuphc (k, hc);
-        Object o = lookuphc(k, hc);
-        if (o instanceof Some) {
-            return ((Some<V>) o).get();
-        }
-        else if (o instanceof None)
-            return null;
-        else
-            return (V) o;
-    }
-
-    final V apply(K k) {
-        int hc = computeHash(k);
-        Object res = lookuphc(k, hc);
-        if (res == null)
-            throw new NoSuchElementException();
-        else
-            return (V) res;
-    }
-
-    final public V get(Object k) {
-        return lookup((K) k);
-    }
-
-    final public Option<V> putOpt(Object key, Object value) {
-        int hc = computeHash((K) key);
-        return insertifhc((K) key, hc, (V) value, null);
-    }
-
-    /* public methods */
-
-    // public Seq<V> seq() {
-    // return this;
-    // }
-
-    // override def par = new ParTrieMap(this)
-
-    // static TrieMap empty() {
-    // return new TrieMap();
-    // }
-
-    final public V put(Object key, Object value) {
-        int hc = computeHash((K) key);
-        Option<V> ov = insertifhc((K) key, hc, (V) value, null);
-        if (ov instanceof Some) {
-            Some<V> sv = (Some<V>) ov;
-            return sv.get();
-        }
-        else
-            return null;
-    }
-
-    final public void update(K k, V v) {
-        int hc = computeHash(k);
-        inserthc(k, hc, v);
-    }
-
-    final public TrieMap<K, V> add(K k, V v) {
-        update(k, v);
-        return this;
-    }
-
-    final Option<V> removeOpt(K k) {
-        int hc = computeHash(k);
-        return removehc(k, (V) null, hc);
-    }
-
-    final public V remove(Object k) {
-        int hc = computeHash((K) k);
-        Option<V> ov = removehc((K) k, (V) null, hc);
-        if (ov instanceof Some) {
-            Some<V> sv = (Some<V>) ov;
-            return sv.get();
-        }
-        else
-            return null;
-    }
-
-    final public Option<V> putIfAbsentOpt(K k, V v) {
-        int hc = computeHash(k);
-        return insertifhc(k, hc, v, INode.KEY_ABSENT);
-    }
-
-    final public V putIfAbsent(Object k, Object v) {
-        int hc = computeHash((K) k);
-        Option<V> ov = insertifhc((K) k, hc, (V) v, INode.KEY_ABSENT);
-        if (ov instanceof Some) {
-            Some<V> sv = (Some<V>) ov;
-            return sv.get();
-        }
-        else
-            return null;
-    }
-
-    public boolean remove(Object k, Object v) {
-        int hc = computeHash((K) k);
-        return removehc((K) k, (V) v, hc).nonEmpty();
-    }
-
-//    final public Option<V> get (K k) {
-//        int hc = computeHash (k);
-//        return Option.makeOption ((V)lookuphc (k, hc));
-//    }
-
-    public boolean replace(K k, V oldvalue, V newvalue) {
-        int hc = computeHash(k);
-        return insertifhc(k, hc, newvalue, (Object) oldvalue).nonEmpty();
-    }
-
-    public Option<V> replaceOpt(K k, V v) {
-        int hc = computeHash(k);
-        return insertifhc(k, hc, v, INode.KEY_PRESENT);
-    }
-
-    public V replace(Object k, Object v) {
-        int hc = computeHash((K) k);
-        Option<V> ov = insertifhc((K) k, hc, (V) v, INode.KEY_PRESENT);
-        if (ov instanceof Some) {
-            Some<V> sv = (Some<V>) ov;
-            return sv.get();
-        }
-        else
-            return null;
-    }
-
-    /**
-     * Return an iterator over a TrieMap.
-     * <p/>
-     * If this is a read-only snapshot, it would return a read-only iterator.
-     * <p/>
-     * If it is the original TrieMap or a non-readonly snapshot, it would return
-     * an iterator that would allow for updates.
-     *
-     * @return iterator
-     */
-    public Iterator<Entry<K, V>> iterator() {
-        if (!nonReadOnly())
-            return readOnlySnapshot().readOnlyIterator();
-        else
-            return new TrieMapIterator<K, V>(0, this);
-    }
-
-    /**
-     * Return an iterator over a TrieMap.
-     * This is a read-only iterator.
-     *
-     * @return iterator
-     */
-    public Iterator<Entry<K, V>> readOnlyIterator() {
-        if (nonReadOnly())
-            return readOnlySnapshot().readOnlyIterator();
-        else
-            return new TrieMapReadOnlyIterator<K, V>(0, this);
-    }
-
-    private int cachedSize() {
-        INode<K, V> r = RDCSS_READ_ROOT();
-        return r.cachedSize(this);
-    }
-
-    public int size() {
-        if (nonReadOnly())
-            return readOnlySnapshot().size();
-        else
-            return cachedSize();
-    }
-
-//    final public TrieMap<K, V> remove (Object k) {
-//        removeOpt ((K)k);
-//        return this;
-//    }
-
-    String stringPrefix() {
-        return "TrieMap";
-    }
-
-    public boolean containsKey(Object key) {
-        return lookup((K) key) != null;
-    }
-
-    @Override
-    public Set<Entry<K, V>> entrySet() {
-        return entrySet;
-    }
-
-    private interface KVNode<K, V> {
-        Entry<K, V> kvPair();
-    }
-
-    private static interface Hashing<K> {
-        public int hash(K k);
-    }
-
-    static class INode<K, V> extends INodeBase<K, V> {
-        static Object KEY_PRESENT = new Object();
-        static Object KEY_ABSENT = new Object();
-
-        public INode(MainNode<K, V> bn, Gen g) {
-            super(g);
-            WRITE(bn);
-        }
-
-        public INode(Gen g) {
-            this(null, g);
-        }
-
-        static <K, V> INode<K, V> newRootNode() {
-            Gen gen = new Gen();
-            CNode<K, V> cn = new CNode<K, V>(0, new BasicNode[]{}, gen);
-            return new INode<K, V>(cn, gen);
-        }
-
-        final void WRITE(final MainNode<K, V> nval) {
-            INodeBase.updater.set(this, nval);
-        }
-
-        final boolean CAS(final MainNode<K, V> old, final MainNode<K, V> n) {
-            return INodeBase.updater.compareAndSet(this, old, n);
-        }
-
-        final MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
-            return GCAS_READ(ct);
-        }
-
-        final MainNode<K, V> GCAS_READ(TrieMap<K, V> ct) {
-            MainNode<K, V> m = /* READ */mainnode;
-            MainNode<K, V> prevval = /* READ */m.prev;
-            if (prevval == null)
-                return m;
-            else
-                return GCAS_Complete(m, ct);
-        }
-
-        private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<K, V> ct) {
-            while (true) {
-                if (m == null)
-                    return null;
-                else {
-                    // complete the GCAS
-                    MainNode<K, V> prev = /* READ */m.prev;
-                    INode<K, V> ctr = ct.readRoot(true);
-
-                    if (prev == null)
-                        return m;
-
-                    if (prev instanceof FailedNode) {
-                        // try to commit to previous value
-                        FailedNode<K, V> fn = (FailedNode<K, V>) prev;
-                        if (CAS(m, fn.prev))
-                            return fn.prev;
-                        else {
-                            // Tailrec
-                            // return GCAS_Complete (/* READ */mainnode, ct);
-                            m = /* READ */mainnode;
-                            continue;
-                        }
-                    }
-                    else if (prev instanceof MainNode) {
-                        // Assume that you've read the root from the generation
-                        // G.
-                        // Assume that the snapshot algorithm is correct.
-                        // ==> you can only reach nodes in generations <= G.
-                        // ==> `gen` is <= G.
-                        // We know that `ctr.gen` is >= G.
-                        // ==> if `ctr.gen` = `gen` then they are both equal to
-                        // G.
-                        // ==> otherwise, we know that either `ctr.gen` > G,
-                        // `gen` <
-                        // G,
-                        // or both
-                        if ((ctr.gen == gen) && ct.nonReadOnly()) {
-                            // try to commit
-                            if (m.CAS_PREV(prev, null))
-                                return m;
-                            else {
-                                // return GCAS_Complete (m, ct);
-                                // tailrec
-                                continue;
-                            }
-                        }
-                        else {
-                            // try to abort
-                            m.CAS_PREV(prev, new FailedNode<K, V>(prev));
-                            return GCAS_Complete(/* READ */mainnode, ct);
-                        }
-                    }
-                }
-                throw new RuntimeException("Should not happen");
-            }
-        }
-
-        final boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
-            n.WRITE_PREV(old);
-            if (CAS(old, n)) {
-                GCAS_Complete(n, ct);
-                return /* READ */n.prev == null;
-            }
-            else
-                return false;
-        }
-
-        private boolean equal(final K k1, final K k2, final TrieMap<K, V> ct) {
-            return ct.equality().equiv(k1, k2);
-        }
-
-        private INode<K, V> inode(final MainNode<K, V> cn) {
-            INode<K, V> nin = new INode<K, V>(gen);
-            nin.WRITE(cn);
-            return nin;
-        }
-
-        final INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
-            INode<K, V> nin = new INode<K, V>(ngen);
-            MainNode<K, V> main = GCAS_READ(ct);
-            nin.WRITE(main);
-            return nin;
-        }
-
-        /**
-         * Inserts a key value pair, overwriting the old pair if the keys match.
-         *
-         * @return true if successful, false otherwise
-         */
-        final boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
-            while (true) {
-                MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
-
-                if (m instanceof CNode) {
-                    // 1) a multiway node
-                    CNode<K, V> cn = (CNode<K, V>) m;
-                    int idx = (hc >>> lev) & 0x1f;
-                    int flag = 1 << idx;
-                    int bmp = cn.bitmap;
-                    int mask = flag - 1;
-                    int pos = Integer.bitCount(bmp & mask);
-                    if ((bmp & flag) != 0) {
-                        // 1a) insert below
-                        BasicNode cnAtPos = cn.array[pos];
-                        if (cnAtPos instanceof INode) {
-                            INode<K, V> in = (INode<K, V>) cnAtPos;
-                            if (startgen == in.gen)
-                                return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
-                            else {
-                                if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
-                                    // return rec_insert (k, v, hc, lev, parent,
-                                    // startgen, ct);
-                                    // tailrec
-                                    continue;
-                                }
-                                else
-                                    return false;
-                            }
-                        }
-                        else if (cnAtPos instanceof SNode) {
-                            SNode<K, V> sn = (SNode<K, V>) cnAtPos;
-                            if (sn.hc == hc && equal((K) sn.k, k, ct))
-                                return GCAS(cn, cn.updatedAt(pos, new SNode<K, V>(k, v, hc), gen), ct);
-                            else {
-                                CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                                MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen);
-                                return GCAS(cn, nn, ct);
-                            }
-                        }
-                    }
-                    else {
-                        CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                        MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<K, V>(k, v, hc), gen);
-                        return GCAS(cn, ncnode, ct);
-                    }
-                }
-                else if (m instanceof TNode) {
-                    clean(parent, ct, lev - 5);
-                    return false;
-                }
-                else if (m instanceof LNode) {
-                    LNode<K, V> ln = (LNode<K, V>) m;
-                    MainNode<K, V> nn = ln.inserted(k, v);
-                    return GCAS(ln, nn, ct);
-                }
-
-                throw new RuntimeException("Should not happen");
-            }
-        }
-
-        /**
-         * Inserts a new key value pair, given that a specific condition is met.
-         *
-         * @param cond null - don't care if the key was there
-         *             KEY_ABSENT - key wasn't there
-         *             KEY_PRESENT - key was there
-         *             other value `v` - key must be bound to `v`
-         * @return null if unsuccessful, Option[V] otherwise (indicating
-         * previous value bound to the key)
-         */
-        final Option<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
-            while (true) {
-                MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
-
-                if (m instanceof CNode) {
-                    // 1) a multiway node
-                    CNode<K, V> cn = (CNode<K, V>) m;
-                    int idx = (hc >>> lev) & 0x1f;
-                    int flag = 1 << idx;
-                    int bmp = cn.bitmap;
-                    int mask = flag - 1;
-                    int pos = Integer.bitCount(bmp & mask);
-
-                    if ((bmp & flag) != 0) {
-                        // 1a) insert below
-                        BasicNode cnAtPos = cn.array[pos];
-                        if (cnAtPos instanceof INode) {
-                            INode<K, V> in = (INode<K, V>) cnAtPos;
-                            if (startgen == in.gen)
-                                return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
-                            else {
-                                if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
-                                    // return rec_insertif (k, v, hc, cond, lev,
-                                    // parent, startgen, ct);
-                                    // tailrec
-                                    continue;
-                                }
-                                else
-                                    return null;
-                            }
-                        }
-                        else if (cnAtPos instanceof SNode) {
-                            SNode<K, V> sn = (SNode<K, V>) cnAtPos;
-                            if (cond == null) {
-                                if (sn.hc == hc && equal(sn.k, k, ct)) {
-                                    if (GCAS(cn, cn.updatedAt(pos, new SNode<K, V>(k, v, hc), gen), ct))
-                                        return Option.makeOption(sn.v);
-                                    else
-                                        return null;
-                                }
-                                else {
-                                    CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                                    MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen);
-                                    if (GCAS(cn, nn, ct))
-                                        return Option.makeOption(); // None;
-                                    else
-                                        return null;
-                                }
-
-                            }
-                            else if (cond == INode.KEY_ABSENT) {
-                                if (sn.hc == hc && equal(sn.k, k, ct))
-                                    return Option.makeOption(sn.v);
-                                else {
-                                    CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                                    MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen);
-                                    if (GCAS(cn, nn, ct))
-                                        return Option.makeOption(); // None
-                                    else
-                                        return null;
-                                }
-                            }
-                            else if (cond == INode.KEY_PRESENT) {
-                                if (sn.hc == hc && equal(sn.k, k, ct)) {
-                                    if (GCAS(cn, cn.updatedAt(pos, new SNode<K, V>(k, v, hc), gen), ct))
-                                        return Option.makeOption(sn.v);
-                                    else
-                                        return null;
-
-                                }
-                                else
-                                    return Option.makeOption();// None;
-                            }
-                            else {
-                                if (sn.hc == hc && equal(sn.k, k, ct) && sn.v == cond) {
-                                    if (GCAS(cn, cn.updatedAt(pos, new SNode<K, V>(k, v, hc), gen), ct))
-                                        return Option.makeOption(sn.v);
-                                    else
-                                        return null;
-                                }
-                                else
-                                    return Option.makeOption(); // None
-                            }
-
-                        }
-                    }
-                    else if (cond == null || cond == INode.KEY_ABSENT) {
-                        CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
-                        CNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<K, V>(k, v, hc), gen);
-                        if (GCAS(cn, ncnode, ct))
-                            return Option.makeOption();// None
-                        else
-                            return null;
-                    }
-                    else if (cond == INode.KEY_PRESENT) {
-                        return Option.makeOption();// None;
-                    }
-                    else
-                        return Option.makeOption(); // None
-                }
-                else if (m instanceof TNode) {
-                    clean(parent, ct, lev - 5);
-                    return null;
-                }
-                else if (m instanceof LNode) {
-                    // 3) an l-node
-                    LNode<K, V> ln = (LNode<K, V>) m;
-                    if (cond == null) {
-                        Option<V> optv = ln.get(k);
-                        if (insertln(ln, k, v, ct))
-                            return optv;
-                        else
-                            return null;
-                    }
-                    else if (cond == INode.KEY_ABSENT) {
-                        Option<V> t = ln.get(k);
-                        if (t == null) {
-                            if (insertln(ln, k, v, ct))
-                                return Option.makeOption();// None
-                            else
-                                return null;
-                        }
-                        else
-                            return t;
-                    }
-                    else if (cond == INode.KEY_PRESENT) {
-                        Option<V> t = ln.get(k);
-                        if (t != null) {
-                            if (insertln(ln, k, v, ct))
-                                return t;
-                            else
-                                return null;
-                        }
-                        else
-                            return null; // None
-                    }
-                    else {
-                        Option<V> t = ln.get(k);
-                        if (t != null) {
-                            if (((Some<V>) t).get() == cond) {
-                                if (insertln(ln, k, v, ct))
-                                    return new Some<V>((V) cond);
-                                else
-                                    return null;
-
-                            }
-                            else
-                                return Option.makeOption();
-                        }
-                    }
-                }
-
-//                throw new RuntimeException ("Should not happen");
-            }
-        }
-
-        final boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
-            LNode<K, V> nn = ln.inserted(k, v);
-            return GCAS(ln, nn, ct);
-        }
-
-        /**
-         * Looks up the value associated with the key.
-         *
-         * @return null if no value has been found, RESTART if the operation
-         * wasn't successful, or any other value otherwise
-         */
-        final Object rec_lookup(final K k, final int hc, int lev, INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
-            while (true) {
-                MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
-
-                if (m instanceof CNode) {
-                    // 1) a multinode
-                    final CNode<K, V> cn = (CNode<K, V>) m;
-                    int idx = (hc >>> lev) & 0x1f;
-                    int flag = 1 << idx;
-                    int bmp = cn.bitmap;
-                    if ((bmp & flag) == 0)
-                        return null; // 1a) bitmap shows no binding
-                    else { // 1b) bitmap contains a value - descend
-                        int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
-                        final BasicNode sub = cn.array[pos];
-                        if (sub instanceof INode) {
-                            INode<K, V> in = (INode<K, V>) sub;
-                            if (ct.isReadOnly() || (startgen == ((INodeBase<K, V>) sub).gen))
-                                return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
-                            else {
-                                if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
-                                    // return rec_lookup (k, hc, lev, parent,
-                                    // startgen, ct);
-                                    // Tailrec
-                                    continue;
-                                }
-                                else
-                                    return RESTART; // used to be throw
-                                // RestartException
-                            }
-                        }
-                        else if (sub instanceof SNode) {
-                            // 2) singleton node
-                            SNode<K, V> sn = (SNode<K, V>) sub;
-                            if (((SNode) sub).hc == hc && equal(sn.k, k, ct))
-                                return sn.v;
-                            else
-                                return null;
-                        }
-                    }
-                }
-                else if (m instanceof TNode) {
-                    // 3) non-live node
-                    return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
-                }
-                else if (m instanceof LNode) {
-                    // 5) an l-node
-                    Option<V> tmp = ((LNode<K, V>) m).get(k);
-                    return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
-                }
-
-                throw new RuntimeException("Should not happen");
-            }
-        }
-
-        private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct, K k, int hc) {
-            if (ct.nonReadOnly()) {
-                clean(parent, ct, lev - 5);
-                return RESTART; // used to be throw RestartException
-            }
-            else {
-                if (tn.hc == hc && tn.k == k)
-                    return tn.v;
-                else
-                    return null;
-            }
-        }
-
-        /**
-         * Removes the key associated with the given value.
-         *
-         * @param v if null, will remove the key irregardless of the value;
-         *          otherwise removes only if binding contains that exact key
-         *          and value
-         * @return null if not successful, an Option[V] indicating the previous
-         * value otherwise
-         */
-        final Option<V> rec_remove(K k, V v, int hc, int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
-            MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
-
-            if (m instanceof CNode) {
-                CNode<K, V> cn = (CNode<K, V>) m;
-                int idx = (hc >>> lev) & 0x1f;
-                int bmp = cn.bitmap;
-                int flag = 1 << idx;
-                if ((bmp & flag) == 0)
-                    return Option.makeOption();
-                else {
-                    int pos = Integer.bitCount(bmp & (flag - 1));
-                    BasicNode sub = cn.array[pos];
-                    Option<V> res = null;
-                    if (sub instanceof INode) {
-                        INode<K, V> in = (INode<K, V>) sub;
-                        if (startgen == in.gen)
-                            res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
-                        else {
-                            if (GCAS(cn, cn.renewed(startgen, ct), ct))
-                                res = rec_remove(k, v, hc, lev, parent, startgen, ct);
-                            else
-                                res = null;
-                        }
-
-                    }
-                    else if (sub instanceof SNode) {
-                        SNode<K, V> sn = (SNode<K, V>) sub;
-                        if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || v.equals(sn.v))) {
-                            MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
-                            if (GCAS(cn, ncn, ct))
-                                res = Option.makeOption(sn.v);
-                            else
-                                res = null;
-                        }
-                        else
-                            res = Option.makeOption();
-                    }
-
-                    if (res instanceof None || (res == null))
-                        return res;
-                    else {
-                        if (parent != null) { // never tomb at root
-                            MainNode<K, V> n = GCAS_READ(ct);
-                            if (n instanceof TNode)
-                                cleanParent(n, parent, ct, hc, lev, startgen);
-                        }
-
-                        return res;
-                    }
-                }
-            }
-            else if (m instanceof TNode) {
-                clean(parent, ct, lev - 5);
-                return null;
-            }
-            else if (m instanceof LNode) {
-                LNode<K, V> ln = (LNode<K, V>) m;
-                if (v == null) {
-                    Option<V> optv = ln.get(k);
-                    MainNode<K, V> nn = ln.removed(k, ct);
-                    if (GCAS(ln, nn, ct))
-                        return optv;
-                    else
-                        return null;
-                }
-                else {
-                    Option<V> tmp = ln.get(k);
-                    if (tmp instanceof Some) {
-                        Some<V> tmp1 = (Some<V>) tmp;
-                        if (tmp1.get() == v) {
-                            MainNode<K, V> nn = ln.removed(k, ct);
-                            if (GCAS(ln, nn, ct))
-                                return tmp;
-                            else
-                                return null;
-                        }
-                    }
-                }
-            }
-            throw new RuntimeException("Should not happen");
-        }
-
-        void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc, final int lev, final Gen startgen) {
-            while (true) {
-                MainNode<K, V> pm = parent.GCAS_READ(ct);
-                if (pm instanceof CNode) {
-                    CNode<K, V> cn = (CNode<K, V>) pm;
-                    int idx = (hc >>> (lev - 5)) & 0x1f;
-                    int bmp = cn.bitmap;
-                    int flag = 1 << idx;
-                    if ((bmp & flag) == 0) {
-                    } // somebody already removed this i-node, we're done
-                    else {
-                        int pos = Integer.bitCount(bmp & (flag - 1));
-                        BasicNode sub = cn.array[pos];
-                        if (sub == this) {
-                            if (nonlive instanceof TNode) {
-                                TNode<K, V> tn = (TNode<K, V>) nonlive;
-                                MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - 5);
-                                if (!parent.GCAS(cn, ncn, ct))
-                                    if (ct.readRoot().gen == startgen) {
-                                        // cleanParent (nonlive, parent, ct, hc,
-                                        // lev, startgen);
-                                        // tailrec
-                                        continue;
-                                    }
-                            }
-                        }
-                    }
-                }
-                else {
-                    // parent is no longer a cnode, we're done
-                }
-                break;
-            }
-        }
-
-        private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, int lev) {
-            MainNode<K, V> m = nd.GCAS_READ(ct);
-            if (m instanceof CNode) {
-                CNode<K, V> cn = (CNode<K, V>) m;
-                nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
-            }
-        }
-
-        final boolean isNullInode(final TrieMap<K, V> ct) {
-            return GCAS_READ(ct) == null;
-        }
-
-        final int cachedSize(final TrieMap<K, V> ct) {
-            MainNode<K, V> m = GCAS_READ(ct);
-            return m.cachedSize(ct);
-        }
-
-        // /* this is a quiescent method! */
-        // def string(lev: Int) = "%sINode -> %s".format("  " * lev, mainnode
-        // match {
-        // case null => "<null>"
-        // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
-        // tn.hc)
-        // case cn: CNode[_, _] => cn.string(lev)
-        // case ln: LNode[_, _] => ln.string(lev)
-        // case x => "<elem: %s>".format(x)
-        // })
-
-        public String string(int lev) {
-            return "INode";
-        }
-
-    }
-
-    private static final class FailedNode<K, V> extends MainNode<K, V> {
-        MainNode<K, V> p;
-
-        FailedNode(final MainNode<K, V> p) {
-            this.p = p;
-            WRITE_PREV(p);
-        }
-
-        public String string(int lev) {
-            throw new UnsupportedOperationException();
-        }
-
-        public int cachedSize(Object ct) {
-            throw new UnsupportedOperationException();
-        }
-
-        public String toString() {
-            return String.format("FailedNode(%s)", p);
-        }
-    }
-
-    private static final class SNode<K, V> extends BasicNode implements KVNode<K, V> {
-        final K k;
-        final V v;
-        final int hc;
-
-        SNode(final K k, final V v, final int hc) {
-            this.k = k;
-            this.v = v;
-            this.hc = hc;
-        }
-
-        final SNode<K, V> copy() {
-            return new SNode<K, V>(k, v, hc);
-        }
-
-        final TNode<K, V> copyTombed() {
-            return new TNode<K, V>(k, v, hc);
-        }
-
-        final SNode<K, V> copyUntombed() {
-            return new SNode<K, V>(k, v, hc);
-        }
-
-        final public Entry<K, V> kvPair() {
-            return new Pair<K, V>(k, v);
-        }
-
-        final public String string(int lev) {
-            // ("  " * lev) + "SNode(%s, %s, %x)".format(k, v, hc);
-            return "SNode";
-        }
-    }
-
-    private static final class TNode<K, V> extends MainNode<K, V> implements KVNode<K, V> {
-        final K k;
-        final V v;
-        final int hc;
-
-        TNode(final K k, final V v, final int hc) {
-            this.k = k;
-            this.v = v;
-            this.hc = hc;
-        }
-
-        final TNode<K, V> copy() {
-            return new TNode<K, V>(k, v, hc);
-        }
-
-        final TNode<K, V> copyTombed() {
-            return new TNode<K, V>(k, v, hc);
-        }
-
-        final SNode<K, V> copyUntombed() {
-            return new SNode<K, V>(k, v, hc);
-        }
-
-        final public Pair<K, V> kvPair() {
-            return new Pair<K, V>(k, v);
-        }
-
-        final public int cachedSize(Object ct) {
-            return 1;
-        }
-
-        final public String string(int lev) {
-            // ("  " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc);
-            return "TNode";
-        }
-    }
-
-    private final static class LNode<K, V> extends MainNode<K, V> {
-        final ListMap<K, V> listmap;
-
-        public LNode(final ListMap<K, V> listmap) {
-            this.listmap = listmap;
-        }
-
-        public LNode(K k, V v) {
-            this(ListMap.map(k, v));
-        }
-
-        public LNode(K k1, V v1, K k2, V v2) {
-            this(ListMap.map(k1, v1, k2, v2));
-        }
-
-        LNode<K, V> inserted(K k, V v) {
-            return new LNode<K, V>(listmap.add(k, v));
-        }
-
-        MainNode<K, V> removed(K k, final TrieMap<K, V> ct) {
-            ListMap<K, V> updmap = listmap.remove(k);
-            if (updmap.size() > 1)
-                return new LNode<K, V>(updmap);
-            else {
-                Entry<K, V> kv = updmap.iterator().next();
-                // create it tombed so that it gets compressed on subsequent
-                // accesses
-                return new TNode<K, V>(kv.getKey(), kv.getValue(), ct.computeHash(kv.getKey()));
-            }
-        }
-
-        Option<V> get(K k) {
-            return listmap.get(k);
-        }
-
-        public int cachedSize(Object ct) {
-            return listmap.size();
-        }
-
-        public String string(int lev) {
-            // (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
-            return "LNode";
-        }
-    }
-
-    private static final class CNode<K, V> extends CNodeBase<K, V> {
-
-        final int bitmap;
-        final BasicNode[] array;
-        final Gen gen;
-
-        CNode(final int bitmap, final BasicNode[] array, final Gen gen) {
-            this.bitmap = bitmap;
-            this.array = array;
-            this.gen = gen;
-        }
-
-        static <K, V> MainNode<K, V> dual(final SNode<K, V> x, int xhc, final SNode<K, V> y, int yhc, int lev, Gen gen) {
-            if (lev < 35) {
-                int xidx = (xhc >>> lev) & 0x1f;
-                int yidx = (yhc >>> lev) & 0x1f;
-                int bmp = (1 << xidx) | (1 << yidx);
-
-                if (xidx == yidx) {
-                    INode<K, V> subinode = new INode<K, V>(gen);// (TrieMap.inodeupdater)
-                    subinode.mainnode = dual(x, xhc, y, yhc, lev + 5, gen);
-                    return new CNode<K, V>(bmp, new BasicNode[]{subinode}, gen);
-                }
-                else {
-                    if (xidx < yidx)
-                        return new CNode<K, V>(bmp, new BasicNode[]{x, y}, gen);
-                    else
-                        return new CNode<K, V>(bmp, new BasicNode[]{y, x}, gen);
-                }
-            }
-            else {
-                return new LNode<K, V>(x.k, x.v, y.k, y.v);
-            }
-        }
-
-        // this should only be called from within read-only snapshots
-        final public int cachedSize(Object ct) {
-            int currsz = READ_SIZE();
-            if (currsz != -1)
-                return currsz;
-            else {
-                int sz = computeSize((TrieMap<K, V>) ct);
-                while (READ_SIZE() == -1)
-                    CAS_SIZE(-1, sz);
-                return READ_SIZE();
-            }
-        }
-
-        // lends itself towards being parallelizable by choosing
-        // a random starting offset in the array
-        // => if there are concurrent size computations, they start
-        // at different positions, so they are more likely to
-        // to be independent
-        private int computeSize(final TrieMap<K, V> ct) {
-            int i = 0;
-            int sz = 0;
-            // final int offset = (array.length > 0) ?
-            // // util.Random.nextInt(array.length) /* <-- benchmarks show that
-            // // this causes observable contention */
-            // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
-            // array.length)
-            // : 0;
-
-            final int offset = 0;
-            while (i < array.length) {
-                int pos = (i + offset) % array.length;
-                BasicNode elem = array[pos];
-                if (elem instanceof SNode)
-                    sz += 1;
-                else if (elem instanceof INode)
-                    sz += ((INode<K, V>) elem).cachedSize(ct);
-                i += 1;
-            }
-            return sz;
-        }
-
-        final CNode<K, V> updatedAt(int pos, final BasicNode nn, final Gen gen) {
-            int len = array.length;
-            BasicNode[] narr = new BasicNode[len];
-            System.arraycopy(array, 0, narr, 0, len);
-            narr[pos] = nn;
-            return new CNode<K, V>(bitmap, narr, gen);
-        }
-
-        final CNode<K, V> removedAt(int pos, int flag, final Gen gen) {
-            BasicNode[] arr = array;
-            int len = arr.length;
-            BasicNode[] narr = new BasicNode[len - 1];
-            System.arraycopy(arr, 0, narr, 0, pos);
-            System.arraycopy(arr, pos + 1, narr, pos, len - pos - 1);
-            return new CNode<K, V>(bitmap ^ flag, narr, gen);
-        }
-
-        final CNode<K, V> insertedAt(int pos, int flag, final BasicNode nn, final Gen gen) {
-            int len = array.length;
-            int bmp = bitmap;
-            BasicNode[] narr = new BasicNode[len + 1];
-            System.arraycopy(array, 0, narr, 0, pos);
-            narr[pos] = nn;
-            System.arraycopy(array, pos, narr, pos + 1, len - pos);
-            return new CNode<K, V>(bmp | flag, narr, gen);
-        }
-
-        /**
-         * Returns a copy of this cnode such that all the i-nodes below it are
-         * copied to the specified generation `ngen`.
-         */
-        final CNode<K, V> renewed(final Gen ngen, final TrieMap<K, V> ct) {
-            int i = 0;
-            BasicNode[] arr = array;
-            int len = arr.length;
-            BasicNode[] narr = new BasicNode[len];
-            while (i < len) {
-                BasicNode elem = arr[i];
-                if (elem instanceof INode) {
-                    INode<K, V> in = (INode<K, V>) elem;
-                    narr[i] = in.copyToGen(ngen, ct);
-                }
-                else if (elem instanceof BasicNode)
-                    narr[i] = elem;
-                i += 1;
-            }
-            return new CNode<K, V>(bitmap, narr, ngen);
-        }
-
-        private BasicNode resurrect(final INode<K, V> inode, final Object inodemain) {
-            if (inodemain instanceof TNode) {
-                TNode<K, V> tn = (TNode<K, V>) inodemain;
-                return tn.copyUntombed();
-            }
-            else
-                return inode;
-        }
-
-        final MainNode<K, V> toContracted(int lev) {
-            if (array.length == 1 && lev > 0) {
-                if (array[0] instanceof SNode) {
-                    SNode<K, V> sn = (SNode<K, V>) array[0];
-                    return sn.copyTombed();
-                }
-                else
-                    return this;
-
-            }
-            else
-                return this;
-        }
-
-        // - if the branching factor is 1 for this CNode, and the child
-        // is a tombed SNode, returns its tombed version
-        // - otherwise, if there is at least one non-null node below,
-        // returns the version of this node with at least some null-inodes
-        // removed (those existing when the op began)
-        // - if there are only null-i-nodes below, returns null
-        final MainNode<K, V> toCompressed(final TrieMap<K, V> ct, int lev, Gen gen) {
-            int bmp = bitmap;
-            int i = 0;
-            BasicNode[] arr = array;
-            BasicNode[] tmparray = new BasicNode[arr.length];
-            while (i < arr.length) { // construct new bitmap
-                BasicNode sub = arr[i];
-                if (sub instanceof INode) {
-                    INode<K, V> in = (INode<K, V>) sub;
-                    MainNode<K, V> inodemain = in.gcasRead(ct);
-                    assert (inodemain != null);
-                    tmparray[i] = resurrect(in, inodemain);
-                }
-                else if (sub instanceof SNode) {
-                    tmparray[i] = sub;
-                }
-                i += 1;
-            }
-
-            return new CNode<K, V>(bmp, tmparray, gen).toContracted(lev);
-        }
-
-        /*
-         * quiescently consistent - don't call concurrently to anything
-         * involving a GCAS!!
-         */
-        // protected Seq<K,V> collectElems() {
-        // array flatMap {
-        // case sn: SNode[K, V] => Some(sn.kvPair)
-        // case in: INode[K, V] => in.mainnode match {
-        // case tn: TNode[K, V] => Some(tn.kvPair)
-        // case ln: LNode[K, V] => ln.listmap.toList
-        // case cn: CNode[K, V] => cn.collectElems
-        // }
-        // }
-        // }
-
-        // protected Seq<String> collectLocalElems() {
-        // // array flatMap {
-        // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
-        // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
-        // ")")
-        // // }
-        // return null;
-        // }
-
-        public String string(int lev) {
-            // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
-            // 1)).mkString("\n"));
-            return "CNode";
-        }
-
-        public String toString() {
-            // val elems = collectLocalElems
-            // "CNode(sz: %d; %s)".format(elems.size,
-            // elems.sorted.mkString(", "))
-            return "CNode";
-        }
-
-    }
-
-    private static class RDCSS_Descriptor<K, V> {
-        INode<K, V> old;
-        MainNode<K, V> expectedmain;
-        INode<K, V> nv;
-        volatile boolean committed = false;
-
-        public RDCSS_Descriptor(final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
-            this.old = old;
-            this.expectedmain = expectedmain;
-            this.nv = nv;
-        }
-
-    }
-
-    private static class Equiv<K> {
-        static Equiv universal = new Equiv();
-
-        public boolean equiv(K k1, K k2) {
-            return k1.equals(k2);
-        }
-    }
-
-    static class Default<K> implements Hashing<K> {
-        public int hash(K k) {
-            int h = k.hashCode();
-            // This function ensures that hashCodes that differ only by
-            // constant multiples at each bit position have a bounded
-            // number of collisions (approximately 8 at default load factor).
-            h ^= (h >>> 20) ^ (h >>> 12);
-            h ^= (h >>> 7) ^ (h >>> 4);
-            return h;
-        }
-    }
-
-    /**
-     * This iterator is a read-only one and does not allow for any update
-     * operations on the underlying data structure.
-     *
-     * @param <K>
-     * @param <V>
-     */
-    private static class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
-        TrieMapReadOnlyIterator(int level, final TrieMap<K, V> ct, boolean mustInit) {
-            super(level, ct, mustInit);
-        }
-
-        TrieMapReadOnlyIterator(int level, TrieMap<K, V> ct) {
-            this(level, ct, true);
-        }
-
-        void initialize() {
-            assert (ct.isReadOnly());
-            super.initialize();
-        }
-
-        public void remove() {
-            throw new RuntimeException("Operation not supported for read-only iterators");
-        }
-
-
-        Entry<K, V> nextEntry(final Entry<K, V> rr) {
-            // Return non-updatable entry
-            return rr;
-        }
-    }
-
-    private static class TrieMapIterator<K, V> implements Iterator<Entry<K, V>> {
-        private final boolean mustInit;
-        protected TrieMap<K, V> ct;
-        private int level;
-        private BasicNode[][] stack = new BasicNode[7][];
-        private int[] stackpos = new int[7];
-        private int depth = -1;
-        private Iterator<Entry<K, V>> subiter = null;
-        private KVNode<K, V> current = null;
-        private Entry<K, V> lastReturned = null;
-
-        TrieMapIterator(int level, final TrieMap<K, V> ct, boolean mustInit) {
-            this.level = level;
-            this.ct = ct;
-            this.mustInit = mustInit;
-            if (this.mustInit)
-                initialize();
-        }
-
-        TrieMapIterator(int level, TrieMap<K, V> ct) {
-            this(level, ct, true);
-        }
-
-
-        public boolean hasNext() {
-            return (current != null) || (subiter != null);
-        }
-
-        public Entry<K, V> next() {
-            if (hasNext()) {
-                Entry<K, V> r = null;
-                if (subiter != null) {
-                    r = subiter.next();
-                    checkSubiter();
-                }
-                else {
-                    r = current.kvPair();
-                    advance();
-                }
-
-                lastReturned = r;
-                if (r instanceof Entry) {
-                    final Entry<K, V> rr = (Entry<K, V>) r;
-                    return nextEntry(rr);
-                }
-                return r;
-            }
-            else {
-                // return Iterator.empty ().next ();
-                return null;
-            }
-        }
-
-        Entry<K, V> nextEntry(final Entry<K, V> rr) {
-            return new Entry<K, V>() {
-                private V updated = null;
-
-                @Override
-                public K getKey() {
-                    return rr.getKey();
-                }
-
-                @Override
-                public V getValue() {
-                    return (updated == null) ? rr.getValue() : updated;
-                }
-
-                @Override
-                public V setValue(V value) {
-                    updated = value;
-                    return ct.replace(getKey(), value);
-                }
-            };
-        }
-
-        private void readin(INode<K, V> in) {
-            MainNode<K, V> m = in.gcasRead(ct);
-            if (m instanceof CNode) {
-                CNode<K, V> cn = (CNode<K, V>) m;
-                depth += 1;
-                stack[depth] = cn.array;
-                stackpos[depth] = -1;
-                advance();
-            }
-            else if (m instanceof TNode) {
-                current = (TNode<K, V>) m;
-            }
-            else if (m instanceof LNode) {
-                subiter = ((LNode<K, V>) m).listmap.iterator();
-                checkSubiter();
-            }
-            else if (m == null) {
-                current = null;
-            }
-        }
-
-        // @inline
-        private void checkSubiter() {
-            if (!subiter.hasNext()) {
-                subiter = null;
-                advance();
-            }
-        }
-
-        // @inline
-        void initialize() {
-//            assert (ct.isReadOnly ());
-            INode<K, V> r = ct.RDCSS_READ_ROOT();
-            readin(r);
-        }
-
-        void advance() {
-            if (depth >= 0) {
-                int npos = stackpos[depth] + 1;
-                if (npos < stack[depth].length) {
-                    stackpos[depth] = npos;
-                    BasicNode elem = stack[depth][npos];
-                    if (elem instanceof SNode) {
-                        current = (SNode<K, V>) elem;
-                    }
-                    else if (elem instanceof INode) {
-                        readin((INode<K, V>) elem);
-                    }
-                }
-                else {
-                    depth -= 1;
-                    advance();
-                }
-            }
-            else
-                current = null;
-        }
-
-        protected TrieMapIterator<K, V> newIterator(int _lev, TrieMap<K, V> _ct, boolean _mustInit) {
-            return new TrieMapIterator<K, V>(_lev, _ct, _mustInit);
-        }
-
-        protected void dupTo(TrieMapIterator<K, V> it) {
-            it.level = this.level;
-            it.ct = this.ct;
-            it.depth = this.depth;
-            it.current = this.current;
-
-            // these need a deep copy
-            System.arraycopy(this.stack, 0, it.stack, 0, 7);
-            System.arraycopy(this.stackpos, 0, it.stackpos, 0, 7);
-
-            // this one needs to be evaluated
-            if (this.subiter == null)
-                it.subiter = null;
-            else {
-                List<Entry<K, V>> lst = toList(this.subiter);
-                this.subiter = lst.iterator();
-                it.subiter = lst.iterator();
-            }
-        }
-
-        // /** Returns a sequence of iterators over subsets of this iterator.
-        // * It's used to ease the implementation of splitters for a parallel
-        // version of the TrieMap.
-        // */
-        // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
-        // null) {
-        // // the case where an LNode is being iterated
-        // val it = subiter
-        // subiter = null
-        // advance()
-        // this.level += 1
-        // Seq(it, this)
-        // } else if (depth == -1) {
-        // this.level += 1
-        // Seq(this)
-        // } else {
-        // var d = 0
-        // while (d <= depth) {
-        // val rem = stack(d).length - 1 - stackpos(d)
-        // if (rem > 0) {
-        // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
-        // stack(d) = arr1
-        // stackpos(d) = -1
-        // val it = newIterator(level + 1, ct, false)
-        // it.stack(0) = arr2
-        // it.stackpos(0) = -1
-        // it.depth = 0
-        // it.advance() // <-- fix it
-        // this.level += 1
-        // return Seq(this, it)
-        // }
-        // d += 1
-        // }
-        // this.level += 1
-        // Seq(this)
-        // }
-
-        private List<Entry<K, V>> toList(Iterator<Entry<K, V>> it) {
-            ArrayList<Entry<K, V>> list = new ArrayList<Entry<K, V>>();
-            while (it.hasNext()) {
-                list.add(it.next());
-            }
-            return list;
-        }
-
-        void printDebug() {
-            System.out.println("ctrie iterator");
-            System.out.println(Arrays.toString(stackpos));
-            System.out.println("depth: " + depth);
-            System.out.println("curr.: " + current);
-            // System.out.println(stack.mkString("\n"));
-        }
-
-        @Override
-        public void remove() {
-            if (lastReturned != null) {
-                ct.remove(lastReturned.getKey());
-                lastReturned = null;
-            }
-            else
-                throw new IllegalStateException();
-        }
-
-    }
-
-    /**
-     * Support for EntrySet operations required by the Map interface
-     */
-    final class EntrySet extends AbstractSet<Entry<K, V>> {
-
-        @Override
-        public Iterator<Entry<K, V>> iterator() {
-            return TrieMap.this.iterator();
-        }
-
-        @Override
-        public final boolean contains(final Object o) {
-            if (!(o instanceof Entry)) {
-                return false;
-            }
-            final Entry<K, V> e = (Entry<K, V>) o;
-            final K k = e.getKey();
-            final V v = lookup(k);
-            return v != null;
-        }
-
-        @Override
-        public final boolean remove(final Object o) {
-            if (!(o instanceof Entry)) {
-                return false;
-            }
-            final Entry<K, V> e = (Entry<K, V>) o;
-            final K k = e.getKey();
-            return null != TrieMap.this.remove(k);
-        }
-
-        @Override
-        public final int size() {
-            int size = 0;
-            for (final Iterator<?> i = iterator(); i.hasNext(); i.next()) {
-                size++;
-            }
-            return size;
-        }
-
-        @Override
-        public final void clear() {
-            TrieMap.this.clear();
-        }
-    }
-}

http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/AmortizedPQueue.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/pcollections/AmortizedPQueue.java b/modules/core/src/main/java/org/pcollections/AmortizedPQueue.java
deleted file mode 100644
index a1df809..0000000
--- a/modules/core/src/main/java/org/pcollections/AmortizedPQueue.java
+++ /dev/null
@@ -1,156 +0,0 @@
-package org.pcollections;
-
-import java.util.*;
-
-// TODO javadoc
-// TODO tests
-
-/**
- * @param <E>
- * @author mtklein
- */
-public class AmortizedPQueue<E> extends AbstractQueue<E> implements PQueue<E> {
-
-    private static final AmortizedPQueue<Object> EMPTY = new AmortizedPQueue<Object>();
-    private final PStack<E> front;
-    private final PStack<E> back;
-    private AmortizedPQueue() {
-        front = Empty.<E>stack();
-        back = Empty.<E>stack();
-    }
-
-    private AmortizedPQueue(AmortizedPQueue<E> queue, E e) {
-        /* Guarantee that there is always at least 1 element
-		 * in front, which makes peek worst-case O(1).
-		 */
-        if (queue.front.size() == 0) {
-            this.front = queue.front.plus(e);
-            this.back = queue.back;
-        }
-        else {
-            this.front = queue.front;
-            this.back = queue.back.plus(e);
-        }
-    }
-
-    private AmortizedPQueue(PStack<E> front, PStack<E> back) {
-        this.front = front;
-        this.back = back;
-    }
-
-    @SuppressWarnings("unchecked")
-    public static <E> AmortizedPQueue<E> empty() {
-        return (AmortizedPQueue<E>) EMPTY;
-    }
-
-    public static void main(String[] args) {
-        AmortizedPQueue<Integer> queue = new AmortizedPQueue<Integer>();
-
-        queue = queue.plus(1).minus().minus().plus(2).plus(3).plus(4).plus(5).minus().plus(6).plus(7);
-        PQueue<Integer> original = queue;
-
-        System.out.println("    \t" + queue.front + " " + queue.back);
-
-        while (queue.size() > 0) {
-            int i = queue.peek();
-            queue = queue.minus();
-            System.out.println(i + " <- \t" + queue.front + " " + queue.back);
-        }
-
-        System.out.println(original);
-    }
-
-    /* Worst-case O(n) */
-    @Override
-    public Iterator<E> iterator() {
-        return new Iterator<E>() {
-            private PQueue<E> queue = AmortizedPQueue.this;
-
-            public boolean hasNext() {
-                return queue.size() > 0;
-            }
-
-            public E next() {
-                E e = queue.peek();
-                queue = queue.minus();
-                return e;
-            }
-
-            public void remove() {
-                throw new UnsupportedOperationException();
-            }
-        };
-    }
-
-    /* Worst-case O(1) */
-    @Override
-    public int size() {
-        return front.size() + back.size();
-    }
-
-    /* Worst-case O(1) */
-    public E peek() {
-        if (size() == 0)
-            return null;
-        return front.get(0);
-    }
-
-    /* Amortized O(1), worst-case O(n) */
-    public AmortizedPQueue<E> minus() {
-        if (size() == 0)
-            return this;
-
-        int fsize = front.size();
-
-        if (fsize == 0) {
-            //If there's nothing on front, dump back onto front
-            //(as stacks, this goes in reverse like we want)
-            //and take one off.
-            return new AmortizedPQueue<E>(Empty.<E>stack().plusAll(back), Empty.<E>stack()).minus();
-        }
-        else if (fsize == 1) {
-            //If there's one element on front, dump back onto front,
-            //but now we've already removed the head.
-            return new AmortizedPQueue<E>(Empty.<E>stack().plusAll(back), Empty.<E>stack());
-        }
-        else {
-            //If there's more than one on front, we pop one off.
-            return new AmortizedPQueue<E>(front.minus(0), back);
-        }
-    }
-
-    /* Worst-case O(1) */
-    public AmortizedPQueue<E> plus(E e) {
-        return new AmortizedPQueue<E>(this, e);
-    }
-
-    /* Worst-case O(k) */
-    public AmortizedPQueue<E> plusAll(Collection<? extends E> list) {
-        AmortizedPQueue<E> result = this;
-        for (E e : list) {
-            result = result.plus(e);
-        }
-        return result;
-    }
-
-    /* These 2 methods not guaranteed to be fast.*/
-    public PCollection<E> minus(Object e) {
-        return Empty.<E>vector().plusAll(this).minus(e);
-    }
-
-    public PCollection<E> minusAll(Collection<?> list) {
-        return Empty.<E>vector().plusAll(this).minusAll(list);
-    }
-
-    /* These 2 methods are not applicable to a persistent collection. */
-    public boolean offer(E o) {
-        // Not possible to modify a persistent queue, interface
-        // says return false if it's not added.
-        throw new UnsupportedOperationException();
-    }
-
-    public E poll() {
-        // Poll is meant to destructively remove and return the front of the queue.
-        throw new UnsupportedOperationException();
-    }
-}

http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/ConsPStack.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/pcollections/ConsPStack.java b/modules/core/src/main/java/org/pcollections/ConsPStack.java
deleted file mode 100644
index 9d2512d..0000000
--- a/modules/core/src/main/java/org/pcollections/ConsPStack.java
+++ /dev/null
@@ -1,225 +0,0 @@
-package org.pcollections;
-
-import java.util.*;
-
-
-/**
- * A simple persistent stack of non-null values.
- * <p/>
- * This implementation is thread-safe (assuming Java's AbstractSequentialList is thread-safe),
- * although its iterators may not be.
- *
- * @param <E>
- * @author harold
- */
-public final class ConsPStack<E> extends AbstractSequentialList<E> implements PStack<E> {
-    //// STATIC FACTORY METHODS ////
-    private static final ConsPStack<Object> EMPTY = new ConsPStack<Object>();
-    //// PRIVATE CONSTRUCTORS ////
-    private final E first;
-    private final ConsPStack<E> rest;
-    private final int size;
-
-    // not externally instantiable (or subclassable):
-    private ConsPStack() { // EMPTY constructor
-        if (EMPTY != null)
-            throw new RuntimeException("empty constructor should only be used once");
-        size = 0;
-        first = null;
-        rest = null;
-    }
-
-
-    private ConsPStack(final E first, final ConsPStack<E> rest) {
-        this.first = first;
-        this.rest = rest;
-
-        size = 1 + rest.size;
-    }
-
-    /**
-     * @param <E>
-     * @return an empty stack
-     */
-    @SuppressWarnings("unchecked")
-    public static <E> ConsPStack<E> empty() {
-        return (ConsPStack<E>) EMPTY;
-    }
-
-    /**
-     * @param <E>
-     * @param e
-     * @return empty().plus(e)
-     */
-    public static <E> ConsPStack<E> singleton(final E e) {
-        return ConsPStack.<E>empty().plus(e);
-    }
-
-    /**
-     * @param <E>
-     * @param list
-     * @return a stack consisting of the elements of list in the order of list.iterator()
-     */
-    @SuppressWarnings("unchecked")
-    public static <E> ConsPStack<E> from(final Collection<? extends E> list) {
-        if (list instanceof ConsPStack)
-            return (ConsPStack<E>) list; //(actually we only know it's ConsPStack<? 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 from(list.iterator());
-    }
-
-    private static <E> ConsPStack<E> from(final Iterator<? extends E> i) {
-        if (!i.hasNext()) return empty();
-        E e = i.next();
-        return from(i).plus(e);
-    }
-
-    //// REQUIRED METHODS FROM AbstractSequentialList ////
-    @Override
-    public int size() {
-        return size;
-    }
-
-    @Override
-    public ListIterator<E> listIterator(final int index) {
-        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
-
-        return new ListIterator<E>() {
-            int i = index;
-            ConsPStack<E> next = subList(index);
-
-            public boolean hasNext() {
-                return next.size > 0;
-            }
-
-            public boolean hasPrevious() {
-                return i > 0;
-            }
-
-            public int nextIndex() {
-                return index;
-            }
-
-            public int previousIndex() {
-                return index - 1;
-            }
-
-            public E next() {
-                E e = next.first;
-                next = next.rest;
-                return e;
-            }
-
-            public E previous() {
-                System.err.println("ConsPStack.listIterator().previous() is inefficient, don't use it!");
-                next = subList(index - 1); // go from beginning...
-                return next.first;
-            }
-
-            public void add(final E o) {
-                throw new UnsupportedOperationException();
-            }
-
-            public void remove() {
-                throw new UnsupportedOperationException();
-            }
-
-            public void set(final E o) {
-                throw new UnsupportedOperationException();
-            }
-        };
-    }
-
-
-    //// OVERRIDDEN METHODS FROM AbstractSequentialList ////
-    @Override
-    public ConsPStack<E> subList(final int start, final int end) {
-        if (start < 0 || end > size || start > end)
-            throw new IndexOutOfBoundsException();
-        if (end == size) // want a substack
-            return subList(start); // this is faster
-        if (start == end) // want nothing
-            return empty();
-        if (start == 0) // want the current element
-            return new ConsPStack<E>(first, rest.subList(0, end - 1));
-        // otherwise, don't want the current element:
-        return rest.subList(start - 1, end - 1);
-    }
-
-
-    //// IMPLEMENTED METHODS OF PStack ////
-    public ConsPStack<E> plus(final E e) {
-        return new ConsPStack<E>(e, this);
-    }
-
-    public ConsPStack<E> plusAll(final Collection<? extends E> list) {
-        ConsPStack<E> result = this;
-        for (E e : list)
-            result = result.plus(e);
-        return result;
-    }
-
-    public ConsPStack<E> plus(final int i, final E e) {
-        if (i < 0 || i > size)
-            throw new IndexOutOfBoundsException();
-        if (i == 0) // insert at beginning
-            return plus(e);
-        return new ConsPStack<E>(first, rest.plus(i - 1, e));
-    }
-
-    public ConsPStack<E> plusAll(final int i, final Collection<? extends E> list) {
-        // TODO inefficient if list.isEmpty()
-        if (i < 0 || i > size)
-            throw new IndexOutOfBoundsException();
-        if (i == 0)
-            return plusAll(list);
-        return new ConsPStack<E>(first, rest.plusAll(i - 1, list));
-    }
-
-    public ConsPStack<E> minus(final Object e) {
-        if (size == 0)
-            return this;
-        if (first.equals(e)) // found it
-            return rest; // don't recurse (only remove one)
-        // otherwise keep looking:
-        ConsPStack<E> newRest = rest.minus(e);
-        if (newRest == rest) return this;
-        return new ConsPStack<E>(first, newRest);
-    }
-
-    public ConsPStack<E> minus(final int i) {
-        return minus(get(i));
-    }
-
-    public ConsPStack<E> minusAll(final Collection<?> list) {
-        if (size == 0)
-            return this;
-        if (list.contains(first)) // get rid of current element
-            return rest.minusAll(list); // recursively delete all
-        // either way keep looking:
-        ConsPStack<E> newRest = rest.minusAll(list);
-        if (newRest == rest) return this;
-        return new ConsPStack<E>(first, newRest);
-    }
-
-    public ConsPStack<E> with(final int i, final E e) {
-        if (i < 0 || i >= size)
-            throw new IndexOutOfBoundsException();
-        if (i == 0) {
-            if (first.equals(e)) return this;
-            return new ConsPStack<E>(e, rest);
-        }
-        ConsPStack<E> newRest = rest.with(i - 1, e);
-        if (newRest == rest) return this;
-        return new ConsPStack<E>(first, newRest);
-    }
-
-    public ConsPStack<E> subList(final int start) {
-        if (start < 0 || start > size)
-            throw new IndexOutOfBoundsException();
-        if (start == 0)
-            return this;
-        return rest.subList(start - 1);
-    }
-}

http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/Empty.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/pcollections/Empty.java b/modules/core/src/main/java/org/pcollections/Empty.java
deleted file mode 100644
index ab7a260..0000000
--- a/modules/core/src/main/java/org/pcollections/Empty.java
+++ /dev/null
@@ -1,47 +0,0 @@
-package org.pcollections;
-
-/* Mike Klein, 2/27/2009 */
-
-/* Empty remembers which classes implement the interface you want,
- * so you don't have to.
- */
-
-/**
- * A static utility class for getting empty PCollections backed by the 'default'
- * implementations.
- *
- * @author mtklein
- */
-public final class Empty {
-    //non-instantiable:
-    private Empty() {
-    }
-
-    public static <E> PStack<E> stack() {
-        return ConsPStack.empty();
-    }
-
-    public static <E> PQueue<E> queue() {
-        return AmortizedPQueue.empty();
-    }
-
-    public static <E> PVector<E> vector() {
-        return TreePVector.empty();
-    }
-
-    public static <E> PSet<E> set() {
-        return HashTreePSet.empty();
-    }
-
-    public static <E> POrderedSet<E> orderedSet() {
-        return OrderedPSet.empty();
-    }
-
-    public static <E> PBag<E> bag() {
-        return HashTreePBag.empty();
-    }
-
-    public static <K, V> PMap<K, V> map() {
-        return HashTreePMap.empty();
-    }
-}

http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/HashPMap.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/pcollections/HashPMap.java b/modules/core/src/main/java/org/pcollections/HashPMap.java
deleted file mode 100644
index e96c1f7..0000000
--- a/modules/core/src/main/java/org/pcollections/HashPMap.java
+++ /dev/null
@@ -1,175 +0,0 @@
-package org.pcollections;
-
-import java.util.*;
-
-
-/**
- * A persistent map from non-null keys to non-null values.
- * <p/>
- * This map uses a given integer map to map hashcodes to lists of elements
- * with the same hashcode. Thus if all elements have the same hashcode, performance
- * is reduced to that of an association list.
- * <p/>
- * This implementation is thread-safe (assuming Java's AbstractMap and AbstractSet are thread-safe),
- * although its iterators may not be.
- *
- * @param <K>
- * @param <V>
- * @author harold
- */
-public final class HashPMap<K, V> extends AbstractMap<K, V> implements PMap<K, V> {
-//// STATIC FACTORY METHODS ////
-
-    //// PRIVATE CONSTRUCTORS ////
-    private final PMap<Integer, PSequence<Entry<K, V>>> intMap;
-    private final int size;
-    //// REQUIRED METHODS FROM AbstractMap ////
-    // this cache variable is thread-safe since assignment in Java is atomic:
-    private Set<Entry<K, V>> entrySet = null;
-
-    // not externally instantiable (or subclassable):
-    private HashPMap(final PMap<Integer, PSequence<Entry<K, V>>> intMap, final int size) {
-        this.intMap = intMap;
-        this.size = size;
-    }
-
-    /**
-     * @param <K>
-     * @param <V>
-     * @param intMap
-     * @return a map backed by an empty version of intMap,
-     * i.e. backed by intMap.minusAll(intMap.keySet())
-     */
-    public static <K, V> HashPMap<K, V> empty(final PMap<Integer, PSequence<Entry<K, V>>> intMap) {
-        return new HashPMap<K, V>(intMap.minusAll(intMap.keySet()), 0);
-    }
-
-    //// PRIVATE STATIC UTILITIES ////
-    private static <K, V> int keyIndexIn(final PSequence<Entry<K, V>> entries, final Object key) {
-        int i = 0;
-        for (Entry<K, V> entry : entries) {
-            if (entry.getKey().equals(key))
-                return i;
-            i++;
-        }
-        return -1;
-    }
-
-    @Override
-    public Set<Entry<K, V>> entrySet() {
-        if (entrySet == null)
-            entrySet = new AbstractSet<Entry<K, V>>() {
-                // REQUIRED METHODS OF AbstractSet //
-                @Override
-                public int size() {
-                    return size;
-                }
-
-                @Override
-                public Iterator<Entry<K, V>> iterator() {
-                    return new SequenceIterator<Entry<K, V>>(intMap.values().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 size;
-    }
-
-    @Override
-    public boolean containsKey(final Object key) {
-        return keyIndexIn(getEntries(key.hashCode()), key) != -1;
-    }
-
-    @Override
-    public V get(final Object key) {
-        PSequence<Entry<K, V>> entries = getEntries(key.hashCode());
-        for (Entry<K, V> entry : entries)
-            if (entry.getKey().equals(key))
-                return entry.getValue();
-        return null;
-    }
-
-    //// IMPLEMENTED METHODS OF PMap////
-    public HashPMap<K, V> plusAll(final Map<? extends K, ? extends V> map) {
-        HashPMap<K, V> result = this;
-        for (Entry<? extends K, ? extends V> entry : map.entrySet())
-            result = result.plus(entry.getKey(), entry.getValue());
-        return result;
-    }
-
-    public HashPMap<K, V> minusAll(final Collection<?> keys) {
-        HashPMap<K, V> result = this;
-        for (Object key : keys)
-            result = result.minus(key);
-        return result;
-    }
-
-    public HashPMap<K, V> plus(final K key, final V value) {
-        PSequence<Entry<K, V>> entries = getEntries(key.hashCode());
-        int size0 = entries.size(),
-            i = keyIndexIn(entries, key);
-        if (i != -1) entries = entries.minus(i);
-        entries = entries.plus(new org.pcollections.SimpleImmutableEntry<K, V>(key, value));
-        return new HashPMap<K, V>(intMap.plus(key.hashCode(), entries),
-            size - size0 + entries.size());
-    }
-
-    public HashPMap<K, V> minus(final Object key) {
-        PSequence<Entry<K, V>> entries = getEntries(key.hashCode());
-        int i = keyIndexIn(entries, key);
-        if (i == -1) // key not in this
-            return this;
-        entries = entries.minus(i);
-        if (entries.size() == 0) // get rid of the entire hash entry
-            return new HashPMap<K, V>(intMap.minus(key.hashCode()),
-                size - 1);
-        // otherwise replace hash entry with new smaller one:
-        return new HashPMap<K, V>(intMap.plus(key.hashCode(), entries),
-            size - 1);
-    }
-
-    //// PRIVATE UTILITIES ////
-    private PSequence<Entry<K, V>> getEntries(final int hash) {
-        PSequence<Entry<K, V>> entries = intMap.get(hash);
-        if (entries == null) return ConsPStack.empty();
-        return entries;
-    }
-
-    static class SequenceIterator<E> implements Iterator<E> {
-        private final Iterator<PSequence<E>> i;
-        private PSequence<E> seq = ConsPStack.empty();
-
-        SequenceIterator(Iterator<PSequence<E>> i) {
-            this.i = i;
-        }
-
-        public boolean hasNext() {
-            return seq.size() > 0 || i.hasNext();
-        }
-
-        public E next() {
-            if (seq.size() == 0)
-                seq = i.next();
-            final E result = seq.get(0);
-            seq = seq.subList(1, seq.size());
-            return result;
-        }
-
-        public void remove() {
-            throw new UnsupportedOperationException();
-        }
-    }
-}

http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/c1f89b21/modules/core/src/main/java/org/pcollections/HashTreePBag.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/pcollections/HashTreePBag.java b/modules/core/src/main/java/org/pcollections/HashTreePBag.java
deleted file mode 100644
index 51dc434..0000000
--- a/modules/core/src/main/java/org/pcollections/HashTreePBag.java
+++ /dev/null
@@ -1,47 +0,0 @@
-package org.pcollections;
-
-import java.util.*;
-
-
-/**
- * A static convenience class for creating efficient persistent bags.
- * <p/>
- * This class simply creates MapPBags backed by HashTreePMaps.
- *
- * @author harold
- */
-public final class HashTreePBag {
-    private static final MapPBag<Object> EMPTY
-        = MapPBag.empty(HashTreePMap.<Object, Integer>empty());
-
-    // not instantiable (or subclassable):
-    private HashTreePBag() {
-    }
-
-    /**
-     * @param <E>
-     * @return an empty bag
-     */
-    @SuppressWarnings("unchecked")
-    public static <E> MapPBag<E> empty() {
-        return (MapPBag<E>) EMPTY;
-    }
-
-    /**
-     * @param <E>
-     * @param e
-     * @return empty().plus(e)
-     */
-    public static <E> MapPBag<E> singleton(final E e) {
-        return HashTreePBag.<E>empty().plus(e);
-    }
-
-    /**
-     * @param <E>
-     * @param list
-     * @return empty().plusAll(map)
-     */
-    public static <E> MapPBag<E> from(final Collection<? extends E> list) {
-        return HashTreePBag.<E>empty().plusAll(list);
-    }
-}


Mime
View raw message