\documentstyle[11pt,cprog]{article}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\begin{document}
\title{Summary of Ada95 Code\\}
\author
{Mark Allen Weiss\\
School of Computer Science\\
Florida International University\\
University Park\\
Miami, FL 33199}
\date{}
\maketitle
\begin{center}
{\large\bf Abstract}
\end{center}
{\small
This handout lists the source files
for the Ada95 code that updates
the Ada83 code in my text
{\em Data Structures and Algorithm Analysis in Ada},
(Benjamin/Cummings, 1993).
Included in this handout is a brief list of Ada95 changes.
}
%\newpage
\section{Chapter 1}
\begin{itemize}
\item
{\tt fig1\_2.adb}: a simple recursive routine with a test program
\item
{\tt fig1\_3.adb}: an example of infinite recursion
\item
{\tt fig1\_4.adb}: recursive routine to print numbers, with a test program
\item
{\tt fig1\_5.adb}: program that counts the number of lines in a file
\item
{\tt complex\_numbers.ads}: package specification for complex numbers
\item
{\tt complex\_numbers.adb}: package implementation for complex numbers
\item
{\tt complex\_numbers\_test.adb}: test program for complex numbers
\item
{\tt error\_pack.ads}: package specification for error routines
\item
{\tt error\_pack.adb}: package implementation for error routines
\end{itemize}
A few Ada95 features are introduced in the new code.
They are:
\begin{enumerate}
\item
Compilation unit {\tt X} must be placed in a source file
named {\tt X.adb}.
There is a limit of one compilation unit per source file.
\item {\tt Text\_IO} is now {\tt Ada.Text\_IO}.
The same goes for the package {\tt Integer\_Text\_IO}.
\item
For packages, the specification goes in a file with
suffix {\tt .ads}; the body goes in {\tt .adb}.
\item
The trivial package {\tt Error\_Pack} is provided.
\end{enumerate}
Read the supplement: {\em Using GNAT on a Unix system}
provided as part of the courseware.
%\newpage
\section{Chapter 2}
\begin{itemize}
\item
{\tt fig2\_5.adb}: $O( n ^ 3 )$ maximum subsequence sum algorithm
\item
{\tt fig2\_6.adb}: $O( n ^ 2 )$ maximum subsequence sum algorithm
\item
{\tt fig2\_7.adb}: $O( n \log n )$ maximum subsequence sum algorithm
\item
{\tt fig2\_8.adb}: $O( n )$ maximum subsequence sum algorithm
\item
{\tt fig2\_9.adb}: Test program for binary search
\item
{\tt binary\_search.ads}: Specification of generic function {\tt Binary\_Search}
\item
{\tt binary\_search.adb}: Implementation of generic function {\tt Binary\_Search}
\item
{\tt fig2\_10.adb}: Euclid's algorithm, with a test program
\item
{\tt fig2\_11.adb}: Recursive exponentiation algorithm, with a test program
\end{itemize}
Once again, not much is new.
\begin{enumerate}
\item
Complete programs are provided.
\item {\tt Binary\_Search} is written as a generic.
\end{enumerate}
%\newpage
\section{Chapter 3}
\begin{itemize}
\item
{\tt linked\_lists.ads}: Package specification for linked list
\item
{\tt linked\_lists.adb}: Package implementation for linked list
\item
{\tt linked\_lists\_test.adb}: Test program for linked list package
\item
{\tt polynomials.ads}: Package specification for polynomial
\item
{\tt polynomials.adb}: Package implementation for polynomial
\item
{\tt polynomials\_test.adb}: Test program for polynomials
\item
{\tt cursor\_lists.ads}: Package specification for cursor linked list
\item
{\tt cursor\_lists.adb}: Package implementation for cursor linked list
\item
{\tt stack\_array.ads}: Package specification for stack: array version
\item
{\tt stack\_array.adb}: Package implementation for stack: array version
\item
{\tt stack\_list.ads}: Package specification for stack: list version
\item
{\tt stack\_list.adb}: Package implementation for stack: list version
\item
{\tt stack\_test.adb}: Test program for stacks
\item
{\tt queue\_array.ads}: Package specification for queue: array version
\item
{\tt queue\_array.adb}: Package implementation for queue: array version
\item
{\tt queue\_test.adb}: Test program for queues
\end{itemize}
The most important change in this chapter is the
use of the package {\tt Ada.Finalization} to achieve the
equivalent of the C++ constructor and destructor.
There are some other minor changes.
\begin{enumerate}
\item {\tt Make\_Null} is changed to {\tt Make\_Empty}.
\item Lists and stacks that use dynamically allocated memory
are now derived from the abstract tagged
type {\tt Ada.Finalization.Limited\_Controlled}.
This changes the implementation in mostly trivial ways.
For example, {\tt L.Next} is replaced by {\tt L.Header.Next}
in the list code.
A procedure for {\tt Initialize} and {\tt Finalize} is
also written for these packages.
\item {\tt "="} is now overloadable, and so it is used in place
of {\tt Equals}.
\end{enumerate}
Read the supplement: {\em Using Finalization in Ada95}
provided as part of the courseware.
Read the supplement: {\em Using Inheritance for Heterogeneity}
provided as part of the courseware.
Also, as an exercise, make the changes to {\tt Cursor\_Lists}
to allow automatic reclamation of resources.
%\newpage
\section{Chapter 4}
\begin{itemize}
\item
{\tt search\_tree\_package.ads}: Package specification for binary search tree
\item
{\tt search\_tree\_package.adb}: Package implementation for binary search tree
\item
{\tt search\_tree\_package\_test.adb}: Test program for binary search trees
\item
{\tt search\_avl.ads}: Package specification for AVL tree
\item
{\tt search\_avl.adb}: Package implementation for AVL tree
\item
{\tt search\_avl\_test.adb}: Test program for AVL trees
\end{itemize}
The main change here is the incorporation of {\tt Ada.Finalization}.
The changes are:
\begin{enumerate}
\item
Type {\tt Search\_Tree} is
no longer merely an access type.
It is now a derived type from {\tt Ada.Finalization.Limited\_Controlled}.
\item
Consequently, for {\tt Tree\_Node},
the {\tt Left} and {\tt Right} fields
are of type {\tt Tree\_Ptr}.
\item
Consequently, the recursive calls use a nesting technique:
The dispatching routine, such as {\tt Find} calls an internal
recursive {\tt Find}, passing the {\tt Root} as a parameter.
\item
Dispatching routines must be declared in the package specification.
Thus, in the {\tt Search\_Tree} package, function {\tt Height}
is declared in the specification.
\end{enumerate}
%\newpage
\section{Chapter 5}
\begin{itemize}
\item
{\tt open\_hash\_table.ads}: Package specification for separate chaining
\item
{\tt open\_hash\_table.adb}: Package implementation for separate chaining
\item
{\tt open\_hash\_table\_test.adb}: Test program for separate chaining
\item
{\tt closed\_hash\_table.ads}: Package specification for quadratic probing hash table
\item
{\tt closed\_hash\_table.adb}: Package implementation for quadratic probing hash table
\item
{\tt closed\_hash\_table\_test.adb}: Test program for quadratic probing hash tables
\item
{\tt expanding\_closed\_hash\_table.ads}: Package specification for quadratic probing hash table with rehashing
\item
{\tt expanding\_closed\_hash\_table.adb}: Package implementation for quadratic probing hash table with rehashing
\end{itemize}
More of the same.
Finalization and the use of {\tt "="} are the major changes.
The code for quadratic probing fixes a bug in
the textbook.
%\newpage
\section{Chapter 6}
\begin{itemize}
\item
{\tt binary\_heap.ads}: Package specification for binary heap
\item
{\tt binary\_heap.adb}: Package implementation for binary heap
\item
{\tt leftist\_heap.ads}: Package specification for leftist heap
\item
{\tt leftist\_heap.adb}: Package implementation for leftist heap
\item
{\tt priority\_queue\_test.adb}: Test program for priority queues
\end{itemize}
More of the same.
The major change is finalization, and the recursion
makes the changes more complex for the leftist heap.
Most importantly, {\tt Merge} is now handled more carefully.
We need to guarantee that every node is in exactly one tree,
or else finalization will double-dispose.
%\newpage
\section{Chapter 7}
\begin{itemize}
\item
{\tt sorters.ads}: Package specification for a collection of sorting and selection routines
\item
{\tt sorters.adb}: Package implementation for a collection of sorting and selection routines
\item
{\tt sort.adb}: A test program for the {\tt Sorters} package
\end{itemize}
No changes.
%\newpage
\section{Chapter 8}
\begin{itemize}
\item
{\tt disjoint\_sets.ads}: Package specification for disjoint sets
\item
{\tt disjoint\_sets.adb}: Package implementation for disjoint sets
\item
{\tt disjoint\_sets\_test.adb}: A test program for disjoint sets
\end{itemize}
No changes.
%\newpage
\section{Chapter 9}
Graphs are not implemented because only
pseudocode is in the text.
%\newpage
\section{Chapter 10}
\begin{itemize}
\item
{\tt fig10\_38.adb}: Simple matrix multiplication algorithm with a test program
\item
{\tt fig10\_40.adb}: Algorithms to compute Fibonacci numbers
\item
{\tt fig10\_43.adb}: Inefficient recursive algorithm (see text)
\item
{\tt fig10\_45.adb}: Better algorithm to replace {\tt fig10\_43.adb} (see text)
\item
{\tt fig10\_46.adb}: Dynamic programming algorithm for optimal chain matrix multiplication, with a test program
\item
{\tt fig10\_53.adb}: All-pairs algorithm, with a test program
\item
{\tt random\_numbers.ads}: Package specification for uniform random numbers
\item
{\tt random\_numbers.adb}: Package implementation for uniform random numbers
\item
{\tt random\_numbers\_test.adb}: Test program for random number package
\item
{\tt fig10\_62.adb}: Randomized primality testing algorithm, with a test program
\item
{\tt tic\_tac\_alpha.adb}: Tic-tac-toe with alpha-beta pruning, with a marginal test program
\end{itemize}
Changes are minor.
\begin{enumerate}
\item
The constants for the random number generator are
changed slightly because of new research results.
\item
A complete tic-tac-toe program with a skeleton
testing driver is provided.
\end{enumerate}
%\newpage
\section{Chapter 11}
No material is here.
%\newpage
\section{Chapter 12}
\begin{itemize}
\item
{\tt splay\_tree\_package.ads}: Package specification for top-down splay tree
\item
{\tt splay\_tree\_package.adb}: Package implementation for top-down splay tree
\item
{\tt splay\_test.adb}: Test program for splay trees
\item
{\tt red\_black\_tree\_package.ads}: Package specification for top-down red black tree
\item
{\tt red\_black\_tree\_package.adb}: Package implementation for top-down red black tree
\item
{\tt red\_black\_test.adb}: Test program for red black trees
\item
{\tt aa\_tree\_package.ads}: Package specification for AA-tree
\item
{\tt aa\_tree\_package.adb}: Package implementation for AA-tree
\item
{\tt aa\_test.adb}: Test program for AA-trees
\item
{\tt pairing\_heap.ads}: Package specification for pairing heap
\item
{\tt pairing\_heap.adb}: Package implementation for pairing heap
\item
{\tt pair\_test.adb}: Test program for pairing heaps
\end{itemize}
Chapter 12 is present in the second edition of the
Pascal version.
For compatibility, four generic packages are written
that implement the following data structures:
\begin{enumerate}
\item
Top down splay trees
\item
Top down red black trees
\item
AA-trees
\item
Pairing heaps
\end{enumerate}
\end{document}