home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / prolog / 2280 < prev    next >
Encoding:
Text File  |  1992-12-21  |  12.0 KB  |  366 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!brunix!brunix!mj
  3. From: mj@cs.brown.edu (Mark Johnson)
  4. Subject: Re: Looking for clause or n-ary tree indexing code
  5. Message-ID: <1992Dec21.151323.25650@cs.brown.edu>
  6. Keywords: indexing, clauses, n-ary trees, Quintus 'indexer'
  7. Sender: news@cs.brown.edu
  8. Organization: Brown University Department of Computer Science
  9. References: <1992Dec18.232658.12613@cs.tu-berlin.de>
  10. Date: Mon, 21 Dec 1992 15:13:23 GMT
  11. Lines: 353
  12.  
  13. This isn't quite what was requested, but perhaps this might
  14. serve as a start.  This is a package for maintaining 2-3
  15. trees.  The total ordering of keys used can be customized
  16. by the user by specializing compare_keys/3.
  17.  
  18. Hope this helps,
  19.  
  20. Mark
  21.  
  22. % tree23.pl    Associates keys with values using 2-3 trees
  23. %
  24. % Author: Mark Johnson
  25. % Date: 21st August 1991
  26. %
  27. % The procedures in this file manipulate finite maps from keys to
  28. % values.  Because 2-3 trees are used, they automatically rebalance
  29. % after each insertion or deletion.
  30. %
  31. % Contents:
  32. %
  33. % empty_23(?Tree23) - Tree23 is the empty map
  34. % gen_23(?Key, +Tree23, ?Value) - enumerate key-values in Tree23
  35. % get_23(+Key, +Tree23, ?Value) - find Value associated with Key in Tree23
  36. % list_to_23(+Pairs, -Tree23) - build a 2-3 tree for Pairs
  37. % portray_23(+Tree23) - portray a 2-3 tree
  38. % is_23(?Tree23) - test if Tree23 is a 2-3 tree
  39. % put_23(+Key, +Old23, ?Value, -New23) - New23 is a 2-3 tree just like
  40. %   Old23 except that it associates Key with Value.
  41. % update_23(+Key, +Old23Tree, ?Val, ?Mode, -New23Tree) is exactly
  42. %   the same as put_23(Key, Old23Tree, Val, New23Tree), except that
  43. %   Mode = replace(OldVal) if a pair Key-OldVal appears in Old23Tree;
  44. %   (in this case OldVal is replaced by NewVal in New23Tree), and
  45. %   that Mode = insert if such a pair does not appear in Old23Tree.
  46.  
  47.  
  48. empty_23(two_three).
  49.  
  50. % gen_23(?Key, +Tree23, ?Value)
  51. % iff Key-Value appears in Tree23.  Use this to enumerate all pairs
  52. % in Tree23.
  53. gen_23(Key, Tree, Value) :-
  54.     gen_23(Tree, Key-Value).
  55.  
  56. gen_23(two(Key), Key).
  57. gen_23(two(T0,_,_), Key) :- gen_23(T0, Key).
  58. gen_23(two(_,Key,_), Key).
  59. gen_23(two(_,_,T1), Key) :- gen_23(T1, Key).
  60. gen_23(three(Key,_), Key).
  61. gen_23(three(_,Key), Key).
  62. gen_23(three(T0,_,_,_,_), Key) :- gen_23(T0, Key).
  63. gen_23(three(_,Key,_,_,_), Key).
  64. gen_23(three(_,_,T1,_,_), Key) :- gen_23(T1, Key).
  65. gen_23(three(_,_,_,Key,_), Key).
  66. gen_23(three(_,_,_,_,T2), Key) :- gen_23(T2, Key).
  67.  
  68.  
  69.  
  70. % get_23(+Key, +Tree23, ?Val)
  71. get_23(Key, Tree, Val) :-
  72.     get_23(Tree, Key-Val).
  73.  
  74. % get_23(Tree23, Key)
  75. % finds Key in Tree23, where compare_keys orders keys.
  76. get_23(two(Key1), Key) :-
  77.     compare_keys(=, Key, Key1),
  78.     Key = Key1.
  79. get_23(two(T0,K1,T1), Key) :-
  80.     compare_keys(Rel, Key, K1),
  81.     get_2(Rel, Key, T0, K1, T1).
  82. get_23(three(K1,K2), Key) :-
  83.     compare_keys(Rel, Key, K1, K2),
  84.     get_3(Rel, Key, K1, K2).
  85. get_23(three(T0,K1,T1,K2,T2), Key) :-
  86.     compare_keys(Rel, Key, K1, K2),
  87.     get_3(Rel, Key, T0, K1, T1, K2, T2).
  88.  
  89. get_2(<, Key, T0, _, _) :- get_23(T0, Key).
  90. get_2(=, Key, _, Key, _).
  91. get_2(>, Key, _, _, T1) :- get_23(T1, Key).
  92.  
  93. get_3(1, Key, Key, _).
  94. get_3(2, Key, _, Key).
  95.  
  96. get_3(<, Key, T0, _, _, _, _) :- get_23(T0, Key).
  97. get_3(1, Key, _, Key, _, _, _).
  98. get_3(><, Key, _, _, T1, _, _) :- get_23(T1, Key).
  99. get_3(2, Key, _, _, _, Key, _).
  100. get_3(>, Key, _, _, _, _, T2) :- get_23(T2, Key).
  101.  
  102.  
  103.  
  104. % list_to_23(List, Tree23)
  105. list_to_23(List, Tree23) :-
  106.     list_to_23(List, two_three, Tree23).
  107.  
  108. list_to_23([], Tree, Tree).
  109. list_to_23([E|Es], Tree0, Tree) :-
  110.     put_23(Tree0, E, Tree1),
  111.     list_to_23(Es, Tree1, Tree).
  112.  
  113.  
  114.  
  115.  
  116. % portray_23(Tree23)
  117. portray_23(Tree) :-
  118.     is_23(Tree),
  119.     portray_23_1(Tree).
  120.  
  121. portray_23_1(_) :- write('23 Tree{'), nl, fail.
  122. portray_23_1(Tree23) :-
  123.     gen_23(Tree23, Key),
  124.     tab(2),
  125.     write(Key),
  126.     nl,
  127.     fail.
  128. portray_23_1(_) :-
  129.     write('}').
  130.  
  131. is_23(two_three).
  132. is_23(two(_)).
  133. is_23(two(_,_,_)).
  134. is_23(three(_,_)).
  135. is_23(three(_,_,_,_,_)).
  136.  
  137.  
  138.  
  139.  
  140. % put_23(Key, Old23Tree, Val, New23Tree) iff
  141. % New23Tree is the tree obtained by replacing the value of Key in
  142. % Old23Tree with Val.  Key need not be defined in Old23Tree.
  143.  
  144. put_23(Key, Old23Tree, Val, New23Tree) :-
  145.     put_23(Old23Tree, Key-Val, New23Tree).
  146.  
  147. % put_23(Old23Tree, Key, New23Tree) iff New23Tree is the tree
  148. % obtained by replacing a key K in Old23Tree with Key,
  149. % such that compare_keys(=, K, Key), or inserting Key if
  150. % there is no such K in Old23Tree
  151.  
  152. put_23(two_three, Key, TwoThree) :- 
  153.     !,
  154.     TwoThree = two(Key).
  155. put_23(Old, Key, New) :-
  156.     put_23(Old, Key, New1, EKey, ETree),
  157.     put_23_top(ETree, New1, EKey, New).
  158.  
  159. put_23_top(none, New1, _, New) :-
  160.     !,
  161.     New=New1.
  162. put_23_top(ETree, Tree0, EKey, two(Tree0,EKey,ETree)).
  163.  
  164. put_23(two(Key1), Key, New, _, none) :-
  165.     compare_keys(Rel, Key, Key1),
  166.     put_2(Rel, Key, Key1, New).
  167. put_23(two(Tree0,Key1,Tree1), Key, New, _, none) :-
  168.     compare_keys(Rel, Key, Key1),
  169.     put_2(Rel, Key, Tree0, Key1, Tree1, New).
  170. put_23(three(Key1,Key2), Key, NewTree, ExtraKey, ExtraTree) :-
  171.     compare_keys(Rel, Key, Key1, Key2),
  172.     put_3(Rel, Key, Key1, Key2, NewTree, ExtraKey, ExtraTree).
  173. put_23(three(Tree0,Key1,Tree1,Key2,Tree2), Key, New, EKey, ETree) :-
  174.     compare_keys(Rel, Key, Key1, Key2),
  175.     put_3(Rel, Key, Tree0, Key1, Tree1, Key2, Tree2, New, EKey, ETree).
  176.  
  177. put_2(=, Key, _, two(Key)).
  178. put_2(<, Key, Key1, three(Key,Key1)).
  179. put_2(>, Key, Key1, three(Key1,Key)).
  180.  
  181. put_2(=, Key, Tree0, _, Tree1, two(Tree0,Key,Tree1)).
  182. put_2(<, Key, OldTree0, Key1, Tree1, New) :-
  183.     put_23(OldTree0, Key, NewTree0, ExtraKey, ExtraTree),
  184.     put_2_l(ExtraTree, NewTree0, ExtraKey, Key1, Tree1, New).
  185. put_2(>, Key, Tree0, Key1, OldTree1, New) :-
  186.     put_23(OldTree1, Key, NewTree1, ExtraKey, ExtraTree),
  187.     put_2_r(ExtraTree, Tree0, Key1, NewTree1, ExtraKey, New).
  188.  
  189. put_2_l(none, Tree0, _, Key1, Tree1, two(Tree0,Key1,Tree1)) :- 
  190.     !.
  191. put_2_l(ETree, Tree0, EKey, Key1, Tree1, 
  192.             three(Tree0,EKey,ETree,Key1,Tree1)).
  193.  
  194. put_2_r(none, Tree0, Key1, Tree1, _, two(Tree0,Key1,Tree1)) :- 
  195.     !.
  196. put_2_r(ETree, Tree0, Key1, Tree1, EKey,
  197.             three(Tree0,Key1,Tree1,EKey,ETree)).
  198.  
  199. put_3(1, Key, _, Key2, three(Key,Key2), _, none).
  200. put_3(2, Key, Key1, _, three(Key1,Key), _, none).
  201. put_3(<, Key, Key1, Key2, two(Key), Key1, two(Key2)).
  202. put_3(><, Key, Key1, Key2, two(Key1), Key, two(Key2)).
  203. put_3(>, Key, Key1, Key2, two(Key1), Key2, two(Key)).
  204.  
  205. put_3(1, Key, Tree0, _, Tree1, Key2, Tree2,
  206.         three(Tree0, Key, Tree1, Key2, Tree2),
  207.         _, none).
  208. put_3(2, Key, Tree0, Key1, Tree1, _, Tree2,
  209.         three(Tree0, Key1, Tree1, Key, Tree2),
  210.         _, none).
  211. put_3(<, Key, OldTree0, Key1, Tree1, Key2, Tree2, New, NEKey, NETree) :-
  212.     put_23(OldTree0, Key, NewTree0, EKey, ETree),
  213.     put_3_l(ETree, NewTree0, EKey, Key1, Tree1, Key2, Tree2, 
  214.         New, NEKey, NETree).
  215. put_3(><, Key, Tree0, Key1, OldTree1, Key2, Tree2, New, NEKey, NETree) :-
  216.     put_23(OldTree1, Key, NewTree1, EKey, ETree),
  217.     put_3_m(ETree, Tree0, Key1, NewTree1, EKey, Key2, Tree2, 
  218.         New, NEKey, NETree).
  219. put_3(>, Key, Tree0, Key1, Tree1, Key2, OldTree2, New, NEKey, NETree) :-
  220.     put_23(OldTree2, Key, NewTree2, EKey, ETree),
  221.     put_3_r(ETree, Tree0, Key1, Tree1, Key2, NewTree2, EKey,
  222.         New, NEKey, NETree).
  223.  
  224. put_3_l(none, Tree0, _, Key1, Tree1, Key2, Tree2,
  225.         three(Tree0,Key1,Tree1,Key2,Tree2),
  226.         _, none) :-
  227.     !.
  228. put_3_l(ETree, Tree0, EKey, Key1, Tree1, Key2, Tree2,
  229.         two(Tree0,EKey,ETree),
  230.         Key1, two(Tree1,Key2,Tree2)).
  231.  
  232. put_3_m(none, Tree0, Key1, Tree1, _, Key2, Tree2,
  233.         three(Tree0,Key1,Tree1,Key2,Tree2),
  234.         _, none) :-
  235.     !.
  236. put_3_m(ETree, Tree0, Key1, Tree1, EKey, Key2, Tree2,
  237.         two(Tree0,Key1,Tree1),
  238.         EKey,
  239.         two(ETree,Key2,Tree2)).
  240.  
  241. put_3_r(none, Tree0, Key1, Tree1, Key2, Tree2, _,
  242.         three(Tree0,Key1,Tree1,Key2,Tree2),
  243.         _, none) :-
  244.     !.
  245. put_3_r(ETree, Tree0, Key1, Tree1, Key2, Tree2, EKey,
  246.         two(Tree0,Key1,Tree1),
  247.         Key2,
  248.         two(Tree2,EKey,ETree)).
  249.  
  250. % compare_keys(Rel, Key, Key1, Key2) assumes that Key1 < Key2,
  251. % then Rel = < iff Key < Key1
  252. %            1     Key = Key1
  253. %            ><    Key1 < Key < Key2
  254. %            2     Key = Key2
  255. %            >     Key2 < Key
  256. % with respect to the pairwise order of the relation compare_keys/3.
  257.  
  258. compare_keys(Rel, Key, Key1, Key2) :-
  259.     compare_keys(Rel1, Key, Key1),
  260.     compare_keys1(Rel1, Key, Key2, Rel).
  261.  
  262. compare_keys1(=, _, _, 1).
  263. compare_keys1(<, _, _, <).
  264. compare_keys1(>, Key, Key2, Rel) :-
  265.     compare_keys(Rel2, Key, Key2),
  266.     compare_keys1(Rel2, Rel).
  267.  
  268. compare_keys1(=, 2).
  269. compare_keys1(<, ><).
  270. compare_keys1(>, >).
  271.  
  272. % compare_keys(Rel, Key0, Key1) is a total order on Keys that is used
  273. % to structure the 23-trees.
  274.  
  275. compare_keys(Rel, Key0-_, Key1-_) :-
  276.     compare(Rel, Key0, Key1).
  277.  
  278. % update_23(+Key, +Old23Tree, ?Val, ?Mode, -New23Tree) is exactly
  279. % the same as put_23(Key, Old23Tree, Val, New23Tree), except that
  280. % Mode = replace(OldVal) if a pair Key-OldVal appears in Old23Tree;
  281. % (in this case OldVal is replaced by NewVal in New23Tree), and
  282. % that Mode = insert if such a pair does not appear in Old23Tree.
  283.  
  284. update_23(Key, Old23Tree, Val, Mode, New23Tree) :-
  285.     var(Mode), !,
  286.     update_23(Old23Tree, Key-Val, Mode0, New23Tree),
  287.     update_mode(Mode, Mode0).
  288. update_23(Key, Old23Tree, Val, Mode, New23Tree) :-
  289.     update_mode(Mode, Mode0),
  290.     update_23(Old23Tree, Key-Val, Mode0, New23Tree).
  291.  
  292. update_mode(insert, insert).
  293. update_mode(replace(Val), replace(_-Val)).
  294.  
  295. % update_23(+Old23Tree, +Key, ?Mode, -New23Tree) iff 
  296. %   (i) Old23Tree contains a key K such that compare_keys(=, K, Key),
  297. %       Mode = replace(K), and New23Tree = Old23Tree - {K} + {Key}, or
  298. %  (ii) Old23Tree does not contain a key K such that compare_keys(=, K, Key),
  299. %       Mode = insert, and New23Tree = Old23Tree + {Key}.
  300.  
  301. update_23(two_three, Key, Mode, TwoThree) :- 
  302.     !,
  303.     Mode = insert,
  304.     TwoThree = two(Key).
  305. update_23(Old, Key, Mode, New) :-
  306.     update_23(Old, Key, Mode, New1, EKey, ETree),
  307.     put_23_top(ETree, New1, EKey, New).
  308.  
  309. update_23(two(Key1), Key, Mode, New, _, none) :-
  310.     compare_keys(Rel, Key, Key1),
  311.     update_2(Rel, Key, Key1, Mode, New).
  312. update_23(two(Tree0,Key1,Tree1), Key, Mode, New, _, none) :-
  313.     compare_keys(Rel, Key, Key1),
  314.     update_2(Rel, Key, Tree0, Key1, Tree1, Mode, New).
  315. update_23(three(Key1,Key2), Key, Mode, NewTree, ExtraKey, ExtraTree) :-
  316.     compare_keys(Rel, Key, Key1, Key2),
  317.     update_3(Rel, Key, Key1, Key2, Mode, NewTree, ExtraKey, ExtraTree).
  318. update_23(three(Tree0,Key1,Tree1,Key2,Tree2), Key, Mode, New, EKey, ETree) :-
  319.     compare_keys(Rel, Key, Key1, Key2),
  320.     update_3(Rel, Key, Tree0, Key1, Tree1, Key2, Tree2, 
  321.                      Mode, New, EKey, ETree).
  322.  
  323. update_2(=, Key, Key1, replace(Key1), two(Key)).
  324. update_2(<, Key, Key1, insert, three(Key,Key1)).
  325. update_2(>, Key, Key1, insert, three(Key1,Key)).
  326.  
  327. update_2(=, Key, Tree0, Key1, Tree1, replace(Key1), two(Tree0,Key,Tree1)).
  328. update_2(<, Key, OldTree0, Key1, Tree1, Mode, New) :-
  329.     update_23(OldTree0, Key, Mode, NewTree0, ExtraKey, ExtraTree),
  330.     put_2_l(ExtraTree, NewTree0, ExtraKey, Key1, Tree1, New).
  331. update_2(>, Key, Tree0, Key1, OldTree1, Mode, New) :-
  332.     update_23(OldTree1, Key, Mode, NewTree1, ExtraKey, ExtraTree),
  333.     put_2_r(ExtraTree, Tree0, Key1, NewTree1, ExtraKey, New).
  334.  
  335. update_3(1, Key, Key1, Key2, replace(Key1), three(Key,Key2), _, none).
  336. update_3(2, Key, Key1, Key2, replace(Key2), three(Key1,Key), _, none).
  337. update_3(<, Key, Key1, Key2, insert, two(Key), Key1, two(Key2)).
  338. update_3(><, Key, Key1, Key2, insert, two(Key1), Key, two(Key2)).
  339. update_3(>, Key, Key1, Key2, insert, two(Key1), Key2, two(Key)).
  340.  
  341. update_3(1, Key, Tree0, Key1, Tree1, Key2, Tree2, replace(Key1),
  342.         three(Tree0, Key, Tree1, Key2, Tree2),
  343.         _, none).
  344. update_3(2, Key, Tree0, Key1, Tree1, Key2, Tree2, replace(Key2),
  345.         three(Tree0, Key1, Tree1, Key, Tree2),
  346.         _, none).
  347. update_3(<, Key, OldTree0, Key1, Tree1, Key2, Tree2, 
  348.                                             Mode, New, NEKey, NETree) :-
  349.     update_23(OldTree0, Key, Mode, NewTree0, EKey, ETree),
  350.     put_3_l(ETree, NewTree0, EKey, Key1, Tree1, Key2, Tree2, 
  351.         New, NEKey, NETree).
  352. update_3(><, Key, Tree0, Key1, OldTree1, Key2, Tree2, 
  353.                                              Mode, New, NEKey, NETree) :-
  354.     update_23(OldTree1, Key, Mode, NewTree1, EKey, ETree),
  355.     put_3_m(ETree, Tree0, Key1, NewTree1, EKey, Key2, Tree2, 
  356.         New, NEKey, NETree).
  357. update_3(>, Key, Tree0, Key1, Tree1, Key2, OldTree2, 
  358.                                              Mode, New, NEKey, NETree) :-
  359.     update_23(OldTree2, Key, Mode, NewTree2, EKey, ETree),
  360.     put_3_r(ETree, Tree0, Key1, Tree1, Key2, NewTree2, EKey,
  361.         New, NEKey, NETree).
  362.  
  363. Mark Johnson
  364. Cognitive Science, Box 1978
  365. Brown University
  366.