Monday, February 4, 2019

Stack Abstract Data Type using Ada


The stack Abstract Data Type is one of the simplest data types to create and understand. There are fundamentally two kinds of stack types.
·         bounded stacks which have a pre-determined capacity
·         unbounded stacks which can grow to the limits of computer memory.
Every stack implementation has some common subprograms.
  • ·         Is_Empty – This function returns true if the stack is empty and false if it is not empty
  • ·         Size – A function returning number of elements currently contained by the stack
  • ·         Top – A function returning the top element of a stack that is not empty
  • ·         Push – Push a data element onto the stack
  • ·         Pop – A procedure that pops the top element off the stack, passing the popped element out as a parameter
  • ·         Clear – A procedure that empties the stack
  • ·         Display – A procedure that displays the current contents of the stack

A bounded stack may also have the function Is_Full, which returns true if the stack is full and returns false if it is not full. Notice that Is_Empty is not simply the inverse of Is_Full. A bounded stack with a capacity of 10 elements may contain 0 elements, in which case it is empty, or it may contain some number of elements from 1 through 9, in which case it is neither empty nor full, or it may contain 10 elements, in which case it is full.

Unbounded Stack

Unbounded stacks are commonly implemented as specialized linked lists. Every Push operation results in the dynamic allocation of a new item onto the stack. Every Pop operation results in one item from the stack being freed back to the program heap.
The following implementation of an unbounded stack is defined in an Ada generic package, allowing instances of the unbounded stack to be created containing any data type. 
Ada does provide a pre-defined doubly linked list package as part of its standard container library, but this example re-invents a simple singly linked list to give a complete example of how the unbounded stack can be implemented.

The package specification defines the API for the stack abstract data type:

generic
   type Element_Type is private;
  
   with function Image (Item : in Element_Type) return String;
  
package Unbounded_Stack is
   type Stack is tagged private;

   function Is_Empty (S : in Stack) return Boolean;
  
   function Size (S : in Stack) return Natural;
  
   function Top (S : in Stack) return Element_Type with
     Pre => not S.Is_Empty;
  
   procedure Push (S : in out Stack; Value : in Element_Type) with
     Post => S.Size = S'Old.Size + 1;
  
   procedure Pop (S : in out Stack; Value : out Element_Type) with
      Pre  => not S.Is_Empty,
     Post => S.Size = S'Old.Size - 1;
  
   procedure Clear (S : in out Stack) with
     Post => S.Is_Empty;
  
   procedure Display (S : Stack);
  
private
  
   type Cell;
  
   type Cell_Access is access Cell;
  
   type Cell is record
      Value : Element_Type;
      Next  : Cell_Access;
   end record;

   type Stack is tagged record
      Head  : Cell_Access := null;
      Count : Natural     := 0;
   end record;

end Unbounded_Stack;

The package specification defines two generic parameters which must be specified when an instance of the package is created. The first generic parameter is the data type that the stack will contain. The second generic parameter is a function taking an instance of the stack element type and returning a string representation of the value of that data type.
Several of the functions and procedures have preconditions and/or post-conditions associated with them. These pre and post conditions specify the requirements of those functions and procedures.

Function or Procedure Name
Condition
Description
Top
Pre => not S.Is_Empty
This precondition requires the stack to not be empty before calling the Top function.
Push
Post => S.Size = S'Old.Size + 1
Upon completion of this procedure the size of the stack must increase by 1.
Pop
Pre  => not S.Is_Empty,
Post => S.Size = S'Old.Size - 1
This procedure cannot be called when the stack is empty. Upon completion of this procedure the size of the stack must decrease by 1.
Clear
Post => S.Is_Empty
Upon completion of this procedure the stack will be empty.

The private part of the package specification defines the data types needed to implement a linked list.
The package body contains the implementation of all the functions and procedures defined in the package specification.

with Ada.Unchecked_Deallocation;
with Ada.Text_IO; use Ada.Text_IO;

package body Unbounded_Stack is
   procedure free is new Ada.Unchecked_Deallocation (Cell, Cell_Access);

   --------------
   -- Is_Empty --
   --------------

   function Is_Empty (S : in Stack) return Boolean is
   begin
      return S.Count = 0;
   end Is_Empty;

   ----------
   -- Size --
   ----------

   function Size (S : in Stack) return Natural is
   begin
      return S.Count;
   end Size;

   ---------
   -- Top --
   ---------

   function Top (S : in Stack) return Element_Type is
   begin
      return S.Head.Value;
   end Top;

   ----------
   -- Push --
   ----------

   procedure Push (S : in out Stack; Value : in Element_Type) is
      C : Cell_Access := new Cell;
   begin
      C.Value := Value;
      C.Next  := S.Head;
      S.Head  := C;
      S.Count := S.Count + 1;
   end Push;

   ---------
   -- Pop --
   ---------

   procedure Pop (S : in out Stack; Value : out Element_Type) is
      C : Cell_Access := S.Head;
   begin
      Value   := S.Head.Value;
      S.Head  := S.Head.Next;
      S.Count := S.Count - 1;
      free (C);
   end Pop;

   -----------
   -- Clear --
   -----------

   procedure Clear (S : in out Stack) is
      C : Cell_Access := S.Head;
   begin
      while S.Head /= null loop
         C       := S.Head;
         S.Head  := S.Head.Next;
         S.Count := S.Count - 1;
         free (C);
      end loop;
   end Clear;

   -------------
   -- Display --
   -------------

   procedure Display (S : Stack) is
      C : Cell_Access := S.Head;
   begin
      if S.Is_Empty then
         Put_Line ("The stack is empty.");
      end if;

      for I in 1 .. S.Count loop
         Put_Line (Image (C.Value));
         C := C.Next;
      end loop;
   end Display;

end Unbounded_Stack;

Bounded Stack

The bounded stack is also implemented as a generic package. Instead of using a linked list which can be enlarged with each Push operation, the bounded stack uses an array defined when an instance of the bounded stack is declared.
You will also notice that the Is_Full function has been defined for the bounded stack. Additionally, the Push procedure now has a precondition requiring the stack not to be full when Push is called. The names and interfaces for all other functions and procedures are identical between the bounded stack and the unbounded stack.

generic
  
   type Element_Type is private;
  
   with function Image (Item : in Element_Type) return String;
  
package Bounded_Stack is
  
   type Stack (Size : Positive) is tagged private;

   function Is_Empty (S : in Stack) return Boolean;
  
   function Is_Full (S : in Stack) return Boolean;
  
   function Count (S : in Stack) return Natural;
  
   function Top (S : in Stack) return Element_Type with
     Pre => not S.Is_Empty;
  
   procedure Push (S : in out Stack; Value : in Element_Type) with
      Pre  => not S.Is_Full,
     Post => S.Count = S'Old.Count + 1;
  
   procedure Pop (S : in out Stack; Value : out Element_Type) with
      Pre  => not S.Is_Empty,
     Post => S.Count = S'Old.Count - 1;
  
   procedure Clear (S : in out Stack) with
     Post => S.Is_Empty;
  
   procedure Display (S : in Stack);
  
private
  
   type Buff_T is array (Positive range <>) of Element_Type;
  
   type Stack (Size : Positive) is tagged record
      Buff  : Buff_T (1 .. Size);
      Index : Positive := 1;
      Tally : Natural  := 0;
   end record;

end Bounded_Stack;

The implementation of the bounded stack differs from the unbounded stack because stack elements are never dynamically allocated or de-allocated.

with Ada.Text_IO; use Ada.Text_IO;

package body Bounded_Stack is

   --------------
   -- Is_Empty --
   --------------

   function Is_Empty (S : in Stack) return Boolean is
   begin
      return S.Tally = 0;
   end Is_Empty;

   -------------
   -- Is_Full --
   -------------

   function Is_Full (S : in Stack) return Boolean is
   begin
      return S.Tally = S.Size;
   end Is_Full;

   -----------
   -- Count --
   -----------

   function Count (S : in Stack) return Natural is
   begin
      return S.Tally;
   end Count;

   ---------
   -- Top --
   ---------

   function Top (S : in Stack) return Element_Type is
   begin
      return S.Buff(S.Index - 1);
   end Top;

   ----------
   -- Push --
   ----------

   procedure Push (S : in out Stack;  Value : in Element_Type) is
   begin
      S.Buff(S.Index) := Value;
      S.Tally         := S.Tally + 1;
      S.Index         := S.Index + 1;
   end Push;

   ---------
   -- Pop --
   ---------

   procedure Pop (S : in out Stack; Value : out Element_Type) is
   begin
      S.Tally := S.Tally - 1;
      S.Index := S.Index - 1;
      Value   := S.Buff(S.Index);
   end Pop;

   -----------
   -- Clear --
   -----------

   procedure Clear (S : in out Stack) is
   begin
      S.Tally := 0;
      S.Index := 1;
   end Clear;

   -------------
   -- Display --
   -------------

   procedure Display (S : in Stack) is
   begin
      if S.Tally = 0 then
         Put_Line("The stack is empty.");
      else
         for I in reverse 1..S.Index - 1 loop
            Put_Line(Image(S.Buff(I)));
         end loop;
      end if;
   end Display;

end Bounded_Stack;

Since the API for both the bounded and unbounded stack packages are so similar the use of these packages is very similar.

Using the unbounded stack package


with Ada.Text_IO; use Ada.Text_IO;
with Unbounded_Stack;

procedure Main is

   package Int_Stack is new Unbounded_Stack (Integer, Integer'Image);
   use Int_Stack;

   S : Stack;
   V : Integer;

begin
   Put_Line ("Push 5 values on the stack");

   for I in 1 .. 5 loop
      S.Push (I);
   end loop;
   S.Display;

   Put_Line ("Pop 2 values off of stack");

   for I in 1 .. 2 loop
      S.Pop (V);
      Put_Line ("Popped value" & V'Image);
   end loop;

   S.Display;
   Put_Line ("The top of the stack is" & S.Top'Image);
   S.Clear;
   S.Display;
end Main;

Using the bounded stack package


with Ada.Text_IO; use Ada.Text_IO;
with bounded_stack;

procedure Main is

   package Int_Stack is new bounded_stack (integer, integer'image);
   use Int_Stack;

   S : Stack (10);
   V : Integer;

begin

   Put_Line ("Push 5 values on the stack");

   for I in 1 .. 5 loop
      S.Push (I);
   end loop;

   S.Display;

   Put_Line ("Pop 2 values off of stack");

   for I in 1 .. 2 loop
      S.Pop (V);
      Put_Line ("Popped value" & V'Image);
   end loop;

   S.Display;

   Put_Line ("Push 5 values on the stack");

   for I in 1 .. 5 loop
      S.Push (I);
   end loop;

   S.Display;

   Put_Line ("The top of the stack is" & S.Top'Image);
   S.Clear;
   S.Display;
end Main;

In the bounded stack instance the variable S is declared to be a stack with a capacity of 10 elements. This is done in the line

S : Stack (10);

The (10) sets the Size parameter of the Stack record to 10 for this instance.

at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Comparison of three algorithms for summing an array of integers

This article shares a comparison of the time taken to sum an array of integers. This article tests three algorithms for summing the array. •...

  • Threads of Confusion
    Many programming languages support concurrent behavior through the creation of threads and the explicit manipulation of semaphores, locks or...
  • Comparing Ada and High Integrity C++
    I have often suspected that use of a safety critical or high integrity coding standard for C++ would yield a level of safety and software r...
  • Producer-Consumer Patterns
    Producer-Consumer Patterns The Producer-Consumer pattern is classically defined as two threads or tasks coordinating their behavior thro...