Lpc Manpages

KONZEPT
        mappings

LETZTE AENDERUNG
        05.10.2004    Nimue        Uebersetzung

AUTOR
        Hyp, 15th Nov, 1993


BESCHREIBUNG
  
  Eine Einfuehrung in Mappings:
  -----------------------------

   1. Was ist ein Mapping?

     Ein  Mapping  ist ein  Datentyp,  bei  dem  Paare aus  Daten  und
   Schluesseln  abgespeichert werden.  In  anderen Programmiersprachen
   bezeichnet man sie auch als 'Dictionaries' oder 'Alists'. LPC kennt
   ebenfalls Alists,  allerdings handelt es sich dabei  nicht um einen
   eigenen  Datentyp,  sondern  um   eine  Struktur,  die  auf  Arrays
   aufsetzt. Alists  sind der Vorlaeufer von  Mappings. Schluessel und
   Werte  koennen  von  jedem  beliebigen Typ  sein.  Die  haeufigsten
   Datentypen fuer Schluessel sind  String, Integer und Object. Andere
   Typen, wie z.B. Arrays, Mappings oder auch Closures sind keine gute
   Wahl,  da  Vergleiche beispielsweise  zwischen  Arrays oft  'false'
   zurueckliefern,  selbst  wenn  beide  Arrays  den  gleichen  Inhalt
   haben.  Das   liegt  daran,  dass  der  Driver   aus  Gruenden  der
   Geschwindigkeit   zwei  Arrays   anhand   ihrer  internen   Pointer
   vergleicht und nicht anhand ihres Inhalts.

     Mappings werden an Funktionen  stets als Referenz uebergeben. Das
   bedeutet:  Wird ein Mapping  an ein  anderes Objekt  uebergeben und
   durch  dieses veraendert,  so findet  diese Aenderung  auf globaler
   Ebene statt und ist fuer  alle Objekte sichtbar, die dieses Mapping
   gerade in einer Variable abgelegt haben.

   2. Wofuer sind Mappings gut?

     Der Ausdruck  'Woerterbuch' beschreibt vielleicht  am besten, wie
   ein  Mapping verwendet  wird. Im  Gegensatz  zu Arrays  gibt es  in
   Mappings keine  bestimmte Reihenfolge. Sie  stellen lediglich einen
   Mechanismus  zur  Verfuegung,   um  einen  Satz  von  Assoziationen
   zwischen  Daten herzustellen.  Solch eine  Assoziation  besteht aus
   einem  eindeutigen  Schluessel  und  den Daten,  die  durch  diesen
   Schluessel  angesprochen  werden.   Hier  liegt  die  Analogie  zum
   Woerterbuch,  in  dem Woerter  und  ihre zugehoerigen  Definitionen
   stehen:  man benutzt  das Wort  als Schluessel,  um  die Definition
   nachzuschlagen.

     Mappings koennen  zum Beispiel benutzt werden, um  ein Alias fuer
   einen  Befehl abzulegen. Der  Schluessel waere  in diesem  Fall der
   Name des Alias,  die Daten der Befehl oder  die Befehle, die diesem
   Alias zugeordnet  sind.  Ein  weiteres Beispiel sind  die Ausgaenge
   eines Raums:  die Schluessel sind  die Richtungen, in die  sich ein
   Spieler bewegen  kann, die  zugehoerigen Daten sind  die Dateinamen
   der  entsprechenden  Zielraeume.  Aber  Mappings  koennen auch  als
   speichersparendere Variante  von Arrays benutzt  werden.  Werden in
   einem  Array   die  meisten   Stellen  nicht  benutzt   (d.h.   die
   zugehoerigen  Elemente  sind 0),  so  wird  unnoetig viel  Speicher
   verbraucht. Will man beispielsweise in einem Array nur die Elemente
   0,  13 und  37642 belegen,  muss  dafuer mindestens  ein Array  der
   Groesse    37642   erzeugt    werden,   mit    dem   entsprechenden
   Speicherverbrauch.  Benutzt  man stattdessen ein  Mapping, kann man
   die Zahlen  0, 13  und 37642 als  Schluessel benutzen,  anstatt als
   Index zu  einer Position im  Array. (Die Schluessel  eines Mappings
   werden oft  als 'Indices' bezeichnet,  weil Daten in  einem Mapping
   aehnlich  wie  in  einem   Array  angesprochen  werden:  durch  den
   []-Operator.)    Dies  erlaubt   es,   alle  besetzten   Positionen
   abzufragen,  indem  man  einfach  alle  Schluessel  eines  Mappings
   abfragt  (im Gegensatz  zu  einem  Array, bei  dem  man ueber  alle
   Elemente iterieren muss).

   3. Wie erzeuge ich ein Mapping? 

     Es gibt verschiedene Moeglichkeiten, ein Mapping zu erzeugen. Die
   bequemste ist die folgende:

      mapping map;
      map = ([ key0: value00; ...; value0n,
               ... : ...    ; ...; ...    ,
               keyn: valuen0; ...; valuenn ]);

     Wie man sieht, kann einem Schluessel mehr als ein Wert zugeordnet
   sein. Allerdings  muss die Anzahl  von Werten pro  Schluessel immer
   gleich sein. Es ist sogar  moeglich, ein Mapping ganz ohne Werte zu
   erzeugen. 

     Eine andere  Moeglichkeit besteht darin, die  Efun mkmapping() zu
   benutzen. Dieser  Efun werden zwei Argumente  uebergeben: ein Array
   von Schluesseln und ein Array von Werten:

      mapping map;
      map = mkmapping (({ key0   , ..., keyn    }),
                       ({ value00, ..., value0n }),
                       ({ ...    , ..., ...     }),
                       ({ valuen0, ..., valuenn }));

     Wird   nur   ein   Array   uebergeben,   so   wird   dieses   als
   Schluessel-Array   interpretiert  und   ein   Mapping  ohne   Werte
   zurueckgegeben. 

     Mit den  oben beschriebenen Methoden laesst sich  auch ein leeres
   Mapping erzeugen, indem man einfach Schluessel und Werte auslaesst: 

      mapping map;
      map = ([]);
   oder:
      map = mkmapping(({}), ({}));

     Eine dritte Methode besteht darin, die Efun allocate_mapping() zu
   benutzen.  Sie   erhaelt  als   erstes  Argument  die   Anzahl  der
   Schluessel,  die spaeter  eingefuegt werden,  sowie  als optionales
   zweites Argument, welches die Breite des Mappings spezifiziert:

      map = allocate_mapping(n, breite);

     Der  Wert <n> mag  etwas verwirrend  sein, da  Mappings dynamisch
   wachsen und schrumpfen. Dieser Wert teilt lediglich dem Driver mit,
   wie 'lang'  das betreffende Mapping  sein wird, damit  die passende
   Menge an Speicherplatz  zugewiesen und unnoetiger Speicherverbrauch
   vermieden wird.   Will man beispielsweise in einer  Datei lesen und
   gelesene Daten als Mapping  ablegen, kennt man vermutlich im Voraus
   die Anzahl  der benoetigten Schluessel.  Also weist man  mit dieser
   Efun  ein Mapping  zu und  teilt dem  Driver mit,  wieviel Speicher
   dafuer bereitgestellt  werden soll, indem man  einen passenden Wert
   fuer <n> angibt.  Auf diese  Weise erreicht man, dass die gelesenen
   Daten  anschliessend schneller  in das  Mapping  eingefuegt werden.
   <breite>  gibt  lediglich an,  wieviele  Werte  pro Schluessel  das
   Mapping haben  wird.  Falls keine  Breite angegeben wird,  wird ein
   Defaultwert von 1 angenommen.

   4. Wie werden Daten in einem Mapping veraendert?

     Das Erzeugen  einens neuen Schluessels  funktioniert aehnlich wie
   Veraenderungen an  Daten, die einem  bereits bestehenden Schluessel
   zugeordnet sind:

      map += ([ key: value0; ...; valuen ]);

     Oder, falls nur ein Schluessel veraendert werden soll:

      map[key, n] = valuen;

     Falls  <n> nicht im  zulaessigen Bereich  liegt oder  <key> nicht
   existiert  und   <n>  groesser  als   0  ist,  wird   ein  "Illegal
   index"-Fehler  ausgegeben.  Ist  <n>  gleich 0  oder  enthaelt  das
   Mapping  nur  einen  Wert  pro Schluessel,  kann  die  Schreibweise
   folgendermassen vereinfacht werden:

      map[key] = value;

     Wenn  <key> nicht  existiert (und  <n>  gleich 0  oder gar  nicht
   spezifiziert   ist),   wird   automatisch  ein   neuer   Schluessel
   hinzugefuegt. Ein Schluessel kann mit  dem -= Operator oder mit der
   Efun m_delete() entfernt werden.   Subtraktion von Mappings ist nur
   moeglich, wenn das zu subtrahierende Mapping keine Werte enthaelt:

      map -= ([ key ]);

     oder:

      map -= ([ key0, ..., keyn ]);

     Die  Efun erhaelt als  erstes Argument  ein Mapping,  als zweites
   einen Schluessel:

      m_delete(map, key);

     Die Efun  m_delete() gibt das  Mapping zurueck, aber  da Mappings
   als  Referenzen   behandelt  werden,  muss   keine  Zuweisung  etwa
   folgender Art erfolgen:

      map = m_delete(map, key);

   5. Wie wird auf die in einem Mapping gespeicherten Daten
      zugegriffen?

     Dies geschieht folgendermassen:

      valuen = map[key, n];

     Oder, im Fall eines Mappings mit nur einem Wert pro Schluessel:

      value0 = map[key];

     Wenn <key>  in dem Mapping nicht  existiert und <n>  0 oder nicht
   spezifiziert ist (was das Gleiche bedeutet), wird 0 zurueckgegeben.
   Ist  <n>  groesser  als  0,  so  wird  ein  "Illegal  index"-Fehler
   ausgegeben. 

   6. Wie  kann  ueberprueft  werden,  ob ein  gegebener  Schluessel
      existiert? 

     Ein  Rueckgabewert  von  0   ist  fuer  die  meisten  Anwendungen
   ausreichend,  jedoch  kann  die mangelnde  Unterscheidung  zwischen
   einem  tatsaechlich  existierenden  Wert  von  0  und  einem  nicht
   existenten Schluessel gelegentlich zu Problemen fuehren. Aus diesem
   Grund  koennen die Efuns  member() oder  mapping_contains() benutzt
   werden, um zu ueberpruefen, ob ein Schluessel tatsaechlich in einem
   Mapping vorhanden ist: 

      if (member(map, key)) {
      ...
      }
     oder:
      if (mapping_contains(&value0, ..., &valuen, map, key)) {
        ...
      }

     Dieses Beispiel  zeigt ausserdem,  wie man alle  einem bestimmten
   Schluessel zugeordneten  Werte in einem Schritt  auslesen kann. Das
   '&' ist  der Referenzoperator, der  benoetigt wird, damit  die Efun
   die Werte in Variablen abspeichern kann.

     Im  Fall  eines Mappings  ohne  Werte  verhalten  sich die  Efuns
   member()  und mapping_contains()  gleich  und werden  auch auf  die
   gleiche   Art    aufgerufen.   mapping_contains()   erhaelt   keine
   Referenzvariablen,   um   die  Werte   darin   zu  speichern   (was
   offensichtlich ist, da es ueberhaupt keine Werte gibt).

     Des  Weiteren liefert member()  normalerweise die  Position eines
   Elements  in  einer  Liste  zurueck  (d.h.  ein  Zeichen  in  einer
   Zeichenkette oder  Daten aus einem  Array). Wird ein  Element nicht
   gefunden,  wird -1  zurueckgegeben. Im  Fall eines  Mappings jedoch
   gibt es  keine Position  oder Reihenfolge, so  dass member()  nur 0
   oder 1 zurueckgibt.

   7. Wie werden Mappings kopiert?

     Ein Mapping wird mit dem  + Operator oder der Efun copy_mapping()
   kopiert: 
      
      newmap = ([]) + map;
     oder:
      newmap = copy_mapping(map);

     Ein Mapping sollte nur kopiert werden, wenn man aus irgendwelchen
   Gruenden  eine  Kopie  benoetigt,  auf die  andere  Objekte  keinen
   Zugriff haben sollen. 

   8. Wie kann man alle Schluessel eines Mappings erhalten? 

     Die Efun m_indices() erhaelt ein Mapping als Argument und liefert
   ein Array mit allen in dem Mapping definierten Schluesseln zurueck:

     keys = m_indices(map);

   9. Wie erhaelt man alle Werte eines Mappings?

     Die Efun m_values() erhaelt  ein Mapping als Argument und liefert
   ein Array zurueck, das alle  ersten Werte des Mappings enthaelt. Es
   ist (noch) nicht  moeglich, mit dieser oder einer  anderen Efun die
   zweite  oder  folgenden 'Spalten'  von  Werten  eines Mappings  als
   Ganzes anzusprechen.

      values0 = m_values(map);
    
   10. Wie kann die Groesse eines Mappings bestimmt werden? 

     Da man  sich ein Mapping  als eine Art Rechteck  vorstellen kann,
   wird  seine  Groesse  durch  zwei  Angaben  definiert:  Laenge  und
   Breite.  Um   diese  Werte   abzufragen,  stehen  zwei   Efuns  zur
   Verfuegung. Die  erste ist  die Efun sizeof(),  die die  Anzahl der
   Schluessel-Wert-Assoziationen zurueckliefert, also die Laenge eines
   Mappings.   Die  zweite  ist  get_type_info(), mit  der  Datentypen
   identifiziert  werden  koennen.  Sie  liefert ein  Array  aus  zwei
   numerischen Werten  zurueck. Der erste bezeichnet  den Datentyp des
   Arguments,  der zweite  ist ein  datentypabhaengiger Wert.  Im Fall
   eines Mappings  ist der  T_MAPPING (definiert in  <lpctypes.h>) und
   der  zweite  die  Anzahl  von  Werten pro  Schluessel  -  also  die
   Spaltenzahl oder die  Breite des Mappings. Genaugenommen entspricht
   die  Breite  des  Mappings  der  Spaltenzahl  plus  Eins  fuer  die
   Schluessel, aber diese Formulierung ist unueblich.

   11. Wie iteriert man am besten ueber ein Mapping? 

     Zuallererst  sollte man  bedenken,  dass ein  Mapping nicht  dazu
   gedacht ist, dass man ueber alle Werte iteriert. Schliesslich haben
   die Schluessel  in einem  Mapping keine feste  Reihenfolge, sondern
   sind    zufaellig    angeordnet    (jedenfalls    von    LPC    aus
   betrachtet).   Trotzdem  ist  es   moeglich,  und   manchmal  sogar
   notwendig. 

     Sollen  alle  Schluessel-Wert-Assoziationen abgearbeitet  werden,
   sollte man walk_mapping() verwenden. Will man alle Schluessel eines
   Mappings abarbeiten,  um ein neues Mapping als  Teilmenge des alten
   zu erzeugen, ist filter_mapping()  das Mittel der Wahl. Sollen alle
   Schluessel abgearbeitet werden, um ein neues Mapping mit den selben
   Schluesseln wie das alte zu erzeugen, benutzt man map_mapping(). Im
   Fall einer  Iteration, die abbrechen kann/sollte,  bevor alle Daten
   bearbeitet  sind,  ist es  wahrscheinlich  klug,  zuerst ueber  das
   Mapping zu  iterieren, um die Schluessel abzufragen,  und dann eine
   zweite  Iteration   ueber  diese   mit  einer  for()-   oder  einer
   while()-Schleife   durchzufuehren,   um   die  Werte   'von   Hand'
   abzufragen. 

     Die Efun walk_mapping() erhaelt  als erstes Argument ein Mapping,
   als  zweites  den Namen  einer  Funktion.  Alle weiteren  Argumente
   werden an  diese Funktion  uebergeben. Anstelle eines  Strings kann
   als  Funktionsname auch  eine  Closure uebergeben  werden. Es  wird
   nichts zurueckgegeben: 

      ...
      walk_mapping(map, "func", xarg0, ..., xargn);
      ...

      void func(mixed key, mixed value0, ..., mixed valuen,
                mixed xarg0, ..., mixed xargn) {
        ...
      }

     func()  wird fuer  alle  Schluessel-Wert-Assoziationen aufgerufen
   und  erhaelt  als erstes  Argument  den  Schluessel. Die  naechsten
   Argumente sind die Werte  hinter dem Schluessel, die als Referenzen
   uebergeben   werden.   Alle  weiteren   Argumente  sind   die,  die
   zusaetzlich uebergeben  wurden. Weil  die Werte als  Referenzen und
   nicht  als  Kopien uebergeben  wurden,  koennen  sie innerhalb  von
   func()  veraendert werden,  indem einfach  den  Variablen <value0>,
   ..., <valuen> neue Werte zugewiesen werden. 

     Die  Efun filter_mapping()  ruft fuer  jeden Schluessel  in einem
   Mapping eine  Funktion auf und  erzeugt ein neues Mapping,  das nur
   die Schluessel-Wert-Assoziationen  enthaelt, fuer die  die Funktion
   'true' (bzw.  nicht 0) zurueckliefert.  Das erste Argument  ist das
   Mapping, ueber  das iteriert werden  soll, das zweite ist  der Name
   der anzuwendenden Funktion als String oder Closure: 

      ...
      submap = filter_mapping(map, "func", xarg0, ..., xargn);
      ...

      int func(mixed key, mixed xarg0, ..., mixed xargn) {
        ...
      }

     func() erhaelt  als erstes Argument den  Schluessel. Eventuell an
   die  Efun uebergebene  zusaetzliche Argumente  werden  ebenfalls an
   func() weitergereicht. 

     Die Efun  map_mapping() erhaelt als erstes  Argument ein Mapping,
   als zweites  einen String (oder  eine Closure) mit dem  namen einer
   Funktion.   Auch   hier   werden   alle  weiteren   Argumente   als
   Zusatzargumente  an die  iterierende Funktion  weitergegeben. Diese
   Efun liefert  ein neues Mapping zurueck, das  die selben Schluessel
   enthaelt  wie  das alte.  Fuer  jeden  dieser  Schluessel wird  die
   genannte  Funktion  aufgerufen,  deren  Rueckgabewert in  das  neue
   Mapping als zugehoerigen Wert eingetragen wird:

      ...
      newmap = map_mapping(map, "func", xarg0, ..., xargn);
      ...

      mixed func(mixed key, mixed xarg0, ..., mixed xargn) {
        ...
      }

     func() erhaelt als erstes  Argument den Schluessel, als moegliche
   weitere   Argumente  diejenigen,  die   zusaetzlich  an   die  Efun
   uebergeben wurden. 

     Da  eine  Funktion nur  einen  einzelnen  Wert zurueckgeben  kann
   (selbst  wenn  es sich  um  ein  Array  handelt), lassen  sich  mit
   map_mapping() nur  Mappings erzeugen, die pro  Schluessel nur einen
   Wert enthalten. 

   12. Ist es  moeglich, Mappings zu vereinigen  oder Schnittmengen zu
       bilden? 

     Vereinigung  von Mappings ist  nur moeglich,  wenn sie  die selbe
   Breite haben, also  die selbe Anzahl von Werten  pro Schluessel. Es
   koennen die Operatoren + und += verwendet werden:

      map = map1 + map2 + ... + mapn;
      map += map1 + map2 + ... + mapn;

     Schnittmengen  von  Mappings  koennen  nur  mit  filter_mapping()
   erzeugt werden. Es gibt keine  Efun und keinen Operator, womit dies
   auf einfache Weise zu erreichen waere. Die 'einfachste' Loesung ist
   vermutlich folgende Funktion:

      mapping intersect_mapping(mapping map1, mapping map2) {
        closure cl;

        cl = lambda(({ 'key }), ({ #'member, map2, 'key }));
        return filter_mapping(map1, cl, map2);
      }

     Diese  Funktion   gibt  ein   Mapping  zurueck,  das   aus  allen
   Schluessel-Wert-Assoziationen  aus <map1> besteht,  fuer die  es in
   <map2> einen Eintrag mit dem gleichen Schluessel gibt. Die Funktion
   verwendet eine  Closure, die 0  oder 1 zurueckgibt, je  nachdem, ob
   ein Schluessel aus <map1> in <map2> enthalten ist oder nicht.

     Um   alle   Schluessel-Wert-Assoziationen   aus   einem   Mapping
   auszuschneiden,  fuer die  ein entsprechender  Schluessel  in einem
   anderen gefunden wurde, kann man die Operatoren - und -= benutzen:

      mapping cut_mapping(mapping map1, mapping map2) {
        return map1 - mkmapping(m_indices(map2));
      }

     Da man von einem Mapping nur eines abziehen kann, das keine Werte
   enthaelt, muss man zuerst ein solches mit Hilfe von m_indices() und
   mkmapping() erzeugen. 

   13. Wozu sind Mappings ohne Werte eigentlich gut? 

     Die  Methode, mit  der der  Driver  in einem  Mapping nach  einem
   Schluessel  sucht, ist  ziemlich schnell.  Deswegen  koennen solche
   Mappings  als Hilfsmittel benutzt  werden, wenn  moeglichst schnell
   getestet  werden soll,  ob ein  bestimmtes Element  in  einer Menge
   enthalten ist.  Diese Technik  wird als 'Hashing'  bezeichnet (eine
   genauere Erklaerung  wuerde an dieser  Stelle zu weit  fuehren) und
   ist viel  schneller, als  ein Array nach  einem bestimmten  Wert zu
   suchen (was linear durchgefuehrt wird). 

     Eine  andere  (vielleicht  etwas praktischere)  Anwendung  dieser
   Mappings  besteht darin,  aus einem  Mapping mit  mehreren gleichen
   Werten eines mit eindeutigen Werten zu erzeugen:

      uniques = m_indices(mkmapping(array));

     mkmapping() benutzt  <array>, um ein Mapping ohne  Werte, nur mit
   Schluesseln, zu erzeugen. Und da Mappings nur eindeutige Schluessel
   enthalten  koennen, werden  alle in  <array>  mehrfach vorkommenden
   Werte zu einem zusammengefasst. m_indices() gibt dann ein Array mit
   diesen eindeutigen  Schluesseln zurueck. Tatsaechlich  werden diese
   Mappings nur temporaer genutzt.

   12. Wie kann man ein Mapping in eine Alist umwandeln und umgekehrt?

     Es gibt keine Efuns, die solche Umwandlungen leisten koennen. Man
   kann folgende Funktion verwenden:

      mapping alist_to_mapping(mixed *alist) {
        return apply(#'mkmapping, alist);
      }

     Die Efun  apply() erhaelt eine  Closure und ein Array  von Werten
   und  gibt jedes  Element des  Arrays  als Argument  an die  Closure
   weiter. Weil  eine Alist ein Arrays  von Arrays ist,  von denen das
   erste  eine Liste  der Schluessel  ist  und die  anderen die  damit
   assoziierten Werte, wird durch ihre Weitergabe als Argumente an die
   Efun-Closure #'mkmapping durch apply()  aus einer Alist ein Mapping
   erzeugt. 

      mixed *mapping_to_alist(mapping map) {
        mixed *alist;
        symbol *vars;
        string var;
        closure cl;
        int width;

        width = get_type_info(map)[1];
        alist = allocate(width + 1);
        vars  = allocate(width + 2);
        for (var = "a"; width; var[0]++, width--) {
          alist[width] = ({});
          vars[width]  = quote(var);
        }
        alist[0] = ({});
        vars[0]  = 'key;
        vars[<1] = 'alist;
        cl = lambda(vars, ({ #'=, 'alist, ({ #'insert_alist }) + vars }));
        walk_mapping(map, cl, &alist);
        return alist;
      }

     Diese Funktion  ist etwas komplizierter als die  andere, und eine
   detaillierte   Beschreibung  wuerde  zu   weit  vom   Thema  dieser
   Einfuehrung   wegfuehren.  Es   gibt  bei   dieser   Funktion  eine
   Einschraenkung: Sie kann nur Mappings  mit bis zu 26 Werten in eine
   Alist umwandeln. Dies sollte allerdings auch fuer alle Anwendungen,
   die Mappings verwenden, ausreichend sein.

     Weiterer Kommentar von Hyp hierzu:
              Die Funktion mapping_to_alist() ist auch ansonsten nicht
              besonders  clever, weil  insert_alist() immer  eine neue
              Alist  erzeugt. Ein  zweites (optionales)  Argument fuer
              m_values(),   das    die   Wertespalte   angibt,   waere
              besser. Abgesehen davon  koennte man eine Umwandlung von
              Mapping nach Alist auch mittels to_array() erreichen.

SIEHE AUCH:

              alists(LPC), closures(LPC), mkmapping(E), walk_mapping(E)