Section 12.2 - Using Access Variables to Create Unbounded Types

Let's imagine that we want to create a long list of Integer values, and we don't know exactly how many Integer values will be in the list when we set up the list. A type that can store varying amounts of information with no fixed limit is called an unbounded type. Arrays can be used to create a list of values if you know how many (at most) could be in the list, but arrays alone are not enough for easily implementing unbounded types.

You can implement Ada types that handle unbounded amounts of information using access types (access types are useful for other situations too, but this is certainly one of their uses). The basic idea is to create a type called a "node" that stores both:

  1. a single piece of the data you want to handle and
  2. one or more access values referring to related nodes. You can use the access values to "connect" your pieces of data together.

Let's start simply and define something that could handle a list of Integers (technically this example is a singly linked list of Integers). Let's create a "Node" type that can hold one piece of data - an Integer - and a reference referring to the "Next" node in the list.

  type List_Node is
    record
      Data        : Integer;
      Next        : List_Node_Access;  -- Next Node in the list.
    end record;

To create a List_Node we'll need an access type; I'm calling it List_Node_Access. Here's the definition of List_Node_Access (you have to put this before the declaration of List_Node):

  type List_Node_Access is access List_Node;

Now we have a problem. Type List_Node depends on the definition of type List_Node_Access, but type List_Node_Access depends on the definition of type List_Node. Note the circularity - each type's definition depends on the other. This is a common situation when using access types. By Ada rules, you have to declare something before you can use it, and this would appear insoluable. The way to solve this is to first use an ``incomplete type declaration'' for the node (this is the same thing you'd do in C or Pascal). An incomplete type declaration simply promises the Ada compiler that the given type with the given name will be defined later. An incomplete type declaration has the keyword "type", the name of the type that you plan to declare later, and an immediately following semicolon. For example, here's how you'd define the types List_Node and List_Node_Access:

  type List_Node;  -- An incomplete type declaration.
  type List_Node_Access is access List_Node;
  type List_Node is
    record
      Data        : Integer;
      Next        : List_Node_Access;  -- Next Node in the list.
    end record;

After defining an access type, you can then declare variables of access types using the normal variable declaration syntax. For example, you can create two access variables named Current and Root by declaring them as follows:

  Current, Root : Tree_Access;


Quiz:

Is the following true or false?

A way to implement unbounded types is to define a record (often called a "node") that stores (1) a piece of data and (2) one or more access values to connect that piece of data to another related piece of data. Thus, access types can be used to create data types that hold an "unbounded" amount of information.

  1. True
  2. False

You may also:

PREVIOUS Go back to the previous section

NEXT     Skip to the next section

OUTLINE  Go up to lesson 12 outline

David A. Wheeler (dwheeler@dwheeler.com)

The master copy of this file is at "http://www.adahome.com/Tutorials/Lovelace/s12s2.htm".