cuex/tmonoid.h

/* Part of the culibs project, <http://www.eideticdew.org/culibs/>.
 * Copyright (C) 2009  Petter Urkedal <urkedal@nbi.dk>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef CUEX_TAGMONOID_H
#define CUEX_TAGMONOID_H

#include <cuex/fwd.h>
#include <cuex/ltree.h>

CU_BEGIN_DECLARATIONS
/** \defgroup cuex_tmonoid_h cuex/tmonoid.h: Monoid Operations with Tagged Generators
 ** @{ \ingroup cuex_mod
 **
 ** This compound expression type aids the manipulation of expressions
 ** representing monoids.  It implement a free monoid under a chosen operator
 ** and generated by expressions which are explicitly tagged with the monoid
 ** operator.
 **
 ** Compared to \ref cuex_monoid_h "cuex/monoid.h", tagging the generators
 ** makes this variant suitable for dealing with nested elements of the same
 ** monoid, where the tag protects against the associativity.  In other words,
 ** it can serve as tuples of arbitrary arity (including 0 and 1) with tuple
 ** concatenation as the monoid operator.
 **
 ** The main advantage over an array-like implementation is \e O(log \e n)
 ** complexity for \ref cuex_tmonoid_rightmult (single-element append).
 **
 ** \see cuex_monoid_h
 ** \see cuex_tuple_h
 **/

typedef struct cuex_tmonoid *cuex_tmonoid_t;
struct cuex_tmonoid
{
    CUOO_HCOBJ
    cuex_meta_t opr;
    cuex_t ltree;
};

/** Special value for the upper bound in slicing operations to indicate slicing
 ** to the end. */
#define CUEX_TMONOID_END CUEX_LTREE_END

extern cuoo_type_t cuexP_tmonoid_type;

/** The object type of the members of tagged monoids. */
CU_SINLINE cuoo_type_t
cuex_tmonoid_type()
{ return cuexP_tmonoid_type; }

/** True iff \a t is the type of a tagged monoid element. */
CU_SINLINE cu_bool_t
cuex_is_tmonoid_type(cuex_t t)
{ return t == cuexP_tmonoid_type; }

/** True iff \a meta is the meta of a tagged monoid element. */
CU_SINLINE cu_bool_t
cuex_is_tmonoid_meta(cuex_meta_t meta)
{ return meta == cuoo_type_to_meta(cuexP_tmonoid_type); }

/** True iff \a x is an element of some tagged monoid. */
CU_SINLINE cu_bool_t
cuex_any_tmonoid_contains(cuex_t x)
{ return cuex_meta(x) == cuoo_type_to_meta(cuex_tmonoid_type()); }

/** The operator of \a x, which must be an element of a tagged monoid. */
CU_SINLINE cuex_meta_t
cuex_tmonoid_opr(cuex_t x)
{ return ((cuex_tmonoid_t)x)->opr; }

/** True iff \a x is an element of the tagged monoid under \a mult. */
CU_SINLINE cu_bool_t
cuex_tmonoid_contains(cuex_meta_t mult, cuex_t x)
{ return cuex_any_tmonoid_contains(x) && ((cuex_tmonoid_t)x)->opr == mult; }

/** True iff \a x is the identity element of some tagged monoid. */
CU_SINLINE cu_bool_t
cuex_tmonoid_is_identity(cuex_t x)
{ return cuex_ltree_is_empty(((cuex_tmonoid_t)x)->ltree); }

/** True iff \a x is a generator for some tagged monoid. */
CU_SINLINE cu_bool_t
cuex_tmonoid_is_generator(cuex_t x)
{ return cuex_ltree_is_singleton(((cuex_tmonoid_t)x)->ltree); }

/** True iff \a x is a composite (not identity or generator) element of some
 ** tagged monoid. */
CU_SINLINE cu_bool_t
cuex_tmonoid_is_composite(cuex_t x)
{ return cuex_ltree_is_composite(((cuex_tmonoid_t)x)->ltree); }

/** The identity element of the tagged monoid under \a mult. */
cuex_t cuex_tmonoid_identity(cuex_meta_t mult);

/** Creates a generator for the monoid under \a mult. */
cuex_t cuex_tmonoid_generator(cuex_meta_t mult, cuex_t x);

cuex_t cuex_tmonoid_from_valist(cuex_meta_t mult, va_list vl);

cuex_t cuex_tmonoid_from_args(cuex_meta_t mult, ...);

/** Returns a tagged monoid under \a mult with untagged factors drawn from \a
 ** src in order. */
cuex_t cuex_tmonoid_from_source(cuex_meta_t mult, cu_ptr_source_t src);

/** Returns a tagged monoid under \a mult with untagged factors from the array
 ** \a factor_arr of \a factor_count elements. */
cuex_t cuex_tmonoid_from_array(cuex_meta_t mult,
                               cuex_t *factor_arr, size_t factor_count);

/** Returns \a x * \a y where * = \a mult where \a x and \a y must be members
 ** of the tagged monoid under \a mult. */
cuex_t cuex_tmonoid_product(cuex_meta_t mult, cuex_t x, cuex_t y);

/** Like \ref cuex_tmonoid_product but only checks that \a x and \a y have the
 ** same operator instead of an explicitly given one. */
cuex_t cuex_any_tmonoid_product(cuex_t x, cuex_t y);

/** Returns \a x * \a y where * = \a mult where \a x must be a tagged monoid
 ** under \a mult and \a y is treated as a single untagged factor. */
cuex_t cuex_tmonoid_rightmult(cuex_meta_t mult, cuex_t x, cuex_t y);

/** Like \ref cuex_tmonoid_rightmult, but don't check the operator. */
cuex_t cuex_any_tmonoid_rightmult(cuex_t x, cuex_t y);

/** The result of repeated application of \ref cuex_tmonoid_rightmult for each
 ** element of \a source as its second argument. */
cuex_t cuex_tmonoid_rightmult_source(cuex_meta_t mult, cuex_t x,
                                     cu_ptr_source_t source);

/** Like \ref cuex_tmonoid_rightmult_source, but don't check the operator. */
cuex_t cuex_any_tmonoid_rightmult_source(cuex_t x, cu_ptr_source_t source);

/** The result of repeated application of \ref cuex_tmonoid_rightmult for each
 ** element of the \a count elements of the array \a array. */
cuex_t cuex_tmonoid_rightmult_array(cuex_meta_t mult, cuex_t x,
                                    cuex_t *array, size_t count);

/** Like \ref cuex_tmonoid_rightmult_array, but don't check the operator. */
cuex_t cuex_any_tmonoid_rightmult_array(cuex_t x, cuex_t *array, size_t count);

size_t cuex_tmonoid_length(cuex_meta_t mult, cuex_t x);

size_t cuex_any_tmonoid_length(cuex_t x);

cuex_t cuex_tmonoid_factor_at(cuex_meta_t mult, cuex_t x, ptrdiff_t i);

cuex_t cuex_any_tmonoid_factor_at(cuex_t x, ptrdiff_t i);

cuex_t cuex_tmonoid_factor_slice(cuex_meta_t mult, cuex_t x,
                                 ptrdiff_t i, ptrdiff_t j);

cuex_t cuex_any_tmonoid_factor_slice(cuex_t x, ptrdiff_t i, ptrdiff_t j);

cu_ptr_source_t cuex_tmonoid_factor_source(cuex_meta_t mult, cuex_t x,
                                           ptrdiff_t i, ptrdiff_t j);

cu_ptr_source_t cuex_any_tmonoid_factor_source(cuex_t x,
                                               ptrdiff_t i, ptrdiff_t j);

struct cuex_tmonoid_itr { struct cuex_ltree_itr sub; };
typedef struct cuex_tmonoid_itr cuex_tmonoid_itr_t;

void cuex_tmonoid_itr_init_full(cuex_meta_t mult, cuex_tmonoid_itr_t *itr,
                                cuex_t x);

void cuex_any_tmonoid_itr_init_full(cuex_tmonoid_itr_t *itr, cuex_t x);

void cuex_tmonoid_itr_init_slice(cuex_meta_t mult, cuex_tmonoid_itr_t *itr,
                                 cuex_t x, ptrdiff_t i, ptrdiff_t j);

void cuex_any_tmonoid_itr_init_slice(cuex_tmonoid_itr_t *itr,
                                     cuex_t x, ptrdiff_t i, ptrdiff_t j);

CU_SINLINE cuex_t cuex_tmonoid_itr_get(cuex_tmonoid_itr_t *itr)
{ return cuex_ltree_itr_get(&itr->sub); }

CU_SINLINE cu_bool_t cuex_tmonoid_itr_is_end(cuex_tmonoid_itr_t *itr)
{ return cuex_ltree_itr_is_end(&itr->sub); }

/** @} */
CU_END_DECLARATIONS

#endif