[PHP] OO linked list maken

[Verwijderd]

Ten eerste hoop ik dat jullie de tijd willen nemen deze lap tekst door te nemen

Ik ben laatst bezig gegaan met het opbouwen van een soort CMS. Nu ben ik begonnen met alle user systemen welke ik inmiddels klaar heb.

Nu wilde ik echter wat types aanmaken welke ik graag zou gaan gebruiken aangezien ik deze mis in PHP. (Ik heb ervaring in C++ & Java)

Nu kunnen er een aantal hiervan opgelost worden dmv een array welke vrij universeel zijn in PHP, alhoewel ik de snelheid er nog niet van weet (momenteel nog niet van belang).

Nu ga ik toch even verder met waarom ik dit topic start. Ik ben bezig gegaan met het maken van een linked list ofwel gelinke lijst in het nederlands.

Die term is bij de meesten waarschijnlijk wel bekend maar het gaat er in principe om dat je pointers hebt naar volgende records in de ketting(in een dubbel gevoerde ook vorige).

Ik heb hier echter wat problemen bij, en zie even niet meer waar het aan ligt.... Vandaar dat ik jullie hulp vraag

Ik heb eigenlijk mijn source van Java gekopieerd en wat geknoeid met references maar het resultaat is er nog niet

Hieronder mijn class Element welke een object bij zich houdt en een verwijzing naar het volgende Element.

PHP:

<?
class Element {
        var $_next;
        var $_object;

        function Element() {
                $this->_next = null;
                $this->_object = null;
        }

        function getNext() {
                return $this->_next;
        }

        function setNext(&$next) {
                $this->_next = $next;
        }

        function getObject() {
                return $this->_object;
        }

        function setObject(&$object) {
                $this->_object = $object;
        }

        function isSentinel() {
                return $this->_object == null;
        }
}
?>

Nu de list zelf waar denk ik het probleem zit. (dit is niet het geheel maar wel het belangrijkste stuk van de source denk ik.

PHP:

class LinkedList {
        var $_current;
        var $_first;

        function LinkedList() {
                $this->_first = new Element();
                $this->reset();
        }

        function &get() {
                return $this->_current->getObject();
        }

        function set(&$object) {
                $this->_current->setObject($object);
        }

        function insert(&$object) {
                $insert = new Element();
                $next =& $this->_current->getNext();
                $insert->setNext($next);
                $this->_current->setNext($insert);
                $insert->setObject($object);
                $this->_current = $insert;
        }
}

Ik heb als test even een paar objecten gecreerd en toegevoegd aan de ketting. Vervolgens probeer ik deze in een while lus 1 voor 1 af te drukken.

Hiervan de code:

PHP:

<?
include_once('LinkedList.inc.php');
include_once('Person.inc.php');

$persoon1 = new Person('Henk',21);
$persoon2 = new Person('Piet',86);
$lijst = new LinkedList();
$lijst->insert($persoon1);
$lijst->insert($persoon2);
$lijst->reset();

while($lijst->hasNext()) {
        $pers =& $lijst->get();
        echo '1<br>';
        echo $pers->toString();
        $lijst->next();
}

?>

Ik kom niet eens in de while lus dus ik denk dat het invoegen van records al mis gaat....

Op GoT en verder op internet (google..... allerlei PHP sites) kon ik vrij weinig vinden over linked list dus vandaar dit topic. Ik kwam alleen iets heel interressants tegen over .so files die PHP kan gebruiken en in C kunnen worden geprogrammeerd. Maar ik wilde eerst dit oplossen want waarschijnlijk is dat hij een hoster ook niet mogelijk.

Mocht er nog vraag zijn naar iets dan hoor ik dat graag.

[.oisyn]

Heb even vluchtig je code doorgenomen, de problemen lijken mij voornamelijk te zitten in het gebruik van PHP's references (die eigenlijk totaal niet lijken op references zoals in java of C++). Neem daarbij PHP's brakke expressie systeem en je hebt de poppen aan het dansen. Als je het mij vraagt is OO in PHP een no-go, zelfs in PHP5

Neem even je Element class

PHP:

<? 
class Element { 
        var $_next; 
        var $_object; 

        function Element() { 
                $this->_next = null; 
                $this->_object = null; 
        } 

        function getNext() { 
                return $this->_next; 
        } 

        function setNext(&$next) { 
                $this->_next = $next; 
        } 

        function getObject() { 
                return $this->_object; 
        } 

        function setObject(&$object) { 
                $this->_object = $object; 
        } 

        function isSentinel() { 
                return $this->_object == null; 
        } 
} 
?> 

Ten eerste return je nergens references, waar je dat wel zou moeten doen. Dat doe je door function & bla () te schrijven. In de returnstatement hoef je vervolgens geen & te gebruiken, maar het is wel belangrijk dat je bij de assignment van het resultaat van de functie aan een variabele wel weer een & gebruikt, anders maak je alsnog een kopie.

Daarnaast accepteert je functie setNext bijvoorbeeld wel een reference, maar die kopieer je dan vervolgens weer naar een instance variabele. Bij de assignment naar $this->_next moet je dus ook weer een & gebruiken.

Verder is het ook handig om een & te gebruiken bij een assignment van het resultaat van een new expressie, anders maak je daar ook al een kopie (hoewel dit in je code niet direct fout zal gaan aangezien je nog niets met het object doet in de constructor zelf, maar best practice is dus gewoon $a = &new Bla () schrijven

---

Verder vind ik je implementatie sowieso een beetje raar, afgezien van het feit dat je de methoden reset (), next () en hasNext () niet hebt gedefinieerd (maar waarvan ik de implementatie wel kan raden ). Een linked list zou niet verantwoordelijk moeten zijn voor het aflopen van elementen, dat is een taak van een iterator. Ik zou dus een methode iterate () oid implementeren, die een iterator object retourneert waar je vervolgens je get, set, next, hasNext en reset in implementeert. Op die manier kun je dus 1 lijst meerdere keren tegelijk itereren

[ Voor 13% gewijzigd door .oisyn op 16-06-2004 00:52 ]

[Verwijderd]

Ten eerste bedankt voor je snelle en hulpvolle reply!!! Eentje waar ik wel veel aan heb

Ik ben nu iig bezig met die references, die inderdaad nogal vaag zijn. Ik dacht namelijk ff dat ik ze snapte maar dat blijkt nu weer niet zo te zijn

Vooral het onderste stukje van je reply vind ik heel interessant!!! Ik ga me gelijk eens verdiepen in de manier waarop frameworks van Java en dergelijke het aanpakken (en de iterator klinkt mij bekend in de oren ).

Ik ga iig weer even flink aan de slag....

Mochten er nog mensen zijn met oplossingen van mijn problemen of tips zoals die van Oisyn zijn, dan houd ik me aanbevolen!!!

//kromme zin ff ge-edit

[ Voor 4% gewijzigd door Verwijderd op 16-06-2004 01:16 ]

[Grijze Vos]

Ik vind het vreemd dat je eerst een object aanmaakt, en dan pas in de lijst pleurt. De meeste implementaties die ik heb geleerd op mn opleiding (in Delphi, weliswaar), hadden gewoon een 'toevoeg-functie' die direct op de lijst zelf werktte. Natuurlijk een klein futiel detail, en ik kan me voorstellen dat in de 'C-style wereld' dit anders geimplementeerd wordt, maar ik vond het wel de moeite waard om te melden.

[.oisyn]

Ik snap niet helemaal wat je bedoelt, heb je een (pseudo-)code voorbeeld? Je wilt toch iets toevoegen aan een lijst? Dan moet je toch opgeven wat je wilt toevoegen? Het lijkt me een beetje raar als je een insert () methode hebt die geen parameters verwacht, en zelf een object aan gaat zitten maken. Hoe weet die insert methode dan wat voor object jij erin wilt hebben? En hoe dat object aangemaakt moet worden? En wat als je gewoon een al bestaand object wilt toevoegen?

[ Voor 74% gewijzigd door .oisyn op 16-06-2004 02:11 ]

[Grijze Vos]

De linked lists die wij gebruiktenn maakten gebruik van een vast type. Omwille van de vrijheid van welk type je wilt gebruiken kan ik me voorstellen om deze aanpak te gebruiken, bij nader inzien.

Btw, ik dnek dat in php (4 althans) je het beste gebruik kunt maken van arrays, voor je lists.

[Verwijderd]

Wat betreft die references. Als je het met C++ vergelijkt, dan heb je references en pointers. Bij Java kun je de situatie het beste met C++ pointers vergelijken, terwijl je bij PHP met echte references te maken hebt. Dit zijn een soort aliases voor de compiler, iets heel anders dus dan het adres van het object. Bij Java kun je meerdere kopieen van dat adres in je geheugen hebben, bij PHP kan dat niet.

[ Voor 9% gewijzigd door Verwijderd op 16-06-2004 02:38 ]

[.oisyn]

Ik zou PHP's references absoluut niet met C++ references willen vergelijken. Als je in C++ namelijk een reference (R) hebt naar een variabele (V), heb je dus de reference en de variabele zelf. De reference kun je niet meer ergens anders naar laten wijzen (als het een pointer was geweest wel), en de variabele die je referenced is altijd een value-type variabele. Je kunt V op zijn beurt niet weer ergens anders naartoe laten wijzen; het is immers een value-type. Als V buiten scope gaat, heb je een probleem als je R benadert, het geheugen waar R naar wijst is immers niet meer valide.

In PHP zit het totaal anders. Variabelen zijn altijd references, en wijzen naar een grote interne datastructuur waar alle waarden in staan. Een variabele zelf heeft een naam, en een reference naar een waarde in die interne datastructuur. Een expressie als $a = 5; alloceert een entry in de datastructuur met de waarde 5 (mits $a nog niet bestaat, daar gaan we even vanuit), en maakt een referentie aan met de naam "a" dat wijst naar die entry. Een opvolgende expressie als $b = &$a; maakt een nieuwe referentie aan, maar niet een nieuwe entry in de datastructuur; hij laat de nieuwe referentie wijzen naar dezelfde entry als waar $a naar wijst. $a en $b wijzen dus naar hetzelfde ding, en het is dus niet zo dat $b wijst naar $a, wat in C++ wel het geval is. Bij een value-type assignment naar $a of $b zorgt dat dezelfde entry in de datastructuur wordt aangepast, en zowel $a als $b laten die verandering dus zien. Stel je doet nu $c = 10; en $a = &$c;. Je hebt nu een nieuwe entry met de waarde 10, en 2 referenties, $a en $c, die ernaar wijzen. Het is niet dat omdat $b naar $a wees, $b nu ook ineens naar $c zal wijzen. Je hebt alleen de verwijzing van $a aangepast, $b zal nog altijd naar dezelfde entry wijzen.

Een = zorgt dus voor een aanpassing van de entry waarnaar de variabele wijst, en een =& zorgt voor een aanpassing van de referentie van de variabele. Bovendien, als je na bovenstaande voorbeeld een unset ($c) zou doen, blijft de waarde 10 nog altijd bestaan; er is immers nog een variabele ($a) die er naar wijst. Pas als je die $a ook unset zal de entry worden verwijderd.

.edit: Euh oh ja,

[Verwijderd]

Ik weet niet zeker of ik helemal begrijp wat jij wil (of bedoeld) met een linked list. Maar PHP heeft al array functies als prev() current() en next(), ik neem aan dat je de documentatie van arrays al grondig hebt doorgenomen maar misschien mis ik iets wat jij wil en native dus niet kan... (het is laat).

[Grijze Vos]

Klopt niet helemaal Oisyn.

code:

<?
$a = 5;
$b = &$a;
$c = 10;
$a = &$c;

echo "a: $a\n";
echo "b: $b\n";
echo "c: $c\n";
?>

code:

(greyfox@bierenfriet)~ $php test.php
a: 10
b: 5
c: 10

De referentie naar $a vanuit $b wordt vernietigd als je $a re-assigned.

edit:
Hmz, ik zie dat ik een typo maakte. ik deed $b &= $a, dat is weer net wat anders als $b = &$a. Dat is natuurlijk een logical and, what ik ervan maakte. Even de output veranderen, en de typo...

Mijn reply: wat Oisyn zegt.

[ Voor 49% gewijzigd door Grijze Vos op 16-06-2004 03:56 ]

[PrisonerOfPain]

Verwijderd schreef op 16 juni 2004 @ 03:16:
Ik weet niet zeker of ik helemal begrijp wat jij wil (of bedoeld) met een linked list. Maar PHP heeft al array functies als prev() current() en next(), ik neem aan dat je de documentatie van arrays al grondig hebt doorgenomen maar misschien mis ik iets wat jij wil en native dus niet kan... (het is laat).

Bij array's word de volgorde aan de hand van de indeces bepaald, bij een linked list (gekoppelde lijst) word de volgorde bepaald door de pointers die naar een volgend object linken.

[RedRose]

.oisyn schreef op 16 juni 2004 @ 00:39:
Heb even vluchtig je code doorgenomen, de problemen lijken mij voornamelijk te zitten in het gebruik van PHP's references (die eigenlijk totaal niet lijken op references zoals in java of C++). Neem daarbij PHP's brakke expressie systeem en je hebt de poppen aan het dansen. Als je het mij vraagt is OO in PHP een no-go, zelfs in PHP5

En dat is dus zo jammer in PHP. Ze hebben wat leuke functionaliteit toegevoegd in PHP 5 (datahiding, destructors etc), maar het interne system dat jij in je andere post (overigens uitstekende uitleg) beschrijft, werkt nog precies zo. Terwijl de mensen van Zend dat eerst hadden moeten aanpakken. Een reference in PHP is dan ook meer een symlink en helemaal geen C++-style pointer.

Uiteraard niet helemaal wat je wil, maar je kan ook objecten op een array pushen en poppen en er op die manier over iteraten.

[Verwijderd]

Ik ben nog even verder gaan knoeien en denk dat de problemen bijna getackeld zijn. Ik heb tenminste een idee waar het probleem ligt

Het gaat denk ik mis in de insert methode van mijn LinkedList class.
Even een nieuwe versie van de methode hieronder gepost met wat test echo's.

PHP:

        function insert(&$object) {
                $insert =& new Element();
                $next =& $this->_current->getNext();
                $insert->setNext($next);
                $this->_current->setNext($insert);
                $insert->setObject($object);
                //$this->_current = $insert;
                echo 'Current<br>';
                print_r($this->_current);
                echo '<br>Insert<br>';
                print_r($insert);
                echo '<br>';
        }

Het blijkt dus dat de = parameter in $this->_current = $insert het zaakje verknald. Deze is nu ook commented. Hierdoor komt er een kopie van het object in de instance var terwijl ik er alleen een verwijzing in wil. Met een =& is het helaas ook niet op te lossen.

de print_r's laten overigens het volgende zien.

code:

Current
element Object ( [_next] => element Object ( [_next] => [_object] => person Object ( [_name] => Henk [_age] => 21 ) ) [_object] => ) 

Insert
element Object ( [_next] => [_object] => person Object ( [_name] => Henk [_age] => 21 ) ) 

Current
element Object ( [_next] => element Object ( [_next] => [_object] => person Object ( [_name] => Piet [_age] => 84 ) ) [_object] => person Object ( [_name] => Henk [_age] => 21 ) ) 

Insert
element Object ( [_next] => [_object] => person Object ( [_name] => Piet [_age] => 84 ) )

Hier worden dus achtereenvolgens record 1 en record 2 ge-insert.

Heeft iemand nog een idee waar mijn probleem zich bevind want momenteel zie ik het even totaal niet meer

/me heeft een schopje in de rug nodig denk ik