From 76c10dada86fd807d36ccafca393e945e381696a Mon Sep 17 00:00:00 2001
From: Eric Wong <e@80x24.org>
Date: Sat, 12 Nov 2016 02:13:42 +0000
Subject: initial

---
 lib/msgthr.rb           | 91 +++++++++++++++++++++++++++++++++++++++++++++++++
 lib/msgthr/container.rb | 73 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 164 insertions(+)
 create mode 100644 lib/msgthr.rb
 create mode 100644 lib/msgthr/container.rb

(limited to 'lib')

diff --git a/lib/msgthr.rb b/lib/msgthr.rb
new file mode 100644
index 0000000..f8b5896
--- /dev/null
+++ b/lib/msgthr.rb
@@ -0,0 +1,91 @@
+# Copyright (C) 2016 all contributors <msgthr-public@80x24.org>
+# License: GPL-2.0+ <https://www.gnu.org/licenses/gpl-2.0.txt>
+
+# Non-recursive, container-agnostic message threading.
+class Msgthr
+
+  # an Array of root (parent-less) messages, only populated after
+  # calling Msgthr#thread!
+  attr_reader :rootset
+
+  # Initialize a Msgthr object
+  def initialize
+    @id_table = {}
+    @rootset = []
+  end
+
+  # Clear internal data structures to save memory and prepare for reuse
+  def clear
+    @rootset.clear
+    @id_table.clear
+  end
+
+  # Threads the message
+  # This does not sort
+  def thread!
+    ret = @rootset
+    @id_table.each_value { |cont| ret << cont if cont.parent.nil? }.clear
+    ret
+  end
+
+  def order!
+    yield @rootset
+    @rootset.each { |cont| cont.order! { |children| yield(children) } }
+  end
+
+  # non-recursively walk a thread
+  def walk_thread
+    i = -1
+    q = @rootset.map { |cont| [ 0, cont, i += 1 ] }
+    while tmp = q.shift
+      level, cont, idx = tmp
+      yield(level, cont, idx)
+      level += 1
+      i = -1
+      q = cont.children.map { |cld| [ level, cld, i += 1 ] }.concat(q)
+    end
+  end
+
+  # Adds a message to prepare a Msgthr object for threading.
+  #
+  # * +mid+ is a unique identifier for the message in a given thread.
+  #
+  # * +refs+ should be an Array of unique identifiers.  For mail and
+  #   news messages, this is usually the parsed result of the
+  #   "References:" header.  Order should be oldest to newest
+  #   in terms of ancestry, with the last element being the
+  #   immediate parent of the given message.
+  #
+  #   This is +nil+ for messages with no parent.
+  #
+  # * +msg+ is an opaque object which typically contains a
+  #   Mail or Tmail object for handling mail.
+  #
+  # If +mid+ is a String, it is recommended to freeze the string before
+  # calling this method to avoid wasting memory on hash keys.
+  def add(mid, refs, msg)
+    cur = @id_table[mid] ||= Msgthr::Container.new(mid)
+    cur.msg = msg
+    refs or return
+
+    # n.b. centralized messaging systems (e.g. forums) do not need
+    # multiple References:, only decentralized systems need it to
+    # tolerate missing messages
+    prev = nil
+    refs.each do |ref|
+      cont = @id_table[ref] ||= Msgthr::Container.new(ref)
+
+      # link refs together in order implied,
+      # but do not change existing links or loop
+      if prev && !cont.parent && !cont.has_descendent(prev)
+        prev.add_child(cont)
+      end
+      prev = cont
+    end
+
+    # set parent of this message to be the last element in refs
+    prev.add_child(cur) if prev
+  end
+end
+
+require_relative 'msgthr/container'
diff --git a/lib/msgthr/container.rb b/lib/msgthr/container.rb
new file mode 100644
index 0000000..30f6775
--- /dev/null
+++ b/lib/msgthr/container.rb
@@ -0,0 +1,73 @@
+# Copyright (C) 2016 all contributors <msgthr-public@80x24.org>
+# License: GPL-2.0+ <https://www.gnu.org/licenses/gpl-2.0.txt>
+
+# An internal container class, this is exposed for sorting APIs
+# but should not be initialized in your own code.
+class Msgthr::Container
+
+  # Unique message identifier, typically the Message-Id header for mail
+  # and news messages.  This may be any hashable object, Integer values
+  # are allowed and will not be coerced to string values.
+  attr_reader :mid
+
+  # Opaque data pointer, may be used by the user for any purpose.
+  # This may be +nil+ to denote missing (aka "ghost") messages.
+  attr_accessor :msg
+
+  attr_accessor :children # :nodoc:
+  attr_accessor :parent # :nodoc:
+
+  def initialize(mid) # :nodoc:
+    @mid = mid
+    @children = {} # becomes an Array after order!
+    @parent = nil
+    @msg = nil # opaque
+  end
+
+  # returns the topmost message container with an opaque message pointer
+  # in it.  This may be +nil+ if none are available.
+  def topmost
+    q = [ self ]
+    while cont = q.shift
+      return cont if cont.msg
+      q.concat(cont.children.values)
+    end
+    nil
+  end
+
+  def add_child(child) # :nodoc:
+    raise 'cannot become child of self' if child == self
+    cid = child.mid
+
+    # reparenting:
+    parent = child.parent and parent.children.delete(cid)
+
+    @children[cid] = child
+    child.parent = self
+  end
+
+  def has_descendent(child) # :nodoc:
+    seen = Hash.new(0)
+    while child
+      return true if self == child || (seen[child] += 1) != 0
+      child = child.parent
+    end
+    false
+  end
+
+  def order! # :nodoc:
+    seen = { @mid => true }
+    q = [ self ]
+    while cur = q.shift
+      c = []
+      cur.children.each do |cmid, cont|
+        next if seen[cmid]
+        c << cont
+        seen[cmid] = true
+      end.clear
+      yield(c) if c.size > 1
+      cur.children = c
+      q.concat(c)
+    end
+  end
+end
-- 
cgit v1.2.3-24-ge0c7