Viewing file:  Double.php (11.29 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 doubly linked list structure. Each node
* (Structures_LinkedList_DoubleNode object) in the list
* (Structures_LinkedList_Double) knows the previous node and 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_Double 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_DoubleNode and add data to the object. Then use the
* Structures_LinkedList_Double 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_Double
* @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: Double.php -1 $
* @link http://pear.php.net/package/Structures_LinkedList
* @example double_link_example.php
*
* @todo Add some actual error conditions
**/
require_once 'PEAR/Exception.php';
require_once 'Single.php';
// {{{ class Structures_LinkedList_Double
/**
* The Structures_LinkedList_Double class represents a linked list structure
* composed of {@link Structures_LinkedList_DoubleNode} objects.
*
* @category Structures
* @package Structures_LinkedList_Double
* @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
*/
class Structures_LinkedList_Double extends Structures_LinkedList_Single implements Iterator
{
// {{{ properties
/**
* Tail node of the linked list
* @var Structures_LinkedList_DoubleNode
*/
protected $tail_node;
// }}}
// {{{ Constructor: function __construct()
/**
* Structures_LinkedList_Double constructor
*
* @param Structures_LinkedList_DoubleNode $root root node for the
* linked list
*/
function __construct(Structures_LinkedList_DoubleNode $root = null)
{
if ($root) {
$this->tail_node = $root;
} else {
$this->tail_node = null;
}
parent::__construct($root);
}
// }}}
// {{{ Destructor: function __destruct()
/**
* Structures_LinkedList_Double 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's references to next node and previous node
* make the old next node the new last node
*/
if (!$last_node = $this->root_node) {
return;
}
while (($next_node = $last_node->next()) !== false) {
$last_node->setNext(null);
$last_node->setPrevious(null);
$last_node = $next_node;
}
$this->current = null;
$this->root_node = null;
$this->tail_node = null;
$last_node = null;
$next_node = null;
}
// }}}
// {{{ function end()
/**
* Sets the pointer for the linked list to its last node
*
* @return Structures_LinkedList_DoubleNode last node in the linked list
*/
public function end()
{
if ($this->tail_node) {
$this->current = $this->tail_node;
} else {
$this->current = null;
}
return $this->current;
}
// }}}
// {{{ function previous()
/**
* Sets the pointer for the linked list to the previous node and
* returns that node
*
* @return Structures_LinkedList_DoubleNode previous node in the linked list
*/
public function previous()
{
if (!$this->current()->previous()) {
return false;
}
$this->current = $this->current()->previous();
return $this->current();
}
// }}}
// {{{ function insertNode()
/**
* Inserts a {@link Structures_LinkedList_DoubleNode} object into the linked
* list, based on a reference node that already exists in the list.
*
* @param Structures_LinkedList_DoubleNode $new_node New node to add to the list
* @param Structures_LinkedList_DoubleNode $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);
}
// Now add the node according to the requested mode
switch ($before) {
case true:
$previous_node = $existing_node->previous();
if ($previous_node) {
$previous_node->setNext($new_node);
$new_node->setPrevious($previous_node);
} else {
// The existing node must be root node; make new node root
$this->root_node = $new_node;
$new_node->setPrevious();
}
$new_node->setNext($existing_node);
$existing_node->setPrevious($new_node);
break;
case false:
$new_node->setPrevious($existing_node);
$next_node = $existing_node->next();
if ($next_node) {
$new_node->setNext($next_node);
$next_node->setPrevious($new_node);
} else {
// The existing node must have been the tail node
$this->tail_node = $new_node;
}
$existing_node->setNext($new_node);
break;
}
return true;
}
// }}}
// {{{ protected function getTailNode()
/**
* Returns the tail node of the linked list.
*
* This is a cheap operation for a doubly-linked list.
*
* @return bool Success or failure
**/
protected function getTailNode()
{
return $this->tail_node;
}
// }}}
// {{{ function deleteNode()
/**
* Deletes a {@link Structures_LinkedList_DoubleNode} from the list.
*
* @param Structures_LinkedList_DoubleNode $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 tail node, and there are more nodes in the list,
* make the previous node the tail node before deleting this node
*/
if ($node === $this->tail_node) {
$this->tail_node = $node->previous();
}
/* If this is the current node, and there are other nodes in the list,
* try making the previous node the current node so that next() works
* as expected.
*
* If that fails, 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->previous()) {
$this->current = $node->previous();
} elseif ($node->next()) {
$this->current = $node->next();
} else {
$this->current = null;
}
}
$node->__destruct();
}
// }}}
}
// }}}
// {{{ class Structures_LinkedList_DoubleNode
/**
* The Structures_LinkedList_DoubleNode class represents a node in a
* {@link Structures_LinkedList_Double} linked list structure.
*
* @category Structures
* @package Structures_LinkedList_Double
* @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
*/
class Structures_LinkedList_DoubleNode extends Structures_LinkedList_SingleNode
{
// {{{ properties
/**
* Previous node in the linked list
* @var Structures_LinkedList_DoubleNode
*/
protected $previous;
// }}}
// {{{ Constructor: function __construct()
/**
* Structures_LinkedList_DoubleNode constructor
*/
public function __construct()
{
$this->next = null;
$this->previous = 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()
{
$next = $this->next();
$previous = $this->previous();
if ($previous && $next) {
$previous->setNext($next);
$next->setPrevious($previous);
} elseif ($previous) {
$previous->setNext();
} elseif ($next) {
$next->setPrevious();
}
}
// }}}
// {{{ function previous()
/**
* Return the previous node in the linked list
*
* @return Structures_LinkedList_DoubleNode previous node in the linked list
*/
public function previous()
{
if ($this->previous) {
return $this->previous;
} else {
return false;
}
}
// }}}
// {{{ function setPrevious()
/**
* Sets the pointer for the previous node in the linked list
* to the specified node
*
* @param Structures_LinkedList_DoubleNode $node new previous node
* in the linked list
*
* @return Structures_LinkedList_DoubleNode new previous node in
* the linked list
*/
public function setPrevious($node = null)
{
$this->previous = $node;
return $this->previous;
}
// }}}
}
// }}}
?>
|