\documentclass{book}
\usepackage{times}
\title{Ada Structured Library\\Release 1.0}
\author{Corey Minyard (minyard@acm.org)}
\date{\today}
\pagenumbering{roman}
\tolerance=9999
\parindent=0pt
\parskip=1em
\begin{document}
\maketitle
\tableofcontents

\chapter*{Preface}
This document describes the Ada Structured Library (ASL or AdaSL), a
set of library routines, frameworks, and container classes for Ada95.
The document describes the following parts of the library:

\begin{itemize}
 \item The Baseclass packages.
 \item The container classes
 \item The general library routines
\end{itemize}

\chapter{Overview of the Baseclass package}
\pagenumbering{arabic}

This package contains the base class used by the rest of the system.
All tagged types should decend from the abstract types defined here.

Two abstract types are defined: Object and Limited\_Object.  Obviously,
Object is not limited and Limited\_Object is.  No other differences
exist.

The base classes each provide three methods:

\begin{description}
\item[To\_String] - Return a string representation for an object.
\item[Get\_Object\_Name] - Return a name for an object.  For debugging
	errors, it is often useful if the object prints its actual
	name so the exact tagged type is known.  All tagged types
	should define one of these functions.
\item[Cast] - A casting operator to allow interfaces and multiple
	inheritance.
\end{description}


\section{The Cast Method}

Ada95 does not include any direct support for multiple inheritance or
interfaces.  However, such support can be easily added to the system
through consistent use of the Cast method.

The base Cast method simple returns the object pointer passed in.  If
the developer wants to create a tagged type with interfaces, they
should create a new tagged type for each interface or subclass.  Then
each interface should override the Cast method and provide the ability
to convert between the various subclasses and interfaces.  It should
also call the parent Cast method for anything it doesn't want to
implicitly handle.

For instance, suppose we have the following interface:

\begin{verbatim}
  with Baseclass;

  package Intf1 is

     type F1 is abstract new Baseclass.Object
       with null record;
     type F1_Class is access all F1'Class;
     type F1_Ptr is access all F1;

     procedure P1 (A : access F1) is abstract;

     function P2 (A : access F1) return String
       is abstract;

  end Intf1;
\end{verbatim}

and another interface:

\begin{verbatim}
  with Baseclass;

  package Intf2 is

     type F2 is abstract new Baseclass.Object
       with null record;
     type F2_Class is access all F2'Class;
     type F2_Ptr is access all F2;

     procedure P3 (A : access F2) is abstract;

     function P4 (A : access F2) return String
       is abstract;

  end Intf2;
\end{verbatim}

and we want to supply an object with both of these interfaces.  We can
create a new tagged type as follows:

\begin{verbatim}
  with Baseclass;
  with Intf1;
  with Intf2;

  package Impl1 is

     type Object is new Baseclass.Object with private;
     type Object_Ptr is access all Object;
     type Object_Class is access all Object'Class;
     subtype Object_Parent is Baseclass.Object;
     subtype Object_Parent_Ptr is Baseclass.Object_Ptr;

     function Cast (To_Cast  : access Object;
                    New_Type : in Ada.Tags.Tag)
                    return Object_Class;

     type Impl1_F1 is new Intf1.F1 with private;
     type Impl1_F1_Ptr is access all Impl1_F1;
     procedure P1 (A : access Impl1_F1);
     function P2 (A : access Impl1_F1) return String;

     type Impl1_F2 is new Intf2.F2 with private;
     type Impl1_F2_Ptr is access all Impl1_F2;
     procedure P3 (A : access Impl1_F2);
     function P4 (A : access Impl1_F2) return String;

  private

     type Object is new Baseclass.Object with record
        My_F1 : Impl1_F1_Ptr;
        My_F2 : Impl1_F2_Ptr;
     end record;

     type Impl1_F1 is new Intf1.F1 with record
        My_Object : Object_Ptr;
     end record;

     type Impl1_F2 is new Intf2.F2 with record
        My_Object : Object_Ptr;
     end record;

  end Impl1;
\end{verbatim}

The above code creates an Object type.  It also creates two other
tagged types that define the interfaces required.  The cast methods
are defined as follows:

\begin{verbatim}
  function Cast (To_Cast  : access Object;
                 New_Type : in Ada.Tags.Tag)
                 return Object_Class is
  begin
     if (New_Type = Intf1.F1'Tag) then
        return Object_Class(To_Cast.My_F1);
     elsif New_Type = Intf2.F2'Tag) then
        return Object_Class(To_Cast.My_F2);
     else
        -- Call my parent's Cast method.
        return Cast(Object_Parent_Ptr(To_Cast),
                    New_Type);
     end if;
  end Cast;
\end{verbatim}

With this cast function, a variable of type Object can be cast to
either of the interfaces using the following syntax:

\begin{verbatim}
  This_F1 := Intf1.F1_Class(Cast(My_Object, F1'Tag));
  This_F2 := Intf2.F2_Class(Cast(My_Object, F2'Tag));
\end{verbatim}

Any methods defined for the new interfaces has access to the main
object for the interfaces.  Obviously, the creation routines
(factories or whatever) should build the structure for the objects to
point to each other.

Note that with this method (unlike Java), it is possible for
interfaces to define code to run.



\chapter{Ada Structured Library Container Classes}

This library contains the Ada Structured Generic Containers (ASGC) and
the Ada Structured Object Containers (ASOC), which is a set of generic
and object container classes that can be used from Ada95 programs.  A
number of general purpose containers are implemented.  These are:

\begin{itemize}
\item Vector
\item Doubly linked list
\item Array List
\item Tree
\item Singly linked list
\item Hash Table
\item Heap
\item Graph
\item Directed Graph (DiGraph)
\item Btree
\end{itemize}

Unlike many other types of containers, these are basic containers that
can be used for a number of functions (stacks, queues, sets, bags,
etc.).  In the author's opinion, those functions can be mapped to many
types of containers, it is the use of the container that defines the
function.

For most of the containers, several implementations are defined.  The
implementation types are:

\begin{itemize}
\item Fixed
\item Expandable
\item Dynamic
\end{itemize}

Each has it's own advantages and disadvantages, discussed later.

Each container defines two public tagged types, Object and Iterator.
As well, each abstract container also defines these types.  The Object
is the actual container.  The Iterator is the object used to iterate
through the items in the container.

Two different package hierarchies are currently defined.  One is the
generic container class library, which defines a set of generic
containers that can contain any type.  Although the contained type may
be any type (tagged or not), containers and iterators are tagged types.

The generic container class library is instantiated with the type in
package Asoc\_Collectible named Object\_Class.  The Asoc\_Collectible
package defines an object and a class pointer to that object.  The
containers are instantiated with the class pointer to the collectible
object, so pointers to tagged types that inherit from
Asoc\_Collectible.Object can be contained using the object container
class library.  All the things contained in a container must be of the
same exact type.

All tagged types defined by the ASGC derive from a single base class
defined in the baseclass package.


\section{Using Generic Containers}

Generic containers exist in a generic package hierarchy.  This means
that the base package (Asgc) is a generic package and thus all it's
children are generic packages.  To instantiate a specific container,
all the packages from the base package to the specific container must
be instantiated.

So, for instance, if we want a sortable fixed vector and an ordered
(not sortable) doubly-linked list both of floating point type, the
following package could be used:

\begin{verbatim}
  with Asgc.Ordered.Sortable.Vector.Fixed;
  with Asgc.Ordered.Dlist.Dynamic;

  package Float_Containers is

     package Float_Base is
       new Asgc(Contained_Type => Float);
     package Float_Ordered is
       new Float_Base.Ordered;
     package Float_Sortable is
       new Float_Ordered.Sortable;
     package Float_Sortable_Vector is
       new Float_Sortable.Vector;
     package FLoat_Ordered_Dlist is
       new Float_Ordered.DList;

     package My_Vector is
       new Float_Sortable_Vector.Fixed;
     package My_DList is
       new Float_Ordered_DList.Dynamic;

  end Float_Containers;
\end{verbatim}

Then we could write a procedure to use these containers:

\begin{verbatim}
  with Float_Containers;
  with Text_IO; use Text_IO;

  procedure Use_Float_Containers is

     package Members renames Float_Containers.Float_Base;
     package Stack
       renames Float_Containers.Float_Ordered;

     My_Members : Members.Object_Class
       := new Float_Containers.My_Vector.Object
              (Size => 10);

     My_Stack : Stack.Object_Class
       := new Float_Containers.My_DList.Object;

     Val : Float;

  begin
     Stack.Push(My_Stack.all, 1.0);
     Members.Add(My_Members.all,
                 Stack.Get_At(My_Stack.all, 1));
     Stack.Push(My_Stack.all, 2.0);
     Members.Add(My_Members.all,
                 Stack.Get_At(My_Stack.all, 1));
     Stack.Push(My_Stack.all, 3.0);
     Members.Add(My_Members.all,
                 Stack.Get_At(My_Stack.all, 1));
  
     while (Stack.Member_Count(My_Stack.all) /= 0) loop
        Stack.Pop(My_Stack.all, Val);
        Put_Line("Popped " & Float'Image(Val));
     end loop;
  end Use_Float_Containers;
\end{verbatim}

This method of instantiating all the packages may seem inconvenient,
but it allows the operations on the container to be as generic as
possible.  For instance, if all you need is generic container
operations, you should cast the type into and Asgc.Object\_Class and
use that particular type for the operations.  This way, you can just
rename the package you are using and you can use a different container
with no other code changes.

It is also recommended that you rename the package to something you
want to use the operation for.  This also gives more flexibility by
renaming the package.  It also lets you name the package what you are
using it for, such as the Stack in the example above.

\section{Storage Management and Containers}

All the containers can use storage management.  Each generic container
has a managed version, with "\_Managed" appended to the end of the
name.  The managed version takes a storage management type and a
storage manager variable as formal generic parameters, it will use
that storage manager for all dynamically allocated data and for all
access types it defines.

Several methods of specifying storage management were considered, and
none of them seemed very good.  The lesser of the evils was chosen.
Some other options considered were:

  Specify the storage manager at object creation - This would involve
  lots of nasty casting and would require a pointer to the storage
  manager (since they are limited types).

  Specify the storage manager on every operation - This is similar
  to above except that the storage manager would have to be held for
  every allocated object so it could be properly deallocated.

  Create a separate package with the storage manager as a required
  discriminant - This requires pretty much complete code duplication
  since all the pointers must have the storage manager specified.

  Pass in a dummy type as a generic parameter and use its storage
  manager - This makes things a little easier, but just seems too
  wierd to use.

The third approach was taken.  Since the code is pre-processed by
scripts anyway, it wasn't a big deal to add a managed version of each
container.

However, I'd really like it to be an optional generic formal
parameter, but there is no way to do this that I could figure out.  If
anyone has any ideas on how to do this, I'm listening...


\section{Container Types}

As mentioned before, the containers come in three different types:

\begin{description}
\item[Fixed] - Fixed containers are defined with a static size (all currently
  implemented containers use an array).  Fixed containers are guaranteed
  to not allocate memory dynamically (unless New\_Iterator is called,
  which will dynamically allocate an iterator).  Fixed containers
  generally take a size discriminant on creation, which is the number
  of element in the container.

\item[Expandable] - Expandable containers are much like fixed containers,
  except that they will expand their size when an item it added when
  they are full.  They will not currently reduce their size (although
  that could feasible be added).  These will only use dynamic allocation
  when they are initially created or when they expand.  Expansion does
  require a copy, so it is not very efficient.  Expandable containers
  generally take two discriminants: an initial size and an amount to
  increase the the container when it is expanded.  The increase amount
  can be zero, then it will behave like a fixed container.

\item[Dynamic] - Dynamic containers use dynamic memory allocation for each
  item in the container.  Dynamic containers do not generally take
  a size discriminant.
\end{description}

The container hierarchy is:

\begin{description}
\item[Asgc] - The base generic container class.  This hold functions that
	are available for all container classes and holds a few
	methods for operating on containers.

\item[Asgc.Ordered] - This package is the base of the package hierarchy
	for packages where each entry has an ordinal value that can
	be addressed.  Ordered types can be used as vectors, lists
	queues, or stacks and have direct support for operations
	for those functions.  All the ordered containers have the
	same interface, the differency lies in the efficiency for
	performing certain operations.

\item[Asgc.Ordered.Sortable] - This package is the base of ordered
	containers whose contained items can be compared using
	\verb|>|, \verb|<|, etc.  Thus they can be sorted.  Otherwise,
	they are exactly like normal ordered containers.  All ordered
	containers are also available as sortable containers.

\item[Asgc.Ordered.Sortable.Vector, Asgc.Ordered.Vector] -
	A variable sized array.  Individual element are
	efficiently addressable, but insertion anyplace but the end
	is not efficient.  Fixed and expandable containers are
	available.

\item[Asgc.Ordered.Sortable.Alist, Asgc.Ordered.Alist] -
	A variable sized array list.  Individual element
	references are efficient (but not as efficient as a vector).
	Insertion is efficient of done at the beginning or at the
	end, but not in the middle.  These make good stacks or queues
	if the maximum size is known or not very much expansion will
	be done.  Fixed and expandable containers are available

\item[Asgc.Ordered.Sortable.Dlist, Asgc.Ordered.Dlist] -
	A doubly linked list.  Insertion at any point
	is very efficient, but direct reference to an element number
	is not very efficient.  Fixed, expandable, and dynamic
	containers are available.  The fixed and exapandable containers
	use array indexes for the next and previous references, so
	copying them is efficient.  They also do not do memory
	allocation for every new element.  Referencing through array
	indexes is slower than direct pointers, though.

\item[Asgc.Tree] - A binary tree.  It may be optionally balance (a balanced
	discriminant determines this).  Fixed, expandable, and dynamic
	containers are available.

\item[Asgc.List] - A singly linked list.  Insertion at any point is efficient
	and referencing the beginning and next values is efficient.
	Searching must be linear and iterators for this container
	cannot back up.  Fixed, expandable, and dynamic containers
	are available.  The fixed and exapandable containers
	use array indexes for the next and previous references, so
	copying them is efficient.  They also do not do memory
	allocation for every new element.  Referencing through array
	indexes is slower than direct pointers, though.

\item[Asgc.Heap] - A heap, ordered so the largest value comes out on
	top.  As usual, insertion and removal or O(log n) operations.
	However, searching for a value in the heap is still O(n).
	Maybe someday another data structure will be laid over the
	heap (perhaps a balanced tree) to make searches quicker.
	Fixed, expandable, and dynamic heaps are available, much like
	trees.  Note that the fixed and expandable structures take
	MUCH less store since their left, right, and up link values
	can be determined by their position in the array; link indexes
	are not needed.  Note that the heap can be made to make the
	smallest value come out on top by reversing the \verb|">"|,
	\verb|"<"|, \verb|">="|, and \verb|"<="| functions passed in
	to the generics.

\item[Asgc.Hash] - A hash table.  A hash function must be provided, and the
	performance of the hash table depends greatly on the performance
	of the hash function.  Note that fixed, expandable, and dynamic
	hash tables do not work quite like other functions.  A fixed
	hash table is a closed hash table with a given size.  An
	expandable hash table is given a size and a maximum fill
	percentage.  If the hash table will exceed the maximum fill
	percentage, it will instead create a new hash table (same size
	as the first) and chain them together, so both will be searched
	for a value.  A dynamic hash table is an open hash table, the
	size of the table is specified.  Note that hash tables can
	optionally hold more than one of the same value if the
	Allow\_Duplicates discriminate is set to True.  The Search and
	Search\_Again functions will efficiently iterate through all
	the values in the table.  A hash function must be supplied
	for hash tables.  The quality of the hash function is very
	important, as well as the size of the hash table chosen.
	Read your data structures book on hash tables for more
	info.

\item[Asgc.Graph] - A graph container.  This container can be used to
	implement arbitrary standard graphs (not directed graphs)
	or directed graphs.  Internally the graph container uses a
	hash table for searching; it unfortunately has to expose some
	of this because it needs a hash table size and a hash function
	to do this, so those must be provided to the generics.  The
	graph container is also a little unusual in that it actually
	has two container types: one for holding the graph nodes and
	one in each node to hold the links.  Each of these may be
	individually chosen to be dynamic, fixed, or expandable,
	giving nine different containers that can be specified.
	Unfortunately, this makes things a little comples to specify.
	A separate section is dedicated to the graph container later
	and talks about how to use it.  As with hash tables, the
	hash function and hash table size are important if the
	search functions are going to be efficient.

\item[Asgc.Btree] - A Btree container.  This implements some variations of
	Btrees with B+ and B* extensions.  Only a dynamic version
	is available.  The other versions were just too hard to do.
	A Btree should be faster than a balanced binary tree for
	most operations, but does not expose its internal tree
	representation.  It has a better worst-case performance
	than a hash table (all operations are logarithmic) but
	worse average performance than a hash table with a good
	hash algorithm.
\end{description}

All the containers are implemented as generic children in their
hierarchy, so to instantiate a generic of a container, the whole
hierarchy up to the required container must be instantiated.  For
instance, to create a dynamic tree if floats, the following would
be used:

\begin{verbatim}
  with Asgc.Tree.Dynamic;

  package Float_Containers is
    new Asgc(Contained_Type => Float);
  package Float_Tree is new Float_Containers.Tree;
  package Float_Dyn_Tree is new Float_Tree.Dynamic;
\end{verbatim}

Notice that the package specified to instantiate a child generic is
the already instantiated parent generic, not the actual container name.


This same hierarchy is defined for object containers, except that the
names are changed from Asgc to Asoc.  The Asoc container's value is
a class pointer to the Object type defined in Asoc\_Collectible.  So
any type that inherits from Asoc\_Collectible.Object can be put into
an Asoc container.  Note that if the values in the container are
going to be compared (searched, sorted, put into a tree, hash table,
etc.) they must be objects with the same tag.  Otherwise, it would
be difficult to compare them since it would raise an exception.

\section{Container Operations}

All containers support the following methods:

\begin{description}
\item[\texttt{Add(O, Val)}] - Add the value "Val" to container "O".  The
	add position may be any location, it depends upon the container.

\item[\texttt{Delete(O, Val)}] - Delete the value "Val" to container "O".
	If a container supports more than one entry of the same value,
	only one of the values is deleted.

\item[\texttt{Member\_Count(O) return Natural}] - Return the number of
	items in the container.

\item[\texttt{"="(O1, O2) return Boolean}] - Compares two containers to
	see if they are equivalent.  The meaning of this varies from
	container to container.  In general, this isn't a very useful
	function for containers with nondeterministic positions (such
	as heaps or hash tables) but works fairly well for trees,
	lists, etc.

\item[\texttt{Verify\_Integrity(O)}] - Performs internal checks on the
	integrity of the container's data structures.  Raises an
	exception if the container has some internal problem.

\item[\texttt{Copy(O) return Object\_Class}] - Make a copy of an object.

\item[\texttt{Set\_Callbacks(O, Cb)}] - Set the callback object for the
	container.  See the section on callbacks for more details.

\item[\texttt{Generic\_For\_All(O)}] - A generic method that will call the
	function specified in the generic for every member in the
	container.  If the container is one with a specified order,
	the members will be processed in order.

\item[\texttt{New\_Iterator(O) return Iterator\_Class}] - Return a
	dynamically allocated iterator for the given object.  Note
	that the value passed in must be a pointer to the object,
	therefore objects that are used with iterators must be able to
	be reference by access.

\item[\texttt{New\_Iterator(O) return Iterator}] - Return an iterator for a
	given container.  This is not a class-wide function, but one
	is provided for every container.  Note that the value passed
	in must be a pointer to the object, therefore objects that are
	used with iterators must be able to be reference by access.

\item[\texttt{Set\_Container(Iter, O)}] - Set the iterator's container.
	When an iterator is just declared, it does not intrinsically
	have a container associated with it.  The container must be
	assigned either by assigning the iterator to another iterator
	or the return value of New\_Iterator or by calling
	Set\_Container.
\end{description}

\subsection{Ordered and Sortable Container Object}

Methods for all ordered and sortable containers follow.  Note that when
using one of the containers for a stack or a queue, the "At" operations
work logically.  Location 1 is the top of the stack, 2 is one under
the top, etc.  Location 1 is the head of the queue, etc.

\begin{description}
\item[\texttt{Add\_At(O, Loc, Val)}] - Add Val at the given location in the
	container.  All members at that location and after in the
	container will be pushed forward one location.

\item[\texttt{Set\_At(O, Loc, Val)}] - Set the value at the given location
	to the specified value.  The Added callback is called for the
	new value then the Deleted value is called for the old value.

\item[\texttt{Get\_At(O, Loc) return Contained\_Type}] - Get the value at
	the specified location.

\item[\texttt{Delete\_At(O, Loc)}] - Delete the specified location.  All
	locations after that location are move one location back.

\item[\texttt{Push(O, Val)}] - Use the container like a stack and push one
	value onto the top of it.

\item[\texttt{Pop(O, Val)}] - Use the container like a stack and pop the
	value off the top of it.

\item[\texttt{Enqueue(O, Val)}] - Use the container like a queue and add
	an entry onto the head of it.

\item[\texttt{Dequeue(O, Val)}] - Use the container like a queue and take
	the tail entry off it.
\end{description}

\subsubsection{Sorting}

Generic sort packages are included for sortable containers.  The
following sort packages are available:

\begin{description}
\item[Asgc.Ordered.Sortable.Bubble\_Sort] - A standard bubble sort.
\item[Asgc.Ordered.Sortable.Quicksort] - A standard bubble sort.
\end{description}

Each of these provides two sort procedures:
\begin{description}
\item[\texttt{Sort(O)}] - Sort the object.  This routine will
	dynamically allocate iterators for its operations.

\item[\texttt{Sort(O, Iter1, Iter2)}] - Sort the object, but use the
	iterators provided instead of allocating them.  The position
	of the iterators is destroyed.
\end{description}


\subsection{Tree Container Object}

No special methods are required for tree containers.  Note that a tree
can never hold more than one of the same value.


\subsection{List Container Object}

List containers add the following methods:

\begin{description}
\item[\texttt{Add\_Head(O, Val)}] - Add the given value to the head of the
	list.

\item[\texttt{Add\_Tail(O, Val)}] - Add the given value to the Tail of the
	list.
\end{description}


\subsection{Heap Container Object}

Heap containers are used to find the Maximum (or minimum) value at the
tree root, so special methods are defined to operate on the root:

\begin{description}
\item[\texttt{Get\_Head(O) return Contained\_Type}] - Return, but do not
	remove the value at the root of the heap.

\item[\texttt{Remove\_Head(O, Val)}] - Return in Val the value at the root
	of the heap then delete it from the heap.
\end{description}


\subsection{Hash Table Container Object}

Hash table containers add no special functions to the basic container
operations.


\subsection{Btree Container Object}

Btree containers add no special functions to the basic container
operations.


\subsection{Graph Container Object}

Graph containers provide the following additional methods:

\begin{description}
\item[\texttt{Set\_Link\_Callbacks(O, Cb)}] - Set the callback object for
	the container.  See the section on link callbacks for more
	details.

\item[\texttt{Add\_Link(O, From, To, Contents, Ignore\_Dup := True)}] - Add
	a link from the "From" value to the "To" value.  If the link
	already exists and Ignore\_Dup is False, an Item\_Already\_Exists
	exception is raised.  If the link already exists and
	Ignore\_Dup is True, the call does nothing.  Otherwise, the
	link is added and the user contents of the link is set to the
	Contents parameter.  Note that this will not change the exists
	contents if the link already exists and duplicates are not
	allowed and Ignore\_Dup is set to True.  Three routine are
	provided in this form, one with two iterators, one with the
	"From" as an iterator and the "To" as a value, and one with
	the "From" as value and the "To" as an iterator.

\item[\texttt{Link\_Exists(O, From, To) return Boolean}] - Returns True if
	a link exists between the elements in the container that
	contain "From" and "To".
\end{description}


\section{Data Storage in Containers}

The data used to maintain a container's data structures is guaranteed
to be unique to the container.  If a container is copied by assignment
or the Copy function, a complete new data structure is allocated to
match the one from the source container.  When a container is destroyed,
all the data structures associated with it are freed automatically.

This does not apply to the values the user supplies the container.
The user may use callbacks to provide a similar function.

Note that for set operations (unions, intersections, etc.) the containers
assume that if a pair of values compare as equal, then they are replaceable,
it doesn't matter which of them is added, removed, etc.  The user must be
careful to honor this semantic if they expect set operations to work
correctly.


\section{Callbacks}

The user may define a callbacks type (inheriting from the Callbacks type
in Asgc) that has methods that will be called when operations are
performed on the values in the container.  The following methods are
provided:

\begin{description}
\item[\texttt{Added(Cb, O, Val)}] - An item was added to the container
	with an explicit add operation of some type (Add, Enqueue,
	etc).

\item[\texttt{Copied(Cb, O, Val)}] - An item was copied from one container
	to another.  this is only called for explicit copies between
	containers, not for copy operations inside the container.

\item[\texttt{Deleted(Cb, O, Val)}] - An item was deleted from the
	container.
\end{description}

The containers are careful to perform the Added method before they
perform the Deleted method if values are being replaced, so it is safe
for the user to keep a reference count in the object to tell how often
it is being used.  Also, the user may replace the object with a new
object, but must be VERY careful to keep the "value" of the object (when
compared) exactly the same as the object being replaced.

These callbacks are primarily intended for automatic storage
reclamation.  So, for instance, the value may be a pointer to some
data structure that the user dynamically allocates and puts in the
container.  The user can add a reference count initialized to zero in
the data structure.  On every Added or Copied call, the user should
increment the reference count.  On every Deleted call, the user should
decrement the reference count and if it reaches zero the value can be
freed.  This removes the difficult operation of freeing memory from
the main body of the user's code (often called ``garbage colletion
lite''.

Another way to do this is to have Added do nothing, Copied make a copy
of the value, and Deleted always free the value.  Since the value it
is passed "in out", the user can modify the value passed in and the
value returned will be put into the new container.

\section{Iterators}

Iterators are objects that hold some position within a container and can
perform operations based upon that position.  This implies, of course,
that containers have some order, but the order is arbitrary and not
always reversable.

Because of the arbitrariness of the order, an operation on a container
that modifies the container's contents will invalidate all iterators
that reference the container, if they are used without their position
being reset an exception will be raised.  If the operation that
modifies the container is performed using an iterator, that specific
iterator will still be valid and will reference the "Next" value in
the container.  The only exception is when the last item in the
container is deleted, the iterator cannot back up and will thus be
invalid.

Iterator operations that move the position of the iterator will
generally return an End\_Marker to tell if the iterator attempted to
move past either end of the container.

When an iterator is created, a class pointer to the base object defined
in Asgc is required.  This means that all containers that need to be
iterated must be dynamically allocated or aliased.  It would be nice
if this was not the case, but it is very difficult to reference one
object from another without a pointer.

Basic methods on iterator are:

\begin{description}
\item[\texttt{Add(Iter, Val)}] - Adds the item to the container the
	iterator references and positions the iterator on the added
	item.

\item[\texttt{First(Iter, Is\_End)}] - Set the iterator position to the
	first item in the container.  If the container is empty, the
	Past\_End will be returned in Is\_End and the iterator will not
	be valid.

\item[\texttt{Next(Iter, Is\_End)}] - Move the iterator to the next item in
	the container.  If the current item is the last item in the
	container, then the iterator will not be modified (it will
	still be positioned on the last item) and Is\_End will be set
	to Past\_End.

\item[\texttt{Delete(Iter, Is\_End)}] - Remove the value reference by the
	iterator from the container.  If the value is the last item in
	the container, Is\_End will be set to Past\_End and the iterator
	will be invalidated.  Otherwise, the iterator will be
	positioned on the item after the deleted item and Is\_End will
	be set to Not\_Past\_End.

\item[\texttt{Is\_Same(Iter1, Iter2) return Boolean}] - Returns True if the
	iterators are positioned on the same location in the same
	container.

\item[\texttt{Get(Iter) return Contained\_Type}] - Return the value at the
	current position of the iterator.

\item[\texttt{Get\_Incr(Iter, Val, Is\_End)}] - Return the value at the
	position of the iterator then move the iterator to the next
	item in the container.  The standard Next() method semantics
	apply to this function, too.

\item[\texttt{"="(Iter1, Iter2)}, \texttt{"="(Iter1, Val)},
	\texttt{"="(Val, Iter1)}] -\\ Normal comparison operations on
	iterators do not compare the iterators themselves but the
	values they reference.

\item[\texttt{Search(Iter, Val, Found)}] - Search for the specified value
	from the beginning of the container.  If the value is found,
	then Found is set to True and the iterator is positioned on
	the position holding that value.  Otherwise, Found is set to
	False and the iterator will be invalid.  The efficiency of
	this operation depends on the specified container.

\item[\texttt{Search\_Again(Iter, Found)}] - Search again for the value at
	the current position of the iterator.  Calling Search() and
	then Search\_Again() until False is returned in Found is
	guaranteed to get all items in the container with the
	specified value.

\item[\texttt{Entry\_Count(O, Val) return Natural}] - Return the number of
	times the specified value is in the container.

\item[\texttt{Union(Dest, O1, O2)}] - Perform a set union of O1 and O2 and
	return the result in Dest.  These values are class pointers to
	object, not straight objects, because iterators must be used
	to work on the containers.  This routine works even if any of
	the containers are the same container.  Note that this is a
	pure set union, if either of the source containers contain
	more than one of the same value then the result of this will
	be invalid or an exception might be raised.

\item[\texttt{Intersection(Dest, O1, O2)}] - Perform a set intersection of
	O1 and O2 and return the result in Dest.  These values are
	class pointers to object, not straight objects, because
	iterators must be used to work on the containers.  This
	routine works even if any of the containers are the same
	container.  Note that this is a pure set intersection, if
	either of the source containers contain more than one of the
	same value then the result of this will be invalid or an
	exception might be raised.

\item[\texttt{Bag\_Union(Dest, O1, O2)}] - Perform a bag union of O1 and O2
	and return the result in Dest.  These values are class
	pointers to object, not straight objects, because iterators
	must be used to work on the containers.  This routine works
	even if any of the containers are the same container.  Since a
	bag can contain multiple of the same value, the destination
	must be able to hold duplicate values.  Otherwise, an
	exception will probably be raised.

\item[\texttt{Bag\_Intersection(Dest, O1, O2)}] - Perform a bag
	intersection of O1 and O2 and return the result in Dest.
	These values are class pointers to object, not straight
	objects, because iterators must be used to work on the
	containers.  This routine works even if any of the containers
	are the same container.  Since a bag can contain multiple of
	the same value, the destination must be able to hold duplicate
	values.  Otherwise, an exception will probably be raised.
\end{description}


\subsection{Ordered and Sortable Container Iterator}

Iterators for ordered and sortable containers have the following
methods:

\begin{description}
\item[\texttt{Last(Iter, Is\_End)}] - Set the iterator position to the last
	position in the container.  Is\_End will be set to Past\_End if
	the container is empty.

\item[\texttt{Prev(Iter, Is\_End)}] - Set the iterator position to the
	previous position in the container.  If the iterator is at the
	first item in the container, the iterator is not modified and
	Is\_End is set to Past\_End.

\item[\texttt{Set\_Loc(Iter, Loc)}] - Set the iterator position to a direct
	location.  If the location is not valid (or the container is
	empty) a Constraint\_Error will be raised.

\item[\texttt{Get\_Loc(Iter) return Natural}] - Return the current direct
	location of the iterator.

\item[\texttt{Is\_After(Iter1, Iter2) return Boolean}] - Return True if the
	position of Iter1 is after the position of Iter2 in the
	container.  The iterators must reference the same container.

\item[\texttt{Is\_Before(Iter1, Iter2) return Boolean}] - Return True if
	the position of Iter1 is before the position of Iter2 in the
	container.  The iterators must reference the same container.

\item[\texttt{"-"(Iter1, Iter2) return Integer}] - Return the difference
	between the location of Iter1 and the location of Iter2.

\item[\texttt{"+"(Iter1, Offset) return Iterator}] - Return a new iterator
	at the given offset from the position of Iter1.  If the
	position goes beyond the range of the container, a
	Constraint\_Error will be raised.

\item[\texttt{"-"(Iter1, Offset) return Iterator}] - Return a new iterator
	at the given offset from the position of Iter1.  If the
	position goes beyond the range of the container, a
	Constraint\_Error will be raised.

\item[\texttt{Swap(Iter1, Iter2)}] - Swap the values at the given
	locations in the iterator.  Note that no callback is called
	for this if the operation occurs in the same container.  If
	Iter1 and Iter2 reference different containers, Added
	callbacks are called for both values on their destination
	containers and then Deleted callbacks are called for the
	source containers.

\item[\texttt{Add\_After(Iter, Val)}] - Add the given value after the
	iterator's current position.  After this operation the
	iterator will be positioned on the newly added value.

\item[\texttt{Add\_Before(Iter, Val)}] - Add the given value before the
	iterator's current position.  After this operation the
	iterator will be positioned on the newly added value.

\item[\texttt{Set(Iter, Val)}] - Set the value of the iterator's position.
	The Added callback is called for the new value then the
	Deleted value is called for the old value.

\item[\texttt{Get\_Decr(Iter, Val, Is\_End)}] - Return the value at the
	position of the iterator then move the iterator to the
	previous item in the container.  The standard Next() method
	semantics apply to this function, too.
\end{description}


Iterators for sortable containers can be compared ordinally, so they
add the following methods.  These comparison methods (as with the
\texttt{"="} operator) compare the values the iterators are positioned at,
not the position of the iterator.

\begin{verbatim}
  ">"(Iter1, Iter2)
  ">"(Iter, Val)
  ">"(Val, Iter)
  "<"(Iter1, Iter2)
  "<"(Iter, Val)
  "<"(Val, Iter)
  ">="(Iter1, Iter2)
  ">="(Iter, Val)
  ">="(Val, Iter)
  "<="(Iter1, Iter2)
  "<="(Iter, Val)
  "<="(Val, Iter)
\end{verbatim}


\subsection{Tree Container Iterator}

Iterators for trees can be used to traverse the tree as a tree.  Note
that the standard iterator methods First and Next will do an in-order
traversal of the tree.

\begin{description}
\item[\texttt{Root(Iter, Is\_End)}] - Move to the root node of the tree.
	If the tree is empty, Is\_End will be set to Past\_End.

\item[\texttt{Left(Iter, Is\_End)}] - Move the iterator to the left subtree
	of the iterators current position.  If the left subtree does
	not exist, Is\_End will be set to Past\_End and the iterator
	will remain in the same position.

\item[\texttt{Right(Iter, Is\_End)}] - Move the iterator to the right
	subtree of the iterators current position.  If the right
	subtree does not exist, Is\_End will be set to Past\_End and the
	iterator will remain in the same position.

\item[\texttt{Up(Iter, Is\_End)}] - Move the the parent of the current
	node.  If the current node is the root node, then Is\_End will
	be set to Past\_End and the position of the iterator will be
	unchanged.

\item[\texttt{Last(Iter, Is\_End)}] - It's as easy to do a reverse in-order
	traversal as a forward in-order traversal, so it is possible
	to go backwards through the tree as well as forwards.  This
	moves to the largest entry in the tree.  If the tree is empty,
	Is\_End will be set to Past\_End;

\item[\texttt{Prev(Iter, Is\_End)}] - Set the iterator position to the
	previous position in the Tree.  If the iterator is at the
	first item in the tree, the iterator is not modified and
	Is\_End is set to Past\_End.

\item[\texttt{Get\_Decr(Iter, Val, Is\_End)}] - Return the value at the
	position of the iterator then move the iterator to the
	previous item in the tree.  The standard Prev() method
	semantics apply to this function, too.
\end{description}

Iterators for tree containers can be compared ordinally, so they
have the following methods.  These comparison methods (as with the
"=" operator) compare the values the iterators are positioned at,
not the position of the iterator.

\begin{verbatim}
  ">"(Iter1, Iter2)
  ">"(Iter, Val)
  ">"(Val, Iter)
  "<"(Iter1, Iter2)
  "<"(Iter, Val)
  "<"(Val, Iter)
  ">="(Iter1, Iter2)
  ">="(Iter, Val)
  ">="(Val, Iter)
  "<="(Iter1, Iter2)
  "<="(Iter, Val)
  "<="(Val, Iter)
\end{verbatim}

\subsection{List Container Iterator}

Iterators for lists add the following methods to the basic iterator
methods:

\begin{description}
\item[\texttt{Add\_After(Iter, Val)}] - Add the given value after the
	iterator's current position.  After this operation the
	iterator will be positioned on the newly added value.

\item[\texttt{Add\_Before(Iter, Val)}] - Add the given value before the
	iterator's current position.  After this operation the
	iterator will be positioned on the newly added value.

\item[\texttt{Set(Iter, Val)}] - Set the value of the iterator's position.
	The Added callback is called for the new value then the
	Deleted value is called for the old value.
\end{description}


\subsection{Heap Container Iterator}

Iterators for heaps add no methods to the basic iterator methods.


\subsection{Hash Table Container Iterator}

Iterators for hash tables add no methods to the basic iterator methods.


\subsection{Btree Container Iterator}

Iterators for Btress add the following methods to the basic iterator
methods:

\begin{description}
\item[\texttt{Prev(Iter, Is\_End)}] - Set the iterator position to the
	previous position in the Btree.  If the iterator is at the
	first item in the tree, the iterator is not modified and
	Is\_End is set to Past\_End.

\item[\texttt{Get\_Decr(Iter, Val, Is\_End)}] - Return the value at the
	position of the iterator then move the iterator to the
	previous item in the tree.  The standard Prev() method
	semantics apply to this function, too.
\end{description}

As well as the following ordinal comparisons are defined:

\begin{verbatim}
  ">"(Iter1, Iter2)
  ">"(Iter, Val)
  ">"(Val, Iter)
  "<"(Iter1, Iter2)
  "<"(Iter, Val)
  "<"(Val, Iter)
  ">="(Iter1, Iter2)
  ">="(Iter, Val)
  ">="(Val, Iter)
  "<="(Iter1, Iter2)
  "<="(Iter, Val)
  "<="(Val, Iter)
\end{verbatim}


\subsection{Graph Container Iterator}

Iterators for graphs can be used like a normal iterator, but have
within them another iterator to iterate over the links a node has.  So
each node in a graph has a set of links that the user may iterate over
with the following special operations.  Note that changing the links
in a node does not invalidate other iterators in the container.  Also
note that if the iterator's node reference is changed, the link
iterator of the iterator is invalidated.

\begin{description}
\item[\texttt{Add\_Link(From, To, Contents, Ignore\_Dup := True)}] - Add a
	link from the "From" iterator to the "To" Iterator.  If the
	link already exists and Ignore\_Dup is False, an
	Item\_Already\_Exists exception is raised.  If the link already
	exists and Ignore\_Dup is True, the call does nothing.
	Otherwise, the link is added and the user contents of the link
	is set to the Contents parameter.  Note that this will not
	change the exists contents if the link already exists and
	duplicates are not allowed and Ignore\_Dup is set to True.

\item[\texttt{Delete\_Link(Iter, Is\_End)}] - Delete the link the iterator
	currently references.  If the last link in the container is
	deleted, Is\_End will be set to Past\_End and the link part of
	the iterator will be set to invalid (the main part of the
	iterator is still valid, though).

\item[\texttt{Find\_Link(From, To) return Iterator}] - Find a link from the
	"From" iterator's node to the "To" iterators node and return
	an iterator that references the link from the "From" iterator.
	So the returned iterator will reference the same node as the
	"From" iterator but the link reference of the iterator will
	reference the link that goes to the "To" iterator.  The "From"
	and "To" iterators must reference the same container.  If the
	link is not found, an Item\_Not\_Found exception will be raised.

\item[\texttt{Find\_Link(From, To, Found)}] - Find a link from the "From"
	iterator's node to the "To" iterators node and move the "From"
	iterator so that its link reference references the link to the
	"To" iterator's node.  If the link is not found, the From
	iterator will not e changed and the Found parameter will be
	set to False.  If the link is found, Found will be set to
	True.  Several versions of this exists with various
	combinations of iterator and contained types.

\item[\texttt{Find\_Link\_Again(From, Found)}] - Search for the next link
	that has the same destination as the current link.  This is
	only useful for graphs that support duplicate links, with this
	function all the links to a specific destination can be found.
	If a link to the same destination is not found, Found will be
	set to False and From will not be modified.  Otherwise, From
	will reference the next link.

\item[\texttt{Link\_Exists(From, To) return Boolean}] - Returns True if a
	link exists from From to To, False if it doesn't exist.
	Several versions of this exists with various combinations of
	iterator and contained types.

\item[\texttt{First\_Link(Iter, Is\_End)}] - Move the link reference for the
	iterator to the first link in the node.  If the node has no
	links, Is\_End will be set to Past\_End and Iter will be
	unchanged.

\item[\texttt{Next\_Link(Iter, Is\_End)}] - Move the link reference for the
	iterator to the next link in the node.  If the iterator
	references the last link in the node, Is\_End will be set to
	Past\_End and Iter will be unchanged.

\item[\texttt{Follow\_Link(Iter) return Iterator}] - Follow the current
	link of "Iter" and return and iterator that reference the node
	the link is to.

\item[\texttt{Follow\_Link(Iter)}] - Set Iter to the node that its link
	references when it is passed in.

\item[\texttt{Link\_Count(Iter)}] - Return the number of links in the node
	the iterator references.

\item[\texttt{Get\_Link(Iter)}] - Return the user data value for the link
	the iterator references.

\item[\texttt{Set\_Link(Iter, Val)}] - Set the user data value for the link
	the iterator references.
\end{description}


\section{Using Graph Containers}

As mentioned before, graph containers are more difficult to create
because of the multitude of options available.  In this example, I
will be using the dynamic graph container, the fixed or expandable
containers may be easily substituted.

A generic graph container takes two formal parameters to instantiate
it, a link container and an iterator for the link container.  These
two parameters must be compatible (you can't use a dynamic link
container with a fixed link iterator, for instance).  The link
container and iterator passed in determine if the graph nodes are
dynamic, expandable, or fixed.

Dynamic graph nodes must be instantiated with a child package named
Asgc.Graph.Dynamic.Links.Dynamic, the names, it contains the types
Graph\_Link and Graph\_Link\_It.  So, to instantiate a dynamic graph
container with dynamic nodes, use something like:

\begin{verbatim}
  package Base is new Asgc(Contained_Type => Integer);
  package Graph_Base is new Base.Graph
    (Do_Hash             => Hash_Integer,
     Link_Contained_Type => Boolean);
  package Dyn_Graph_Base is new Graph_Base.Dynamic;
  package My_Graph_Links is
    new Dyn_Graph_Base.Links.Dynamic;
  package My_Graph is new Dyn_Graph_Base.Graph
    (My_Graph_Links.Graph_Link,
     My_Graph_Links.Graph_Link_It,
     Allow_Duplicate_Links => False);
\end{verbatim}

And My\_Graph will be a package that the graphs can be used from.

Fixed and expandable graph node are more complicated because they have
discriminants that have to be handled.  The user cannot just subtype
some type and constrain a type with a size because that cannot be
passed in as one of the package discriminators for the graph package;
Ada95 does not allow that.  Instead, the user must instantiate a
generic package with the required sizes.  For instance, in the above
example, replace the last two lines with:

\begin{verbatim}
  package My_Graph_Links is
    new Dyn_Graph_Base.Links.Fixed(Size => 20);
  package My_Graph is new Dyn_Graph_Base.Graph
    (My_Graph_Links.Graph_Link,
     My_Graph_Links.Graph_Link_It,
     Allow_Duplicate_Links => False);
\end{verbatim}

or

\begin{verbatim}
  package My_Graph_Links is
    new Dyn_Graph_Base.Links.Expandable
    (Initial_Size => 20, Increment => 30);
  package My_Graph is new Dyn_Graph_Base.Graph
    (My_Graph_Links.Graph_Link,
     My_Graph_Links.Graph_Link_It,
     Allow_Duplicate_Links => False);
\end{verbatim}

For fixed or expandable nodes.

Digraphs are specified by using DiGraph instead of Graph in the last
generic package instantiation.  For instance, taking the first example
above, replacing the last package with the following will make a
digraph:

\begin{verbatim}
  package My_DiGraph is new Dyn_Graph_Base.DiGraph
    (Dynamic_Graph_Link, Dynamic_Graph_Link_It);
\end{verbatim}

Note that, obviously, if you follow a link in a digraph you don't
necessarily have a link back.  Also, since you don't have a link back,
links in to a digraph to not eat up the normal links.  However, there
is a hidden link back to all the links to a node and it is the same
size as the normal links, so a fixed node has a limit on the number of
other nodes that can link to it.

Note that links themselves support having data items on them (like the
Link\_Contained\_Type above).  They are added with Add\_Link and can be
fetched with Get\_Link or modified with Set\_Link.

Also note that duplicate links between nodes can be optionally
supported by setting Allow\_Duplicate\_Links to True as shown above.


\subsection{Creating Your Own Graph Link Nodes}

You can create your own graph link node types if you need some special
properties (for instance, you have a lot of links in each node and it
needs to be more efficient than a linked list).  However, you must be
VERY careful to follow the semantics of the interface carefully.  See
the package Asgc.Graph.Links for details on doing this.


\subsection{Link Callbacks for Graph Containers}

For graph containers, the links themselves carry data values and these
may have callbacks just like regular values in the graph.  See the
Callbacks section for more details.  Since link values are not used by
the container classes, the values on links may be changed arbitrarily,
unlike the main container callbacks.

\emph{IMPORTANT} -- With regular graphs, these functions will be called
TWICE for every link added, deleted, or copied, since the link goes both
directions.  The methods must account for this properly, especially if
they generate a new copy, since each link direction will have a
different copy in that case.  The methods should not assume any
calling order, so doing something like "Odd adds are real and even one
just use the last value" is dangerous.  This does NOT apply to
directed graphs, they will only call the functions once per link since
the links only go one way.



\chapter{General ASL Library Routines}

Some general library routines are defined by the ASL library.  These
are routines that are often used in Ada95 code.

\section{Semaphores}

Ada95 does not define semaphore directly, but they are easily defined
using protected types.  Please don't use semaphores unless you really
need them.  Protected types are much safer and easier to use.
However, if you need to block during an operation, need a wakeup
function that cannot be done with a rendevous, need a counting
semaphore, or need a nested semaphore, these packages are for you.

The package Asl.Semaphore contains an abstract semaphore type that all
semaphores derive from and implement.  It contains the whole interface
to semaphores, with the following methods:

\begin{description}
\item[\texttt{Take(S)}] - Claim the semphore S.  This will block until S
	becomes free and then claims S.

\item[\texttt{Give(S)}] - Release a semaphore so it can be taken again.

\item[\texttt{Try\_To\_Take(S, Success, Timeout)}] - Attempt to take the
	semaphore, but fail the operation if it takes longer than
	Timeout.  If the operation is successful, Success is set to
	True, Otherwise it is False.  Timeout defaults to 0.0.
\end{description}

Four semaphore types are declared in the following packages:

\begin{description}
\item[Asl.Semaphore.Binary] - A standard binary semaphore.

\item[Asl.Semaphore.Counting] - A standard counting semaphore.  The
	initial value is specified when the variable is declared.

\item[Asl.Semaphore.Nested] - A binary semaphore that allows the same
	task to take it multiple times.  The number of claims is
	tracked and the semaphore must be given the same number of
	times.  A Tasking\_Error will be raised if a task other than
	the owner tries to give the semaphore.

\item[Asl.Semaphore.Nested\_Prio] - Like a nested semaphore, but it
	implements a priority inheritance algorithm.  DANGER - These
	semaphores don't work right unless setting the dynamic
	priority of a task sets it immediately.  GNAT doesn't do this
	by under Linux.  I'm thinking of a way to fix it, but nothing
	has come to me yet.
\end{description}


\section{Leak Detection Storage Pool}

Asl.Leak\_Detect\_Pool defines a storage manager that can be used
to detect leaks in your code.  If you specify this storage manager,
it will keep a linked list of all data items that have been allocated
but not freed using it.  After you are done, you can use the storage
manager to iterate over all the elements that have not been freed.
This means, of course, that you must free all your data :-).

The iterator returns an address and a size.  If your system is
deterministic about its memory allocation, you can set a conditional
breakpoint in the Allocate routine of this package right before it
sets the return address that has the leaked address from a previous
run.  Then you can move up stack levels to see where the memory was
allocated.  The same address can be returned again if it is freed, so
be aware that you must catch the last allocation.

\section{Reference Counted Pointers}

Asl.Refcount\_Ptr provides a ``smart'' pointer that automatically
cleans itself up when the last reference to it gets freed.  This way,
a pointer may be duplicated many times throughout the program, but it
will only be freed when the last duplicate is freed.  This way, the
program does not need to keep track of when the pointer is really
freed, only the local users need to track when they are done.  This
only works pointers that cannot point to themself (since in a cyclic
structure the last pointer never goes away).

Asl.Refcount\_Ptr.Managed provides a storage managed version of this.
String versions are already available in Asl.Refcount\_String and
Asl.Refcount\_String.Managed.

\section{String Tokenizer}

Asl.Strings.Tokenizer provides a convenient way to break a string into
pieces using separators (such as spaces and tabs).

\section{Telnet}

Asl.Protocol.Telnet holds a telnet protocol engine that implements the
full RFC 854 and RFC 855 protocol.  It allows options processors to be
plugged in to handle options.

Asl.Protocol.Telnet.Option implements a basic telnet option handler.
It can handle options like echo, binary, and others that are simple.
Other more complex options should descend from this, since it does the
dirty work of option negotiation.  Several options are already
available, including:
\begin{itemize}
\item Asl.Protocol.Telnet.Option.Terminal\_Type
\item Asl.Protocol.Telnet.Option.Window\_Size
\item Asl.Protocol.Telnet.Option.Status
\end{itemize}

Asl.Protocol.Telnet.Stream\_IO implement an Ada stream over telnet.
This is useful with an AdaSockets stream.  Note that currently,
AdaSockets calls to Read are blocking until \emph{all} the items are
read from the stream, so if you want to use telnet over an AdaSockets
you have to read from the stream one element at a time.  A patch
exists that corrects this, but it's hard to know when this will be
applied or if it will ever be applied.

\section{Abstract I/O}

Unfortunately, Ada has no abstract file type like Java has, so you
can't easily create new file types, such as telnet sockets.  You have
streams, but streams have very limited sets of types they can read and
write.  {Asl.Abstract\_IO} attempts to fill this void.  It looks a lot
like {Ada.Text\_IO}, but the file type is abstract.  It provides all
the dirty work of things like {Integer\_IO}, all the real I/O
processors need to provide are the basics.  It has subtle differences
with Ada.Text\_IO, so read the documentation in the package carefully.

Asl.Abstract\_IO.Telnet implements abstract I/O over a telnet stream.

The real and fixed I/O is a rather cheap hack.  It does work, but the
accuracy will suffer.

\section{Security}

Asl.Security provides an abstract mechanism for verifying user names.
No real mechanisms currently exist, the user must supply their own.

\section{Debug Output}

Applications often need some way to optionally generate debug output
upon command.  {Asl.Debug\_Out} provides a framework for this.  The
user creates and registers debug levels with a debug processor.
Through command, the levels may be enabled and disabled.  The user
checks a Boolean in the level, if it is on they should generate
debug output.

Asl.Debug\_Out.Command provides a command processor command that
controls debug levels.

\section{Command Processor}

Asl.Cmdproc provides a small framework that allow a command processor
over an abstract I/O file.  This lets the user bind in commands and
have them executed when the user types in a specific command.  A help
and exit command are already implemented and bound in.

Asl.Cmdproc.Telnet provides a full telnet listener task, you just
provide the port to the task entry, it will give you back the actual
command table it is using, listen for requests, create the command
processors and telnet streams when requests come in.  All you have to
do is bind in your commands.  If you want security, you can pass in a
security handler.  It also creates a debug processor and a debug
command for processing debug output.

\section{Date and Time Utilities}

Asl.Date\_Time provides a fairly complete date and time manipulation package.
It has the following packages:

\begin{description}
\item[Asl.Date\_Time] - Holds the basic types used by all the date and time
	packages.  This also holds some basic utilities for calculating with
	time.
\item[Asl.Date\_Time.Calendar] - Provides a ``Calendar\_Time'' type that can
	be used for date and time manipulation.  This is the basic type the
	users will deal with.
\item[Asl.Date\_Time.Timezone] - The abstract base for timezones.  The timezone
	used by the calendar package must be a subclass of this type.  This
	package also provides a simple timezone with only a GMT offset, no
	daylight savings.  It provides a set of classes for the various
	wierd times that timezones start (last sunday of month, first sunday
	after the 10th day, etc.).
\item[Asl.Date\_Time.Timezone.Simple] - A simple timezone that only has a start
	and a stop time per year.
\item[Asl.Date\_Time.Timezone.Complex] - A timezone based upon the *nix zone
	info file.  It can do pretty much anything you would need, although
	some political entity someplace will probably dream up a way to break
	it.
\item[Asl.Date\_Time.Local] - A package that attempts to determine and set
	the local timezone and to get the current time without having to
	deal with Ada.Calendar.  It currently has a *nix implementation.
\item[Asl.Date\_Time.Register\_Simple\_Timezones] - A procedure that will register
	all the timezones from the Timezones directory (which were stolen from
	glibc-2.2) as simple timezones.
\item[Asl.Date\_Time.Register\_Complex\_Timezones] - A procedure that will register
	all the timezones from the Timezones directory as complex timezones.
\end{description}

As well, a program named Conv\_Zones converts files in the *nix zone
info format into the Register\_Simple\_Timezones and
Register\_Complex\_Timezones procedures.  The complex timezone
procedure is very large, and probably not necessary for most systems.
However, if you need to go back in time and have accurate timezone
information, it's the only way.  If you cannot afford the memory but
need the complex timezones, you probably want to modify the makefile
and zone info files to only include the timezones you need.

To use these package, you must first register the timezones you need,
either by hand or by calling one of the procedures to do this.  Then
you should call the Set\_Local\_Timezone routine in the Local package
to attempt to find the default timezone, or you should set the default
timezone yourself if you need a special one.  If you register
timezones, you \emph{must} register a UTC timezone that has the name
and id set to ``UTC'' and the offset set to zero.

After that, the Calendar\_Time type is what the user primarily deals
with, it is used to compute times, convert between timezones, and do
other time calculations.  It can handle leap seconds, day of week
calculations with different first days of week and daylight savings
time.  It can also convert to/from the standard Ada Time type,
although it might have problems with daylight savings.

\emph{IMPORTANT:} Unlike other calendar packages in other languages, this package
will not normally let you move into invalid times.  So, for instance, if
you set the time to Jan 31, 2001 then add a month, this package will raise
an exception, because Feb 31 is invalid.  If you set the time to April 1 2001
2:30AM CST, it will raise an exception because daylight savings time has
skipped over this particular time.  Leap seconds can also cause problems,
because some minutes has 59 seconds and others have 61 seconds.
You can avoid the exceptions by setting the "Sloppy" flag in the time
calculations, however, the time will be moved to a valid time.  It handles
them the following ways:

\begin{description}
\item[Invalid day of month] - Move to the last day of the month.
\item[Invalid time due to DST] - Add the daylight savings offset (usually an hour).
\item[Invalid time due to leap seconds] - move to the first second of the next minute.
\end{description}

In this case, for instance, if you set the time to April 1 2001 2:30AM CST,
the time will magically migrate to April 1 2001 3:30AM CDT.

If a portable way to transfer time between systems is needed, then
the Portable\_Time type can be used for this.  It is UTC based, thus
can be sent to a remote site in another timezone and be represented
properly.  It can represent a very large range of dates using only
32-bit types.

Also, Calendar\_Time can be converted to and from the standard *nix
timeval for interacting with *nix systems.  If Interfaces.C.long is
only 32-bits, however, this will run out sometime in the year 2038.

The calendar package will work with BC years, even though it seems
kind of silly.  Just remember that there was not year zero, Setting
the year to 0 will be 1BC, -1 will be 2BC, etc.  When printing, 0
will be converted to -1, and so on automatically, so BC years will
print properly with a negative sign.

\section{Reference Counting Pointers}
This provides a reference counting pointer, a primitive garbage collector
for non-cyclic data structures.  This package uses controlled type to
detect when references are created and destroyed.  When an item has
no references left, this package will automatically free the data.
This way, you can create an item and give it to multiple users, they
have to all free it before it will actually be freed.  The packages are:

\begin{description}
\item[Asl.Refcount\_Ptr] - The main package.
\item[Asl.Refcount\_Ptr.Managed] - Another version that uses a user-supplied
	storage pool.
\item[Asl.Refcount\_String] - A string version of the package.
\item[Asl.Refcount\_String.Managed] - A string version that uses a user-supplied
	storage pool.
\end{description}

\end{document}
