Die AutoLISP-Funktion member gibt eine Liste beginnend ab dem zuerst gefundenen Ausdruck, der gesucht ist, zurück. Wird der Ausdruck nicht gefunden ist die Rückgabe nil.

(member "C" '("A" "B" "C" "A" "D" "E" "B")) => ("C" "A" "D" "E" "B")

(member "X" '("A" "B" "C" "A" "D" "E" "B")) => nil

Der Rest der Liste wird also zurück gegeben. Was aber, wenn eine Liste vom Anfang bis zum gefundenen Eintrag ausgegeben werden soll? Schreiben wir einfach eine ReverseMember Funktion mittels Rekursion:

(defun ReverseMember (val lst)
   (cond ((or (null lst) (= (car lst) val)) nil)
   ('else (cons (car lst) (ReverseMember val (cdr lst))))
   )
)

Die Funktion wiederholt sich so lange, bis entweder die Liste keinen Eintrag mehr enthält, oder aber der Ausdruck gefunden wird. Dabei legt sie immer das erste Element der Liste auf den Stack und ruft sich wieder selbst auf, übergibt aber dabei die Liste ohne den ersten Eintrag! Das heißt, unsere Liste schrumpft dadurch immer um einen Eintrag. Wenn nun entweder die eine Bedingung <Liste hat keinen Eintrag mehr> oder die andere Bedingung <Eintrag wurde in der Liste gefunden> erfüllt ist, wird der Stack wieder zurückgegeben und zwar in umgekehrter Reihenfolge, also so wie die Liste ursprünglich sortiert war.

(ReverseMember "D" '("A" "B" "C" "A" "D" "E" "B")) => ("A" "B" "C" "A")
(ReverseMember "X" '("A" "B" "C" "A" "D" "E" "B")) => ("A" "B" "C" "A" "D" "E" "B")

Leider gibt aber mehrere Probleme!

Im Gegensatz zur normalen member Funktion ist die Rückgabe stets eine Liste. Wir wollen aber nur dann eine Rückgabe, wenn der zu suchende Ausdruck in der Liste vorhanden ist. Darüber hinaus soll die Funktion die Möglichkeit bieten den zu suchenden Ausdruck inklusive oder exklusive zu betrachten.
Und schließlich: Unter Umständen erzeugt die Funktion einen hübschen Stack-Overflow, wenn sich z.B. bei sehr großen Listen der zu suchende Ausdruck am Ende einer Liste befindet oder erst gar nicht vorhanden ist!

Zusammenfassend:

  • Rückgabe nil, wenn der zu suchende Ausdruck nicht in der Liste vorhanden ist.
  • Der zu suchende Ausdruck soll wahlweise inklusive oder exklusive sein.
  • Keine Rekursion aufgrund eines Stack-Overflows bei großen Listen.

 

So könnte nun die Funktion aussehen:

; Argumente
; #val = der zu suchende Ausdruck
; #lst = die Liste
; #flag = 't für inklusives #val, nil für exklusives #val
; sexy coded by Rolf Wischnewski (www.cadmaro.de)
(defun :L-ReverseMember (#val #lst #flag / RetVal)
   (cond ((member #val #lst)
     (while (/= #val (car #lst))
       (setq RetVal (cons (car #lst) RetVal)
         #lst (cdr #lst)
       )
     )
     (if #flag
       (reverse (cons #val RetVal))
       (reverse RetVal)
     )
   )
  )
)

:L-ReverseMember prüft einmalig mittels der member-Funktion, ob der zu suchende Wert überhaupt in der Liste vorhanden ist. Sobald diese Bedingung als erfüllt gilt, wird die while-Schleife gestartet. Die übergebene Liste wird bei jedem Durchlauf innerhalb der while-Schleife um einen Eintrag kleiner, wogegen die Variable RetVal jeweils um einen Eintrag größer wird. Zum Schluss wird geprüft, ob die Funktion den zu suchenden Eintrag mit der Rückgabe-Liste aufnehmen soll oder nicht.

 

Prüfen wir die neue Funktion...

(:L-ReverseMember "D" '("A" "B" "C" "A" "D" "E" "B") 't) => ("A" "B" "C" "A" "D")
(:L-ReverseMember "D" '("A" "B" "C" "A" "D" "E" "B") nil) => ("A" "B" "C" "A")

(:L-ReverseMember "X" '("A" "B" "C" "A" "D" "E" "B") 't) => nil

Selbst bei sehr großen Listen (> 50000) arbeitet sie noch sehr effizient, auch wenn der zu suchende Ausdruck sich weiter am Ende der Liste befindet (getestet mit einer Listengröße von ca. 55000 Einträgen).

 

Mit freundlicher Genehmigung von Rolf Wischnewski. Originalbeitrag im Februar 2006, CADmaro.de

 

Diese Internetseite ist urheberrechtlich geschützt. Alle Rechte vorbehalten.     © 2024 Markus Hoffmann (─┼──) www.CADmaro.de