Added public files
Roughly added all public files. Probably missed some, though.
diff --git a/doc/LPC/mappings b/doc/LPC/mappings
new file mode 100644
index 0000000..381e3c8
--- /dev/null
+++ b/doc/LPC/mappings
@@ -0,0 +1,474 @@
+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)