.. include:: ../global.rst

.. _`sorting`:

Sorting
^^^^^^^

These sorting functions are a port of SRFI-95_ and, generally the
functions take a sequence (a list or an array), a function that can
determine a "less than" comparison between two values and an optional
*accessor* function.

The *accessor* function allows you to indirect through another data
structure and have the comparison function sort the value returned by
the accessor rather than the original datum.  Sorting by proxy, if you
will.

For example, suppose you want to sort a list of file names by the size
of each file:

#. :ref:`stat <libc/stat>` all the files and put the results in a hash
   table indexed by file name

   You could put the entire :ref:`struct-stat <libc/struct-stat>`
   struct in the hash table or just the ``st_size`` member depending
   on what you want your accessor function to do.

#. create a named, or anonymous, accessor function that, given a file
   name, retrieves the corresponding ``st_size`` member from the hash
   table

#. the ``st_size`` member is a :lname:`C` type so we can use
   :ref:`C/\< <C/\<>` as the "less than" comparison function

#. call :ref:`sort <sort>` with the list of file names, ``C/<`` and
   your accessor function

Obviously, you call :ref:`reverse <reverse>` if you want the file
names sorted in the opposite order.

Functions for sorting file names by ``st_atime``, ``st_ctime``,
``st_atime`` and ``st_size`` are below.


.. _`sorted?`:

.. idio:function:: sorted? seq less? [opt-key]


   
   Is sequence `seq` sorted?
   
   :param seq: sequence to be verified as sorted
   :type seq: list or array
   :param less?: 2-ary function that computes *less than*
   :type less?: function
   :param opt-key: accessor function, defaults to :ref:`identity <identity>`
   :type opt-key: function, optional
   
   For a list ``(x0 x1 ... xm)``, ``sorted?`` returns `true` when for all
   1 <= i <= m:
   
       :samp:`(not ({less?} (list-ref list {i}) (list-ref list (- {i} 1))))`
   


.. _`sort`:

.. idio:function:: sort seq less? [opt-key]


   
   sort the sequence `seq` using comparitor `less?`
   
   :param seq: sequence
   :type seq: list or array
   :param less?: 2-ary function that computes *less than*
   :type less?: function
   :param opt-key: accessor function, defaults to :ref:`identity <identity>`
   :type opt-key: function, optional
   


.. _`sort!`:

.. idio:function:: sort! seq less? [opt-key]


   
   destructively sort the sequence `seq` using comparitor `less?`
   
   :param seq: sequence
   :type seq: list or array
   :param less?: 2-ary function that computes *less than*
   :type less?: function
   :param opt-key: accessor function, defaults to :ref:`identity <identity>`
   :type opt-key: function, optional
   


.. _`merge`:

.. idio:function:: merge a b less? [opt-key]


   
   merge pre-sorted lists `a` and `b`
   
   :param a: sorted list
   :type a: list
   :param b: sorted list
   :type b: list
   :param less?: 2-ary function that computes *less than*
   :type less?: function
   :param opt-key: accessor function, defaults to :ref:`identity <identity>`
   :type opt-key: function, optional
   
   returns a new list in which the elements of a and b have been stably
   interleaved so that :samp:`(sorted? (merge {a} {b} {less?}) {less?})`
   is `true`.
   


.. _`merge!`:

.. idio:function:: merge! a b less? [opt-key]


   
   a destructive merge of pre-sorted lists `a` and `b`
   
   :param a: sorted list
   :type a: list
   :param b: sorted list
   :type b: list
   :param less?: 2-ary function that computes *less than*
   :type less?: function
   :param opt-key: accessor function, defaults to :ref:`identity <identity>`
   :type opt-key: function, optional
   


.. _`sort-atime`:

.. idio:function:: sort-atime l


   
   sort the filenames in `l` by file access time
   
   :param l: filenames
   :type l: list
     


.. _`sort-ctime`:

.. idio:function:: sort-ctime l


   
   sort sort filenames in `l` by file creation time
   
   :param l: filenames
   :type l: list
     


.. _`sort-mtime`:

.. idio:function:: sort-mtime l


   
   sort the filenames in `l` by file modification time
   
   :param l: filenames
   :type l: list
     


.. _`sort-size`:

.. idio:function:: sort-size l


   
   sort the filenames in `l` by file size
   
   :param l: filenames
   :type l: list
     


.. _`sort-string`:

.. idio:function:: sort-string seq


   
   sort the strings `seq` using comparitor :ref:`string\<? <string\<?>`
   
   :param seq: sequence of strings
   :type seq: list
   


.. _`sort-symbol`:

.. idio:function:: sort-symbol seq


   
   sort the symbols `seq`
   
   :param seq: sequence of symbols
   :type seq: list
   
   :Example:
   
   .. code-block:: idio
   
      sort-symbol (module-exports libc)
   




.. include:: ../commit.rst