Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 7 of 7

Thread: Ordering Nodes

  1. #1
    New Coder
    Join Date
    Jun 2007
    Posts
    60
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Ordering Nodes

    Hello guys, I am having a problem.
    I am making my first double linked list, using php and mysql.
    What my problem is right now is displaying the double linked list in order.
    I know how to statically display the list, but I want to be able to loop through everything in my database to dynamically display the list in the right order.

    right now here is how I statically display the node list:
    (the function getNextNode uses the returned id of the previous node to query where the next node is.)
    PHP Code:
    //get next node function
    function getNextNode($main_id)
    {
    $next_id mysql_query("SELECT * FROM list WHERE prev_id = '$main_id'");
    $next_id mysql_fetch_array($next_id);
    return 
    $next_id;
    }

    //get the first node
    $firstNode mysql_query("SELECT * FROM list WHERE prev_id='head'");
    $firstNode mysql_fetch_array($firstNode);
    //get the next nodes
    $secondNode getNextNode($firstNode['main_id']);
    $thirdNode getNextNode($secondNode['main_id']);
    $fourthNode getNextNode($thirdNode['main_id']); 
    how could I make this a statically generated list of nodes into a dynamic display which knows how many nodes there are in the database and then from knowing that will run the getNextNode function from all of the ids in the database starting from the first node?
    Last edited by elementis0; 05-08-2008 at 02:52 AM.

  • #2
    God Emperor Fou-Lu's Avatar
    Join Date
    Sep 2002
    Location
    Saskatoon, Saskatchewan
    Posts
    16,994
    Thanks
    4
    Thanked 2,662 Times in 2,631 Posts
    It doesn't look like your using an object for a linked list. In PHP, that sort of kills it off. Here's what I would do, create a linked list object (implementing Iterable of course [or leave for later it can be tricky to use]), then run a single query. Each result in the query I assume is a node, insert each node into the linked list. Now, for sorting, you can sort on an object, so should also be able to usort an object.
    Advantage of this route, all the data is there for comparisons, use a simple callback delegate to perform the sorting for you. Also saves on potentially thousands of queries. Downside is that if you have a lot of items, it will take a lot of resource to allot them. This is all about how you control it though. If you're not familiar with OOP style LL, this is a quick example rundown for you:
    PHP Code:
    class DLL // Actually, there would probably be an extends LL in here
    {
        private 
    $head;
        private 
    $tail;
        private 
    $elements;

        public function 
    __construct($node null)
        {
            
    $node $this->convNode($node);
            
    $this->head $this->tail $node;
        }

        private function 
    convNode($data)
        {
            if (
    $data != null)
            {
                if (!(
    $data instanceof Node)) // pre... 5.2.1 I think it is, use Node as 'Node'
                
    {
                     
    $data = new Node($data);
                }
            } 
            return 
    $data;       
        }

        public function 
    addNode($node)
        {
             
    $node $this->convNode($node);
             if (
    $this->head == null)
             {
                  
    //Should be empty
                  
    $this->head $this->tail $node;
             }
             else
             {
                 
    // Not a priority list, throw it at the end:
                  
    $prevTail $this->tail;
                  
    $this->tail $node;
                  
    // Prev tail can never be empty by this point (unless something was done badly in removal methods :P)
                  
    $this->tail->setPrev($prevTail);
                  
    $prevTail->setNext($node);
             }
        }


    }

    class 
    Node
    {
        private 
    $data;
        private 
    $next;
        private 
    $prev;
        
        public function 
    __construct($data)
        {
            
    $this->data $data;
        }
        public function 
    setNext(Node $next)
        {
             
    $this->next $next;
        }
        public function 
    getNext()
        {
            return 
    $this->next;
        }
        public function 
    setPrev(Node $prev)
        {
           
    $this->prev $prev;
        }
        public function 
    getPrev()
        {
            return 
    $this->prev;
        }
        public function 
    getData()
        {
             return 
    $this->data;
        }

    Control your sorting with a usort/ DLL::sort and I would recommend creating a comparable interface to throw on your node class.

    Now, just put it in something like:
    PHP Code:
    $dll = new DLL();
    $qry mysql_query("Select stuff");
    while (
    $records mysql_fetch_assoc($qry))
    {
        
    $dll->addNode($dll);
    }
    $dll->sort(); 
    Sort in DLL would consist of:
    1. Having iterable interface on DLL OR iterating manually through the list and constructing a new linked list on the fly
    2. Having an actual comparison values for it (ie: $node->getData()['key'] comparison for example, where 'key' = primary field to sort on (from db probably))

    Does this go along an idea you are looking for, or am I way off on my assumptions?
    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 ;)

  • #3
    New Coder
    Join Date
    Jun 2007
    Posts
    60
    Thanks
    3
    Thanked 0 Times in 0 Posts
    I think what your trying to explain would work. Im not sure.
    Im not experienced enough in PHP to really thoroughly comprehend what you were trying to explain.

    But what I can show you right now is everything im working with so far.
    first heres my database structure:

    TABLE USED:
    PHP Code:
    CREATE TABLE `list` (
      `
    main_idint(11NOT NULL auto_increment,
      `
    prev_idvarchar(11NOT NULL,
      `
    next_idvarchar(11NOT NULL,
      `
    titlevarchar(30NOT NULL,
      `
    descriptionvarchar(100NOT NULL,
      
    PRIMARY KEY  (`main_id`)
    ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=16 
    Form to add/Delete Nodes(nodeform.php)
    PHP Code:
    <html>
    <
    head>
    </
    head>
    <
    body>
    <
    h3>Add Node</h3>
    <
    form action="handlenodes.php" method="post">
    MAIN_ID <input type="text" name="main_id"/><br />
    Title <input type="text" name="title"/><br />
    Description <input type="text" name="description" /><br />
    <
    input type="hidden" name="addNode" />
    <
    input type="submit" value="add node">
    </
    form>
    <
    hr />
    <
    h3>Delete Node</h3>
    <
    form action="handlenodes.php" method="post">
    MAIN_ID <input type="text" name="main_id"/><br />
    <
    input type="hidden" name="removeNode" />
    <
    input type="submit" value="remove node">
    </
    form>
    </
    body>
    </
    html
    processing page for the Node Forms(handlenodes.php)
    PHP Code:
    <?php
    include("dbconnect.php");
    //adds a node to the system
    function addNode($newlast_id,$title,$description)
    {
    $q mysql_query("SELECT main_id FROM list");
        if(
    mysql_num_rows($q) == 0)
        {
        
    //no nodes exists, add first node
        
    $addNode mysql_query("INSERT INTO list (prev_id, next_id,main_id,title,description) VALUES('head','tail','$newlast_id','$title','$description')");
        if(
    $addNode)
            {
            echo 
    "New Node added";
            }
            else
            {
            echo 
    "error";
            }
        }
        
        else
        {
        
    //nodes exist add a node at the tail
        
    $oldlast_id mysql_fetch_array(mysql_query("SELECT main_id FROM list WHERE next_id = 'tail'")); //get last id of list
        
    $oldlast_id $oldlast_id[0]; //make last id a value
        
    $update_main mysql_query("UPDATE list SET next_id='$newlast_id' WHERE main_id='$oldlast_id'"); //get last id of list
        
    $addNode mysql_query("INSERT INTO list (prev_id, next_id,main_id,title,description) VALUES('$oldlast_id','tail','$newlast_id','$title','$description')"); //insert new node
            
    if($addNode == true && $update_main == true)
            {
            echo 
    "Node has been added";
            }
            else
            {
            echo 
    "error";
            }
        }
    }

    // Deletes a Node from the system
    function removeNode($main_id)
    {
    //get row information for row that is being deleted
    $deadInfo mysql_query("SELECT prev_id,next_id FROM list WHERE main_id='$main_id'");

    //break down information into seperate variables
    $deadInfo mysql_fetch_array($deadInfo);
    $dead_prev_id $deadInfo[prev_id];
    $dead_next_id $deadInfo[next_id];
    //update rows with new the pointers
        
    if($dead_next_id != "tail"//check if row exists to make pointer
        
    {
        
    $next_row_update mysql_query("UPDATE list SET prev_id = '$dead_prev_id' WHERE main_id = '$dead_next_id'");
        }
        
        if(
    $dead_prev_id != "head"//check if row exists to make pointer
        
    {
        
    $prev_row_update mysql_query("UPDATE list SET next_id = '$dead_next_id' WHERE main_id = '$dead_prev_id'");
        }

    //delete the desired row
    $delete_row mysql_query("DELETE FROM list WHERE main_id = $main_id");
        if(
    $dead_prev_id != "head" || "tail")
        {
        
    //its not end end node, check all actions
            
    if($next_row_update && $prev_row_update && $delete_row)
            {
            echo 
    "Node has been Deleted";
            }
        }
        
        else if(
    $dead_prev_id == "head")
        {
        
    //it is beginning node, check two actions
            
    if($next_row_update && $delete_row)
            {
            echo 
    "Node has been Deleted";
            }
        }
        
        else if(
    $dead_next_id == "tail")
        {
        
    //it is ending node, check two actions
            
    if($prev_row_update && $delete_row)
            {
            echo 
    "Node has been Deleted";
            }
        }
        
        else
        {
        echo 
    "error";
        }
    }

    //finds the next node from a given main_id
    function getNextNode($main_id)
    {
    $next_id mysql_query("SELECT * FROM list WHERE prev_id = '$main_id'");
    $next_id mysql_fetch_array($next_id);
    return 
    $next_id;
    }

    if(isset(
    $_POST['addNode']))
    {
    //add node form submitted, process form
    addNode($_POST['main_id'],$_POST['title'],$_POST['description']);
    }

    elseif(isset(
    $_POST['removeNode']))
    {
    //remove node form submitted, process form
    removeNode($_POST['main_id']);
    }
    ?>
    Page the shows the nodes(the one im asking for help with) (displaynodes.php)
    PHP Code:
    $firstNode mysql_query("SELECT * FROM list WHERE prev_id='head'");
    $firstNode mysql_fetch_array($firstNode);
    print_r($firstNode);
    $secondNode getNextNode($firstNode['main_id']);
    print_r($secondNode);
    $thirdNode getNextNode($secondNode['main_id']);
    print_r($thirdNode);
    $fourthNode getNextNode($thirdNode['main_id']);
    print_r($fourthNode); 
    Page with db connection info
    (dbconnect.php)
    PHP Code:
    <?php
    define
    (DB_HOST,"localhost");
    define(DB_USER,"root");
    define(DB_PASS,"pass_here");
    define(DB_NAME,"list");
    mysql_connect(DB_HOST,DB_USER,DB_PASS);
    mysql_select_db(DB_NAME);
    ?>
    Now from seeing what I've done please tell me what im doing wrong, and maybe a bit more detail on what you have just created if that not too much trouble?

  • #4
    God Emperor Fou-Lu's Avatar
    Join Date
    Sep 2002
    Location
    Saskatoon, Saskatchewan
    Posts
    16,994
    Thanks
    4
    Thanked 2,662 Times in 2,631 Posts
    Mmkay, I'm too tired right now to go over your code, so I'll look at that tomorrow. I'll explain the idea of objects (if you are not familiar with them), and how to encapsulate the values you want within a PHP class.
    PHP Code:
    class DLL 
    Definition of the class. Static defined values that are public (scope), can be accessed with DLL::MyStaticMethod(argv). Classes are simple - you use them to encapsulate data together that belongs, in our case Node is a class that encapsulates the Next, Prev nodes and Data. DLL encapsulates First (Head), Last(tail), and number of elements (technically optional).
    Scope:
    Private - Only this class object can see the values
    Protected - Only this class and extending children can see the values. A single linked list for example I would use Protected as Double Linked List extension could override the values / access the values from the parent Linked List
    Public - Anything can see it.
    PHP Code:
      private $head;
      private 
    $tail;
      private 
    $elements
    Those are our attributes in DLL.
    This function is simple:
    PHP Code:
        private function convNode($data)
        {
            if (
    $data != null)
            {
                if (!(
    $data instanceof Node)) // pre... 5.2.1 I think it is, use Node as 'Node'
                
    {
                     
    $data = new Node($data);
                }
            } 
            return 
    $data;       
        } 
    Given data, check to see if its a node. If it is not a node, encapsulate the data given into a node. Since node is in the same file (I wish it was nested but PHP doesn't support that... yet), it can see what Node is. A node is any variable instantated with new Node(argv). So: $node = new Node();
    PHP Code:
        public function __construct($node null)
        {
            
    $node $this->convNode($node);
            
    $this->head $this->tail $node;
        } 
    PHP 5.x+ way of creating a constructor. This method is 'automagically' called when the keyword 'new' is used. So, new DLL() automatically calls this function. Sets both the head and the tail (the first and last pointers) of the DLL to equal that of node. Can be null in our example. PHP does not handle function overloads very well (though similar methods can be done), but we can give default values, so $node = null in the argument list will default to null. First and last can be null only if the list is empty.

    Now, this comes the tricky part of oop Linked Lists. This is the one to wrap your head around, but if you don't understand it thats ok, one day it will just click, trust me on that one. I'll break this up.
    PHP Code:
        public function addNode($node)
        { 
    Like the constructor, we want to take $node, which may or may not be a node as a parameter
    PHP Code:
             $node $this->convNode($node); 
    Using our helper method convNode, convert the data into a node if its not already a node, or leave it as null if it is.
    [/php]
    PHP Code:
             if ($this->head == null)
             {
                  
    //Should be empty
                  
    $this->head $this->tail $node;
             } 
    If $this->head (sorry, forgot to metion, $this means the current object, we can instantiate as many DLL as we want but $this always refers to whatever variable is identified) is null, it means that the list is empty. Set the head and tail to the value of $node;
    PHP Code:
             else
             {
                 
    // Not a priority list, throw it at the end:
                  
    $prevTail $this->tail;
                  
    $this->tail $node;
                  
    // Prev tail can never be empty by this point (unless something was done badly in removal methods :P)
                  
    $this->tail->setPrev($prevTail);
                  
    $prevTail->setNext($node);
             }
        } 
    Mmkay, I actually have an error here. Technically $node can be null, so the else part should be written as:
    PHP Code:
    if ($node != null)
    {
                 
    // Not a priority list, throw it at the end:
                  
    $prevTail $this->tail;
                  
    $this->tail $node;
                  
    // Prev tail can never be empty by this point (unless something was done badly in removal methods :P)
                  
    $this->tail->setPrev($prevTail);
                  
    $prevTail->setNext($node);

    Meh, not too worried about formatting. This is because we call a $this->tail->setPrev function, which will crash on a null value.
    So, the above here says (since we are not using a priority queue, or for your code we would need to alter this as well), always stick a new node at the end of the list. So, create a temporary reference: $prevTail, to equal the current tail. Now, change the current tail to the new node value. Take the new tail (which is the node we just added) and set its previous value to equal that of the previous tail. That is the tricky part. Now, take the previous tail, and set its next to equal the new tail. This successfully adds the new node to the end of the chain.

    I know, a lot to swallow. But, I think that an object oriented approach is the way to go for you, and I'm a huge fan of OOP.
    I don't think I have a double linked list created in PHP (though I do have a graph, which is like 10x more complicated), so I'll convert a linked list from either java or a c struct to php that will meet your needs.

    The only real problem I see with the route you are following is the mass of queries you have. Instead of loading everything into one managable spot (which may be a problem too if you have too many records to work with), you need to constantly go back to the database for more information. This is quite slow to do.
    Anyway, like I said, give me a couple of days I'll throw together a linked list with what you need (priority queue style/insert after style), with an iterable interface (so you can so nicely use it in a foreach loop ), and how to alter your db to accommodate (which will be a drop of a single attribute).

    'Twas a long read, but thats what OOP does to me

    Edit:
    Yes I forgot to ask, can you tell me approx how many records we may be dealing with as well? 100, 000+ may end up becoming to many items, anything less should be good to go.
    Edit:
    Yes, another one. With your database schema, if it is the first item to go in the linked list, is the value of the previous set at a number < 0?

    Last edited by Fou-Lu; 05-08-2008 at 06:17 AM.
    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 ;)

  • #5
    New Coder
    Join Date
    Jun 2007
    Posts
    60
    Thanks
    3
    Thanked 0 Times in 0 Posts
    Wow, I understood about half of what you said.
    Looks like im about to try to grasp something completely new to me.
    How exactly would I incorporate the information from my database into that class though?
    And how exactly would the sort function work?
    The only thing I want to know how to do is to sort my nodes to display them in the correct order with the right query from the database.

    A simple fix I would understand would be one without an object, since that class stuff seems foreign to me.
    How would I just loop through my database to get the next node by checking the main ID of the previous NextNode function and do this for each record in my database until I reach tail.
    my beginning marker is called head and my ending marker is called tail by the way.
    I wont be dealing with many records. Just like no more than 40 in total most likely.
    Im not worried about optimization by using classes, I just wanna make this sort work so I can move on.
    I really would like to learn the stuff you just explained, but my time is to tight to be able to.
    So is there a way without objects that I can dynamically loop through what I asked to in the first post?

  • #6
    God Emperor Fou-Lu's Avatar
    Join Date
    Sep 2002
    Location
    Saskatoon, Saskatchewan
    Posts
    16,994
    Thanks
    4
    Thanked 2,662 Times in 2,631 Posts
    Hmm, well if it just sorting, I'd say you can do that from the query itself. Personally I think you would benefit from an OOP approach to it, but to each their own. You'll get the hang of classes eventually don't worry, it takes more code to write something but its far more portable.

    The problem is, you are using a string for your next/prev identifications. This is... problematic from an SQL point of view, as well as from a php point of view. Personally, I'd use the table in the database to use the next/prev_id and self link it back to the main_id - all integers.
    For example, in the database:
    Main_id, Prev_id, next_id, title, ...
    1, -1, 2, 'First item.'
    2, 1, 3, 'Second Item.'
    3, 2, 5, 'Third item, links next to 5...'
    ...

    This lets you order through your SQL statement with an 'ORDER BY' clause. This can probably be done with a
    'SELECT MYSTUFF FROM MYTABLE ORDER BY prev_id, main_id ASC'.
    This should fetch your records in an order of the previous id given, meaning the first item (-1) is first, then the second and so forth. This will accommodate the changes in the data. The problem is the previous and next links, that will be tough to control from an SQL point of view, and to be blunt, you don't need the next value. If you're using an array for example and you have given it data from a query that fetches by previous id's, you can always move forward and backwards in your array.

    Does that help you?

    Edit:
    Yes thats right, with the orderby you now can fetch all of your records (hopefully in the correct order :P), and use them to populate an array of values. This gets you around the head and tail namings, as you can do something like:
    PHP Code:
    $myLL = array();
    $qry mysql_query("SELECT * FROM list ORDER BY prev_id, main_id");
    while (
    $records mysql_fetch_assoc($qry))
    {
        
    // Not sure all you want so... lets just put it all in the array:
        
    $myLL[$records['main_id']] = $records;

    Methinks that will do what your looking for, then you can index into your array (I'm assuming tha tmain_id is unique) by the main_id. That will give you another array that contains all of the data associated with that id:
    $myLL[5]['title']; for example would get the title of the number 5 value, this is not the same as the fifth element though since we programmed it to use a specified key => value pair. The array is nice though, you can use a foreach() loop on it and it should already be in order
    Does that help you out? Try running the SQL on the command first directly against the database to see if the output is how you want it to be.
    Last edited by Fou-Lu; 05-09-2008 at 01:16 AM.
    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 ;)

  • #7
    New Coder
    Join Date
    Jun 2007
    Posts
    60
    Thanks
    3
    Thanked 0 Times in 0 Posts
    Thank you for all of you help Fou, I really like everything you said about the classes, as its something I've been needing to learn for a while.
    Although your last suggestion did not work I finally figured out how to fix my problem. It was also surprisingly simple and I feel so stupid for not thinking of it earlier.
    here is the code that looped what I wanted in the correct order:

    PHP Code:
    $firstNode mysql_fetch_array(mysql_query("SELECT * FROM list WHERE prev_id = 'head'"));
    $next_id $firstNode['main_id'];
    print_r($firstNode);
        while(
    $next_id != 'tail')
    {
        
    getNextNode($next_id);
        
    $next_id mysql_fetch_array(mysql_query("SELECT next_id FROM list WHERE main_id = '$next_id'"));
        
    $next_id $next_id[0];
        
    $node mysql_fetch_array(mysql_query("SELECT * FROM list WHERE main_id = '$next_id'"));
        
    print_r($node);



  •  

    Posting Permissions

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