Phabstractic: List Data Types

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:

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 different 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:

List Interface

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

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 include a stack, or a queue, or even a sef-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.

If you appreciate my programming please help support me through my Patreon.

photo credit: Train Departures via photopin (license)

Liked it? Take a second to support kadar on Patreon!

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

Leave a Reply

%d bloggers like this: