A tiny little integer stack package from a novice.

A tiny little integer stack package from a novice.

[Stapler]

I just coded up this stack package. The type system is alot simpler than
in the past. I want to get the core logic right before I start adding
features to it.

As a newbie, I would appreciate any critiques the more experienced among
you might have to offer. Although I call it a stack, it's more like a
fixed buffer, a psuedo-stack if you will.

with Ada.Unchecked_Deallocation;
generic

	Size : Positive;
		
package int_stack is
	
	type Int_Stack is limited private;
	type Stack_Ptr is limited private;
	
	procedure Push(X : in Integer);
	procedure Free_Stack;
	
	function Pop return Integer;
	
private

	
	type Int_Stack is array(1..Size) of Integer;
	type Stack_Ptr is access all Int_Stack;
	The_Stack : Stack_Ptr := new Int_Stack;	-- Provides access for De-allocation of entire stack
						-- Is also the sole allocation point for this package.
	procedure Free is new Ada.Unchecked_Deallocation(Int_Stack, Stack_Ptr);
	
end int_stack;
	


package body int_stack is 
	
	Counter : Positive := 1;
	
	procedure Push(X : in Integer) is
	
	begin
	
		The_Stack.all(Counter) := X;
		
		Counter := Counter + 1;
		
	end Push;
	
	procedure Free_Stack is
	
	begin
	
		Free(The_Stack); -- I'm learning to make the commands 
						 -- self-explanatory here. Heh.
		
	end Free_Stack;
		
	function Pop return Integer is
	
		X : Integer := 0;
		
	begin
		Counter := Counter - 1; -- The Counter op is placed here because
								-- the Counter variable will point to 1 element
								-- past the end of the array on the first
								-- call.
		X := The_Stack(Counter);
		
		return X;
		
	end Pop;
	
end int_stack;

And here is the first full test program, which will expanded.

with int_stack;
with Ada.Text_IO;
procedure test_int_stack is

	Bar_Int : Integer := 0;
	S_Size : Positive := 10000;

	package My_Stack is new int_stack( Size => S_Size);
	use My_Stack;	
begin

	for J in 1..S_Size loop
	
		Ada.Text_IO.Put_Line("Pushing "&J'img&" onto the stack.");
		
		Push(J);
		
	end loop;
	
	Ada.Text_IO.New_Line;
	
	for H in 1..S_Size loop
	
		Bar_Int := Pop;
		
		Ada.Text_IO.Put_Line("Got "&Bar_Int'img&" from the stack.");
		
	end loop;
	
	Free_Stack;
	
end test_int_stack;

Gmem reports no memory leaks. But seeing as there is only a single
allocation and de-allocation here, that's really nothing to get excited
about.

Any features I should add on to make it more useful? I'm gonna be funning
around with this package for a while to see where it breaks down, so I'll
have plenty of time to plan new stuff.

More importantly, I'm looking for places this thing breaks.

Any advice would be greatly appreciated.

Stapler.

Re: A tiny little integer stack package from a novice.

[Grein, Christoph]

> with Ada.Unchecked_Deallocation;
> generic
> 
> 	Size : Positive;
> 		
> package int_stack is
> 	
> 	type Int_Stack is limited private;
>	type Stack_Ptr is limited private;

Why are these two types visible? There is nothing one can do with them.
A user or your package can declare variables of those types, but they will never 
be used by your package.

> 	
> 	procedure Push(X : in Integer);
> 	procedure Free_Stack;

Once you've called Free_Stack, you can never again use it. Is this really what 
you want?


> 	function Pop return Integer;
> 	
> private
> 
> 	
> 	type Int_Stack is array(1..Size) of Integer;
> 	type Stack_Ptr is access all Int_Stack;
> 	The_Stack : Stack_Ptr := new Int_Stack;	-- Provides access for 
De-allocation of entire stack
> 						-- Is also the sole allocation 
point for this package.
> 	procedure Free is new Ada.Unchecked_Deallocation(Int_Stack, Stack_Ptr);

Why do you use dynamic allocation? There are other possibilities.


> end int_stack;
> 	
> 
> 
> package body int_stack is 
> 	
> 	Counter : Positive := 1;
> 	
> 	procedure Push(X : in Integer) is
> 	
> 	begin
> 	
> 		The_Stack.all(Counter) := X;
> 		
> 		Counter := Counter + 1;
>

What about overflow here or underflow below?
	
> 	end Push;
> 	
> 	procedure Free_Stack is
> 	
> 	begin
> 	
> 		Free(The_Stack); -- I'm learning to make the commands 
> 						 -- self-explanatory here. Heh.
> 		
> 	end Free_Stack;
> 		
> 	function Pop return Integer is
> 	
> 		X : Integer := 0;
> 		
> 	begin
> 		Counter := Counter - 1; -- The Counter op is placed here because
> 								-- the Counter 
variable will point to 1 element
> 								-- past the end 
of the array on the first
> 								-- call.
> 		X := The_Stack(Counter);
> 		
> 		return X;
> 		
> 	end Pop;
> 	
> end int_stack;

There is mnre to say, but suffice this for the moment. I think when you ponder 
about the above, you'll see further enhancement possibilities.

Re: A tiny little integer stack package from a novice.

[Matthew Heaney]

Stapler <spam.magnet@yahoo.com> wrote in message news:<S9kE9.106573$__1.63580@rwcrnsc51.ops.asp.att.net>...
> generic
> 
> 	Size : Positive;
> 		
> package int_stack is
> 	
> 	type Int_Stack is limited private;
> 	type Stack_Ptr is limited private;
> 	
> 	procedure Push(X : in Integer);
> 	procedure Free_Stack;
> 	
> 	function Pop return Integer;
> 	
> private
> 
> 	
> 	type Int_Stack is array(1..Size) of Integer;
> 	type Stack_Ptr is access all Int_Stack;
> 	The_Stack : Stack_Ptr := new Int_Stack;	-- Provides access for De-allocation of entire stack
> 						-- Is also the sole allocation point for this package.
> 	procedure Free is new Ada.Unchecked_Deallocation(Int_Stack, Stack_Ptr);
> 	
> end int_stack;


Why is this a generic package?  Why isn't this an abstract data type?

If the stack has a fixed, maximum size, it's easier to simply declare
it as a discriminated record, which avoids all the headaches
associated with memory allocation.  For example:

package Integer_Stacks is

   pragma Pure (Integer_Stacks);

   type Stack_Type (Size : Natural) is limited private;
...
private

   type Integer_Array is array (Positive range <>) of Integer;

   type Stack_Type (Size : Natural) is
      limited record
         Elements : Integer_Array (1 .. Size);
         Top      : Natural := 0;
      end record;

end Integer_Stacks;

Re: A tiny little integer stack package from a novice.

[Stapler]

On Mon, 25 Nov 2002 12:31:57 -0500, Matthew Heaney wrote:


> 
> Why is this a generic package?  Why isn't this an abstract data type?

  Good question. Good point. As I said, I'm a real newb, so I hadn't
really considered using an abstract data type. That makes sense.

> If the stack has a fixed, maximum size, it's easier to simply declare it
> as a discriminated record, which avoids all the headaches associated
> with memory allocation.  For example:
> 

Good thinking. I'm reworking the package as per your advice and that of
Mr. Grein in an earlier post.

It's gonna look so much better.


Stapler

Re: A tiny little integer stack package from a novice.

[Jeffrey Carter]

Stapler wrote:
> 
> As a newbie, I would appreciate any critiques the more experienced among
> you might have to offer. Although I call it a stack, it's more like a
> fixed buffer, a psuedo-stack if you will.

It looks exactly like a stack to me.

This is an example of a package-as-object implementation. There's 
nothing wrong with this approach, but it's often easier for the client 
to use an ADT.

> 
> with Ada.Unchecked_Deallocation;
> generic
> 
> 	Size : Positive;
> 		
> package int_stack is
> 	
> 	type Int_Stack is limited private;
> 	type Stack_Ptr is limited private;

Why are these visible to the client?

> 	
> 	procedure Push(X : in Integer);
> 	procedure Free_Stack;

Why is Free_Stack visible to the client?

> 	
> 	function Pop return Integer;
> 	
> private
> 
> 	
> 	type Int_Stack is array(1..Size) of Integer;
> 	type Stack_Ptr is access all Int_Stack;
> 	The_Stack : Stack_Ptr := new Int_Stack;	-- Provides access for De-allocation of entire stack
> 						-- Is also the sole allocation point for this package.
> 	procedure Free is new Ada.Unchecked_Deallocation(Int_Stack, Stack_Ptr);

Why are these here rather than in the body?

> 	
> end int_stack;
> 	
> 
> 
> package body int_stack is 
> 	
> 	Counter : Positive := 1;
> 	
> 	procedure Push(X : in Integer) is
> 	
> 	begin
> 	
> 		The_Stack.all(Counter) := X;
> 		
> 		Counter := Counter + 1;
> 		
> 	end Push;

What happens if Counter > Size?

> 	
> 	procedure Free_Stack is
> 	
> 	begin
> 	
> 		Free(The_Stack); -- I'm learning to make the commands 
> 						 -- self-explanatory here. Heh.
> 		
> 	end Free_Stack;
> 		
> 	function Pop return Integer is
> 	
> 		X : Integer := 0;
> 		
> 	begin
> 		Counter := Counter - 1; -- The Counter op is placed here because
> 								-- the Counter variable will point to 1 element
> 								-- past the end of the array on the first
> 								-- call.
> 		X := The_Stack(Counter);

What happens if Counter < 1?

> 		
> 		return X;
> 		
> 	end Pop;
> 	
> end int_stack;

There doesn't seem to be any need for access types for a bounded stack.

You might want to add such operations as Is_Empty, Is_Full, and Length 
to the package.

I suggest you consider how you could implement the following 2 packages:

generic -- Int_Stack
    Size : Positive;
package Int_Stack is
    Overflow : Exception;

    procedure Push (Value : in Integer);
    -- Adds Value to the top of the stack
    -- Raises Overflow if the stack contains Size values

    Underflow : Exception;

    function Pop return Integer;
    -- Removes the top value from the stack and returns it
    -- Raises Underflow if the stack is empty
end Int_Stack; -- No private part

package Int_Stack is
    type Stack (Size : Positive) is limited private;

    Overflow : exception;

    procedure Push (Onto : in out Stack; Value : in Integer);
    -- Adds Value to the top of Onto
    -- Raises Overflow if Onto contains Onto.Size values

    Underflow : exception;

    procedure Pop (From : in out Stack; Value : out Integer);
    -- Removes the top value from From and assigns it to Value
    -- Raises Underflow if From is empty
private -- Int_Stack
    type Int_Array is array (Positive range <>) of Integer;

    type Stack (Size : Positive) is limited record
       Top   : Natural := 0;
       Value : Int_Array;
    end record;
end Int_Stack;

-- 
Jeff Carter
"Death awaits you all, with nasty, big, pointy teeth!"
Monty Python & the Holy Grail

Re: A tiny little integer stack package from a novice.

[tmoran]

>There doesn't seem to be any need for access types for a bounded stack.
  As given the stack necessarily uses dynamic allocation - the user
has no choice.  If the stack was a simple declaration, the user would
have the option of simply declaring objects of type stack, or he
could do his own dynamic allocation.