Repository: yorkie-team/yorkie
Pull request #415 (2022-09-20 10:43:42)

Remove size cache from RGATreeList and use SplayTree instead
<!--  Thanks for sending a pull request! -->

**What this PR does / why we need it**:

Previously, in JS SDK, the element size of RGATreeList was changed to be returned from SplayTree rather than `size` property.

**Which issue(s) this PR fixes**:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
-->
Related to https://github.com/yorkie-team/yorkie-js-sdk/pull/315

**Special notes for your reviewer**:

**Does this PR introduce a user-facing change?**:
<!--
If no, just write "NONE" in the release-note block below.
If yes, a release note is required:
Enter your extended release note in the block below. If the PR requires additional action from users switching to the new release, include the string "action required".
-->
```release-note

```

**Additional documentation**:

<!--
This section can be blank if this pull request does not require a release note.

Please use the following format for linking documentation:
- [Usage]: <link>
- [Other doc]: <link>
-->
```docs

```

**Checklist**:
- [x] Added relevant tests or not required
- [x] Didn't break anything


codecov[bot]: # [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/415?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) Report
> Merging [#415](https://codecov.io/gh/yorkie-team/yorkie/pull/415?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (0f23fa8) into [main](https://codecov.io/gh/yorkie-team/yorkie/commit/33006c3d40cdffcb8021b89f43157c9d6213334f?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (33006c3) will **decrease** coverage by `0.00%`.
> The diff coverage is `40.00%`.

```diff
@@            Coverage Diff             @@
##             main     #415      +/-   ##
==========================================
- Coverage   46.83%   46.82%   -0.01%     
==========================================
  Files          71       71              
  Lines        5923     5922       -1     
==========================================
- Hits         2774     2773       -1     
  Misses       2846     2846              
  Partials      303      303              
```


| [Impacted Files](https://codecov.io/gh/yorkie-team/yorkie/pull/415?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) | Coverage Δ | |
|---|---|---|
| [pkg/document/crdt/rga\_tree\_list.go](https://codecov.io/gh/yorkie-team/yorkie/pull/415/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2NyZHQvcmdhX3RyZWVfbGlzdC5nbw==) | `64.46% <0.00%> (+0.17%)` | :arrow_up: |
| [pkg/splay/splay.go](https://codecov.io/gh/yorkie-team/yorkie/pull/415/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL3NwbGF5L3NwbGF5Lmdv) | `77.08% <50.00%> (-0.58%)` | :arrow_down: |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team)


Patch:
diff --git a/pkg/document/crdt/rga_tree_list.go b/pkg/document/crdt/rga_tree_list.go
index b3a88ad9..8d893476 100644
--- a/pkg/document/crdt/rga_tree_list.go
+++ b/pkg/document/crdt/rga_tree_list.go
@@ -100,7 +100,6 @@ func (n *RGATreeListNode) isRemoved() bool {
 type RGATreeList struct {
 	dummyHead          *RGATreeListNode
 	last               *RGATreeListNode
-	size               int
 	nodeMapByIndex     *splay.Tree[*RGATreeListNode]
 	nodeMapByCreatedAt map[string]*RGATreeListNode
 }
@@ -117,7 +116,6 @@ func NewRGATreeList() *RGATreeList {
 	return &RGATreeList{
 		dummyHead:          dummyHead,
 		last:               dummyHead,
-		size:               0,
 		nodeMapByIndex:     nodeMapByIndex,
 		nodeMapByCreatedAt: nodeMapByCreatedAt,
 	}
@@ -214,14 +212,13 @@ func (a *RGATreeList) DeleteByCreatedAt(createdAt *time.Ticket, deletedAt *time.
 	alreadyRemoved := node.isRemoved()
 	if node.elem.Remove(deletedAt) && !alreadyRemoved {
 		a.nodeMapByIndex.Splay(node.indexNode)
-		a.size--
 	}
 	return node
 }
 
 // Len returns length of this RGATreeList.
 func (a *RGATreeList) Len() int {
-	return a.size
+	return a.nodeMapByIndex.Len()
 }
 
 // StructureAsString returns a String containing the metadata of the node id
@@ -313,10 +310,6 @@ func (a *RGATreeList) release(node *RGATreeListNode) {
 
 	a.nodeMapByIndex.Delete(node.indexNode)
 	delete(a.nodeMapByCreatedAt, node.CreatedAt().Key())
-
-	if !node.isRemoved() {
-		a.size--
-	}
 }
 
 func (a *RGATreeList) insertAfter(
@@ -332,6 +325,4 @@ func (a *RGATreeList) insertAfter(
 
 	a.nodeMapByIndex.InsertAfter(prevNode.indexNode, newNode.indexNode)
 	a.nodeMapByCreatedAt[value.CreatedAt().Key()] = newNode
-
-	a.size++
 }
diff --git a/pkg/splay/splay.go b/pkg/splay/splay.go
index ff8db874..58b9facf 100644
--- a/pkg/splay/splay.go
+++ b/pkg/splay/splay.go
@@ -156,6 +156,7 @@ func (t *Tree[V]) Splay(node *Node[V]) {
 			} else if isRightChild(node) {
 				t.rotateLeft(node)
 			}
+			t.updateTreeWeight(node)
 			return
 		}
 	}
@@ -387,6 +388,14 @@ func (t *Tree[V]) rightmost() *Node[V] {
 	return node
 }
 
+func (t *Tree[V]) Len() int {
+	if t.root == nil {
+		return 0
+	}
+
+	return t.root.weight
+}
+
 func traverseInOrder[V Value](node *Node[V], callback func(node *Node[V])) {
 	if node == nil {
 		return


Test patch:
diff --git a/pkg/document/document_test.go b/pkg/document/document_test.go
index 0a6cbf25..b984ae2a 100644
--- a/pkg/document/document_test.go
+++ b/pkg/document/document_test.go
@@ -160,6 +160,41 @@ func TestDocument(t *testing.T) {
 		assert.NoError(t, err)
 	})
 
+	t.Run("delete elements of array test", func(t *testing.T) {
+		doc := document.New("d1")
+		err := doc.Update(func(root *json.Object) error {
+			root.SetNewArray("data").AddInteger(0).AddInteger(1).AddInteger(2)
+			return nil
+		})
+		assert.NoError(t, err)
+		assert.Equal(t, `{"data":[0,1,2]}`, doc.Marshal())
+		assert.Equal(t, 3, doc.Root().GetArray("data").Len())
+
+		err = doc.Update(func(root *json.Object) error {
+			root.GetArray("data").Delete(0)
+			return nil
+		})
+		assert.NoError(t, err)
+		assert.Equal(t, `{"data":[1,2]}`, doc.Marshal())
+		assert.Equal(t, 2, doc.Root().GetArray("data").Len())
+
+		err = doc.Update(func(root *json.Object) error {
+			root.GetArray("data").Delete(1)
+			return nil
+		})
+		assert.NoError(t, err)
+		assert.Equal(t, `{"data":[1]}`, doc.Marshal())
+		assert.Equal(t, 1, doc.Root().GetArray("data").Len())
+
+		err = doc.Update(func(root *json.Object) error {
+			root.GetArray("data").Delete(0)
+			return nil
+		})
+		assert.NoError(t, err)
+		assert.Equal(t, `{"data":[]}`, doc.Marshal())
+		assert.Equal(t, 0, doc.Root().GetArray("data").Len())
+	})
+
 	t.Run("text test", func(t *testing.T) {
 		doc := document.New("d1")
 
diff --git a/pkg/splay/splay_test.go b/pkg/splay/splay_test.go
index 4e665df8..1960d52b 100644
--- a/pkg/splay/splay_test.go
+++ b/pkg/splay/splay_test.go
@@ -89,15 +89,20 @@ func TestSplayTree(t *testing.T) {
 
 		nodeH := tree.Insert(newSplayNode("H"))
 		assert.Equal(t, "[1,1]H", tree.StructureAsString())
+		assert.Equal(t, 1, tree.Len())
 		nodeE := tree.Insert(newSplayNode("E"))
 		assert.Equal(t, "[1,1]H[2,1]E", tree.StructureAsString())
+		assert.Equal(t, 2, tree.Len())
 		nodeL := tree.Insert(newSplayNode("LL"))
 		assert.Equal(t, "[1,1]H[2,1]E[4,2]LL", tree.StructureAsString())
+		assert.Equal(t, 4, tree.Len())
 		nodeO := tree.Insert(newSplayNode("O"))
 		assert.Equal(t, "[1,1]H[2,1]E[4,2]LL[5,1]O", tree.StructureAsString())
+		assert.Equal(t, 5, tree.Len())
 
 		tree.Delete(nodeE)
 		assert.Equal(t, "[4,1]H[3,2]LL[1,1]O", tree.StructureAsString())
+		assert.Equal(t, 4, tree.Len())
 
 		assert.Equal(t, tree.IndexOf(nodeH), 0)
 		assert.Equal(t, tree.IndexOf(nodeE), -1)