2 files changed, 139 insertions, 4 deletions

diff --git a/worker/types/thread.go b/worker/types/thread.go
index 4bcd843a..bfe3edc7 100644
--- a/worker/types/thread.go
+++ b/worker/types/thread.go
@@ -19,21 +19,29 @@ type Thread struct {
 	Deleted bool // if this flag is set the message was deleted
 }
 
+// AddChild appends the child node at the end of the existing children of t.
 func (t *Thread) AddChild(child *Thread) {
-	t.InsertCmp(child, func(child, iter *Thread) bool { return true })
+	t.InsertCmp(child, func(_, _ *Thread) bool { return true })
 }
 
+// OrderedInsert inserts the child node in ascending order among the existing
+// children based on their respective UIDs.
 func (t *Thread) OrderedInsert(child *Thread) {
 	t.InsertCmp(child, func(child, iter *Thread) bool { return child.Uid > iter.Uid })
 }
 
-func (t *Thread) InsertCmp(child *Thread, cmp func(*Thread, *Thread) bool) {
+// InsertCmp inserts child as a child node into t in ascending order. The
+// ascending order is determined by the bigger function that compares the child
+// with the existing children. It should return true when the child is bigger
+// than the other, and false otherwise.
+func (t *Thread) InsertCmp(child *Thread, bigger func(*Thread, *Thread) bool) {
 	if t.FirstChild == nil {
 		t.FirstChild = child
 	} else {
-		start := &Thread{Uid: t.FirstChild.Uid, NextSibling: t.FirstChild}
+		start := &Thread{NextSibling: t.FirstChild}
 		var iter *Thread
-		for iter = start; iter.NextSibling != nil && cmp(child, iter); iter = iter.NextSibling {
+		for iter = start; iter.NextSibling != nil &&
+			bigger(child, iter.NextSibling); iter = iter.NextSibling {
 		}
 		child.NextSibling = iter.NextSibling
 		iter.NextSibling = child
diff --git a/worker/types/thread_test.go b/worker/types/thread_test.go
index b3c39322..669803d8 100644
--- a/worker/types/thread_test.go
+++ b/worker/types/thread_test.go
@@ -103,3 +103,130 @@ func TestNewWalk(t *testing.T) {
 		return nil
 	})
 }
+
+func uidSeq(tree *Thread) string {
+	var seq []string
+	tree.Walk(func(t *Thread, _ int, _ error) error {
+		seq = append(seq, fmt.Sprintf("%d", t.Uid))
+		return nil
+	})
+	return strings.Join(seq, ".")
+}
+
+func TestThread_AddChild(t *testing.T) {
+	tests := []struct {
+		name string
+		seq  []int
+		want string
+	}{
+		{
+			name: "ascending",
+			seq:  []int{1, 2, 3, 4, 5, 6},
+			want: "0.1.2.3.4.5.6",
+		},
+		{
+			name: "descending",
+			seq:  []int{6, 5, 4, 3, 2, 1},
+			want: "0.6.5.4.3.2.1",
+		},
+	}
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			tree := &Thread{Uid: 0}
+			for _, i := range test.seq {
+				tree.AddChild(&Thread{Uid: uint32(i)})
+			}
+			if got := uidSeq(tree); got != test.want {
+				t.Errorf("got: %s, but wanted: %s", got,
+					test.want)
+			}
+		})
+	}
+}
+
+func TestThread_OrderedInsert(t *testing.T) {
+	tests := []struct {
+		name string
+		seq  []int
+		want string
+	}{
+		{
+			name: "ascending",
+			seq:  []int{1, 2, 3, 4, 5, 6},
+			want: "0.1.2.3.4.5.6",
+		},
+		{
+			name: "descending",
+			seq:  []int{6, 5, 4, 3, 2, 1},
+			want: "0.1.2.3.4.5.6",
+		},
+		{
+			name: "mixed",
+			seq:  []int{2, 1, 6, 3, 4, 5},
+			want: "0.1.2.3.4.5.6",
+		},
+	}
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			tree := &Thread{Uid: 0}
+			for _, i := range test.seq {
+				tree.OrderedInsert(&Thread{Uid: uint32(i)})
+			}
+			if got := uidSeq(tree); got != test.want {
+				t.Errorf("got: %s, but wanted: %s", got,
+					test.want)
+			}
+		})
+	}
+}
+
+func TestThread_InsertCmd(t *testing.T) {
+	tests := []struct {
+		name string
+		seq  []int
+		want string
+	}{
+		{
+			name: "ascending",
+			seq:  []int{1, 2, 3, 4, 5, 6},
+			want: "0.6.4.2.1.3.5",
+		},
+		{
+			name: "descending",
+			seq:  []int{6, 5, 4, 3, 2, 1},
+			want: "0.6.4.2.1.3.5",
+		},
+		{
+			name: "mixed",
+			seq:  []int{2, 1, 6, 3, 4, 5},
+			want: "0.6.4.2.1.3.5",
+		},
+	}
+	sortMap := map[uint32]int{
+		uint32(6): 1,
+		uint32(4): 2,
+		uint32(2): 3,
+		uint32(1): 4,
+		uint32(3): 5,
+		uint32(5): 6,
+	}
+
+	// bigger compares the new child with the next node and returns true if
+	// the child node is bigger and false otherwise.
+	bigger := func(newNode, nextChild *Thread) bool {
+		return sortMap[newNode.Uid] > sortMap[nextChild.Uid]
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			tree := &Thread{Uid: 0}
+			for _, i := range test.seq {
+				tree.InsertCmp(&Thread{Uid: uint32(i)}, bigger)
+			}
+			if got := uidSeq(tree); got != test.want {
+				t.Errorf("got: %s, but wanted: %s", got,
+					test.want)
+			}
+		})
+	}
+}