root/tags/lgt2310/library/bintree.lgt

Revision 3687, 3.2 KB (checked in by pmoura, 21 months ago)

Code reformating.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1
2:- object(bintree,
3    implements(dictionaryp),
4    extends(compound)).
5
6    :- info([
7        version is 1.1,
8        author is 'Paulo Moura',
9        date is 2006/9/17,
10        comment is 'Dictionary protocol implemented using binary trees.']).
11
12    :- private(map/4).
13    :- meta_predicate(map(*, *, *, ::)).
14    :- mode(map(+atom, +tree, -tree, -callable), zero_or_one).
15
16    as_list(Tree, List) :-
17        as_list(Tree, [], List).
18
19    as_list(t, List, List).
20    as_list(t(Key, Value, Left, Right), Acc, List) :-
21        as_list(Right, Acc, Acc2),
22        as_list(Left, [Key-Value| Acc2], List).
23
24    empty(Tree) :-
25        Tree == t.
26
27    insert(Key, Value, t, t(Key, Value, t, t)) :-
28        nonvar(Key).
29    insert(Key, Value, t(Key1, Value1, Left1, Right1), t(Key1, Value2, Left2, Right2)) :-
30        compare(Order, Key, Key1),
31        insert(Order, Key, Value, Key1, Value1, Left1, Right1, Value2, Left2, Right2).
32
33    insert(=, _, Value, _, _, Left, Right, Value, Left, Right).
34    insert(<, Key, Value, _, Value1, Left1, Right, Value1, Left2, Right) :-
35        insert(Key, Value, Left1, Left2).
36    insert(>, Key, Value, _, Value1, Left, Right1, Value1, Left, Right2) :-
37        insert(Key, Value, Right1, Right2).
38
39    insert_all([], Tree, Tree).
40    insert_all([Key-Value| Rest], Old, New) :-
41        insert(Key, Value, Old, Aux),
42        insert_all(Rest, Aux, New).
43
44    lookup(Key, Value, Tree) :-
45        (   var(Key) ->
46            lookup_var(Key, Value, Tree)
47        ;   lookup_nonvar(Key, Value, Tree)
48        ).
49
50    lookup_nonvar(Key, Value, t(Key1, Value1, Left1, Right1)) :-
51        compare(Order, Key, Key1),
52        lookup_nonvar(Order, Key, Value, Value1, Left1, Right1).
53
54    lookup_nonvar(=, _, Value, Value, _, _).
55    lookup_nonvar(<, Key, Value, _, Left, _) :-
56        lookup_nonvar(Key, Value, Left).
57    lookup_nonvar(<, Key, Value, _, _, Right) :-
58        lookup_nonvar(Key, Value, Right).
59
60    lookup_var(Key, Value, t(_, _, Left, _)) :-
61        lookup_var(Key, Value, Left).
62    lookup_var(Key, Value, t(Key, Value,_,_)).
63    lookup_var(Key, Value, t(_, _, _, Right)) :-
64        lookup_var(Key, Value, Right).
65
66    keys(Tree, Keys) :-
67        keys(Tree, [], Keys).
68
69    keys(t, Keys, Keys).
70    keys(t(Key, _, Left, Right), Acc, Keys) :-
71        keys(Right, Acc, Acc2),
72        keys(Left, [Key| Acc2], Keys).
73
74    delete(t, _, _, t).
75    delete(t(Key1, Value1, Left1, Right1), Key, Value, Out) :-
76        compare(Order, Key, Key1),
77        delete(Order, Key1, Value1, Left1, Right1, Key, Value, Out).
78
79    delete(=, Key1, Value1, Left1, Right1, Key1, Value1, Out) :-
80        join(Left1, Right1, Out).
81    delete(<, Key1, Value1, Left1, Right1, Key, Value, t(Key1, Value1, Left2, Right1)) :-
82        delete(Left1, Key, Value, Left2).
83    delete(>, Key1, Value1, Left1, Right1, Key, Value, t(Key1, Value1, Left1, Right2)) :-
84        delete(Right1, Key, Value, Right2).
85
86    join(t, Right, Right) :-
87        !.
88    join(Left, t, Left) :-
89        !.
90    join(t(Key, Value, Left, Right), Tree, t(Key, Value, Left, Right2)) :-
91        join(Right, Tree, Right2).
92
93    map(Pred, Old, New) :-
94        map(Pred, Old, New, _).
95
96    map(Pred, t(Key1, Value1, Left1, Right1), t(Key2, Value2, Left2, Right2), Goal) :-
97        Goal =.. [Pred, Key1-Value1, Key2-Value2],
98        once(Goal),
99        map(Pred, Left1, Left2, _),
100        map(Pred, Right1, Right2, _).
101    map(_, t, t, _).
102
103    new(t).
104
105    size(Dictionary, Size) :-
106        size(Dictionary, 0, Size).
107
108    size(t, Size, Size).
109    size(t(_, _, Left, Right), Acc, Size) :-
110        size(Left, Acc, Acc2),
111        Acc3 is Acc2 + 1,
112        size(Right, Acc3, Size).
113
114:- end_object.
Note: See TracBrowser for help on using the browser.