(** Thread Reconstruction Algorithms for JMAP.
    
    This module implements various email threading algorithms used to group related
    emails into conversations. Supports both standard threading (RFC 5256) and
    custom algorithms for reconstructing thread relationships from email headers.
    
    Threading algorithms analyze Message-ID, References, and In-Reply-To headers
    to determine which emails belong in the same conversation thread.
    
    @see <https://www.rfc-editor.org/rfc/rfc5256.html> RFC 5256: Threading algorithms
    @see <https://www.rfc-editor.org/rfc/rfc8621.html#section-3> RFC 8621 Section 3: Threads
*)

(* Remove open statement to avoid circular dependency *)

(** Thread reconstruction result containing grouped emails *)
type thread_group = {
  thread_id : Jmap.Id.t;
  (** Unique identifier for this thread *)
  
  email_ids : Jmap.Id.t list;
  (** List of email IDs in this thread, ordered by relationship *)
  
  root_email_id : Jmap.Id.t option;
  (** ID of the root email that started this thread *)
  
  last_updated : Jmap.Date.t;
  (** Timestamp of the most recent email in the thread *)
}

(** Thread relationship information for an email *)
type email_relationship = {
  email_id : Jmap.Id.t;
  (** The email's unique identifier *)
  
  message_id : string option;
  (** The email's Message-ID header value *)
  
  in_reply_to : string option;
  (** The In-Reply-To header value indicating parent message *)
  
  references : string list;
  (** List of Message-IDs from References header *)
  
  subject : string;
  (** Normalized subject for subject-based threading *)
  
  date : Jmap.Date.t;
  (** Email's date for chronological ordering *)
}

(** Threading algorithm type *)
type algorithm = [
  | `RFC5256_REFERENCES
  (** Standard REFERENCES algorithm from RFC 5256 *)
  
  | `RFC5256_ORDEREDSUBJECT  
  (** Standard ORDEREDSUBJECT algorithm from RFC 5256 *)
  
  | `HYBRID
  (** Hybrid algorithm combining references and subject matching *)
  
  | `CONVERSATION
  (** Gmail-style conversation threading *)
]

(** {1 Core Threading Functions} *)

(** Extract email relationship information from an Email object.
    
    Parses the email's headers to extract Message-ID, In-Reply-To, References,
    and other fields needed for threading algorithms.
    
    @param email The email to analyze
    @return Relationship information for threading *)
val extract_relationships : Jmap_email.Email.Email.t -> email_relationship

(** Build a thread group from a list of related emails.
    
    Takes emails that have been determined to belong to the same thread and
    organizes them into a thread group with proper ordering.
    
    @param emails List of related emails
    @return Thread group containing the emails in conversation order *)
val build_thread_group : Jmap_email.Email.Email.t list -> thread_group

(** {1 Threading Algorithms} *)

(** Reconstruct threads using the REFERENCES algorithm (RFC 5256).
    
    This is the standard threading algorithm that uses Message-ID, In-Reply-To,
    and References headers to build a tree of related messages.
    
    @param emails List of emails to thread
    @return List of thread groups *)
val thread_by_references : Jmap_email.Email.Email.t list -> thread_group list

(** Reconstruct threads using the ORDEREDSUBJECT algorithm (RFC 5256).
    
    Groups emails by normalized subject line, then orders them chronologically.
    Less accurate than REFERENCES but works when headers are missing.
    
    @param emails List of emails to thread  
    @return List of thread groups *)
val thread_by_ordered_subject : Jmap_email.Email.Email.t list -> thread_group list

(** Reconstruct threads using a hybrid algorithm.
    
    Combines REFERENCES and subject-based threading. First attempts to thread
    by references, then groups orphaned messages by subject similarity.
    
    @param emails List of emails to thread
    @return List of thread groups *)
val thread_hybrid : Jmap_email.Email.Email.t list -> thread_group list

(** Reconstruct threads using conversation-style grouping.
    
    Similar to Gmail's conversation view - aggressively groups emails that
    appear to be part of the same discussion, even with broken threading.
    
    @param emails List of emails to thread
    @return List of thread groups *)
val thread_conversations : Jmap_email.Email.Email.t list -> thread_group list

(** Apply the specified threading algorithm to a list of emails.
    
    @param algorithm The threading algorithm to use
    @param emails List of emails to thread
    @return List of thread groups *)
val apply_algorithm : algorithm -> Jmap_email.Email.Email.t list -> thread_group list

(** {1 Thread Relationship Management} *)

(** Thread relationship graph for managing conversation structure *)
module ThreadGraph : sig
  (** Thread graph type maintaining email relationships *)
  type t
  
  (** Create an empty thread graph.
      @return New empty graph *)
  val create : unit -> t
  
  (** Add an email to the thread graph.
      
      Analyzes the email's headers and adds it to the appropriate position
      in the conversation tree based on its relationships.
      
      @param t The thread graph
      @param email The email to add
      @return Updated thread graph *)
  val add_email : t -> Jmap_email.Email.Email.t -> t
  
  (** Remove an email from the thread graph.
      
      @param t The thread graph
      @param email_id The ID of the email to remove
      @return Updated thread graph *)
  val remove_email : t -> Jmap.Id.t -> t
  
  (** Find the thread containing a specific email.
      
      @param t The thread graph
      @param email_id The email ID to search for
      @return Thread ID if found *)
  val find_thread : t -> Jmap.Id.t -> Jmap.Id.t option
  
  (** Get all emails in a specific thread.
      
      @param t The thread graph
      @param thread_id The thread ID
      @return List of email IDs in conversation order *)
  val get_thread_emails : t -> Jmap.Id.t -> Jmap.Id.t list
  
  (** Get all threads in the graph.
      
      @param t The thread graph
      @return List of all thread groups *)
  val get_all_threads : t -> thread_group list
  
  (** Merge two threads into one.
      
      Used when discovering that two apparently separate threads are actually
      part of the same conversation.
      
      @param t The thread graph
      @param thread1 First thread ID
      @param thread2 Second thread ID
      @return Updated graph with merged threads *)
  val merge_threads : t -> Jmap.Id.t -> Jmap.Id.t -> t
  
  (** Split a thread into two separate threads.
      
      Used when determining that emails were incorrectly grouped together.
      
      @param t The thread graph
      @param thread_id Thread to split
      @param split_point Email ID where split should occur
      @return Updated graph with split threads *)
  val split_thread : t -> Jmap.Id.t -> Jmap.Id.t -> t
  
  (** Recalculate thread relationships.
      
      Re-runs the threading algorithm on all emails in the graph, useful after
      bulk operations or when threading rules change.
      
      @param t The thread graph
      @param algorithm Algorithm to use for recalculation
      @return Updated graph with recalculated threads *)
  val recalculate : t -> algorithm -> t
end

(** {1 Utility Functions} *)

(** Normalize a subject line for threading comparison.
    
    Removes "Re:", "Fwd:", and other prefixes, normalizes whitespace, and
    converts to a canonical form for comparison.
    
    @param subject The subject line to normalize
    @return Normalized subject string *)
val normalize_subject : string -> string

(** Check if two emails appear to be related based on headers.
    
    Examines Message-ID, References, and In-Reply-To headers to determine
    if emails are part of the same conversation.
    
    @param email1 First email to compare
    @param email2 Second email to compare
    @return true if emails appear related *)
val are_related : Jmap_email.Email.Email.t -> Jmap_email.Email.Email.t -> bool

(** Sort emails within a thread by conversation order.
    
    Orders emails based on their relationships and timestamps to create
    a natural reading order for the conversation.
    
    @param emails List of emails in the same thread
    @return Emails sorted in conversation order *)
val sort_thread_emails : Jmap_email.Email.Email.t list -> Jmap_email.Email.Email.t list

(** Calculate threading statistics for a set of emails.
    
    @param threads List of thread groups
    @return Statistics including thread count, average thread size, etc. *)
val calculate_stats : thread_group list -> [
  | `ThreadCount of int
  | `AverageThreadSize of float
  | `LargestThread of int
  | `SingletonThreads of int
  | `MultiEmailThreads of int
]  list