Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
07-16-2008, 04:12 AM #1
- Join Date
- Sep 2002
- Saskatoon, Saskatchewan
- Thanked 2,662 Times in 2,631 Posts
Data Collections: [Doubly]LinkedList, Stack, Queue and PriorityQueue
So I decided that I was going to play around with some of the newly added interfaces and classes into the PHP libraries. The ones I decided to try out were the ArrayAccess and Countable interfaces, both of which fit well into data collections. None of these include arrays, nor do they include optimization indexing, figured I'd save the latter for a graph. Since I put all of this work into them, I figured someone else may have some use.
Attached are 13 classes plus 1 testing file comprising a start to my ADT Collections. They do not include usability documentation. They require PHP version 5.1+ to operate.
If you do not know what a datacollection is, chances are these are not for you. If you're still interested I'll provide a brief outline for what each included collection is for, and how it is used.
A linked list is a collection that handles node chaining. The list itself tracks only the starting point for the list while each node tracks the next node in the chain. If the chain encounters a null, the list is complete. DoublyLinkedLists are identical except an additional pointer is placed at the end node of the list and each node also contains a previous node reference. LinkedLists have are advantageous due to their ability to insert and remove easily from the list. Iteration always begins at the front of the list so it has an O(n) magnitude.
A stack is comparable to a stack of papers. You place one item on the top of the stack, and you remove it again from the top of the stack. This follows the Last In First Out method (LIFO). Magnitude is also O(n).
A queue is like a line at a theater. Each person lines up behind another and the first person where is the first person out. Follows First In First Out method (FIFO). Magnitude O(n).
A priority queue is identical to a queue but also allows priority insertions. This allows a higher numbered priority to outrank a currently existing queued value and force their position higher than the original. Magnitude O(n).
The lists and nodes allow access via ArrayAccess interfacing. This allows the objects to be treated similar to an array, both for reading and writing data. The queues and stacks do not support this feature.
I will not go over how the insertions and deletions work. Unshift always refers to placing at the 'top' or 'front', push always refers to placing on the 'end' or 'bottom', shift removing from the 'top', and pop from the 'bottom'. Read the comments for these methods to see how they are used as each are PHP style overloaded to handle various arguments.
The ArrayAccess allows an interesting usage for the lists:
$dll = new DoublyLinkedList();
$dll->push('Push on end');
$dll = 'Push onto the end';
$dll['stringKeyed'] = 'Another Push';
$dll = new DoublyLinkedList();
$dll = 1;
$dll = 2;
$dll = 4;
$dll = 8;
for ($i = 0; $i < count($dll); $i++)
echo $dll[$i]['data'] . "\n";
foreach ($dll AS $key => $val)
printf("%s => %s\n", $key, $val);
// 0 => 1
// 1 => 2
// 2 => 4
// 3 => 8
Please remember though that these are not arrays. With the exception of an indexed class I had made for testing, each of these collections take substantially more processing time and memory than a standard array uses. The indexed classes took about 4 times the memory usage, but the time comparisons blew an array out of the water for every test - I was quite impressed. So why bother use a collection? They are specialized. LinkedLists allow for easy insertions into the middle of the list - arrays do not. Queues and Stacks allow forced order additions and removals. Arrays support but become confusing when using combination push/shift and unshift/pop. Finally the priority queue - IMO the only real useful one of this lot. Priority queues are great, say you have a collection of links you want to use to send someone to other pages. Now say you have a page and you want to add a special link to the top of the links - a priority queue is great for these choices. Instead of needing to hack together some code to work around you can simply push you're new link into the queue with a higher priority - done and done, it will be the first link that appears.
Feel free to use these class, but please respect where they have come from by not removing the copyrights. Also, do not use these for any educational code; you would be surprised how large my instructor networks are. I will tan you're hide if I catch you cheating.
Let me know if you like these collections. If there is enough support for them, I'll throw together trees and heaps next, followed by a graph (the collection chalice if you will). Also, please PM me if you have any questions on how to use these (don't post in the thread please), but post bugs if you find any. These are tested, but there are always bugs hanging around
And finally. I am such a windbag. Wow.PHP Code:
header('HTTP/1.1 420 Enhance Your Calm');
Users who have thanked Fou-Lu for this post:
07-29-2008, 04:52 AM #2
- Join Date
- Jul 2008
- Thanked 0 Times in 0 Posts
[size=2]Wow! This post rocks[size]