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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
|
<HTML>
<HEAD>
<TITLE>Utilities (Subsystem of AIMA Code)</TITLE>
<!-- Changed by: Peter Norvig, 30-Oct-1996 -->
</HEAD>
<BODY bgcolor="#ffffff">
<H1>Utilities (Subsystem of AIMA Code)</H1>
The <b>utilities</b> system provides a set of basic functions, macros,
and data types that are used throughout the other systems. For
example, we define the <tt>while</tt> and <tt>for</tt> iteration
macros, the two-dimensional point (and operations on it), the queue
and binary tree types, and some debugging and testing code.
<P><HR size=3></UL><A HREF="../utilities/"><B>utilities/</B></A>:
<UL> <LI><A HREF="#utilities/utilities.lisp"><B>utilities.lisp</B></A> Basic utility functions and macros, used throughout the code. <LI><A HREF="#utilities/binary-tree.lisp"><B>binary-tree.lisp</B></A> The following definitions implement binary search trees.<LI><A HREF="#utilities/queue.lisp"><B>queue.lisp</B></A> The Queue datatype<LI><A HREF="#utilities/cltl2.lisp"><B>cltl2.lisp</B></A> Compatibility package for 'Common Lisp the Language: 2nd edition'<LI><A HREF="#utilities/test-utilities.lisp"><B>test-utilities.lisp</B></A> Test cases for the basic utilities</UL>
<A NAME="utilities/utilities.lisp"><HR>
<H2>File <A HREF="../utilities/utilities.lisp">utilities/utilities.lisp</A></H2></A>
<H2><I> Basic utility functions and macros, used throughout the code. </I>
</H2>
<I> The utilities are divided into control flow macros, list</I>
<I> utilities, functions for 2-dimensional points, numeric utilities,</I>
<I> some trivial functions, utilities for strings, symbols and</I>
<I> printing, a debugging tool, and a testing tool."</I>
<H2><I> Control Flow Macros</I>
</H2>
<I> We define iteration macros to match the book's pseudo-code.</I>
<I> This could all be done with LOOP, but some users don't have</I>
<I> the LOOP from the 2nd edition of 'Common Lisp: the Language'.</I>
<A NAME="while"><P><A HREF="../utilities/utilities.lisp"><B>while</B></A></A> <I>macro</I> (test
do
&body
body)
<blockquote>Execute body while the test is true.</blockquote>
<A NAME="for-each"><P><A HREF="../utilities/utilities.lisp"><B>for-each</B></A></A> <I>macro</I> (var
in
list
do
&body
body)
<blockquote>Execute body for each element of list. VAR can be a list or tree
of variables, in which case the elements are destructured.</blockquote>
<A NAME="for"><P><A HREF="../utilities/utilities.lisp"><B>for</B></A></A> <I>macro</I> (var
=
start
to
end
do
&body
body)
<blockquote>Execute body with var bound to succesive integers.</blockquote>
<A NAME="deletef"><P><A HREF="../utilities/utilities.lisp"><B>deletef</B></A></A> <I>macro</I> (item
sequence
&rest
keys
&environment
env)
<blockquote>Destructively delete item from sequence, which must be SETF-able.</blockquote>
<A NAME="define-if-undefined"><P><A HREF="../utilities/utilities.lisp"><B>define-if-undefined</B></A></A> <I>macro</I> (&rest
definitions)
<blockquote>Use this to conditionally define functions, variables, or macros that
may or may not be pre-defined in this Lisp. This can be used to provide
CLtL2 compatibility for older Lisps.</blockquote>
<H2><I> List Utilities</I>
</H2>
<A NAME="length>1"><P><A HREF="../utilities/utilities.lisp"><B>length>1</B></A></A> <I>function</I> (list)
<blockquote>Is this a list of 2 or more elements?</blockquote>
<A NAME="length=1"><P><A HREF="../utilities/utilities.lisp"><B>length=1</B></A></A> <I>function</I> (list)
<blockquote>Is this a list of exactly one element?</blockquote>
<A NAME="random-element"><P><A HREF="../utilities/utilities.lisp"><B>random-element</B></A></A> <I>function</I> (list)
<blockquote>Return some element of the list, chosen at random.</blockquote>
<A NAME="mappend"><P><A HREF="../utilities/utilities.lisp"><B>mappend</B></A></A> <I>function</I> (fn
&rest
lists)
<blockquote>Apply fn to respective elements of list(s), and append results.</blockquote>
<A NAME="starts-with"><P><A HREF="../utilities/utilities.lisp"><B>starts-with</B></A></A> <I>function</I> (list
element)
<blockquote>Is this a list that starts with the given element?</blockquote>
<A NAME="last1"><P><A HREF="../utilities/utilities.lisp"><B>last1</B></A></A> <I>function</I> (list)
<blockquote>Return the last element of a list.</blockquote>
<A NAME="left-rotate"><P><A HREF="../utilities/utilities.lisp"><B>left-rotate</B></A></A> <I>function</I> (list)
<blockquote>Move the first element to the end of the list.</blockquote>
<A NAME="right-rotate"><P><A HREF="../utilities/utilities.lisp"><B>right-rotate</B></A></A> <I>function</I> (list)
<blockquote>Move the last element to the front of the list.</blockquote>
<A NAME="transpose"><P><A HREF="../utilities/utilities.lisp"><B>transpose</B></A></A> <I>function</I> (list-of-lists)
<blockquote>Transpose a matrix represented as a list of lists.
Example: (transpose '((a b c) (d e f))) => ((a d) (b e) (c f)).</blockquote>
<A NAME="reuse-cons"><P><A HREF="../utilities/utilities.lisp"><B>reuse-cons</B></A></A> <I>function</I> (x
y
x-y)
<blockquote>Return (cons x y), or reuse x-y if it is equal to (cons x y)</blockquote>
<A NAME="make-exp"><P><A HREF="../utilities/utilities.lisp"><B>make-exp</B></A></A> <I>function</I> (op
&rest
args)
<P>
<A NAME="op"><P><A HREF="../utilities/utilities.lisp"><B>op</B></A></A> <I>function</I> (exp)
<blockquote>Operator of an expression</blockquote>
<A NAME="args"><P><A HREF="../utilities/utilities.lisp"><B>args</B></A></A> <I>function</I> (exp)
<blockquote>Arguments of an expression</blockquote>
<A NAME="arg1"><P><A HREF="../utilities/utilities.lisp"><B>arg1</B></A></A> <I>function</I> (exp)
<blockquote>First argument</blockquote>
<A NAME="arg2"><P><A HREF="../utilities/utilities.lisp"><B>arg2</B></A></A> <I>function</I> (exp)
<blockquote>Second argument</blockquote>
<A NAME="prefix->infix"><P><A HREF="../utilities/utilities.lisp"><B>prefix->infix</B></A></A> <I>function</I> (exp)
<blockquote>Convert a fully parenthesized prefix expression into infix notation.</blockquote>
<A NAME="insert-between"><P><A HREF="../utilities/utilities.lisp"><B>insert-between</B></A></A> <I>function</I> (item
list)
<blockquote>Insert item between every element of list.</blockquote>
<H2><I> Functions for manipulating 2-dimensional points </I>
</H2>
<A NAME="xy"><P><A HREF="../utilities/utilities.lisp"><B>xy</B></A></A> <I>type</I> (x
y)
<blockquote>A two-dimensional (i.e. x and y) point.</blockquote>
<A NAME="xy-p"><P><A HREF="../utilities/utilities.lisp"><B>xy-p</B></A></A> <I>function</I> (arg)
<blockquote>Is the argument a 2-D point?</blockquote>
<A NAME="@"><P><A HREF="../utilities/utilities.lisp"><B>@</B></A></A> <I>function</I> (x
y)
<blockquote>Create a 2-D point</blockquote>
<A NAME="xy-equal"><P><A HREF="../utilities/utilities.lisp"><B>xy-equal</B></A></A> <I>function</I> (p
q)
<P>
<A NAME="xy-add"><P><A HREF="../utilities/utilities.lisp"><B>xy-add</B></A></A> <I>function</I> (p
q)
<blockquote>Add two points, component-wise.</blockquote>
<A NAME="xy-distance"><P><A HREF="../utilities/utilities.lisp"><B>xy-distance</B></A></A> <I>function</I> (p
q)
<blockquote>The distance between two points.</blockquote>
<A NAME="x+y-distance"><P><A HREF="../utilities/utilities.lisp"><B>x+y-distance</B></A></A> <I>function</I> (p
q)
<blockquote>The 'city block distance' between two points.</blockquote>
<A NAME="xy-between"><P><A HREF="../utilities/utilities.lisp"><B>xy-between</B></A></A> <I>function</I> (xy1
xy2
xy3)
<blockquote>Predicate; return t iff xy1 is between xy2 and xy3. Points are collinear.</blockquote>
<A NAME="rotate"><P><A HREF="../utilities/utilities.lisp"><B>rotate</B></A></A> <I>function</I> (o
a
b
c
d)
<P>
<A NAME="inside"><P><A HREF="../utilities/utilities.lisp"><B>inside</B></A></A> <I>function</I> (l
xmax
ymax)
<blockquote>Is the point l inside a rectangle from 0,0 to xmax,ymax?</blockquote>
<H2><I> Numeric Utilities</I>
</H2>
<A NAME="infinity"><P><A HREF="../utilities/utilities.lisp"><B>infinity</B></A></A> <I>constant</I>
<P>
<A NAME="minus-infinity"><P><A HREF="../utilities/utilities.lisp"><B>minus-infinity</B></A></A> <I>constant</I>
<P>
<A NAME="average"><P><A HREF="../utilities/utilities.lisp"><B>average</B></A></A> <I>function</I> (numbers)
<blockquote>Numerical average (mean) of a list of numbers.</blockquote>
<A NAME="running-average"><P><A HREF="../utilities/utilities.lisp"><B>running-average</B></A></A> <I>function</I> (avg
new
n)
<blockquote>Calculate new average given previous average over n data points</blockquote>
<A NAME="square"><P><A HREF="../utilities/utilities.lisp"><B>square</B></A></A> <I>function</I> (x)
<P>
<A NAME="sum"><P><A HREF="../utilities/utilities.lisp"><B>sum</B></A></A> <I>function</I> (numbers
&optional
key)
<blockquote>Add up all the numbers; if KEY is given, apply it to each number first.</blockquote>
<A NAME="between"><P><A HREF="../utilities/utilities.lisp"><B>between</B></A></A> <I>function</I> (x
y
z)
<blockquote>Predicate; return t iff number x is between numbers y and z.</blockquote>
<A NAME="rms-error"><P><A HREF="../utilities/utilities.lisp"><B>rms-error</B></A></A> <I>function</I> (predicted
target)
<blockquote>Compute root mean square error between predicted list and target list</blockquote>
<A NAME="ms-error"><P><A HREF="../utilities/utilities.lisp"><B>ms-error</B></A></A> <I>function</I> (predicted
target)
<blockquote>Compute mean square error between predicted list and target list</blockquote>
<A NAME="boolean-error"><P><A HREF="../utilities/utilities.lisp"><B>boolean-error</B></A></A> <I>function</I> (predicted
target)
<P>
<A NAME="dot-product"><P><A HREF="../utilities/utilities.lisp"><B>dot-product</B></A></A> <I>function</I> (l1
l2)
<P>
<A NAME="iota"><P><A HREF="../utilities/utilities.lisp"><B>iota</B></A></A> <I>function</I> (n
&optional
start-at)
<blockquote>Return a list of n consecutive integers, by default starting at 0.</blockquote>
<A NAME="random-integer"><P><A HREF="../utilities/utilities.lisp"><B>random-integer</B></A></A> <I>function</I> (from
to)
<blockquote>Return an integer chosen at random from the given interval.</blockquote>
<A NAME="normal"><P><A HREF="../utilities/utilities.lisp"><B>normal</B></A></A> <I>function</I> (x
mu
sigma)
<P>
<A NAME="sample-with-replacement"><P><A HREF="../utilities/utilities.lisp"><B>sample-with-replacement</B></A></A> <I>function</I> (n
population)
<P>
<A NAME="sample-without-replacement"><P><A HREF="../utilities/utilities.lisp"><B>sample-without-replacement</B></A></A> <I>function</I> (n
population
&optional
m)
<P>
<A NAME="fuzz"><P><A HREF="../utilities/utilities.lisp"><B>fuzz</B></A></A> <I>function</I> (quantity
&optional
proportion
round-off)
<blockquote>Add and also subtract a random fuzz-factor to a quantity.</blockquote>
<A NAME="round-off"><P><A HREF="../utilities/utilities.lisp"><B>round-off</B></A></A> <I>function</I> (number
precision)
<blockquote>Round off the number to specified precision. E.g. (round-off 1.23 .1) = 1.2</blockquote>
<H2><I> Trivial Functions</I>
</H2>
<A NAME="nothing"><P><A HREF="../utilities/utilities.lisp"><B>nothing</B></A></A> <I>function</I> (&rest
args)
<blockquote>Don't do anything, and return nil.</blockquote>
<A NAME="declare-ignore"><P><A HREF="../utilities/utilities.lisp"><B>declare-ignore</B></A></A> <I>function</I> (&rest
args)
<blockquote>Ignore the arguments.</blockquote>
<A NAME="true"><P><A HREF="../utilities/utilities.lisp"><B>true</B></A></A> <I>function</I> (&rest
args)
<blockquote>Always return true.</blockquote>
<A NAME="false"><P><A HREF="../utilities/utilities.lisp"><B>false</B></A></A> <I>function</I> (&rest
args)
<blockquote>Always return false.</blockquote>
<A NAME="required"><P><A HREF="../utilities/utilities.lisp"><B>required</B></A></A> <I>function</I> (&optional
msg
&rest
args)
<blockquote>If this ever gets called, it means something that was required was not
supplied. Use as default value for &key args or defstruct slots.</blockquote>
<H2><I> Utilities for strings and symbols and printing</I>
</H2>
<A NAME="stringify"><P><A HREF="../utilities/utilities.lisp"><B>stringify</B></A></A> <I>function</I> (exp)
<blockquote>Coerce argument to a string.</blockquote>
<A NAME="concat-symbol"><P><A HREF="../utilities/utilities.lisp"><B>concat-symbol</B></A></A> <I>function</I> (&rest
args)
<blockquote>Concatenate the args into one string, and turn that into a symbol.</blockquote>
<A NAME="print-grid"><P><A HREF="../utilities/utilities.lisp"><B>print-grid</B></A></A> <I>function</I> (array
&key
stream
key
width)
<blockquote>Print the contents of a 2-D array, numbering the edges.</blockquote>
<A NAME="print-centered"><P><A HREF="../utilities/utilities.lisp"><B>print-centered</B></A></A> <I>function</I> (string
width
&optional
stream)
<blockquote>Print STRING centered in a field WIDTH wide.</blockquote>
<A NAME="print-repeated"><P><A HREF="../utilities/utilities.lisp"><B>print-repeated</B></A></A> <I>function</I> (string
n
&optional
stream)
<blockquote>Print the string n times.</blockquote>
<A NAME="print-dashes"><P><A HREF="../utilities/utilities.lisp"><B>print-dashes</B></A></A> <I>function</I> (width
&optional
stream
separate-line)
<blockquote>Print a line of dashes WIDTH wide.</blockquote>
<H2><I> Assorted conversion utilities and predicates</I>
</H2>
<A NAME="copy-array"><P><A HREF="../utilities/utilities.lisp"><B>copy-array</B></A></A> <I>function</I> (a)
<blockquote>Make a copy of an array.</blockquote>
<A NAME="copy-subarray"><P><A HREF="../utilities/utilities.lisp"><B>copy-subarray</B></A></A> <I>function</I> (a
b
indices
dim)
<P>
<A NAME="array->vector"><P><A HREF="../utilities/utilities.lisp"><B>array->vector</B></A></A> <I>function</I> (array)
<blockquote>Convert a multi-dimensional array to a vector with the same elements.</blockquote>
<A NAME="plot-alist"><P><A HREF="../utilities/utilities.lisp"><B>plot-alist</B></A></A> <I>function</I> (alist
file)
<P>
<A NAME="copy-hash-table"><P><A HREF="../utilities/utilities.lisp"><B>copy-hash-table</B></A></A> <I>function</I> (h1
&optional
copy-fn)
<P>
<A NAME="hash-table->list"><P><A HREF="../utilities/utilities.lisp"><B>hash-table->list</B></A></A> <I>function</I> (table)
<blockquote>Convert a hash table into a list of (key . val) pairs.</blockquote>
<A NAME="hprint"><P><A HREF="../utilities/utilities.lisp"><B>hprint</B></A></A> <I>function</I> (h
&optional
stream)
<blockquote>prints a hash table line by line</blockquote>
<A NAME="compose"><P><A HREF="../utilities/utilities.lisp"><B>compose</B></A></A> <I>function</I> (f
g)
<blockquote>Return a function h such that (h x) = (f (g x)).</blockquote>
<A NAME="the-biggest"><P><A HREF="../utilities/utilities.lisp"><B>the-biggest</B></A></A> <I>function</I> (fn
l)
<P>
<A NAME="the-biggest-random-tie"><P><A HREF="../utilities/utilities.lisp"><B>the-biggest-random-tie</B></A></A> <I>function</I> (fn
l)
<P>
<A NAME="the-biggest-that"><P><A HREF="../utilities/utilities.lisp"><B>the-biggest-that</B></A></A> <I>function</I> (fn
p
l)
<P>
<A NAME="the-smallest"><P><A HREF="../utilities/utilities.lisp"><B>the-smallest</B></A></A> <I>function</I> (fn
l)
<P>
<A NAME="the-smallest-random-tie"><P><A HREF="../utilities/utilities.lisp"><B>the-smallest-random-tie</B></A></A> <I>function</I> (fn
l)
<P>
<A NAME="the-smallest-that"><P><A HREF="../utilities/utilities.lisp"><B>the-smallest-that</B></A></A> <I>function</I> (fn
p
l)
<P>
<H2><I> Debugging tool</I>
</H2>
<A NAME="*debugging*"><P><A HREF="../utilities/utilities.lisp"><B>*debugging*</B></A></A> <I>variable</I>
<P>
<A NAME="dprint"><P><A HREF="../utilities/utilities.lisp"><B>dprint</B></A></A> <I>function</I> (&rest
args)
<blockquote>Echo all the args when *debugging* is true. Return the first one.</blockquote>
<H2><I> Testing Tool: deftest and test</I>
</H2>
<A NAME="deftest"><P><A HREF="../utilities/utilities.lisp"><B>deftest</B></A></A> <I>macro</I> (name
&rest
examples)
<blockquote>Define a set of test examples. Each example is of the form (exp test)
or (exp). Evaluate exp and see if the result passes the test. Within the
test, the result is bound to *. The example ((f 2))) has no test to
fail, so it alweays passes the test. But ((+ 2 2) (= * 3)) has the test
(= * 3), which fails because * will be bound to the result 4, so the test
fails. Call (TEST name) to count how many tests are failed within the
named test. NAME is the name of an aima-system.</blockquote>
<A NAME="add-test"><P><A HREF="../utilities/utilities.lisp"><B>add-test</B></A></A> <I>function</I> (name
examples)
<blockquote>The functional interface for deftest: adds test examples to a system.</blockquote>
<A NAME="test"><P><A HREF="../utilities/utilities.lisp"><B>test</B></A></A> <I>function</I> (&optional
name
print?)
<blockquote>Run a test suite and sum the number of errors. If all is well, this
should return 0. The second argument says what to print: nil for
nothing, t for everything, or FAIL for just those examples that fail.
If there are no test examples in the named system, put the system has
other systems as parts, run the tests for all those and sum the result.</blockquote>
<A NAME="test-example"><P><A HREF="../utilities/utilities.lisp"><B>test-example</B></A></A> <I>function</I> (example
&optional
print?)
<blockquote>Does the EXP part of this example pass the TEST?</blockquote>
<A NAME="utilities/binary-tree.lisp"><HR>
<H2>File <A HREF="../utilities/binary-tree.lisp">utilities/binary-tree.lisp</A></H2></A>
<H2><I> The following definitions implement binary search trees.</I>
</H2>
<I> They are not balanced as yet. Currently, they all order their</I>
<I> elements by #'<, and test for identity of elements by #'eq.</I>
<A NAME="search-tree-node"><P><A HREF="../utilities/binary-tree.lisp"><B>search-tree-node</B></A></A> <I>type</I> (value
num-elements
key
parent
leftson
rightson)
<blockquote>node for binary search tree</blockquote>
<A NAME="make-search-tree"><P><A HREF="../utilities/binary-tree.lisp"><B>make-search-tree</B></A></A> <I>function</I> (root-elem
root-key)
<blockquote>return dummy header for binary search tree, with initial
element root-elem whose key is root-key.</blockquote>
<A NAME="create-sorted-tree"><P><A HREF="../utilities/binary-tree.lisp"><B>create-sorted-tree</B></A></A> <I>function</I> (list-of-elems
key-fun)
<blockquote>return binary search tree containing list-of-elems ordered according
tp key-fun</blockquote>
<A NAME="empty-tree"><P><A HREF="../utilities/binary-tree.lisp"><B>empty-tree</B></A></A> <I>function</I> (root)
<blockquote>Predicate of search trees; return t iff empty.</blockquote>
<A NAME="leftmost"><P><A HREF="../utilities/binary-tree.lisp"><B>leftmost</B></A></A> <I>function</I> (tree-node)
<blockquote>return leftmost descendant of tree-node</blockquote>
<A NAME="rightmost"><P><A HREF="../utilities/binary-tree.lisp"><B>rightmost</B></A></A> <I>function</I> (header)
<blockquote>return rightmost descendant of header</blockquote>
<A NAME="pop-least-element"><P><A HREF="../utilities/binary-tree.lisp"><B>pop-least-element</B></A></A> <I>function</I> (header)
<blockquote>return least element of binary search tree; delete from tree as side-effect</blockquote>
<A NAME="pop-largest-element"><P><A HREF="../utilities/binary-tree.lisp"><B>pop-largest-element</B></A></A> <I>function</I> (header)
<blockquote>return largest element of binary search tree; delete from tree as side-effect</blockquote>
<A NAME="least-key"><P><A HREF="../utilities/binary-tree.lisp"><B>least-key</B></A></A> <I>function</I> (header)
<blockquote>return least key of binary search tree; no side effects</blockquote>
<A NAME="largest-key"><P><A HREF="../utilities/binary-tree.lisp"><B>largest-key</B></A></A> <I>function</I> (header)
<blockquote>return least key of binary search tree; no side effects</blockquote>
<A NAME="insert-element"><P><A HREF="../utilities/binary-tree.lisp"><B>insert-element</B></A></A> <I>function</I> (element
parent
key
&optional
direction)
<blockquote>insert new element at proper place in binary search tree</blockquote>
<A NAME="randomized-insert-element"><P><A HREF="../utilities/binary-tree.lisp"><B>randomized-insert-element</B></A></A> <I>function</I> (element
parent
key
&optional
direction)
<blockquote>insert new element at proper place in binary search tree -- break
ties randomly</blockquote>
<A NAME="randomized-push"><P><A HREF="../utilities/binary-tree.lisp"><B>randomized-push</B></A></A> <I>function</I> (element
list)
<blockquote>return list with element destructively inserted at random into list</blockquote>
<A NAME="find-element"><P><A HREF="../utilities/binary-tree.lisp"><B>find-element</B></A></A> <I>function</I> (element
parent
key
&optional
direction)
<blockquote>return t if element is int tree</blockquote>
<A NAME="delete-element"><P><A HREF="../utilities/binary-tree.lisp"><B>delete-element</B></A></A> <I>function</I> (element
parent
key
&optional
error-p)
<blockquote>delete element from binary search tree</blockquote>
<A NAME="inorder-successor"><P><A HREF="../utilities/binary-tree.lisp"><B>inorder-successor</B></A></A> <I>function</I> (tree-node)
<blockquote>return inorder-successor of tree-node assuming it has a right son</blockquote>
<A NAME="list-elements"><P><A HREF="../utilities/binary-tree.lisp"><B>list-elements</B></A></A> <I>function</I> (parent)
<blockquote>return list of elements in tree</blockquote>
<A NAME="utilities/queue.lisp"><HR>
<H2>File <A HREF="../utilities/queue.lisp">utilities/queue.lisp</A></H2></A>
<H2><I> The Queue datatype</I>
</H2>
<I> We can remove elements form the front of a queue. We can add elements in</I>
<I> three ways: to the front, to the back, or ordered by some numeric score.</I>
<I> This is done with the following enqueing functions, which make use of the</I>
<I> following implementations of the elements:</I>
<I> ENQUEUE-AT-FRONT - elements are a list</I>
<I> ENQUEUE-AT-END - elements are a list, with a pointer to end</I>
<I> ENQUEUE-BY-PRIORITY - elements are a heap, implemented as an array</I>
<I> The best element in the queue is always in position 0.</I>
<I> The heap implementation is taken from "Introduction to Algorithms" by</I>
<I> Cormen, Lieserson & Rivest [CL&R], Chapter 7. We could certainly speed</I>
<I> up the constant factors of this implementation. It is meant to be clear</I>
<I> and simple and O(log n), but not super efficient. Consider a Fibonacci</I>
<I> heap [Page 420 CL&R] if you really have large queues to deal with.</I>
<A NAME="q"><P><A HREF="../utilities/queue.lisp"><B>q</B></A></A> <I>type</I> (key
last
elements)
<P>
<H2><I> Basic Operations on Queues</I>
</H2>
<A NAME="make-empty-queue"><P><A HREF="../utilities/queue.lisp"><B>make-empty-queue</B></A></A> <I>function</I> ()
<P>
<A NAME="empty-queue?"><P><A HREF="../utilities/queue.lisp"><B>empty-queue?</B></A></A> <I>function</I> (q)
<blockquote>Are there no elements in the queue?</blockquote>
<A NAME="queue-front"><P><A HREF="../utilities/queue.lisp"><B>queue-front</B></A></A> <I>function</I> (q)
<blockquote>Return the element at the front of the queue.</blockquote>
<A NAME="remove-front"><P><A HREF="../utilities/queue.lisp"><B>remove-front</B></A></A> <I>function</I> (q)
<blockquote>Remove the element from the front of the queue and return it.</blockquote>
<H2><I> The Three Enqueing Functions</I>
</H2>
<A NAME="enqueue-at-front"><P><A HREF="../utilities/queue.lisp"><B>enqueue-at-front</B></A></A> <I>function</I> (q
items)
<blockquote>Add a list of items to the front of the queue.</blockquote>
<A NAME="enqueue-at-end"><P><A HREF="../utilities/queue.lisp"><B>enqueue-at-end</B></A></A> <I>function</I> (q
items)
<blockquote>Add a list of items to the end of the queue.</blockquote>
<A NAME="enqueue-by-priority"><P><A HREF="../utilities/queue.lisp"><B>enqueue-by-priority</B></A></A> <I>function</I> (q
items
key)
<blockquote>Insert the items by priority according to the key function.</blockquote>
<H2><I> The Heap Implementation of Priority Queues</I>
</H2>
<I> The idea is to store a heap in an array so that the heap property is</I>
<I> maintained for all elements: heap[Parent(i)] <= heap[i]. Note that we</I>
<I> start at index 0, not 1, and that we put the lowest value at the top of</I>
<I> the heap, not the highest value.</I>
<A NAME="heap-val"><P><A HREF="../utilities/queue.lisp"><B>heap-val</B></A></A> <I>function</I> (heap
i
key)
<P>
<A NAME="heap-parent"><P><A HREF="../utilities/queue.lisp"><B>heap-parent</B></A></A> <I>function</I> (i)
<P>
<A NAME="heap-left"><P><A HREF="../utilities/queue.lisp"><B>heap-left</B></A></A> <I>function</I> (i)
<P>
<A NAME="heap-right"><P><A HREF="../utilities/queue.lisp"><B>heap-right</B></A></A> <I>function</I> (i)
<P>
<A NAME="heapify"><P><A HREF="../utilities/queue.lisp"><B>heapify</B></A></A> <I>function</I> (heap
i
key)
<blockquote>Assume that the children of i are heaps, but that heap[i] may be
larger than its children. If it is, move heap[i] down where it belongs.
[Page 143 CL&R].</blockquote>
<A NAME="heap-extract-min"><P><A HREF="../utilities/queue.lisp"><B>heap-extract-min</B></A></A> <I>function</I> (heap
key)
<blockquote>Pop the best (lowest valued) item off the heap. [Page 150 CL&R].</blockquote>
<A NAME="heap-insert"><P><A HREF="../utilities/queue.lisp"><B>heap-insert</B></A></A> <I>function</I> (heap
item
key)
<blockquote>Put an item into a heap. [Page 150 CL&R].</blockquote>
<A NAME="make-heap"><P><A HREF="../utilities/queue.lisp"><B>make-heap</B></A></A> <I>function</I> (&optional
size)
<P>
<A NAME="heap-sort"><P><A HREF="../utilities/queue.lisp"><B>heap-sort</B></A></A> <I>function</I> (numbers
&key
key)
<blockquote>Return a sorted list, with elements that are < according to key first.</blockquote>
<A NAME="utilities/cltl2.lisp"><HR>
<H2>File <A HREF="../utilities/cltl2.lisp">utilities/cltl2.lisp</A></H2></A>
<H2><I> Compatibility package for 'Common Lisp the Language: 2nd edition'</I>
</H2>
<I> Functions and macros in CLtL2 that are not in the first edition of</I>
<I> the book, and thus not in some old implementations of Common Lisp.</I>
<A NAME="with-simple-restart"><P><A HREF="../utilities/cltl2.lisp"><B>with-simple-restart</B></A></A> <I>macro</I> (restart
&rest
body)
<blockquote>Like PROGN, except provides control over restarts if there is an error.</blockquote>
<A NAME="destructuring-bind"><P><A HREF="../utilities/cltl2.lisp"><B>destructuring-bind</B></A></A> <I>macro</I> (lambda-list
list
&body
body)
<blockquote>Bind the variables in lambda-list to the result list and execute body.</blockquote>
<H2><I> Mini Implementation of CLOS</I>
</H2>
<I> If you don't have CLOS (the Common Lisp Object System) installed,</I>
<I> then this defines a simple version of DEFMETHOD which only</I>
<I> dispatches on the first argument, and works for structures (and</I>
<I> some other types) but not classes. Note that you can still do</I>
<I> (single) inheritance with structures using the :include option.</I>
<I> To properly inform DEFMETHOD of the inheritance tree, you should</I>
<I> use DEFSTRUCTURE rather than DEFSTRUCT. This has the added</I>
<I> benefit of allowing you to write PRINT-STRUCTURE methods rather</I>
<I> than :print-function functions, if you like (they will be</I>
<I> inherited properly, and they don't have the silly DEPTH argument).</I>
<A NAME="defstructure"><P><A HREF="../utilities/cltl2.lisp"><B>defstructure</B></A></A> <I>macro</I> (type-and-args
&rest
slots)
<blockquote>This is just like DEFSTRUCT, except it keeps track of :include types, for
the benefit of METHOD-FOR, and it makes printing go through PRINT-STRUCTURE.</blockquote>
<A NAME="print-structure:t"><P><A HREF="../utilities/cltl2.lisp"><B>print-structure</B></A></A> <I>method</I> ((structure
t)
stream)
<blockquote>Print a structure. You can specialize this function.
It will be called to print anything defined with DEFSTRUCTURE.</blockquote>
<A NAME="defmethod"><P><A HREF="../utilities/cltl2.lisp"><B>defmethod</B></A></A> <I>macro</I> (name
((var
class)
&rest
other-args)
&rest
body)
<blockquote>This version of DEFMETHOD is like the CLOS version, except it only
dispatches on the first argument, and it only handles structures and
some built-in types, not classes.</blockquote>
<A NAME="ensure-generic-function"><P><A HREF="../utilities/cltl2.lisp"><B>ensure-generic-function</B></A></A> <I>function</I> (name)
<blockquote>Define NAME to be a generic function.</blockquote>
<A NAME="supertype"><P><A HREF="../utilities/cltl2.lisp"><B>supertype</B></A></A> <I>function</I> (type)
<blockquote>Find the most specific supertype of this type.</blockquote>
<A NAME="call-method-for"><P><A HREF="../utilities/cltl2.lisp"><B>call-method-for</B></A></A> <I>function</I> (name
type
var
args)
<blockquote>Find the method for this type, following :supertype links if needed.</blockquote>
<A NAME="utilities/test-utilities.lisp"><HR>
<H2>File <A HREF="../utilities/test-utilities.lisp">utilities/test-utilities.lisp</A></H2></A>
<H2><I> Test cases for the basic utilities</I>
</H2>
<HR>
<TABLE BORDER=4 CELLPADDING=4 CELLSPACING=0><tr>
<td> <A HREF="../../aima.html">AIMA Home</A>
<td> <A HREF="../../contact.html">Authors</A>
<td> <A HREF="overview.html">Lisp Code</A>
<td> <A HREF="../../prog.html">AI Programming</A>
<td> <A HREF="../../instructors.html">Instructors Pages</A>
</TABLE>
</BODY>
</HTML>
|
