Viewing file:  Single.php (14.61 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
<?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: Single.php -1 $
* @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;
}
}
// }}}
// {{{ Destructor: function __destruct()
/**
* Structures_LinkedList_Single destructor
*
* If we do not destroy all of the references in the linked list,
* we will quickly run out of memory for large / complex structures.
*
*/
function __destruct()
{
/*
* Starting with root node, set last node = root_node
* get next node
* if next node exists, delete last node reference to next node
*/
if (!$last_node = $this->root_node) {
return;
}
while (($next_node = $last_node->next()) !== false) {
$last_node->setNext(null);
$temp_node = $last_node;
$last_node = $next_node;
unset($temp_node);
}
$this->current = null;
$this->root_node = null;
$last_node = null;
$next_node = 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;
}
// }}}
// {{{ protected function getTailNode()
/**
* Returns the tail node of the linked list.
*
* This is an expensive operation!
*
* @return bool Success or failure
**/
protected function getTailNode()
{
$tail_node = $this->root_node;
while (($y = $tail_node->next()) !== false) {
$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!
*
* @param Structures_LinkedList_SingleNode $node (Optional) Specific node
* for which we want to find the previous node
*
* @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()) !== false) {
if ($y == $node) {
return $prior_node;
}
$prior_node = $y;
}
return null;
}
// }}}
// {{{ 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($new_node, $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;
}
$previous_node = $this->_getPreviousNode($existing_node);
if ($previous_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_node, true);
return true;
}
// }}}
// {{{ function deleteNode()
/**
* Deletes a {@link Structures_LinkedList_SingleNode} from the list.
*
* @param Structures_LinkedList_SingleNode $node Node to delete.
*
* @return null
*/
public function deleteNode($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($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($node = null)
{
return false;
}
// }}}
}
// }}}
?>
|