
/* records.pure: A simple record data structure. */

/* Copyright (c) 2009-2012 by Albert Graef <Dr.Graef@t-online.de>.

   This file is part of the Pure standard library.

   The Pure standard library is free software: you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public License as
   published by the Free Software Foundation, either version 3 of the License,
   or (at your option) any later version.

   Pure 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.  See the GNU Lesser General Public License for
   more details.

   You should have received a copy of the GNU Lesser General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

/* .. _Record Functions:

   Record Functions
   ----------------

   As of Pure 0.41, the prelude also provides a basic record data structure,
   implemented as symbolic vectors of ``key=>value`` pairs which support a few
   dictionary-like operations such as :func:`member/record`,
   :func:`insert/record` and indexing.  Records may be represented as row,
   column or empty vectors (i.e., the number of rows or columns must be zero
   or one). They must be symbolic matrices consisting only of "hash pairs"
   ``key=>value``, where the keys can be either symbols or strings. The values
   can be any kind of Pure data; in particular, they may themselves be
   records, so records can be nested.

   The following operations are provided. Please note that all updates of
   record members are non-destructive and thus involve copying, which takes
   linear time (and space) and thus might be slow for large record values; if
   this is a problem then you should use dictionaries instead
   (cf. Dictionaries_). Or you can create mutable records by using expression
   references (cf. `Expression References`_) as values, which allow you to
   modify the data in-place. Element lookup (indexing) uses binary search on
   an internal index data structure and thus takes logarithmic time once the
   index has been constructed (which is done automatically when needed, or
   when calling ``recordp`` on a fresh record value).

   Also note that records with duplicate keys are permitted; in such a case
   the following operations will always operate on the *last* entry for a
   given key.

   .. type:: record /type

      The record type. This is functionally equivalent to :func:`recordp`, but
      can be used as a type tag on the left-hand side of equations.

   .. function:: recordp x

      Check for record values.

   .. function:: record x

      Normalizes a record. This removes duplicate keys and orders the record
      by keys (using an apparently random but well-defined order of the key
      values), so that normalized records are syntactically equal
      (:func:`===`) if and only if they contain the same hash pairs. For
      convenience, this function can also be used directly on lists and tuples
      of hash pairs to convert them to a normalized record value.

   .. function:: prefix # /record x

      The size of a record (number of entries it contains). Duplicate entries
      are counted. (This is in fact just the standard matrix size operation.)

   .. function:: member /record x y

      Check whether ``x`` contains the key ``y``.

   .. function:: infix ! /record x y

      Retrieves the (last) value associated with the key ``y`` in ``x``, if
      any, otherwise throws an :cons:`out_of_bound` exception.

   .. function:: infix !! /record x ys

      Slicing also works as expected, by virtue of the generic definition of
      slicing provided by the matrix data structure.

   .. function:: insert /record x (y=>z)
                 update /record x y z

      Associate the key ``y`` with the value ``z`` in ``x``. If ``x`` already
      contains the key ``y`` then the corresponding value is updated (the last
      such value if ``x`` contains more than one association for ``y``),
      otherwise a new member is inserted at the end of the record.

   .. function:: delete /record x y

      Delete the key ``y`` (and its associated value) from ``x``. If ``x``
      contains more than one entry for ``y`` then the last such entry is
      removed.

   .. function:: keys /record x
                 vals /record x

      List the keys and associated values of ``x``. If the record contains
      duplicate keys, they are all listed in the order in which they are
      stored in the record.

   Here are a few basic examples::

     > let r = {x=>5, y=>12};
     > r!y; r!![y,x];              // indexing and slicing
     12
     {12,5}
     > keys r; vals r;             // keys and values of a record
     {x,y}
     {5,12}
     > insert r (x=>99);           // update an existing entry
     {x=>99,y=>12}
     > insert ans (z=>77);         // add a new entry
     {x=>99,y=>12,z=>77}
     > delete ans z;               // delete an existing entry
     {x=>99,y=>12}
     > let r = {r,x=>7,z=>3}; r;   // duplicate key x
     {x=>5,y=>12,x=>7,z=>3}
     > r!x, r!z;                   // indexing returns the last value of x
     7,3
     > delete r x;                 // delete removes the last entry for x
     {x=>5,y=>12,z=>3}
     > record r;                   // normalize (remove dups and sort)
     {x=>7,y=>12,z=>3}
     > record [x=>5, x=>7, y=>12]; // construct a normalized record from a list
     {x=>7,y=>12}
     > record (x=>5, x=>7, y=>12); // ... or a tuple
     {x=>7,y=>12}

   More examples can be found in the :ref:`Record Data` section in the Pure
   Manual. */

/* These are implemented in the runtime for better performance. */

namespace __C;
extern bool record_check(expr *x);
extern bool record_member(expr *x, expr *y);
extern expr* record_elem_at(expr *x, expr *y);
extern expr* record_update(expr *x, expr *y, expr *z);
extern expr* record_delete(expr *x, expr *y);
extern expr* record_pack(expr *x);
record_elem_at x y = throw out_of_bounds;
namespace;

/* Type check. */

recordp x = __C::record_check x;

/* Convenience type. */

type record = recordp;

/* Normalization and conversions. */

record x = __C::record_pack x if recordp x;
       	 = record x if recordp x when x = matrix x end;

/* Membership test, indexing and non-destructive updates. */

member x::matrix y	= __C::record_member x y if recordp x;
x::matrix!y		= __C::record_elem_at x y if recordp x;
insert x::matrix (y=>z)	= __C::record_update x y z if recordp x;
update x::matrix y z	= __C::record_update x y z if recordp x;
delete x::matrix y	= __C::record_delete x y if recordp x;

/* Keys and values of a record. */

keys x::matrix		= {u | u=>v = x} if recordp x;
vals x::matrix		= {v | u=>v = x} if recordp x;
