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;
        }
}