doc/LPC/mappings - mudlib-public - Gitiles

 CONCEPT
         mappings

 LAST UPDATE
         Mon, 15 Mar 1999

 DESCRIPTION

   A step-by-step introduction to mappings:
   ----------------------------------------

   1. What is a mapping?

     A mapping is a datatype which allows to store data associated to a key.
   In other languages  they are also  known  as 'dictionaries' or  'alists'.
   There are also alists in LPC but they are not a separate datatype but are
   implemented on  top of arrays.  Alists are  the predecessors of mappings.
   The keys and the values  can be of  any type.  But most common  datatypes
   for keys are strings, integers and objects.  Others like arrays, mappings
   or closures aren't a good choice because comparision between i.e.  arrays
   often returns false  even if they equal  in content.  This is because the
   driver compares i.e. two arrays by their internal pointers and not by
   their content. The reason for this is simple: speed.

     Mappings  are allways  treated  as references    when passing  them  to
   functions. This means when you pass a mapping  to another object and this
   object modifies the mapping the modification will  take place in a global
   scope - visible to all objects holding this mapping in a variable.


   2. What are mappings good for?

     The term 'dictionary'  probably describes the  use  of a mapping  best.
   Opposed  to arrays mappings don't have  a specific  order. They provide a
   mechanism to   create  a set  of associations  between  values.  Such  an
   association consists of a unique  key and data  that is identified by the
   key. Think of  a dictionary  where you have  a  word and a definition  of
   it. You use the word to lookup its definition.

     Mappings can be used i.e.  to hold  aliases for commands. The key would
   then be the  name of  the alias and  the  data the command(s) behind   an
   alias.  Or they can be used for  the exits of a  room.  The keys would be
   the directions where one can go  to and the associated  data would be the
   file names of the  rooms.  But mappings can  also be used  as a kind of a
   sparse array.   A  sparse array is  an  array where most of  the elements
   aren't used  (occupied by 0).  I.e.  if  you want to  store values at the
   position 0, 13  and 37642 of an  array you would  have to create an array
   with a size of at least 37643.  This  costs a lot  of memory so a mapping
   would be  more useful because you would  then use the  numbers 0,  13 and
   37642 as a key and not as an index to a position  (actually the keys of a
   mapping are sometimes  called indices  but this  is just  because the way
   data is accessed in a mapping is similar to  arrays: by the [] operator).
   This also allows to  query all occupied   positions of a sparse array  by
   querying for all  the keys of  the mapping opposed  to an array where you
   have to iterate over all elements.


   3. How do I create a mapping?

     There are several ways to do so. The most convenient is the following:

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

     As you can see, a key may  have more than  one value assigned.  But the
   amount of values per key must always be equal.  It  is  even  possible to
   have mappings without any values!
     Another  method is  to use the   efun mkmapping().  This  efun gets two
   arguments with the first beeing an array of keys and the following beeing
   arrays of values:

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

     If the efun only gets one argument, then this argument will be taken as
   an array of keys and a mapping  without values will  be returned.

     An empty mapping can be created by using the above described methods by
   simply ommitting the keys and values:

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

     Or  by  using the efun   m_allocate().  This efun gets  as  first
   argument the  amount  of keys which will  be  added soon and  an optional
   second argument specifying the width of the mapping:

       map = m_allocate(n, width);

     The value <n>  may be a bit  confusing  since mappings shrink and  grow
   dynamically. This value just tells the driver how 'long' this  mapping is
   going to be  so proper memory  allocations  will be  performed to  reduce
   the overhead of memory reallocation.  I.e.  if you want to read in a file
   and store the  read data in  a mapping  you probably  know  the amount of
   keys.  So you allocate  a mapping with this  efun and tell the driver how
   much memory should  be allocated  by specifing  a proper <n>  value.
   Thus causing  a    speedup when adding  the  read   data to the   mapping
   afterwards.    The <width> just specifies how   many  values per key this
   mapping is   going to have. If  no  width is given, 1  will  be  taken as
   default.

   An empty mapping created with '([])' will always have a width of 1. To
   create empty mappings with other widths, write it as

       map = ([:width ]);

   <width> can be any expression returning an integer value (including
   function calls), and in fact this notation is just a fancy way of
   writing

       map = m_allocate(0, width);


   4. How can I modify the data of a mapping?

     Adding a  new key is similiar to   modifying the associated  data of an
   existing key:

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

     Or in case only a single value should be modified:

       map[key, n] = valuen;

     If  <n> is out of  range or if <key> doesn't  exists and <n> is greater
   than 0 an "Illegal index" error will be reported. If <n> is equal to 0 or
   the mapping only has a single value per key one can abbreviate it with:

       map[key] = value;

     If there is no <key> (and <n> is equal to 0 or  not specified at all) a
   new one will be added automatically.

     Deletion   of a key    is  done with    the  -=  operator or  the  efun
   m_delete(). A mapping can only be substracted by one without any values:

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

   The efun takes a mapping as first and a key as second argument:

       m_delete(map, key);

     The  efun   m_delete() returns  the mapping   but because  mappings are
   handled as references there is no need of an assignment like:

       map = m_delete(map, key);


   5. How can I access the data stored in a mapping?

     This can be done by:

       valuen = map[key, n];

     Or in case of a mapping with just one value per key:

       value0 = map[key];

     If there is no  <key> in the mapping  and <n> is  0 or not specified at
   all (which is the same) a 0 will be returned or if <n>  is greater than 0
   an "Illegal index" error will be reported.


   6. How can I test for the existance of a key?

     A  return value of 0 is  sufficient for most applications but sometimes
   the ambiguity  between an existing value of  0 and  a nonexisting key can
   lead   to  a  problem.  Therefore   one  can use   the  efun member()  or
   mapping_contains() to check if there actually is a key in the mapping:

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

     This also shows how  one can retrieve all values   associated to a  key
   from a mapping in a single step. The '&' is  the reference operator which
   is neccesary to let the efun store the values in the variables.

     In case   of  mappings   with   no  values,   the  efun   member()  and
   mapping_contains() are equal in their behaviour  and their way of calling
   because mapping_contains() won't get any reference variables to store the
   values in (obviously, because there aren't any).

      Also normally member() is known to return the postion of an element in
   a list (i.e.  a  character in a  string or data   in an array) and if  an
   element couldn't be  found -1 is returned.   But in the case  of mappings
   there are no such things as order and postion. So member() only returns 0
   or 1.


   7. How can I copy a mapping?

     A  mapping can  be  copied   with  the  +  operator   or by the    efun
   copy_mapping():

       newmap = ([]) + map;
   or:
       newmap = copy_mapping(map);

     A mapping should only be copied when it is neccesary to get an own copy
   of it that  must not be  shared by other objects.


   8. How can I get all keys of a mapping?

     The  efun m_indices() gets a mapping  as argument  and returns an array
   holding all keys defined in this mapping:

       keys = m_indices(map);


   9. How can I get all the values of a mapping?

     The efun m_values() gets  a mapping as  argument  and returns  an array
   holding all the first (second, ...) values of it.

       values0 = m_values(map);     returns the first values
       values0 = m_values(map, 0);  dito
       values1 = m_values(map, 1);  returns the second values
         etc


   10. How can I determine the size of a mapping?

     Because a mapping is a kind of rectangle it has two sizes: a length and
   a width.  There are three different efuns  to query these values. The first
   two are the  efuns sizeof(), which returns the  amount of key-value
   associations (the length of  a mapping), and widthof(), which returns the
   number of values per key (the width). The third is the efun get_type_info().
   get_type_info() is meant  to be a function  to identify a datatype.   Its
   return value is an  array of two  numerical values.  The first  specifies
   the datatype   of the argument and   the second is a   datatype dependend
   value. In the case of a mapping the first value  is T_MAPPING (which is a
   value defined in  <lpctypes.h>) and the  second the amount of values  per
   key (a.k.a.  columns or the width  of the mapping  - actually it would be
   correct to say that the width of a mapping is the  amount of columns plus
   one for the keys but this is uncommon).


   11. What is the best method to iterate over a mapping?

     First of all the main purpose of a mapping is not meant to  be a set of
   data to iterate over. Afterall the keys in a mapping have no specific but
   a random order (at least on the LPC side).  But  still it is possible and
   sometimes even neccesary to do so.

     If all key-value associations  should be processed  then one should use
   walk_mapping().  If all keys of a mapping should be processed to create a
   new mapping being a subset of the given one, then filter_mapping() should
   be  used.  If all  keys  are going to  be  processed and  to create a new
   mapping with the  same set of keys as  the given mapping, then one  would
   use map_mapping().  But in the case of an  iteration that should/can stop
   even if not all data is processed it is probably wise to iterate over the
   mapping by first querying for the keys and then to iterate over them with
   a for() or a while() loop and querying the values by 'hand'.

     The efun walk_mapping() gets  a mapping as  first argument and the name
   of a function  as second one. All the  following arguments are treated as
   extras which  will  be  passed to the   function specified  with the  2nd
   argument. Instead of a string for the name of a function a closure can be
   used, too. Nothing will be returned:

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

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

     func() will be called for all key-value associations  and gets as first
   argument the key.  The next arguments are the  values behind the key  and
   are passed as references.  The  rest  of the  passed arguments are  those
   specified as extras. Because the values are passed as references (opposed
   to  copies) it is possible  to modify them  from  inside func() by simply
   assigning new value to the variables <value0>, ..., <valuen>.

     The efun filter_mapping() calls  a function for  each key in  a mapping
   and creates a new mapping  which only contains key-value associations for
   which the called function returned true (not  equal 0 that is). The first
   argument is the mapping to iterate over and the second is a function name
   given as a string or a closure:

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

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

     func() gets  as first argument the key  and the others are those passed
   as extras to filter_mapping().

     The efun map_mapping() gets a mapping as first argument and a string as
   a function name (or again a closure) as  second argument.  Any additional
   arguments are again used  as extras that will  be passed to the iteration
   function. This efun returns a new mapping with the same keys as the given
   one.  The values  returned by the function  that is invoked  for each key
   will be used as the associated data behind each key of the new mapping:

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

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

     func() gets  as first argument the key  and the others are those passed
   as extras to map_mapping().

     Because a function can only return  a single value  (even when it is an
   array) it restricts the use  of map_mapping() to  only allow creation  of
   mappings with a single value per key.


   12. Is it possible to join/intersect/cut mappings with another?

     Joining mappings is only possible, if  they have the same width (amount
   of values per key). One can use the + and += operator:

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

     Intersection     of   two   mappings is    only      possible by  using
   filter_mapping(). There is  no efun or operator  which features this. The
   'easiest' way may be the following function:

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

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

     This function returns a  new mapping which   consists of all  key-value
   associations   of  <map1>  for which  an  equal  key  could   be found in
   <map2>. This function uses  a closure which returns 0  or 1  depending on
   wether a key from <map1> is contained in <map2> or not.

     Cutting out  all key-value associations of a   mapping for which  a key
   could be  found in another mapping  can  be done  by using  the  - and -=
   operator:

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

     Because a maping can  only be substracted by one  without any values we
   first have to create such by using m_indices() and mkmapping().


   13. What are those mappings without any values (besides keys) good for?

     Because the way how the driver  searches for a  key in a mapping is
   rather fast, those mappings can be used as a  set of elements with a fast
   method for testing if an element is  contained in the set. This technique
   is called hashing (further  explanation   would lead  too far)  which  is
   faster  than searching for  values  in array  (which  is done in a linear
   fashion).

     Another (maybe  more pratical) use  of these  mappings  are to create a
   array of unique values out of an array with several equal values:

       uniques = m_indices(mkmapping(array));

     mkmapping() uses  <array> to  create  a mapping without any  values but
   just keys. And  because a mapping can only  have unique keys all multiple
   values in <array> are taken as one.  The call of m_indices() then returns
   an  array  of  these  unique keys.  Actually we  only  make  use of those
   mappings temporarily.


   14. How can I convert an alist into a  mapping and vice versa?

     There are no special efuns which handle such conversions. But it can be
   done by the following functions:

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

     The efun apply() takes a closure and an array of values and passes each
   element of the  array as an  argument  to the  closure. Because  an alist
   consists of an array of arrays with the first beeing the list of keys and
   the others the values associated to each key passing them as arguments to
   the efun closure #'mkmapping via apply() causes the creation of a mapping
   out of an alist.

       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;
       }

     This function is  a bit more  complicated  than the other  and detailed
   description would lead   too far of   the topic.  This  function has  one
   restriction:  it can only turn a  mappings with up to  26  values per key
   into an  alist.    But  this  should  be   sufficient for probably    all
   applications which use mappings.

   And Hyps further comment on this:
         The function mapping_to_alist() is also not that
         clever because insert_alist() allways creates a new
         alist.  A second (optional) argument to m_values() to
         specify the value column would be better. Besides
         this, the conversion of a mapping into an alist could
         be done by to_array().

   15. Dirty Mappings

   'Dirty mappings' are nothing the LPC programmer directly is involved
   with, however, as it relates to the way mappings are implemented
   internally by the gamedriver. However, as this term shows up in
   various driver statistics, it is explained here.

   There are two fundamental approaches to implement mappings:

     1. Store all data entries in an array-like structure, in sorted order.
     2. Store all data in a hashtable, each entry allocaed separately.

   Method 1 is very space efficient, as it doesn't need much overhead
   per entry; however, insertions and deletions of entries are
   relatively slow as all other entries need to be moved.
   Method 2 is very fast as nothing needs to be moved in memory,
   however it has a large overhead.

   The gamedriver uses a hybrid method: at the basis is a mapping
   implementation based on arrays. However the driver uses a hash table
   in addition to handle all the ongoing insertions and deletions.
   Every once in a while, the contents of the hash table are sorted
   into the base array, reasoning that any entry surviving for longer
   time in the hash table is worth keeping in a more space-efficient
   manner. 'Dirty' mappings are such mappings with both an array and a
   hash part, 'clean' mappings are those with just an array part.

 HISTORY
         The ([:width ]) notation was added in LDMud 3.2.9/3.3.208 .

 SEE ALSO
         alists(LPC), closures(LPC), structs(LPC), mkmapping(E),
         walk_mapping(E)
	CONCEPT
	mappings

	LAST UPDATE
	Mon, 15 Mar 1999

	DESCRIPTION

	A step-by-step introduction to mappings:
	----------------------------------------

	1. What is a mapping?

	A mapping is a datatype which allows to store data associated to a key.
	In other languages they are also known as 'dictionaries' or 'alists'.
	There are also alists in LPC but they are not a separate datatype but are
	implemented on top of arrays. Alists are the predecessors of mappings.
	The keys and the values can be of any type. But most common datatypes
	for keys are strings, integers and objects. Others like arrays, mappings
	or closures aren't a good choice because comparision between i.e. arrays
	often returns false even if they equal in content. This is because the
	driver compares i.e. two arrays by their internal pointers and not by
	their content. The reason for this is simple: speed.

	Mappings are allways treated as references when passing them to
	functions. This means when you pass a mapping to another object and this
	object modifies the mapping the modification will take place in a global
	scope - visible to all objects holding this mapping in a variable.


	2. What are mappings good for?

	The term 'dictionary' probably describes the use of a mapping best.
	Opposed to arrays mappings don't have a specific order. They provide a
	mechanism to create a set of associations between values. Such an
	association consists of a unique key and data that is identified by the
	key. Think of a dictionary where you have a word and a definition of
	it. You use the word to lookup its definition.

	Mappings can be used i.e. to hold aliases for commands. The key would
	then be the name of the alias and the data the command(s) behind an
	alias. Or they can be used for the exits of a room. The keys would be
	the directions where one can go to and the associated data would be the
	file names of the rooms. But mappings can also be used as a kind of a
	sparse array. A sparse array is an array where most of the elements
	aren't used (occupied by 0). I.e. if you want to store values at the
	position 0, 13 and 37642 of an array you would have to create an array
	with a size of at least 37643. This costs a lot of memory so a mapping
	would be more useful because you would then use the numbers 0, 13 and
	37642 as a key and not as an index to a position (actually the keys of a
	mapping are sometimes called indices but this is just because the way
	data is accessed in a mapping is similar to arrays: by the [] operator).
	This also allows to query all occupied positions of a sparse array by
	querying for all the keys of the mapping opposed to an array where you
	have to iterate over all elements.


	3. How do I create a mapping?

	There are several ways to do so. The most convenient is the following:

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

	As you can see, a key may have more than one value assigned. But the
	amount of values per key must always be equal. It is even possible to
	have mappings without any values!
	Another method is to use the efun mkmapping(). This efun gets two
	arguments with the first beeing an array of keys and the following beeing
	arrays of values:

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

	If the efun only gets one argument, then this argument will be taken as
	an array of keys and a mapping without values will be returned.

	An empty mapping can be created by using the above described methods by
	simply ommitting the keys and values:

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

	Or by using the efun m_allocate(). This efun gets as first
	argument the amount of keys which will be added soon and an optional
	second argument specifying the width of the mapping:

	map = m_allocate(n, width);

	The value <n> may be a bit confusing since mappings shrink and grow
	dynamically. This value just tells the driver how 'long' this mapping is
	going to be so proper memory allocations will be performed to reduce
	the overhead of memory reallocation. I.e. if you want to read in a file
	and store the read data in a mapping you probably know the amount of
	keys. So you allocate a mapping with this efun and tell the driver how
	much memory should be allocated by specifing a proper <n> value.
	Thus causing a speedup when adding the read data to the mapping
	afterwards. The <width> just specifies how many values per key this
	mapping is going to have. If no width is given, 1 will be taken as
	default.

	An empty mapping created with '([])' will always have a width of 1. To
	create empty mappings with other widths, write it as

	map = ([:width ]);

	<width> can be any expression returning an integer value (including
	function calls), and in fact this notation is just a fancy way of
	writing

	map = m_allocate(0, width);



	4. How can I modify the data of a mapping?

	Adding a new key is similiar to modifying the associated data of an
	existing key:

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

	Or in case only a single value should be modified:

	map[key, n] = valuen;

	If <n> is out of range or if <key> doesn't exists and <n> is greater
	than 0 an "Illegal index" error will be reported. If <n> is equal to 0 or
	the mapping only has a single value per key one can abbreviate it with:

	map[key] = value;

	If there is no <key> (and <n> is equal to 0 or not specified at all) a
	new one will be added automatically.

	Deletion of a key is done with the -= operator or the efun
	m_delete(). A mapping can only be substracted by one without any values:

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

	The efun takes a mapping as first and a key as second argument:

	m_delete(map, key);

	The efun m_delete() returns the mapping but because mappings are
	handled as references there is no need of an assignment like:

	map = m_delete(map, key);


	5. How can I access the data stored in a mapping?

	This can be done by:

	valuen = map[key, n];

	Or in case of a mapping with just one value per key:

	value0 = map[key];

	If there is no <key> in the mapping and <n> is 0 or not specified at
	all (which is the same) a 0 will be returned or if <n> is greater than 0
	an "Illegal index" error will be reported.


	6. How can I test for the existance of a key?

	A return value of 0 is sufficient for most applications but sometimes
	the ambiguity between an existing value of 0 and a nonexisting key can
	lead to a problem. Therefore one can use the efun member() or
	mapping_contains() to check if there actually is a key in the mapping:

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

	This also shows how one can retrieve all values associated to a key
	from a mapping in a single step. The '&' is the reference operator which
	is neccesary to let the efun store the values in the variables.

	In case of mappings with no values, the efun member() and
	mapping_contains() are equal in their behaviour and their way of calling
	because mapping_contains() won't get any reference variables to store the
	values in (obviously, because there aren't any).

	Also normally member() is known to return the postion of an element in
	a list (i.e. a character in a string or data in an array) and if an
	element couldn't be found -1 is returned. But in the case of mappings
	there are no such things as order and postion. So member() only returns 0
	or 1.


	7. How can I copy a mapping?

	A mapping can be copied with the + operator or by the efun
	copy_mapping():

	newmap = ([]) + map;
	or:
	newmap = copy_mapping(map);

	A mapping should only be copied when it is neccesary to get an own copy
	of it that must not be shared by other objects.


	8. How can I get all keys of a mapping?

	The efun m_indices() gets a mapping as argument and returns an array
	holding all keys defined in this mapping:

	keys = m_indices(map);


	9. How can I get all the values of a mapping?

	The efun m_values() gets a mapping as argument and returns an array
	holding all the first (second, ...) values of it.

	values0 = m_values(map); returns the first values
	values0 = m_values(map, 0); dito
	values1 = m_values(map, 1); returns the second values
	etc


	10. How can I determine the size of a mapping?

	Because a mapping is a kind of rectangle it has two sizes: a length and
	a width. There are three different efuns to query these values. The first
	two are the efuns sizeof(), which returns the amount of key-value
	associations (the length of a mapping), and widthof(), which returns the
	number of values per key (the width). The third is the efun get_type_info().
	get_type_info() is meant to be a function to identify a datatype. Its
	return value is an array of two numerical values. The first specifies
	the datatype of the argument and the second is a datatype dependend
	value. In the case of a mapping the first value is T_MAPPING (which is a
	value defined in <lpctypes.h>) and the second the amount of values per
	key (a.k.a. columns or the width of the mapping - actually it would be
	correct to say that the width of a mapping is the amount of columns plus
	one for the keys but this is uncommon).


	11. What is the best method to iterate over a mapping?

	First of all the main purpose of a mapping is not meant to be a set of
	data to iterate over. Afterall the keys in a mapping have no specific but
	a random order (at least on the LPC side). But still it is possible and
	sometimes even neccesary to do so.

	If all key-value associations should be processed then one should use
	walk_mapping(). If all keys of a mapping should be processed to create a
	new mapping being a subset of the given one, then filter_mapping() should
	be used. If all keys are going to be processed and to create a new
	mapping with the same set of keys as the given mapping, then one would
	use map_mapping(). But in the case of an iteration that should/can stop
	even if not all data is processed it is probably wise to iterate over the
	mapping by first querying for the keys and then to iterate over them with
	a for() or a while() loop and querying the values by 'hand'.

	The efun walk_mapping() gets a mapping as first argument and the name
	of a function as second one. All the following arguments are treated as
	extras which will be passed to the function specified with the 2nd
	argument. Instead of a string for the name of a function a closure can be
	used, too. Nothing will be returned:

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

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

	func() will be called for all key-value associations and gets as first
	argument the key. The next arguments are the values behind the key and
	are passed as references. The rest of the passed arguments are those
	specified as extras. Because the values are passed as references (opposed
	to copies) it is possible to modify them from inside func() by simply
	assigning new value to the variables <value0>, ..., <valuen>.

	The efun filter_mapping() calls a function for each key in a mapping
	and creates a new mapping which only contains key-value associations for
	which the called function returned true (not equal 0 that is). The first
	argument is the mapping to iterate over and the second is a function name
	given as a string or a closure:

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

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

	func() gets as first argument the key and the others are those passed
	as extras to filter_mapping().

	The efun map_mapping() gets a mapping as first argument and a string as
	a function name (or again a closure) as second argument. Any additional
	arguments are again used as extras that will be passed to the iteration
	function. This efun returns a new mapping with the same keys as the given
	one. The values returned by the function that is invoked for each key
	will be used as the associated data behind each key of the new mapping:

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

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

	func() gets as first argument the key and the others are those passed
	as extras to map_mapping().

	Because a function can only return a single value (even when it is an
	array) it restricts the use of map_mapping() to only allow creation of
	mappings with a single value per key.


	12. Is it possible to join/intersect/cut mappings with another?

	Joining mappings is only possible, if they have the same width (amount
	of values per key). One can use the + and += operator:

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

	Intersection of two mappings is only possible by using
	filter_mapping(). There is no efun or operator which features this. The
	'easiest' way may be the following function:

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

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

	This function returns a new mapping which consists of all key-value
	associations of <map1> for which an equal key could be found in
	<map2>. This function uses a closure which returns 0 or 1 depending on
	wether a key from <map1> is contained in <map2> or not.

	Cutting out all key-value associations of a mapping for which a key
	could be found in another mapping can be done by using the - and -=
	operator:

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

	Because a maping can only be substracted by one without any values we
	first have to create such by using m_indices() and mkmapping().


	13. What are those mappings without any values (besides keys) good for?

	Because the way how the driver searches for a key in a mapping is
	rather fast, those mappings can be used as a set of elements with a fast
	method for testing if an element is contained in the set. This technique
	is called hashing (further explanation would lead too far) which is
	faster than searching for values in array (which is done in a linear
	fashion).

	Another (maybe more pratical) use of these mappings are to create a
	array of unique values out of an array with several equal values:

	uniques = m_indices(mkmapping(array));

	mkmapping() uses <array> to create a mapping without any values but
	just keys. And because a mapping can only have unique keys all multiple
	values in <array> are taken as one. The call of m_indices() then returns
	an array of these unique keys. Actually we only make use of those
	mappings temporarily.


	14. How can I convert an alist into a mapping and vice versa?

	There are no special efuns which handle such conversions. But it can be
	done by the following functions:

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

	The efun apply() takes a closure and an array of values and passes each
	element of the array as an argument to the closure. Because an alist
	consists of an array of arrays with the first beeing the list of keys and
	the others the values associated to each key passing them as arguments to
	the efun closure #'mkmapping via apply() causes the creation of a mapping
	out of an alist.

	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;
	}

	This function is a bit more complicated than the other and detailed
	description would lead too far of the topic. This function has one
	restriction: it can only turn a mappings with up to 26 values per key
	into an alist. But this should be sufficient for probably all
	applications which use mappings.

	And Hyps further comment on this:
	The function mapping_to_alist() is also not that
	clever because insert_alist() allways creates a new
	alist. A second (optional) argument to m_values() to
	specify the value column would be better. Besides
	this, the conversion of a mapping into an alist could
	be done by to_array().

	15. Dirty Mappings

	'Dirty mappings' are nothing the LPC programmer directly is involved
	with, however, as it relates to the way mappings are implemented
	internally by the gamedriver. However, as this term shows up in
	various driver statistics, it is explained here.

	There are two fundamental approaches to implement mappings:

	1. Store all data entries in an array-like structure, in sorted order.
	2. Store all data in a hashtable, each entry allocaed separately.

	Method 1 is very space efficient, as it doesn't need much overhead
	per entry; however, insertions and deletions of entries are
	relatively slow as all other entries need to be moved.
	Method 2 is very fast as nothing needs to be moved in memory,
	however it has a large overhead.

	The gamedriver uses a hybrid method: at the basis is a mapping
	implementation based on arrays. However the driver uses a hash table
	in addition to handle all the ongoing insertions and deletions.
	Every once in a while, the contents of the hash table are sorted
	into the base array, reasoning that any entry surviving for longer
	time in the hash table is worth keeping in a more space-efficient
	manner. 'Dirty' mappings are such mappings with both an array and a
	hash part, 'clean' mappings are those with just an array part.

	HISTORY
	The ([:width ]) notation was added in LDMud 3.2.9/3.3.208 .

	SEE ALSO
	alists(LPC), closures(LPC), structs(LPC), mkmapping(E),
	walk_mapping(E)