
===========
pure-stlmap
===========

.. default-domain:: pure
.. module:: stlmap
.. module:: stlmmap
.. module:: stlhmap

Version @version@, |today|

| Peter Summerland <p.summerland@gmail.com>

pure-stlmap is a `Pure`_ interface to six associative containers provided by
the `C++ Standard Library`_: map, set, multimap, multiset, unordered_map and
unordered_set.

.. _Pure: http://purelang.bitbucket.org

.. _C++ Standard Library: http://en.cppreference.com/w/cpp

.. contents::
.. sectnum::


Copying
=======

| Copyright (c) 2012 by Peter Summerland <p.summerland@gmail.com>.

All rights reserved. 

pure-stlmap is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
A PARTICULAR PURPOSE. 

pure-stlmap is distributed under a BSD-style license, see the COPYING file
for details.

Introduction
============

This is pure-stlmap-0.1, the first release of pure-stlmap. It is possible that
some of the functions might be changed slightly or even removed. Comments and
questions would be especially appreciated at this early stage. 

Supported Containers
--------------------

The Standard C++ Containers Library, often refered to as the standard template
library ("STL"), provides templates for generic containers and generic
algorithms. pure-stlmap provides six mutable containers, "stlmap", "stlset",
"stlmmap", "stlmset", "stlhmap" and "stlhset", that are thin wrappers around
the corresponding associative containers provided by the STL, map, set,
multimap, multiset, unordered_map and unordered_set, specialized to hold
pure-expressions. pure-stlmap does not provide wrappers for unordered_multimap
and unordered_multiset.

Interface
---------

pure-stlmap provides a "key-based" interface that can be used to work with the
supported STL containers in a way that should feel natural to Pure
programmers. For example, the (!) function can be used to access values
associated with keys and functions like :func:`map/stlmap`,
:func:`foldl/stlmap`, :func:`filter/stlmap` and :func:`do/stlmap` can be used
to operate on all or part of a container's elements without using an explict
tail recursive loop. In addition, for the ordered containers, stlmap, stlmmap,
stlset and stlmset, pure-stlmap provides an "interator-based" interface that
corresponds to the C++ interface, mostly on a one-to-one basis.

The interface for the unordered or "hash table" containers, stlhmap and
stlhset, is limited compared to that provided for the ordered containers. In
particular iterators, operations on subsequences (ranges) and set operations
are not supported.

In some cases, the STL's associative containers have different semantics than
the the associative containers provided by the Pure standard library. Where
there is a conflict, pure-stlmap follows the STL.

Many of the functions provided by pure-stlmap, such as the constructors,
equivalence and lexicographical comparison operations, insert and erase
operations, and the set operations are just thin wrappers around the the
corresponding C++ functions. Users can consult the C++ Library documentation
to understand the performance characteristics and corner case behavior of any
pure-stlmap function that has a corresponding function in the STL.

The C++ library is sometimes more complicated than the Pure Standard
Library. For example many of the applicable C++ functions, including set
operations and tests for equality, assume that the containers are
lexicographically ordered. The reward for playing by the rules (which occurs
automatically for stlmap and stlset) is O(n) time complexity for comparison
and set operations.

Installation
============

pure-stlmap-@version@ is included in the "umbrella" addon, :doc:`pure-stllib`
which is available at https://bitbucket.org/purelang/pure-lang/downloads. After
you have downloaded and installed :doc:`pure-stllib`, you will be able to use
pure-stlmap (and :doc:`pure-stlvec`, as well).


Examples
========

The pure-stlmap/uts subdirectory contains Pure scripts that are used to test
pure-stlmap. These scripts contain simple tests, each of which consists of a
single line of code followed by a comment that contains the expected
output. E.g., ::

   let sm1 = stlmap ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5];
   //- ()

   sm1!stl::smbeg, sm1!"a", sm1!"d", sm1!"e"
   //- 1,1,4,5

   catch id $ sm1!"0";
   //- out_of_bounds

You might consider pasting parts of these scripts into a temporary file that
you can play with if you are curious about how something works.

Two short example programs, anagrams.pure and poly.pure, can be found in the
pure-stlmap/examples subdirectory.

Quick Start
===========

This section introduces the basic functions you need to get up and running
with pure-stlmap. For a quick look at the other functions provided by
pure-stlmap, you can refer to pure-stllib-cheatsheet.pdf, which can be found
in the pure-stllib/doc directory. 

Example Containers
------------------

The code snippets that appear in the examples that follow assume that
six containers have been created by entering the following at the prompt. ::

   $> pure -q
   > using stlmap, stlhmap, stlmmap;
   > using namespace stl;

   > // Make some maps and sets with default characteristics
   > let sm  = stlmap  ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5];
   > let shm = stlhmap ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5];
   > let smm = stlmmap ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4,"e"=>5];
   > let ss  = stlset  ["a","b","c","d","e"];
   > let shs = stlhset ["a","b","c","d","e"];
   > let sms = stlmset ["a","b","c","c","d"];

The ``using`` statement imports the three modules provided by pure-stlmap:
:mod:`stlmap` provides the interface for the stlmap and stlset containers,
:mod:`stlmmap` provides the interface the stlmmap and stlmset containers, and
:mod:`stlhmap` provides the interface to the stlhmap and stlhset
containers. The ``let`` statements set up an instance of each of the containers
provided by pure-stlmap, loaded with some sample elements.

To save typing you can run readme-data.pure, a file that contains the
corresponding source code. It can be found in in the pure-stlmap/examples
directory.

Constructors
------------

You can construct empty pure-stlmap containers using the
:func:`emptystlmap/stlmap`, :func:`emptystlset/stlmap`,
:func:`emptystlmmap/stlmap`, :func:`emptystlmset/stlmap`,
:func:`emptystlhmap/stlmap` and :func:`emptystlhset/stlmap` functions. ::

   > let sm1 = emptystlmap;   // uses (<) to order keys

You can construct a pure-stlmap container and fill it with elements all in one
go using the :func:`stlmap/stlmap`, :func:`stlset/stlmap`,
:func:`stlmmap/stlmap`, :func:`stlmset/stlmap`, :func:`stlhmap/stlmap` and
:func:`stlhset/stlmap` functions. ::

   > let shm1 = stlhmap ["a"=>1,"b"=>2,"c"=>3]; 

   > members shm1;
   ["c"=>3,"a"=>1,"b"=>2]

   > smh1!"b";
   2

As opposed to the hashed containers (stlhmap and stlhset), the ordered
containers (stlmap, stlset, stlmmap and stlmset) keep their elements ordered
by key. ::

   > let sm1 = stlmap ["a"=>1,"b"=>2,"c"=>3]; members sm1;
   ["a"=>1,"b"=>2,"c"=>3]

Ranges
------

For the ordered containers (stlmap, stlset, stlmmap and stlmset) you can work
with subsequences, called "ranges", of the containers' elements. A range is
specified by a tuple that consists of a container and two keys. If (sm,
first_key, last_key) designates a range, the elements of the range are
all of elements of the container sm whose keys are equivalent to or
greater than first_key and less than last_key. If first_key and
last_key are left out of the tuple, the range consists of all of sm's
elements. ::

   > members sm;               // no range keys - the whole container
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

   > members (sm,"b","e");     // a range from "b" up but not including "e"
   ["b"=>2,"c"=>3,"d"=>4]

   > members (sm,"c1","z");    // keys do not have to be stored
   ["d"=>4,"e"=>5]

   > members shm;              // works on a unordered set (with no range keys)
   ["c"=>3,"d"=>4,"e"=>5,"a"=>1,"b"=>2]

Two special keys, :cons:`stl::smbeg/stlmap` and :cons:`stl::smend/stlmap` are
reserved for use in ranges to designate the first element in a container and
the imaginary "past-end" element. ::

   > members (sm,smbeg,"d");
   ["a"=>1,"b"=>2,"c"=>3]

   > members (sm,"b",smend);
   ["b"=>2,"c"=>3,"d"=>4,"e"=>5]

Perhaps it should go without saying, but you cannot use either of these
symbols as the keys of elements stored in a pure-stlmap container.

Inserting and Replacing Elements
--------------------------------

You can insert elements and, for the maps (stlmap, stlmmap and stlhmap),
replace the values associated with keys that are already stored in the map,
using the :func:`insert/stlmap`, :func:`replace/stlmap` and
:func:`insert_or_replace/stlmap` functions. For the maps, the elements to
inserted are specified as (key=>value) hash-pairs. ::

   > let sm1 = emptystlmap;

   > insert sm1 ("e"=>5);              // returns number of elements inserted
   1
   > members sm1;
   ["e"=>5]

   > replace sm1 "e" 15;               // returns value
   15
   > members sm1;
   ["e"=>15]

   > catch id $ replace sm1 "x" 10;    // replace never inserts new elements
   out_of_bounds

   > insert sm1 ("e"=>25);             // insert never changes existing elements
   0
   > members sm1;
   ["e"=>15]

   > insert_or_replace sm1 ("e"=>25);  // 1 value changed 
   1                                   
   > members sm1;
   ["e"=>25]
   >

The :func:`insert/stlmap` and :func:`insert_or_replace/stlmap` functions are
overloaded to insert or replace elements specified in a list, vector, stlvec
or another pure-stlmap container (of the same type). E.g., ::

   > let sm2 = emptystlmap;

   > insert sm2 ["b"=>2,"a"=>1];       // insert from a list
   2

   > insert sm2 (sm,"c","e");          // insert from a range
   2

   > members sm2;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4]

   > insert_or_replace sm2 {"a"=>11,"e"=>15};
   2

   > members sm2;
   ["a"=>11,"b"=>2,"c"=>3,"d"=>4,"e"=>15]

Access
------

If you want to see if a key is stored in a container use the
:func:`member/stlmap` function. (A key, k, is considered to be "stored" in a
container if there is an element in the container that is equivalent to k.) ::

   > member sm "x";  // ("x"=>val) is not an element of sm for any val
   0

   > member sm "a";  // ("a"=>1) is an element with key equivalent to "a"
   1

The value (or values for a multi-key container) associated with a key can be
accessed using the (!) function. ::

   > sm!"a";   // return the value associated with "a"
   1

   > shm!"b";  // try it with a hashed map
   2

   > smm!"c";  // multimap returns a the list of values associated with "c"
   [31,32]

   > ss!"a";   // with sets, return the key
   "a"

   > sms!"c";  // with multisets, return a list of keys
   ["c","c"]

If the key is not stored in the container, (!) throws an :cons:`out_of_bounds`
exception. ::

   > catch id $ sm!"x"; // "x" is not stored as a key in sm
   out_of_bounds

Please note that all access is strictly by keys. For example you cannot use
the :func:`member/stlmap` function to determine if ("a"=>1) is an element
stored in sm; you can only ask if the key "a" is stored in sm.

Erasing Elements
----------------

For any pure-stlmap container, you can use the :func:`erase/stlmap` function
to remove all the elements associated with a given key in the container, all
of the elements in the container or, unless the container is a stlhmap or
stlhset, all of the elements in a range defined on the container. ::

   > let shm1 = stlhmap shm;       // make some copies of maps
   > let smm1 = stlmmap smm;
   > let sm1 = stlmap sm;

   > members smm1;                 // smm1 has multiple values for "c"
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4,"e"=>5]

   > erase (shm1,"c");             // erase "c" keyed elements from a stlmmap
   1
   > members shm1;                 // all the "c" keyed elements are gone
   ["d"=>4,"e"=>5,"a"=>1,"b"=>2]

   > erase shm1;                   // erase all elements
   4
   > empty shm1;
   1

   > erase (sm1,"b","d");         // erase a subsequence       
   2
   > members sm1;
   ["a"=>1,"d"=>4,"e"=>5]

   > erase (sm1,"x");             // attempt to erase something not there
   0

   > erase (smm1,"c");            // erase all elements with key "c"
   2
   > members smm1;
   ["a"=>1,"b"=>2,"d"=>4,"e"=>5]

Conversions
-----------

The elements of an associated container be copied into a list, vector or
stlvec using the :func:`members/stlmap`, :func:`stl::vector/stlmap` and
:func:`stlvec/stlmap` functions. For ordered containers (stlmap, stlset,
stlmmap and stlmset) the list, vector or stlvec can be built from a range. ::

   > members ss;
   ["a","b","c","d","e"]

   > members (ss,"b","d"); // list subsequence from "b" up to but not "d" 
   ["b","c"]

   > members (smm,"c","e");
   ["c"=>31,"c"=>32,"d"=>4]
   
   > members (shm,"b","d"); // fails - ranges not supported for stlhmaps
   stl::members (#<pointer 0x83b4908>,"b","d")

   > members shm;          // ok - all elements are copied
   ["d"=>4,"e"=>5,"a"=>1,"b"=>2,"c"=>3]

   > vector (sm,smbeg,"d");
   {"a"=>1,"b"=>2,"c"=>3}

   > using stlvec;
   > members $ stlvec sm; 
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

You can convert the contents of an ordered container (stlmap, stlset, stlmmap
or stlmset) or a range defined on one to a stream using the
:func:`stream/stlmap` function. ::

   > let ss1 = stlhset (0..100000);

   > stats -m

   > let xx = drop 99998 $ scanl (+) 0 (stream ss);
   0.3s, 18 cells

   > list xx;
   [704782707,704882705,704982704,705082704]
   0s, 17 cells

Functional Programming
----------------------

Most of the Pure list operations, including :func:`map/stlmap`,
:func:`do/stlmap`, :func:`filter/stlmap`, :func:`catmap/stlmap`,
:func:`foldl/stlmap` and :func:`foldl1/stlmap` can be applied to any of
pure-stlmap's associative containers. E.g., ::

   > map (\x->x-32) shs;
   ["D","E","A","B","C"]

   > using system;

   > do (puts . str) (sm,smbeg,"c");
   "a"=>1
   "b"=>2
   ()

List comprehensions also work. ::

   > [k-32=>v+100 | (k=>v) = smm; k>"a" && k<"e"];
   ["B"=>102,"C"=>131,"C"=>132,"D"=>104]

   > {k-32=>v+100 | (k=>v) = (smm,"b","e")};
   {"B"=>102,"C"=>131,"C"=>132,"D"=>104}

It is highly recommended that you use the functional programming operations,
as opposed to recursive loops, whenever possible.

Concepts
========

This section describes pure-stlmap's containers, iterators, ranges, elements,
keys, values and how these objects are related to each other. It also
describes a group of functions associated with containers that help define the
container's behavior. E.g., each ordered container (stlmap, stlset, stlmmap or
stlmset) stores a function that it used to order its keys and to determine if
two keys are equivalent.

Containers and Elements
-----------------------

The six associative containers supported by pure-stlmap can be grouped
together in terms of certain defining attributes. 

The three "maps" provided by pure-stlmap, stlmap, stlmmap and stlhmap,
associate values with keys. If a value v is associated with a key, k, in an
map, m, then we say that (k=>v) is an element of m, k is a key stored in m and
v is a value stored in m.

The three "sets" provided by pure-stlmap, stlset, stlmset and stlhset, hold
single elements, as opposed to key value pairs. If an element e is contained a
set, s, we say that e is simultaneously an element, key and value stored s. In
other words, we sometimes speak of a set as if it were a map where each
element, key and value are the same object.

The "ordered" containers, stlmap, stlset, stlmmap and stlmset, each have a
"key-less-than" function that they use keep their elements in a sequence that
is ordered by keys. The default key-less-than function is :func:`(<)/stlmap`,
but this can be changed when the container is created. The elements stored in
a stlmap or stlset have unique keys, i.e., two elements stored in the
container will never have equivalent keys. For these purposes, two keys are
"equivalent" if neither key is key-less-than the other. In contrast, stlmmap
and stlmset do not have unique keys. I.e., it is possible for different
elements stored in a stlmmap or stlmset can have equivalent keys.

The "hashed" containers, sthmap and stlhset do not keep their elements in a
sequence. Instead they store their elments in a hash table using a "key-hash"
function and a "key-equal" function. Currently the key-hash function is always
:func:`hash` and the key-equal function is always (===), both of which are
defined in the Prelude. The elements stored in a hashed container have unique
keys. I.e., two elements stored in the container will never by "key-equal". At
times we say that two keys stored in a hashed container are "equivalent" if
they are key-equal.
  
The "ordered maps", stlmap and stlmmap, each have a "value-less-than" function
and a "value-equal" function that is used for lexicographical comparisons. The
default functions are :func:`(<)` and (==) respectively, but these can
customized when the container is created.

As is the case for the underlying C++ functions, set operations (i.e., union,
intersection, etc.) and container equivalence for the ordered containers are
based on lexicographical comparisons. For these purposes one element, e1, is
less than another, e2, if (a) e1's key is less-than e2's key and, (b) if the
ordered container is a stlmap or stlmap, e1's value is value-less-than e2's
value. Finally, for purposes of determining if two ordered containers are
equal, e1 and e2 are considered to be equal if (a) their keys are equivalent
and (b), in the case of stlmap or stlmmap, their values are value-equal.

Set operations are not provided for the hashed containers, stlhmap and
stlhset.

Ranges
------

For the ordered containers (stlmap, stlset, stlmmap and stlmset), you can work
with a subsequence or "range" of a container's elements. Given an ordered
container, oc, and keys f and l, the range (oc,f,l) consists of all of the
elements in oc starting with the first element that is not less than f up to
but not including the first element that is greater or equal to l. Note that f
and l do not have to be stored in oc. ::

   > members (sm,"b","e");
   ["b"=>2,"c"=>3,"d"=>4]

   > members (sm,"c1",smend);
   ["d"=>4,"e"=>5]

When a range is passed to a function provided by pure-stlmap, the keys can be
dropped, in which case the range consists of all of the container's
elements. ::

   > members sm;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

Please note that support for ranges is not provided for the unordered
containers (stlhmap and stlhset). Most pure-stlmap functions that act on
ranges can, however, operate on stlhmaps or stlhsets as well, except that, for
stlhmaps and stlhsets, they always operate on all of the container's
elements. Accordingly, whenever the documentation of a function refers to a
range, and the container in question is a a stlhmap or stlhset, the range
simply refers to the container itself.

Iterators
---------

The native STL interface is based on "iterators" that point to elements in
containers. pure-stlmap provides support for iterators defined on its ordered
containers (stlmap, stlmmap, stlset and stlmset) but not for its unordered
containers (stlhmap and stlhset).

Iterators are most useful when dealing with stlmmaps where elements with
different values can have equivalent keys. In most cases, it is recommended
that you avoid using iterators. The functions that operate on or return
iterators are discussed separately at the end of this document.

Selecting Elements Using Keys
-----------------------------

Throughout pure-stlmap, unless you resort to using iterators, you can only
specify elements and ranges of elements using keys. For example you cannot use
the :func:`member/stlmap` function to see if a specific key, value pair is an
element of a stlmap.  ::

   > members sm;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

   > member sm "a";
   1

   > catch id $ member sm (a=>1);
   bad_argument

In the last line of code, :func:`member/stlmap` treats (a=>1) as a
key. Because (a=>1) cannot be compared to a string using :func:`(<)/stlmap`,
the ersatz key is treated as a bad argument.

This "key access only" approach can be an issue for stlmmaps and because
multiple elements can have equivalent keys. I.e., given a stlmmap, smm, that
containes multiple element with keys equivalent to, say, k, which element
should (!) return? pure-stlmap dodges this issue by returning all on
them. Thus, for stlmmap and stlmset (!) and :func:`replace/stlmap` work with
lists of elements associated with a given key rather than, say, the first
elment with the given key. ::

   > members smm;
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4];

   > smm!"c";
   "c"=>[31,32]

   > replace smm "c" [31,32,33]; members smm;
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"c"=>33,"d"=>4]

   > replace smm "c" []; members smm;
   ["a"=>1,"b"=>2,"d"=>4,"e"=>5]

If selecting and replacing lists of elements with the same key is not
convenient, you can always use iterators to track down and modify any specific
element.

C++ Implementation
------------------

For those that want to refer to the `C++ standard library documentation`_,
stlmap is (essentially) map<px*,px*>, stlmmap is multimap<px*,px*> and stlhmap
is unordered_map<px*,px*>, where px is defined by "typedef pure_expr
px". I.e., in C++ Containers library speak, key_type is px*, mapped_type is
px* and value_type is pair<px*,px*>. This might be a bit confusing because
pure-stlmap's (key=>value) "elements" correspond to C++ value_types, a
pair<key_type,mapped_type>, and pure-stlmap's values correspond to
mapped_types. The C++ objects for stlset, stlmset and stlhset are the same as
stlmap, stmmap and stlhmap except that pure-stlmap ensures that the second
member of the C++ value_type pair is always NULL.

.. _C++ standard library documentation: http://en.cppreference.com/w/cpp


Modules
=======

pure-stlmap provides three separate modules :mod:`stlmap`, :mod:`stlmmap` and
:mod:`stlhmap`.

Importing any one of these modules defines the stl namespace as well as two
important symbols, :cons:`stl::smbeg/stlmap` and :cons:`stl::smend/stlmap`.

.. namespace:: stl

.. constructor:: smbeg /stlmap
                 smend /stlmap

   These symbols are used to designate the key of the first element in an
   ordered container (stlmap, stlset, stlmmap or stlmset) and the key of an
   imaginary element that would come immediately after the last element of in
   the constainer. They are used to define ranges over the ordered
   containers. 

E.g., ::

   > members sm;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

   > members (sm,"c",smend);
   ["c"=>3,"d"=>4,"e"=>5]

.. namespace:: ::

The stlhmap Module
------------------

If all you want is fast insertion and lookup, you don't care about the order
of the elements stored in the container, and you do not want to use set
operations like :func:`stl::map_intersection/stlmap`, then :mod:`stlhmap` is
probably your best choice. The supported containers, stlhmap and stlhset are
simpler to use and faster than the other containers provided by pure-stlmap.

The :mod:`stlhmap` module defines stlhmaps and stlhsets and provides functions
for dealing with them. You can import it by adding the following ``using``
statement to your code. ::

  > using stlhmap;

The :mod:`stlhmap` module defines types two types:

.. type:: stlhmap /type
          stlhset /type

Please note that a stlhset is just a stlhmap where the values associated with
keys cannot be accessed or modified. I.e., a stlhset is a specialized kind of
stlhmap.

The stlmap Module
-----------------

The :mod:`stlmap` module provides you with stlmaps and stlsets and the
functions that operate on them. Consider using these containers if you want
their elements to be orderd by key, want to use ranges or if you are using any
set operations (:func:`stl::map_union/stlmap`,
:func:`stl::map_intersection/stlmap`, etc).

You can import the stlmap module by adding the following using statement to
your code. ::

  > using stlmap;

Importing the stlmap module introduces types to describe stlmap and stlset,
their iterators and ranges defined on them.

.. type:: stlmap /type
          stlset /type

.. type:: stlmap_iter /type

.. type:: stlmap_rng /type

Please note that a stlset is just a stlmap where the values associated with
keys cannot be accessed or modified. I.e., a stlset is a specialized kind of
stlmap. Accordingly, it is not necessary, for example, to define a separate
type for iterators on stlsets as opposed to iterators on stlmaps.

The stlmmap Module
------------------

If you need a multi-keyed container, the :mod:`stlmmap` module, which provides
support for stlmaps and stlmsets, is your only choice. Set operations and
ranges are supported, but the semantics are more complicated than is the case
for stlmap and stlset. Because the keys stored in multi-keyed containers are
not unique you might have to resort to using iterators when working with them.

You can import the :mod:`stlmmap` module by adding the following using
statement to your code. ::

  > using stlmmap;

Importing the stlmmap module introduces types to describe stlmmap and stlmset,
along with their iterators and ranges defined on them.

.. type:: stlmmap /type
          stlmset /type

.. type:: stlmmap_iter /type

.. type:: stlmmap_rng /type

Please note that a stlmset is just a stlmmap where the values associated with
keys cannot be accessed or modified. I.e., a stlmset is a specialized kind of
stlmmap. Accordingly, it is not necessary, for example, to define a separate
type for iterators on stlmsets as opposed to iterators on stlmmaps.

Container Operations
====================

Each of the six associative containers supported by pure-stlmap has its own
set of unique characteristics. Because of this the description of functions
that operate on more than one type of container can get a little complicated.
When reading this section it might be helpful to consult
pure-stllib-cheatsheet.pdf which can be found in the pure-stlib/doc directory.

Container Construction
----------------------

New empty ordered containers (stlmap, stlset, stlmmap and stlmset) can be
constructed using optional parameters that allow you to specify customized
key-less-than functions, default values, value-less-than and value-equal
functions.

.. namespace:: ::

.. function:: mkstlmap /stlmap (klt,dflt,vlt,veq)
              mkstlmmap /stlmap (klt,dflt,vlt,veq)
  
   Create a new stlmap or stlmmap where ``klt`` is the map's key-less-than
   function. dflt is the maps default value (used by replace_with and
   find_with_default). vlt is the map's value-compare function and veq is its
   value-equal function.  Only ``klt`` is required, and the default values for
   dflt, vlt, veq are [], (<) and (==) respectively.

.. function:: mkstlset /stlmap klt
              mkstlmset /stlmap klt

   Create a new stlset or stlmset where ``klt`` is the set's key-less-than
   function.

The internal lookup functions for the ordered containers (stlmap, stlset,
stlmmap and stlmset) are optimized to avoid callbacks if the container's
key-less-than function is is :func:`(>)/stlmap` or :func:`(<)/stlmap` and the
keys being compared are a pair of strings, ints, bigints or doubles.

You can create an empty associative container using default values for using
:func:`emptystlmap/stlmap` and friends. 

.. function:: emptystlmap /stlmap
              emptystlmmap /stlmap
              emptystlset /stlmap
              emptystlmset /stlmap 

   Create a new ordered map or set using default values. I.e., emptystlmap is
   the same as mkstlmap :func:`(<)`, and so on. 

.. function:: emptystlhmap /stlmap
              emptystlhset /stlmap

   Create a new stlhmap or stlhset with default values. The hash-function is
   hash and the value-equal function is (===).

Convenience functions are also provided to construct an empty container and
insert elements into it in one go. The source of the elements can be a list,
vector, a stlvec, or a range defined on another container of the same type as
the new container.

.. function:: stlmap /stlmap src
              stlmmap /stlmap src
              stlset /stlmap src
              stlmset /stlmap src
              stlhmap /stlmap src
              stlhset /stlmap src

   Create an associative constructor using default values and insert elements
   from copied from ``src``. ``src`` can be a list, vector or stlvec of
   elements or a range defined over a container of the same type as the new
   container. If the new container is a stlmap, stlmmap or stlhmap, the
   elements of src must be (key=>val) pairs. If the new container is a stlset,
   stlmset or stlhset they can be any pure expression that can be used as a
   key (i.e., anything except for :cons:`stl::smbeg/stlmap` or
   :cons:`stl::smend/stlmap`).

Information
-----------

This group of functions allows you make inquiries regarding the number of
elments in a container, the number of instances of a given key held by a
container, the upper and lower bounds of a range and other information. In
addition this group includes a function that can be used to change the number
of slots used by a stlhmap or stlhset.

.. namespace:: ::

.. function:: prefix # /stlmap acon

  Return the number of elements in ``acon``.

.. namespace:: stl

.. function:: empty /stlmap acon

  Return true if ``acon`` is empty, else false.

.. function:: distance /stlmap rng

   Returns the number of elements contained in ``rng`` where rng is a range
   defined on an ordered container (stlmap, stlmmap, stlset, stlmset).

.. function:: count /stlmap acon k

   Returns the number of elements in an associative container, acon, that have
   a key that is equivalent to ``k``.

.. function:: bounds /stlmap rng

   Return a pair of keys, first and last, such that first <= k < last for each
   k, where k is the key of an element in ``rng``. If there is no such last,
   the second member of the returned pair will be
   :cons:`stl::smend/stlmap`. If first is the key of the first element of
   ``rng's`` container, the first member of the returned pair will
   :cons:`stl::smbeg/stlmap`. 

Here are two examples using the :func:`stl::bounds/stlmap` function. Notice
that bounds returns :cons:`stl::smbeg/stlmap` instead of "a" in the first
example. ::

     > members sm;
     ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

     > bounds sm;
     stl::smbeg,stl::smend

     > bounds (sm,"a1","e");
     "b","e"

.. function:: container_info /stlmap acon

   If ``acon`` is a stlmap or stlmmap, returns (0, klt, dflt, vlt, veq) where
   klt is ``acon``'s key-less-than function, dflt is its default value, vlt is
   its value-less-than function and veq is its value_equal function. If
   ``acon`` is a stlset or stlmset, returns (1,klt,_,_,_) where klt is
   ``acon``'s key-less-than function. If ``acon`` is a stlhmap or stlhset,
   returns (is_set, bucket_count, load_factor, max_load_factor).

.. function:: bucket_size /stlmap hacon n

   Returns the number of elements in ``hacon``'s nth (zero-based) bucket where 
   ``hacon`` is a stlhmap or stlhset.

.. function:: hmap_reserve /stlmap hacon mlf size

   Sets ``hacon``'s max_load_factor to ``mlf``, sets the number of ``hacon 's
   buckets to ``size``/``mlf` and rehashes ``hacon`` where ``hacon`` is a
   stlhmap or stlhset.

Modification
------------

.. namespace:: ::

You can insert new items or, for the maps (stlmap, stlmmap and stlhmap),
replace values associated with keys using the :func:`insert/stlmap`,
:func:`replace/stlmap` or :func:`insert_or_replace/stlmap` functions.

Please note that when working with the ordered containers (stlmap, stlset,
stlmmap and stlmset) the keys of elements passed to these functions must be
compatible with the container's key-less-than function and keys that are
already inserted. E.g., ::

   > members ss;
   ["a","b","c","d","e"]

   > catch id $ insert ss 1;   // e.g., 1<"a" is not defined
   bad_argument

Currently there is no similar restriction for stlhmaps and stlhsets because
(a) they do not have a key-less-than function and (b) the function they do use
for testing equality, the key-equal function is always (===), a function that
can compare any two objects. ::

   > members shs;
   ["c","d","e","a","b"]

   > insert shs 1;
   1
   > members shs;
   ["c",1,"d","e","a","b"]

Elements can be inserted into a pure-stlmap container individually or en masse
from a list, vector, stlvec or another container of the same type. If there is
a key in the container that is equivalent to the key of the element being
inserted, the element will not be inserted (unless the container is a stlmmap
or stlmset, both of which can hold multiple elements with equivalent keys).

.. function:: insert /stlmap acon src

  Attempts to copy elements from ``src`` a valid "insert source" into ``acon``
  which can be any pure-stlmap container. A valid insert source is (a) a
  single element, (b) a list, vector, stlvec of elements or (c), a range over
  an associative container of the same type as ``acon``. If ``acon`` is an
  associative map (stlmap, stlmmap or stlhmap), the ``src`` itself, or all the
  elements of ``src``, must be key value pairs of the form (k=>v). In
  contrast, if ``acon`` is a stlset, stlmset or stlhset, ``src`` or all of its
  elements can be any pure object (except :cons:`stl::smbeg/stlmap` or
  :cons:`stl::smend/stlmap`). If ``acon`` is a stlmap, stlset, stlhmap or
  stlhset, the element will not be inserted if its key is already stored in
  the target container. Returns the number of elements inserted, if any.

If you are dealing with a stlmap or stlhmap and want to override the values of
elements have keys that equivalent to the keys of the items you wan to insert
you can use the :func:`insert_or_replace/stlmap` function.

.. function:: insert_or_replace /stlmap acon src

  The same as :func:`insert/stlmap` except that (a) ``acon`` must be a stlmap
  or a stlhmap and (b) if an element (key=>newval) is about to be inserted and
  the container already contains an element (key=>oldval) the element in the
  container will be changed to (key=>newval). Returns the number of elements
  inserted or updated.

.. function:: replace /stlmap map key x

   ``map`` must be a stlmap, stlmmap or stlhmap. If ``key`` is not stored in
   ``map`` this function throws :cons:`out_of_bounds`. If ``map`` is a stlmap
   or stlhmap and (oldkey=>oldval) is an element of ``map``, where oldkey is
   equivalent to ``key``, change the element to (oldkey=>``x``). If ``map`` is
   a stlmmap and ``key`` is stored in ``map``, change the values of elements
   with key eqivalent to ``key``, one by one, to the elements of ``x``. Add or
   delete elements as necessary so that, when the smoke clears, the values of
   ``map``!``key`` are copies of the elements of ``x``. In all cases, if
   ``key`` is stored in ``map`` returns ``x``.

Here are some examples using :func:`replace/stlmap`. ::

   > members sm1;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

   > replace sm1 "e" 50;
   50

   > members sm1;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>50]

   > members smm1;
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4,"e"=>5]

   > replace smm1 "c" [31,33,35,36] $$ smm1!"c";
   [31,33,35,36]

   > replace smm1 "c" [] $$ smm1!"c";
   []

   > members smm1;
   ["a"=>1,"b"=>2,"d"=>4,"e"=>5]

.. function:: replace_with /stlmap fun map (k=>v)

  ``map`` must be a stlmap. The effect of this function is as follows: (a) if
  ~ :func:`member/stlmap` ``map`` ``k`` then :func:`insert/stlmap` ``map``
  (``k``=>dflt) else (), where dflt is ``map``'s dflt value, (b)
  :func:`replace/stlmap` ``map`` ``k`` nv when nv = ``fun`` ``v``
  (``map``!``k``) end. Returns ``map``.

Here is an example using :func:`replace_with/stlmap` in which a stlmmap is
converted to a stlmap. ::

   > let sm1 = emptystlmap;

   > members smm;
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4,"e"=>5]

   > do (replace_with (:) sm1) smm;
   ()

   > members sm1;
   ["a"=>[1],"b"=>[2],"c"=>[32,31],"d"=>[4],"e"=>[5]]

Here is another example in which items are counted. ::

   > let sm1 = mkstlmap ( (<), 0 );

   > members sms;
   ["a","b","c","c","d"]

   > do (\x->replace_with (+) sm1 (x=>1)) sms;
   ()

   > members sm1;
   ["a"=>1,"b"=>1,"c"=>2,"d"=>1]

You can remove all the elements in a container, remove all the elements
equivalent to a given key or a remove a range of elements using the
:func:`erase/stlmap` function.

.. function:: erase /stlmap acon
              erase /stlmap (acon,k)
              erase /stlmap (acon,k1,k2)

  The first form erases all elements in ``acon`` which can be any container
  provided by pure-stlmap. The second erases all elements in ``acon`` with key
  equivalent to ``k``. The third erases the elements in the range
  (``acon``,``k1``,``k2``). The third form only applys to the ordered
  containers (stlmap, stlmmap, stlset and stlmset), not stlhmap or stlhset
  (because ranges are not defined for stlhmaps or stlhsets). Returns the
  number of elements removed from the container. 

Here are some examples using :func:`erase/stlmap`. ::

   > members smm;
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4,"e"=>5]

   > erase (sm,"z");
   0

   > erase (smm,"c");
   2

   > members smm;
   ["a"=>1,"b"=>2,"d"=>4,"e"=>5]

   > erase (smm,"b","e");
   2

   > members smm;;
   ["a"=>1,"e"=>5]

.. namespace:: stl

.. function:: swap /stlmap acon1 acon2

  Swaps the elements of the two containers, ``acon1`` and ``acon2`` where
  ``acon1`` and ``acon2`` are the same type of container (E.g., both are
  stlmaps or both are stlmsets).

Accessing Elements
------------------

.. namespace:: ::
   
You can test if a key is stored in a container and access the value associated
with a key using the familiar :func:`member/stlmap` and (!) functions.

.. function:: member /stlmap acon k

   Returns true if ``acon``, any container provided by pure-stlmap, contains
   an element that has a key that is equivalent to ``k``.

.. function:: infix ! /stlmap acon k

  If ``acon`` is not a stlmmap then (a) if ``acon`` has an element with key
  equivalent to ``k`` return its value, otherwise (b) throw an
  :cons:`out_of_bounds` exception. If ``acon`` is a stlmmap then (a) if acon
  has as least one element with key equivalent to ``k`` return a list of
  values of all the elements with key equivalent to ``k``, otherwise (b)
  return an null list.

E.g.::

   > sm!"c";
   3

   > catch id $ sm!"f";    // "f" is not stored in sm
   out_of_bounds

   > catch id $ sm!100;    // 100 cannot be compared to strings using (<)
   bad_argument

   > smm!"c";              // for stlmmap, return list of values
   [31,32]

   > smm!"f";              // stlmmap returns null list if key is not stored
   []

.. namespace:: stl

You can access a sequence of elements in an ordered container (stlmap, stlset,
stlmmap or stlmset) without resorting to iterators using the next_key and
prev_key functions.

.. function:: next_key /stlmap acon k
              prev_key /stlmap acon k

   ``acon`` must be a stlmap, stlset, stlmmap or stlmmap. Also if ``k`` is not
   :cons:`stl::smbeg/stlmap`, :cons:`stl::smend/stlmap` or an element of acon
   an :cons:`out_of_bounds` exception will be throw.  :func:`next_key/stlmap`
   returns the key of the first element in acon that has a key that is greater
   than ``k``. If no such element exists or if ``k`` is
   :cons:`stl::smend/stlmap`, returns :cons:`stl::smend/stlmap`.
   :func:`prev_key/stlmap` returns the last element in acon that has a key
   that is less that ``k``, or, if no such element exists, throws an
   :cons:`out_of_bounds` exception.

.. namespace:: ::

For various reasons, it is very common to see a call to (!) or
:func:`replace/stlmap` preceded by a call to :func:`member/stlmap` with the
same container and key. E.g., ::

   > bump_wc sm w = if member sm w then replace sm w (sm!w + 1)
                    else insert sm (w=>1);

In general, this function would require two lookups to add a new word and
three lookups to bump the count for an existing word. For the ordered
containers, lookups have O(log N) complexity which can be relatively slow for
large containers.

To speed things up, each stlmap or stlset maintains a small cache of (key, C++
iterator) pairs for recently accessed keys. During lookup, the cache is
checked for a matching key, and if the key is found, the element pointed to by
the C++ iterator is used immediately. Thus, when applied to a stlmap or
stlset bump_wc will use only one O(log N) search, rather than two or
three. For these purposes, a key matches a key in the cache only if it is the
same Pure object (i.e., the test is C++ pointer equality, not Pure's (===) or
(==) functions). For example, the following will result in two O(log N)
lookups. ::

  > if member sm "a" then sm!"a" else insert sm ("a"=>10);

Here each "a" is a distinct Pure object. The two "a"s satisfy (==) and even
(===) but they are not the same internally and the caching mechanism will not
help.

Almost any pure-stlmap function that accepts a stlmap or stlset as an argument
will check the container's cache before doing an O(log N) lookup.  Currently
the cache is limited to hold only the most recently used key.

Here are some examples produced by compiling pure-stlmap with a trace function
that shows caching in action. ::

   > let a_key = "a";

   > members sm;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

   > member sm a_key;           // a_key is not yet in the cache
   1

   > sm!a_key;                  // a_key is found in the cache
   found iterator for: "a"
   1

   > replace sm a_key 10;
   found iterator for: "a"
   10

   > sm!"a";                    // "a" is a new key, not same C++ pointer as k or a_key
   1

   > let k = next_key sm a_key; // now k is in the cache, in front of a_key
   found iterator for: "a"

   > let k1 = next_key sm k;    // now k1 is at the head of the queue
   found iterator for: "b"

   > replace sm k1 30;
   found iterator for: "c"
   30

   > members sm;
   ["a"=>10,"b"=>2,"c"=>30,"d"=>4,"e"=>5]

These examples show that caching can be effective wnen visiting elements of a
stlmap or stlset in order using :func:`next_key/stlmap` or
:func:`prev_key/stlmap`.

Conversions
-----------

.. namespace:: ::

The contents of a pure-stlmap container can be copied to a list, vector,
stlvec. For stlmaps, stlsets, stlmmaps and stlmsets, these operations
act on ranges as well as on the entire container.

.. function:: members /stlmap rng

  Returns a list of the elments in the range, ``rng``. 

.. function:: keys /stlmap rng
              vals /stlmap rng

  Return the keys and vals of the range's elements.

Here are some examples using the :func:`members/stlmap`, :func:`keys/stlmap`
and :func:`vals/stlmap` functions. ::

   > members shm;   // must do all of shm elements because shm is a stlhmap
   ["d"=>4,"e"=>5,"a"=>1,"b"=>2,"c"=>3]

   > keys (sm,"b","e"); // can ask for a range - sm is an ordered container
   ["b","c","d"]

   > vals (sm,"b","e");
   [2,3,4]

.. namespace:: stl

.. function:: vector /stlmap rng

  Return a vector containing the elments of in the range, rng.

.. namespace:: ::

.. function:: stlvec /stlmap rng

  returns a stlvec containing the elments of in the range, rng.

You can also convert an ordered container (stlmap, stlset, stlmmap or stlmset)
into a stream of elements.

.. function:: stream /stlmap rng

  Returns a stream consisting of the range's elements.

Here is an example using the stream function on a stlmmap. ::

   > members smm;
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4,"e"=>5]

   > take 3 $ stream smm;
   ("a"=>1):#<thunk 0xb70f438c>

   > list ans;
   ["a"=>1,"b"=>2,"c"=>31]

Functional Programming
----------------------

pure-stlmap provides the most commonly used functional programming operations,
implemented to act on ranges as if they were lists.

.. function:: do /stlmap fun rng
              map /stlmap fun rng
              filter /stlmap pred rng
              foldl /stlmap fun x rng
              foldl1 /stlmap fun rng
              foldr /stlmap fun x rng
              foldr1 /stlmap fun rng
   
   These functions are the same as the corresponding functions provided in the
   Prelude for lists. ``rng`` is a rng defined on a stlmap, stlset, stlmmap or
   stlmset or ``rng`` is simply a stlhmap or stlhset. :func:`foldr/stlmap` and
   :func:`foldr1/stlmap` are not defined for stlhmaps or stlhsets.

Here are some examples. ::

   > members sm;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

   > map (\(k=>v)->k+str v) (sm,"b","e");
   ["b2","c3","d4"]

   > foldr1 (\(k=>v) (ks=>sum)-> (k+ks=>v+sum)) (sm,"b","e");
   "bcd"=>9

   > filter (\(k=>v)->v mod 2) sm;
   ["a"=>1,"c"=>3,"e"=>5]


.. function:: listmap /stlmap fun rng
              catmap /stlmap fun rng
              rowmap /stlmap fun rng
              rowcatmap /stlmap fun rng
              colmap /stlmap fun rng
              colcatmap /stlmap fun rng

   These functions are the same as the corresponding functions provided in the
   Prelude for lists. ``rng`` is a rng defined on a stlmap, stlset, stlmmap or
   stlmset or simply a stlhmap or stlhset. 

These functions are provided primarily to enable the use of list and matrix
comprehensions over pure-stlmap's containers. E.g., ::

   > [ k + str v | (k=>v) = (sm,"b","e")];
   ["b2","c3","d4"]

   > [ k=>v | (k=>v) = sm; v mod 2];
   ["a"=>1,"c"=>3,"e"=>5]

   > { {k;v} |  (k=>v) = sm; v mod 2};
   {"a","c","e";1,3,5}

The functional programming operations work directly on the underlying data
structure. ::

   > let ints = 0..10000;

   stats -m
   > filter (==99) ints;
   [99]
   0s, 6 cells

Comparison 
----------

Two associative containers of the same type are considered to be equal if they
contain the same number of elements and if each pair of their corresponding
elements are equal. Two elements are equal if their keys are equivalent and,
if the container is a stlmap, stlmap or stlhmap, the values associated with
equal keys are equal (using the container's value-equal function).

.. namespace:: stl

.. function:: map_equal /stlmap rng1 rng2

.. namespace:: :: 

.. function:: infix == /stlmap rng1 rng2
              infix ~= /stlmap rng1 rng2

  Test ``rng1`` and ``rng2`` for equality or nonequality where ``rng1`` and
  ``rng2`` are ranges defined over containers of the same type. 

You need to be careful when using these operators. E.g., ::

   > members ss;
   ["a","b","c","d","e"]
 
   > let xx = stlset ss;

   > xx == ss;
   1

   > (xx,"a","c") == (ss,"a","c");  // oops!
   0

The second comparison was intended to compare identical ranges and return
true. It failed to do so because (==) is defined in the Prelude to compare
tuples element by element, long before it is defined in the stlmap module to
compare ranges. The tuple operation take precedence and determines that the
tuples are not equal because ``xx`` and ``ss`` are different (pointers) for
purposes of this comparison. To avoid this issue when using ranges, you can
use the :func:`stl::map_equal/stlmap` function. ::

   > map_equal (xx,"a","c") (ss,"a","c");
   1

The other comparison operators :func:`(<)/stlmap`, :func:`(<=)/stlmap`,
:func:`(>)/stlmap` and :func:`(>=)/stlmap` are provided only for the ordered
containers (stlmap, stlset, stlmmap and stlmset). These operators reflect
lexicographical comparisons of keys and, then if the keys are equal,
lexicographical comparisons of values. I.e., this is not set inclusion - order
matters. Accordingly, these comparison operators are not defined for a stlhmap
or stlhset.

.. function:: infix <  /stlmap rng1 rng2

   Traverse the ranges comparing pairs of elements e1 and e2. If e1 is less
   than e2, stop and return true; if e2 is less than e1 then stop and return
   false. If rng1 is exhausted but rng2 is not, return true, else return false. 
   The two ranges must be defined on ordered associative containers of the
   same type.

.. function:: infix >  /stlmap rng1 rng2
              infix <= /stlmap rng1 rng2
              infix >= /stlmap rng1 rng2

  The these three operators are the same as ``rng2`` < ``rng1``,
  ~(``rng1``>``rng2`) and ~(``rng1``<``rng2``) respectively.

You also have to be careful when using equivalence and comparison operators
with stlmmaps because elements with the same key and different values are not
necessarily ordered by values. ::

    > let smm2 = stlmmap ["a"=>1,"b"=>2,"c"=>32,"c"=>31,"d"=>4];

    > members smm;
    ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4]

    > members smm2;
    ["a"=>1,"b"=>2,"c"=>32,"c"=>31,"d"=>4]

    > smm == smm2; // probably not what you want
    0 

These operations do not make much sense for a stlmmap unless elements with
equivalent keys are stored by value, in the order enforced by the stlmmap's
value-comp function. In this regard it is worth noting that, depending on your
implementation, the :func:`insert/stlmap` function may or may not preserve the
order of insertion of elements with equivalent keys (C++11 does preserve the
order).

Set Algorithms
--------------

.. namespace:: stl

pure-stlmap provides wrappers for the STL set algorithms that apply to ranges
defined on the four ordered associative containers (stlmap, stlset, stlmmap
and stlmset). These algorithms are very efficient, with linear time
complexity, but they do require that the elements of the two ranges be
ordered. Accordingly, the set algorithms are not applicable to stlhmap or
stlhset. Also, when dealing with stlmmaps, care must be taken to ensure that
items with the equivalent keys are ordered by their values.

.. function:: map_merge /stlmap rng1 rng2

  Constructs a new ordered container from ``rng1`` and then insert the elments
  of ``rng2`` into the new container and return it. ``rng1`` and ``rng2`` must
  be defined on the same type of ordered container.

.. function:: map_union /stlmap rng1 rng2
              map_difference /stlmap rng1 rng2
              map_intersection /stlmap rng1 rng2
              map_symmetric_difference /stlmap rng1 rng2
              map_includes /stlmap rng1 rng2

   Returns a new ordered associative container of the same type as the ordered
   containers underlying ``rng1`` and ``rng2``. If the ranges are defined over
   a stlmap or stlmmap elements of ``rng1`` have priority over the elments of
   ``rng2``. Uses ``rng1``'s key-less-than, value-less-than and value-equal
   functions.

pure-stlmap's set functions do not necessarily produce the same results as
their Pure standard library counterparts. In particular, when applied to
multi-keyed contaners, :func:`stl::map_union/stlmap` Produces the multiset
union of its arguments while (+) in the Pure standard library produces the
multiset sum. If you want the multiset sum of a stlmmap or stlhmap, use
:func:`stl::map_merge/stlmap`. Also, in pure-stlmap, as in the STL, the left
hand map or set has priority of elements while in the Pure standard library
the right hand set has priority of elements. This can make a difference when
applying set operations to a pair of stlmaps or stlmmaps. E.g., ::

   > let smm1 = stlmmap ["a"=>1,"b"=>2,"c"=>31,"c"=>32];
   > let smm2 = stlmmap ["c"=>32,"c"=>32,"c"=>33,"d"=>4,"e"=>5];

   > members $ map_merge smm1 smm2; // three "c"=>32
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"c"=>32,"c"=>32,"c"=>33,"d"=>4,"e"=>5]

   > members $ map_union smm1 smm2;  // two "c"=>32
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"c"=>32,"c"=>33,"d"=>4,"e"=>5]

   > let sm1 = stlmap ["a"=>1,"b"=>2,"c"=>31];
   > let sm2 = stlmap ["c"=>32,"d"=>4,"e"=>5];

   > members $ map_union sm1 sm2; // "c"=>31 from sm1, not "c"=>32 from sm2
   ["a"=>1,"b"=>2,"c"=>31,"d"=>4,"e"=>5]

   > members $ map_intersection sm1 sm2; // "c"=>31 from sm1
   ["c"=>31]

Direct C Calls
--------------

.. namespace:: ::

It is common to encounter code that (a) tests if a key is stored in a
container using :func:`member/stlmap` and (b) in the case of maps, retreives
the value or values associated with the key using (!) and/or (c) changes the
value or values using :func:`replace/stlmap`. Depending on what modules have
been loaded, these functions may be heavily overloaded which can cause a small
delay when the functions are called. To avoid this, pure-stlmap exposes the
corresponding C functions so that they can be called directly. The C functions
have the same name as the overloaded functions except for a prefix. E.g.,

.. namespace:: stl

.. function:: sm_member /stlmap sm key
              sm_get /stlmap sm key
              sm_put /stlmap sm key val

  The first two functions are the direct C call equivalents of
  (:func:`::member/stlmap` ``sm`` ``key``) and (``sm!key``). The third is like
  (:func:`::replace/stlmap` ``sm`` ``key`` ``val``) except that it will insert
  (key=>val) if key is not already stored in ``sm``. Here, ``sm`` is a stlmap
  or a stlset (except that sm_put is not defined for stlsets).

.. namespace:: stl

.. function:: shm_member /stlmap shm key
              shm_get /stlmap shm key
              shm_put /stlmap shm key val

  The first two functions are the direct C call equivalents of
  (:func:`::member/stlmap` ``shm`` ``key``) and (``shm!key``). The third is
  like (:func:`::replace/stlmap` ``shm`` ``key`` ``val``) except that it will
  insert (key=>val) if key is not already stored in ``shm``. Here, ``shm`` is
  a stlhmap or a stlhset (except that shm_put is not defined for stlhsets).

.. namespace:: stl

.. function:: smm_member /stlmap smm key
              smm_get /stlmap smm key
              smm_put /stlmap smm key vals

  The first two functions are the direct C call equivalents of
  (:func:`::member/stlmap` ``smm`` ``key``) and (``smm!key``). The third is
  like (:func:`::replace/stlmap` ``smm`` ``key`` ``val``) except that it will
  insert (key=>val1, key=>val2, ...) if key is not already stored in ``smm``.
  Here, ``smm`` is a stlmmap or a stlmset (except that smm_put is not defined
  for stlmsets).

Iterators
=========

.. namespace:: stl

This section provides a quick overview of pure-stlmap's "iterator-based"
interface.

Concepts
--------

Given a valid iterator you can access, modify or erase the element it points
to. ::

   > let sm1 = stlmap sm; members sm1;  
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5];

   > let i = find sm1 "b";   // use find to get an iterator - like C++

   > get_elm i; 
   "b"=>2

   > get_val i; 
   2

   > put_val i 20;
   20

   > members sm1;
   ["a"=>1,"b"=>20,"c"=>3,"d"=>4,"e"=>5]

Please note that you can never modify an element's key, only its value. If you
want to change both key and value, you have to erase the element and insert a
new element. ::

   > erase (sm1,i) $$ insert sm1 ("b1"=>21);
   1

   > members sm1;
   ["a"=>1,"b1"=>21,"c"=>3,"d"=>4,"e"=>5]

Given two iterators, i and j, pointing into a ordered container oc, the
range (i,j), denotes oc's elements starting with "oc[i]", the element pointed
to by i, up to but not including oc[j]. In pure-stlmap, this range is denoted
by the tuple (i,j). ::

   > members sm;
   ["a"=>1,"b"=>2,"c"=>3,"d"=>4,"e"=>5]

   > let i = stl::find sm1 "b"; // get the iterator

   > let j = stl::find sm1 "e";

   > members (i,j);             // get the elements in the range
   ["b"=>2,"c"=>3,"d"=>4]

Perhaps it is worth mentioning that functions that act on ranges do not care
if the range is specified by a pair of iterators or by keys. ::

   > members ss;
   ["a","b","c","d","e"]

   > map (+21) (ss,"c",smend);
   ["x","y","z"]

   > let i = find ss "c";
   > let j = pastend ss;
   > map (+21) (i,j);
   ["x","y","z"]

Exceptions
----------

In pure-stlmap functions that accept iterators throw a :cons:`bad_argument`
exception if called with an invalid iterator. An iterator remains valid until
the element it was pointing to has been erased. These functions also attempt
to throw bad argument exceptions for invalid usage that would otherwise result
in undefined behavior. An example of an invalid use would be a range specified
by iterators from different containers. Here are some examples of iterator
errors. ::

   > let i,j = find sm "a", find sm "d";

   > get_elm i, get_elm j;
   "a"=>1,"d"=>4

   > members (i,j);
   ["a"=>1,"b"=>2,"c"=>3]

   > catch id $ members (j,i); // j and i transposed, C++ would segfault
   bad_argument

   > erase (sm,"b");  // erase "b"=>2, leaving i and j valid
   1

   > get_elm i; // still valid
   "a"=>1

   > erase (sm,"a");  // erase "a"=>1 - invalidating i
   1

   > catch id $ get_elm i; // bad iterator exception
   bad_argument


Functions
---------

In this section "acon" always denotes one of the containers that supports
interators (stlmap, stlset, stlmmap and stlmset).

.. function:: iterator /stlmap i

   Returns a new iterator that points to the same element as ``i``.

.. function:: begin /stlmap acon
              pastend /stlmap acon

   Returns ``acon``'s begin or past-end iterator.

.. function:: find /stlmap acon k
 
  Creates a new iterator that points to an element in ``acon`` with key
  equivalent to ``k`` (if any) or ``acon``'s past-end iterator if no such
  element exists. 

.. function:: find_with_default /stlmap map k

   Returns an iterator pointing to the element in ``map``, a stlmap, with key
   equivalent to ``k``. If no such element existed before the call, one is
   created and inserted using ``k`` and ``map``'s default value. This function
   is pure-stlmap's version of C++'s [] operator for associative containers.

.. function:: insert_elm /stlmap acon elm

  Attempts to insert ``elm`` into ``acon``. (If ``acon`` is a stlmap or
  stlmmap, then elm must be a key value pair, (k=>v)). If acon is a stlmap or
  stlset (i.e., with unique keys) :func:`insert_elm/stlmap` returns a pair,
  the first of which is an iterator pointing to the element with key k that
  was just inserted (or the pre-existing element that blocked the
  insertion). The second element in the pair is a boolean value that is true
  if a new element was inserted. In contrast, if ``acon`` is a multi-keyed
  container (stlmmap or stlmset) the insert will always be successful and
  :func:`insert_elm/stlmap` returns an iterator pointing to the element with
  key k that was just inserted, instead of an (iterator, boolean) tuple.

.. function:: insert_elm /stlmap acon (elm,i)

  This is the same as the previous function except that (a) ``i`` is passed in
  as a hint to where the new element should be inserted and (b) a single
  iterator is returned rather than a iterator,boolean pair. If the new element
  is inserted just after ``i``, the insertion can have constant time
  complexity.

.. function:: l_bound /stlmap acon k

  Return a new iterator that points to the first element in ``acon``, a
  stlmap, stlset, stlmmap or stlmset, that is not less than ``k``, or
  ``acon``'s past-end iterator if none exists.
 
.. function:: u_bound /stlmap acon k

  Return a new iterator that points to the first element in ``acon``, a
  stlmap, stlset, stlmmap or stlmset, that is greater than ``k``, or
  ``acon``'s past-end iterator if none exists.
 
.. function:: lu_bounds /stlmap acon k

  Return the pair l_bound ``acon`` ``k``, u_bound ``acon`` ``k``.

.. function range_info /stlmap rng

   Returns a tuple (ok, sac, first, last) where ok is true if ``rng`` is a
   valid range defined on a stlmap, stlset, stlmmap or stlmset, ac is the
   container that the range points into, and first and last are iterators that
   define the range. 

E.g., ::

   > let ok, smx, f, l = stl::range_info (sm1,"b","e");

   > ok, smx === sm1, stl::members (f,l);
   1,1,["b"=>2,"c"=>3,"d"=>4]

.. function:: inc /stlmap i
              dec /stlmap i
              move /stlmap i n::int
  
  Move the iterator ``i`` forward one, back one or forward ``n`` elements
  respectively, where n can be negative.  The iterator is mutated by these
  operations, provided the move is successful. An attempt to move to a
  position before the first element's position causes an :cons:`out_of_bounds`
  exception. Moves past the last element return the past-end iterator for the
  container that ``i`` is defined on.

.. function:: get_elm  /stlmap i
              get_key  /stlmap i
              get_val  /stlmap i

  Return the element pointed to by the iterator ``i``, or the element's key
  or value. For maps the element is returned as a key=>value hash rocket
  pair. For sets, get_elem, get_key and get_val all return the element (which
  is the same as its key).

.. function:: put_val i newvalue

  Change the value of the element pointed to by the iterator ``i`` to
  ``newvalue``. The element's key cannot be changed. The iterator must point
  into a stlmap or stlmmap.

.. function:: beginp /stlmap i
              pastendp /stlmap i

  Returns true if the iterator ``i`` is the begin iterator or pastend
  iterator of the container it is defined on.

.. function:: get_info /stlmap i

  Returns a tuple (is_valid,acon,key,val) where is_valid is true if the
  iterator ``i`` is valid or false if not, acon is the container that i is
  defined on, and key, val are the key and value of the element ``i`` points
  to, if any. If ``i`` is the past-end iterator, key and val are set to
  :cons:`stl::smend/stlmap` and ``[]``, respectively.

.. namespace:: ::

.. function:: infix == /stlmap i j
   
   Returns true if the iterators ``i`` and ``j`` point to the same element.

.. function:: erase /stlmap (acon,i)
              erase /stlmap (acon,i,j)

   Erases the element pointed to by ``i`` or the elements in the range
   (``i``, ``j``). Both ``i`` and ``j`` must be iterators defined on
   ``acon`` (or a :cons:`bad_argument` exception will be thrown).

Examples
--------

Here are some examples using iterators. ::

   > let b,e = begin smm, pastend smm;

   > members (b,e);
   ["a"=>1,"b"=>2,"c"=>31,"c"=>32,"d"=>4,"e"=>5]

   > let i,j = lu_bounds smm "c";

   > members (b,i);
   ["a"=>1,"b"=>2]

   > members (i,j);
   ["c"=>31,"c"=>32]

   > members (j,e);
   ["d"=>4,"e"=>5]

   > get_elm i;
   "c"=>31

   > get_elm (inc i);
   "c"=>32

   > put_val i 132;
   132

   > map (\(k=>_)->k=>ord k) (b,i);
   ["a"=>97,"b"=>98,"c"=>99]

   > let is_set, smm1, k, v = get_info i; is_set, members smm1, k, v;
   1,["a"=>1,"b"=>2,"c"=>31,"c"=>132,"d"=>4,"e"=>5],"c",132

   > get_elm (dec j);
   "c"=>132

   > inc j $$ inc j $$ get_elm j;
   "e"=>5

   > inc j $$ endp j;
   1

Backward Compatibilty
=====================

.. namespace:: ::

This section documents changes in pure-stlmap.

pure-stlmap-0.2
---------------

Optimized common predicates, such as (<) and (>)

pure-stlmap-0.3
---------------

Fixed (>) comparisons on plain old data.

