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

asherwunk/phabstractic now has functionality for lists in abstract form.  This can give rise to Stacks, Queues, and more.

Lists

There are many different kinds of lists in computer programming.  Some of them act like heaps of data, some like grocery lines, some like unending rings.  Some lists you can only go forward in, some you can go backward as well.

Abstractions

asherwunk/phabstractic implements lists from a basic abstract class that provides some basic functionality.  This abstraction was inspired by the stack available in the PostScript language.  This was actually written as a PostScript emulation.  Personally, I implemented this in PHP after I worked for a financial statement printing firm where we ‘hand wrote’ PostScript and generated it from C programs.  My job was to measure things with a ruler and input the measurements into a standard program that changed a little bit every time. I was fired from the job and then re-hired, and then fired again, and that was that.

Abstract List

AbstractList defines all the basic functionality of a list.  Functions such as ::isEmpty() or ::exchange() are universal to most all lists, so those types of functions (including ::clear()) are defined in this abstract class for convenience.  List access is where most lists will have their specific functionalities programmed.  In this vein, AbstractList defines the following abstract functions:

abstract class AbstractList implements ListInterface
{
    // ...

    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 );
    
    // ...
}

Top accesses the top of the list (like peek in other implementations) but does not alter or delete the top element of the list.  When I say top here I mean the access point of ‘out’ on the list.  So, for a list that is Last In Last Out, ::top() accesses the last element put in, whereas for a list that is First In Last Out, ::top() access the earlier element put in.  Push is meant to put an element on the relative ‘end’ of a list, so for a stack/heap, it would be at the ‘top’ of the pile.  For a queue (FIFO) that would be the ‘end of the line’.

If for some reason you want to access the i’th element of the list, index enables this, but some lists will count differently according to their implementations.

For instance, for a PriorityQueue, this function will return multiple list items depending on the input.  Whereas, a stack and queue are each accessed in opposite ways.

AbstractList also defines some common functionality that child lists don’t have to re-implement:

public function __construct($data = null) 
{
    /* Version 3.0 eliminates default configurability
    
    if (is_array($options)) {
        $options = array_change_key_case($options);
    }
    
    $this->configure($options); */
     
    if (is_array($data)) { 
        $this->list = $data; 
    } elseif ($data instanceof AbstractList) { 
        $this->list = $data->getList(); 
    } elseif ( $data ) { 
        $this->list = array($data);
    } else { 
        $this->list = array();
    }
    
}

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;
}

List Interface

So that we can identify a list that may not have been inherited from AbstractList we also define a ListInterface establishing the common interface:

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();
        
    }
    
}

As you can see the interface not only defines the abstract functions but ALSO defines the elements necessary to be \Countable. This is important to keep in mind when implementing a list that implements this interface.

Implementing Lists

I decided that it was smarter to implement further functionality for lists, such as \ArrayAccess, you would do it in the child class.  Some lists may not be able to be accessed through something like \ArrayAccess (such as a priority queue, at least Phabstractic’s implementation), so it wouldn’t make sense to guarantee that functionality in the interface of abstraction.

With this functionality available we should be able to implement some interesting lists, all with a standard defined interface.  This includes a stack, a queue, or even a self-sorting list.  I’m planning to further implement those in future posts.

Conclusion

Lists are very important abstract data types and are used in many many different applications.  Stacks are often used with programming languages, and in fact, some programming languages depend entirely on a stack, such as Postscript.  Interpreters, finite state machines, and all sorts of things implement stacks and heaps.  This abstract data type is actually different from a heap, which we’ll build much later.

This is part of the Phabstractic Library.

photo credit: Train Departures 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