Primus2\Falcraft: New Data Type (lists)

IMPORTANT!

This code is now obsolete and out of date.  It has been moved to another programming project, asherwunk/phabstractic.  For more information see the current blog post.

Primus/Falcraft now has lists implemented through a common abstraction classes in Data\Types

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.  Here are some lists that Primus/Falcraft implements.

Abstractions

Falcraft 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.

Primus/Falcraft/Data/Types/Resource/AbstractList.php

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 (FILO) 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.

Primus/Falcraft/Data/Types/Resource/ListInterface.php

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.

Self-Sorting Lists

What’s really nifty is that you can implement a self-sorting list simply by wrapping a few parent functions in some sorting logic.  This is what AbstractSortedList accomplishes.

Falcraft/Data/Types/Resource/AbstractSortedList.php

AbstractSortedList establishes the existence of a ‘cmp’ method which is used to to compare two values and say if they are equal, less than, or more than (if they come behind or in front of each other).  This is used in sorting algorithms (usually provided by PHP) to alter the list in place so that it is always sorted.  In order to do this we have to catch the value as it’s being ‘inserted’ into the list so we can sort afterwards.  AbstractSortedList achieves this with some ‘wrapper’ code:

As you can see by default we sort the list using the built-in function usort in PHP.  These functions can of course be overridden in a child class so that a custom sorting function using ::cmp() can be used.

Restricted Lists

Another nifty feature in Falcraft is the Restricted List.  This is a list that checks if a piece of data being put in the list fits a particular filter (usually a type restriction, see Type Restrictions).

Falcraft/Data/Types/Resource/AbstractRestrictedList.php

This is very much like a sorted list except the functionality is instead to compare a value against a filter BEFORE it gets put in the list.  In this sense we again override the normal AbstractList functions:

As you can see this abstract class defines methods for constructing a filter (or providing your own, see AbstractFilter.php) and then checks values against that filter using a private function returning either true or false. The two functions where information is entered into the list are overridden so that they submit a check against the filter logic.  Note that ::check() can accept multiple arguments, thus it is also compatible with the variant function ::push().

NOTE: These functions are meant to supply checking logic, returning either true or false when called under parent:: .  Actual insertion into the list MUST be done in the child class, as this insertion will be specific to that list (queue, or stack, etc.)

Falcraft/Data/Types/RestrictedList.php

There is a simple array based restricted list concrete in the data types library.  This enables you to have in essence an array with type restrictions without worrying about any particular list logic.

Stack (Heap)

To quote Wikipedia:

In computer science, a stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations:[1]

  • push adds an element to the collection;
  • pop removes the last element that was added.

The term LIFO stems from the fact that, using these operations, the first element “popped off” a stack in series of pushes and pops is the last element that was pushed in the sequence. This is equivalent to the requirement that, considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. (Additionally, a peek operation may give access to the top.)

The point of a stack is that you put something into it (on the top), and when you want it back you take it off the top.  The LAST one put in, is the FIRST one pull out.  There are two implementations of the Stack in Falcraft.  There is the Stack.php which can implement a stack where any sort of value can be put in the pile, and there is the RestrictedStack.php which is like a stack but restricted to specific types (or otherwise implemented filter).  You can see the custom implementation of the abstract functions from AbstractList.php:

As you can see the stack has to implement specific functionality for referencing into an array (if the array is implemented normally).  You can observe that in the lines:

if ($i > ($l = $this->count() - 1) || $i < 0)

This is in the indexing function, and is written so that the Stack and Queue indexing functions operate generally the same.

Queues

A queue is like a line.  You put a thing at the end of the conveyer belt, and then you grab the thing at the other end of the conveyer built off.  For instance, the FIRST person to get in line at the grocery store, is the FIRST person, relatively speaking, to be served.  To quote Wikipedia:

In computer science, a queue (/ˈkjuː/ kew) is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.

The diagram on Wikipedia illustrates this very well:

fifo

There are two types of Queue classes: Queue.php and RestrictedQueue.php.  They serve much the same purpose as the Stack distinctions noted above.  The Queue class does not have special method names for enqueue and dequeue, but instead relies on the standard AbstractList function names.  You can see the specifically implemented methods for the queue:

As you can see the functionality of the queue is opposite that of the stack.

\ArrayAccess

Though the methods are not listed here, both Queue and Stack classes implement the built-in PHP \ArrayAccess interface.  This is in an effort to make it possible to write $queue[] = $foobar; and to index the stack and queues specifically (though indexing is a special case).

Priority Queue

A priority queue abstracts out lists a step further.  The basic idea is that you specify a priority for a given element and then put it in the list.  The list is sorted by priority (smallest- or -largest first if using integers, although you can create a priority object that uses other data types by implementing Falcraft/Data/Types/Resource/PriorityInterface.php)  In order to do this we specify a Priority object (that inherits from PriorityInterface.php) that maintains a priority marking in association with a piece of data.

Falcraft/Data/Type/PriorityQueue.php

This priority object is then used in a list that is both restricted (for PriorityInterface objects only) and automatically sorted (so ::top() for instance doesn’t have to continuously search the array every time its accessed, sorting happens once).  Since the Priority object can be associated with any data type the list isn’t restricted to particular data types itself, just to PriorityInterface objects.  It is restricted to these types so that they are guaranteed sortable.

Because I couldn’t inherit from AbstractRestrictedList and AbstractSortedList at the same time I had to make a concession.  So, in light of this I inherited form AbstractSortedList and then implemented the specific sorting and storing mechanisms necessary for prioritization in this class itself.  Many operations work the same for Priority Queues, however, the index method is a little different:

As you can see the ::cmp() function relies on PriorityInterface objects and built in comparison functions. However, the index and range functions operate differently than other lists. It is possible to specify an index and receive all the items with that priority, all the elements with that priority and higher, or all the item with that priority or lower. This is specified in the second argument using class constants. This means that a call to index and indexReference may/will return an array of data rather than one datum.

NOTE: The data returned is the data value of the PriorityInterface, not the Priority implementation itself.

Lexicographic List

A special sorted list is a list that doesn’t sort based on integers but rather sorts based on alphabetical representations.  This is useful for strings and other string-like information that must come before or after each other.  This class is very much like Priority Queue in that it inherits from AbstractSortedList.php but still maintains a type restrictions filter internally.

The difference between this filter however is that it operates directly on the data, by default type string, not on a mediating object like a Priority.  It is possible to supply your own filter that limits the list to something other than lists if need be.

In terms of implementation it is much like RestrictedList (above), but this also adds the logic of being able to automatically sort the information as well.

Conclusion

Primus\Falcraft implements many different kinds of lists, from Queues, Stacks, to sorted lists like Priority Queue.  With these lists it should be possible to implement other list like structures such as a double-linked list, or a buffer ring.  I hope you found this useful, or will find this useful in your own list implementations.

photo credit: Coralville IA HyVee renovation via photopin (license)

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: