PHP linked list node swap

[thelordofcheese]

It's been a while since I programmed in PHP and I'm having trouble with the references to nodes.

Basically, I call a function from one class and in that function I am messing with the nodes. I want to swap the 2 nodes, and not just their values. I want the nodes themselves to change the references to the next and previous nodes of each other.

Can anyone help out here?

This is the only function I have left to write.

[Jon-86]

It depends on how your linked list is setup. And if you want to swap a node with the previous or next node (checking for the head or tail of course) But for a one-way linked list. Assumming the node we are swapping is somewhere in the middle and were swapping it with the next node (the node one space closer to the head)

Your algorithm would go.

// Read the list from the tail to he head
// Stop at the node before the one you want to swap
// Read the next noe (the one you want to swap)
//Read the next node (the one you want to swap it with)

//Point the first node towards the third you have read (so it is now in the place of the node you want to swap)
//Point the node you want to swap it with towards the sedon node you read it will now be in the swapped position.
//Finally point the node you want to swap to the node the swapped node was pointing to closing all points on the list

A lot of swapping but if you read that through a few times it should be clear enough!

[BoneIdol]

I don't suppose you could hack around not being able to access the reference location with a sneaky serialize/deserialize to actually get the reference from a variable?

[BoneIdol]

Some quick code to illustrate my point (I'm not good with refferences).

<?php
	$text1 = 'rawr';
	$text2 = 'blah';
	$foo =& $text1;
	$bar =& $text2;
	echo "$foo $bar \n";
	$temp1 = serialize( $foo );
	$temp2 = serialize( $bar );
	$foo = unserialize( $temp2 );
	$bar = unserialize( $temp1 );
	echo "$foo $bar \n";
	$text1 = 'test1';
	echo "$foo $bar \n";
?>

This code will swap the refferences rather than swapping the values.

[BoneIdol]

No wait, hang on. It doesn't work, I forgot to put unsets in to break the references. Turns out serialize only serializes circular references inside an array or object (and even then only if you serialize the whole object/array). Arses.

[Jon-86]

It would be easier to just track list position with an int value for each record and then using array_pop() and array_push() since you dont really have pointers in the true sense with PHP

[thelordofcheese]

class Node {
private $prev;
private $next;
private $value;
private $row;

function Node($value = null, $row = null){
$this->value = &$value;
$this->row = &$row;
}

function setPrev($node){
$this->prev = &$node;
}
function setNext($node){
$this->next = &$node;
}

function &getPrev(){
return $this->prev;
}
function &getNext(){
return $this->next;
}

...
}

class NodeList {
private $first;//head
private $last;//tail
private $size;

function NodeList(){
$this->first = new Node();
$this->last = new Node();
$this->size = 0;
}

function addNode($value,$row){
//this works fine
...
}

function swap($nodeA, $nodeB){
???
}
}

[BoneIdol]

At 7/23/08 11:16 AM, Jon-86 wrote: It would be easier to just track list position with an int value for each record and then using array_pop() and array_push() since you dont really have pointers in the true sense with PHP

Agreed. Although I would rather use next(), last() and current() rather than array_pop, as popping an array is treating it as a stack.

[Jon-86]

At 7/23/08 11:37 AM, BoneIdol wrote: next(), last() and current()

I didnt know about thoes functions. Cheers

[BoneIdol]

Sorry to bring this topic back from the dead, but my head's working a lot better today.

Rather than using a full on linked list, would it not be easier to make your class implement PHP's iterator interface?

http://www.phpbuilder.com/manual/en/lang uage.oop5.iterations.php

The main upside to doing this is that your class will be much more friendly with foreach statements.

[thelordofcheese]

At 7/24/08 06:28 AM, BoneIdol wrote: Sorry to bring this topic back from the dead, but my head's working a lot better today.

Rather than using a full on linked list, would it not be easier to make your class implement PHP's iterator interface?

http://www.phpbuilder.com/manual/en/lang uage.oop5.iterations.php

The main upside to doing this is that your class will be much more friendly with foreach statements.

No, not dead. I just had to work.

As for the iterator, I should have read the release notes for 5, but when you really only want access to one thing, and protect the rest, it seems that's not the way to go.

Hmmm...
I guess I was thinking too much like C.
Seems the references don't really act like pointers.
But they would if I used shared memory.

Well, I'll just swap values down for now, but damn that raises the Big O.

[BoneIdol]

At 7/25/08 07:58 AM, thelordofcheese wrote: As for the iterator, I should have read the release notes for 5, but when you really only want access to one thing, and protect the rest, it seems that's not the way to go.

Ok, I'll admit my brain isn't working at 100% today either (the curse of a lengthy pub lunch; it's probably closer to 30%) but I would have thought you could implement the iterator class in your code without too much difficulty. Ok it'll break your get/set/do coding style but it'll make your class much more friendly with foreach statements and more portable.

Given that PHP's default behaviour is to loop through each and every public element, I think it would be worthwhile to implement it. Even if its just to return false when people try and pass it to a foreach.

Seems the references don't really act like pointers.

I thought they didn't in C either. I'm not a C/C++ expert though.

Well, I'll just swap values down for now, but damn that raises the Big O.

One of the annoying things about programming is that there sometimes isn't an eloquent or ideal solution in your chosen language (occasionally in any language). Peoople discourage hacks/kludges but sometimes they are a necessary evil.