<?php

/* vim: set expandtab shiftwidth=4 tabstop=4 softtabstop=4 foldmethod=marker textwidth=80: */

/**
 * Linked list structure
 * 
 * This package implements a singly linked list structure. Each node
 * (Structures_LinkedList_SingleNode object) in the list
 * (Structures_LinkedList_Single) knows the the next node in the list.
 * Unlike an array, you can insert or delete nodes at arbitrary points
 * in the list.
 *
 * If your application normally traverses the linked list in a forward-only
 * direction, use the singly-linked list implemented by
 * {@link Structures_LinkedList_Single}. If, however, your application
 * needs to traverse the list backwards, or insert nodes into the list before
 * other nodes in the list, use the double-linked list implemented by
 * {@link Structures_LinkedList_Double} to give your application better
 * performance at the cost of a slightly larger memory footprint.
 *
 * Structures_LinkedList_Single implements the Iterator interface so control
 * structures like foreach($list as $node) and while($list->next()) work
 * as expected.
 *
 * To use this package, derive a child class from
 * Structures_LinkedList_SingleNode and add data to the object. Then use the
 * Structures_LinkedList_Single class to access the nodes.
 *
 * PHP version 5
 *
 * LICENSE:  Copyright 2006 Dan Scott
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may
 * not use this file except in compliance with the License. You may obtain
 * a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * @category   Structures
 * @package    Structures_LinkedList_Single
 * @author     Dan Scott <dscott@laurentian.ca>
 * @copyright  2006 Dan Scott
 * @license    http://www.apache.org/licenses/LICENSE-2.0  Apache License, Version 2.0
 * @version    CVS: $Id:$
 * @link       http://pear.php.net/package/Structures_LinkedList_Single
 * @example    single_link_example.php
 *
 * @todo Add some actual error conditions
 **/

require_once 'PEAR/Exception.php';

// {{{ class Structures_LinkedList_Single
/**
 * The Structures_LinkedList_Single class represents a linked list structure
 * composed of {@link Structures_LinkedList_SingleNode} objects.
 *
 * @category   Structures
 * @package    Structures_LinkedList_Single
 * @author     Dan Scott <dscott@laurentian.ca>
 * @license    http://www.apache.org/licenses/LICENSE-2.0  Apache License, Version 2.0
 * @link       http://pear.php.net/package/Structures_LinkedList_Single
 */
class Structures_LinkedList_Single implements Iterator {
    
// {{{ properties
    /**
     * Current node in the linked list
     * @var Structures_LinkedList_SingleNode
     */
    
protected $current;

    
/**
     * Root node of the linked list
     * @var Structures_LinkedList_SingleNode
     */
    
protected $root_node;

    
/**
     * The linked list contains no nodes
     */
    
const ERROR_EMPTY = -1;

    public static 
$messages = array(
        
self::ERROR_EMPTY => 'No nodes in this linked list' 
    
);
    
// }}}

    // {{{ Constructor: function __construct()
    /**
     * Structures_LinkedList_Single constructor
     *
     * @param Structures_LinkedList_SingleNode $root root node for the
     * linked list
     */
    
function __construct(Structures_LinkedList_SingleNode $root null)
    {
        if (
$root) {
            
$this->root_node $root;
            
$this->current $root;
        } else {
            
$this->root_node null;
            
$this->current null;
        }
    }
    
// }}}

    // {{{ function current()
    /**
     * Returns the current node in the linked list
     *
     * @return Structures_LinkedList_SingleNode current node in the linked list
     */
    
public function current()
    {
        return 
$this->current;
    }
    
// }}}

    // {{{ function rewind()
    /**
     * Sets the pointer for the linked list to the root node
     *
     * @return Structures_LinkedList_SingleNode root node in the linked list
     */
    
public function rewind()
    {
        if (
$this->root_node) {
            
$this->current $this->root_node;
        } else {
            
$this->current null;
        }
        return 
$this->current;
    }
    
// }}}

    // {{{ function end()
    /**
     * Sets the pointer for the linked list to the root node
     *
     * @return Structures_LinkedList_SingleNode root node in the linked list
     */
    
public function end()
    {
        
$this->current $this->_getTailNode();
        return 
$this->current;
    }
    
// }}}

    // {{{ function key()
    /**
     * Stub for Iterator interface that simply returns the current node
     *
     * @return Structures_LinkedList_SingleNode current node in the linked list
     */
    
public function key()
    {
        return 
$this->current;
    }
    
// }}}

    // {{{ function valid()
    /**
     * Stub for Iterator interface that simply returns the current node
     *
     * @return Structures_LinkedList_SingleNode current node in the linked list
     */
    
public function valid()
    {
        return 
$this->current();
    }
    
// }}}

    // {{{ function next()
    /**
     * Sets the pointer for the linked list to the next node and
     * returns that node
     *
     * @return Structures_LinkedList_SingleNode next node in the linked list
     */
    
public function next()
    {
        if (!
$this->current) {
            return 
false;
        }
        
$this->current $this->current()->next();
        return 
$this->current;
    }
    
// }}}

    // {{{ function previous()
    /**
     * Sets the pointer for the linked list to the previous node and
     * returns that node
     *
     * @return Structures_LinkedList_SingleNode previous node in the linked list
     */
    
public function previous()
    {
        if (!
$this->current) {
            return 
false;
        }
        
$this->current $this->_getPreviousNode();
        return 
$this->current;
    }
    
// }}}

    // {{{ private function _getTailNode()
    /**
     * Returns the tail node of the linked list.
     *
     * This is an expensive operation!
     *
     * @param Structures_LinkedList_SingleNode $new_node New node to append
     * @return bool Success or failure
     **/
    
private function _getTailNode()
    {
        
$tail_node $this->root_node;
        while (
$y $tail_node->next()) {
            
$tail_node $y;
        }
        return 
$tail_node;
    }
    
// }}}

    // {{{ private function _getPreviousNode()
    /**
     * Returns the node prior to the current node in the linked list.
     *
     * This is an expensive operation for a singly linked list!
     *
     * @return Structures_LinkedList_SingleNode Previous node
     **/
    
private function _getPreviousNode($node null)
    {
        if (!
$node) {
            
$node $this->current;
        }
        
$prior_node $this->root_node;
        while (
$y $prior_node->next()) {
            if (
$y == $node) {
                return 
$prior_node;
            }
            
$prior_node $y;
        }
    }
    
// }}}

    // {{{ function appendNode()
    /**
     * Adds a {@link Structures_LinkedList_SingleNode} object to the end of
     * the linked list.
     *
     * @param Structures_LinkedList_SingleNode $new_node New node to append
     * @return bool Success or failure
     **/
    
public function appendNode(Structures_LinkedList_SingleNode $new_node)
    {
        if (!
$this->root_node) {
            
$this->__construct($new_node);
            return 
true;
        }

        
// This is just a special case of insertNode()
        
$this->insertNode($new_node$this->_getTailNode());

        return 
true;
    }
    
// }}}

    // {{{ function insertNode()
    /**
     * Inserts a {@link Structures_LinkedList_SingleNode} object into the linked
     * list, based on a reference node that already exists in the list.
     *
     * @param Structures_LinkedList_SingleNode $new_node New node to add to
     * the list
     * @param Structures_LinkedList_SingleNode $existing_node Reference
     * position node
     * @param bool $before Insert new node before or after the existing node
     * @return bool Success or failure
     **/
    
public function insertNode(Structures_LinkedList_SingleNode $new_nodeStructures_LinkedList_SingleNode $existing_node$before false)
    {
        if (!
$this->root_node) {
            
$this->__construct($new_node);
            return 
true;
        }

        
// Now add the node according to the requested mode
        
switch ($before) {

        case 
true:
            if (
$existing_node === $this->root_node) {
                
$this->root_node $new_node;
            }
            if (
$previous_node $this->_getPreviousNode($existing_node)) {
                
$previous_node->setNext($new_node);
            }
            
$new_node->setNext($existing_node);

            break;

        case 
false:
            
$next_node $existing_node->next();
            if (
$next_node) {
                
$new_node->setNext($next_node);
            }
            
$existing_node->setNext($new_node);

            break;

        }

        return 
true;
    }
    
// }}}

    // {{{ function prependNode()
    /**
     * Adds a {@link Structures_LinkedList_SingleNode} object to the start
     * of the linked list.
     *
     * @param Structures_LinkedList_SingleNode $new_node Node to prepend
     * to the list
     * @return bool Success or failure
     **/
    
public function prependNode(Structures_LinkedList_SingleNode $new_node)
    {
        if (!
$this->root_node) {
            
$this->__construct($new_node);
            return 
true;
        }

        
// This is just a special case of insertNode()
        
$this->insertNode($new_node$this->root_nodetrue);

        return 
true;
    }
    
// }}}

    // {{{ function deleteNode()
    /**
     * Deletes a {@link Structures_LinkedList_SingleNode} from the list.
     *
     * @param Structures_LinkedList_SingleNode $node Node to delete.
     */
    
public function deleteNode(Structures_LinkedList_SingleNode $node)
    {
        
/* If this is the root node, and there are more nodes in the list,
         * make the next node the new root node before deleting this node.
         */
        
if ($node === $this->root_node) {
            
$this->root_node $node->next();
        }
        
        
/* If this is the current node, make the next node the current node.
         *
         * If that fails, null isn't such a bad place to be.
         */
        
if ($node === $this->current) {
            if (
$node->next()) {
                
$this->current $node->next();
            } else {
                
$this->current null;
            }
        }
        
$node->__destruct();
    }
    
// }}}

}
// }}}

// {{{ class Structures_LinkedList_SingleNode
/**
 * The Structures_LinkedList_SingleNode class represents a node in a
 * {@link Structures_LinkedList_Single} linked list structure.
 *
 * @category   Structures
 * @package    Structures_LinkedList_Single
 * @author     Dan Scott <dscott@laurentian.ca>
 * @license    http://www.apache.org/licenses/LICENSE-2.0  Apache License, Version 2.0
 * @link       http://pear.php.net/package/Structures_LinkedList_Single
 */
class Structures_LinkedList_SingleNode {
    
// {{{ properties
    /**
     * Next node in the linked list
     * @var Structures_LinkedList_SingleNode
     */
    
protected $next;
    
// }}}

    // {{{ Constructor: function __construct()
    /**
     * Structures_LinkedList_SingleNode constructor
     */
    
public function __construct()
    {
        
$this->next null;
    }
    
// }}}

    // {{{ Destructor: function __destruct()
    /**
     * Removes node from the list, adjusting the related nodes accordingly.
     *
     * This is a problem if the node is the root node for the list.
     * At this point, however, we do not have access to the list itself. Hmm.
     */
    
public function __destruct()
    {
    }
    
// }}}

    // {{{ function next()
    /**
     * Return the next node in the linked list
     *
     * @return Structures_LinkedList_SingleNode next node in the linked list
     */
    
public function next()
    {
        if (
$this->next) {
            return 
$this->next;
        } else {
            return 
false;
        }
    }
    
// }}}

    // {{{ function previous()
    /**
     * Return the previous node in the linked list
     *
     * Stub method for Structures_LinkedList_DoubleNode to override.
     *
     * @return Structures_LinkedList_SingleNode previous node in the linked list
     */
    
public function previous()
    {
        return 
false;
    }
    
// }}}

    // {{{ function setNext()
    /**
     * Sets the pointer for the next node in the linked list to the
     * specified node
     *
     * @param Structures_LinkedList_SingleNode $node new next node in
     * the linked list
     * @return Structures_LinkedList_SingleNode new next node in the linked list
     */
    
public function setNext(Structures_LinkedList_SingleNode $node null)
    {
        
$this->next $node;
        return 
$this->next;
    }
    
// }}}

    // {{{ function setPrevious()
    /**
     * Sets the pointer for the next node in the linked list to the
     * specified node
     *
     * Stub method for Structures_LinkedList_DoubleNode to override.
     *
     * @param Structures_LinkedList_SingleNode $node new next node in
     * the linked list
     * @return Structures_LinkedList_SingleNode new next node in the linked list
     */
    
public function setPrevious(Structures_LinkedList_SingleNode $node null)
    {
        return 
false;
    }
    
// }}}
}

// }}}

?>