You should attempt as many as you can of the following tasks. Remember, you must write each function to comply with the specification above, as well as with the instructions given below.
Write MERGE-URLPATH. Use the following algorithm to merge the directories:
If the directory is relative, thenstrip off the :RELATIVE flag and then append to the provided default.elseit is absolute, return it.
Notes: the function is not allowed to modify its arguments destructively. However, the value it returns may share structure with its arguments. You do not need to check that the given default argument is an :ABSOLUTE directory (though you can if you wish).
Write INDEXIFY-URLPATH. The function should destructively modify its argument.
The two parts of this question will receive equal weight when marked.
Write ELIMINATE-BACKS. Your object is to eliminate all pairs of DIRNAME :BACK from the argument dirlist. To do this, prune the list using the following algorithm:
if the list is empty, thenreturn the empty listelseif the second element is :BACK, thenif the first element is not :BACK, thenelsereturn the result of pruning DIRLIST from the third element onwardselsereturn a list: the first element should be :BACK, the second element should be :BACK, and the rest of the returned list should be the result of pruning the argument DIRLIST from the third element onwardsreturn a list: the first element should be the first element of DIRLIST, and the rest of the list should be the result of pruning the rest of the argument DIRLIST
Check the result against the original DIRLIST. If it has not changed, thenreturn the resultelseprune the result recursively by calling ELIMINATE-BACKS on the result
Note: this may not destructively modify its argument. However its return value may share structure with the argument if that is convenient.
Why is it necessary to compare the result of pruning with the argument list, and prune again? The algorithm given is inefficient, because it traverses the argument over and over again until there are no more pairs of DIRNAME :BACK which can be eliminated.
Comment out your original version of ELIMINATE-BACKS. Write another version which uses a more efficient algorithm to eliminate all pairs of DIRNAME :BACK from the dirlist.
Write PRUNE-DIRECTORY. Use ELIMINATE-BACKS to remove any pairs of DIRNAME :BACK from the specification. Then if the path is absolute, strip off any leading chain of :BACKs from the front of the directory list.
Note: this may not destructively modify its argument. However the return value may share structure with its argument if that is convenient.
Write PRUNE-URLPATH. This function must destructively modify its argument.
Write CANONICALIZE-LINK. Call INDEXIFY-URLPATH, MERGE-URLPATH and PRUNE-URLPATH as necessary. This function will destructively modify its argument as it calls destructive functions.
Write STORE-ALL-PAGE-DESCRIPTIONS. This function must destructively modify its tree argument.
Write URLPATH-VALUE-IN-UPT. Note that the specification states that in certain circumstances an error or a warning should be signalled by URLPATH-VALUE-IN-UPT. Use ERROR and WARN to signal these in your version.
Write MAP-UPT-NODES. Hint: You may wish to implement this by defining an auxiliary function with an additional parameter. Note that the argument fn should be called with two arguments; the name of the node and the node itself. This is analogous to the behaviour of MAPHASH. Note also that the name of the given root node is "".
Write URLPATH-DANGLING-LINKS. Follow the specification carefully.
Write UPT-DANGLING-LINKS.
Write UPT-DANGLING-PATH-NAMES. This function will return the names of all the dangling links in a form in which, if printed, you can easily read them on the screen (compare its result to the result of UPT-DANGLING-LINKS).