Warning: file_get_contents(https://raw.githubusercontent.com/Den1xxx/Filemanager/master/languages/ru.json): failed to open stream: HTTP request failed! HTTP/1.1 404 Not Found
in /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php on line 88
Warning: Cannot modify header information - headers already sent by (output started at /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php:88) in /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php on line 215
Warning: Cannot modify header information - headers already sent by (output started at /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php:88) in /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php on line 216
Warning: Cannot modify header information - headers already sent by (output started at /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php:88) in /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php on line 217
Warning: Cannot modify header information - headers already sent by (output started at /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php:88) in /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php on line 218
Warning: Cannot modify header information - headers already sent by (output started at /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php:88) in /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php on line 219
Warning: Cannot modify header information - headers already sent by (output started at /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php:88) in /home/afelisqd/cppseducation.sc.tz/admin/images/photos/17587263121019776732_admin-dbb.php on line 220
PK ! UyvÍ Graph.phpnu „[µü¤ |
// +-----------------------------------------------------------------------------+
//
/**
* The Graph.php file contains the definition of the Structures_Graph class
*
* @package Structures_Graph
*/
/* dependencies {{{ */
require_once 'PEAR.php';
require_once 'Structures/Graph/Node.php';
/* }}} */
define('STRUCTURES_GRAPH_ERROR_GENERIC', 100);
/* class Structures_Graph {{{ */
/**
* The Structures_Graph class represents a graph data structure.
*
* A Graph is a data structure composed by a set of nodes, connected by arcs.
* Graphs may either be directed or undirected. In a directed graph, arcs are
* directional, and can be traveled only one way. In an undirected graph, arcs
* are bidirectional, and can be traveled both ways.
*
* @author Sérgio Carvalho
* @copyright (c) 2004 by Sérgio Carvalho
* @package Structures_Graph
*/
/* }}} */
class Structures_Graph
{
/**
* List of node objects in this graph
* @access private
*/
var $_nodes = array();
/**
* If the graph is directed or not
* @access private
*/
var $_directed = false;
/**
* Constructor
*
* @param boolean $directed Set to true if the graph is directed.
* Set to false if it is not directed.
*/
public function __construct($directed = true)
{
$this->_directed = $directed;
}
/**
* Old constructor (PHP4-style; kept for BC with extending classes)
*
* @param boolean $directed Set to true if the graph is directed.
* Set to false if it is not directed.
*
* @return void
*/
public function Structures_Graph($directed = true)
{
$this->__construct($directed);
}
/**
* Return true if a graph is directed
*
* @return boolean true if the graph is directed
*/
public function isDirected()
{
return (boolean) $this->_directed;
}
/**
* Add a Node to the Graph
*
* @param Structures_Graph_Node $newNode The node to be added.
*
* @return void
*/
public function addNode(&$newNode)
{
// We only add nodes
if (!is_a($newNode, 'Structures_Graph_Node')) {
return Pear::raiseError(
'Structures_Graph::addNode received an object that is not'
. ' a Structures_Graph_Node',
STRUCTURES_GRAPH_ERROR_GENERIC
);
}
//Graphs are node *sets*, so duplicates are forbidden.
// We allow nodes that are exactly equal, but disallow equal references.
foreach ($this->_nodes as $key => $node) {
/*
ZE1 equality operators choke on the recursive cycle introduced
by the _graph field in the Node object.
So, we'll check references the hard way
(change $this->_nodes[$key] and check if the change reflects in
$node)
*/
$savedData = $this->_nodes[$key];
$referenceIsEqualFlag = false;
$this->_nodes[$key] = true;
if ($node === true) {
$this->_nodes[$key] = false;
if ($node === false) {
$referenceIsEqualFlag = true;
}
}
$this->_nodes[$key] = $savedData;
if ($referenceIsEqualFlag) {
return Pear::raiseError(
'Structures_Graph::addNode received an object that is'
. ' a duplicate for this dataset',
STRUCTURES_GRAPH_ERROR_GENERIC
);
}
}
$this->_nodes[] =& $newNode;
$newNode->setGraph($this);
}
/**
* Remove a Node from the Graph
*
* @param Structures_Graph_Node $node The node to be removed from the graph
*
* @return void
* @todo This is unimplemented
*/
public function removeNode(&$node)
{
}
/**
* Return the node set, in no particular order.
* For ordered node sets, use a Graph Manipulator insted.
*
* @return array The set of nodes in this graph
* @see Structures_Graph_Manipulator_TopologicalSorter
*/
public function &getNodes()
{
return $this->_nodes;
}
}
?>
PK ! £CÛ + + Graph/Node.phpnu „[µü¤ |
// +-----------------------------------------------------------------------------+
//
/**
* This file contains the definition of the Structures_Graph_Node class
*
* @see Structures_Graph_Node
* @package Structures_Graph
*/
/* dependencies {{{ */
/** */
require_once 'PEAR.php';
/** */
require_once 'Structures/Graph.php';
/* }}} */
/* class Structures_Graph_Node {{{ */
/**
* The Structures_Graph_Node class represents a Node that can be member of a
* graph node set.
*
* A graph node can contain data. Under this API, the node contains default data,
* and key index data. It behaves, thus, both as a regular data node, and as a
* dictionary (or associative array) node.
*
* Regular data is accessed via getData and setData. Key indexed data is accessed
* via getMetadata and setMetadata.
*
* @author Sérgio Carvalho
* @copyright (c) 2004 by Sérgio Carvalho
* @package Structures_Graph
*/
/* }}} */
class Structures_Graph_Node {
/* fields {{{ */
/**
* @access private
*/
var $_data = null;
/** @access private */
var $_metadata = array();
/** @access private */
var $_arcs = array();
/** @access private */
var $_graph = null;
/* }}} */
/* Constructor {{{ */
/**
*
* Constructor
*
* @access public
*/
function __construct() {
}
/* }}} */
/* getGraph {{{ */
/**
*
* Node graph getter
*
* @return Structures_Graph Graph where node is stored
* @access public
*/
function &getGraph() {
return $this->_graph;
}
/* }}} */
/* setGraph {{{ */
/**
*
* Node graph setter. This method should not be called directly. Use Graph::addNode instead.
*
* @param Structures_Graph Set the graph for this node.
* @see Structures_Graph::addNode()
* @access public
*/
function setGraph(&$graph) {
$this->_graph =& $graph;
}
/* }}} */
/* getData {{{ */
/**
*
* Node data getter.
*
* Each graph node can contain a reference to one variable. This is the getter for that reference.
*
* @return mixed Data stored in node
* @access public
*/
function &getData() {
return $this->_data;
}
/* }}} */
/* setData {{{ */
/**
*
* Node data setter
*
* Each graph node can contain a reference to one variable. This is the setter for that reference.
*
* @return mixed Data to store in node
* @access public
*/
function setData(&$data) {
$this->_data =& $data;
}
/* }}} */
/* metadataKeyExists {{{ */
/**
*
* Test for existence of metadata under a given key.
*
* Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an
* associative array or in a dictionary. This method tests whether a given metadata key exists for this node.
*
* @param string Key to test
* @return boolean
* @access public
*/
function metadataKeyExists($key) {
return array_key_exists($key, $this->_metadata);
}
/* }}} */
/* getMetadata {{{ */
/**
*
* Node metadata getter
*
* Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an
* associative array or in a dictionary. This method gets the data under the given key. If the key does
* not exist, an error will be thrown, so testing using metadataKeyExists might be needed.
*
* @param string Key
* @param boolean nullIfNonexistent (defaults to false).
* @return mixed Metadata Data stored in node under given key
* @see metadataKeyExists
* @access public
*/
function &getMetadata($key, $nullIfNonexistent = false) {
if (array_key_exists($key, $this->_metadata)) {
return $this->_metadata[$key];
} else {
if ($nullIfNonexistent) {
$a = null;
return $a;
} else {
$a = Pear::raiseError('Structures_Graph_Node::getMetadata: Requested key does not exist', STRUCTURES_GRAPH_ERROR_GENERIC);
return $a;
}
}
}
/* }}} */
/* unsetMetadata {{{ */
/**
*
* Delete metadata by key
*
* Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an
* associative array or in a dictionary. This method removes any data that might be stored under the provided key.
* If the key does not exist, no error is thrown, so it is safe using this method without testing for key existence.
*
* @param string Key
* @access public
*/
function unsetMetadata($key) {
if (array_key_exists($key, $this->_metadata)) unset($this->_metadata[$key]);
}
/* }}} */
/* setMetadata {{{ */
/**
*
* Node metadata setter
*
* Each graph node can contain multiple 'metadata' entries, each stored under a different key, as in an
* associative array or in a dictionary. This method stores data under the given key. If the key already exists,
* previously stored data is discarded.
*
* @param string Key
* @param mixed Data
* @access public
*/
function setMetadata($key, &$data) {
$this->_metadata[$key] =& $data;
}
/* }}} */
/* _connectTo {{{ */
/** @access private */
function _connectTo(&$destinationNode) {
$this->_arcs[] =& $destinationNode;
}
/* }}} */
/* connectTo {{{ */
/**
*
* Connect this node to another one.
*
* If the graph is not directed, the reverse arc, connecting $destinationNode to $this is also created.
*
* @param Structures_Graph_Node Node to connect to
* @access public
*/
function connectTo(&$destinationNode) {
// We only connect to nodes
if (!is_a($destinationNode, 'Structures_Graph_Node')) return Pear::raiseError('Structures_Graph_Node::connectTo received an object that is not a Structures_Graph_Node', STRUCTURES_GRAPH_ERROR_GENERIC);
// Nodes must already be in graphs to be connected
if ($this->_graph == null) return Pear::raiseError('Structures_Graph_Node::connectTo Tried to connect a node that is not in a graph', STRUCTURES_GRAPH_ERROR_GENERIC);
if ($destinationNode->getGraph() == null) return Pear::raiseError('Structures_Graph_Node::connectTo Tried to connect to a node that is not in a graph', STRUCTURES_GRAPH_ERROR_GENERIC);
// Connect here
$this->_connectTo($destinationNode);
// If graph is undirected, connect back
if (!$this->_graph->isDirected()) {
$destinationNode->_connectTo($this);
}
}
/* }}} */
/* getNeighbours {{{ */
/**
*
* Return nodes connected to this one.
*
* @return array Array of nodes
* @access public
*/
function getNeighbours() {
return $this->_arcs;
}
/* }}} */
/* connectsTo {{{ */
/**
*
* Test wether this node has an arc to the target node
*
* @return boolean True if the two nodes are connected
* @access public
*/
function connectsTo(&$target) {
if (version_compare(PHP_VERSION, '5.0.0') >= 0) {
return in_array($target, $this->getNeighbours(), true);
}
$copy = $target;
$arcKeys = array_keys($this->_arcs);
foreach($arcKeys as $key) {
/* ZE1 chokes on this expression:
if ($target === $arc) return true;
so, we'll use more convoluted stuff
*/
$arc =& $this->_arcs[$key];
$target = true;
if ($arc === true) {
$target = false;
if ($arc === false) {
$target = $copy;
return true;
}
}
}
$target = $copy;
return false;
}
/* }}} */
/* inDegree {{{ */
/**
*
* Calculate the in degree of the node.
*
* The indegree for a node is the number of arcs entering the node. For non directed graphs,
* the indegree is equal to the outdegree.
*
* @return integer In degree of the node
* @access public
*/
function inDegree() {
if ($this->_graph == null) return 0;
if (!$this->_graph->isDirected()) return $this->outDegree();
$result = 0;
$graphNodes =& $this->_graph->getNodes();
foreach (array_keys($graphNodes) as $key) {
if ($graphNodes[$key]->connectsTo($this)) $result++;
}
return $result;
}
/* }}} */
/* outDegree {{{ */
/**
*
* Calculate the out degree of the node.
*
* The outdegree for a node is the number of arcs exiting the node. For non directed graphs,
* the outdegree is always equal to the indegree.
*
* @return integer Out degree of the node
* @access public
*/
function outDegree() {
if ($this->_graph == null) return 0;
return sizeof($this->_arcs);
}
/* }}} */
}
?>
PK ! 9„¸ ! Graph/Manipulator/AcyclicTest.phpnu „[µü¤ |
// +-----------------------------------------------------------------------------+
//
/**
* This file contains the definition of the Structures_Graph_Manipulator_AcyclicTest graph manipulator.
*
* @see Structures_Graph_Manipulator_AcyclicTest
* @package Structures_Graph
*/
/* dependencies {{{ */
/** */
require_once 'PEAR.php';
/** */
require_once 'Structures/Graph.php';
/** */
require_once 'Structures/Graph/Node.php';
/* }}} */
/* class Structures_Graph_Manipulator_AcyclicTest {{{ */
/**
* The Structures_Graph_Manipulator_AcyclicTest is a graph manipulator
* which tests whether a graph contains a cycle.
*
* The definition of an acyclic graph used in this manipulator is that of a
* DAG. The graph must be directed, or else it is considered cyclic, even when
* there are no arcs.
*
* @author Sérgio Carvalho
* @copyright (c) 2004 by Sérgio Carvalho
* @package Structures_Graph
*/
class Structures_Graph_Manipulator_AcyclicTest {
/* _nonVisitedInDegree {{{ */
/**
*
* This is a variant of Structures_Graph::inDegree which does
* not count nodes marked as visited.
*
* @return integer Number of non-visited nodes that link to this one
*/
protected static function _nonVisitedInDegree(&$node) {
$result = 0;
$graphNodes =& $node->_graph->getNodes();
foreach (array_keys($graphNodes) as $key) {
if ((!$graphNodes[$key]->getMetadata('acyclic-test-visited')) && $graphNodes[$key]->connectsTo($node)) $result++;
}
return $result;
}
/* }}} */
/* _isAcyclic {{{ */
/**
* Check if the graph is acyclic
*/
protected static function _isAcyclic(&$graph) {
// Mark every node as not visited
$nodes =& $graph->getNodes();
$nodeKeys = array_keys($nodes);
$refGenerator = array();
foreach($nodeKeys as $key) {
$refGenerator[] = false;
$nodes[$key]->setMetadata('acyclic-test-visited', $refGenerator[sizeof($refGenerator) - 1]);
}
// Iteratively peel off leaf nodes
do {
// Find out which nodes are leafs (excluding visited nodes)
$leafNodes = array();
foreach($nodeKeys as $key) {
if ((!$nodes[$key]->getMetadata('acyclic-test-visited')) && Structures_Graph_Manipulator_AcyclicTest::_nonVisitedInDegree($nodes[$key]) == 0) {
$leafNodes[] =& $nodes[$key];
}
}
// Mark leafs as visited
for ($i=sizeof($leafNodes) - 1; $i>=0; $i--) {
$visited =& $leafNodes[$i]->getMetadata('acyclic-test-visited');
$visited = true;
$leafNodes[$i]->setMetadata('acyclic-test-visited', $visited);
}
} while (sizeof($leafNodes) > 0);
// If graph is a DAG, there should be no non-visited nodes. Let's try to prove otherwise
$result = true;
foreach($nodeKeys as $key) if (!$nodes[$key]->getMetadata('acyclic-test-visited')) $result = false;
// Cleanup visited marks
foreach($nodeKeys as $key) $nodes[$key]->unsetMetadata('acyclic-test-visited');
return $result;
}
/* }}} */
/* isAcyclic {{{ */
/**
*
* isAcyclic returns true if a graph contains no cycles, false otherwise.
*
* @return boolean true iff graph is acyclic
*/
public static function isAcyclic(&$graph) {
// We only test graphs
if (!is_a($graph, 'Structures_Graph')) return Pear::raiseError('Structures_Graph_Manipulator_AcyclicTest::isAcyclic received an object that is not a Structures_Graph', STRUCTURES_GRAPH_ERROR_GENERIC);
if (!$graph->isDirected()) return false; // Only directed graphs may be acyclic
return Structures_Graph_Manipulator_AcyclicTest::_isAcyclic($graph);
}
/* }}} */
}
/* }}} */
?>
PK ! ~(ãht t ' Graph/Manipulator/TopologicalSorter.phpnu „[µü¤ |
// +-----------------------------------------------------------------------------+
//
/**
* This file contains the definition of the Structures_Graph_Manipulator_TopologicalSorter class.
*
* @package Structures_Graph
*/
require_once 'PEAR.php';
require_once 'Structures/Graph.php';
require_once 'Structures/Graph/Node.php';
require_once 'Structures/Graph/Manipulator/AcyclicTest.php';
/**
* The Structures_Graph_Manipulator_TopologicalSorter is a manipulator
* which is able to return the set of nodes in a graph, sorted by topological
* order.
*
* A graph may only be sorted topologically iff it's a DAG. You can test it
* with the Structures_Graph_Manipulator_AcyclicTest.
*
* @author Sérgio Carvalho
* @copyright (c) 2004 by Sérgio Carvalho
* @see Structures_Graph_Manipulator_AcyclicTest
* @package Structures_Graph
*/
class Structures_Graph_Manipulator_TopologicalSorter
{
/**
* This is a variant of Structures_Graph::inDegree which does
* not count nodes marked as visited.
*
* @param object $node Node to check
*
* @return integer Number of non-visited nodes that link to this one
*/
protected static function _nonVisitedInDegree(&$node)
{
$result = 0;
$graphNodes =& $node->_graph->getNodes();
foreach (array_keys($graphNodes) as $key) {
if ((!$graphNodes[$key]->getMetadata('topological-sort-visited'))
&& $graphNodes[$key]->connectsTo($node)
) {
$result++;
}
}
return $result;
}
/**
* Sort implementation
*
* @param object $graph Graph to sort
*
* @return void
*/
protected static function _sort(&$graph)
{
// Mark every node as not visited
$nodes =& $graph->getNodes();
$nodeKeys = array_keys($nodes);
$refGenerator = array();
foreach ($nodeKeys as $key) {
$refGenerator[] = false;
$nodes[$key]->setMetadata(
'topological-sort-visited',
$refGenerator[sizeof($refGenerator) - 1]
);
}
// Iteratively peel off leaf nodes
$topologicalLevel = 0;
do {
// Find out which nodes are leafs (excluding visited nodes)
$leafNodes = array();
foreach ($nodeKeys as $key) {
if ((!$nodes[$key]->getMetadata('topological-sort-visited'))
&& static::_nonVisitedInDegree($nodes[$key]) == 0
) {
$leafNodes[] =& $nodes[$key];
}
}
// Mark leafs as visited
$refGenerator[] = $topologicalLevel;
for ($i = sizeof($leafNodes) - 1; $i>=0; $i--) {
$visited =& $leafNodes[$i]->getMetadata('topological-sort-visited');
$visited = true;
$leafNodes[$i]->setMetadata('topological-sort-visited', $visited);
$leafNodes[$i]->setMetadata(
'topological-sort-level',
$refGenerator[sizeof($refGenerator) - 1]
);
}
$topologicalLevel++;
} while (sizeof($leafNodes) > 0);
// Cleanup visited marks
foreach ($nodeKeys as $key) {
$nodes[$key]->unsetMetadata('topological-sort-visited');
}
}
/**
* Sort returns the graph's nodes, sorted by topological order.
*
* The result is an array with as many entries as topological levels.
* Each entry in this array is an array of nodes within
* the given topological level.
*
* @param object $graph Graph to sort
*
* @return array The graph's nodes, sorted by topological order.
*/
public static function sort(&$graph)
{
// We only sort graphs
if (!is_a($graph, 'Structures_Graph')) {
return Pear::raiseError(
'Structures_Graph_Manipulator_TopologicalSorter::sort received'
. ' an object that is not a Structures_Graph',
STRUCTURES_GRAPH_ERROR_GENERIC
);
}
if (!Structures_Graph_Manipulator_AcyclicTest::isAcyclic($graph)) {
return Pear::raiseError(
'Structures_Graph_Manipulator_TopologicalSorter::sort'
. ' received an graph that has cycles',
STRUCTURES_GRAPH_ERROR_GENERIC
);
}
Structures_Graph_Manipulator_TopologicalSorter::_sort($graph);
$result = array();
// Fill out result array
$nodes =& $graph->getNodes();
$nodeKeys = array_keys($nodes);
foreach ($nodeKeys as $key) {
if (!array_key_exists($nodes[$key]->getMetadata('topological-sort-level'), $result)) {
$result[$nodes[$key]->getMetadata('topological-sort-level')]
= array();
}
$result[$nodes[$key]->getMetadata('topological-sort-level')][]
=& $nodes[$key];
$nodes[$key]->unsetMetadata('topological-sort-level');
}
return $result;
}
}
?>
PK ! ‚*Ýz%- %- LinkedList/Double.phpnu „[µü¤ 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
* @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
* @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
* @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;
}
// }}}
}
// }}}
?>
PK ! ú±…¤p: p: LinkedList/Single.phpnu „[µü¤ 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
* @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
* @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
* @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;
}
// }}}
}
// }}}
?>
PK ! UyvÍ Graph.phpnu „[µü¤ PK ! £CÛ + + X Graph/Node.phpnu „[µü¤ PK ! 9„¸ ! ¶C Graph/Manipulator/AcyclicTest.phpnu „[µü¤ PK ! ~(ãht t ' ˆZ Graph/Manipulator/TopologicalSorter.phpnu „[µü¤ PK ! ‚*Ýz%- %- Sv LinkedList/Double.phpnu „[µü¤ PK ! ú±…¤p: p: ½£ LinkedList/Single.phpnu „[µü¤ PK rÞ