## c't-Projekte - Mailinglisten

[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

### Re: [ct-bot] area - Stack- Pfadplanung

Absender: Timo Sandmann
Datum: Sa, 25.10.2008 19:32:07
In-reply-to: <000001c936bf$f27ad740$0200a8c0@mexpnew>
References: <000001c936bf$f27ad740$0200a8c0@mexpnew>

    Hi Frank,

    Am 25.10.2008 um 18:37 schrieb Frank Menzel:

>     Hi Timo,

> `wenn ich das richtig verstanden habe, wird einfach der Indexwert` `geholt`

>     und gemerkt, ab dem der neue Stack sozusagen losgeht. Dann kommen die
>     diversen Push's und irgendwann auch die Pop's und wenn der gemerkte
>     Indexwert erreicht wird, ist dieser Stack sozusagen leer.

    ganz genau.

>     Das sollte doch mit dem Fifo genauso klappen. Ich hole zuerst den
>     Indexwert und packe mit Push (bzw. _queue) die Daten hinten drauf. Bei
>     dequeue müsste doch immer der Wert des Arrays an der Stelle des
>     gemerkten Indexwertes zurückgegeben werden, bis der eigentliche
>     Arrayzähler diesen Indexwert unterschreitet. Oder habe ich einen
>     Denkfehler ?

`Ich mache mal ein einfaches Beispiel, um das Problem zu verdeutlichen` `(hoffentlich ist die ASCII-Art auch bei anderen eMail-Clients noch` `korrekt... ich schreibe die Indizes der Pointer besser mit dazu):`

`- Anfangssituation (keine Daten gespeichert): sp (Stackpointer /` `Index) = 3; fp (FIFO-Pointer / Index) = 3; count = 0` `- Jetzt kommen 3 pushs, die die Daten x1, x2, x3 ablegen, dann sieht` `es im Array (hat hier jetzt mal 10 Plätze von 0 bis 9) so aus ( --` `bedeutet keine Daten):`

    | -- | -- | -- | x1 | x2 | x3 | -- | -- | -- | -- |
                       ^                    ^
                       fp = 3           sp = 6              count = 3

`- Nun will ein Verhalten den Speicher als FIFO für 3 Einträge nutzen,` `es sollen also 3 weitere Einträge (y1, y2, y3) an Position 6, 7 und 8` `abgelegt werden. Um seinen eigenen Anfang später zu finden, kann sich` `das Verhalten jetzt sp_alt = 6 merken und es macht 3 pushs, das Array` `sieht nun wie folgt aus:`

    | -- | -- | -- | x1 | x2 | x3 | y1 | y2 | y3 | -- |
                       ^                    ^                    ^

`fp = 3 sp_alt=6 sp = 9` `count = 6`

`- Jetzt will das Verhalten seine 3 abgelegten Datensätze (y1, y2, y3)` `wieder haben, ruft also dequeue() auf mit Parameter fp = 6 (gemerkter` `Index sp_alt). Aber was macht der pos_store-Code nun? Zurückgegeben` `werden muss y1, an Index 6 ist anschließend eine Lücke und count` `müsste 5 werden. Wir können aber weder fp updaten (x1 ist ja immer` `noch gespeichert und wird vielleicht noch gebraucht) noch sp updaten.` `Es sieht also erstmal so aus:`

    | -- | -- | -- | x1 | x2 | x3 | -- | y2 | y3 | -- |
                       ^                    ^                   ^

`fp = 3 sp_alt=6 sp = 9` `count = 5`

`Möglich wäre, jetzt x1, x2 und x3 eins nach rechts schieben und fp auf` `4 setzen.` `ABER: Erstens müsste das nächste dequeue() nun y2 liefern, der` `übergebene Parameter müsste also auf Index 7 zeigen, d.h. sp_alt (vom` `Verhalten gespeichert) müsste beim letzten dequeue() um eins erhöht` `worden sein. Das Kopieren der Daten und ändern von sp_alt, obwohl es` `dem Verhalten gehört, ist irgendwie sehr unschön. Das viel größere` `Problem ist aber, dass dadurch die Daten x1, x2 und x3 verschoben` `wurden. Wenn sich nun ein anderes Verhalten ebenfalls irgendwann mal` `einen Index gemerkt hat (z.B. "sp_uralt"), ist der nun nicht mehr` `gültig und dieses Verhalten käme nie mehr an seine Daten.` `Was bei einem Stack ganz einfach ist, weil nie Lücken entstehen` `können, funktioniert bei FIFO also so nicht mehr.`

>     Andererseits könnte man bei dem Beispiel der Pfadplanung
>     und dem danach gestarteten Stackfahrverhalten die Sache umdrehen. Also
>     nicht mittels Fifo rausholen und hinten reinschieben, sondern vorn
>     reinschieben und hinten einfach rausholen, also das Stackfahrverhalten
>     ganz normal ohne fifo-Entnahme starten. Also entnehmen mittels
>     pos_store_pop_until.

`Wenn ich dich richtig verstehe, wären dann im obigen Beispiel y1, y2` `und y3 links von x1, also an Index 2,1 und 0:`

    | y3 | y2 | y1 | x1 | x2 | x3 | -- | -- | -- | -- |
      ^                    ^                    ^
      fp = 0            fp_alt=3       sp = 6             count = 6

`Wie willst du jetzt an y1 kommen, was als erstes wieder benötigt` `wird? Ein pop_from(fp_alt = 3) würde zwar y1 liefern, erzeugt aber` `wieder eine Lücke mit denselben Problem wie oben beschrieben.`

>     Müßte nicht eigentlich auch ein pos_store_clear_until her ?

`Ist nach Stack-Semantik möglich (^= pop_until und Daten verwerfen),` `nach FIFO aber nicht (s.o.)`

>     Und um noch mal beim Beispiel der Pfadplanung zu bleiben, müsste man
>     auch den gemerkten Indexwert aus der Pfadplanung, also dem Wert ab dem
>     die abzufahrenden Punkte losgehen, dem folgenden Stackfahrverhalten
>     übermitteln können. Denn für diese beiden Verhalten ist ja der Stack
>     identisch.

> `Wird irgendwie doch alles komplexer als gedacht. Erst mal danke` `soweit.`

`Ich denke es wird zu komplex, insbesondere wenn es in beliebigen` `Kombinationen funktionieren soll. Und alles andere wäre eigentlich` `unschön, weil der Positionsspeicher ja allgemein sein und nicht nur` `für eine bestimme Verhaltenskombination korrekte Ergebnisse liefern` `soll.` `Am besten wäre wohl, wenn es mehrere Instanzen des Positionsspeichers` `geben kann, so dass jedes Verhalten auch einen Neuen erzeugen kann.` `Dann sagt Verhalten A, dass es einen Positionsspeicher braucht und` `dieser ist dann auf jeden Fall erstmal leer. Bei Bedarf kann Verhalten` `den Speicher mit Verhalten B gemeinsam nutzen (irgendwer muss dann nur` `wieder aufräumen), ein Verhalten C, das für sich selbst (oder für sich` `und Verhalten D) einen solchen Speicher braucht, fordert dann einen` `Weiteren an und kommt sich nie mit A und B in die Quere. Das wäre dann` `mehr in Richtung eines objektorientierten Ansatzes.`

    Grüße,
    Timo

- Antworten:
  - AW: [ct-bot] area - Stack- Pfadplanung
    - From: Frank Menzel

- Referenzen:
  - AW: [ct-bot] area - Stack- Pfadplanung
    - From: Frank Menzel

- Voriger (Datum): AW: [ct-bot] area - Stack- Pfadplanung, Frank Menzel
- Nächster (Datum): AW: [ct-bot] area - Stack- Pfadplanung, Frank Menzel
- Voriger (Thread): AW: [ct-bot] area - Stack- Pfadplanung, Frank Menzel
- Nächster (Thread): AW: [ct-bot] area - Stack- Pfadplanung, Frank Menzel
- Indizes:
  - Datum
  - Thread