-
Notifications
You must be signed in to change notification settings - Fork 0
/
adts.pl
148 lines (106 loc) · 4.06 KB
/
adts.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
%%%
%%% This is one of the example programs from the textbook:
%%%
%%% Artificial Intelligence:
%%% Structures and strategies for complex problem solving
%%%
%%% by George F. Luger and William A. Stubblefield
%%%
%%% Corrections by Christopher E. Davis ([email protected])
%%%
%%% These programs are copyrighted by Benjamin/Cummings Publishers.
%%%
%%% We offer them for use, free of charge, for educational purposes only.
%%%
%%% Disclaimer: These programs are provided with no warranty whatsoever as to
%%% their correctness, reliability, or any other property. We have written
%%% them for specific educational purposes, and have made no effort
%%% to produce commercial quality computer programs. Please do not expect
%%% more of them then we have intended.
%%%
%%% This code has been tested with SWI-Prolog (Multi-threaded, Version 5.2.13)
%%% and appears to function as intended.
%%%%%%%%%%%%%%%%%%%% stack operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These predicates give a simple, list based implementation of stacks
% empty stack generates/tests an empty stack
member(X,[X|_]).
member(X,[_|T]):-member(X,T).
empty_stack([]).
% member_stack tests if an element is a member of a stack
member_stack(E, S) :- member(E, S).
% stack performs the push, pop and peek operations
% to push an element onto the stack
% ?- stack(a, [b,c,d], S).
% S = [a,b,c,d]
% To pop an element from the stack
% ?- stack(Top, Rest, [a,b,c]).
% Top = a, Rest = [b,c]
% To peek at the top element on the stack
% ?- stack(Top, _, [a,b,c]).
% Top = a
stack(E, S, [E|S]).
length_stack(S, Len) :- length(S, Len).
%%%%%%%%%%%%%%%%%%%% queue operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These predicates give a simple, list based implementation of
% FIFO queues
% empty queue generates/tests an empty queue
empty_queue([]).
% member_queue tests if an element is a member of a queue
member_queue(E, S) :- member(E, S).
% add_to_queue adds a new element to the back of the queue
add_to_queue(E, [], [E]).
add_to_queue(E, [H|T], [H|Tnew]) :- add_to_queue(E, T, Tnew).
% remove_from_queue removes the next element from the queue
% Note that it can also be used to examine that element
% without removing it
remove_from_queue(E, [E|T], T).
append_queue(First, Second, Concatenation) :-
append(First, Second, Concatenation).
%%%%%%%%%%%%%%%%%%%% set operations %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These predicates give a simple,
% list based implementation of sets
% empty_set tests/generates an empty set.
empty_set([]).
member_set(E, S) :- member(E, S).
% add_to_set adds a new member to a set, allowing each element
% to appear only once
add_to_set(X, S, S) :- member(X, S), !.
add_to_set(X, S, [X|S]).
remove_from_set(_, [], []).
remove_from_set(E, [E|T], T) :- !.
remove_from_set(E, [H|T], [H|T_new]) :-
remove_from_set(E, T, T_new), !.
union([], S, S).
union([H|T], S, S_new) :-
union(T, S, S2),
add_to_set(H, S2, S_new).
intersection([], _, []).
intersection([H|T], S, [H|S_new]) :-
member_set(H, S),
intersection(T, S, S_new),!.
intersection([_|T], S, S_new) :-
intersection(T, S, S_new),!.
set_diff([], _, []).
set_diff([H|T], S, T_new) :-
member_set(H, S),
set_diff(T, S, T_new),!.
set_diff([H|T], S, [H|T_new]) :-
set_diff(T, S, T_new), !.
subset([], _).
subset([H|T], S) :-
member_set(H, S),
subset(T, S).
equal_set(S1, S2) :-
subset(S1, S2), subset(S2, S1).
%%%%%%%%%%%%%%%%%%%%%%% priority queue operations %%%%%%%%%%%%%%%%%%%
% These predicates provide a simple list based implementation
% of a priority queue.
% They assume a definition of precedes for the objects being handled
empty_sort_queue([]).
member_sort_queue(E, S) :- member(E, S).
insert_sort_queue(State, [], [State]).
insert_sort_queue(State, [H | T], [State, H | T]) :-
precedes(State, H).
insert_sort_queue(State, [H|T], [H | T_new]) :-
insert_sort_queue(State, T, T_new).
remove_sort_queue(First, [First|Rest], Rest).