Rework threading and add REFERENCES

* Implement a simplified version of the REFERENCES algorithm
* Remove FormatThreads function
* Instead of acting on all threads, handle each thread independently

Signed-off-by: Kevin Kuehler <keur@xcf.berkeley.edu>

3 files changed, 100 insertions, 39 deletions

diff --git a/worker/imap/open.go b/worker/imap/open.go
index bdb794b..1152887 100644
--- a/worker/imap/open.go
+++ b/worker/imap/open.go
@@ -64,18 +64,23 @@ func (imapw *IMAPWorker) handleDirectoryThreaded(
 			Error:   err,
 		}, nil)
 	} else {
-		aercThreads, count := convertThreads(threads)
+		root := &types.Thread{
+			Uid:   0,
+			Dummy: true,
+		}
+		aercThreads, count := convertThreads(threads, root)
+		root.Children = aercThreads
 		imapw.seqMap = make([]uint32, count)
 		imapw.worker.PostMessage(&types.DirectoryThreaded{
-			Message: types.RespondTo(msg),
-			Threads: aercThreads,
+			Message:    types.RespondTo(msg),
+			ThreadRoot: root,
 		}, nil)
 		imapw.worker.PostMessage(&types.Done{types.RespondTo(msg)}, nil)
 	}
 }
 
 // This sucks... TODO: find a better way to do this.
-func convertThreads(threads []*sortthread.Thread) ([]*types.Thread, int) {
+func convertThreads(threads []*sortthread.Thread, parent *types.Thread) ([]*types.Thread, int) {
 	if threads == nil {
 		return nil, 0
 	}
@@ -84,11 +89,13 @@ func convertThreads(threads []*sortthread.Thread) ([]*types.Thread, int) {
 
 	for i := 0; i < len(threads); i++ {
 		t := threads[i]
-		children, childCount := convertThreads(t.Children)
 		conv[i] = &types.Thread{
-			Uid:      t.Id,
-			Children: children,
+			Uid:   t.Id,
+			Dummy: false,
 		}
+		conv[i].Parent = parent
+		children, childCount := convertThreads(t.Children, conv[i])
+		conv[i].Children = children
 		count += childCount + 1
 	}
 	return conv, count
diff --git a/worker/types/messages.go b/worker/types/messages.go
index 0b9dc6e..d5f2484 100644
--- a/worker/types/messages.go
+++ b/worker/types/messages.go
@@ -159,7 +159,7 @@ type DirectoryContents struct {
 
 type DirectoryThreaded struct {
 	Message
-	Threads []*Thread
+	ThreadRoot *Thread
 }
 
 type SearchResults struct {
diff --git a/worker/types/thread.go b/worker/types/thread.go
index a51a5c4..51cd599 100644
--- a/worker/types/thread.go
+++ b/worker/types/thread.go
@@ -3,44 +3,98 @@ package types
 type Thread struct {
 	Uid      uint32
 	Children []*Thread
+	Parent   *Thread
+	Dummy    bool
 }
 
-func (t *Thread) FormatThread(cb func(*Thread, []rune) bool) {
-	cb(t, []rune{})
-	walkThreads(t.Children, []rune{}, cb)
+func (t *Thread) Find(uid uint32) *Thread {
+	if t.Uid == uid && !t.Dummy {
+		return t
+	}
+
+	for _, child := range t.Children {
+		if needle := child.Find(uid); needle != nil {
+			return needle
+		}
+	}
+
+	return nil
 }
 
-func walkThreads(threads []*Thread, threadFmt []rune,
-	cb func(*Thread, []rune) bool) {
-	if threads == nil {
-		return
-	}
-
-	var (
-		indent          []rune = []rune{'\u0020', '\u0020'}
-		indentConnected []rune = []rune{'\u2502', '\u0020'}
-		arrow           []rune = []rune{'\u251c', '\u2500', '\u003e'}
-		arrowConnected  []rune = []rune{'\u2514', '\u2500', '\u003e'}
-
-		threadPrefix          []rune = append(threadFmt, arrow...)
-		threadPrefixConnected []rune = append(threadFmt, arrowConnected...)
-		nextThread            []rune = append(threadFmt, indent...)
-		nextThreadConnected   []rune = append(threadFmt, indentConnected...)
-	)
-
-	for i := len(threads) - 1; i >= 0; i-- {
-		t := threads[i]
-		if i > 0 && len(threads) > 1 {
-			if cb(t, threadPrefix) {
-				return
-			}
-			walkThreads(t.Children, nextThreadConnected, cb)
+func (t *Thread) Traverse(dummies bool, cb func(*Thread) bool) {
+	if dummies || !t.Dummy {
+		if cb(t) {
+			return
+		}
+	}
+
+	threads := t.Children
+	for i := 0; i < len(threads); i++ {
+		child := threads[i]
+		child.Traverse(dummies, cb)
+	}
+}
+
+var (
+	BINDENT []rune = []rune{'\u0020', '\u0020'}
+	CINDENT []rune = []rune{'\u2502', '\u0020'}
+	LARROW  []rune = []rune{'\u2514', '\u2500', '\u003e'}
+	TARROW  []rune = []rune{'\u252c', '\u2500', '\u003e'}
+	IARROW  []rune = []rune{'\u251c', '\u2500', '\u003e'}
+)
+
+func (t *Thread) isRoot() bool {
+	return t.Dummy && t.Parent == nil
+}
+
+func (t *Thread) isDummyRoot() bool {
+	p := t
+	for p.Dummy {
+		if p.isRoot() {
+			return true
+		}
+		p = p.Parent
+	}
+	return false
+}
+
+func (t *Thread) DrawThread() []rune {
+	var line []rune
+	if t.Parent.isRoot() {
+		return line
+	}
+
+	children := t.Parent.Children
+	if t.Parent.Dummy {
+		children := t.Parent.Children
+		if len(children) > 1 && t == children[0] {
+			line = TARROW
+		} else if len(children) > 1 && t != children[len(children)-1] {
+			line = IARROW
+		} else if len(children) > 1 {
+			line = LARROW
+		}
+	} else {
+		if len(children) > 1 && t != children[len(children)-1] {
+			line = IARROW
 		} else {
-			if cb(t, threadPrefixConnected) {
-				return
+			line = LARROW
+		}
+	}
+
+	p := t.Parent
+
+	for p != nil && !p.Parent.isDummyRoot() {
+		if !p.Dummy {
+			children := p.Parent.Children
+			if len(children) > 1 && p != children[len(children)-1] {
+				line = append(CINDENT, line...)
+			} else {
+				line = append(BINDENT, line...)
 			}
-			walkThreads(t.Children, nextThread, cb)
 		}
+		p = p.Parent
 	}
 
+	return line
 }