## c't-Projekte - Mailinglisten

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

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

Absender: Frank Menzel
Datum: Sa, 25.10.2008 20:24:07
In-reply-to: <D71F512F-D069-4A31-A8E4-269F1756D0E5@xxxxxxxxxxxxxxx>

    Hi Timo,
    ich meinte das reinschieben von vorn eigentlich folgendermaßen.

    Ausgangssituation so, wie von Dir vorgegeben:
    - 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

    Das nächste Verhalten (Pfadplanung) erhält "seinen" Stack ab Position 6.
    Dann wird ab Pos 6 reingeschoben, wieso Du die Werte nun links von x1
    einzeichnest ist mir völlig unklar.

    Also in 3 Schritten zu:
    | -- | -- | -- | x1 | x2 | x3 | y1 | -- | -- | -- |
    | -- | -- | -- | x1 | x2 | x3 | y2 | y1 | -- | -- |
    | -- | -- | -- | x1 | x2 | x3 | y3 | y2 | y1 | -- |

    Der gemerkte Stackwert ist immer noch die 6, diese muss dem
    Folgeverhalten (Stackfahrverhalten) mitgeteilt werden, welches nun via
    Pop bis zum Merker 6 genau die Werte in der Reihenfolge y1 y2 y3
    entnimmt.

    Gruß, Frank

    -----Ursprüngliche Nachricht-----
    Von: ct-bot-entwickler-bounces@xxxxxxxxxxxxxxxxx
    [mailto:ct-bot-entwickler-bounces@xxxxxxxxxxxxxxxxx] Im Auftrag von Timo
    Sandmann
    Gesendet: Samstag, 25. Oktober 2008 19:32
    An: Entwicklung rund um den c't-bot
    Betreff: Re: [ct-bot] area - Stack- Pfadplanung

    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

    _______________________________________________
    ct-bot-entwickler Mailingliste
    ct-bot-entwickler@xxxxxxxxxxxxxxxxx
    http://www.heise.de/bin/newsletter/listinfo/ct-bot-entwickler

- Antworten:
  - Re: [ct-bot] area - Stack- Pfadplanung
    - From: Timo Sandmann

- Referenzen:
  - Re: [ct-bot] area - Stack- Pfadplanung
    - From: Timo Sandmann

- Voriger (Datum): Re: [ct-bot] area - Stack- Pfadplanung, Timo Sandmann
- Nächster (Datum): Re: [ct-bot] area - Stack- Pfadplanung, Timo Sandmann
- Voriger (Thread): Re: [ct-bot] area - Stack- Pfadplanung, Timo Sandmann
- Nächster (Thread): Re: [ct-bot] area - Stack- Pfadplanung, Timo Sandmann
- Indizes:
  - Datum
  - Thread