Repository: yorkie-team/yorkie
Pull request #331 (2022-05-21 08:22:44)

Improve the llrb tree using generic
<!--  Thanks for sending a pull request! -->

**What this PR does / why we need it**:
Improve the `llrb.go` using generic.

**Which issue(s) this PR fixes**:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
-->
Address #304

**Special notes for your reviewer**:
When a generic type is a return type, nil cannot be returned because of the zero-value issue.
It is possible to add a method that handles zero-value, but I think it is sufficient to handle it within the method. What do you think?

**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


dc7303: When generics are return types, we can't return nil, so we can handle zero-values ​​like this.
```go
var zeroK K
var zeroV V
return zeroK, zeroV
```

https://github.com/yorkie-team/yorkie/pull/331/files#diff-24b81e7ebed48258518bbf8ade164201ec590aec37112d003a3b05fd4126db15R133-R135
codecov[bot]: # [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/331?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) Report
> Merging [#331](https://codecov.io/gh/yorkie-team/yorkie/pull/331?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (5efbc85) into [main](https://codecov.io/gh/yorkie-team/yorkie/commit/546f32070c8b33bd8091fac8fef92b6c35ce6822?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (546f320) will **decrease** coverage by `0.03%`.
> The diff coverage is `55.55%`.

```diff
@@            Coverage Diff             @@
##             main     #331      +/-   ##
==========================================
- Coverage   46.09%   46.05%   -0.04%     
==========================================
  Files          64       64              
  Lines        5328     5328              
==========================================
- Hits         2456     2454       -2     
- Misses       2606     2608       +2     
  Partials      266      266              
```


| [Impacted Files](https://codecov.io/gh/yorkie-team/yorkie/pull/331?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) | Coverage Δ | |
|---|---|---|
| [pkg/llrb/llrb.go](https://codecov.io/gh/yorkie-team/yorkie/pull/331/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2xscmIvbGxyYi5nbw==) | `80.31% <50.00%> (-1.29%)` | :arrow_down: |
| [pkg/document/json/rga\_tree\_split.go](https://codecov.io/gh/yorkie-team/yorkie/pull/331/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2pzb24vcmdhX3RyZWVfc3BsaXQuZ28=) | `73.51% <66.66%> (-0.24%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/331?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/331?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team). Last update [546f320...5efbc85](https://codecov.io/gh/yorkie-team/yorkie/pull/331?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team).


Patch:
diff --git a/pkg/document/json/rga_tree_split.go b/pkg/document/json/rga_tree_split.go
index 145f8e2d..c302796a 100644
--- a/pkg/document/json/rga_tree_split.go
+++ b/pkg/document/json/rga_tree_split.go
@@ -286,7 +286,7 @@ func (t *RGATreeSplitNode) Value() RGATreeSplitValue {
 type RGATreeSplit struct {
 	initialHead *RGATreeSplitNode
 	treeByIndex *splay.Tree
-	treeByID    *llrb.Tree
+	treeByID    *llrb.Tree[*RGATreeSplitNodeID, *RGATreeSplitNode]
 
 	// removedNodeMap is a map that holds tombstone nodes
 	// when the edit operation is executed.
@@ -296,7 +296,7 @@ type RGATreeSplit struct {
 // NewRGATreeSplit creates a new instance of RGATreeSplit.
 func NewRGATreeSplit(initialHead *RGATreeSplitNode) *RGATreeSplit {
 	treeByIndex := splay.NewTree(initialHead.indexNode)
-	treeByID := llrb.NewTree()
+	treeByID := llrb.NewTree[*RGATreeSplitNodeID, *RGATreeSplitNode]()
 	treeByID.Put(initialHead.ID(), initialHead)
 
 	return &RGATreeSplit{
@@ -418,14 +418,11 @@ func (s *RGATreeSplit) findFloorNode(id *RGATreeSplitNodeID) *RGATreeSplitNode {
 		return nil
 	}
 
-	foundID := key.(*RGATreeSplitNodeID)
-	foundValue := value.(*RGATreeSplitNode)
-
-	if !foundID.Equal(id) && !foundID.hasSameCreatedAt(id) {
+	if !key.Equal(id) && !key.hasSameCreatedAt(id) {
 		return nil
 	}
 
-	return foundValue
+	return value
 }
 
 func (s *RGATreeSplit) edit(
diff --git a/pkg/llrb/llrb.go b/pkg/llrb/llrb.go
index 2734232f..0f8617cf 100644
--- a/pkg/llrb/llrb.go
+++ b/pkg/llrb/llrb.go
@@ -35,18 +35,18 @@ type Value interface {
 }
 
 // Node is a node of Tree.
-type Node struct {
-	key    Key
-	value  Value
-	parent *Node
-	left   *Node
-	right  *Node
+type Node[K Key, V Value] struct {
+	key    K
+	value  V
+	parent *Node[K, V]
+	left   *Node[K, V]
+	right  *Node[K, V]
 	isRed  bool
 }
 
 // NewNode creates a new instance of Node.
-func NewNode(key Key, value Value, isRed bool) *Node {
-	return &Node{
+func NewNode[K Key, V Value](key K, value V, isRed bool) *Node[K, V] {
+	return &Node[K, V]{
 		key:   key,
 		value: value,
 		isRed: isRed,
@@ -60,33 +60,33 @@ func NewNode(key Key, value Value, isRed bool) *Node {
 // Invariant 1: No red node has a red child
 // Invariant 2: Every leaf path has the same number of black nodes
 // Invariant 3: Only the left child can be red (left leaning)
-type Tree struct {
-	root *Node
+type Tree[K Key, V Value] struct {
+	root *Node[K, V]
 	size int
 }
 
 // NewTree creates a new instance of Tree.
-func NewTree() *Tree {
-	return &Tree{}
+func NewTree[K Key, V Value]() *Tree[K, V] {
+	return &Tree[K, V]{}
 }
 
 // Put puts the value of the given key.
-func (t *Tree) Put(k Key, v Value) Value {
+func (t *Tree[K, V]) Put(k K, v V) V {
 	t.root = t.put(t.root, k, v)
 	t.root.isRed = false
 	return v
 }
 
-func (t *Tree) String() string {
+func (t *Tree[K, V]) String() string {
 	var str []string
-	traverseInOrder(t.root, func(node *Node) {
+	traverseInOrder(t.root, func(node *Node[K, V]) {
 		str = append(str, node.value.String())
 	})
 	return strings.Join(str, ",")
 }
 
 // Remove removes the value of the given key.
-func (t *Tree) Remove(key Key) {
+func (t *Tree[K, V]) Remove(key K) {
 	if !isRed(t.root.left) && !isRed(t.root.right) {
 		t.root.isRed = true
 	}
@@ -98,7 +98,7 @@ func (t *Tree) Remove(key Key) {
 }
 
 // Floor returns the greatest key less than or equal to the given key.
-func (t *Tree) Floor(key Key) (Key, Value) {
+func (t *Tree[K, V]) Floor(key K) (K, V) {
 	node := t.root
 
 	for node != nil {
@@ -130,10 +130,12 @@ func (t *Tree) Floor(key Key) (Key, Value) {
 		}
 	}
 
-	return nil, nil
+	var zeroK K
+	var zeroV V
+	return zeroK, zeroV
 }
 
-func (t *Tree) put(node *Node, key Key, value Value) *Node {
+func (t *Tree[K, V]) put(node *Node[K, V], key K, value V) *Node[K, V] {
 	if node == nil {
 		t.size++
 		return NewNode(key, value, true)
@@ -163,7 +165,7 @@ func (t *Tree) put(node *Node, key Key, value Value) *Node {
 	return node
 }
 
-func (t *Tree) remove(node *Node, key Key) *Node {
+func (t *Tree[K, V]) remove(node *Node[K, V], key K) *Node[K, V] {
 	if key.Compare(node.key) < 0 {
 		if !isRed(node.left) && !isRed(node.left.left) {
 			node = moveRedLeft(node)
@@ -197,7 +199,7 @@ func (t *Tree) remove(node *Node, key Key) *Node {
 	return fixUp(node)
 }
 
-func rotateLeft(node *Node) *Node {
+func rotateLeft[K Key, V Value](node *Node[K, V]) *Node[K, V] {
 	right := node.right
 	node.right = right.left
 	right.left = node
@@ -206,7 +208,7 @@ func rotateLeft(node *Node) *Node {
 	return right
 }
 
-func rotateRight(node *Node) *Node {
+func rotateRight[K Key, V Value](node *Node[K, V]) *Node[K, V] {
 	left := node.left
 	node.left = left.right
 	left.right = node
@@ -215,13 +217,13 @@ func rotateRight(node *Node) *Node {
 	return left
 }
 
-func flipColors(node *Node) {
+func flipColors[K Key, V Value](node *Node[K, V]) {
 	node.isRed = !node.isRed
 	node.left.isRed = !node.left.isRed
 	node.right.isRed = !node.right.isRed
 }
 
-func moveRedLeft(node *Node) *Node {
+func moveRedLeft[K Key, V Value](node *Node[K, V]) *Node[K, V] {
 	flipColors(node)
 	if isRed(node.right.left) {
 		node.right = rotateRight(node.right)
@@ -231,7 +233,7 @@ func moveRedLeft(node *Node) *Node {
 	return node
 }
 
-func moveRedRight(node *Node) *Node {
+func moveRedRight[K Key, V Value](node *Node[K, V]) *Node[K, V] {
 	flipColors(node)
 	if isRed(node.left.left) {
 		node = rotateRight(node)
@@ -240,7 +242,7 @@ func moveRedRight(node *Node) *Node {
 	return node
 }
 
-func removeMin(node *Node) *Node {
+func removeMin[K Key, V Value](node *Node[K, V]) *Node[K, V] {
 	if node.left == nil {
 		return nil
 	}
@@ -254,7 +256,7 @@ func removeMin(node *Node) *Node {
 
 }
 
-func min(node *Node) *Node {
+func min[K Key, V Value](node *Node[K, V]) *Node[K, V] {
 	if node.left == nil {
 		return node
 	}
@@ -262,7 +264,7 @@ func min(node *Node) *Node {
 	return min(node.left)
 }
 
-func fixUp(node *Node) *Node {
+func fixUp[K Key, V Value](node *Node[K, V]) *Node[K, V] {
 	if isRed(node.right) {
 		node = rotateLeft(node)
 	}
@@ -278,11 +280,11 @@ func fixUp(node *Node) *Node {
 	return node
 }
 
-func isRed(node *Node) bool {
+func isRed[K Key, V Value](node *Node[K, V]) bool {
 	return node != nil && node.isRed
 }
 
-func traverseInOrder(node *Node, callback func(node *Node)) {
+func traverseInOrder[K Key, V Value](node *Node[K, V], callback func(node *Node[K, V])) {
 	if node == nil {
 		return
 	}


Test patch:
diff --git a/pkg/llrb/llrb_test.go b/pkg/llrb/llrb_test.go
index 9e6feaea..9003ac1e 100644
--- a/pkg/llrb/llrb_test.go
+++ b/pkg/llrb/llrb_test.go
@@ -71,7 +71,7 @@ func TestTree(t *testing.T) {
 		}
 
 		for _, array := range arrays {
-			tree := llrb.NewTree()
+			tree := llrb.NewTree[*intKey, *intValue]()
 			for _, value := range array {
 				tree.Put(newIntKey(value), newIntValue(value))
 			}