00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2005--2007 Petter Urkedal <urkedal@nbi.dk> 00003 * 00004 * This program is free software: you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation, either version 3 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 #ifndef CUEX_MONOID_H 00019 #define CUEX_MONOID_H 00020 00021 #include <cuex/fwd.h> 00022 #include <cuex/ltree.h> 00023 00024 CU_BEGIN_DECLARATIONS 00025 /** \defgroup cuex_monoid_h cuex/monoid.h: Monoid Operations 00026 ** @{ \ingroup cuex_mod 00027 ** 00028 ** This compound expression type aids in manipulating expressions of 00029 ** associative operators by keeping them in a canonical form. It implements a 00030 ** free monoid where the generators are arbitrary expressions. Further 00031 ** degeneracies, including handling of variables is left the client. 00032 **/ 00033 00034 typedef struct cuex_monoid *cuex_monoid_t; 00035 struct cuex_monoid 00036 { 00037 CUOO_HCOBJ 00038 cuex_meta_t opr; 00039 cuex_t ltree; 00040 }; 00041 00042 /** Special value for the end position of slicing operations to indicate 00043 ** slicing to the end. */ 00044 #define CUEX_MONOID_END CUEX_LTREE_END 00045 00046 extern cuoo_type_t cuexP_monoid_type; 00047 00048 /** The object type of elements of monoid compounds. */ 00049 CU_SINLINE cuoo_type_t 00050 cuex_monoid_type() 00051 { return cuexP_monoid_type; } 00052 00053 /** True iff \a t is the type of a monoid element. */ 00054 CU_SINLINE cu_bool_t 00055 cuex_is_monoid_type(cuex_t t) 00056 { return t == cuexP_monoid_type; } 00057 00058 /** True iff \a meta is the meta of a monoid element. */ 00059 CU_SINLINE cu_bool_t 00060 cuex_is_monoid_meta(cuex_meta_t meta) 00061 { return meta == cuoo_type_to_meta(cuexP_monoid_type); } 00062 00063 /** True iff a monoid under any operator contains \a x as a non-generator. 00064 ** \see cuex_check_monoid 00065 ** \see cuex_is_monoid_nongen */ 00066 CU_SINLINE cu_bool_t 00067 cuex_is_any_monoid_nongen(cuex_t x) 00068 { return cuex_meta(x) == cuoo_type_to_meta(cuex_monoid_type()); } 00069 00070 /** If \a x is a monoid (according to \ref cuex_is_monoid_nongen), then set 00071 ** <code>*\a mult_out</code> to the exact operator and return true, else 00072 ** return false. 00073 ** 00074 ** \see cuex_is_monoid_nongen 00075 ** \see cuex_is_any_monoid_nongen */ 00076 CU_SINLINE cu_bool_t 00077 cuex_check_monoid(cuex_t x, cuex_meta_t *mult_out) 00078 { 00079 if (cuex_is_any_monoid_nongen(x)) { 00080 *mult_out = ((cuex_monoid_t)x)->opr; 00081 return cu_true; 00082 } else 00083 return cu_false; 00084 } 00085 00086 /** Provided \a x is a monoid, returns it's operator. Do not call this without 00087 ** checking if \a x is a monoid. */ 00088 CU_SINLINE cuex_meta_t 00089 cuex_monoid_opr(cuex_t x) 00090 { return ((cuex_monoid_t)x)->opr; } 00091 00092 /** True iff \a x is a non-generator element of the monoid under \a mult. That 00093 ** is, if \a x is either the identity element or a composite element. 00094 ** 00095 ** \see cuex_is_monoid_nongen 00096 ** \see cuex_check_monoid */ 00097 CU_SINLINE cu_bool_t 00098 cuex_is_monoid_nongen(cuex_meta_t mult, cuex_t x) 00099 { return cuex_is_any_monoid_nongen(x) && ((cuex_monoid_t)x)->opr == mult; } 00100 00101 /** True iff \a x is the identity element of the monoid under \a mult. */ 00102 CU_SINLINE cu_bool_t 00103 cuex_is_monoid_identity(cuex_meta_t mult, cuex_t x) 00104 { 00105 return cuex_is_monoid_nongen(mult, x) 00106 && cuex_ltree_is_empty(((cuex_monoid_t)x)->ltree); 00107 } 00108 00109 /** True iff \a x is a composite element of the monoid under \A{mult}. */ 00110 CU_SINLINE cu_bool_t 00111 cuex_is_monoid_composite(cuex_meta_t mult, cuex_t x) 00112 { return cuex_is_monoid_nongen(mult, x) 00113 && !cuex_ltree_is_empty(((cuex_monoid_t)x)->ltree); } 00114 00115 /** The identity element of the monoid induced by \a mult. This is the same 00116 ** for both unnested or nested cases.*/ 00117 cuex_t cuex_monoid_identity(cuex_meta_t mult); 00118 00119 /** Returns the \A{mult}-product of factors drawn from \a source in order. */ 00120 cuex_t cuex_monoid_from_source(cuex_meta_t mult, cu_ptr_source_t source); 00121 00122 /** Returns a \a mult monoid element of \a factor_count factors from the array 00123 ** \a factor_arr. */ 00124 cuex_t cuex_monoid_from_array(cuex_meta_t mult, 00125 cuex_t *factor_arr, size_t factor_count); 00126 00127 /** Returns \a x * \a y, where * = \a mult. */ 00128 cuex_t cuex_monoid_product(cuex_meta_t mult, cuex_t x, cuex_t y); 00129 00130 /** Returns \a x * \a y, where * = \a mult and \a y is treated as a single 00131 ** factor. If \a y is itself a monoid, the result is a nested monoid. */ 00132 cuex_t cuex_monoid_rightmult(cuex_meta_t mult, cuex_t x, cuex_t y); 00133 00134 /** The result of repeated application of \ref cuex_monoid_rightmult, starting 00135 ** with \a x, for each expression drawn from \a source as the last 00136 ** argument. */ 00137 cuex_t cuex_monoid_rightmult_source(cuex_meta_t mult, cuex_t x, 00138 cu_ptr_source_t source); 00139 00140 /** The result of repeated application of \ref cuex_monoid_rightmult, starting 00141 ** with \a x, for of the \a count expressions of the \a array as the last 00142 ** argument. */ 00143 cuex_t cuex_monoid_rightmult_array(cuex_meta_t mult, cuex_t x, 00144 cuex_t *array, size_t count); 00145 00146 /** The number of factors in the factorisation of \a x with respect to 00147 ** \a mult. */ 00148 size_t cuex_monoid_length(cuex_meta_t mult, cuex_t x); 00149 00150 /** Factor number \a i (counting from 0) of the factorisation of \a x with 00151 ** respect to \a mult. If \a i is negative it's taken to be relative to just 00152 ** past the last factor of \a x. 00153 ** 00154 ** \pre \e N ≤ \a i < \e N where \e N = \ref cuex_monoid_length(\a mult, \a x) 00155 **/ 00156 cuex_t cuex_monoid_factor_at(cuex_meta_t mult, cuex_t x, ptrdiff_t i); 00157 00158 /** The monoid of factors \a i inclusive to \a j exclusive of the factorisation 00159 ** of \a x, considering the operator \a mult. 00160 ** 00161 ** \pre \a i ≤ \a j ≤ \ref cuex_monoid_length(\a mult, \a x) */ 00162 cuex_t cuex_monoid_factor_slice(cuex_meta_t mult, cuex_t x, 00163 ptrdiff_t i, ptrdiff_t j); 00164 00165 /** Returns a source which provides the factors \a i inclusive to \a j 00166 ** exclusive in the factorisation of \a x with respect to \a mult. */ 00167 cu_ptr_source_t cuex_any_monoid_factor_source(cuex_t e, 00168 ptrdiff_t i, ptrdiff_t j); 00169 00170 struct cuex_monoid_itr { struct cuex_ltree_itr sub; }; 00171 typedef struct cuex_monoid_itr cuex_monoid_itr_t; 00172 00173 /** Initialises \a itr for iterating over all \A{mult}-factors of \a x. */ 00174 void cuex_monoid_itr_init_full(cuex_meta_t mult, 00175 cuex_monoid_itr_t *itr, cuex_t x); 00176 00177 /** Initialises \a itr for iterating over \A{mult}-factors starting with number 00178 ** \a i and stopping at number \a j. */ 00179 void cuex_monoid_itr_init_slice(cuex_meta_t mult, 00180 cuex_monoid_itr_t *itr, cuex_t x, 00181 ptrdiff_t i, ptrdiff_t j); 00182 00183 /** Pops the next expression off \a itr or returns \c NULL if \a itr is 00184 ** empty. */ 00185 CU_SINLINE cuex_t cuex_monoid_itr_get(cuex_monoid_itr_t *itr) 00186 { return cuex_ltree_itr_get(&itr->sub); } 00187 00188 /** Checks if \a itr is empty without altering it. */ 00189 CU_SINLINE cu_bool_t cuex_monoid_itr_is_end(cuex_monoid_itr_t *itr) 00190 { return cuex_ltree_itr_is_end(&itr->sub); } 00191 00192 /** @} */ 00193 CU_END_DECLARATIONS 00194 00195 #endif