AVL tree: Difference between revisions
→{{header|Lua}}: Added Logtalk solution.
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
Ttmrichter (talk | contribs) (→{{header|Lua}}: Added Logtalk solution.) |
||
Line 8,451:
Printing key : 1 2 3 4 5 6 7 8 9 10
Printing balance : 0 0 0 1 0 0 0 0 1 0
</pre>
=={{header|Logtalk}}==
The Logtalk library comes with an AVL implementation of its `dictionaryp` protocol, whose definition begins thusly:
<syntaxhighlight lang="logtalk">
:- object(avltree,
implements(dictionaryp),
extends(term)).
% ... lots of elision ...
:- end_object.
</syntaxhighlight>
{{Out}}
This makes the use of an AVL tree in Logtalk dirt simple. First we load the `dictionaries` library.
<pre>
?- logtalk_load(dictionaries(loader)).
% ... messages elided ...
true.
</pre>
We can make a new, empty AVL tree.
<pre>
?- avltree::new(Dictionary).
Dictionary = t.
</pre>
Using Logtalk's broadcast notation to avoid having to repeatedly type `avltree::` in front of every operation we can insert some keys, update one, and look up values. Note that since variables in Logtalk, as in most declarative languages, cannot be altered, we actually have several dictionaries (`D0` through `D4`) representing the initial empty state, various intermediate states, as well as the final state.
<pre>
4 ?- avltree::(
new(D0),
insert(D0, a, 1, D1),
insert(D1, b, 2, D2),
insert(D2, c, 3, D3),
update(D3, a, 7, D4),
lookup(a, Va, D4),
lookup(c, Vc, D4)).
D0 = t,
D1 = t(a, 1, -, t, t),
D2 = t(a, 1, >, t, t(b, 2, -, t, t)),
D3 = t(b, 2, -, t(a, 1, -, t, t), t(c, 3, -, t, t)),
D4 = t(b, 2, -, t(a, 7, -, t, t), t(c, 3, -, t, t)),
Va = 7,
Vc = 3.
</pre>
To save some rote typing, the `as_dictionary/2` method lets a list of `Key-Value` pairs be used to initialize a dictionary instead:
<pre>
?- avltree::(
as_dictionary([a-1, b-2, c-3, a-7], D),
lookup(a, Va, D),
lookup(c, Vc, D)).
D = t(b, 2, <, t(a, 7, <, t(a, 1, -, t, t), t), t(c, 3, -, t, t)),
Va = 7,
Vc = 3.
</pre>
| |||