Double Sided Stack Class

[stfuji]

Current as of 11/18/2004

<?php

############################################################
############################################################
##  Class:  double stack
##			double sided stack
##
##	November 16, 2004
##	Geoffrey DeFilippi
##  Thanks to:
##		PHP Builder & Weedpacket
##	
##	Methods:
##		push..........Push an element onto the stack
##		pop...........Pop an element off the stack
##		rpush.........Push an element onto bottom of stack
##		rpop..........Pop an element off bottom of stack
##		peek..........Get value of top element of stack without removing it from the stack
##		rpeek.........Get value of bottom element of stack without removing it
##		dump..........Output Stack from top down delimited by a delimiter
##		rdump.........Output Stack from bottom up delimited by a delimiter
##		emptyStack....Empty the stack of all entries
##		_count........Return number of entries in stack
##		_isEmpty......Is the stack empty? Boolean
############################################################
############################################################

////////////////////////////////////////////////////////////
//  DEFINE INSTALLATION VARIABLE
define( "INSTALLED_DOUBLE_STACK", 1);

////////////////////////////////////////////////////////////
// START CODE

class double_stack {

var $dstack = array();

//  Constructor
function double_stack() {
}

//  Push an element into the top of the stack
function push( $element ) {
	array_push( $this->dstack, $element );
}

//  Pop an element from the top of the stack
//  returns NULL on empty
function pop() {
	return array_pop( $this->dstack );
}

//  Push an element into bottom of stack
function rpush( $element ) {
	array_unshift( $this->dstack, $element );
}

//  Pop an element from the bottom of the stack
function rpop() {
	return array_shift( $this->dstack );
}

//  View or return without taking out of the stack the top element
function peek() {
	return $this->dstack[ count( $this->dstack ) - 1 ];
}

//  View or return the bottom element of the stack
function rpeek() {
	return $this->dstack[0];
}

//  Output stack as a string delimited by delimiter top to bottom
function dump( $delimiter = "," ) {
	return implode( array_reverse( $this->dstack ), $delimiter );
}

//  Reverse output stack as a string delimited by delimiter bottom to top 
function rdump( $delimiter = "," ) {
	return implode( $this->dstack, $delimiter );
}

//  Clear the current stack of all elements
function emptyStack() {
	unset( $this->dstack );
	$this->dstack = array();
}

//  Return current size of stack
function _count() {
	return count( $this->dstack );
}

//  Is stack Empty?
function _isEmpty() {
	if ( $this->_count() == 0 || $this->_count() == NULL ) {
		return true;
	} else {
		return false;
	}
}
}

?>

Prefix Stack Class (Extension of Double Stack)

<?php

############################################################
############################################################
##  Class:  prefix_double_stack
##		Prepends a prefix to any added elements of a double stack
##
##  Extends Double Stack Class
##
##	November 16, 2004
##	Geoffrey DeFilippi
##
##	Methods:
##		push..........Push an element onto the stack (with prefix)
##		pop...........Pop an element off the stack
##		rpush.........Push an element onto bottom of stack (with prefix)
##		rpop..........Pop an element off bottom of stack
##		peek..........Get value of top element of stack without removing it from the stack
##		rpeek.........Get value of bottom element of stack without removing it
##		dump..........Output Stack from top down delimited by a delimiter
##		rdump.........Output Stack from bottom up delimited by a delimiter
##		emptyStack....Empty the stack of all entries
##		_count........Return number of entries in stack
##		_isEmpty......Is the stack empty? Boolean
############################################################
############################################################

////////////////////////////////////////////////////////////
//  CHECK CLASS DEPENDANCIES
//

//  DEPENDANT CLASSES
if( !( defined( 'INSTALLED_DOUBLE_STACK' ) ) ) {
	die( 'DEPENDANCY NOT LOADED: Class: double_stack.class.php' );
}

////////////////////////////////////////////////////////////
//  DEFINE INSTALLATION VARIABLE
define( 'INSTALLED_PREFIX_STACK', 1 );

////////////////////////////////////////////////////////////
//  START CODE

class prefix_double_stack extends double_stack {

var $prefix = "";

//  Class constructor accepts a prefix
function prefix_double_stack( $prefix = "" ) {
	$this->prefix = $prefix;
}

//  Push an element into the top of the stack
function push( $element ) {
	array_push( $this->dstack, $this->prefix . $element );
}

//  Push an element into bottom of stack
function rpush( $element ) {
	array_unshift( $this->dstack, $this->prefix . $element );
}

}

/*  Nov 24,2004 Fixed error in constructor of prefix double stack class (had an extra _ in the constructor i.e. what should have been function prefix_double_stack was function prefix__double_stack) */
?>

[Weedpacket]

array_push, array_pop, array_shift, and array_unshift might simplify the code a bit.

A couple of (inessential, but useful) methods would be peek() and rpeek(), which just return the relevant items without removing them - otherwise, the only way to just look at the ends of the dequeue would be to take them out, look at them, and then put them back again.

[stfuji]

Lesson 1: Read the documentation
Lession 2: Don't reinvent the wheel.

Thanks for the suggestions. PHP already did / does what I intended in my code so the update is:

SEE FIRST POST FOR CURRENT VERSION

The peek / rpeek was a great addition thanks again,

Geoffrey

[stfuji]

SEE FIRST POST FOR CURRENT VERSION

A class extension

SEE FIRST POST FOR CURRENT VERSION

[planetsim]

Havent had a chance to play with the class or extension but from observation you seem to have an alright little class there, following weedpackets ideas make the class efficient.

My only concern is this

    function rpeek() {
        return $this->dstack[0];
    } 

This may work for now, yes it will in most cases however to make this truly reusable put quotes around the 0

[laserlight]

This may work for now, yes it will in most cases however to make this truly reusable put quotes around the 0

hmm... but isnt it supposed to be a numeric index anyway?

[Weedpacket]

What is your convention on the mapping between classes and files? I'm strongly considering a one-class/one-file standard:

require_once('superclass.php');
require_once('some_interface.php');

class some_class extends superclass implements some_interface
{
...
}

(or at least, limiting a file to near-identical siblings with identical dependencies).

That skips the need for defines or calls to class_exists(), and makes immediate dependencies explicit (something I'm speculating might come in handy for something like documentation post-processing or maybe even makefile generation (if for some reason I needed a makefile). I might even have includes within methods so that imports can be deferred until they're necessary. Some drawbacks are that with all those files something may be lost; dependency information ends up being written into each file twice - in the inclusions and in the class declaration (with a risk that the two might go out of sync during editing); and it may bad for performance.

[Shrike]

Originally posted by Weedpacket
What is your convention on the mapping between classes and files? I'm strongly considering a one-class/one-file standard...

I've been using PHP5's __autoload() a fair bit, and having 1 class per file is a must.

Other fun things about __autoload(): Try throwing an exception from it 😉

[stfuji]

I only put one class per file as a rule of life for php. I actually tried doing it with two or multiple classes and it got way to hard to deal with and I couldn't end up finding anything.

I am just discovering PHP 5 and class interfaces (php variety) so I will be adjusting my architecture to reflect some of the new capabilities.

I have settled into using the following format

1 class per file
Each class must define a constant of the form INSTALLED_CLASSNAME

Each child class will check for the constant or die

Each class will also check for any configuration files needed or function groups.

Configuration files must be of the form classname.config.php

Configuration should be external to the class for possible exposure from cpls etc.

Function groups may contain function that are of a similar variety.

I divide all of this up into different directories and load with a breadth first search of the directories.

Anyway I think this can be adjusted. I didn't even know about the __autoload function...

Planetsim, the 0 was a numeric index as the push / pop do not modify the base array structure and the shift unshift always reset / clean the stack so that the numeric index of inplay elements is 0.

Do php4 flavors allow for class interfaces?

P.S. I use constants because I have a great fear of putting any paths / including relative into a file that I plan to drag all over the place. I didn't know about the class_exists either when I began doing this, but I suspect checking a constant may be quicker that perusing the heap for the existance of a class loaded in memory.

Thanks,

Geoffrey

[stfuji]

Here is a version of the above code that allows for variable length pushing...

i.e.

$stack = new double_stack();
$stack->push(1, 2, 3);

echo "Output:<br>\n";
echo $stack->dump();

Output:
3,2,1

$stack->emptyStack()  //  clear the stack of elements
$stack->rpush(1, 2, 3);

echo "Output:<br>\n";
echo $stack->dump();

Output:
1,2,3

Double Stack Class

<?php

############################################################
############################################################
##  Class:  double stack
##			double sided stack
##
##	November 24, 2004
##	Geoffrey DeFilippi
##  Thanks to:
##		PHP Builder & Weedpacket
##	
##	Methods:
##		push..........Push elements onto the stack
##		pop...........Pop an element off the stack
##		rpush.........Push elements onto bottom of stack
##		rpop..........Pop an element off bottom of stack
##		peek..........Get value of top element of stack without removing it from the stack
##		rpeek.........Get value of bottom element of stack without removing it
##		dump..........Output Stack from top down delimited by a delimiter
##		rdump.........Output Stack from bottom up delimited by a delimiter
##		emptyStack....Empty the stack of all entries
##		_count........Return number of entries in stack
##		_isEmpty......Is the stack empty? Boolean
############################################################
############################################################

if( !defined( 'INSTALLED_DOUBLED_STACK' ) ) {
////////////////////////////////////////////////////////////
//  DEFINE INSTALLATION VARIABLE
define( 'INSTALLED_DOUBLE_STACK', 1);

////////////////////////////////////////////////////////////
// START CODE

class double_stack {

var $dstack = array();

//  Constructor
function double_stack() {
}

//  Push an element into the top of the stack
function push( ) {
	if( func_num_args() > 0 ){
		$elements = func_get_args();
		for($i = 0; $i < count( $elements ); $i++) {
			array_push( $this->dstack, $elements[ $i ] );
		}
	} else {
		die( "ERROR: Must pass at least one element to push on stack" );
	}
}

//  Pop an element from the top of the stack
//  returns NULL on empty
function pop() {
	return array_pop( $this->dstack );
}

//  Push an element into bottom of stack
function rpush( ) {
	if( func_num_args() > 0 ){
		$elements = func_get_args();
		for($i = 0; $i < count( $elements ); $i++) {
			array_unshift( $this->dstack, $elements[ $i ] );
		}
	} else {
		die( "ERROR: Must pass at least one element to push on stack" );
	}
}

//  Pop an element from the bottom of the stack
function rpop() {
	return array_shift( $this->dstack );
}

//  View or return without taking out of the stack the top element
function peek() {
	return $this->dstack[ count( $this->dstack ) - 1 ];
}

//  View or return the bottom element of the stack
function rpeek() {
	return $this->dstack[0];
}

//  Output stack as a string delimited by delimiter top to bottom
function dump( $delimiter = "," ) {
	return implode( array_reverse( $this->dstack ), $delimiter );
}

//  Reverse output stack as a string delimited by delimiter bottom to top 
function rdump( $delimiter = "," ) {
	return implode( $this->dstack, $delimiter );
}

//  Clear the current stack of all elements
function emptyStack() {
	unset( $this->dstack );
	$this->dstack = array();
}

//  Return current size of stack
function _count() {
	return count( $this->dstack );
}

//  Is stack Empty?
function _isEmpty() {
	if ( $this->_count() == 0 || $this->_count() == NULL ) {
		return true;
	} else {
		return false;
	}
}
}

}  //  End Definition Test
?>

Prefix Double Stack Class

<?php

############################################################
############################################################
##  Class:  prefix_double_stack
##		Prepends a prefix to any added elements of a double stack
##
##  Extends Double Stack Class
##
##	November 16, 2004
##	Geoffrey DeFilippi
##
##	Methods:
##		push..........Push elements onto the stack (with prefix)
##		pop...........Pop an element off the stack
##		rpush.........Push elements onto bottom of stack (with prefix)
##		rpop..........Pop an element off bottom of stack
##		peek..........Get value of top element of stack without removing it from the stack
##		rpeek.........Get value of bottom element of stack without removing it
##		dump..........Output Stack from top down delimited by a delimiter
##		rdump.........Output Stack from bottom up delimited by a delimiter
##		emptyStack....Empty the stack of all entries
##		_count........Return number of entries in stack
##		_isEmpty......Is the stack empty? Boolean
############################################################
############################################################

if( !defined( 'INSTALLED_PREFIX_DOUBLE_STACK' ) ) {
////////////////////////////////////////////////////////////
//  DEFINE INSTALLATION VARIABLE
define( 'INSTALLED_PREFIX_DOUBLE_STACK', 1 );

////////////////////////////////////////////////////////////
//  START CODE

class prefix_double_stack extends double_stack {

var $prefix = "";

//  Class constructor accepts a prefix
function prefix_double_stack( $prefix = "" ) {
	////////////////////////////////////////////////////////////
	//  CHECK CLASS DEPENDANCIES
	//

	//  DEPENDANT CLASSES

		//  Double Stack
		if( !( defined( 'INSTALLED_DOUBLE_STACK' ) ) ) {
			die( 'DEPENDANCY NOT LOADED: Class: double_stack.class.php' );
		}

	//
	//  END Class Dependancies
	////////////////////////////////////////////////////////////

	$this->prefix = $prefix;
}

//  Push an element into the top of the stack
function push( $element ) {
	if( func_num_args() > 0 ){
		$elements = func_get_args();
		for($i = 0; $i < count( $elements ); $i++) {
			array_push( $this->dstack, $this->prefix . $elements[ $i ] );
		}
	} else {
		die( "ERROR: Must pass at least one element to push on stack" );
	}
}

//  Push an element into bottom of stack
function rpush( $element ) {
	if( func_num_args() > 0 ){
		$elements = func_get_args();
		for($i = 0; $i < count( $elements ); $i++) {
			array_unshift( $this->dstack, $this->prefix . $elements[ $i ] );
		}
	} else {
		die( "ERROR: Must pass at least one element to push on stack" );
	}
}

}

} // End Definition Test
?>

-Geoffrey

[stfuji]

I have also started checking class dependancies inside the constructor which has its ups and downs. I am loading directories of classes which means they are not loaded in a defined order so checking the dependancy outside of the constructor means they have to be loaded in a very specific order which is not possible. However checking the dependancy at run time means that the instantiation will cause the app to crash if the dependancies are not loaded...