MBOX-Line: From arnt at gulbrandsen.priv.no  Sat Apr  1 00:50:05 2006
To: imap-protocol@u.washington.edu
From: Arnt Gulbrandsen <arnt@gulbrandsen.priv.no>
Date: Fri Jun  8 12:34:37 2018
Subject: [Imap-protocol] Thread extension
In-Reply-To: <1143843283.3985.18.camel@hurina>
References: <1143819932.8744.163.camel@localhost.localdomain>
	<Pine.OSX.4.64.0603310950110.26204@pangtzu.panda.com>
	<1143843283.3985.18.camel@hurina>
Message-ID: <3qTXSmifRKnU9Fm0eQf0og.md5@libertango.oryx.com>

I wrote this sort of code six years ago, for an offline reader. I 
remember mrc telling me it was difficult, and then when I did it it was 
not much more than 400 lines of code.

First, you need some threading code. The algorithm I used originally 
came from trn, I think, although I pinched it from a friend of mine.

Once you have your threading algorithm (maybe half of my code back 
then), you've two options for persistence:

1. Store everything. Use something like the THREAD=REFERENCES algorithm, 
but leaving out steps 3 and 5, and make the main data structure 
persistent. This is what I did in 2000.

2. Just store thread membership, not position. This is simpler. Make 
your persistent data structure store a thread ID (e.g. an integer) and 
the messages it has seen belonging to that thread. It should be able to 
find the thread ID for a message-id quickly, and find all messages for 
a thread ID. Updating this structure at injection time is easy. At read 
time, you have to determine the detailed relationships within the 
thread.

Arnt

