| Am I making this too complicated? Surely every imap implementor | has faced this issue. Do people live with O(n) deletes, or | am I missing something?
Either use a Hashtable with UID as the key and sequence number as the value, or do a binary search on the seq->UID vector to lookup sequence number given a UID (you can do that given that UIDs will always appear in ascending order in the vector). You'll have to figure out which is more efficient.
But after a set-flag-delete and an expunge, I have to renumber the messages following the expunged message, right? And that's O(n) with either a Hashtable (have to change O(n) values) or a Vector (have to copy O(n) values).
Sorry I didn't make it clear before that I meant set-flag-delete + expunge. Expunges occur frequently in our environment. Maybe that's why no one runs into this issue, namely that they assume that expunges are infrequent.
- Joe
