To help you see how these different capabilities can work together, I've built a sample package combining these different ideas. You don't need to understand every little nuance at this time, though I've given you enough information to do so. Concentrate on understanding the big picture the first time you read this.
The sample package I've developed is a generic stack package, similar to the example we saw in the section on generics. Now, however, we can use access types to implement an unbounded stack - we no longer need to be limited to any particular size. We will want to permit users to assign stacks to other stacks, so we will use "Ada.Finalization" and implement type Stack as a child of type Controlled so we can control how assignment and finalization occurs (we discussed type Controlled in the last section of lesson 7).
We will have push and pop operations as before. Let's add an "Empty" operation to erase the contents of a stack, and a boolean function "Is_Empty" that will return True if there's no data in the stack. We'll also add an "=" operation that will return True if two stacks are equal (two stacks are equal if they have the same length and contain equal data in the same order).
I recommend that you always consider adding a "swap" operation to reusable data types [Wheeler 1992]; note that swap operation can be implemented very efficiently using access types. A "Length" operation is also defined so you can find how many items are in the stack. Note there's a new type, "Natural". Natural is a predefined subtype of Integer that starts at zero. Since we can't have a negative number of objects on a stack, it's more appropriate to return a Natural than to return an Integer.
When you're implementing an unbounded type you should almost always override the default Adjust and Finalize procedures - if you don't you're probably doing something wrong. If we didn't override Adjust, an assignment would cause two "different" stacks to point to the same data nodes. As a result, any later finalizing we did would affect other stacks, even if they shouldn't. If we didn't override Finalize, we wouldn't Free the data nodes that we should.
Given all that, here is a generic package specification for Generic_Stack:
with Ada.Finalization; use Ada.Finalization; generic type Item is private; -- This is the data type to be stacked. package Generic_Stack is -- This implements a simple generic stack of Items. -- (C) 1996 David A. Wheeler. type Stack is new Controlled with private; -- Stack type. Assignment copies the contents of one Stack into another, -- and might copy each Item in the Stack. -- You can inherit from Stack and overload its controlled operations. type Stack_Access is access all Stack'Class; -- standard access type. function "="(Left : in Stack; Right : in Stack) return Boolean; -- Stacks are equal if lengths equal and each item in order is equal. procedure Swap(Left : in out Stack; Right : in out Stack); -- Swap the contents of the two stacks. procedure Push(S : in out Stack; I : in Item); procedure Pop (S : in out Stack; I : out Item); -- Pop raises Constraint_Error if Is_Empty(Stack). procedure Top (S : in out Stack; I : out Item); -- Top copies, but does not Pop, the topmost element. -- Top raises Constraint_Error if Is_Empty(Stack). procedure Empty(S : in out Stack); -- Empties the given Stack function Is_Empty(S : in Stack) return Boolean; -- True if Empty. function Length(S : in Stack) return Natural; -- returns 0 if Empty -- Permission is granted to use this package in any way you wish under -- the condition that the author (David A. Wheeler) is given credit. -- NO WARRANTIES, EITHER EXPRESS OR IMPLIED, APPLY. private type Stack_Node; type Stack_Node_Access is access Stack_Node; type Stack is new Controlled with record Start : Stack_Node_Access; end record; procedure Adjust(Object : in out Stack); procedure Finalize(Object : in out Stack); end Generic_Stack;
Note the tricky thing that was done here - the node isn't even completely defined in the package! Since the node wasn't passed in or out of anything, we can leave it as an incomplete type definition and complete the definition in the generic package body.
Since it's a generic, we have to instantiate the generic with a specific type to use it. For test purposes, let's instantiate the generic to allow us to stack up Integers:
with Generic_Stack; -- Instantiate a Stack of Integers. package Stack_Int is new Generic_Stack(Integer);
And finally, let's write a short test program to demonstrate using the generic stack:
with Stack_Int; use Stack_Int; procedure Demo_GS is -- Demonstrate the use of the Generic_Stack package by using a -- Stack of Integers. Stack1, Stack2 : Stack; Dummy : Integer; begin Push(Stack1, 1); -- Put 1 onto Stack1. Push(Stack1, 2); -- Put 2 onto the Stack1. Stack2 := Stack1; -- Copy stack1's contents into stack2. Pop(Stack2, Dummy); -- Dummy is now 2. Pop(Stack2, Dummy); -- Dummy is now 1. -- Now Stack2 is empty and Stack1 has two items. end Demo_GS;
The generic package body implements the operations defined by the generic package declaration using access types as we've discussed. Feel free to examine the package body of Generic_Stack, and compare it to its package specification, a sample instantiation (that creates a Stack of Integers), another instantiation (creating a Stack of Stacks of Integers), a short demonstration program, and a longer test program that puts the Stack through its paces.
Can customers of the generic stack package defined above use the Stack_Node_Access type and manipulate the internal structure of the Generic_Stack?
|Go back to the previous section||Skip to the next section||Go up to lesson 12 outline|
David A. Wheeler (firstname.lastname@example.org)
The master copy of this file is at
The master copy of this file is at "http://www.adahome.com/Tutorials/Lovelace/s12sf.htm".