Ternary Trees

Inspired by an article in Dr. Dobb's Journal, April 1998.

/* insert(Characters, Tree0, Tree) is true if Tree is the result of        */
/*   inserting the Characters in the ternary search tree Tree0.            */
insert([], void, tree(0,void,void,void)):-!.
insert([], tree(0,Lo,Eq,Hi), tree(0,Lo,Eq,Hi)):-!.
insert([X|Xs], void, tree(X,void,Eq,void)):-!, 
  insert(Xs, void, Eq).
insert([X|Xs], tree(C,Lo,Eq,Hi), tree(C,Lo,Eq,Hi1)):-
  X > C, !,
  insert([X|Xs], Hi, Hi1).
insert([X|Xs], tree(X,Lo,Eq,Hi), tree(X,Lo,Eq1,Hi)):-!, 
  insert(Xs, Eq, Eq1).
insert(Xs, tree(C,Lo,Eq,Hi), tree(C,Lo1,Eq,Hi)):-
  insert(Xs, Lo, Lo1).

/* search(Characters, Tree) is true if the Characters are contained in the */
/*   ternary search tree Tree.                                             */
search([], tree(0,_,_,_)):-!.
search([X|Xs], tree(C,_,_,Hi)):-
  X > C, !,
  search([X|Xs], Hi).
search([X|Xs], tree(X,_,Eq,_)):-!, 
  search(Xs, Eq).
search(Xs, tree(_,Lo,_,_)):-
  search(Xs, Lo).

/*
 * Note: The following predicates use non-standard LPA Win-Prolog strings
 */

/* strings_tree(Strings, Tree) is true if Tree is the ternary search tree  */
/*   resulting from inserting the Strings in a void ternary search tree.   */
strings_tree(Strings, Tree):-
  strings_tree_1(Strings, void, Tree).

strings_tree_1([], Tree, Tree).
strings_tree_1([String|Strings], Tree0, Tree):-
  string_chars(String, Chars),
  insert(Chars, Tree0, Tree1),
  strings_tree_1(Strings, Tree1, Tree).

/* tree_strings(Tree, Strings) is true if the list Strings contains the    */
/*   strings in the ternary search tree Tree sorted in ascending order of  */
/*   sequence.                                                             */
tree_strings(Tree, Strings):-
  tree_strings_1(Tree, [], [], Strings0),
  reverse(Strings0, Strings).

tree_strings_1(void, _, Strings, Strings).
tree_strings_1(tree(C,Lo,Eq,Hi), Chars, Strings0, Strings):-
  tree_strings_1(Lo, Chars, Strings0, Strings1),
  tree_strings_2(C, Eq, Chars, Strings1, Strings2),
  tree_strings_1(Hi, Chars, Strings2, Strings).

tree_strings_2(0, _, Chars, Strings, [String|Strings]):-!,
  string_chars(String, Chars).
tree_strings_2(Char, Tree, Chars, Strings0, Strings):-
  append(Chars, [Char], Chars1),
  tree_strings_1(Tree, Chars1, Strings0, Strings).

/* string_sort(Strings, SortedStrings) is true if SortedStrings contains   */
/*   the strings in the list Strings sorted in ascending order of sequence.*/
/* e.g. string_sort([`pig`,`pi`,`pin`,`pip`,`pins`], Tree).                */
string_sort(Strings, SortedStrings):-
  strings_tree(Strings, Tree),
  tree_strings(Tree, SortedStrings).

LPA Index     Home Page