root/tags/lgt291/library/bintree.lgt

Revision 2, 3.2 KB (checked in by pmoura, 7 years ago)

Initial revision
  • 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
7    :- info([
8        version is 1.0,
9        authors is 'Paulo Moura',
10        date is 2000/7/24,
11        comment is 'Dictionary protocol implemented using binary trees.']).
12
13
14    :- private(map/4).
15    :- metapredicate(map(*, *, *, ::)).
16
17    :- mode(map(+atom, +tree, -tree, -callable), zero_or_one).
18
19
20    as_list(Tree, List) :-
21        as_list(Tree, [], List).
22
23
24    as_list(t, List, List).
25
26    as_list(t(Key, Value, Left, Right), Acc, List) :-
27        as_list(Right, Acc, Acc2),
28        as_list(Left, [Key-Value| Acc2], List).
29
30
31    empty(Tree) :-
32        Tree == t.
33
34
35    insert(Key, Value, t, t(Key, Value, t, t)) :-
36        nonvar(Key).
37
38    insert(Key, Value, t(Key1, Value1, Left1, Right1), t(Key1, Value2, Left2, Right2)) :-
39        compare(Order, Key, Key1),
40        insert(Order, Key, Value, Key1, Value1, Left1, Right1, Value2, Left2, Right2).
41
42
43    insert(=, _, Value, _, _, Left, Right, Value, Left, Right).
44
45    insert(<, Key, Value, _, Value1, Left1, Right, Value1, Left2, Right) :-
46        insert(Key, Value, Left1, Left2).
47
48    insert(>, Key, Value, _, Value1, Left, Right1, Value1, Left, Right2) :-
49        insert(Key, Value, Right1, Right2).
50
51
52    insert_all([], Tree, Tree).
53
54    insert_all([Key-Value| Rest], Old, New) :-
55        insert(Key, Value, Old, Aux),
56        insert_all(Rest, Aux, New).
57
58
59    lookup(Key, Value, Tree) :-
60        var(Key) ->
61            lookup_var(Key, Value, Tree)
62            ;
63            lookup_nonvar(Key, Value, Tree).
64
65
66    lookup_nonvar(Key, Value, t(Key1, Value1, Left1, Right1)) :-
67        compare(Order, Key, Key1),
68        lookup_nonvar(Order, Key, Value, Value1, Left1, Right1).
69
70
71    lookup_nonvar(=, _, Value, Value, _, _).
72
73    lookup_nonvar(<, Key, Value, _, Left, _) :-
74        lookup_nonvar(Key, Value, Left).
75
76    lookup_nonvar(<, Key, Value, _, _, Right) :-
77        lookup_nonvar(Key, Value, Right).
78
79
80    lookup_var(Key, Value, t(_, _, Left, _)) :-
81        lookup_var(Key, Value, Left).
82
83    lookup_var(Key, Value, t(Key, Value,_,_)).
84
85    lookup_var(Key, Value, t(_, _, _, Right)) :-
86        lookup_var(Key, Value, Right).
87
88
89    keys(Tree, Keys) :-
90        keys(Tree, [], Keys).
91
92
93    keys(t, Keys, Keys).
94
95    keys(t(Key, _, Left, Right), Acc, Keys) :-
96        keys(Right, Acc, Acc2),
97        keys(Left, [Key| Acc2], Keys).
98
99
100    delete(t, _, _, t).
101
102    delete(t(Key1, Value1, Left1, Right1), Key, Value, Out) :-
103        compare(Order, Key, Key1),
104        delete(Order, Key1, Value1, Left1, Right1, Key, Value, Out).
105
106
107    delete(=, Key1, Value1, Left1, Right1, Key1, Value1, Out) :-
108        join(Left1, Right1, Out).
109
110    delete(<, Key1, Value1, Left1, Right1, Key, Value, t(Key1, Value1, Left2, Right1)) :-
111        delete(Left1, Key, Value, Left2).
112
113    delete(>, Key1, Value1, Left1, Right1, Key, Value, t(Key1, Value1, Left1, Right2)) :-
114        delete(Right1, Key, Value, Right2).
115
116
117    join(t, Right, Right) :-
118        !.
119
120    join(Left, t, Left) :-
121        !.
122
123    join(t(Key, Value, Left, Right), Tree, t(Key, Value, Left, Right2)) :-
124        join(Right, Tree, Right2).
125
126
127    map(Pred, Old, New) :-
128        map(Pred, Old, New, _).
129
130
131    map(Pred, t(Key1, Value1, Left1, Right1), t(Key2, Value2, Left2, Right2), Goal) :-
132        Goal =.. [Pred, Key1-Value1, Key2-Value2],
133        once(Goal),
134        map(Pred, Left1, Left2, _),
135        map(Pred, Right1, Right2, _).
136
137    map(_, t, t, _).
138
139
140    new(t).
141
142
143    size(Dictionary, Size) :-
144        size(Dictionary, 0, Size).
145
146
147    size(t, Size, Size).
148
149    size(t(_, _, Left, Right), Acc, Size) :-
150        size(Left, Acc, Acc2),
151        Acc3 is Acc2 + 1,
152        size(Right, Acc3, Size).
153
154
155:- end_object.
Note: See TracBrowser for help on using the browser.