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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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 (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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
namespace Falcraft\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.
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
namespace Falcraft\Data\Types\Resource { abstract class AbstractSortedList extends AbstractRestrictedList { // ... public function __construct( $data = null, $restrictions = null, $options = array() ) { // ... parent::__construct($data, $this->restrictions, $options); // Auto sort according to comparison function provided by child usort( $this->list, array( $this, 'cmp' ) ); } /** * The comparison function. * * Returns -1 if $l is 'less than'/before $r * 0 if $l and $r are equal * +1 if $l is 'greater than'/after $r */ abstract protected function cmp($l, $r); public function push() { // ... $exec .= " ); usort( \$this->list, array( \$this, 'cmp' ) ); " . "return count(\$this->list); } else { return null; }"; // ... } public function pushReference( &$a ) { if (parent::push($a)) { array_push($this->list, $a); usort($this->list, array($this, 'cmp')); return true; } return null; } } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
namespace Falcraft\Data\Types\Resource { abstract class AbstractRestrictedList extends AbstractList { // ... protected $restrictions = null; // ... public function __construct( $data = null, AbstractFilter $restrictions = null, $options = array()) { // ... // If there are no restrictions given, build basic free form restrictions // Default doesn't allow Type::TYPED_OBJECT if (!$restrictions) { $restrictions = Types\Restrictions::getDefaultRestrictions(); } $this->restrictions = $restrictions; if ( is_array( $data ) ) { // Plain Array /* Check input values for any illegal types If false, throw error because this is a constructor and can' really return anything. */ if (!Types\Restrictions::checkElements( $data, $this->restrictions, $this->conf->strict)) { throw new Exception\InvalidArgumentException( 'AbstractRestrictedList->__construct: Illegal Value'); } } else if ($data instanceof AbstractList) { // Falcraft\Data\Types\FList\AbstractList /* Check input values for any illegal types If false, throw error because this is a constructor and can't really return anything. */ if (!Types\Restrictions::checkElements( $data->getList(), $this->restrictions, $this->conf->strict)) { throw new Exception\InvalidArgumentException( 'AbstractRestrictedList->__construct: Illegal Value'); } } else if ($data) { // A scalar value /* Check input values for any illegal types If false, throw error because this is a constructor and can't really return nothing */ if (!Types\Restrictions::checkElements( array($data), $this->restrictions, $this->conf->strict)) { throw new Exception\InvalidArgumentException( 'AbstractRestrictedList->__construct: Illegal Value'); } } parent::__construct($data, $options); } private function check() { if (!Types\Restrictions::checkElements( func_get_args(), $this->restrictions, $this->conf->strict)) { if ($this->conf->strict) { throw new Exception\InvalidArgumentException( 'AbstractRestrictedList->check: Value not in ' . 'restrictions' ); } else { return false; } } return true; } public function push() { $args = func_get_args(); return call_user_func_array(array($this, 'check'), $args); } public function pushReference(&$a) { return $this->check($a); } } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
namespace Falcraft\Data\Types { class Stack extends DataResource\AbstractList implements \ArrayAccess { // ... public function top() { if (!empty($this->list)) { $stack = $this->getStack(); return $stack[0]; } else { if ($this->conf->strict) { throw new Exception\RangeException( 'Stack->top: top called on empty stack.'); } else { return new Null(); } } } public function &topReference() { if (!empty($this->list)) { return $this->list[count($this->list) - 1]; } else { if ($this->conf->strict) { throw new \RangeException( 'Stack->topReference: top called on empty stack.'); } else { return new Null(); } } } public function push() { $args = func_get_args(); $exec = 'array_push( $this->list'; for ($a = 0; $a < count($args); $a++) { $exec .= ', $args[' . $a . ']'; } $exec .= ' );'; return eval( $exec ); } public function pushReference(&$a) { return $this->list[] =& $a; } public function pop() { if ($this->top()) { return array_pop( $this->list ); } return new Null(); } public function &popReference() { $return = $this->topReference(); array_pop($this->list); // can return Types\Null return $return; } public function index($i) { if ($i > ($l = count($this->list) - 1) || $i < 0) { if ($this->conf->strict) { throw new Exception\RangeException( 'Stack->index: index out of range'); } } else { return $this->list[$l - $i]; } } public function &indexReference($i) { if ($i > ($l = count($this->list) - 1) || $i < 0) { throw new Exception\RangeException( 'Stack->indexReference: index out of range'); } else { return $this->list[$l - $i]; } } public function roll($c) { if (!is_int($c)) { if ($this->conf->strict) { throw new Exception\InvalidArgumentException( 'Stack->roll: invalid argument roll'); } else { return false; } } if (abs($c) > ($l = count($this->list))) { if ($c < 0) { $c = (abs($c) % $l) * -1; } else { $c %= $l; } } echo 'c ' . $c . "\n"; 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)); } } } } |
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:
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 |
namespace Falcraft\Data\Types { class Queue extends DataResource\AbstractList implements \ArrayAccess { public function top() { if (!empty($this->list)) { $queue = $this->getQueue(); return $queue[0]; } else { if ($this->conf->strict) { throw new Exception\RangeException( 'Queue->top: called on empty queue.'); } else { return new Null(); } } } public function bottom() { if (!empty($this->list)) { $queue = $this->getQueue(); return $queue[count($queue)-1]; } else { if ($this->conf->strict) { throw new Exception\RangeException( 'Queue->bottom: called on empty queue.'); } else { return new Null(); } } } public function &bottomReference() { if (!empty($this->list)) { return $this->list[count($this->list)-1]; } else { if ($this->conf->strict) { throw new Exception\RangeException( 'Queue: top called on empty queue.'); } else { return new Null(); } } } public function &topReference() { if (!empty($this->list)) { return $this->list[0]; } else { if ($this->conf->strict) { throw new Exception\RangeException( 'Queue: top called on empty queue.'); } else { return new Null(); } } } public function push() { $args = func_get_args(); $exec = 'array_push( $this->list'; for ($a = 0; $a < count($args); $a++) { $exec .= ', $args[' . $a . ']'; } $exec .= ' );'; return eval($exec); } public function pushReference(&$a) { return $this->list[] = &$a; } public function pop() { if ($this->top()) { return array_shift($this->list); } return new Null(); } public function &popReference() { $return = $this->topReference(); array_shift($this->list); // Can return Types\Null() return $return; } public function index($i) { if ($i > (count($this->list) - 1) || $i < 0) { if ($this->conf->strict) { throw new Exception\RangeException( 'Queue->index: out of range'); } else { return new Null(); } } else { return $this->list[$i]; } } public function &indexReference($i) { if ($i > (count($this->list) - 1) || $i < 0) { if ($this->conf->strict) { throw new \RangeException( 'Queue->indexReference: index out of range'); } else { return new Null(); } } else { return $this->list[$i]; } } public function roll($c) { if (!is_int($c)) { if ($this->conf->strict) { throw new Exception\InvalidArgumentException( 'Queue->roll: argument not integer'); } else { return false; } } if (abs($c) > ($l = count($this->list))) { if ($c < 0) { $c = (abs($c) % $l) * -1; } else { $c %= $l; } } // rotate right if ($c > 0) { $this->list = array_merge(array_slice($this->list, $c), array_slice($this->list, 0, $c)); } else if ( $c < 0 ) { // rotate left $c = abs($c); $this->list = array_merge(array_slice($this->list, $l - $c), array_slice($this->list, 0, $l - $c)); } return true; } } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 |
namespace Falcraft\Data\Types { class PriorityQueue extends DataResource\AbstractSortedList { /** * Return Data Equal To Given Urgency Index? * */ const EQUAL = 'e'; /** * Return Data Equal or Higher To Given Urgency Index? * */ const HIGHER = 'h'; /** * Return Data Equal or Lower to Given Urgency Index? * */ const LOWER = 'l'; /** * Compare Two Priority Objects * * This is used by AbstractSortedList to sort the elements of the list * * @param Falcraft\Data\Type\Resource\PriorityInterface $l * The first value to compare * @param Falcraft\Data\Type\Resource\PriorityInterface $r * The second value to compare * * @return int The required comparison results. * * @throws Exception\InvalidArgumentException * if the values to compare are not of PriorityInterface * */ protected function cmp( $l, $r ) { if (!($l instanceof DataResource\PriorityInterface ) || !($r instanceof DataResource\PriorityInterface)) { throw new Exception\InvalidArgumentException( 'PriorityQueue->cmp: comparison must be between ' . 'Falcraft\\Data\\Type\\Resource\\PriorityInterface'); } $lp = $l->getPriority(); $rp = $r->getPriority(); if ( $lp > $rp ) { return 1; } else if ( $lp < $rp ) { return -1; } else { return 0; } } public function top() { if (!empty($this->list)) { return $this->list[0]->getData(); } else { if ($this->conf->strict) { throw new Exception\RangeException( 'PriorityQueue->top: called on empty queue.'); } else { return new Null(); } } } public function bottom() { if (!empty($this->list)) { return $this->list[count($this->list)-1]->getData(); } else { if ($this->conf->strict) { throw new Exception\RangeException( 'PriorityQueue->bottom: called on empty queue.'); } else { return new Null(); } } } public function index( $i, $order = self::EQUAL ) { if (empty($this->list)) { if ($this->conf->strict) { throw new Exception\RangeException( 'PriorityQueue->index: call on empty list'); } else { return new Null(); } } else { $return = array(); foreach ($this->list as $item) { switch ($order) { case self::HIGHER: $predicate = $item->getPriority() >= $i; break; case self::LOWER: $predicate = $item->getPriority() <= $i; break; case self::EQUAL: $predicate = $item->getPriority() == $i; break; default: $predicate = true; } // Do we include the item? if ( $predicate ) { $return[] = $item->getData(); } } return $return; } } public function indexRange(Range $r) { return StandardResource\ArrayUtilities::returnUnique( array_merge($this->index($r->getMinimum(), self::HIGHER), $this->index($r->getMaximum(), self::LOWER))); } public function delete($data) { foreach ($this->list as $key => $priority) { if ($priority->getData() == $data) { unset($this->list[$key]); return true; } } return false; } public function deletePriority($priority) { foreach ($this->list as $key => $val) { if ($val->getPriority() == $priority) { unset($this->list[$key]); return true; } } return false; } public function pop() { $datum = $this->top(); if (!($datum instanceof Null)) { $priority = array_shift($this->list); return $priority->getData(); } return $datum; } public function pull() { $datum = $this->bottom(); if (!($datum instanceof Null)) { $priority = array_pop($this->list); return $priority->getData(); } return $datum; } } } |
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)
