Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    God Emperor Fou-Lu's Avatar
    Join Date
    Sep 2002
    Saskatoon, Saskatchewan
    Thanked 2,668 Times in 2,637 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:
    PHP Code:
    $dll = new DoublyLinkedList();
    $dll->push('Push on end');
    $dll[] = 'Push onto the end';
    $dll['stringKeyed'] = 'Another Push';
    Numerically indexed or auto-indexed values can also be iterated in a for loop:
    PHP Code:
    $dll = new DoublyLinkedList();
    $dll[] = 1;
    $dll[] = 2;
    $dll[] = 4;
    $dll[] = 8;
    for (
    $i 0$i count($dll); $i++)
    $dll[$i]['data'] . "\n";
    // Produces
    // 1
    // 2
    // 4
    // 8
    foreach ($dll AS $key => $val)
    printf("%s => %s\n"$key$val);
    // Produces
    // 0 => 1
    // 1 => 2
    // 2 => 4
    // 3 => 8 
    Deletion of values (shift/pop/dequeue/remove) do not reset the auto key used for auto key increments. Only removeall will allow this. This can be implemented at a later time.

    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.
    Attached Files Attached Files
    PHP Code:
    header('HTTP/1.1 420 Enhance Your Calm'); 
    Been gone for a few months, and haven't programmed in that long of a time. Meh, I'll wing it ;)

  2. Users who have thanked Fou-Lu for this post:

    oesxyl (07-29-2008)

  3. #2
    New to the CF scene
    Join Date
    Jul 2008
    Thanked 0 Times in 0 Posts

    Cool reply3

    [size=2]Wow! This post rocks[size]


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts