CopyOnWriteTreeMap.java

/*
 * MIT License
 *
 * Copyright (c) 2026 Casper Kuethe
 * All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

package com.casperswebsites.util.concurrent;

import java.io.Serial;
import java.io.Serializable;
import java.util.*;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentNavigableMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

/**
 * A concurrent {@link ConcurrentNavigableMap} implementation.
 * The map is sorted according to the {@linkplain Comparable natural
 * ordering} of its keys, or by a {@link Comparator} provided at map
 * creation time, depending on which constructor is used.
 *
 * <p>
 * This class implements a Copy-on-Write (CoW) variant of a <a
 * href="https://en.wikipedia.org/wiki/Red%E2%80%93black_tree" target="_top">
 * Red-black Tree</a>, the same algorithm used in {@link TreeMap}, providing
 * expected <i>log(n)</i> time
 * cost for the {@code containsKey}, {@code get}, {@code put} and
 * {@code remove} operations and their variants. Insertion, removal,
 * update, and access operations safely execute concurrently by
 * multiple threads.
 * </p>
 * <p>
 *
 * <p>
 * Unlike other CoW implementations that copy all underlying
 * nodes, {@code CopyOnWriteTreeMap} is implemented by copying only the nodes
 * that are necessary to be copied, then atomically swapping the root.
 * </p>
 *
 * <p>
 * Iterators and spliterators are <i>strongly consistent</i>.
 *
 * <p>
 * All {@code Map.Entry} pairs returned by methods in this class
 * and its views represent snapshots of mappings at the time they were
 * produced. They do <em>not</em> support the {@code Entry.setValue}
 * method. (Note however that it is possible to change mappings in the
 * associated map using {@code put}, {@code putIfAbsent}, or
 * {@code replace}, depending on exactly which effect you need.)
 *
 * 
 * <p>
 * This class and its views and iterators implement most of the
 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
 * interfaces. Like most other concurrent collections, this class does
 * <em>not</em> permit the use of {@code null} keys or values because some
 * null return values cannot be reliably distinguished from the absence of
 * elements.
 * </p>
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 * @author Casper Kuethe
 */
public class CopyOnWriteTreeMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentNavigableMap<K, V>, Cloneable, Serializable {

    @Serial
    private static final long serialVersionUID = -8079617966180616297L;

    /**
     * The comparator used to maintain order in this map, or null if using
     * natural ordering. (Non-private to simplify access in nested classes.)
     *
     * @serial
     */
    @SuppressWarnings("serial") // Conditionally serializable
    final Comparator<? super K> comparator;

    /**
     * Root element
     */
    private transient AtomicReference<Node<K, V>> root;
    /**
     * Element count
     */
    private transient AtomicInteger size;
    /**
     * Lazily initialized key set
     */
    private transient KeySet<K, V> keySet;
    /**
     * Lazily initialized values collection
     */
    private transient Values<K, V> values;
    /**
     * Lazily initialized entry set
     */
    private transient EntrySet<K, V> entrySet;
    /**
     * Lazily initialized descending map
     */
    private transient SubMap<K, V> descendingMap;

    private static final int MAX_TREE_HEIGHT = 64;

    private static final int SPIN_THRESHOLD = 10;

    private int backoff(int spins) {
        if (spins < SPIN_THRESHOLD) {
            Thread.onSpinWait();
            return spins + 1;
        } else {
            // spin failed, use the nuclear option
            synchronized (root) {
            }
            return 0; // reset after blocking
        }
    }

    // @SuppressWarnings("unchecked")
    // private static <K, V> PathBuffer<K, V> createPathBuffer() {
    // return new PathBuffer<>(MAX_TREE_HEIGHT);
    // }

    // private static final ThreadLocal<ArrayDeque<Node<K,V>>> STACK_POOL =
    // ThreadLocal.withInitial(ArrayDeque::new);

    @SuppressWarnings({ "rawtypes", "unchecked" })
    private static final ThreadLocal<PathBuffer<?, ?>> PATH_BUFFER_CACHE = ThreadLocal
            .withInitial(() -> new PathBuffer(MAX_TREE_HEIGHT * 2));

    @SuppressWarnings("unchecked")
    private static <K, V> PathBuffer<K, V> getPathBuffer() {
        PathBuffer<K, V> pb = (PathBuffer<K, V>) PATH_BUFFER_CACHE.get();
        pb.clear();
        return pb;
    }

    private static <K, V> PathBuffer<K, V> createPathBuffer() {
        return new PathBuffer<>(MAX_TREE_HEIGHT * 2);
    }

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    /**
     * A node in a Red-black tree holds a key and a value and can have a color,
     * either red or black.
     */
    static final class Node<K, V> implements Map.Entry<K, V> {
        final K key;
        V value;
        Node<K, V> left;
        Node<K, V> right;
        boolean color;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.color = RED;
        }

        Node(K key, V value, boolean color, Node<K, V> left, Node<K, V> right) {
            this.key = key;
            this.value = value;
            this.color = color;
            this.left = left;
            this.right = right;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            throw new UnsupportedOperationException();
        }

        /**
         * Copies the current node with a different value
         *
         * @param newValue
         * @return the new node
         */
        Node<K, V> withValue(V newValue) {
            return new Node<>(key, newValue, color, left, right);
        }

        /**
         * Copies the current node with a different color
         *
         * @param newColor
         * @return the new node
         */
        Node<K, V> withColor(boolean newColor) {
            return new Node<>(key, value, newColor, left, right);
        }

        /**
         * Copies the current node with a different left node
         *
         * @param newLeft
         * @return the new node
         */
        Node<K, V> withLeft(Node<K, V> newLeft) {
            return new Node<>(key, value, color, newLeft, right);
        }

        /**
         * Copies the current node with a different right node
         *
         * @param newRight
         * @return the new node
         */
        Node<K, V> withRight(Node<K, V> newRight) {
            return new Node<>(key, value, color, left, newRight);
        }

        /**
         * @return a copy of the current node
         */
        Node<K, V> copy() {
            return new Node<K, V>(key, value, color, left, right);
        }

        public boolean equals(Object o) {
            return o instanceof Node<?, ?> e && key.equals(e.key) && value.equals(e.value);
        }
    }

    private static <K, V> boolean colorOf(Node<K, V> node) {
        return node == null ? BLACK : node.color;
    }

    private static <K, V> Node<K, V> leftOf(Node<K, V> node) {
        return node == null ? null : node.left;
    }

    private static <K, V> Node<K, V> rightOf(Node<K, V> node) {
        return node == null ? null : node.right;
    }

    private static <K, V> boolean keyEquals(Node<K, V> a, Node<K, V> b) {
        return a != null && b != null && a.key.equals(b.key);
    }

    /**
     * Represents the relative offset in a {@code PathBuffer} to get the
     * corresponding relation.
     *
     * <p>
     * For example, the index of the current node's parent is
     * {@code pointer - NodePathOffset.PARENT.ordinal()}
     * equals {@code pointer - 2}.
     * </p>
     */
    enum NodePathOffset {
        CURRENT,
        SIBLING,
        PARENT,
        UNCLE,
        GRANDPARENT;
    }

    private final static boolean LEFT = false;
    private final static boolean RIGHT = true;

    /**
     * A fixed size reusable buffer that stores the "path" of a node when traversing
     * a binary tree.
     * Allowing easy access to a sibling, parent, uncle, or grandparent relative to
     * a node without
     * the need of a {@code parent} pointer.
     *
     * <p>
     * Every instance of `PathBuffer` has a max size of {@code MAX_TREE_HEIGHT}.
     * This limit means it can store the path of a tree with {@code 2^63 - 1} nodes
     * from the root to its leafs.
     * </p>
     *
     * @param <K>
     * @param <V>
     */
    static final class PathBuffer<K, V> {
        private int pointer = 0;
        private int len = 0;
        private long branches = 0L;
        private final Node<K, V>[] buffer;

        @SuppressWarnings("unchecked")
        public PathBuffer(int size) {
            buffer = new Node[size];
        }

        /**
         * Puts the root of the tree in the buffer. Assumes the buffer is empty.
         *
         * @param root
         */
        public void setRoot(Node<K, V> root) {
            len = 1;
            pointer = 0;
            buffer[0] = root;
        }

        /**
         * @return the root of the tree stored
         */
        public Node<K, V> getRoot() {
            return buffer[0];
        }

        /**
         * @return whether we are at the root
         */
        public boolean atRoot() {
            return pointer == 0;
        }

        public void clear() {
            pointer = 0;
            len = 0;
        }

        /**
         * Add a node and its sibling to the buffer.
         * Sets the current pointer to the current child of `parent`.
         *
         * @param parent
         * @param gotoRight set the current pointer to the right child of `parent`,
         *                  else set current to the left child.
         */
        public void addFrom(Node<K, V> parent, boolean gotoRight) {
            if (pointer + 2 >= len) {
                len += 2;
            }
            pointer += 2;
            assert pointer < buffer.length;
            // current
            buffer[pointer] = gotoRight ? parent.right : parent.left;
            setBranch(pointer, gotoRight);
            // sibling
            buffer[pointer - 1] = gotoRight ? parent.left : parent.right;
            // branches[pointer - 1] = !gotoRight;
            // setBranch(pointer - 1, !gotoRight);
        }

        /**
         * Go to the node at `offset` relative from the current node.
         * Set's current to the root node if the node at `offset` relative from the
         * current node
         * cannot exist.
         *
         * @param offset
         */
        public void gotoNode(NodePathOffset offset) {
            int target = pointer - offset.ordinal();

            pointer = target;
        }

        /**
         * Get a node relative to the current node.
         *
         * @param offset the offset from the current node
         * @return `null` if the node at `offset` doesn't exist.
         */
        public Node<K, V> getNode(NodePathOffset offset) {
            int target = pointer - offset.ordinal();
            if (target < 0)
                return null;
            return buffer[target];
        }

        /**
         * Set a node relative to the current node
         *
         * @param offset the offset from the current node
         * @param node
         */
        public void setNode(NodePathOffset offset, Node<K, V> node) {
            int target = pointer - offset.ordinal();
            assert target >= 0 : "attempted to set node above root";
            buffer[target] = node;
        }

        public void setNode(int target, Node<K, V> node) {
            assert target >= 0 : "attempted to set node above root";
            assert target < len : "attempted to set target out of range";
            buffer[target] = node;
        }

        /**
         * Copies the node relative to the current node and updates the buffer
         *
         * @param offset the offset from the current node
         */
        public void copyNode(NodePathOffset offset) {
            int target = pointer - offset.ordinal();
            assert target >= 0 : "attempted to set node above root";
            buffer[target] = buffer[target].copy();
        }

        /**
         * Colors the node relative to the current node red and updates the buffer
         *
         * @param offset the offset from the current node
         */
        public void colorRed(NodePathOffset offset) {
            int target = pointer - offset.ordinal();
            if (target < 0)
                return;
            buffer[target] = buffer[target].withColor(RED);
        }

        /**
         * Colors the node relative to the current node black and updates the buffer
         *
         * @param offset the offset from the current node
         */
        public void colorBlack(NodePathOffset offset) {
            int target = pointer - offset.ordinal();
            if (target < 0)
                return;
            buffer[target] = buffer[target].withColor(BLACK);
        }

        /**
         * Update the child of the node at `offset` relative from the current node.
         * Does <b>not</b> make a copy of the parent node.
         *
         * @param offset        the offset from the current node
         * @param isRightBranch whether to set the node's right child
         * @param node          the new node
         */
        public void setChildOf(NodePathOffset offset, boolean isRightBranch, Node<K, V> node) {
            int target = pointer - offset.ordinal();
            if (target < 0)
                return;
            // assert target >= 0 : "attempted to set child of node above root";

            if (isRightBranch) {
                buffer[target].right = node;
            } else {
                buffer[target].left = node;
            }
        }

        private void setBranch(int offset, boolean value) {
            if (value) {
                branches |= (1L << (offset / 2));
            } else {
                branches &= ~(1L << (offset / 2));
            }
            // branches[offset] = value;
        }

        /**
         * @param offset
         * @return whether the node at `offset` relative from the current node is its
         *         parents
         *         right or left child
         */
        public boolean getBranch(NodePathOffset offset) {
            int index = (pointer - offset.ordinal()) / 2; // only need to store
            assert index >= 0 : "attempted to get branch from node above root";
            return (branches & (1L << index)) != 0;
            // return branches[index];
        }

        /**
         * @return the current offset in the path buffer
         */
        int getPointer() {
            return pointer;
        }

        /**
         * Set the path buffer to a target pointer
         *
         * @param target
         */
        void setPointer(int target) {
            assert target >= 0 : "attempted to set node above root";
            assert target < len : "attempted to set target out of range";
            pointer = target;
        }

        /* ---------- Testing --------- */

        int size() {
            return len;
        }

        Node<K, V>[] getBuffer() {
            return buffer;
        }
    }

    /**
     * Copy all parent nodes and return the new root node
     *
     * @param pb
     * @return
     */
    private Node<K, V> copyUntilRoot(PathBuffer<K, V> pb) {
        while (!pb.atRoot()) {
            // copy parent
            pb.copyNode(NodePathOffset.PARENT);
            // update child pointer of parent
            pb.setChildOf(
                    NodePathOffset.PARENT,
                    pb.getBranch(NodePathOffset.CURRENT),
                    pb.getNode(NodePathOffset.CURRENT));
            // move up the tree
            pb.gotoNode(NodePathOffset.PARENT);
        }
        return pb.getNode(NodePathOffset.CURRENT);
    }

    /**
     * CLR rotate left. Copies nodes that are changed.
     *
     * @param x
     * @return the new y node
     */
    private Node<K, V> rotateLeft(Node<K, V> x) {
        Node<K, V> y = x.right;
        return y.withLeft(x.withRight(y.left));
    }

    /**
     * CLR rotate right. Copies nodes that are changed.
     *
     * @param y
     * @return the new x node
     */
    private Node<K, V> rotateRight(Node<K, V> y) {
        Node<K, V> x = y.left;
        return x.withRight(y.withLeft(x.right));
    }

    /* ---------------- Utilities -------------- */

    /**
     * Compares using comparator or natural ordering if null. Called only by
     * methods that have performed required type checks.
     */
    @SuppressWarnings({ "unchecked", "rawtypes" })
    static int cpr(Comparator c, Object x, Object y) {
        return (c != null) ? c.compare(x, y) : ((Comparable) x).compareTo(y);
    }

    static <K, V> AbstractMap.SimpleImmutableEntry<K, V> exportNode(Node<K, V> n) {
        return n == null ? null : new AbstractMap.SimpleImmutableEntry<>(n.key, n.value);
    }

    /* ---------------- Traversal -------------- */

    /**
     * Find a node by key
     *
     * @param key
     * @return the node if found, else {@code null}
     */
    final Node<K, V> findNode(Object key) {
        Node<K, V> current = root.get();
        while (current != null) {
            int cmp = cpr(comparator, key, current.key);
            if (cmp < 0) {
                current = current.left;
            } else if (cmp > 0) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }

    /**
     * Find a node by key. Assumes {@code root} is set in the path buffer
     *
     * @param <K>
     * @param <V>
     * @param key
     * @param pb         the path buffer
     * @param comparator
     * @return the node if found, else {@code null}
     */
    static <K, V> Node<K, V> findNode(Object key, PathBuffer<K, V> pb, Comparator<? super K> comparator) {
        Node<K, V> current = pb.getRoot();
        while (current != null) {
            int cmp = cpr(comparator, key, current.key);
            if (cmp < 0) {
                pb.addFrom(current, LEFT);
                current = current.left;
            } else if (cmp > 0) {
                pb.addFrom(current, RIGHT);
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }

    /**
     * Get the successor of the {@code current} node in the path buffer
     *
     * @param pb  the PathBuffer
     * @param <K>
     * @param <V>
     * @return the successor or `null` if there is no successor
     */
    static <K, V> Node<K, V> successor(PathBuffer<K, V> pb) {
        Node<K, V> node = pb.getNode(NodePathOffset.CURRENT);
        if (node == null) {
            return null;
        } else if (node.right != null) {
            pb.addFrom(node, RIGHT);
            node = node.right;
            while (node.left != null) {
                pb.addFrom(node, LEFT);
                node = node.left;
            }
            return node;
        } else {
            while (pb.getNode(NodePathOffset.PARENT) != null && pb.getBranch(NodePathOffset.CURRENT) == RIGHT) {
                pb.gotoNode(NodePathOffset.PARENT);
            }
            pb.gotoNode(NodePathOffset.PARENT);
            return pb.getNode(NodePathOffset.CURRENT);
        }
    }

    /**
     * Get the node with the smalles key in the right subtree of the current node
     *
     * @param pb the path buffer
     * @return the minimum node in the right subtree of the curent node
     */
    private Node<K, V> tree_minimum(PathBuffer<K, V> pb) {
        Node<K, V> n = pb.getNode(NodePathOffset.CURRENT);
        pb.addFrom(n, RIGHT);
        n = n.right;
        while (n != null && n.left != null) {
            pb.addFrom(n, LEFT);
            n = n.left;
        }
        return n;
    }

    /**
     * Get the predecessor of the {@code current} node in the path buffer
     *
     * @param pb  the PathBuffer
     * @param <K>
     * @param <V>
     * @return the predecessor
     */
    static <K, V> Node<K, V> predecessor(PathBuffer<K, V> pb) {
        Node<K, V> node = pb.getNode(NodePathOffset.CURRENT);
        if (node == null) {
            return null;
        } else if (node.left != null) {
            pb.addFrom(node, LEFT);
            node = node.left;
            while (node.right != null) {
                pb.addFrom(node, RIGHT);
                node = node.right;
            }
            return node;
        } else {
            while (pb.getNode(NodePathOffset.PARENT) != null && pb.getBranch(NodePathOffset.CURRENT) == LEFT) {
                pb.gotoNode(NodePathOffset.PARENT);
            }
            pb.gotoNode(NodePathOffset.PARENT);
            return pb.getNode(NodePathOffset.CURRENT);
        }
    }

    /* ---------------- Finding and removing first element -------------- */

    final Node<K, V> findFirst() {
        Node<K, V> current = root.get();
        if (current != null) {
            while (current.left != null)
                current = current.left;
        }
        return current;
    }

    static <K, V> Node<K, V> findFirst(PathBuffer<K, V> pb) {
        Node<K, V> current = pb.getRoot();
        if (current != null) {
            while (current.left != null) {
                pb.addFrom(current, LEFT);
                current = current.left;
            }
        }
        return current;
    }

    final AbstractMap.SimpleImmutableEntry<K, V> findFirstEntry() {
        return exportNode(findFirst());
    }

    /**
     * Removes first entry; returns its snapshot.
     *
     * @return null if empty, else snapshot of first entry
     */
    private AbstractMap.SimpleImmutableEntry<K, V> doRemoveFirstEntry() {
        int spins = 0;
        while (true) {
            Node<K, V> oldRoot = root.get();
            PathBuffer<K, V> pb = getPathBuffer();
            pb.setRoot(oldRoot);
            Node<K, V> node = findFirst(pb);
            if (node != null) {
                if (root.compareAndSet(oldRoot, deleteNode(pb))) {
                    this.size.decrementAndGet();
                    return new AbstractMap.SimpleImmutableEntry<>(node.key, node.value);
                }
                spins = backoff(spins);
            } else {
                return null;
            }

        }
    }

    /* ---------------- Finding and removing last element -------------- */

    final Node<K, V> findLast() {
        Node<K, V> current = root.get();
        if (current != null) {
            while (current.right != null)
                current = current.right;
        }
        return current;
    }

    static <K, V> Node<K, V> findLast(PathBuffer<K, V> pb) {
        Node<K, V> current = pb.getRoot();
        if (current != null) {
            while (current.right != null) {
                pb.addFrom(current, RIGHT);
                current = current.right;
            }
        }
        return current;
    }

    final AbstractMap.SimpleImmutableEntry<K, V> findLastEntry() {
        return exportNode(findLast());
    }

    /**
     * Removes last entry; returns its snapshot. Specialized variant of
     * doRemove.
     *
     * @return null if empty, else snapshot of last entry
     */
    private Map.Entry<K, V> doRemoveLastEntry() {
        int spins = 0;
        while (true) {
            Node<K, V> oldRoot = root.get();
            PathBuffer<K, V> pb = getPathBuffer();
            pb.setRoot(oldRoot);
            Node<K, V> node = findLast(pb);
            if (node != null) {
                if (root.compareAndSet(oldRoot, deleteNode(pb))) {
                    this.size.decrementAndGet();
                    return new AbstractMap.SimpleImmutableEntry<>(node.key, node.value);
                }
                spins = backoff(spins);
            } else {
                return null;
            }
        }
    }

    /* ---------------- Insertion -------------- */

    /**
     * Insert a key-value pair. Replaces the old value if the key has already been
     * inserted.
     *
     * @param key          the key
     * @param value        the key
     * @param onlyIfAbsent if true, will prevent replacing an existing value
     * @return
     */
    private V putInternal(K key, V value, boolean onlyIfAbsent) {
        if (key == null) {
            throw new NullPointerException();
        }

        int spins = 0;

        casLoop: while (true) {
            Node<K, V> oldRoot = root.get();
            if (oldRoot == null) {
                cpr(comparator, key, key); // type check
                // insert root
                Node<K, V> newRoot = new Node<>(key, value);
                newRoot.color = BLACK;
                if (root.compareAndSet(null, newRoot)) {
                    this.size.incrementAndGet();
                    return null;
                }
                spins = backoff(spins);
                continue;
            }

            PathBuffer<K, V> pb = getPathBuffer();
            pb.setRoot(oldRoot);

            Node<K, V> target = oldRoot;
            int cmp;
            do {
                cmp = cpr(comparator, key, target.key);
                if (cmp < 0) {
                    pb.addFrom(target, LEFT);
                    target = target.left;
                } else if (cmp > 0) {
                    pb.addFrom(target, RIGHT);
                    target = target.right;
                } else {
                    // node has same value, replace it and else return the old value
                    V oldValue = target.value;
                    if (!onlyIfAbsent) {
                        pb.setNode(NodePathOffset.CURRENT, target.withValue(value));
                        Node<K, V> newRoot = copyUntilRoot(pb);
                        if (root.compareAndSet(oldRoot, newRoot)) {
                            return oldValue;
                        }
                        spins = backoff(spins);
                        continue casLoop;
                    }
                    return oldValue;
                }
            } while (target != null);
            Node<K, V> createdNode = new Node<K, V>(key, value);
            // insert node in the buffer. left/right pointer of parent is updated in
            // `fixAfterInsertion` or eventually `copyUntilRoot`.
            pb.setNode(NodePathOffset.CURRENT, createdNode);

            Node<K, V> newRoot = fixAfterInsertion(pb);

            if (root.compareAndSet(oldRoot, newRoot)) {
                this.size.incrementAndGet();
                return null;
            }
            spins = backoff(spins);
        }
    }

    /**
     * Rewrite of CLR algorithm to use the {@link PathBuffer} structure.
     * Copies all nodes that need to be changed up until the root.
     *
     * @param pb the PathBuffer
     * @return the new root node
     */
    private Node<K, V> fixAfterInsertion(PathBuffer<K, V> pb) {
        // case 1 don't need to do anything if the parent is null (the root)
        // case 2: if the parent is red rule 4 is violated, because inserted nodes
        // are always red
        while (pb.getNode(NodePathOffset.CURRENT) != null && !pb.atRoot()
                && colorOf(pb.getNode(NodePathOffset.PARENT)) == RED) {
            boolean parentBranch = pb.getBranch(NodePathOffset.PARENT);
            // update child pointer from the parent
            pb.copyNode(NodePathOffset.PARENT);
            pb.setChildOf(
                    NodePathOffset.PARENT,
                    pb.getBranch(NodePathOffset.CURRENT),
                    pb.getNode(NodePathOffset.CURRENT));

            if (pb.getNode(NodePathOffset.UNCLE) != null && colorOf(pb.getNode(NodePathOffset.UNCLE)) == RED) {
                // case 3: uncle is red: recolour the grandparent and its children (rule 4)
                pb.colorBlack(NodePathOffset.PARENT);
                pb.colorBlack(NodePathOffset.UNCLE);
                pb.colorRed(NodePathOffset.GRANDPARENT);
                // update child pointers
                pb.setChildOf(NodePathOffset.GRANDPARENT, parentBranch, pb.getNode(NodePathOffset.PARENT));
                pb.setChildOf(NodePathOffset.GRANDPARENT, !parentBranch, pb.getNode(NodePathOffset.UNCLE));
                // update target pointer
                pb.gotoNode(NodePathOffset.GRANDPARENT);
            } else {
                // case 4: uncle is black (nil) and an "inner child"
                // i.e. the current node, its parent and grandparent
                // form a triangle around the uncle.
                // balance the tree by performing a RL or RL rotation depending on which side
                // the uncle is relative to the current node
                Node<K, V> newNode;
                pb.copyNode(NodePathOffset.GRANDPARENT);
                if (parentBranch == LEFT && pb.getBranch(NodePathOffset.CURRENT) == RIGHT) {
                    newNode = rotateLeft(pb.getNode(NodePathOffset.PARENT));
                    pb.setNode(NodePathOffset.PARENT, newNode);
                } else if (parentBranch == RIGHT && pb.getBranch(NodePathOffset.CURRENT) == LEFT) {
                    newNode = rotateRight(pb.getNode(NodePathOffset.PARENT));
                    pb.setNode(NodePathOffset.PARENT, newNode);
                }
                // at this point the node is always an "outer child"
                // i.e. the current node and its parent and grandparent form a straight line
                // at this point both the node and its parent are red and its grandparent is
                // black
                // if we rotate the grandparent and recolour it and the nodes parent the tree is
                // fixed

                pb.colorBlack(NodePathOffset.PARENT);
                pb.colorRed(NodePathOffset.GRANDPARENT);
                // update child pointer
                pb.setChildOf(
                        NodePathOffset.GRANDPARENT,
                        pb.getBranch(NodePathOffset.PARENT),
                        pb.getNode(NodePathOffset.PARENT));
                if (parentBranch == LEFT) {
                    newNode = rotateRight(pb.getNode(NodePathOffset.GRANDPARENT));
                    pb.setNode(NodePathOffset.GRANDPARENT, newNode);

                } else {
                    newNode = rotateLeft(pb.getNode(NodePathOffset.GRANDPARENT));
                    pb.setNode(NodePathOffset.GRANDPARENT, newNode);
                }
                pb.gotoNode(NodePathOffset.GRANDPARENT);
                // tree is fixed at this point (parent is black) and we don't need to check
                // again
                break;
            }
        }
        // walk up to the root node and copy the parents
        Node<K, V> newRoot = copyUntilRoot(pb);
        // root node always has to be black
        newRoot.color = BLACK;
        return newRoot;
    }

    /* ---------------- Deletion -------------- */

    /**
     * Delete the associated node
     *
     * @param key   the key
     * @param value value if non-null, the value that must be associated with the
     *              key
     * @return the old value, or null if not found
     */
    private V doRemove(Object key, Object value) {
        if (key == null) {
            throw new NullPointerException();
        }

        int spins = 0;
        while (true) {
            Node<K, V> oldRoot = root.get();
            PathBuffer<K, V> pb = getPathBuffer();
            pb.setRoot(oldRoot);
            Node<K, V> node = findNode(key, pb, comparator);
            if (node == null) {
                return null;
            }

            if (value != null && !value.equals(node.value)) {
                return null;
            } else {
                // delete
                if (root.compareAndSet(oldRoot, deleteNode(pb))) {
                    this.size.decrementAndGet();
                    return node.value;
                }
                spins = backoff(spins);
            }
        }
    }

    private Node<K, V> deleteNode(PathBuffer<K, V> pb) {
        Node<K, V> z = pb.getNode(NodePathOffset.CURRENT);
        Node<K, V> y = z;
        boolean originalColor = y.color;

        Node<K, V> replacement = z.left == null ? z.right : z.left;

        if (replacement == null && pb.atRoot()) {
            // deleting the last node
            return null;
        } else if (z.left == null) {
            pb.setNode(NodePathOffset.CURRENT, z.right); // x = z.right
        } else if (z.right == null) {
            pb.setNode(NodePathOffset.CURRENT, z.left); // x = z.left
        } else {
            int zPointer = pb.getPointer();
            y = tree_minimum(pb);
            boolean isDirectChild = y == z.right;
            originalColor = colorOf(y);

            pb.setNode(NodePathOffset.CURRENT, y.right); // x = y.right
            y = y.copy();
            if (!isDirectChild) {
                y.right = z.right; // successor is further down the tree
            }
            y.left = z.left;
            y.color = z.color;
            pb.setNode(zPointer, y); // replace z with its successor
        }

        if (originalColor == BLACK) {
            return fixAfterDeletion(pb); // rb-delete-fixup(x)
        } else {
            return copyUntilRoot(pb);
        }
    }

    /**
     * Fix after deletion function from CLR.
     * Variable names follow the examples from the book.
     *
     * @param pb
     * @return
     */
    private Node<K, V> fixAfterDeletion(PathBuffer<K, V> pb) {
        boolean shouldColorCurrentBlack = true;
        while (!pb.atRoot() && colorOf(pb.getNode(NodePathOffset.CURRENT)) == BLACK) {
            boolean branch = pb.getBranch(NodePathOffset.CURRENT);
            // update child pointer from the parent
            pb.copyNode(NodePathOffset.PARENT);
            pb.setChildOf(
                    NodePathOffset.PARENT,
                    branch,
                    pb.getNode(NodePathOffset.CURRENT));

            if (branch == LEFT) {
                if (colorOf(pb.getNode(NodePathOffset.SIBLING)) == RED) {
                    // case 1: x's sibling is red
                    Node<K, V> D = rotateLeft(pb.getNode(NodePathOffset.PARENT));
                    D.color = BLACK;
                    D.left.color = RED;
                    pb.setNode(NodePathOffset.PARENT, D); // set B as parent of A and C
                    pb.setNode(NodePathOffset.SIBLING, D.right); // set E
                    pb.setNode(NodePathOffset.CURRENT, D.left);
                    pb.addFrom(D.left, LEFT); // set A and C in correct positions
                    // x (current node in path buffer) is now A again
                }
                if (colorOf(leftOf(pb.getNode(NodePathOffset.SIBLING))) == BLACK
                        && colorOf(rightOf(pb.getNode(NodePathOffset.SIBLING))) == BLACK) {
                    pb.colorRed(NodePathOffset.SIBLING); // copy node
                    pb.copyNode(NodePathOffset.PARENT);
                    pb.setChildOf(NodePathOffset.PARENT, RIGHT, pb.getNode(NodePathOffset.SIBLING));
                    pb.gotoNode(NodePathOffset.PARENT);
                } else {
                    if (colorOf(rightOf(pb.getNode(NodePathOffset.SIBLING))) == BLACK) {
                        // case 3
                        Node<K, V> newW = rotateRight(pb.getNode(NodePathOffset.SIBLING));
                        newW.color = BLACK;
                        newW.right.color = RED;
                        pb.setNode(NodePathOffset.SIBLING, newW);
                        pb.copyNode(NodePathOffset.PARENT);
                        pb.setChildOf(NodePathOffset.PARENT, RIGHT, newW);
                    }
                    // case 4
                    Node<K, V> c = rotateLeft(pb.getNode(NodePathOffset.PARENT));
                    c.color = colorOf(pb.getNode(NodePathOffset.PARENT));
                    c.left.color = BLACK;
                    c.right = c.right.withColor(BLACK);
                    // only need to update parent node in the buffer. Don't need
                    pb.setNode(NodePathOffset.PARENT, c);
                    pb.gotoNode(NodePathOffset.PARENT);
                    shouldColorCurrentBlack = false;
                    break;
                }
            } else { // symmetric
                if (colorOf(pb.getNode(NodePathOffset.SIBLING)) == RED) {
                    Node<K, V> D = rotateRight(pb.getNode(NodePathOffset.PARENT));
                    D.color = BLACK;
                    D.right.color = RED;
                    pb.setNode(NodePathOffset.PARENT, D);
                    pb.setNode(NodePathOffset.SIBLING, D.left);
                    pb.setNode(NodePathOffset.CURRENT, D.right);
                    pb.addFrom(D.right, RIGHT);
                }
                if (colorOf(rightOf(pb.getNode(NodePathOffset.SIBLING))) == BLACK
                        && colorOf(leftOf(pb.getNode(NodePathOffset.SIBLING))) == BLACK) {
                    pb.colorRed(NodePathOffset.SIBLING);
                    pb.copyNode(NodePathOffset.PARENT);
                    pb.setChildOf(NodePathOffset.PARENT, LEFT, pb.getNode(NodePathOffset.SIBLING));
                    pb.gotoNode(NodePathOffset.PARENT);
                } else {
                    if (colorOf(leftOf(pb.getNode(NodePathOffset.SIBLING))) == BLACK) {
                        Node<K, V> newW = rotateLeft(pb.getNode(NodePathOffset.SIBLING));
                        newW.color = BLACK;
                        newW.left.color = RED;
                        pb.setNode(NodePathOffset.SIBLING, newW);
                        pb.copyNode(NodePathOffset.PARENT);
                        pb.setChildOf(NodePathOffset.PARENT, LEFT, newW);
                    }
                    Node<K, V> c = rotateRight(pb.getNode(NodePathOffset.PARENT));
                    c.color = colorOf(pb.getNode(NodePathOffset.PARENT));
                    c.right.color = BLACK;
                    c.left = c.left.withColor(BLACK);
                    pb.setNode(NodePathOffset.PARENT, c);
                    pb.gotoNode(NodePathOffset.PARENT);
                    shouldColorCurrentBlack = false;
                    break;
                }
            }
        }
        if (shouldColorCurrentBlack)
            pb.colorBlack(NodePathOffset.CURRENT);

        Node<K, V> newRoot = copyUntilRoot(pb);
        newRoot.color = BLACK;
        return newRoot;
    }

    /* ---------------- Relational operations -------------- */
    // Control values OR'ed as arguments to findNear
    private static final int EQ = 1;
    private static final int LT = 2;
    private static final int GT = 0; // Actually checked as !LT

    /**
     * Utility for ceiling, floor, lower, higher methods.
     *
     * @param key the key
     * @param rel the relation -- OR'ed combination of EQ, LT, GT
     * @return nearest node fitting relation, or null if no such
     */
    final Node<K, V> findNear(K key, int rel, Comparator<? super K> cmp) {
        PathBuffer<K, V> pb = getPathBuffer();
        pb.setRoot(root.get());
        return findNear(pb, key, rel, cmp);
    }

    final Node<K, V> findNear(PathBuffer<K, V> pb, K key, int rel, Comparator<? super K> cmp) {
        if (key == null) {
            throw new NullPointerException();
        }

        Node<K, V> nearest = null;
        Node<K, V> current = pb.getRoot();
        int c;
        int nearestPointer = 0;

        while (current != null) {
            c = cpr(cmp, key, current.key);
            if (c == 0) {
                if ((rel & EQ) != 0) {
                    return current;
                } else if ((rel & LT) != 0) {
                    pb.addFrom(current, LEFT);
                    current = current.left;
                } else {
                    pb.addFrom(current, RIGHT);
                    current = current.right;
                }
            } else if (c < 0) {
                if ((rel & LT) == 0) {
                    nearest = current;
                    nearestPointer = pb.getPointer();
                }
                pb.addFrom(current, LEFT);
                current = current.left;
            } else {
                if ((rel & LT) != 0) {
                    nearest = current;
                    nearestPointer = pb.getPointer();
                }
                pb.addFrom(current, RIGHT);
                current = current.right;
            }
        }
        pb.setPointer(nearestPointer);
        return nearest;
    }

    /**
     * Variant of findNear returning SimpleImmutableEntry
     *
     * @param key the key
     * @param rel the relation -- OR'ed combination of EQ, LT, GT
     * @return Entry fitting relation, or null if no such
     */
    final AbstractMap.SimpleImmutableEntry<K, V> findNearEntry(K key, int rel, Comparator<? super K> cmp) {
        return exportNode(findNear(key, rel, cmp));

    }

    /* ---------------- Constructors -------------- */

    public CopyOnWriteTreeMap() {
        // this.comparator = (a, b) -> ((Comparable<K>) a).compareTo(b);
        this.comparator = null;
        this.root = new AtomicReference<>(null);
        this.size = new AtomicInteger(0);
    }

    public CopyOnWriteTreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
        this.root = new AtomicReference<>(null);
        this.size = new AtomicInteger(0);
    }

    // copy constructor
    public CopyOnWriteTreeMap(CopyOnWriteTreeMap<K, V> m) {
        this.comparator = m.comparator;
        this.keySet = null;
        this.entrySet = null;
        this.values = null;
        this.descendingMap = null;
        this.root = new AtomicReference<>(m.root.get());
        this.size = new AtomicInteger(m.count());
    }

    public CopyOnWriteTreeMap(Map<? extends K, ? extends V> m) {
        this.comparator = null;
        this.root = new AtomicReference<>(null);
        this.size = new AtomicInteger(0);
        putAll(m);
    }

    public CopyOnWriteTreeMap(SortedMap<K, ? extends V> m) {
        this.comparator = m.comparator();
        this.root = new AtomicReference<>(null);
        this.size = new AtomicInteger(0);
        // buildFromSorted(m); TODO:!
        putAll(m);
    }

    /**
     * Returns a shallow copy of this {@code CopyOnWriteTreeMap} instance.
     * Internal nodes don't need to be cloned due to CoW semantics
     * (The keys and valeus themselves are not cloned.)
     */
    public CopyOnWriteTreeMap<K, V> clone() {
        // copy constructor intiializes all nods??
        try {
            @SuppressWarnings("unchecked")
            CopyOnWriteTreeMap<K, V> clone = (CopyOnWriteTreeMap<K, V>) super.clone();
            clone.keySet = null;
            clone.entrySet = null;
            clone.values = null;
            clone.descendingMap = null;
            clone.root = new AtomicReference<>(root.get());

            // recount
            clone.size = new AtomicInteger(clone.count());
            return clone;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    int count() {
        PathBuffer<K, V> pb = getPathBuffer();
        pb.setRoot(root.get());
        Node<K, V> n = findFirst(pb);
        int count = 0;
        while (n != null) {
            count++;
            n = successor(pb);
        }
        return count;
    }

    /* ---------------- Serialization -------------- */

    private static final Object NULL_MARKER = "null";

    /**
     *
     * @param s
     * @throws java.io.IOException
     * @serialData the Key (object), value (Object) and color (boolean) for each
     *             mapping,
     *             followed by {@code null}. Nodes are written in BFS fashion
     *             following the tree
     */
    @Serial
    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
        s.defaultWriteObject();

        // write out keys and values and color
        Node<K, V> n = root.get();
        Queue<Node<K, V>> queue = new LinkedList<>();
        queue.add(n);

        while (!queue.isEmpty()) {
            n = queue.poll();
            if (n == null) {
                s.writeObject(NULL_MARKER);
            } else {
                s.writeObject(n.key);
                s.writeObject(n.value);
                s.writeBoolean(n.color);

                queue.add(n.left);
                queue.add(n.right);
            }
        }

        s.writeObject(null);
    }

    @Serial
    @SuppressWarnings("unchecked")
    private void readObject(final java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();

        int count = 0;
        Queue<Node<K, V>> queue = new LinkedList<>();
        Node<K, V> current;
        Node<K, V> root;

        Object first = s.readObject();
        if (first == null || first.equals(NULL_MARKER)) {
            this.root = new AtomicReference<>(null);
            this.size = new AtomicInteger(0);
            return;
        }
        K k = (K) first;
        V v = (V) s.readObject();
        if (v == null) {
            throw new NullPointerException();
        }
        boolean color = s.readBoolean();
        current = new Node<>(k, v);
        current.color = color;

        count++;
        root = current;
        queue.add(current);

        while (!queue.isEmpty()) {
            current = queue.poll();

            Object left = s.readObject();
            if (left == null) {
                break;
            }

            if (!left.equals(NULL_MARKER)) {
                k = (K) left;
                v = (V) s.readObject();
                if (v == null) {
                    throw new NullPointerException();
                }
                color = s.readBoolean();
                current.left = new Node<>(k, v);
                current.left.color = color;
                count++;
                queue.add(current.left);
            }

            Object right = s.readObject();
            if (right == null) {
                break;
            }

            if (!right.equals(NULL_MARKER)) {
                k = (K) right;
                v = (V) s.readObject();
                if (v == null) {
                    throw new NullPointerException();
                }
                color = s.readBoolean();
                current.right = new Node<>(k, v);
                current.right.color = color;
                count++;
                queue.add(current.right);
            }
        }

        this.root = new AtomicReference<>(root);
        this.size = new AtomicInteger(count);
    }

    /* ------ Map API methods ------ */

    @Override
    public boolean containsKey(Object key) {
        return get(key) != null;
    }

    public V get(Object key) {
        Node<K, V> n = findNode(key);
        return n == null ? null : n.value;
    }

    @Override
    public V getOrDefault(Object key, V defaultValue) {
        V v;
        return ((v = get(key)) == null) ? defaultValue : v;
    }

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key   key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with the specified key, or
     *         {@code null} if there was no mapping for the key
     * @throws ClassCastException   if the specified key cannot be compared
     *                              with the keys currently in the map
     * @throws NullPointerException if the specified key or value is null
     */
    public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        return putInternal(key, value, false);
    }

    @Override
    public V remove(Object key) {
        return doRemove(key, null);
    }

    @Override
    public boolean containsValue(Object value) {
        if (value == null)
            throw new NullPointerException();

        PathBuffer<K, V> pb = getPathBuffer();
        pb.setRoot(root.get());
        for (Node<K, V> node = findFirst(pb); node != null; node = successor(pb)) {
            if (node.value.equals(value)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int size() {
        return this.size.get();
    }

    @Override
    public boolean isEmpty() {
        return root.get() == null;
    }

    @Override
    public void clear() {
        int spins = 0;
        while (true) {
            if (root.compareAndSet(root.get(), null)) {
                size.set(0);
                return;
            }
            spins = backoff(spins);
        }
    }

    /**
     * {@inheritDoc}
     *
     * @throws NullPointerException if the specified key is null or the
     *                              mappingFunction is null
     */
    @Override
    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
        if (key == null || mappingFunction == null) {
            throw new NullPointerException();
        }
        V currentValue = get(key);
        V result = null;
        if (currentValue == null && ((result = mappingFunction.apply(key)) != null)) {
            V putResult = putInternal(key, result, true);
            currentValue = putResult == null ? result : putResult;
        }
        return currentValue;
    }

    /**
     * @throws NullPointerException if the specified key is null or the
     *                              remappingFunction is null
     * @{inheritDoc}
     */
    @Override
    public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (key == null || remappingFunction == null) {
            throw new NullPointerException();
        }
        int spins = 0;
        while (true) {
            PathBuffer<K, V> pb = getPathBuffer();
            Node<K, V> oldRoot = root.get();
            pb.setRoot(oldRoot);
            Node<K, V> n = findNode(key, pb, comparator);
            if (n == null)
                return null;

            V r = remappingFunction.apply(key, n.value);
            if (r == null) {
                if (root.compareAndSet(oldRoot, deleteNode(pb))) {
                    this.size.decrementAndGet();
                    return null;
                }
            } else {
                pb.setNode(NodePathOffset.CURRENT, n.withValue(r));
                if (root.compareAndSet(oldRoot, copyUntilRoot(pb))) {
                    return r;
                }
            }
            spins = backoff(spins);
        }
    }

    /**
     * @throws NullPointerException if the specified key is null or the
     *                              remappingFunction is null
     * @{inheritDoc}
     */
    @Override
    public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (key == null || remappingFunction == null) {
            throw new NullPointerException();
        }
        int spins = 0;
        while (true) {
            PathBuffer<K, V> pb = getPathBuffer();
            Node<K, V> oldRoot = root.get();
            pb.setRoot(oldRoot);
            Node<K, V> n = findNode(key, pb, comparator);
            if (n == null) {
                V r = remappingFunction.apply(key, null);
                if (r == null) {
                    return null;
                }

                if (putInternal(key, r, true) == null) {
                    return r;
                }
            } else if (n.value != null) {
                V r = remappingFunction.apply(key, n.value);
                if (r == null) {
                    if (root.compareAndSet(oldRoot, deleteNode(pb))) {
                        this.size.decrementAndGet();
                        return null;
                    }
                } else {
                    pb.setNode(NodePathOffset.CURRENT, n.withValue(r));
                    if (root.compareAndSet(oldRoot, copyUntilRoot(pb))) {
                        return r;
                    }
                }
            }
            spins = backoff(spins);
        }
    }

    /**
     * @throws NullPointerException if the specified key or value is null or the
     *                              remappingFunction is null
     * @{inheritDoc}
     */
    @Override
    public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        if (key == null || value == null || remappingFunction == null) {
            throw new NullPointerException();
        }
        int spins = 0;
        while (true) {
            PathBuffer<K, V> pb = getPathBuffer();
            Node<K, V> oldRoot = root.get();
            pb.setRoot(oldRoot);
            Node<K, V> n = findNode(key, pb, comparator);
            if (n == null) {
                // close path buffer since it's reused in `putInternal`
                putInternal(key, value, true);
                return value;
            } else if (n.value != null) {
                V r = remappingFunction.apply(n.value, value);
                if (r == null) {
                    if (root.compareAndSet(oldRoot, deleteNode(pb))) {
                        this.size.decrementAndGet();
                        return null;
                    }
                } else {
                    pb.setNode(NodePathOffset.CURRENT, n.withValue(r));
                    if (root.compareAndSet(oldRoot, copyUntilRoot(pb))) {
                        return r;
                    }
                }
            }
            spins = backoff(spins);
        }
    }

    /* ---------------- View methods -------------- */

    @Override
    public NavigableSet<K> keySet() {
        KeySet<K, V> ks;
        if ((ks = keySet) != null) {
            return ks;
        }
        return keySet = new KeySet<>(this);
    }

    @Override
    public NavigableSet<K> navigableKeySet() {
        KeySet<K, V> ks;
        if ((ks = keySet) != null) {
            return ks;
        }
        return keySet = new KeySet<>(this);
    }

    @Override
    public Collection<V> values() {
        Values<K, V> vs;
        if ((vs = values) != null) {
            return vs;
        }
        return values = new Values<>(this);
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        EntrySet<K, V> es;
        if ((es = entrySet) != null) {
            return es;
        }
        return entrySet = new EntrySet<>(this);
    }

    @Override
    public ConcurrentNavigableMap<K, V> descendingMap() {
        ConcurrentNavigableMap<K, V> dm;
        if ((dm = descendingMap) != null) {
            return dm;
        }
        return descendingMap = new CopyOnWriteTreeMap.SubMap<K, V>(this, null, false, null, false, true);
    }

    @Override
    public NavigableSet<K> descendingKeySet() {
        return descendingMap().navigableKeySet();
    }

    /* ---------------- AbstractMap Overrides -------------- */

    public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (!(o instanceof Map)) {
            return false;
        }
        Map<?, ?> m = (Map<?, ?>) o;
        // TODO: use copies to make safe for concurrent modifications??
        try {
            PathBuffer<K, V> pb = getPathBuffer();
            // acquire roots in both maps creating a snapshot
            pb.setRoot(root.get());
            Iterator<? extends Map.Entry<?, ?>> it = m.entrySet().iterator();

            if (m instanceof SortedMap && ((SortedMap<?, ?>) m).comparator() == comparator) {
                // they have the same comparator meaning we can just iterate in order
                Node<K, V> n = findFirst(pb);
                while (n != null) {
                    if (!it.hasNext()) {
                        return false;
                    }
                    Map.Entry<?, ?> e = it.next();
                    Object mk = e.getKey();
                    Object mv = e.getValue();
                    if (mk == null || mv == null) {
                        return false;
                    }
                    try {
                        if (cpr(comparator, n.key, mk) != 0) {
                            return false;
                        }
                    } catch (ClassCastException cce) {
                        return false;
                    }
                    if (!mv.equals(n.value)) {
                        return false;
                    }
                    n = successor(pb); // goto next
                }
                return !it.hasNext();
            } else {
                // different comparators. Need to check if `this` contains all elements in `m`
                // AND `m` contains all elements in `this`
                while (it.hasNext()) {
                    V v;
                    Map.Entry<?, ?> e = it.next();
                    Object mk = e.getKey();
                    Object mv = e.getValue();
                    if (mk == null || mv == null
                            || (v = get(mk)) == null || !v.equals(mv)) {
                        return false;
                    }
                }

                Node<K, V> n = findFirst(pb);
                while (n != null) {
                    K k;
                    V v;
                    Object mv;
                    if ((v = n.value) != null && (k = n.key) != null
                            && ((mv = m.get(k)) == null || !mv.equals(v))) {
                        return false;
                    }

                    n = successor(pb);
                }
                return true;
            }
        } catch (ClassCastException | NullPointerException unused) {
            return false;
        }
    }

    /* ------ ConcurrentMap API methods ------ */

    /**
     * {@inheritDoc ConcurrentMap}
     *
     * @return the previous value associated with the specified key, or
     *         {@code null} if there was no mapping for the key
     * @throws ClassCastException   if the specified key cannot be compared with
     *                              the keys currently in the map
     * @throws NullPointerException if the specified key or value is null
     */
    public V putIfAbsent(K key, V value) {
        if (value == null) {
            throw new NullPointerException();
        }
        return putInternal(key, value, true);
    }

    /**
     * {@inheritDoc ConcurrentMap}
     *
     * @return {@inheritDoc ConcurrentMap}
     * @throws ClassCastException   if the specified key cannot be compared with
     *                              the keys currently in the map
     * @throws NullPointerException if the specified key is null
     */
    public boolean remove(Object key, Object value) {
        if (key == null) {
            throw new NullPointerException();
        }
        return value != null && doRemove(key, value) != null;
    }

    /**
     * {@inheritDoc ConcurrentMap}
     *
     * @return {@inheritDoc ConcurrentMap}
     * @throws ClassCastException   if the specified key cannot be compared with
     *                              the keys currently in the map
     * @throws NullPointerException if any of the arguments are null
     */
    public boolean replace(K key, V oldValue, V newValue) {
        if (key == null || oldValue == null || newValue == null) {
            throw new NullPointerException();
        }
        int spins = 0;
        while (true) {
            PathBuffer<K, V> pb = getPathBuffer();
            Node<K, V> oldRoot = root.get();
            pb.setRoot(oldRoot);

            Node<K, V> target = findNode(key, pb, comparator);
            if (target == null) {
                return false;
            } else if (target.value != null) {
                if (!oldValue.equals(target.value)) {
                    return false;
                } else {
                    pb.setNode(NodePathOffset.CURRENT, target.withValue(newValue));
                    Node<K, V> newRoot = copyUntilRoot(pb);
                    if (root.compareAndSet(oldRoot, newRoot)) {
                        return true;
                    }
                    spins = backoff(spins);
                }
            }
        }
    }

    /**
     * {@inheritDoc ConcurrentMap}
     *
     * @return the previous value associated with the specified key, or
     *         {@code null} if there was no mapping for the key
     * @throws ClassCastException   if the specified key cannot be compared with
     *                              the keys currently in the map
     * @throws NullPointerException if the specified key or value is null
     */
    public V replace(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException();
        }
        int spins = 0;
        while (true) {
            PathBuffer<K, V> pb = getPathBuffer();
            Node<K, V> oldRoot = root.get();
            pb.setRoot(oldRoot);

            Node<K, V> target = findNode(key, pb, comparator);
            if (target == null) {
                return null;
            }
            if (target.value != null) {
                pb.setNode(NodePathOffset.CURRENT, target.withValue(value));
                Node<K, V> newRoot = copyUntilRoot(pb);
                if (root.compareAndSet(oldRoot, newRoot)) {
                    return target.value;
                }
                spins = backoff(spins);
            }
        }
    }

    /* ------ SortedMap API methods ------ */

    public Comparator<? super K> comparator() {
        return comparator;
    }

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public K firstKey() {
        Node<K, V> n = findFirst();
        if (n == null) {
            throw new NoSuchElementException();
        }
        return n.key;
    }

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public K lastKey() {
        Node<K, V> n = findLast();
        if (n == null) {
            throw new NoSuchElementException();
        }
        return n.key;
    }

    /**
     * Throws {@code UnsupportedOperationException}. The encounter order induced
     * by this map's comparison method determines the position of mappings, so
     * explicit positioning is not supported.
     *
     * @throws UnsupportedOperationException always
     * @since 21
     */
    public V putFirst(K k, V v) {
        throw new UnsupportedOperationException();
    }

    /**
     * Throws {@code UnsupportedOperationException}. The encounter order induced
     * by this map's comparison method determines the position of mappings, so
     * explicit positioning is not supported.
     *
     * @throws UnsupportedOperationException always
     * @since 21
     */
    public V putLast(K k, V v) {
        throw new UnsupportedOperationException();
    }

    /**
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     if {@code fromKey} or {@code toKey} is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public ConcurrentNavigableMap<K, V> subMap(K fromKey,
            boolean fromInclusive,
            K toKey,
            boolean toInclusive) {
        if (fromKey == null || toKey == null) {
            throw new NullPointerException();
        }
        return new SubMap<K, V>(this, fromKey, fromInclusive, toKey, toInclusive, false);
    }

    /**
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     if {@code toKey} is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public ConcurrentNavigableMap<K, V> headMap(K toKey,
            boolean inclusive) {
        if (toKey == null) {
            throw new NullPointerException();
        }
        return new SubMap<K, V>(this, null, false, toKey, inclusive, false);
    }

    /**
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     if {@code fromKey} is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public ConcurrentNavigableMap<K, V> tailMap(K fromKey,
            boolean inclusive) {
        if (fromKey == null) {
            throw new NullPointerException();
        }
        return new SubMap<K, V>(this, fromKey, inclusive, null, false, false);
    }

    /**
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     if {@code fromKey} or {@code toKey} is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey) {
        return subMap(fromKey, true, toKey, false);
    }

    /**
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     if {@code toKey} is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public ConcurrentNavigableMap<K, V> headMap(K toKey) {
        return headMap(toKey, false);
    }

    /**
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     if {@code fromKey} is null
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public ConcurrentNavigableMap<K, V> tailMap(K fromKey) {
        return tailMap(fromKey, true);
    }

    /* ---------------- Relational operations -------------- */

    /**
     * Returns a key-value mapping associated with the greatest key strictly
     * less than the given key, or {@code null} if there is no such key. The
     * returned entry does <em>not</em> support the {@code Entry.setValue}
     * method.
     *
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     */
    public Map.Entry<K, V> lowerEntry(K key) {
        return findNearEntry(key, LT, comparator);
    }

    /**
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     */
    public K lowerKey(K key) {
        Node<K, V> n = findNear(key, LT, comparator);
        return (n == null) ? null : n.key;
    }

    /**
     * Returns a key-value mapping associated with the greatest key less than or
     * equal to the given key, or {@code null} if there is no such key. The
     * returned entry does <em>not</em> support the {@code Entry.setValue}
     * method.
     *
     * @param key the key
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     */
    public Map.Entry<K, V> floorEntry(K key) {
        return findNearEntry(key, LT | EQ, comparator);
    }

    /**
     * @param key the key
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     */
    public K floorKey(K key) {
        Node<K, V> n = findNear(key, LT | EQ, comparator);
        return (n == null) ? null : n.key;
    }

    /**
     * Returns a key-value mapping associated with the least key greater than or
     * equal to the given key, or {@code null} if there is no such entry. The
     * returned entry does <em>not</em>
     * support the {@code Entry.setValue} method.
     *
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     */
    public Map.Entry<K, V> ceilingEntry(K key) {
        return findNearEntry(key, GT | EQ, comparator);
    }

    /**
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     */
    public K ceilingKey(K key) {
        Node<K, V> n = findNear(key, GT | EQ, comparator);
        return (n == null) ? null : n.key;
    }

    /**
     * Returns a key-value mapping associated with the least key strictly
     * greater than the given key, or {@code null} if there is no such key. The
     * returned entry does <em>not</em> support the {@code Entry.setValue}
     * method.
     *
     * @param key the key
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     */
    public Map.Entry<K, V> higherEntry(K key) {
        return findNearEntry(key, GT, comparator);
    }

    /**
     * @param key the key
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     */
    public K higherKey(K key) {
        Node<K, V> n = findNear(key, GT, comparator);
        return (n == null) ? null : n.key;
    }

    /**
     * Returns a key-value mapping associated with the least key in this map, or
     * {@code null} if the map is empty. The returned entry does <em>not</em>
     * support the {@code Entry.setValue} method.
     */
    public Map.Entry<K, V> firstEntry() {
        return findFirstEntry();
    }

    /**
     * Returns a key-value mapping associated with the greatest key in this map,
     * or {@code null} if the map is empty. The returned entry does <em>not</em>
     * support the {@code Entry.setValue} method.
     */
    public Map.Entry<K, V> lastEntry() {
        return findLastEntry();
    }

    /**
     * Removes and returns a key-value mapping associated with the least key in
     * this map, or {@code null} if the map is empty. The returned entry does
     * <em>not</em> support the {@code Entry.setValue} method.
     */
    public Map.Entry<K, V> pollFirstEntry() {
        return doRemoveFirstEntry();
    }

    /**
     * Removes and returns a key-value mapping associated with the greatest key
     * in this map, or {@code null} if the map is empty. The returned entry does
     * <em>not</em> support the {@code Entry.setValue} method.
     */
    public Map.Entry<K, V> pollLastEntry() {
        return doRemoveLastEntry();
    }

    /* ---------------- Iterators -------------- */

    /**
     * Base of iterator classes.
     *
     * <p>
     * Takes in a {@link PathBuffer} and expects the caller to close it.
     * The iterator will start from the current position in the path buffer.
     * </p>
     *
     * <p>
     * A snapshot of the tree when the iterator was created is used.
     * If an element gets removed during the iteration, the change will <em>not</em>
     * be reflected in the current iteration
     * </p>
     */
    abstract class Iter<T> implements Iterator<T> {
        Node<K, V> next;
        Node<K, V> lastReturned;
        PathBuffer<K, V> pb;

        Iter(Node<K, V> root) {
            lastReturned = null;
            this.pb = createPathBuffer();
            this.pb.setRoot(root);
            this.next = findFirst(this.pb);
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        final Node<K, V> nextNode() {
            Node<K, V> n = next;
            if (n == null) {
                throw new NoSuchElementException();
            }
            next = successor(pb);
            lastReturned = n;
            return n;
        }

        final Node<K, V> prevNode() {
            Node<K, V> n = next;
            if (n == null) {
                throw new NoSuchElementException();
            }
            next = predecessor(pb);
            lastReturned = n;
            return n;
        }

        /**
         * Removes the last entry but doesn't show the changes for this current
         * iteration
         */
        public void remove() {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            doRemove(lastReturned.key, null);
            lastReturned = null;
        }
    }

    final class EntryIterator extends Iter<Map.Entry<K, V>> {
        EntryIterator(Node<K, V> root) {
            super(root);
        }

        public Map.Entry<K, V> next() {
            return exportNode(nextNode());
        }
    }

    final class ValueIterator extends Iter<V> {
        ValueIterator(Node<K, V> root) {
            super(root);
        }

        public V next() {
            return nextNode().value;
        }
    }

    final class KeyIterator extends Iter<K> {
        KeyIterator(Node<K, V> root) {
            super(root);
        }

        public K next() {
            return nextNode().key;
        }
    }

    /* ---------------- View Classes -------------- */

    /*
     * View classes are static, delegating to a ConcurrentNavigableMap
     * to allow use by SubMaps, which outweighs the ugliness of
     * needing type-tests for Iterator methods.
     */
    static final <E> List<E> toList(Collection<E> c) {
        ArrayList<E> list = new ArrayList<E>();
        for (E e : c) {
            list.add(e);
        }
        return list;
    }

    static final class KeySet<K, V> extends AbstractSet<K> implements NavigableSet<K> {
        final ConcurrentNavigableMap<K, V> m;

        KeySet(ConcurrentNavigableMap<K, V> map) {
            m = map;
        }

        public int size() {
            return m.size();
        }

        public boolean isEmpty() {
            return m.isEmpty();
        }

        public boolean contains(Object o) {
            return m.containsKey(o);
        }

        public boolean remove(Object o) {
            return m.remove(o) != null;
        }

        public void clear() {
            m.clear();
        }

        public K lower(K e) {
            return m.lowerKey(e);
        }

        public K floor(K e) {
            return m.floorKey(e);
        }

        public K ceiling(K e) {
            return m.ceilingKey(e);
        }

        public K higher(K e) {
            return m.higherKey(e);
        }

        public Comparator<? super K> comparator() {
            return m.comparator();
        }

        public K first() {
            return m.firstKey();
        }

        public K last() {
            return m.lastKey();
        }

        public K pollFirst() {
            Map.Entry<K, V> e = m.pollFirstEntry();
            return (e == null) ? null : e.getKey();
        }

        public K pollLast() {
            Map.Entry<K, V> e = m.pollLastEntry();
            return (e == null) ? null : e.getKey();
        }

        public boolean equals(Object o) {
            if (o == this) {
                return true;
            }
            if (!(o instanceof Set)) {
                return false;
            }
            Collection<?> c = (Collection<?>) o;
            try {
                return containsAll(c) && c.containsAll(this);
            } catch (ClassCastException | NullPointerException unused) {
                return false;
            }
        }

        public Object[] toArray() {
            return toList(this).toArray();
        }

        public <T> T[] toArray(T[] a) {
            return toList(this).toArray(a);
        }

        public Iterator<K> descendingIterator() {
            return descendingSet().iterator();
        }

        public NavigableSet<K> subSet(K fromElement,
                boolean fromInclusive,
                K toElement,
                boolean toInclusive) {
            return new KeySet<>(m.subMap(fromElement, fromInclusive,
                    toElement, toInclusive));
        }

        public NavigableSet<K> headSet(K toElement, boolean inclusive) {
            return new KeySet<>(m.headMap(toElement, inclusive));
        }

        public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
            return new KeySet<>(m.tailMap(fromElement, inclusive));
        }

        public NavigableSet<K> subSet(K fromElement, K toElement) {
            return subSet(fromElement, true, toElement, false);
        }

        public NavigableSet<K> headSet(K toElement) {
            return headSet(toElement, false);
        }

        public NavigableSet<K> tailSet(K fromElement) {
            return tailSet(fromElement, true);
        }

        public NavigableSet<K> descendingSet() {
            return new KeySet<>(m.descendingMap());
        }

        public Iterator<K> iterator() {
            if (m instanceof CopyOnWriteTreeMap) {
                CopyOnWriteTreeMap<K, V> cm = (CopyOnWriteTreeMap<K, V>) m;
                return cm.new KeyIterator(cm.root.get());

            } else {
                SubMap<K, V> sm = (SubMap<K, V>) m;
                return sm.new SubMapKeyIterator(sm.m.root.get());

            }
        }

        public Spliterator<K> spliterator() {
            if (m instanceof CopyOnWriteTreeMap) {
                CopyOnWriteTreeMap<K, V> cm = (CopyOnWriteTreeMap<K, V>) m;
                return cm.keySpliterator();
            } else {
                SubMap<K, V> sm = (SubMap<K, V>) m;
                CopyOnWriteTreeMap<K, V> cm = sm.m;
                if (sm.isDescending) {
                    return cm.descendingKeySpliterator();
                } else {
                    return sm.new SubMapKeyIterator(cm.root.get());
                }
            }
        }
    }

    static final class Values<K, V> extends AbstractCollection<V> {
        final ConcurrentNavigableMap<K, V> m;

        Values(ConcurrentNavigableMap<K, V> map) {
            m = map;
        }

        public int size() {
            return m.size();
        }

        public boolean isEmpty() {
            return m.isEmpty();
        }

        public boolean contains(Object o) {
            return m.containsValue(o);
        }

        public void clear() {
            m.clear();
        }

        public Object[] toArray() {
            return toList(this).toArray();
        }

        public <T> T[] toArray(T[] a) {
            return toList(this).toArray(a);
        }

        public Iterator<V> iterator() {
            if (m instanceof CopyOnWriteTreeMap) {
                CopyOnWriteTreeMap<K, V> cm = (CopyOnWriteTreeMap<K, V>) m;
                return cm.new ValueIterator(cm.root.get());

            } else {
                SubMap<K, V> sm = (SubMap<K, V>) m;
                return sm.new SubMapValueIterator(sm.m.root.get());
            }
        }

        public Spliterator<V> spliterator() {
            if (m instanceof CopyOnWriteTreeMap) {
                return ((CopyOnWriteTreeMap<K, V>) m).valueSpliterator();
            } else {
                SubMap<K, V> sm = ((SubMap<K, V>) m);
                return sm.new SubMapValueIterator(sm.m.root.get());
            }
        }
    }

    // public boolean removeIf(Predicate<? super V> filter) {
    // if (filter == null) {
    // throw new NullPointerException();
    // }
    // if (m instanceof CopyOnWriteTreeMap) {
    // return ((CopyOnWriteTreeMap<K, V>) m).remove
    // }
    // }
    // }

    static final class EntrySet<K, V> extends AbstractSet<Map.Entry<K, V>> {
        final ConcurrentNavigableMap<K, V> m;

        EntrySet(ConcurrentNavigableMap<K, V> map) {
            m = map;
        }

        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
            V v = m.get(e.getKey());
            return v != null && v.equals(e.getValue());
        }

        public boolean remove(Object o) {
            if (!(o instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
            return m.remove(e.getKey(),
                    e.getValue());
        }

        public boolean isEmpty() {
            return m.isEmpty();
        }

        public int size() {
            return m.size();
        }

        public void clear() {
            m.clear();
        }

        public boolean equals(Object o) {
            if (o == this) {
                return true;
            }
            if (!(o instanceof Set)) {
                return false;
            }
            Collection<?> c = (Collection<?>) o;
            try {
                return containsAll(c) && c.containsAll(this);
            } catch (ClassCastException | NullPointerException unused) {
                return false;
            }
        }

        public Object[] toArray() {
            return toList(this).toArray();
        }

        public <T> T[] toArray(T[] a) {
            return toList(this).toArray(a);
        }

        public Iterator<Map.Entry<K, V>> iterator() {
            if (m instanceof CopyOnWriteTreeMap) {
                CopyOnWriteTreeMap<K, V> cm = (CopyOnWriteTreeMap<K, V>) m;
                return cm.new EntryIterator(cm.root.get());
            } else {
                SubMap<K, V> sm = (SubMap<K, V>) m;
                return sm.new SubMapEntryIterator(sm.m.root.get());
            }
        }

        public Spliterator<Map.Entry<K, V>> spliterator() {
            if (m instanceof CopyOnWriteTreeMap) {
                return ((CopyOnWriteTreeMap<K, V>) m).entrySpliterator();
            } else {
                SubMap<K, V> sm = ((SubMap<K, V>) m);
                return sm.new SubMapEntryIterator(sm.m.root.get());
            }
        }
    }

    /* ------------- SubMap 1 ----------- */

    static final class SubMap<K, V> extends AbstractMap<K, V>
            implements ConcurrentNavigableMap<K, V>, Serializable {

        @Serial
        private static final long serialVersionUID = -7980544695998842832L;
        /**
         * @serial underlying map
         */
        final CopyOnWriteTreeMap<K, V> m;
        /**
         * @serial lower bound key, or null if from start
         */
        @SuppressWarnings("serial") // Conditionally serializable
        private final K lo;
        /**
         * @serial upper bound key, or null if to end
         */
        @SuppressWarnings("serial") // Conditionally serializable
        private final K hi;
        /**
         * @serial inclusion flag for lo
         */
        private final boolean loInclusive;
        /**
         * @serial inclusion flag for hi
         */
        private final boolean hiInclusive;
        /**
         * @serial direction
         */
        final boolean isDescending;

        // Lazily initialized view holders
        private transient KeySet<K, V> keySetView;
        private transient Values<K, V> valuesView;
        private transient EntrySet<K, V> entrySetView;

        /**
         * Creates a new submap, initializing all fields.
         */
        SubMap(CopyOnWriteTreeMap<K, V> map, K fromKey, boolean fromInclusive,
                K toKey, boolean toInclusive,
                boolean isDescending) {
            Comparator<? super K> cmp = map.comparator;
            if (fromKey != null && toKey != null
                    && cpr(cmp, fromKey, toKey) > 0) {
                throw new IllegalArgumentException("inconsistent range");
            } else {
                if (fromKey != null) // type check
                    cpr(cmp, fromKey, fromKey);
                if (toKey != null)
                    cpr(cmp, toKey, toKey);
            }
            this.m = map;
            this.lo = fromKey;
            this.hi = toKey;
            this.loInclusive = fromInclusive;
            this.hiInclusive = toInclusive;
            this.isDescending = isDescending;
        }

        /* ---------------- Utilities -------------- */
        boolean tooLow(Object key, Comparator<? super K> cmp) {
            int c;
            return (lo != null && ((c = cpr(cmp, key, lo)) < 0
                    || (c == 0 && !loInclusive)));
        }

        boolean tooHigh(Object key, Comparator<? super K> cmp) {
            int c;
            return (hi != null && ((c = cpr(cmp, key, hi)) > 0
                    || (c == 0 && !hiInclusive)));
        }

        boolean inBounds(Object key, Comparator<? super K> cmp) {
            return !tooLow(key, cmp) && !tooHigh(key, cmp);
        }

        void checkKeyBounds(K key, Comparator<? super K> cmp) {
            if (key == null) {
                throw new NullPointerException();
            }
            if (!inBounds(key, cmp)) {
                throw new IllegalArgumentException("key out of range");
            }
        }

        /**
         * Returns true if node key is less than upper bound of range.
         */
        boolean isBeforeEnd(CopyOnWriteTreeMap.Node<K, V> n,
                Comparator<? super K> cmp) {
            if (n == null) {
                return false;
            }
            if (hi == null) {
                return true;
            }
            K k = n.key;
            if (k == null) // pass by markers and headers
            {
                return true;
            }
            int c = cpr(cmp, k, hi);
            return c < 0 || (c == 0 && hiInclusive);
        }

        /**
         * Returns lowest node. This node might not be in range, so most usages
         * need to check bounds.
         */
        CopyOnWriteTreeMap.Node<K, V> loNode(Comparator<? super K> cmp) {
            if (lo == null) {
                return m.findFirst();
            } else if (loInclusive) {
                return m.findNear(lo, GT | EQ, cmp);
            } else {
                return m.findNear(lo, GT, cmp);
            }
        }

        CopyOnWriteTreeMap.Node<K, V> loNode(PathBuffer<K, V> pb, Comparator<? super K> cmp) {
            if (lo == null) {
                return m.findFirst(pb);
            } else if (loInclusive) {
                return m.findNear(pb, lo, GT | EQ, cmp);
            } else {
                return m.findNear(pb, lo, GT, cmp);
            }
        }

        /**
         * Returns highest node. This node might not be in range, so most usages
         * need to check bounds.
         */
        CopyOnWriteTreeMap.Node<K, V> hiNode(Comparator<? super K> cmp) {
            if (hi == null) {
                return m.findLast();
            } else if (hiInclusive) {
                return m.findNear(hi, LT | EQ, cmp);
            } else {
                return m.findNear(hi, LT, cmp);
            }
        }

        CopyOnWriteTreeMap.Node<K, V> hiNode(PathBuffer<K, V> pb, Comparator<? super K> cmp) {
            if (hi == null) {
                return m.findLast(pb);
            } else if (hiInclusive) {
                return m.findNear(pb, hi, LT | EQ, cmp);
            } else {
                return m.findNear(pb, hi, LT, cmp);
            }
        }

        /**
         * Returns lowest absolute key (ignoring directionality).
         */
        K lowestKey() {
            Comparator<? super K> cmp = m.comparator;
            CopyOnWriteTreeMap.Node<K, V> n = loNode(cmp);
            if (isBeforeEnd(n, cmp)) {
                return n.key;
            } else {
                throw new NoSuchElementException();
            }
        }

        /**
         * Returns highest absolute key (ignoring directionality).
         */
        K highestKey() {
            Comparator<? super K> cmp = m.comparator;
            CopyOnWriteTreeMap.Node<K, V> n = hiNode(cmp);
            if (n != null) {
                K last = n.key;
                if (inBounds(last, cmp)) {
                    return last;
                }
            }
            throw new NoSuchElementException();
        }

        Map.Entry<K, V> lowestEntry() {
            Comparator<? super K> cmp = m.comparator;
            for (;;) {
                CopyOnWriteTreeMap.Node<K, V> n;
                V v;
                if ((n = loNode(cmp)) == null || !isBeforeEnd(n, cmp)) {
                    return null;
                } else if ((v = n.value) != null) {
                    return new AbstractMap.SimpleImmutableEntry<K, V>(n.key, v);
                }
            }
        }

        Map.Entry<K, V> highestEntry() {
            Comparator<? super K> cmp = m.comparator;
            for (;;) {
                CopyOnWriteTreeMap.Node<K, V> n;
                V v;
                if ((n = hiNode(cmp)) == null || !inBounds(n.key, cmp)) {
                    return null;
                } else if ((v = n.value) != null) {
                    return new AbstractMap.SimpleImmutableEntry<K, V>(n.key, v);
                }
            }
        }

        Map.Entry<K, V> removeLowest() {
            Comparator<? super K> cmp = m.comparator;
            for (;;) {
                CopyOnWriteTreeMap.Node<K, V> n;
                K k;
                V v;
                if ((n = loNode(cmp)) == null) {
                    return null;
                } else if (!inBounds((k = n.key), cmp)) {
                    return null;
                } else if ((v = m.doRemove(k, null)) != null) {
                    return new AbstractMap.SimpleImmutableEntry<K, V>(k, v);
                }
            }
        }

        Map.Entry<K, V> removeHighest() {
            Comparator<? super K> cmp = m.comparator;
            for (;;) {
                CopyOnWriteTreeMap.Node<K, V> n;
                K k;
                V v;
                if ((n = hiNode(cmp)) == null) {
                    return null;
                } else if (!inBounds((k = n.key), cmp)) {
                    return null;
                } else if ((v = m.doRemove(k, null)) != null) {
                    return new AbstractMap.SimpleImmutableEntry<K, V>(k, v);
                }
            }
        }

        /**
         * Submap version of CopyOnWriteTreeMap.findNearEntry.
         */
        Map.Entry<K, V> getNearEntry(K key, int rel) {
            Comparator<? super K> cmp = m.comparator;
            if (isDescending) { // adjust relation for direction
                if ((rel & LT) == 0) {
                    rel |= LT;
                } else {
                    rel &= ~LT;
                }
            }
            if (tooLow(key, cmp)) {
                return ((rel & LT) != 0) ? null : lowestEntry();
            }
            if (tooHigh(key, cmp)) {
                return ((rel & LT) != 0) ? highestEntry() : null;
            }
            AbstractMap.SimpleImmutableEntry<K, V> e = m.findNearEntry(key, rel, cmp);
            if (e == null || !inBounds(e.getKey(), cmp)) {
                return null;
            } else {
                return e;
            }
        }

        // Almost the same as getNearEntry, except for keys
        K getNearKey(K key, int rel) {
            Comparator<? super K> cmp = m.comparator;
            if (isDescending) { // adjust relation for direction
                if ((rel & LT) == 0) {
                    rel |= LT;
                } else {
                    rel &= ~LT;
                }
            }
            if (tooLow(key, cmp)) {
                if ((rel & LT) == 0) {
                    CopyOnWriteTreeMap.Node<K, V> n = loNode(cmp);
                    if (isBeforeEnd(n, cmp)) {
                        return n.key;
                    }
                }
                return null;
            }
            if (tooHigh(key, cmp)) {
                if ((rel & LT) != 0) {
                    CopyOnWriteTreeMap.Node<K, V> n = hiNode(cmp);
                    if (n != null) {
                        K last = n.key;
                        if (inBounds(last, cmp)) {
                            return last;
                        }
                    }
                }
                return null;
            }

            Node<K, V> n = m.findNear(key, rel, cmp);
            if (n == null || !inBounds(n.key, cmp)) {
                return null;
            }
            return n.key;
        }

        /* ---------------- Map API methods -------------- */
        public boolean containsKey(Object key) {
            if (key == null) {
                throw new NullPointerException();
            }
            return inBounds(key, m.comparator) && m.containsKey(key);
        }

        public V get(Object key) {
            if (key == null) {
                throw new NullPointerException();
            }
            return (!inBounds(key, m.comparator)) ? null : m.get(key);
        }

        public V put(K key, V value) {
            checkKeyBounds(key, m.comparator);
            return m.put(key, value);
        }

        public V remove(Object key) {
            return (!inBounds(key, m.comparator)) ? null : m.remove(key);
        }

        public int size() {
            int count = 0;
            PathBuffer<K, V> pb = getPathBuffer();
            pb.setRoot(m.root.get());

            for (Node<K, V> n = loNode(pb, m.comparator); isBeforeEnd(n, m.comparator); n = successor(pb)) {
                ++count;
            }
            return count;
        }

        public boolean isEmpty() {
            Comparator<? super K> cmp = m.comparator;
            return !isBeforeEnd(loNode(cmp), cmp);
        }

        public boolean containsValue(Object value) {
            if (value == null) {
                throw new NullPointerException();
            }

            PathBuffer<K, V> pb = getPathBuffer();
            pb.setRoot(m.root.get());
            for (Node<K, V> n = loNode(pb, m.comparator); isBeforeEnd(n, m.comparator); n = successor(pb)) {
                if (n.value.equals(value)) {
                    return true;
                }
            }
            return false;
        }

        public void clear() {
            PathBuffer<K, V> pb = createPathBuffer();
            pb.setRoot(m.root.get());
            for (Node<K, V> n = loNode(pb, m.comparator); isBeforeEnd(n, m.comparator); n = successor(pb)) {
                m.remove(n.key);
            }
        }

        /* ---------------- ConcurrentMap API methods -------------- */
        public V putIfAbsent(K key, V value) {
            checkKeyBounds(key, m.comparator);
            return m.putIfAbsent(key, value);
        }

        public boolean remove(Object key, Object value) {
            return inBounds(key, m.comparator) && m.remove(key, value);
        }

        public boolean replace(K key, V oldValue, V newValue) {
            checkKeyBounds(key, m.comparator);
            return m.replace(key, oldValue, newValue);
        }

        public V replace(K key, V value) {
            checkKeyBounds(key, m.comparator);
            return m.replace(key, value);
        }

        /* ---------------- SortedMap API methods -------------- */
        public Comparator<? super K> comparator() {
            Comparator<? super K> cmp = m.comparator();
            if (isDescending) {
                return Collections.reverseOrder(cmp);
            } else {
                return cmp;
            }
        }

        /**
         * Utility to create submaps, where given bounds override
         * unbounded(null) ones and/or are checked against bounded ones.
         */
        SubMap<K, V> newSubMap(K fromKey, boolean fromInclusive,
                K toKey, boolean toInclusive) {
            Comparator<? super K> cmp = m.comparator;
            if (isDescending) { // flip senses
                K tk = fromKey;
                fromKey = toKey;
                toKey = tk;
                boolean ti = fromInclusive;
                fromInclusive = toInclusive;
                toInclusive = ti;
            }
            if (lo != null) {
                if (fromKey == null) {
                    fromKey = lo;
                    fromInclusive = loInclusive;
                } else {
                    int c = cpr(cmp, fromKey, lo);
                    if (c < 0 || (c == 0 && !loInclusive && fromInclusive)) {
                        throw new IllegalArgumentException("key out of range");
                    }
                }
            }
            if (hi != null) {
                if (toKey == null) {
                    toKey = hi;
                    toInclusive = hiInclusive;
                } else {
                    int c = cpr(cmp, toKey, hi);
                    if (c > 0 || (c == 0 && !hiInclusive && toInclusive)) {
                        throw new IllegalArgumentException("key out of range");
                    }
                }
            }
            return new SubMap<K, V>(m, fromKey, fromInclusive,
                    toKey, toInclusive, isDescending);
        }

        public SubMap<K, V> subMap(K fromKey, boolean fromInclusive,
                K toKey, boolean toInclusive) {
            if (fromKey == null || toKey == null) {
                throw new NullPointerException();
            }
            return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
        }

        public SubMap<K, V> headMap(K toKey, boolean inclusive) {
            if (toKey == null) {
                throw new NullPointerException();
            }
            return newSubMap(null, false, toKey, inclusive);
        }

        public SubMap<K, V> tailMap(K fromKey, boolean inclusive) {
            if (fromKey == null) {
                throw new NullPointerException();
            }
            return newSubMap(fromKey, inclusive, null, false);
        }

        public SubMap<K, V> subMap(K fromKey, K toKey) {
            return subMap(fromKey, true, toKey, false);
        }

        public SubMap<K, V> headMap(K toKey) {
            return headMap(toKey, false);
        }

        public SubMap<K, V> tailMap(K fromKey) {
            return tailMap(fromKey, true);
        }

        public SubMap<K, V> descendingMap() {
            return new SubMap<K, V>(m, lo, loInclusive,
                    hi, hiInclusive, !isDescending);
        }

        /* ---------------- Relational methods -------------- */
        public Map.Entry<K, V> ceilingEntry(K key) {
            return getNearEntry(key, GT | EQ);
        }

        public K ceilingKey(K key) {
            return getNearKey(key, GT | EQ);
        }

        public Map.Entry<K, V> lowerEntry(K key) {
            return getNearEntry(key, LT);
        }

        public K lowerKey(K key) {
            return getNearKey(key, LT);
        }

        public Map.Entry<K, V> floorEntry(K key) {
            return getNearEntry(key, LT | EQ);
        }

        public K floorKey(K key) {
            return getNearKey(key, LT | EQ);
        }

        public Map.Entry<K, V> higherEntry(K key) {
            return getNearEntry(key, GT);
        }

        public K higherKey(K key) {
            return getNearKey(key, GT);
        }

        public K firstKey() {
            return isDescending ? highestKey() : lowestKey();
        }

        public K lastKey() {
            return isDescending ? lowestKey() : highestKey();
        }

        public Map.Entry<K, V> firstEntry() {
            return isDescending ? highestEntry() : lowestEntry();
        }

        public Map.Entry<K, V> lastEntry() {
            return isDescending ? lowestEntry() : highestEntry();
        }

        public Map.Entry<K, V> pollFirstEntry() {
            return isDescending ? removeHighest() : removeLowest();
        }

        public Map.Entry<K, V> pollLastEntry() {
            return isDescending ? removeLowest() : removeHighest();
        }

        /* ---------------- Submap Views -------------- */
        public NavigableSet<K> keySet() {
            KeySet<K, V> ks;
            if ((ks = keySetView) != null) {
                return ks;
            }
            return keySetView = new KeySet<>(this);
        }

        public NavigableSet<K> navigableKeySet() {
            KeySet<K, V> ks;
            if ((ks = keySetView) != null) {
                return ks;
            }
            return keySetView = new KeySet<>(this);
        }

        public Collection<V> values() {
            Values<K, V> vs;
            if ((vs = valuesView) != null) {
                return vs;
            }
            return valuesView = new Values<>(this);
        }

        public Set<Map.Entry<K, V>> entrySet() {
            EntrySet<K, V> es;
            if ((es = entrySetView) != null) {
                return es;
            }
            return entrySetView = new EntrySet<K, V>(this);
        }

        public NavigableSet<K> descendingKeySet() {
            return descendingMap().navigableKeySet();
        }

        abstract class SubMapIter<T> implements Iterator<T>, Spliterator<T> {
            Node<K, V> next;
            Node<K, V> lastReturned;
            PathBuffer<K, V> pb;

            SubMapIter(Node<K, V> root) {
                this.pb = createPathBuffer();
                this.pb.setRoot(root);
                this.lastReturned = null;

                next = isDescending ? hiNode(pb, m.comparator) : loNode(pb, m.comparator);
                if (next == null)
                    return;

                if (!inBounds(next.key, m.comparator)) {
                    next = null;
                }
            }

            @Override
            public boolean hasNext() {
                return next != null;
            }

            final void advance() {
                if (next == null) {
                    throw new NoSuchElementException();
                }
                lastReturned = next;
                if (isDescending) {
                    prevNode();
                } else {
                    nextNode();
                }
            }

            private void nextNode() {
                next = successor(pb);
                if (next == null) {
                    return;
                }
                if (tooHigh(next.key, m.comparator)) {
                    next = null;
                }
            }

            private void prevNode() {
                next = predecessor(pb);
                if (next == null) {
                    return;
                }
                if (tooLow(next.key, m.comparator)) {
                    next = null;
                }
            }

            public void remove() {
                Node<K, V> l = lastReturned;
                if (l == null) {
                    throw new IllegalStateException();
                }

                m.remove(l.key);
                lastReturned = null;
            }

            public Spliterator<T> trySplit() {
                return null;
            }

            public boolean tryAdvance(Consumer<? super T> action) {
                if (hasNext()) {
                    action.accept(next());
                    return true;
                }
                return false;
            }

            public void forEachRemaining(Consumer<? super T> action) {
                while (hasNext()) {
                    action.accept(next());
                }
            }

            public long estimateSize() {
                return Long.MAX_VALUE;
            }
        }

        final class SubMapValueIterator extends SubMapIter<V> {
            SubMapValueIterator(Node<K, V> root) {
                super(root);
            }

            public V next() {
                Node<K, V> n = next;
                advance();
                return n.value;
            }

            public int characteristics() {
                return 0;
            }
        }

        final class SubMapKeyIterator extends SubMapIter<K> {

            SubMapKeyIterator(Node<K, V> root) {
                super(root);
            }

            public K next() {
                Node<K, V> n = next;
                advance();
                return n.key;
            }

            public int characteristics() {
                return Spliterator.DISTINCT | Spliterator.ORDERED
                        | Spliterator.SORTED;
            }

            public final Comparator<? super K> getComparator() {
                return SubMap.this.comparator();
            }
        }

        final class SubMapEntryIterator extends SubMapIter<Map.Entry<K, V>> {

            SubMapEntryIterator(Node<K, V> node) {
                super(node);
            }

            public Map.Entry<K, V> next() {
                Node<K, V> n = next;
                advance();
                return new AbstractMap.SimpleImmutableEntry<K, V>(n.key, n.value);
            }

            public int characteristics() {
                return Spliterator.DISTINCT;
            }
        }

    }

    /* ---------------- Default Map Overrides -------------- */

    public void forEach(BiConsumer<? super K, ? super V> action) {
        PathBuffer<K, V> pb = createPathBuffer();
        pb.setRoot(root.get());
        Node<K, V> n = findFirst(pb);
        while (n != null) {
            action.accept(n.key, n.value);
            n = successor(pb);
        }
    }

    /**
     * {@inheritDoc}
     *
     * @throws NullPointerException if {@code function} returns a {@code null} value
     */
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        int spins = 0;
        while (true) {
            // copies all nodes internally
            Node<K, V> oldRoot = root.get();
            Node<K, V> newRoot = oldRoot.copy();

            Queue<Node<K, V>> queue = new LinkedList<>();
            queue.offer(newRoot);

            Node<K, V> node, tmp;
            while (!queue.isEmpty()) {
                node = queue.poll();
                node.value = function.apply(node.key, node.value);
                if (node.value == null) {
                    throw new NullPointerException();
                }
                if (node.left != null) {
                    tmp = node.left.copy();
                    node.left = tmp;
                    queue.offer(tmp);
                }
                if (node.right != null) {
                    tmp = node.right.copy();
                    node.right = tmp;
                    queue.offer(tmp);
                }
            }

            if (root.compareAndSet(oldRoot, newRoot)) {
                return;
            }
            spins = backoff(spins);
        }
    }

    /* ---------------- Spliterator -------------- */

    abstract static class COWTreeMapSpliterator<K, V> {
        final Node<K, V> currentRoot;
        final Comparator<? super K> comparator;
        Node<K, V> fence; // exclusive upper bound for keys, or null if to end
        Node<K, V> current;
        int est; // size estimate. Only exact for top-level
        int side; // 0: top, -1: is a left split, +1: right
        PathBuffer<K, V> pb;

        COWTreeMapSpliterator(Node<K, V> root, Comparator<? super K> comparator, Node<K, V> origin, Node<K, V> fence,
                int side,
                int est, boolean isDescending) {

            this.currentRoot = root;
            this.comparator = comparator;
            this.fence = fence;
            this.side = side;
            this.est = est;

            pb = createPathBuffer();
            pb.setRoot(this.currentRoot);

            this.current = origin == null
                    ? (isDescending ? findLast(pb) : findFirst(pb))
                    : findNode(origin.key, pb, comparator);
        }

        public final long estimateSize() { // force initialization
            return (long) est;
        }
    }

    static final class KeySpliterator<K, V> extends COWTreeMapSpliterator<K, V>
            implements Spliterator<K> {
        KeySpliterator(Node<K, V> root, Comparator<? super K> comparator, Node<K, V> origin, Node<K, V> fence, int side,
                int est) {
            super(root, comparator, origin, fence, side, est, false);
        }

        public Spliterator<K> trySplit() {
            int d = side;
            Node<K, V> e = current, f = fence,
                    s = ((e == null || keyEquals(e, f)) ? null
                            : // empty
                            (d == 0) ? currentRoot
                                    : (d > 0) ? e.right
                                            : // was right
                                            (d < 0 && f != null) ? f.left
                                                    : // was left
                                                    null);

            if (s != null && !keyEquals(s, e) && !keyEquals(s, f) && cpr(comparator, e.key, s.key) < 0) {
                // e is not already pas s
                side = 1;
                est >>>= 1; // halve estimate
                pb.setPointer(0);
                current = findNode(s.key, pb, comparator);
                return new KeySpliterator<>(currentRoot, comparator, e, s, -1, est);
            }
            return null;
        }

        public void forEachRemaining(Consumer<? super K> action) {
            if (action == null) {
                throw new NullPointerException();
            }

            Node<K, V> f = fence, e, p, pl;
            if ((e = current) != null && !keyEquals(e, f)) {
                current = f; // exhaust
                do {
                    action.accept(e.key);
                    if ((p = e.right) != null) {
                        pb.addFrom(e, RIGHT);
                        while ((pl = p.left) != null) {
                            pb.addFrom(p, LEFT);
                            p = pl;
                        }
                    } else {
                        while (pb.getNode(NodePathOffset.PARENT) != null
                                && pb.getBranch(NodePathOffset.CURRENT) == RIGHT) {
                            pb.gotoNode(NodePathOffset.PARENT);
                        }
                        e = pb.getNode(NodePathOffset.CURRENT);
                        pb.gotoNode(NodePathOffset.PARENT);
                    }

                } while ((e = pb.getNode(NodePathOffset.CURRENT)) != null && !keyEquals(e, f));
            }
        }

        public boolean tryAdvance(Consumer<? super K> action) {
            if (action == null) {
                throw new NullPointerException();
            }

            Node<K, V> e;
            if ((e = current) == null || keyEquals(e, fence)) {
                return false;
            }
            current = successor(this.pb);
            action.accept(e.key);
            return true;
        }

        public int characteristics() {
            return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.DISTINCT | Spliterator.SORTED
                    | Spliterator.IMMUTABLE
                    | Spliterator.ORDERED | Spliterator.NONNULL;
        }

        public Comparator<? super K> getComparator() {
            return comparator;
        }
    }

    final KeySpliterator<K, V> keySpliterator() {
        return new KeySpliterator<>(root.get(), comparator, null, null, 0, size.get());
    }

    static final class DescendingKeySpliterator<K, V> extends COWTreeMapSpliterator<K, V>
            implements Spliterator<K> {
        DescendingKeySpliterator(Node<K, V> root, Comparator<? super K> comparator, Node<K, V> origin, Node<K, V> fence,
                int side,
                int est) {
            super(root, comparator, origin, fence, side, est, true);
        }

        public Spliterator<K> trySplit() {
            int d = side;
            Node<K, V> e = current, f = fence,
                    s = ((e == null || keyEquals(e, f)) ? null
                            : // empty
                            (d == 0) ? currentRoot
                                    : (d < 0) ? e.left
                                            : // was left
                                            (d > 0 && f != null) ? f.right
                                                    : // was right
                                                    null);

            if (s != null && !keyEquals(s, e) && !keyEquals(s, f) && cpr(comparator, e.key, s.key) > 0) {
                // e is not already pas s
                side = 1;
                est >>>= 1; // halve estimate
                pb.setPointer(0);
                current = findNode(s.key, pb, comparator);
                return new DescendingKeySpliterator<>(currentRoot, comparator, e, s, -1, est);
            }
            return null;
        }

        public void forEachRemaining(Consumer<? super K> action) {
            if (action == null) {
                throw new NullPointerException();
            }

            Node<K, V> f = fence, e, p, pl;
            if ((e = current) != null && !keyEquals(e, f)) {
                current = f; // exhaust
                do {
                    action.accept(e.key);
                    if ((p = e.left) != null) {
                        pb.addFrom(e, LEFT);
                        while ((pl = p.right) != null) {
                            pb.addFrom(p, RIGHT);
                            p = pl;
                        }
                    } else {
                        while (pb.getNode(NodePathOffset.PARENT) != null
                                && pb.getBranch(NodePathOffset.CURRENT) == LEFT) {
                            pb.gotoNode(NodePathOffset.PARENT);
                        }
                        e = pb.getNode(NodePathOffset.CURRENT);
                        pb.gotoNode(NodePathOffset.PARENT);
                    }
                } while ((e = pb.getNode(NodePathOffset.CURRENT)) != null && !keyEquals(e, f));
            }
        }

        public boolean tryAdvance(Consumer<? super K> action) {
            if (action == null) {
                throw new NullPointerException();
            }

            Node<K, V> e;
            if ((e = current) == null || keyEquals(e, fence)) {
                return false;
            }
            current = predecessor(this.pb);
            action.accept(e.key);
            return true;
        }

        public int characteristics() {
            return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.DISTINCT | Spliterator.IMMUTABLE
                    | Spliterator.ORDERED | Spliterator.NONNULL;
        }

        public Comparator<? super K> getComparator() {
            return comparator;
        }
    }

    final DescendingKeySpliterator<K, V> descendingKeySpliterator() {
        return new DescendingKeySpliterator<>(root.get(), comparator, null, null, 0, size.get());
    }

    static final class ValueSpliterator<K, V> extends COWTreeMapSpliterator<K, V> implements Spliterator<V> {
        ValueSpliterator(Node<K, V> root, Comparator<? super K> comparator, Node<K, V> origin, Node<K, V> fence,
                int side,
                int est) {
            super(root, comparator, origin, fence, side, est, false);
        }

        public Spliterator<V> trySplit() {
            int d = side;
            Node<K, V> e = current, f = fence,
                    s = ((e == null || keyEquals(e, f)) ? null
                            : // empty
                            (d == 0) ? currentRoot
                                    : (d > 0) ? e.right
                                            : // was right
                                            (d < 0 && f != null) ? f.left
                                                    : // was left
                                                    null);

            if (s != null && !keyEquals(s, e) && !keyEquals(s, f) && cpr(comparator, e.key, s.key) < 0) {
                // e is not already pas s
                side = 1;
                est >>>= 1; // halve estimate
                pb.setPointer(0);
                current = findNode(s.key, pb, comparator);
                return new ValueSpliterator<>(currentRoot, comparator, e, s, -1, est);
            }
            return null;
        }

        public void forEachRemaining(Consumer<? super V> action) {
            if (action == null) {
                throw new NullPointerException();
            }

            Node<K, V> f = fence, e, p, pl;
            if ((e = current) != null && !keyEquals(e, f)) {
                current = f; // exhaust
                do {
                    action.accept(e.value);
                    if ((p = e.right) != null) {
                        pb.addFrom(e, RIGHT);
                        while ((pl = p.left) != null) {
                            pb.addFrom(p, LEFT);
                            p = pl;
                        }
                    } else {
                        while (pb.getNode(NodePathOffset.PARENT) != null
                                && pb.getBranch(NodePathOffset.CURRENT) == RIGHT) {
                            pb.gotoNode(NodePathOffset.PARENT);
                        }
                        e = pb.getNode(NodePathOffset.CURRENT);
                        pb.gotoNode(NodePathOffset.PARENT);
                    }

                } while ((e = pb.getNode(NodePathOffset.CURRENT)) != null && !keyEquals(e, f));
            }
        }

        public boolean tryAdvance(Consumer<? super V> action) {
            if (action == null) {
                throw new NullPointerException();
            }

            Node<K, V> e;
            if ((e = current) == null || keyEquals(e, fence)) {
                return false;
            }
            current = successor(this.pb);
            action.accept(e.value);
            return true;
        }

        public int characteristics() {
            return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.IMMUTABLE
                    | Spliterator.ORDERED | Spliterator.NONNULL;
        }
    }

    final ValueSpliterator<K, V> valueSpliterator() {
        return new ValueSpliterator<>(root.get(), comparator, null, null, 0, size.get());
    }

    static final class EntrySpliterator<K, V> extends COWTreeMapSpliterator<K, V>
            implements Spliterator<Map.Entry<K, V>> {
        EntrySpliterator(Node<K, V> root, Comparator<? super K> comparator, Node<K, V> origin, Node<K, V> fence,
                int side,
                int est) {
            super(root, comparator, origin, fence, side, est, false);
        }

        public Spliterator<Map.Entry<K, V>> trySplit() {
            int d = side;
            Node<K, V> e = current, f = fence,
                    s = ((e == null || keyEquals(e, f)) ? null
                            : // empty
                            (d == 0) ? currentRoot
                                    : (d > 0) ? e.right
                                            : // was right
                                            (d < 0 && f != null) ? f.left
                                                    : // was left
                                                    null);

            if (s != null && !keyEquals(s, e) && !keyEquals(s, f) && cpr(comparator, e.key, s.key) < 0) {
                // e is not already pas s
                side = 1;
                est >>>= 1; // halve estimate
                pb.setPointer(0);
                current = findNode(s.key, pb, comparator);
                return new EntrySpliterator<>(currentRoot, comparator, e, s, -1, est);
            }
            return null;
        }

        public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
            if (action == null) {
                throw new NullPointerException();
            }

            Node<K, V> f = fence, e, p, pl;
            if ((e = current) != null && !keyEquals(e, f)) {
                current = f; // exhaust
                do {
                    action.accept(new AbstractMap.SimpleImmutableEntry<>(e.key, e.value));
                    if ((p = e.right) != null) {
                        pb.addFrom(e, RIGHT);
                        while ((pl = p.left) != null) {
                            pb.addFrom(p, LEFT);
                            p = pl;
                        }
                    } else {
                        while (pb.getNode(NodePathOffset.PARENT) != null
                                && pb.getBranch(NodePathOffset.CURRENT) == RIGHT) {
                            pb.gotoNode(NodePathOffset.PARENT);
                        }
                        e = pb.getNode(NodePathOffset.CURRENT);
                        pb.gotoNode(NodePathOffset.PARENT);
                    }

                } while ((e = pb.getNode(NodePathOffset.CURRENT)) != null && !keyEquals(e, f));
            }
        }

        public boolean tryAdvance(Consumer<? super Map.Entry<K, V>> action) {
            if (action == null) {
                throw new NullPointerException();
            }

            Node<K, V> e;
            if ((e = current) == null || keyEquals(e, fence)) {
                return false;
            }
            current = successor(this.pb);
            action.accept(new AbstractMap.SimpleImmutableEntry<>(e.key, e.value));
            return true;
        }

        public int characteristics() {
            return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.DISTINCT | Spliterator.SORTED
                    | Spliterator.IMMUTABLE
                    | Spliterator.ORDERED | Spliterator.NONNULL;
        }

        @Override
        public Comparator<Map.Entry<K, V>> getComparator() {
            // Adapt or create a key-based comparator
            if (comparator != null) {
                return Map.Entry.comparingByKey(comparator);
            } else {
                return (Comparator<Map.Entry<K, V>> & Serializable) (e1, e2) -> {
                    @SuppressWarnings("unchecked")
                    Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
                    return k1.compareTo(e2.getKey());
                };
            }
        }
    }

    final EntrySpliterator<K, V> entrySpliterator() {
        return new EntrySpliterator<>(root.get(), comparator, null, null, 0, size.get());
    }

    /* ---------------- RB-Specific utilities -------------- */

    public boolean validate() {
        Node<K, V> n = root.get();
        if (n == null) {
            return true;
        } else if (colorOf(n) != BLACK) {
            // root must be black
            return false;
        }

        return validate_helper(n) != -1;
    }

    private int validate_helper(Node<K, V> n) {
        if (n == null) {
            return 1;
        }

        if (colorOf(n) == RED && (colorOf(n.left) == RED || colorOf(n.right) == RED)) {
            // red node can't have red children
            return -1;
        }

        int lbh = validate_helper(n.left);
        int rbh = validate_helper(n.right);
        if (lbh == -1 || rbh == -1) {
            return -1;
        }
        if (lbh != rbh) {
            return -1;
        }

        return lbh + (colorOf(n) == BLACK ? 1 : 0);

    }

    public String stringFrom(Node<K, V> start) {

        // 1. Collect all nodes level by level (BFS), including nulls for gaps
        List<Node<K, V>> currentLevel = new ArrayList<>();
        currentLevel.add(start);

        List<List<Node<K, V>>> levels = new ArrayList<>();

        while (true) {
            levels.add(currentLevel);

            List<Node<K, V>> nextLevel = new ArrayList<>();
            boolean hasNonNull = false;

            for (Node<K, V> node : currentLevel) {
                if (node != null) {
                    nextLevel.add(node.left);
                    nextLevel.add(node.right);
                    if (node.left != null || node.right != null)
                        hasNonNull = true;
                } else {
                    nextLevel.add(null);
                    nextLevel.add(null);
                }
            }

            if (!hasNonNull)
                break;
            currentLevel = nextLevel;
        }

        // 2. Render each level with spacing proportional to tree height
        int height = levels.size();
        int maxWidth = (1 << height) - 1; // 2^height - 1 slots

        StringBuilder sb = new StringBuilder();

        for (int depth = 0; depth < height; depth++) {
            List<Node<K, V>> level = levels.get(depth);
            int slots = 1 << depth; // nodes in a full level at this depth
            int cellWidth = maxWidth / slots; // characters per cell

            // --- Node<K, V> row ---
            StringBuilder nodeRow = new StringBuilder();
            for (Node<K, V> node : level) {
                String label = (node != null) ? String.valueOf(node.key) : " ";
                nodeRow.append(centerPad(label, cellWidth + 1, colorOf(node) == RED));
            }
            sb.append(nodeRow.toString().stripTrailing()).append("\n");

            // --- Connector row (skip for last level) ---
            if (depth < height - 1) {
                StringBuilder connRow = new StringBuilder();
                int halfCell = cellWidth / 2;

                for (Node<K, V> node : level) {
                    boolean hasLeft = node != null && node.left != null;
                    boolean hasRight = node != null && node.right != null;

                    // Left branch: spaces then '/'
                    String leftPart = hasLeft ? " ".repeat(halfCell - 1) + "/" : " ".repeat(halfCell);
                    // Right branch: '\' then spaces
                    String rightPart = hasRight ? "\\" + " ".repeat(halfCell - 1) : " ".repeat(halfCell);

                    connRow.append(leftPart).append(" ").append(rightPart).append(" ");
                }
                sb.append(connRow.toString().stripTrailing()).append("\n");
            }
        }

        return sb.toString();
    }

    public String stringFromKey(K key) {
        Node<K, V> n = findNode(key);
        return stringFrom(n);
    }

    public String prettyToString() {
        if (root == null)
            return "(empty tree)";
        return stringFrom(root.get());
    }

    /**
     * Centers a string inside a field of `width` characters, padding with spaces.
     */
    private static String centerPad(String s, int width, boolean isRed) {
        if (s.length() >= width)
            return s;
        int total = width - s.length();
        int left = total / 2;
        int right = total - left;
        if (isRed)
            s = "\u001B[31m" + s + "\u001B[0m";
        return " ".repeat(left) + s + " ".repeat(right);
    }
}