Editors Note, February 14th 2022: This project is now ABANDONED and no longer supported or updated.

asherwunk/phabstractic now implements a stack data type (an extension of AbstractList implementing ListInterface)

Stack

I quote Wikipedia in my explanation of a stack data structure:

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out). Additionally, a peek operation may give access to the top without modifying the stack.

Stacks are extremely useful abstract data types.  They are implemented in many programming languages, and sometimes even make up the core of the programming language (such as PostScript, a language I learned when I worked at the financial statement printing firm).  They are so useful they are often implemented in hardware for various purposes, and even in virtual machines such as the Java Virtual Machine.  One application they have is in syntax parsing and expression evaluation for constructions such as interpreters and compilers.

A stack can be visualized as the following (also from Wikipedia):

ListInterface

First Stack inherits from AbstractList and thus implements ListInterface (github):

namespace Phabstractic\Data\Types\Resource
{
    interface ListInterface extends \Countable {
        public function top(); 
        
        public function &topReference();
        
        public function push();
        
        public function pushReference(&$a); 
        
        public function pop();
        
        public function &popReference(); 
        
        public function index($i);
        
        public function &indexReference($i); 
        
        public function count();
        
        public function isEmpty();
        
        public function clear();
        
        public function getList();
        
    }
    
}

NOTE – ::top() is like ::peek() as reference in Wikipedia.

AbstractList

As noted Stack inherits from AbstractList (github):

namespace Phabstractic\Data\Types\Resource
{
    abstract class AbstractList implements ListInterface
    {
        protected $list = array();
        
        public function __construct($data = null) 
        {
            // ...
        } 
        
        abstract public function top();
        
        abstract public function &topReference();
        
        abstract public function push();
        
        abstract public function pushReference( &$a );
        
        abstract public function pop();
        
        abstract public function &popReference();
        
        abstract public function index($i);
        
        abstract public function &indexReference($i); 
        
        public function count()
        {
            return count($this->list);
        }
        
        public function isEmpty()
        { 
            return empty($this->list); 
        } 
    
        public function clear()
        { 
            $this->list = array();
            return $this;
        }
        
        public function remove($value)
        {
            if ($key = array_search($value, $this->list)) {
                unset($this->list[$key]);
            }
            
            // resets indices
            $this->list = array_merge($this->list, array());
            return $this->list;
        }
        
        public function getList()
        {
            return $this->list;
        }
        
        abstract public function exchange();
         
        abstract public function duplicate();
        
        abstract function roll($i);

    }     

}

Stack Specifics

We implement the Stack LIFO by simply using an array in PHP.  This array grows and shrinks accordingly.  We mostly just wrap functionality around the idea that the last element of the internal array is the top of the stack.  Doing that, it’s simply a matter of pushing and popping an array using the built-in PHP array functions.  A function of interest, however, would be exchange and roll:

public function exchange() { 
    $m1 = &$this->popReference(); 
    $m2 = &$this->popReference();
    $this->list[] = &$m1; 
    $this->list[] = &$m2;
    return $this;
}
public function roll($c)
{
    if (!is_int($c)) {
        if ($this->conf->strict) {
            throw new TypesException\InvalidArgumentException(
                'Phabstractic\\Data\\Types\\Stack->roll: ' .
                'invalid argument to roll');
        } else {
            return false;
        }
        
    }
    
    if (abs($c) > ($l = count($this->list))) {
        if ($c < 0) {
            $c = (abs($c) % $l) * -1;
        } else {
            $c %= $l;
        }
        
    }
    
    if ($c > 0) { // rotate right
        $this->list = array_merge(array_slice($this->list, $l - $c),
                                  array_slice($this->list, 0, $l - $c));
    } else if ($c < 0) { // rotate left
        $c = abs($c);
        $this->list = array_merge(array_slice($this->list, $c),
                                  array_slice($this->list, 0, $c));
    }
    
}

These are functions inspired by PostScript, which is where this class found inspiration.

Something to note about indexing that’s very important.  We don’t index from the beginning of the private array, we index from the end of the array as if we’re delving into the stack. You can observe this here:

public function index($i)
{
    if ($i > ($l = count($this->list) - 1) || $i < 0)
    {
        if ($this->conf->strict) {
            throw new TypesException\RangeException(
                'Phabstractic\\Data\\Types\\Stack->index: ' .
                'index out of range');
        }
        
    } else {
        return $this->list[$l - $i];
    }
    
    return new None();
    
}

We also define a bottom method as well as a top method.

A nice thing about concrete implementation is you can do things like implement \ArrayAccess.  Note that ArrayAccess methods index using the index() method, which accesses the private array from the end (see above):

public function offsetSet($key, $value)
{
    if (is_numeric($key)) {
        if ($this->offsetExists($key)) {
            // encapsulate indexing logic in indexing function
            $r = &$this->indexReference($key);
            $r = $value;
            return count($this->list);
        }
        
    }
    
    // If the key is empty: stack[], push value
    if (!$key) {
        return $this->push($value);
    }
    
    // At this point, we should have returned, or something is wrong
    // Such as treating the stack as an associative variable
    
    if ($this->conf->strict) {
        throw new TypesException\RangeException(
            'Phabstractic\\Data\\Types\\Stack->offsetSet: offsetSet key ' .
            $key . ' out of range.');
    }
} 

public function offsetGet($key)
{
    if (!is_numeric($key)) {
        if ($this->conf->strict) {
            throw new TypesException\RangeException(
                'Phabstractic\\Data\\Types\\Stack->offsetGet: ' .
                'Invalid Argument Key');
        }
        
    }
    
    // encapsulates the indexing logic in the index method
    return $this->index($key);
} 

public function offsetUnset($key)
{ 
    if (is_numeric($key)) {
        // is this out of range?
        if ($key > ($l = count($this->list) - 1) || $key < 0) { 
            return false;
        } else {
            unset($this->list[$l - $key]);
            // reset keys
            $this->list = array_merge($this->list, array());
            return true;
        }
        
    }
    
    return false;
} 

public function offsetExists($key)
{
    if (is_numeric($key)) {
        // is this out of range?
        if ($key > ($l = count($this->list) - 1) || $key < 0) {
            return false;
        } else {
            return isset($this->list[$l - $key]);
        }
        
    }
    
}

Conclusion

Stacks are very important pieces of code.  They are used in numerous many places including parsing syntax trees, calling subroutines, managing memory, and artificial intelligence.  The ability to ‘remember’ state as you put and pull states off the stack is essential in being able to operate on memory.

(View on GitHub)

This is part of the Phabstractic Library.

photo credit: Reynisdrangar via photopin (license)

Asher Wolfstein

Metaverse Resident

About the Author

A metaverse resident, you can find me on Second Life (kadar.talbot) and other online platforms. I write about my digital life, my musings, and my projects as a programmer, webmaster, artist, and game designer. (exist (be wunk) (use rational imagination) (import artist coder maker furry) (conditional (if (eq you asshole) (me (block you))))

View Articles