[250416] clojure PersistentVector - 작업중

final int cnt;
public final int shift;
public final Node root;
public final Object[] tail;
final IPersistentMap _meta;

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

	public 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 static AtomicReference<Thread> NOEDIT = new AtomicReference<Thread>(null);
public final static Node EMPTY_NODE = new Node(NOEDIT, new Object[32]);

final int cnt;
public final int shift;
public final Node root;
public final Object[] tail;
final IPersistentMap _meta;


public final static PersistentVector EMPTY = new PersistentVector(0, 5, EMPTY_NODE, new Object[]{});

private static final IFn TRANSIENT_VECTOR_CONJ = new AFn() {
    public Object invoke(Object coll, Object val) {
	return ((ITransientVector)coll).conj(val);
    }
    public Object invoke(Object coll) {
	return coll;
    }
};

static public PersistentVector adopt(Object [] items){
	return new PersistentVector(items.length, 5, EMPTY_NODE, items);
}

static public PersistentVector create(IReduceInit items) {
    TransientVector ret = EMPTY.asTransient();
    items.reduce(TRANSIENT_VECTOR_CONJ, ret);
    return ret.persistent();
}

public final int shift;
public final Node root;
public final Object[] tail;

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

// 초기화
public PersistentVector(int cnt, int shift, Node root, Object[] tail){
    this._meta = null;
    this.cnt = cnt;
    this.shift = shift;
    this.root = root;
    this.tail = tail;
}

// 빈 벡터 생성
public static final PersistentVector EMPTY = new PersistentVector(0, 5, EMPTY_NODE, new Object[]{});

// 요소를 추가할 때 tail에 저장되며, cnt - tailoff() < 32 조건 확인:
public PersistentVector cons(Object val){
    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);
    }
    // 32를 초과하면 트리 구조로 전환 (다음 케이스에서 설명)
}
// 여기서 tailoff()는 tail이 시작되는 오프셋을 계산:
final int tailoff(){
    if(cnt < 32)
	return 0;
    return ((cnt-1) >>> 5) << 5;
}

PersistentVector (cnt=5)
├── root: 빈 노드
└── tail: [0, 1, 2, 3, 4]

// 요소 추가 시 cnt - tailoff() >= 32이면 root에 새 노드를 추가:
public PersistentVector cons(Object val){
    if(cnt - tailoff() < 32) {
	// tail에 공간이 있을 때
    } else {
	Node tailnode = new Node(root.edit, tail);
	Node newroot;
	if((cnt >>> 5) > (1 << shift)) {
	    newroot = new Node(root.edit);
	    newroot.array[0] = root;
	    newroot.array[1] = newPath(root.edit, shift, tailnode);
	    shift += 5;
	} else {
	    newroot = pushTail(shift, root, tailnode);
	}
	return new PersistentVector(meta(), cnt + 1, shift, newroot, new Object[]{val});
    }
}

// tailoff()는 tail의 시작 지점을 계산:
final int tailoff(){
    if(cnt < 32)
	return 0;
    return ((cnt-1) >>> 5) << 5; // 33일 때 32 반환
}

// 인덱스 접근 시 arrayFor 메서드가 사용
public Object[] arrayFor(int i){
    if(i >= 0 && i < cnt){
	if(i >= tailoff()) // i >= 32면 tail 반환
	    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();
}

// shift 값은 트리의 깊이를 제어
public PersistentVector(int cnt, int shift, Node root, Object[] tail){
    this.cnt = cnt;
    this.shift = shift; // 트리 깊이에 따라 5, 10, 15 등으로 증가
    this.root = root;
    this.tail = tail;
}

// pushTail 메서드는 트리에 새 리프 노드를 추가
private PersistentVector pushTail(int level, Node parent, Node tailnode){
    int subidx = ((cnt - 1) >>> level) & 0x01f;
    Node ret = new Node(parent.edit, parent.array.clone());
    Node nodeToInsert;
    if(level == 5) {
	nodeToInsert = tailnode;
    } else {
	Node child = (Node) parent.array[subidx];
	nodeToInsert = (child != null) ?
	    pushTail(level - 5, child, tailnode) :
	    newPath(root.edit, level - 5, tailnode);
    }
    ret.array[subidx] = nodeToInsert;
    return ret;
}

final int tailoff(){
    if(cnt < 32)
	return 0;
    return ((cnt-1) >>> 5) << 5; // 1025일 때 992 반환
}

PersistentVector (cnt=1025)
├── root (내부 노드)
│   ├── array[0] → 내부 노드
│   │   ├── array[0] → 리프 노드: [0, 1, ..., 31]
│   │   ├── array[1] → 리프 노드: [32, 33, ..., 63]
│   │   └── ... (최대 array[31]까지, [992, 993, ..., 1023])
│   ├── array[1] → 내부 노드
│   │   ├── array[0] → 리프 노드: [1024]
│   └── array[2] ~ array[31]: null
└── tail: [1024]

public PersistentVector cons(Object val) {
    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);
    } else {
	Node tailnode = new Node(root.edit, tail);
	Node newroot;
	if ((cnt >>> 5) > (1 << shift)) {
	    newroot = new Node(root.edit);
	    newroot.array[0] = root;
	    newroot.array[1] = newPath(root.edit, shift, tailnode);
	    shift += 5;
	} else {
	    newroot = pushTail(shift, root, tailnode);
	}
	return new PersistentVector(meta(), cnt + 1, shift, newroot, new Object[]{val});
    }
}

public PersistentVector assocN(int i, Object val) {
    if (i >= 0 && i < cnt) {
	if (i >= tailoff()) {
	    Object[] newTail = new Object[tail.length];
	    System.arraycopy(tail, 0, newTail, 0, tail.length);
	    newTail[i & 0x01f] = val;
	    return new PersistentVector(meta(), cnt, shift, root, newTail);
	}
	return new PersistentVector(meta(), cnt, shift, doAssoc(shift, root, i, val), tail);
    }
    if (i == cnt)
	return cons(val);
    throw new IndexOutOfBoundsException();
}

// 경로복사가 수행되는 곳.
// 동작방식
// assoc 연산이 호출되면 doAssoc가 트리의 루트에서 시작
// 각 레벨에서 노드를 복사하고, 변경이 필요한 경로를 따라 하위 노드로 내려감
// 리프 노드에 도달하면 값을 업데이트하고, 새로운 노드를 반환하며 상위 노드로 거슬러 올라감
// 결과적으로, 변경된 경로상의 노드만 새로 생성되고 나머지는 기존 트리와 공유됨
private static Node doAssoc(int level, Node node, int i, Object val) {
    // 현재 노드를 복사해 새로운 노드(ret)를 생성한다.
    // node.array.clone()을 통해 배열을 복사하므로 원본과 독립적인 노드가 만들어진다. 이는 경로 복사의 핵심이다.
    Node ret = new Node(node.edit, node.array.clone());
    // 리프 노드 업데이트
    if (level == 0) {
	// level이 0이면 리프 노드에 도달한 것이므로, 지정된 인덱스(i & 0x01f)에 새 값(val)을 설정한다.
	// 0x01f는 16진수 값으로, 10진수로는 31에 해당, 11111이며, 5비트가 모두 1로 설정된 값
	// PersistentVector는 32-ary 트리(각 노드가 최대 32개의 자식을 가짐)를 사용하므로, 인덱스를 5비트 단위로 분할하여 처리
	// 이는 2^5 = 32 이기 때문
	// 코드에서 i & 0x01f 연산은 인덱스 i의 하위 5비트를 추출. 
	// 이 값은 현재 레벨에서 선택할 슬롯(0부터 31까지)을 결정
	// 인덱스 i = 33의 이진수는 100001.
	// 100001 & 11111 = 00001이므로, i & 0x01f = 1
	// 즉, 현재 레벨에서 1번 슬롯을 선택
	ret.array[i & 0x01f] = val;
    } else {
	// 재귀적 하위 노드 처리
	// 리프가 아닌 경우, 인덱스를 계산하여 하위 노드로 재귀 호출을 수행. 
	// 이 과정에서 필요한 경로상의 노드들이 순차적으로 복사됨.

	// 현재 노드의 하위 노드 인덱스 계산
	// i >>> level 은 인덱스 i를 level 만큼 오른쪽으로 이동하여 하위 레벨을 선택
	// 예시 i = 33, level = 5인 경우
	//   - (33 >>> 5) & 0x01f
	//     - 33 >>> 5 = 00001 (1).
	//     - 00001 & 0x01f = 00001 (1).
	//   - 결과: 슬롯 1을 선택 (root.array[1]).
	// 
	// 예시 i = 33, level = 0인 경우
	//   - (33 >>> 0) & 0x01f
	//     - 33 >>> 0 = 100001 (33, 이동 없음).
	//     - 100001 & 11111 = 00001 (1).
	//   - 결과: 슬롯 1을 선택 (leaf.array[1]).
	int subidx = (i >>> level) & 0x01f;
	// level - 5 는 현재 레벨에서 5비트 오른쪽으로 이동하여 하위 레벨을 선택
	// 예를 들어, level = 5인 경우, level - 5 = 0이 되어 리프 노드 레벨에 도달
	// level 이 0 일 때까지 재귀적으로 호출됨.

	ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
    }
    return ret;
}