File: class.LinkedList.php

<?
/*
  Double-Ended Linked-List PHP class.
  Scott Hurring ([email protected])

  This code is public domain, but i do hope that if you use
  portions of it you give me some credit.  Thanks.

  	I felt like learning about PHP References, so i wrote
  	this little implementation of a Linked List for PHP.

  	... PHP supports all this stuff natively, so this code
  	really doesn't serve much purpose, other than being a
  	good tool to help me learn a bit more about references.

	In PHP, if you have an array of "nodes", see:
  	array_push(), array_unshift(), array_pop(), and array_shift();

	The "node" structure ($this->node) can be *any* kind of array you want.

    // Functions provided by this class

	push($node)	Adds the node to the END of the list
	pop()		Removes a node from the END of the list

	unshift($node)	Adds the node to the BEGINNING of the list
	shift()		Removes a node from the BEGINNING of the list

    // How the code works

	// Get a fresh node to populate
	$node = $list->node();

	// Populate it
	$node['field'] = "Some data";

	// Put it onto the list
	$list->push($node);
	$list->unshift($node);

	// You get the idea...

*/

class LinkedList
{

  /*
  Define node structure here
  (don't touch 'next', it points to the next node)
  */
  var $_node = array(
	// Contains reference to next node
  	'next'		=> NULL,

	// Define your node structure below:

	// Process ID
  	'pid'		=> 0,
	// Time of process start
	'start'		=> 0,
	// Duration of process
	'duration'	=> 0,
  );

  // Head is a reference to first node
  // (which should always be an empty 'dummy' head node)
  var $head = NULL;

  // Number of nodes in the linked list
  // (not including the 'dummy' head node)
  var $count = 0;

  // Set $dbg=1 to print some debugging info
  var $dbg = 0;


// Constructor
function LinkedList()
{
	// Create and insert 'dummy' head node at beginning of list
	$dummy_head = $this->_node;
	$this->head = &$dummy_head;

	$this->debug("[LinkedList]: Constructor, creating dumy head");
}


/*
  Put $node onto BOTTOM of list
*/
function unshift(&$node)
{
	// Get pointer to first node
	$first =& $this->first();

	// $node is now the first item
	$node['next'] = $first;

	// point the dummy head at $node
	$this->head['next'] = $node;

	$this->count++;
	return 1;
}


/*
  Remove (and return) BOTTOM element from the list
  Returns NULL if list is empty
*/
function shift()
{
	// Get copy of first node
	$first = $this->first();

	// There is no first item
	if ($first == NULL)
		return NULL;

	// Point the 'dummy' head at the node after the removed node ($first)
	$this->head['next'] = $first['next'];

	// Clear pointers for the removed node
	$first['next'] = NULL;
	$first['prev'] = NULL;

	$this->count--;
	return $first;
}


/*
  Put $node onto the TOP of the list
*/
function push(&$node)
{
	// Get pointer to last node
	$last =& $this->last();

	$this->debug("[push]: current last = {$last['pid']}    new last = {$node['pid']}");

	// Insert $node after the current last element
	$last['next'] = $node;

	// $node is now the end of the list
	$node['next'] = NULL;

	$this->count++;
	return 1;
}


/*
  Remove (and return) TOP node from the list
  Returns NULL if list is empty
*/
function pop()
{
	$last = $this->last();
	$next_to_last =& $this->next_to_last();

	// If the last item is the head, then it's an empty list
	if ($last == $this->head)
		return NULL;

	$this->debug("[pop]: last = {$last['pid']}     next_to_last = {$next_to_last['pid']}");

	// next_to_last is now the end
	$next_to_last['next'] = NULL;

	$this->count--;
	return $last;
}


/*
  Return the BOTTOM node without modifying the list.
  Returns NULL if list is empty

  $node =& $this->first()	returns pointer to actual node
  $node = $this->first()	returns copy of node data
*/
function &first()
{
	// Pointer to the first 'non-dummy' element
	$curr =& $this->head['next'];

	// List is empty
	if ($curr == NULL)
		return NULL;

	return $curr;
}


/*
  Return the TOP node without modifying the list.
  Returns NULL if list is empty

  $node =& $this->last()	returns pointer to actual node
  $node = $this->last()		returns copy of node data
*/
function &last()
{
	// Get pointer to the 'dummy' head node
	$curr =& $this->head;

	// Iterate through list BOTTOM->TOP, until reaching the TOP node
	while($curr['next'] != NULL)
		$curr = &$curr['next'];

	return $curr;
}


/*
  Return the next-to-last node
  either return a copy or a ref depending on how it's called
*/
function &next_to_last()
{
	// Pointer to 'dummy' head node
	$curr =& $this->head;

	// Iterate through the list BOTTOM->TOP, until reaching TOP-1 node
	while($curr['next']['next'] != NULL)
		$curr = &$curr['next'];

	return $curr;
}


/*
  Update the contents of an existing node
*/
function update($index, &$node)
{
	// Pointer to the node that's being updated
	$curr =& $this->search($index);

	$this->debug("[update]: (index=$index), (pid={$curr['pid']})");

	// Set the pointer correctly in the new node, then
	// replace the current node with the new data
	$node['next'] = $curr['next'];
	$curr = $node;

	return 1;
}


/*
  Return a specific node
*/
function &search($index)
{
	// Pointer to first data node
	$curr =& $this->first();

	$i = 0;
	while ($i++ < ($index-1)) {

		if ($curr == NULL)
			return NULL;

		$curr = &$curr['next'];

	}

	return $curr;
}


/*
  Return an empty node struct to popuate and 'push' or 'unshift' onto the list
*/
function new_node()
{
	return $_node;
}


/*
  Show all items in the list BOTTOM->TOP
*/
function show()
{
	print "\nShowing list (count==". $this->count .")\n";

	// Copy of BOTTOM node
	$curr = $this->first();

	if ($curr == NULL)
		print "\tNOTHING TO SHOW\n";

	while($curr != NULL) {
		print "\tPID=". $curr['pid'];
		print " (next: ". $curr['next']['pid'] .")";
		print " (time: ". $curr['time'] .")";
		print "\n";

		$curr = $curr['next'];
	}

	print "\n";

	return 1;
}


/*
  Print debugging output, if ($this->dbg)
*/
function debug($text)
{
	if ($this->dbg == 1)
		print $text ."\n";

	return 1;
}


} // End  LinkedList class

?>