A common data structure is the stack. Think of a stack as a bag. You can place things in a bag, you can take things out of a bag. What sort of things? Anything.
What you put in last, you can take out first. This is commonly abbreviated as LIFO.
In this example and in OopCdaisy, a stack is implemented as a linked list. For the simplicity of it, instead of the usual link-node view, I will take a more recursive perspective.
A stack is a bag that can contain 2 objects. An arbitrary object, and a stack. In fact in C we have the structure :-...
/* the minimal container. Stacks */
typedef
struct
{
objects ancestor;
objects * object;
struct stacks * stack;
} stacks;
Thus the first field of a stack structure are the fields inherited from the base object data type, the second a pointer to an object, and the third is a pointer to a stack.
We then declare the stackType variable which holds the index into the registry for the stack object :-
objectTypes stackType;
And then we must declare the various method variables which hold the index into the VMT.
methods push, pop, isEmpty;
In this example I will only contemplate a very abbreviated list of methods, OopCdaisy itself comes with
lastObject, lastNode, secondLastNode, matchAddress, howMany, pushBottom, popBottom, getBottom, putBottom, search, searchPop, tellAll, tellUntil, tellMin, rotate, concatenate;
in addition to the methods of the base object type.
The external functions corresponding to the methods must also be declared.
stacks * stack_init( stacks * ) ; void stack_done( stacks * ) ; stacks * stack_display( stacks * ) ; stacks * stack_push( stacks * , objects * ); objects * stack_pop( stacks * ) ; int stack_isEmpty( stacks * ) ;
Note that stack_init, stack_done and
stack_display replace the methods inherited from the
parent base object type. As a matter of habit, future proofing, and
often from necessity, it is good policy for a descendants method to
statically invoke the parent method that it is replacing. Clearly it
is also good policy to invoke the parents "init" method before the
descendants initialization starts, and invoke the parents "done"
method at the end of the descendants clean-up code.
The declarations for the object are placed in an include file, so they may be included into the user program and into the file that implements the stack object.
In the file which implements the stack object we must have procedure that registers the stack object in the object registry :-...
void register_stack()
{
/* Register the object type stack, informing OopCdaisy of the object
types existence, ASCII name, parent's name and the amount of memory
each instance uses. In return OopCdaisy allocates a slot in the
VMT for this object type, and returns an index into the VMT in the
variable stackType. OopCdaisy also zero's the count of stack
instances.
*/
register_type( "stack", &stackType, "base", sizeof( stacks));
/* Register each method, informing OopCdaisy of the existence of the
method, and its ASCII name. If a method already in the registry has
the same ASCII name, any such method, whether an a method of an
ancestor or not, then OopCdaisy uses the same index into the VMT
and places it into the variable init. OopCdaisy then places the
address of the function stack_init into the VMT at location
VMT[ stackType][ init].
*/
register_method( stackType, "init", &init, &stack_init);
register_method( stackType, "done", &done, &stack_done);
register_method( stackType, "display", &display, &stack_display);
register_method( stackType, "push", &push, &stack_push);
register_method( stackType, "pop", &pop, &stack_pop);
}
To simplify life, (this is the standard dummy end node trick), the object in the topmost bag is never there. Its merely for convenience. The result is that stacks / single-link nodes etc are all the same beast, there is no special case for push and popping the last object, the user's pointer doesn't have to be modified, and a nice uniform recursive view of stacks within stacks can be maintained.
In the file that implements the stack object type the methods are defined :-...
stacks * stack_init( stacks * self)
{
/* stackCheck is a macro that checks that the object pointed to by
self exists, is writable, and that its type is, or is a descendant
of, the type stack. If not it signals that the typeGuard has failed
and in which routine.
*/
stackCheck( self, "stack_init" );
/* Initialize the stack object. */
self->object = 0;
self->stack = 0;
return self;
/* This "return self" is vital. This is the means by which the address
of the object created by new is returned to the user.
*/
}
/**************************************************/
/* Method to remove all objects from a stack.*/
stacks * stack_empty( stacks * self)
{
stackCheck( self, "stack_empty" );
while (!tell(self, isEmpty)) tell( self, pop);
return self;
}
/**************************************************/
/* Here is a nice debatable issue. What does a "container" library
procedure do when told that the user is finished with a container
object and the container is not empty?
1) Give error message and die.
2) Remove all objects from container and then deallocate container.
3) Destroy all objects in the container and then the container itself?
4) Don't worry, be happy.
I have chosen to Raise an information grade error condition, Empty the
container, and then deallocate the container.
*/
void stack_done( stacks * self)
{
stackCheck( self, "stack_done" );
if( ! tell( self, isEmpty) )
{
LIB$SIGNAL( STK_STKNOTEMPTY, 0, /* Info grade message only. */
STK_WHERE, 2, AD( "stack_done" ) );
tell( self, empty);
}
base_done( self); /* Tell daddy */
}
/**************************************************/
/* Brown paper bag display method. Uses Daddies display method to show
self. Then tell everybody inside to display self. Cute.
*/
stacks * stack_display( stacks * self )
{
stackCheck( self, "stack_display" );
base_display( self);
tell( self, tellAll, display, 0);
return self;
}
/**************************************************/
stacks * stack_push( stacks * self, objects * object)
{
stacks * bag; /* Local pointer */
stackCheck( self, "stack_push" );
validateObjectPtr( object, baseType, "stack_push", STK_OBJECTPTR);
/* Local pointer set to point at new object on heap. */
bag = new( stackType, init);
/* New object worked into linked list. Don't need to worry about end
cases thanks to dummy node. */
bag->stack = self->stack;
bag->object = object;
self->stack = bag;
/* OopCdaisy stylistic note. Always try to return something useful,
like the self pointer.
*/
return self;
}
/**************************************************/
objects * stack_pop( stacks * self )
{
objects * object;
stacks * bag;
stackCheck( self, "stack_pop" );
bag = self->stack;
if( bag == 0)
LIB$SIGNAL( STK_UNDERFLOW, 0, STK_WHERE, 2, AD( "stack_pop" ) );
validateObjectPtr(
bag, stackType, "stack_pop", STK_BADBAG );
object = bag->object;
self->stack = bag->stack;
/* We are about to get rid of a stack object, but stack_Done always
empties stacks first, so make this stack object empty, or the rest
of the stack will disappear.
*/
bag->stack = 0;
tell( bag, done);
return object;
}
Here follows an exceedingly simple and useless program that creates two objects, stuffs them into a bag, displays them, and then destroys the objects in sundry manners :-
#include oopdir:oops
#include oopdir:stack
#include oopdir:2d
main()
{
points * point;
lines * line;
stacks * bag;
register_init();
register_stack();
register_point();
/* Note : Parent types, (such as point), must be registered before
descendant types such as line. */
register_line();
point = new( pointType, init, 1.0, 2.0);
line = new( lineType, init, 1.0, 1.0, 3.0, 4.0);
bag = new( stackType, init);
tell( bag, push, point);
tell( bag, push, line);
tell( bag, display);
/* Remove and destroy the line. */
tell( tell( bag, pop), done);
/* Destroys all objects in the bag and then destroys the bag. */
tell( bag, destroy);
registry_done();
}
| Previous | The End | Contents |