Repository: yorkie-team/yorkie (go)

Issue:
Introduce RGATreeList with LLRB tree for upstream performance
RGA has LinkedList inside, so the index-based upstream editing takes O(n) (e.g. `document.getArray('k1').remove(100)` or `document.getArray('k1').add(100, 'a')`). We can improve index-based upstream editing by introducing LLRB tree.

For more details about RGATreeList:
https://hal.inria.fr/hal-01343941/document

For more details about LLRB:
https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

Pull request description:
Introduce RGATreeList
<!--  Thanks for sending a pull request! -->

**What type of PR is this?**
> Uncomment only one ` /kind <>` line, hit enter to put that in a new line, and remove leading whitespace from that line:
>
> /kind api-change
> /kind bug
> /kind cleanup
> /kind deprecation
> /kind design
> /kind documentation
> /kind failing-test

/kind feature

**What this PR does / why we need it**:

Introduce RGATreeList

**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 #1

**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

```


Patch:
diff --git a/api/converter/from_bytes.go b/api/converter/from_bytes.go
index 40576cbb..ad0ee798 100644
--- a/api/converter/from_bytes.go
+++ b/api/converter/from_bytes.go
@@ -68,7 +68,7 @@ func fromJSONObject(pbObj *api.JSONElement_Object) *json.Object {
 }
 
 func fromJSONArray(pbArr *api.JSONElement_Array) *json.Array {
-	elements := json.NewRGA()
+	elements := json.NewRGATreeList()
 	for _, pbNode := range pbArr.Nodes {
 		elements.Add(fromJSONElement(pbNode.Element))
 	}
diff --git a/api/converter/from_pb.go b/api/converter/from_pb.go
index 60763943..f5e5f19c 100644
--- a/api/converter/from_pb.go
+++ b/api/converter/from_pb.go
@@ -189,7 +189,7 @@ func fromElement(pbElement *api.JSONElementSimple) json.Element {
 		)
 	case api.ValueType_JSON_ARRAY:
 		return json.NewArray(
-			json.NewRGA(),
+			json.NewRGATreeList(),
 			fromTimeTicket(pbElement.CreatedAt),
 		)
 	case api.ValueType_BOOLEAN:
diff --git a/api/converter/to_bytes.go b/api/converter/to_bytes.go
index a1eda143..00ff6d44 100644
--- a/api/converter/to_bytes.go
+++ b/api/converter/to_bytes.go
@@ -103,7 +103,7 @@ func toRHTNodes(rhtNodes []*json.RHTNode) []*api.RHTNode {
 	return pbRHTNodes
 }
 
-func toRGANodes(rgaNodes []*json.RGANode) []*api.RGANode {
+func toRGANodes(rgaNodes []*json.RGATreeListNode) []*api.RGANode {
 	var pbRGANodes []*api.RGANode
 	for _, rgaNode := range rgaNodes {
 		pbRGANodes = append(pbRGANodes, &api.RGANode{
diff --git a/pkg/document/json/array.go b/pkg/document/json/array.go
index 447c112d..66170b81 100644
--- a/pkg/document/json/array.go
+++ b/pkg/document/json/array.go
@@ -23,13 +23,13 @@ import (
 // Array represents JSON array data structure including logical clock.
 // Array implements Element interface.
 type Array struct {
-	elements  *RGA
+	elements  *RGATreeList
 	createdAt *time.Ticket
 	deletedAt *time.Ticket
 }
 
 // NewArray creates a new instance of Array.
-func NewArray(elements *RGA, createdAt *time.Ticket) *Array {
+func NewArray(elements *RGATreeList, createdAt *time.Ticket) *Array {
 	return &Array{
 		elements:  elements,
 		createdAt: createdAt,
@@ -44,20 +44,15 @@ func (a *Array) Add(elem Element) *Array {
 
 // Get returns the element of the given index.
 func (a *Array) Get(idx int) Element {
-	return a.elements.Get(idx)
+	return a.elements.Get(idx).elem
 }
 
 // Remove removes the element of the given index.
 func (a *Array) Remove(idx int, deletedAt *time.Ticket) Element {
-	removed := a.elements.Get(idx)
-	if removed != nil {
-		a.elements.RemoveByCreatedAt(removed.CreatedAt(), deletedAt)
-	}
-
-	return removed
+	return a.elements.Remove(idx, deletedAt).elem
 }
 
-// Elements returns an array of elements contained in this RGA.
+// Elements returns an array of elements contained in this RGATreeList.
 func (a *Array) Elements() []Element {
 	var elements []Element
 	for _, node := range a.elements.Nodes() {
@@ -75,9 +70,13 @@ func (a *Array) Marshal() string {
 	return a.elements.Marshal()
 }
 
+func (a *Array) AnnotatedString() string {
+	return a.elements.AnnotatedString()
+}
+
 // DeepCopy copies itself deeply.
 func (a *Array) DeepCopy() Element {
-	elements := NewRGA()
+	elements := NewRGATreeList()
 
 	for _, node := range a.elements.Nodes() {
 		elements.Add(node.elem.DeepCopy())
@@ -99,8 +98,12 @@ func (a *Array) DeletedAt() *time.Ticket {
 }
 
 // Delete deletes this element.
-func (a *Array) Delete(deletedAt *time.Ticket) {
-	a.deletedAt = deletedAt
+func (a *Array) Delete(deletedAt *time.Ticket) bool {
+	if a.deletedAt == nil || deletedAt.After(a.deletedAt) {
+		a.deletedAt = deletedAt
+		return true
+	}
+	return false
 }
 
 // LastCreatedAt returns the creation time of the last element.
@@ -115,7 +118,7 @@ func (a *Array) InsertAfter(prevCreatedAt *time.Ticket, element Element) {
 
 // RemoveByCreatedAt removes the given element.
 func (a *Array) RemoveByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) Element {
-	return a.elements.RemoveByCreatedAt(createdAt, deletedAt)
+	return a.elements.RemoveByCreatedAt(createdAt, deletedAt).elem
 }
 
 // Len returns length of this Array.
@@ -135,6 +138,6 @@ func (a *Array) Descendants(descendants chan Element) {
 	}
 }
 
-func (a *Array) RGANodes() []*RGANode {
+func (a *Array) RGANodes() []*RGATreeListNode {
 	return a.elements.Nodes()
 }
diff --git a/pkg/document/json/element.go b/pkg/document/json/element.go
index f33e3da6..2fe9d472 100644
--- a/pkg/document/json/element.go
+++ b/pkg/document/json/element.go
@@ -35,5 +35,5 @@ type Element interface {
 	DeletedAt() *time.Ticket
 
 	// Delete deletes this element.
-	Delete(*time.Ticket)
+	Delete(*time.Ticket) bool
 }
diff --git a/pkg/document/json/object.go b/pkg/document/json/object.go
index ab929149..15943efb 100644
--- a/pkg/document/json/object.go
+++ b/pkg/document/json/object.go
@@ -27,13 +27,13 @@ import (
 // Object represents a JSON object, but unlike regular JSON, it has time
 // tickets which is created by logical clock.
 type Object struct {
-	memberNodes *RHT
+	memberNodes *RHTPriorityQueueMap
 	createdAt   *time.Ticket
 	deletedAt   *time.Ticket
 }
 
 // NewObject creates a new instance of Object.
-func NewObject(memberNodes *RHT, createdAt *time.Ticket) *Object {
+func NewObject(memberNodes *RHTPriorityQueueMap, createdAt *time.Ticket) *Object {
 	return &Object{
 		memberNodes: memberNodes,
 		createdAt:   createdAt,
@@ -134,11 +134,15 @@ func (o *Object) DeletedAt() *time.Ticket {
 }
 
 // Delete deletes this object.
-func (o *Object) Delete(deletedAt *time.Ticket) {
-	o.deletedAt = deletedAt
+func (o *Object) Delete(deletedAt *time.Ticket) bool {
+	if o.deletedAt == nil || deletedAt.After(o.deletedAt) {
+		o.deletedAt = deletedAt
+		return true
+	}
+	return false
 }
 
-// RHTNodes returns the RHT nodes.
+// RHTNodes returns the RHTPriorityQueueMap nodes.
 func (o *Object) RHTNodes() []*RHTNode {
 	return o.memberNodes.AllNodes()
 }
diff --git a/pkg/document/json/primitive.go b/pkg/document/json/primitive.go
index 7ed044dc..f204d612 100644
--- a/pkg/document/json/primitive.go
+++ b/pkg/document/json/primitive.go
@@ -196,8 +196,12 @@ func (p *Primitive) DeletedAt() *time.Ticket {
 }
 
 // Delete deletes this element.
-func (p *Primitive) Delete(deletedAt *time.Ticket) {
-	p.deletedAt = deletedAt
+func (p *Primitive) Delete(deletedAt *time.Ticket) bool {
+	if p.deletedAt == nil || deletedAt.After(p.deletedAt) {
+		p.deletedAt = deletedAt
+		return true
+	}
+	return false
 }
 
 // ValueType returns the type of the value.
diff --git a/pkg/document/json/rga.go b/pkg/document/json/rga.go
deleted file mode 100644
index 33914336..00000000
--- a/pkg/document/json/rga.go
+++ /dev/null
@@ -1,206 +0,0 @@
-/*
- * Copyright 2020 The Yorkie Authors. All rights reserved.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package json
-
-import (
-	"strings"
-
-	"github.com/yorkie-team/yorkie/pkg/document/time"
-	"github.com/yorkie-team/yorkie/pkg/log"
-)
-
-type RGANode struct {
-	prev *RGANode
-	next *RGANode
-	elem Element
-}
-
-func newRGANode(elem Element) *RGANode {
-	return &RGANode{
-		prev: nil,
-		next: nil,
-		elem: elem,
-	}
-}
-
-func newNodeAfter(prev *RGANode, elem Element) *RGANode {
-	newNode := newRGANode(elem)
-	prevNext := prev.next
-
-	prev.next = newNode
-	newNode.prev = prev
-	newNode.next = prevNext
-	if prevNext != nil {
-		prevNext.prev = newNode
-	}
-
-	return prev.next
-}
-
-func (n *RGANode) isDeleted() bool {
-	return n.elem.DeletedAt() != nil
-}
-
-func (n *RGANode) Element() Element {
-	return n.elem
-}
-
-// RGA is replicated growable array.
-type RGA struct {
-	nodeMapByCreatedAt map[string]*RGANode
-	first              *RGANode
-	last               *RGANode
-	size               int
-}
-
-// NewRGA creates a new instance of RGA.
-func NewRGA() *RGA {
-	nodeMapByCreatedAt := make(map[string]*RGANode)
-	dummyHead := newRGANode(NewPrimitive("", time.InitialTicket))
-	nodeMapByCreatedAt[dummyHead.elem.CreatedAt().Key()] = dummyHead
-
-	return &RGA{
-		nodeMapByCreatedAt: nodeMapByCreatedAt,
-		first:              dummyHead,
-		last:               dummyHead,
-		size:               0,
-	}
-}
-
-// Marshal returns the JSON encoding of this RGA.
-func (a *RGA) Marshal() string {
-	sb := strings.Builder{}
-	sb.WriteString("[")
-
-	idx := 0
-	current := a.first.next
-	for {
-		if current == nil {
-			break
-		}
-
-		if !current.isDeleted() {
-			sb.WriteString(current.elem.Marshal())
-			if a.size-1 != idx {
-				sb.WriteString(",")
-			}
-			idx++
-		}
-
-		current = current.next
-	}
-
-	sb.WriteString("]")
-
-	return sb.String()
-}
-
-// Add adds the given element at the last.
-func (a *RGA) Add(elem Element) {
-	a.insertAfter(a.last, elem)
-}
-
-// Nodes returns an array of elements contained in this RGA.
-// TODO If we encounter performance issues, we need to replace this with other solution.
-func (a *RGA) Nodes() []*RGANode {
-	var nodes []*RGANode
-	current := a.first.next
-	for {
-		if current == nil {
-			break
-		}
-		nodes = append(nodes, current)
-		current = current.next
-	}
-
-	return nodes
-}
-
-// LastCreatedAt returns the creation time of last elements.
-func (a *RGA) LastCreatedAt() *time.Ticket {
-	return a.last.elem.CreatedAt()
-}
-
-// InsertAfter inserts the given element after the given previous element.
-func (a *RGA) InsertAfter(prevCreatedAt *time.Ticket, elem Element) {
-	prevNode := a.findByCreatedAt(prevCreatedAt, elem.CreatedAt())
-	a.insertAfter(prevNode, elem)
-}
-
-// Get returns the element of the given index.
-func (a *RGA) Get(idx int) Element {
-	// TODO introduce LLRBTree for improving upstream performance
-	current := a.first.next
-	for {
-		if current == nil {
-			break
-		}
-		if idx == 0 && !current.isDeleted() {
-			return current.elem
-		}
-
-		current = current.next
-		if !current.isDeleted() {
-			idx--
-		}
-	}
-	return nil
-}
-
-// RemoveByCreatedAt removes the given element.
-func (a *RGA) RemoveByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) Element {
-	if node, ok := a.nodeMapByCreatedAt[createdAt.Key()]; ok {
-		node.elem.Delete(deletedAt)
-		a.size--
-		return node.elem
-	}
-
-	log.Logger.Warnf("fail to find the given createdAt: %s", createdAt.Key())
-	return nil
-}
-
-// Len returns length of this RGA.
-func (a *RGA) Len() int {
-	return a.size
-}
-
-func (a *RGA) findByCreatedAt(prevCreatedAt *time.Ticket, createdAt *time.Ticket) *RGANode {
-	node := a.nodeMapByCreatedAt[prevCreatedAt.Key()]
-	if node == nil {
-		log.Logger.Fatalf(
-			"fail to find the given prevCreatedAt: %s",
-			prevCreatedAt.Key(),
-		)
-		return nil
-	}
-
-	for node.next != nil && node.next.elem.CreatedAt().After(createdAt) {
-		node = node.next
-	}
-
-	return node
-}
-
-func (a *RGA) insertAfter(prev *RGANode, element Element) {
-	newNode := newNodeAfter(prev, element)
-	if prev == a.last {
-		a.last = newNode
-	}
-
-	a.size++
-	a.nodeMapByCreatedAt[element.CreatedAt().Key()] = newNode
-}
diff --git a/pkg/document/json/rgatreelist.go b/pkg/document/json/rgatreelist.go
new file mode 100644
index 00000000..d56d3cbf
--- /dev/null
+++ b/pkg/document/json/rgatreelist.go
@@ -0,0 +1,248 @@
+/*
+ * Copyright 2020 The Yorkie Authors. All rights reserved.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package json
+
+import (
+	"github.com/yorkie-team/yorkie/pkg/splay"
+	"strings"
+
+	"github.com/yorkie-team/yorkie/pkg/document/time"
+	"github.com/yorkie-team/yorkie/pkg/log"
+)
+
+type RGATreeListNode struct {
+	indexNode *splay.Node
+	elem      Element
+
+	prev *RGATreeListNode
+	next *RGATreeListNode
+}
+
+func newRGATreeListNode(elem Element) *RGATreeListNode {
+	node := &RGATreeListNode{
+		prev: nil,
+		next: nil,
+		elem: elem,
+	}
+	node.indexNode = splay.NewNode(node)
+
+	return node
+}
+
+func newRGATreeListNodeAfter(prev *RGATreeListNode, elem Element) *RGATreeListNode {
+	newNode := newRGATreeListNode(elem)
+	prevNext := prev.next
+
+	prev.next = newNode
+	newNode.prev = prev
+	newNode.next = prevNext
+	if prevNext != nil {
+		prevNext.prev = newNode
+	}
+
+	return prev.next
+}
+
+func (n *RGATreeListNode) isDeleted() bool {
+	return n.elem.DeletedAt() != nil
+}
+
+func (n *RGATreeListNode) Element() Element {
+	return n.elem
+}
+
+func (n *RGATreeListNode) Len() int {
+	if n.isDeleted() {
+		return 0
+	}
+	return 1
+}
+
+func (n *RGATreeListNode) String() string {
+	return n.elem.Marshal()
+}
+
+type RGATreeList struct {
+	dummyHead          *RGATreeListNode
+	last               *RGATreeListNode
+	size               int
+	nodeMapByIndex     *splay.Tree
+	nodeMapByCreatedAt map[string]*RGATreeListNode
+}
+
+// NewRGATreeList creates a new instance of RGATreeList.
+func NewRGATreeList() *RGATreeList {
+	dummyValue := NewPrimitive(0, time.InitialTicket)
+	dummyValue.Delete(time.InitialTicket)
+	dummyHead := newRGATreeListNode(dummyValue)
+	nodeMapByCreatedAt := make(map[string]*RGATreeListNode)
+	nodeMapByIndex := splay.NewTree()
+
+	nodeMapByIndex.Insert(dummyHead.indexNode)
+	nodeMapByCreatedAt[dummyHead.elem.CreatedAt().Key()] = dummyHead
+
+	return &RGATreeList{
+		dummyHead:          dummyHead,
+		last:               dummyHead,
+		size:               0,
+		nodeMapByIndex:     nodeMapByIndex,
+		nodeMapByCreatedAt: nodeMapByCreatedAt,
+	}
+}
+
+// Marshal returns the JSON encoding of this RGATreeList.
+func (a *RGATreeList) Marshal() string {
+	sb := strings.Builder{}
+	sb.WriteString("[")
+
+	current := a.dummyHead.next
+	for {
+		if current == nil {
+			break
+		}
+
+		if !current.isDeleted() {
+			sb.WriteString(current.elem.Marshal())
+			if current != a.last {
+				sb.WriteString(",")
+			}
+		}
+
+		current = current.next
+	}
+
+	sb.WriteString("]")
+
+	return sb.String()
+}
+
+// Add adds the given element at the last.
+func (a *RGATreeList) Add(elem Element) {
+	a.insertAfter(a.last, elem)
+}
+
+// Nodes returns an array of elements contained in this RGATreeList.
+// TODO If we encounter performance issues, we need to replace this with other solution.
+func (a *RGATreeList) Nodes() []*RGATreeListNode {
+	var nodes []*RGATreeListNode
+	current := a.dummyHead.next
+	for {
+		if current == nil {
+			break
+		}
+		nodes = append(nodes, current)
+		current = current.next
+	}
+
+	return nodes
+}
+
+// LastCreatedAt returns the creation time of last elements.
+func (a *RGATreeList) LastCreatedAt() *time.Ticket {
+	return a.last.elem.CreatedAt()
+}
+
+// InsertAfter inserts the given element after the given previous element.
+func (a *RGATreeList) InsertAfter(prevCreatedAt *time.Ticket, elem Element) {
+	prevNode := a.findByCreatedAt(prevCreatedAt, elem.CreatedAt())
+	a.insertAfter(prevNode, elem)
+}
+
+// Get returns the element of the given index.
+func (a *RGATreeList) Get(idx int) *RGATreeListNode {
+	splayNode, offset := a.nodeMapByIndex.Find(idx)
+	node := splayNode.Value().(*RGATreeListNode)
+
+	if idx == 0 && splayNode == a.dummyHead.indexNode {
+		for {
+			node = node.next
+			if !node.isDeleted() {
+				break
+			}
+		}
+	} else if offset > 0 {
+		for {
+			node = node.next
+			if !node.isDeleted() {
+				break
+			}
+		}
+	}
+
+	return node
+}
+
+// RemoveByCreatedAt removes the given element.
+func (a *RGATreeList) RemoveByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) *RGATreeListNode {
+	node, ok := a.nodeMapByCreatedAt[createdAt.Key()]
+	if !ok {
+		log.Logger.Fatalf(
+			"fail to find the given createdAt: %s",
+			createdAt.Key(),
+		)
+
+	}
+
+	if node.elem.Delete(deletedAt) {
+		a.nodeMapByIndex.Splay(node.indexNode)
+		a.size--
+	}
+	return node
+}
+
+// Len returns length of this RGATreeList.
+func (a *RGATreeList) Len() int {
+	return a.size
+}
+
+func (a *RGATreeList) findByCreatedAt(prevCreatedAt *time.Ticket, createdAt *time.Ticket) *RGATreeListNode {
+	node, ok := a.nodeMapByCreatedAt[prevCreatedAt.Key()]
+	if !ok {
+		log.Logger.Fatalf(
+			"fail to find the given prevCreatedAt: %s",
+			prevCreatedAt.Key(),
+		)
+		return nil
+	}
+
+	for node.next != nil && node.next.elem.CreatedAt().After(createdAt) {
+		node = node.next
+	}
+
+	return node
+}
+
+func (a *RGATreeList) insertAfter(prev *RGATreeListNode, element Element) {
+	node := newRGATreeListNodeAfter(prev, element)
+	if prev == a.last {
+		a.last = node
+	}
+
+	a.nodeMapByIndex.InsertAfter(prev.indexNode, node.indexNode)
+	a.nodeMapByCreatedAt[element.CreatedAt().Key()] = node
+
+	a.size++
+}
+
+func (a *RGATreeList) AnnotatedString() string {
+	return a.nodeMapByIndex.AnnotatedString()
+}
+
+func (a *RGATreeList) Remove(idx int, deletedAt *time.Ticket) *RGATreeListNode {
+	target := a.Get(idx)
+	return a.RemoveByCreatedAt(target.elem.CreatedAt(), deletedAt)
+}
diff --git a/pkg/document/json/rht.go b/pkg/document/json/rhtpqmap.go
similarity index 68%
rename from pkg/document/json/rht.go
rename to pkg/document/json/rhtpqmap.go
index a1ce2198..c7ab5dd0 100644
--- a/pkg/document/json/rht.go
+++ b/pkg/document/json/rhtpqmap.go
@@ -55,45 +55,47 @@ func (n *RHTNode) Element() Element {
 	return n.elem
 }
 
-// RHT is replicated hash table.
-type RHT struct {
+// RHTPriorityQueueMap is replicated hash table.
+type RHTPriorityQueueMap struct {
 	nodeQueueMapByKey  map[string]*pq.PriorityQueue
 	nodeMapByCreatedAt map[string]*RHTNode
 }
 
-// NewRHT creates a new instance of RHT.
-func NewRHT() *RHT {
-	return &RHT{
+// NewRHT creates a new instance of RHTPriorityQueueMap.
+func NewRHT() *RHTPriorityQueueMap {
+	return &RHTPriorityQueueMap{
 		nodeQueueMapByKey:  make(map[string]*pq.PriorityQueue),
 		nodeMapByCreatedAt: make(map[string]*RHTNode),
 	}
 }
 
 // Get returns the value of the given key.
-func (rht *RHT) Get(key string) Element {
-	if queue, ok := rht.nodeQueueMapByKey[key]; ok {
-		node := queue.Peek().(*RHTNode)
-		if node.isDeleted() {
-			return nil
-		}
-		return node.elem
+func (rht *RHTPriorityQueueMap) Get(key string) Element {
+	queue, ok := rht.nodeQueueMapByKey[key]
+	if !ok {
+		return nil
 	}
 
-	return nil
+	node := queue.Peek().(*RHTNode)
+	if node.isDeleted() {
+		return nil
+	}
+	return node.elem
 }
 
 // Has returns whether the element exists of the given key or not.
-func (rht *RHT) Has(key string) bool {
-	if queue, ok := rht.nodeQueueMapByKey[key]; ok {
-		node := queue.Peek().(*RHTNode)
-		return node != nil && !node.isDeleted()
+func (rht *RHTPriorityQueueMap) Has(key string) bool {
+	queue, ok := rht.nodeQueueMapByKey[key]
+	if !ok {
+		return false
 	}
 
-	return false
+	node := queue.Peek().(*RHTNode)
+	return node != nil && !node.isDeleted()
 }
 
 // Set sets the value of the given key.
-func (rht *RHT) Set(k string, v Element) {
+func (rht *RHTPriorityQueueMap) Set(k string, v Element) {
 	if _, ok := rht.nodeQueueMapByKey[k]; !ok {
 		rht.nodeQueueMapByKey[k] = pq.NewPriorityQueue()
 	}
@@ -104,29 +106,32 @@ func (rht *RHT) Set(k string, v Element) {
 }
 
 // Remove removes the Element of the given key.
-func (rht *RHT) Remove(k string, deletedAt *time.Ticket) Element {
-	if queue, ok := rht.nodeQueueMapByKey[k]; ok {
-		node := queue.Peek().(*RHTNode)
-		node.Delete(deletedAt)
-		return node.elem
+func (rht *RHTPriorityQueueMap) Remove(k string, deletedAt *time.Ticket) Element {
+	queue, ok := rht.nodeQueueMapByKey[k]
+	if !ok {
+		return nil
 	}
-	return nil
+
+	node := queue.Peek().(*RHTNode)
+	node.Delete(deletedAt)
+	return node.elem
 }
 
 // RemoveByCreatedAt removes the Element of the given creation time.
-func (rht *RHT) RemoveByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) Element {
-	if node, ok := rht.nodeMapByCreatedAt[createdAt.Key()]; ok {
-		node.Delete(deletedAt)
-		return node.elem
+func (rht *RHTPriorityQueueMap) RemoveByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) Element {
+	node, ok := rht.nodeMapByCreatedAt[createdAt.Key()]
+	if !ok {
+		log.Logger.Warn("fail to find " + createdAt.Key())
+		return nil
 	}
 
-	log.Logger.Warn("fail to find " + createdAt.Key())
-	return nil
+	node.Delete(deletedAt)
+	return node.elem
 }
 
 // Elements returns a map of elements because the map easy to use for loop.
 // TODO If we encounter performance issues, we need to replace this with other solution.
-func (rht *RHT) Elements() map[string]Element {
+func (rht *RHTPriorityQueueMap) Elements() map[string]Element {
 	members := make(map[string]Element)
 	for _, queue := range rht.nodeQueueMapByKey {
 		if node := queue.Peek().(*RHTNode); !node.isDeleted() {
@@ -139,7 +144,7 @@ func (rht *RHT) Elements() map[string]Element {
 
 // AllNodes returns a map of elements because the map easy to use for loop.
 // TODO If we encounter performance issues, we need to replace this with other solution.
-func (rht *RHT) AllNodes() []*RHTNode {
+func (rht *RHTPriorityQueueMap) AllNodes() []*RHTNode {
 	var nodes []*RHTNode
 	for _, queue := range rht.nodeQueueMapByKey {
 		for _, value := range queue.Values() {
diff --git a/pkg/document/json/text.go b/pkg/document/json/text.go
index c4237e1c..193f4f9c 100644
--- a/pkg/document/json/text.go
+++ b/pkg/document/json/text.go
@@ -560,8 +560,12 @@ func (t *Text) DeletedAt() *time.Ticket {
 }
 
 // Delete deletes this Text.
-func (t *Text) Delete(deletedAt *time.Ticket) {
-	t.deletedAt = deletedAt
+func (t *Text) Delete(deletedAt *time.Ticket) bool {
+	if t.deletedAt == nil || deletedAt.After(t.deletedAt) {
+		t.deletedAt = deletedAt
+		return true
+	}
+	return false
 }
 
 // CreateRange returns pair of TextNodePos of the given integer offsets.
diff --git a/pkg/document/proxy/array_proxy.go b/pkg/document/proxy/array_proxy.go
index 39fed906..8fadac13 100644
--- a/pkg/document/proxy/array_proxy.go
+++ b/pkg/document/proxy/array_proxy.go
@@ -94,6 +94,14 @@ func (p *ArrayProxy) AddString(v string) *ArrayProxy {
 	return p
 }
 
+func (p *ArrayProxy) AddNewArray() *ArrayProxy {
+	v := p.addInternal(func(ticket *time.Ticket) json.Element {
+		return NewArrayProxy(p.context, json.NewArray(json.NewRGATreeList(), ticket))
+	})
+
+	return v.(*ArrayProxy)
+}
+
 func (p *ArrayProxy) InsertStringAfter(index int, v string) *ArrayProxy {
 	prev := p.Get(index)
 	p.insertAfterInternal(prev.CreatedAt(), func(ticket *time.Ticket) json.Element {
@@ -103,12 +111,13 @@ func (p *ArrayProxy) InsertStringAfter(index int, v string) *ArrayProxy {
 	return p
 }
 
-func (p *ArrayProxy) AddNewArray() *ArrayProxy {
-	v := p.addInternal(func(ticket *time.Ticket) json.Element {
-		return NewArrayProxy(p.context, json.NewArray(json.NewRGA(), ticket))
+func (p *ArrayProxy) InsertIntegerAfter(index int, v int) *ArrayProxy {
+	prev := p.Get(index)
+	p.insertAfterInternal(prev.CreatedAt(), func(ticket *time.Ticket) json.Element {
+		return json.NewPrimitive(v, ticket)
 	})
 
-	return v.(*ArrayProxy)
+	return p
 }
 
 func (p *ArrayProxy) Remove(idx int) json.Element {
diff --git a/pkg/document/proxy/object_proxy.go b/pkg/document/proxy/object_proxy.go
index a8dbb8f3..bea3ebc5 100644
--- a/pkg/document/proxy/object_proxy.go
+++ b/pkg/document/proxy/object_proxy.go
@@ -47,7 +47,7 @@ func (p *ObjectProxy) SetNewObject(k string) *ObjectProxy {
 
 func (p *ObjectProxy) SetNewArray(k string) *ArrayProxy {
 	v := p.setInternal(k, func(ticket *time.Ticket) json.Element {
-		return NewArrayProxy(p.context, json.NewArray(json.NewRGA(), ticket))
+		return NewArrayProxy(p.context, json.NewArray(json.NewRGATreeList(), ticket))
 	})
 
 	return v.(*ArrayProxy)
diff --git a/pkg/splay/splay.go b/pkg/splay/splay.go
index 498783a1..494cf491 100644
--- a/pkg/splay/splay.go
+++ b/pkg/splay/splay.go
@@ -136,6 +136,10 @@ func (t *Tree) Splay(node *Node) {
 			// zig-zig
 			t.rotateRight(node.parent)
 			t.rotateRight(node)
+		} else if isRightChild(node.parent) && isRightChild(node) {
+			// zig-zig
+			t.rotateLeft(node.parent)
+			t.rotateLeft(node)
 		} else {
 			// zig
 			if isLeftChild(node) {


Test patch:
diff --git a/pkg/document/document_test.go b/pkg/document/document_test.go
index 5a79c2ea..41fc2f20 100644
--- a/pkg/document/document_test.go
+++ b/pkg/document/document_test.go
@@ -18,6 +18,7 @@ package document_test
 
 import (
 	"errors"
+	"fmt"
 	"testing"
 
 	"github.com/stretchr/testify/assert"
@@ -116,23 +117,37 @@ func TestDocument(t *testing.T) {
 		doc := document.New("c1", "d1")
 
 		err := doc.Update(func(root *proxy.ObjectProxy) error {
-			root.SetNewArray("k1").AddString("1").AddString("2").AddString("3")
+			root.SetNewArray("k1").AddInteger(1).AddInteger(2).AddInteger(3)
 			assert.Equal(t, 3, root.GetArray("k1").Len())
-			assert.Equal(t, `{"k1":["1","2","3"]}`, root.Marshal())
+			assert.Equal(t, `{"k1":[1,2,3]}`, root.Marshal())
+			assert.Equal(t, "[0,0]0[1,1]1[2,1]2[3,1]3", root.GetArray("k1").AnnotatedString())
 
 			root.GetArray("k1").Remove(1)
-			assert.Equal(t, `{"k1":["1","3"]}`, root.Marshal())
+			assert.Equal(t, `{"k1":[1,3]}`, root.Marshal())
 			assert.Equal(t, 2, root.GetArray("k1").Len())
+			assert.Equal(t, "[0,0]0[1,1]1[2,0]2[1,1]3", root.GetArray("k1").AnnotatedString())
 
-			root.GetArray("k1").InsertStringAfter(0, "2")
-			assert.Equal(t, `{"k1":["1","2","3"]}`, root.Marshal())
+			root.GetArray("k1").InsertIntegerAfter(0, 2)
+			assert.Equal(t, `{"k1":[1,2,3]}`, root.Marshal())
 			assert.Equal(t, 3, root.GetArray("k1").Len())
+			assert.Equal(t, "[0,0]0[1,1]1[3,1]2[1,0]2[1,1]3", root.GetArray("k1").AnnotatedString())
 
-			root.GetArray("k1").InsertStringAfter(2, "4")
-			assert.Equal(t, `{"k1":["1","2","3","4"]}`, root.Marshal())
+			root.GetArray("k1").InsertIntegerAfter(2, 4)
+			assert.Equal(t, `{"k1":[1,2,3,4]}`, root.Marshal())
 			assert.Equal(t, 4, root.GetArray("k1").Len())
+			assert.Equal(t, "[0,0]0[1,1]1[2,1]2[2,0]2[3,1]3[4,1]4", root.GetArray("k1").AnnotatedString())
+
+			for i := 0; i < root.GetArray("k1").Len(); i++ {
+				assert.Equal(
+					t,
+					fmt.Sprintf("%d", i + 1),
+					root.GetArray("k1").Get(i).Marshal(),
+				)
+			}
+
 			return nil
 		})
+
 		assert.NoError(t, err)
 	})
 
diff --git a/pkg/document/json/array_test.go b/pkg/document/json/array_test.go
index 3aaa3a94..e89d071f 100644
--- a/pkg/document/json/array_test.go
+++ b/pkg/document/json/array_test.go
@@ -27,7 +27,7 @@ import (
 
 func TestArray(t *testing.T) {
 	t.Run("marshal test", func(t *testing.T) {
-		a := json.NewArray(json.NewRGA(), time.InitialTicket)
+		a := json.NewArray(json.NewRGATreeList(), time.InitialTicket)
 
 		a.Add(json.NewPrimitive("1", time.InitialTicket))
 		assert.Equal(t, `["1"]`, a.Marshal())