K.I.S.S

public Object[] arrayFor(int i){
        if(i >= 0 && i < cnt)
        {
                if(i >= tailoff())
                return tail;
                Node node = root;
                for(int level = shift; level > 0; level -= 5)
                node = (Node) node.array[(i >>> level) & 0x01f];
                return node.array;
        }
        throw new IndexOutOfBoundsException();
}

public Object nth(int i){
        Object[] node = arrayFor(i);
        return node[i & 0x01f];
}

static class Node implements Serializable {
        transient final AtomicReference<Thread> edit;
        final Object[] array;

        Node(AtomicReference<Thread> edit, Object[] array){
        this.edit = edit;
        this.array = array;
        }

        Node(AtomicReference<Thread> edit){
        this.edit = edit;
        this.array = new Object[32];
        }
}

final private int tailoff(){
    if(cnt < 32)
        return 0;
    return ((cnt-1) >>> 5) << 5;
}

public PersistentVector cons(Object val){
        int i = cnt;
        //room in tail?
      //        if(tail.length < 32)
      //这里还是tail的特殊处理,tail的长度没有32,就先放tail里面.这里好理解.
        if(cnt - tailoff() < 32)
          {
                Object[] newTail = new Object[tail.length + 1];
                System.arraycopy(tail, 0, newTail, 0, tail.length);
                newTail[tail.length] = val;
                return new PersistentVector(meta(), cnt + 1, shift, root, newTail);
          }
        //full tail, push into tree 如前所述,满了32.
        Node newroot;
        Node tailnode = new Node(root.edit,tail);
        int newshift = shift;
        //overflow root?下面的一坨操作,要先看看pushTail和newPath
      //树全满的情况下,重新升高一层树,新的tailnode要放在另外新建的深度如旧树的一棵树上
        if((cnt >>> 5) > (1 << shift))
          {
                newroot = new Node(root.edit);
                newroot.array[0] = root;
                newroot.array[1] = newPath(root.edit,shift, tailnode);
                newshift += 5;
          }
      //树没有全满,那么就往下找,有空就插入,没空就建新的枝.
        else
          newroot = pushTail(shift, root, tailnode);
      //所有的增加都会直接保证加入位置的深度一致.因为只有叶子才存数据.
        return new PersistentVector(meta(), cnt + 1, newshift, newroot, new Object[]{val});
  }

  private Node pushTail(int level, Node parent, Node tailnode){
        //if parent is leaf, insert node,
        // else does it map to an existing child? -> nodeToInsert = pushNode one more level
        // else alloc new path
        //return  nodeToInsert placed in copy of parent
      //
        int subidx = ((cnt - 1) >>> level) & 0x01f;
        Node ret = new Node(parent.edit, parent.array.clone());
        Node nodeToInsert;
      //parent is leaf的情况
        if(level == 5)
          {
                nodeToInsert = tailnode;
          }
        else
          {
                Node child = (Node) parent.array[subidx];
              //第二个判断情况,子树是null就新建一个单分支的子树到底层.不是的话就一直找到底层,然后加入.
                nodeToInsert = (child != null)?
                  pushTail(level-5,child, tailnode)
                  :newPath(root.edit,level-5, tailnode);
          }
        ret.array[subidx] = nodeToInsert;
        return ret;
  }

  //一路新建单分支的子树
  private static Node newPath(AtomicReference<Thread> edit,int level, Node node){
        if(level == 0)
          return node;
        Node ret = new Node(edit);
        ret.array[0] = newPath(edit, level - 5, node);
        return ret;
  }

public PersistentVector pop(){
        if(cnt == 0)
        throw new IllegalStateException("Can't pop empty vector");
        if(cnt == 1)
        return EMPTY.withMeta(meta());
        //if(tail.length > 1)
    //以直接在tail里面pop的,很容易.
        if(cnt-tailoff() > 1)
        {
                Object[] newTail = new Object[tail.length - 1];
                System.arraycopy(tail, 0, newTail, 0, newTail.length);
                return new PersistentVector(meta(), cnt - 1, shift, root, newTail);
        }
    //不能的情况下,就从树里pop出来一个,当然,同时就需要把剩下的31个不完整的抽出来当做newtail.
    //为什么要以cnt-2开始,因为前面的判断是tail.length > 1,tail里面有可能还有一个孤零零的元素.
        Object[] newtail = arrayFor(cnt - 2);

    //以下的代码就是从树中删除newtail的过程了.

    //新树的root也有可能需要做变更.
        Node newroot = popTail(shift, root);
        int newshift = shift;
    //这里如果一路都是单枝,结果是一路都删除路径到root,应该其实就是长度为32/33的情况.
        if(newroot == null)
        {
                newroot = EMPTY_NODE;
        }
    //层次大于1,但是root的第二子树已经是空的话,就需要降低层次了.
        if(shift > 5 && newroot.array[1] == null)
        {
                newroot = (Node) newroot.array[0];
                newshift -= 5;
        }
        return new PersistentVector(meta(), cnt - 1, newshift, newroot, newtail);
}

//
private Node popTail(int level, Node node){
    //倒数第二个位置的元素在最底层的index
        int subidx = ((cnt-2) >>> level) & 0x01f;
    //一直往底层走
        if(level > 5)
        {
            //去下层, level-5, 以subidx所在的array开始.
                Node newchild = popTail(level - 5, (Node) node.array[subidx]);
            //上层依然是单枝,需要继续删除路径的情况
                if(newchild == null && subidx == 0)
                return null;
                else
                {
                        Node ret = new Node(root.edit, node.array.clone());
                        ret.array[subidx] = newchild;
                        return ret;
                }
        }
    //到达底层,位置却是0,这里到达的不是包含叶子的底层,而是最后一个树枝层.
    //到达底树枝层,正好是一个单枝,因为下一步叶子层的index是0,如果要提出来当tail,这个单枝就需要删除了.而且要一路删除到上层不再是单枝路径为止.
        else if(subidx == 0)
        return null;
    //到达底树枝层
        else
        {
                Node ret = new Node(root.edit, node.array.clone());
            //显然,直接将要pop出来的tail删掉了.
                ret.array[subidx] = null;
                return ret;
        }
}