NNTP News Message Tree - Felix John COLIBRI.

• abstract : how to build a tree of the NNTP News Messages. The downloaded messages are displayed in tListBox by message thread (topic), and for each thread the messages are presented in a tTreeView
  
• key words : NNTP - News Messages - newsgroups - message tree - tTreeView
  
• software used : Windows XP, Delphi 6
  
• hardware used : Pentium 2.800Mhz, 512 M memory, 140 G hard disc
  
• scope : Delphi 1 to 2006, Turbo Delphi for Windows, Kylix
  
• level : Delphi developer
  
• plan :
  
  • Displaying News Messages
    
  • Organizing Messages in a Thread
    
  • The Delphi News Message Tree
    
  • Download the Delphi Sources
    

1 - Displaying News Messages

The standard NNTP protocol allows us to retrieve the news headers before donwloading the text of the message.

The answer from such a command is one line per message, with the topic of the message (the "thread"), the user, the date etc. However this line does not directly tell the hierarchy of the messages. This paper will present a structure allowing to display the message in a hierarchical way. Obviously this services is interesting when incorporated

• in a news reader
  
• in an off-line news reader
  

2 - Organizing Messages in a Thread

2.1 - The Message Tree of a thread

And within each forum, members start new threads. In OODesign, we found, for instance:

An then other people start answering to this thread and talk to each other about this topic. When a thread is started, many people can answer. And many other can answer in turn to those "second level" messages. The result of this is a message tree

Lets take a simple example

• we start the thread aaa1

  101_aaa

• two people answer back

  101_aaa   102_aaa_bbb_2   103_aaa_bbb_3

• one person answers to the aaa_bb1

  101_aaa   102_aaa_bbb_2     104_aaa_bbb_ccc_4   103_aaa_bbb_3

• one person answers to the original message

  101_aaa   102_aaa_bbb_2     104_aaa_bbb_ccc_4   103_aaa_bbb_3   105_aaa_bbb_5

  
  

and our task is to build the tree from this sequential message list.

All messages are uniquely identified by a key. In our example, we used simple names for the hierarchy (aaa for level 0, bbb for level 1, ccc for level 3) and a sequential id (101, 102, 103 etc). Actual keys are not so simple. For instance, for the Borland forum, we have keys like

Building the tree is possible because each message header contains a list of all the keys from the thread root to the message itself. In message 104_aaa_bbb_ccc_4, for instance, we would have

which should be interpreted as:

• the message is 104_aaa_bbb_ccc_4
  
• the key of the message is <aaa_bbb_ccc_4>
  
• the branch to which the message belongs is <aaa> - <aaa_bbb_2>
  

2.2 - real live example

The original message header is the following (tabs have been replaced by new lines):

The first answer had the following keys:

and you notice that

• the first key is the message's own key
  
• the second key is the root key
  

2.3 - Parsing the Message Header

The only surprise comes from the key list, where the different keys are

• often separated by tabs
  
• sometimes separated by a space or two
  
• or not separated at all (<aaa><bbb>)
  

2.4 - The Construction Algorithm

So
    1 - sort the messages by thread
    2 - for each thread
    22 - start with the root
    22 - for each message of the thread, add the message at the bottom of its key branch

Most of the time, the thread root is the message with a thread title without "Re: " at the start. However this is not always true, and some people (or some news readers) do not systematically prepend "Re: " to an answer message. So the best test is to check the reference list: when the list contains only one key, then this message is a thread root.

The second difficulty is that the downloading of messages is performed by requesting an ID range. In our example, we downloaded ALL available OODesign messages, which started at ID 26145 (13 Jun 2006) and ended at ID 26827 (8 Dec 2006). The "Why did OOdb failed" were in the 26808..26826 ID range.

Here is a shortened dump of some headers in the 26809..26827 range:

 
26809 Why has OODB failed?       William Egge 
26810 Re: Why has OODB failed?   Michael Baytalsky 
26811 Re: Why has OODB failed?   Franz-Leo Chomse 
  
26812 Re: Why has OODB failed?   Wayne Niddery [TeamB] 
26813 Re: SmallTalk              Peter Morris 
26814 Re: Why has OODB failed?   Andreas Dorn 
26815 Re: SmallTalk              Jarle Stabell 
26816 Re: Why has OODB failed?   Wayne Niddery [TeamB] 
26817 Re: Why has OODB failed?   Bob Dawson 
26818 Onion                      Peter Morris 
26819 TTreeView.ValidateSelecti  Ricardo Villela Coppola 
26820 Re: SmallTalk              Peter Morris 
26821 Re: SmallTalk              Bart 
26822 Re: SmallTalk              Peter Morris 
26823 Re: SmallTalk              Bart 
26824 Re: Why has OODB failed?   John Herbster 
26825 Re: Why has OODB failed?   Harley Pebley 
26826 Re: Why has OODB failed?   Michael Baytalsky 
26827 Re: TTreeView.ValidateSel  Bob Dawson 

If we had requested the 26812..26827 range, we would have missed the start of the "Why OOdb" thread. The best we can do is to insert dummy entries in the tree:

2.5 - Header Surprises

Here are a couple of points:

• In our 600 entries, we found two cases where the reference list does not start at the root (entry 26279 and 26456, in our .ZIP sample file). The search for the relevant tree branch has therefore been adapted to locate the relevant entry point.
  
• in the user id and e-mail part, both elements are not always present. We event found headers without ANY user/e-mail, which totally desynchronised the whole analysis
  
• in the "database_ado" newsgroup, we also found messages answers without any reference to other thread messages (entry 56642 for instance, not in the header .ZIP)
  
• in addition (but we have not experienced this in our sample), if the WebMaster removes some entries (because of some rude words or for some other reason), the nice reference list could have holes, and finding a nice path from the root to the end of a branch could become problematic.
  

3 - The Delphi News Message Tree

3.1 - The Basic structure

Here is the UML class diagram of the thread list:

where

• the c_thread_list contains a tStringList of c_threads
  
• each c_thread contains a tStringList of c_messages
  

where

• each c_thread contains an m_c_root_message pointer
  
• each c_message_tree contains
  
  • a reference to a c_message
    
  • a m_c_child_message_list, wich is a tStringList of c_message_trees
    
  So the c_message_tree is a recursive structure
  

3.2 - The c_news_message CLASS

and

• m_id, m_user_name_and_e_mail, m_date, m_byte_count, m_line_count, m_group_ref, m_c_key_list are directly extracted from the NNTP message header
  
• m_key is the first entry in the key list (the message's own key)
  
• m_user_name and m_user_e_mail are extracted from the m_user_name_and_e_mail header field
  
• m_user_name_and_e_mail is set for the first message found with this thread title (not necessarily the root, if we start downloading in the middle of a thread)
  

3.3 - The c_news_message_tree

and:

• the f_xxx_count(), f_c_xxx(), f_index_of_xxx(), f_c_find_by_xxx(), add_xxx(), f_c_add_xxx() are our traditional tStringList encapsulation methods, which should be familiar to those who already looked at many of our other projects
  
• here is, as an example, the recursive display method which was used above to display the tree structure of the OODb thread:

  procedure c_news_message_tree.display_news_message_child_list;   procedure display_recursive(p_level: Integer;       p_c_news_message: c_news_message_tree);     var l_news_message_index: Integer;     begin       with p_c_news_message do       begin         if m_c_news_message_ref= Nil           then display(f_spaces(2+ p_level* 2)+ 'bogus')           else             with m_c_news_message_ref do               display(f_spaces(2+ p_level* 2)+ m_user_name_and_e_mail                   + ' ['+ m_id+ ']');         for l_news_message_index:= 0 to f_news_message_child_count- 1 do           display_recursive(p_level+ 1,               f_c_news_message_child(l_news_message_index));       end; // with p_c_news_message     end; // display_recursive   begin // display_news_message_child_list     display_recursive(0, Self);   end; // display_news_message_child_list

  
  

3.4 - The c_news_thread_message CLASS

and:

• the main method inserts a new message in the tree:

  procedure c_news_thread.add_news_thread_message_to_tree(     p_c_news_message: c_news_message);   procedure append_leaf_message(p_c_parent_news_message_tree: c_news_message_tree);     // ...   procedure create_initial_branch;     // ...   procedure add_the_message;     // ...   procedure add_broken_message;     // ...   begin // add_news_thread_message_to_tree     if m_c_root_news_message= Nil       then begin           // -- this is the first message with this topic           if p_c_news_message.m_c_key_list.Count> 1             then // -- if the key list contains several items (not the first),                 // -- build a bogus tree                 create_initial_branch             else m_c_root_news_message:=                 c_news_message_tree.create_news_message_tree(                     p_c_news_message.m_c_key_list[0], p_c_news_message);         end       else begin           // -- the tree has already been initialized (could be a broken tree)           // --   Insert the message in this tree           if not m_has_root_message             then add_broken_message             else // add_the_message_recursive(m_c_root_news_message, 1);                  add_the_message;         end;   end; // add_news_thread_message_to_tree

• the message is added as a leaf with:

  procedure append_leaf_message(p_c_parent_news_message_tree: c_news_message_tree);   var l_new_news_message_key: String;       l_c_new_news_message_tree: c_news_message_tree;   begin     l_new_news_message_key:= p_c_news_message.m_c_key_list[0];     l_c_new_news_message_tree:=         c_news_message_tree.create_news_message_tree(l_new_news_message_key,             p_c_news_message);     p_c_parent_news_message_tree.add_news_message_child(l_c_new_news_message_tree);   end; // append_leaf_message

• a "standard" message is inserted by walking down from the root using:

  procedure add_the_message;   var l_key_index: Integer;       l_key: String;       l_c_parent_news_message_tree, l_c_child_news_message_tree: c_news_message_tree;   begin     // -- normally [1] is the root. In some cases this is not the case     // --  => has to locate the [1] value     l_key:= p_c_news_message.m_c_key_list[1];     l_c_parent_news_message_tree:= f_c_find_in_tree(l_key);     l_key_index:= 2;     while l_key_index<= p_c_news_message.m_c_key_list.Count- 1 do     begin       l_key:= p_c_news_message.m_c_key_list[l_key_index];       l_c_child_news_message_tree:=           l_c_parent_news_message_tree.f_c_find_by_news_message_child(l_key);       if l_c_child_news_message_tree= Nil         then display_bug_stop('not_found_'+ l_key)         else l_c_parent_news_message_tree:= l_c_child_news_message_tree;       Inc(l_key_index);     end; // while l_key_index     // -- finally append the node itself     append_leaf_message(l_c_parent_news_message_tree);   end; // add_the_message

• when the first message of a thread is not the root (there are several keys in the key list), we build an initial bogus tree, and append the first message:

  procedure create_initial_branch;     // -- no root, and already keys => create a bogus tree   var l_key_index: Integer;       l_c_parent_news_message_tree,           l_c_intermediate_news_message_tree: c_news_message_tree;   begin     with p_c_news_message.m_c_key_list do     begin       // -- the (empty) root       m_c_root_news_message:=           c_news_message_tree.create_news_message_tree(Strings[1], Nil);       l_c_parent_news_message_tree:= m_c_root_news_message;       // -- now the branch of the intermediates       for l_key_index:= 2 to Count- 1 do       begin         l_c_intermediate_news_message_tree:=             c_news_message_tree.create_news_message_tree(Strings[l_key_index], Nil);         l_c_parent_news_message_tree.add_news_message_child(             l_c_intermediate_news_message_tree);         l_c_parent_news_message_tree:= l_c_intermediate_news_message_tree;       end;     end; // with p_c_news_message     // -- finally append the node itself     append_leaf_message(l_c_parent_news_message_tree);   end; // create_initial_branch

• and if we find a message which is not the first in a thread with no root, we try to append the message to a previous branch, or create a new branch if necessary:

  procedure add_broken_message;     // -- we do not have the first message. Could start in the middle     // -- of many answers     // --  => if finds an ancestor, ok, else create bogus branches   var l_key_index: Integer;       l_key: String;       l_c_parent_news_message_tree,           l_c_child_news_message_tree: c_news_message_tree;       l_intermediate_key_index: Integer;       l_c_intermediate_news_message_tree: c_news_message_tree;   begin     // -- Try to locate the [1] value     l_key:= p_c_news_message.m_c_key_list[1];     l_c_parent_news_message_tree:= f_c_find_in_tree(l_key);     if l_c_parent_news_message_tree= Nil       then begin           // -- create the branch (not tested)           create_initial_branch;         end;     // -- now, starting from the initial root, try to find the longest parent     l_key_index:= 2;     while l_key_index<= p_c_news_message.m_c_key_list.Count- 1 do     begin       l_key:= p_c_news_message.m_c_key_list[l_key_index];       l_c_child_news_message_tree:=           l_c_parent_news_message_tree.f_c_find_by_news_message_child(l_key);       if l_c_child_news_message_tree= Nil         then Break         else l_c_parent_news_message_tree:= l_c_child_news_message_tree;       Inc(l_key_index);     end; // while l_key_index     // -- if did not reach the end, create a bogus branch from the parent to the node     for l_intermediate_key_index:= l_key_index         to p_c_news_message.m_c_key_list.Count- 1 do     begin       l_key:= p_c_news_message.m_c_key_list[l_intermediate_key_index];       l_c_intermediate_news_message_tree:=           c_news_message_tree.create_news_message_tree(l_key, Nil);       l_c_parent_news_message_tree.add_news_message_child(           l_c_intermediate_news_message_tree);       l_c_parent_news_message_tree:= l_c_intermediate_news_message_tree;     end;     // -- finally append the node itself     append_leaf_message(l_c_parent_news_message_tree);   end; // add_broken_message

  To locate a key anywhere in the tree (for messages which do not start the key list at the root), we have created a special f_c_find_in_tree() method:

  function c_news_thread.f_c_find_in_tree(p_key: String): c_news_message_tree;   procedure find_in_tree_recursive(p_c_news_message_tree: c_news_message_tree);     var l_child_index: Integer;     begin       if p_c_news_message_tree= Nil         then         else           with p_c_news_message_tree do           begin             if m_name= p_key               then begin                   Result:= f_c_self;                   Exit;                 end;             for l_child_index:= 0 to f_news_message_child_count- 1 do               find_in_tree_recursive(f_c_news_message_child(l_child_index));           end;     end; // find_in_tree_recursive   begin // f_c_find_in_tree     Result:= Nil;     find_in_tree_recursive(m_c_root_news_message);   end; // f_c_find_in_tree

  
  

3.5 - The c_news_thread_list CLASS

and:

• the main method is the load_from_file PROCEDURE:

  procedure c_news_thread_list.load_from_file(p_full_file_name: String);   var l_list_index: Integer;       l_the_line: String;       l_index, l_length: Integer;   function f_extract_tab: String;     // ...   procedure extract_keys(p_c_news_message: c_news_message);     // ...   function f_extract: String;     // ...   var l_c_news_thread: c_news_thread;       l_id, l_thread_name: String;       l_name, l_date: String;       l_c_news_message: c_news_message;       l_is_first_in_thread: Boolean;   begin // load_from_file     with tStringList.Create do     begin       LoadFromFile(p_full_file_name);       for l_list_index:= 0 to Count- 1 do       begin         l_the_line:= Trim(Strings[l_list_index]);         l_index:= 1;         l_length:= Length(l_the_line);         l_id:= f_string_extract_non_blank(l_the_line, l_index);         l_thread_name:= f_extract_tab;         l_is_first_in_thread:= False;         if Copy(l_thread_name, 1, 4)= 'Re: '           then begin               System.Delete(l_thread_name, 1, 4);               l_c_news_thread:= f_c_find_by_news_thread(l_thread_name);               if l_c_news_thread= Nil                 then begin                     l_c_news_thread:= f_c_add_news_thread(l_thread_name);                     l_is_first_in_thread:= True;                   end;             end           else begin               l_c_news_thread:= f_c_find_by_news_thread(l_thread_name);               // -- should NOT find a prior element               if l_c_news_thread= Nil                 then begin                     l_c_news_thread:= f_c_add_news_thread(l_thread_name);                     l_is_first_in_thread:= True;                   end;             end;         l_name:= f_extract_tab;         l_date:= f_extract_tab;         l_c_news_message:= c_news_message.create_news_message(l_id);         with l_c_news_message do         begin           m_id:= l_id;           m_user_name_and_e_mail:= l_name;           m_date:= l_date;           extract_keys(f_c_self);           m_key:= m_c_key_list[0];           m_byte_count:= f_extract;           m_line_count:= f_extract;           m_group_ref:= f_extract;           l_index:= 1;           m_user_name:= Trim(f_string_extract_until(m_user_name_and_e_mail,               '<', l_index));           m_user_e_mail:= Copy(m_user_name_and_e_mail, l_index,               Length(m_user_name_and_e_mail)+ 1- l_index);           m_is_first_in_thread:= l_is_first_in_thread;           if m_is_first_in_thread             then l_c_news_thread.m_has_root_message:= (m_c_key_list.Count= 1);         end; // with l_c_news_message         l_c_news_thread.add_news_message(l_id, l_c_news_message);         l_c_news_thread.add_news_thread_message_to_tree(l_c_news_message);       end; // while l_list_index       Free;     end; // with tStringList   end; // load_from_file

  
  

3.6 - The complete Delphi Project

Here is a snapshot of the project, when we create the linear structure, and ask to display the messages of the OODb thread:

If we build the trees, the application displays this:

and if we look at the "treeview" tab:

I did not have the time to read the messages, but now that the tree sytem works, I am eager to look at the "Onion" thread. Just curious...

4 - Improvements to the Message Tree

We started with the linear list, and after the analysis of the key lists, we created the tree structure. We then scrapped the linear structure, only to find out that it was convenient for displaying unexpected key lists (for instance when the list does not start at the root). In addition, when we dowload the daily news, it is quite often to break into a thread started days, or even weeks before our download. In this case, building the tree does not make much sense. So we included the linear list back into the structure.

Reading and organizing the NNTP news headers is a fine exercise, but not very usefull. The whole UNIT obviously has to be grafted upon a on-line or off-line news reader. Well, the Threaded Indy News Reader presents such an on-line newsreader based on the Indy NNTP component.

5 - Download the Delphi Sources

• build_news_message_tree.zip: the project building the tree and displaying it in a tTreeView, with all the used UNITs (28 K)
  
• borland_public_delphi_oodesign.zip: the .TXT file of the message headers downloaded from the OODesign Delphi newsgroup. This is just an example, but the project can work on any similar file (31 K)
  

The .ZIP file(s) contain:

• the main program (.DPR, .DOF, .RES), the main form (.PAS, .DFM), and any other auxiliary form
  
• any .TXT for parameters, samples, test data
  
• all units (.PAS) for units
  

• are self-contained: you will not need any other product (unless expressly mentioned).
  
• for Delphi 6 projects, can be used from any folder (the pathes are RELATIVE)
  
• will not modify your PC in any way beyond the path where you placed the .ZIP (no registry changes, no path creation etc).
  

• create or select any folder of your choice
  
• unzip the downloaded file
  
• using Delphi, compile and execute
  

The Pascal code uses the Alsacian notation, which prefixes identifier by program area: K_onstant, T_ype, G_lobal, L_ocal, P_arametre, F_unction, C_lasse etc. This notation is presented in the Alsacian Notation paper.

As usual:

• please tell us at fcolibri@felix-colibri.com if you found some errors, mistakes, bugs, broken links or had some problem downloading the file. Resulting corrections will be helpful for other readers
  
• we welcome any comment, criticism, enhancement, other sources or reference suggestion. Just send an e-mail to fcolibri@felix-colibri.com.
  
• or more simply, enter your (anonymous or with your e-mail if you want an answer) comments below and clic the "send" button

  Name :
  E-mail :
  Comments * :

• and if you liked this article, talk about this site to your fellow developpers, add a link to your links page ou mention our articles in your blog or newsgroup posts when relevant. That's the way we operate: the more traffic and Google references we get, the more articles we will write.
  

6 - The author