Repository: yorkie-team/yorkie
Pull request #470 (2023-02-17 07:44:01)

Fix invalid index of SplayTree with single node
<!--  Thanks for sending a pull request! -->

**What this PR does / why we need it**:

Fix invalid index of SplayTree with a single node.

This PR addresses an issue with the `indexOf` in SplayTree, which was failing to calculate the correct index when there was only one node in the tree. The conditional statement has been updated to account for this scenario.

**Which issue(s) this PR fixes**:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
-->
Fixes #

**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/470?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) Report
> Merging [#470](https://codecov.io/gh/yorkie-team/yorkie/pull/470?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (225b584) into [main](https://codecov.io/gh/yorkie-team/yorkie/commit/3d9fe9dae1e001f8711ef48b75e47933b38edb91?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (3d9fe9d) will **increase** coverage by `0.03%`.
> The diff coverage is `100.00%`.

```diff
@@            Coverage Diff             @@
##             main     #470      +/-   ##
==========================================
+ Coverage   46.26%   46.30%   +0.03%     
==========================================
  Files          69       69              
  Lines        5678     5678              
==========================================
+ Hits         2627     2629       +2     
+ Misses       2758     2756       -2     
  Partials      293      293              
```


| [Impacted Files](https://codecov.io/gh/yorkie-team/yorkie/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) | Coverage Δ | |
|---|---|---|
| [pkg/splay/splay.go](https://codecov.io/gh/yorkie-team/yorkie/pull/470?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL3NwbGF5L3NwbGF5Lmdv) | `78.12% <100.00%> (+1.04%)` | :arrow_up: |

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/splay/splay.go b/pkg/splay/splay.go
index 760302cd..5d6e7fc1 100644
--- a/pkg/splay/splay.go
+++ b/pkg/splay/splay.go
@@ -165,7 +165,7 @@ func (t *Tree[V]) Splay(node *Node[V]) {
 
 // IndexOf Find the index of the given node.
 func (t *Tree[V]) IndexOf(node *Node[V]) int {
-	if node == nil || !node.hasLinks() {
+	if node == nil || node != t.root && !node.hasLinks() {
 		return -1
 	}
 


Test patch:
diff --git a/pkg/splay/splay_test.go b/pkg/splay/splay_test.go
index 1960d52b..7db5d112 100644
--- a/pkg/splay/splay_test.go
+++ b/pkg/splay/splay_test.go
@@ -143,6 +143,14 @@ func TestSplayTree(t *testing.T) {
 			tree.StructureAsString(),
 		)
 	})
+
+	t.Run("single node index test", func(t *testing.T) {
+		tree := splay.NewTree[*stringValue](nil)
+		node := tree.Insert(newSplayNode("A"))
+		assert.Equal(t, 0, tree.IndexOf(node))
+		tree.Delete(node)
+		assert.Equal(t, -1, tree.IndexOf(node))
+	})
 }
 
 func makeSampleTree() (*splay.Tree[*stringValue], []*splay.Node[*stringValue]) {