/**
     * returns a new list, that is "this" minus the deleted item.
     * @param element the element to delete
     * @return the modified version
     */
    public PersistentRedBlackTreeSet<D> delete(D element){
        RedBlackNode<D> current = newRoot = root.clone();
        //RedBlackNode<D> current = newRoot = root.deepClone();
        LinkedList<RedBlackNode<D>> parents = new LinkedList<RedBlackNode<D>>();
        parents.add(null);//root represented by null


        //find the node where the element should go at the bottom of the tree
        while (current.element != null) {
            parents.add(current);

            int dir = comparator.compare(element, current.element);
            if (dir < 0) {
                current = current.left = current.left.clone();
            } else if(dir > 0){
                current = current.right= current.right.clone();
            }else{

                parents.removeLast();
                delete(parents, current);
                PersistentRedBlackTreeSet<D> tree = new PersistentRedBlackTreeSet<D>(comparator, newRoot, size-1, hashcode ^ element.hashCode(), longHashcode - element.hashCode());
                newRoot = null;
                return tree;
            }
        }
        newRoot = null;
        //no change
        return this;
    }

    private void delete(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {

        assert n.parent(parents) == null || n.parent(parents).left == n || n.parent(parents).right == n;

        //if the node has two children, we swap it with the next leaf
        if(n.left.element != null && n.right.element != null){
            parents.addLast(n);
            n.left = n.left.clone();
            RedBlackNode<D> current = n.right = n.right.clone();
            while(current.element != null){
                parents.addLast(current);
                current = current.left = current.left.clone();
            }

            n.element = current.parent(parents).element;

            RedBlackNode<D> currentParent = current.parent(parents);
            parents.removeLast();
            delete_one_child(parents, currentParent);
        }else{
            delete_one_child(parents, n);
        }
    }

    private void delete_one_child(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
        /* Precondition: n has at most one non-null child */
        RedBlackNode<D> child;
        if(n.right.element == null){
            child = n.left = n.left.clone();
        }else{
            assert n.left.element == null;
            child = n.right = n.right.clone();
        }

        replace_node(n, n.parent(parents), child);
        if (n.black) {
            if (!child.black)
                child.black = BLACK;
            else
                delete_case1(parents, child);
        }
    }


    private void delete_case1(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
        if (n.parent(parents) == null)
        {
            newRoot = n;
        }else{
            delete_case2(parents, n);
        }
    }

    private void delete_case2(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
        if (!n.sibling(parents).black) {
            n.cloneSibling(parents);
            n.parent(parents).black = RED;
            n.sibling(parents).black = BLACK;
            if (n == n.parent(parents).left)
            {
                //rotate on the parent, back up one level
                RedBlackNode<D> parent = n.parent(parents);
                parents.removeLast();
                RedBlackNode<D> replacement = rotate_left(parents, parent);

                //n acually ends up deeper now than to begin with
                //so we need to regenerate the parents list to its prior level
                parents.add(replacement);
                parents.add(replacement.left);
                n = replacement.left.left = replacement.left.left.clone();
            }
            else
            {
                RedBlackNode<D> parent = n.parent(parents);
                parents.removeLast();
                RedBlackNode<D> replacement =rotate_right(parents, parent);
                parents.add(replacement);
                parents.add(replacement.right);
                n = replacement.right.right = replacement.right.right.clone();
            }
        }
        delete_case3(parents, n);
    }

    private void delete_case3(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
        if (n.parent(parents).black &&
                n.sibling(parents).black &&
                n.sibling(parents).left.black &&
                n.sibling(parents).right.black) {
            n.cloneSibling(parents);
            n.sibling(parents).black = RED;

            RedBlackNode<D> parent = parents.removeLast();
            delete_case1(parents, parent);
        } else
            delete_case4(parents, n);
    }

    private void delete_case4(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
        if (!n.parent(parents).black &&
                n.sibling(parents).black &&
                n.sibling(parents).left.black &&
                n.sibling(parents).right.black) {
            n.cloneSibling(parents);
            n.sibling(parents).black = RED;
            n.parent(parents).black = BLACK;
        } else
            delete_case5(parents, n);
    }

    private void delete_case5(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
        if (n == n.parent(parents).left &&
                n.sibling(parents).black &&
                !n.sibling(parents).left.black &&
                n.sibling(parents).right.black) {
            n.cloneSibling(parents);
            n.sibling(parents).black = RED;
            n.sibling(parents).left = n.sibling(parents).left.clone();
            n.sibling(parents).left.black = BLACK;
            rotate_right(parents, n.sibling(parents));
        } else if (n == n.parent(parents).right &&
                n.sibling(parents).black &&
                !n.sibling(parents).right.black &&
                n.sibling(parents).left.black) {
            n.cloneSibling(parents);
            n.sibling(parents).black = RED;
            n.sibling(parents).right = n.sibling(parents).right.clone();
            n.sibling(parents).right.black = BLACK;
            rotate_left(parents, n.sibling(parents));
        }
        delete_case6(parents, n);
    }

    private void delete_case6(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
        n.cloneSibling(parents);
        n.sibling(parents).black = n.parent(parents).black;
        n.parent(parents).black = BLACK;
        if (n == n.parent(parents).left) {
            n.sibling(parents).right = n.sibling(parents).right.clone();
            n.sibling(parents).right.black = BLACK;
            RedBlackNode<D> parent = parents.removeLast();
            rotate_left(parents, parent);
        } else {
            n.sibling(parents).left = n.sibling(parents).left.clone();
            n.sibling(parents).left.black = BLACK;
            RedBlackNode<D> parent = parents.removeLast();
            rotate_right(parents, parent);
        }
    }