00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 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_COMPOUND_H 00019 #define CUEX_COMPOUND_H 00020 00021 #include <cuoo/type.h> 00022 #include <cuex/fwd.h> 00023 #include <cuex/intf.h> 00024 #include <cu/clos.h> 00025 00026 CU_BEGIN_DECLARATIONS 00027 /*!\defgroup cuex_compound_h cuex/compound.h: Compound Expressions 00028 *@{\ingroup cuex_mod 00029 * 00030 * Compound expressions, or compounds for short, are containers of expressions 00031 * (dynamic objects and operations). 00032 * Compounds are also themselves expressions. 00033 * One thing you can do an compounds without knowing more about their structure 00034 * is to iterate over their subexpressions. 00035 * Further, compounds may support creation of their image under a function or 00036 * iterable construction. 00037 * 00038 * The following terminology will reflect that compounds are geared towards 00039 * representing associative binary operations, though it is just as useful for 00040 * containers. 00041 * We distinguish between non-commutative and commutative views. A compound 00042 * may bind one or both views. 00043 * For example, a map may be an commutative compound of key-value pairs, or a 00044 * non-commutative compound of just the values where the keys are treated 00045 * inertly. 00046 * Conversely, a vector may have a commutative iterator where the values are 00047 * index-value pairs. 00048 */ 00049 00050 typedef struct cuex_intf_compound *cuex_intf_compound_t; 00051 00052 /*!Set if the non-commutative interface is preferable when an algorithm 00053 * supports both. 00054 * This flag \e must be set if the commutative interface is unbound. */ 00055 #define CUEX_COMPOUNDFLAG_PREFER_NCOMM 1 00056 00057 /*!Set if the commutative interface is preferable when an algorithm supports 00058 * both. 00059 * This flag \e must be set if the non-commutative interface is unbound. */ 00060 #define CUEX_COMPOUNDFLAG_PREFER_COMM 2 00061 00062 /*!Set iff successive elements which are equal reduces to a single occurrence 00063 * for the non-commutative interface. */ 00064 #define CUEX_COMPOUNDFLAG_NCOMM_IDEMPOTENT 4 00065 00066 /*!Set iff equal elements reduces to a single occurrence for the commutative 00067 * interface. */ 00068 #define CUEX_COMPOUNDFLAG_COMM_IDEMPOTENT 8 00069 00070 /*!Set iff \ref cuex_intf_compound::ncomm_image_junctor allows dropping 00071 * elements by omitting some calls to \ref cu_ptr_junction_put. */ 00072 #define CUEX_COMPOUNDFLAG_NCOMM_FILTERABLE_IMAGE 16 00073 00074 /*!Set iff \ref cuex_intf_compound::comm_image_junctor allows dropping 00075 * elements by omitting some calls to \ref cu_ptr_junction_put. */ 00076 #define CUEX_COMPOUNDFLAG_COMM_FILTERABLE_IMAGE 32 00077 00078 /*!Set iff \ref cuex_intf_compound::ncomm_image_junctor allows adding extra 00079 * elements by calling \ref cu_ptr_junction_put more than once after a call to 00080 * \ref cu_ptr_junction_get. */ 00081 #define CUEX_COMPOUNDFLAG_NCOMM_EXPANSIVE_IMAGE 64 00082 00083 /*!Set iff \ref cuex_intf_compound::comm_image_junctor allows adding extra 00084 * elements by calling \ref cu_ptr_junction_put more than once after a call to 00085 * \ref cu_ptr_junction_get. */ 00086 #define CUEX_COMPOUNDFLAG_COMM_EXPANSIVE_IMAGE 128 00087 00088 /*!Interface for compound expressions. 00089 * This struct is meant to be declared with static storage and initialised 00090 * using C99 struct member designators and must have static storage so that any 00091 * future added fields become \c NULL. 00092 * An alternative to using member designators is to provide an initialisation 00093 * function. 00094 * In any case, \ref cuex_intf_compound_finish must be called on the interface 00095 * at some point before the first time it is returned by an interface 00096 * dispatcher, so that the implied fields can be computed. 00097 * Some valid assignments for the most important members are, 00098 * 00099 * <table class="normal"> 00100 * <tr><th>assigned</th><th>synthesised</th><th>comment</th></tr> 00101 * <tr> 00102 * <td>\ref ncomm_iter_source, \ref ncomm_image_junctor</td> 00103 * <td>\ref comm_iter_source, \ref comm_image_junctor</td> 00104 * <td>A non-commutative compound with an implied commutative view.</td> 00105 * </tr> 00106 * <tr> 00107 * <td>\ref comm_iter_source, \ref comm_image_junctor</td> 00108 * <td></td> 00109 * <td>A purely commutative compound with limited construction.</td> 00110 * </tr> 00111 * <tr> 00112 * <td>\ref comm_iter_source, \ref comm_build_sinktor</td> 00113 * <td>\ref comm_image_junctor (or explicit)</td> 00114 * <td>A purely commutative compound with full construction.</td> 00115 * </tr> 00116 * <tr> 00117 * <td>\ref ncomm_iter_source, \ref ncomm_image_junctor<br> 00118 * \ref comm_iter_source, \ref comm_image_junctor</td> 00119 * <td></td> 00120 * <td>A compound with explicit non-commutative and commutative views.</td> 00121 * </tr> 00122 * <tr> 00123 * <td>\ref ncomm_iter_source, \ref ncomm_image_junctor<br> 00124 * \ref comm_iter_source, \ref comm_build_sinktor</td> 00125 * <td>\ref comm_image_junctor (or explicit)</td> 00126 * <td>A compound with explicit non-commutative and commutative views, 00127 * where the commutative view has full construction.</td> 00128 * </tr> 00129 * </table> 00130 * 00131 * The \ref comm_union_sinktor may optionally be assigned whenever \ref 00132 * comm_build_sinktor is defined. 00133 */ 00134 struct cuex_intf_compound 00135 { 00136 unsigned int flags; 00137 00138 /*!Source sequence of elements for the non-commutative view. This can be 00139 * left unassigned for purely commutative compounds. It will not be 00140 * synthesised. */ 00141 cu_ptr_source_t (*ncomm_iter_source)(cuex_intf_compound_t, cuex_t C); 00142 00143 /*!Shall return a \ref cu_ptr_seq_h "junctor" which allows the construction 00144 * of an image of \a C. The elements must have the same order as that 00145 * returned by \ref ncomm_iter_source. This may be left unassigned, in 00146 * which case it will be synthesised if \ref ncomm_build_sinktor is 00147 * defined. If assigned, then \ref ncomm_iter_source must also be 00148 * assigned. */ 00149 cu_ptr_junctor_t (*ncomm_image_junctor)(cuex_intf_compound_t, cuex_t C); 00150 00151 /*!Shall return a \ref cu_ptr_seq_h "sinktor" to construct a container from 00152 * scratch using the non-commutative view. */ 00153 cu_ptr_sinktor_t (*ncomm_build_sinktor)(cuex_intf_compound_t, cuex_t C); 00154 00155 /*!Source sequence of elements for the commutative view. If not assigned, 00156 * it will be synthesised from \ref ncomm_iter_source. */ 00157 cu_ptr_source_t (*comm_iter_source)(cuex_intf_compound_t, cuex_t C); 00158 00159 /*!Shall return a \ref cu_ptr_seq_h "junctor" which allows the construction 00160 * of an image of \a C. The element order must be the same as that of \ref 00161 * comm_iter_source. This can be synthesised from \ref comm_iter_source 00162 * and \ref comm_build_sinktor. Otherwise, if \ref comm_iter_source is 00163 * synthetic, then it can also be synthesised from \ref 00164 * ncomm_image_junctor. Otherwise, no construction is allowed on this 00165 * compound. */ 00166 cu_ptr_junctor_t (*comm_image_junctor)(cuex_intf_compound_t, cuex_t C); 00167 00168 /*!Shall return a \ref cu_ptr_seq_h "sinktor" which allows the construction 00169 * of a container from scratch, using \a C as a template for any additional 00170 * properties. */ 00171 cu_ptr_sinktor_t (*comm_build_sinktor)(cuex_intf_compound_t, cuex_t C); 00172 00173 /*!Shall return a \ref cu_ptr_seq_h "sinktor" which allows the construction 00174 * of a copy of \a C with additional elements put into the sink. */ 00175 cu_ptr_sinktor_t (*comm_union_sinktor)(cuex_intf_compound_t, cuex_t C); 00176 00177 /*!Shall return the number of elements. This must correspond to the number 00178 * of elements provided by \ref ncomm_iter_source and \ref 00179 * comm_iter_source. If not defined, it will be synthesised from \ref 00180 * comm_iter_source or \ref ncomm_iter_source. */ 00181 size_t (*size)(cuex_intf_compound_t, cuex_t C); 00182 00183 #if 0 00184 cuex_t (*comm_find)(cuex_intf_compound_t, cuex_t C, cuex_t key); 00185 #endif 00186 }; 00187 00188 /*!Returns the compound implementation of \a type, or \c NULL if not 00189 * implemented for this type. */ 00190 CU_SINLINE cuex_intf_compound_t cuex_type_compound(cuoo_type_t type) 00191 { return (cuex_intf_compound_t)cuoo_type_impl_ptr(type, CUEX_INTF_COMPOUND); } 00192 00193 /*!Verifies that \a impl has been correctly initialised, and may synthesise 00194 * some missing fields as indicated in \ref cuex_intf_compound. */ 00195 void cuex_intf_compound_finish(cuex_intf_compound_t impl); 00196 00197 /*!Returns the number of elements in \a C. */ 00198 CU_SINLINE size_t 00199 cuex_compound_size(cuex_intf_compound_t impl, cuex_t C) 00200 { return impl->size(impl, C); } 00201 00202 /*!Returns a source for iterating through \a C using either non-commutative or 00203 * commutative view as preferred by the compound. */ 00204 cu_ptr_source_t 00205 cuex_compound_pref_iter_source(cuex_intf_compound_t impl, cuex_t C); 00206 00207 /*!Returns a source for iterating through \a C using the commutative view. */ 00208 CU_SINLINE cu_ptr_source_t 00209 cuex_compound_comm_iter_source(cuex_intf_compound_t impl, cuex_t C) 00210 { return impl->comm_iter_source(impl, C); } 00211 00212 /*!Returns a junctor for constructing an image of \a C using either 00213 * non-commutative or commutative view as preferred by the compound. */ 00214 cu_ptr_junctor_t 00215 cuex_compound_pref_image_junctor(cuex_intf_compound_t impl, cuex_t C); 00216 00217 /*!Returns a junctor for constructing an image of \a C using the commutative 00218 * view. */ 00219 CU_SINLINE cu_ptr_junctor_t 00220 cuex_compound_comm_image_junctor(cuex_intf_compound_t impl, cuex_t C) 00221 { return impl->comm_image_junctor(impl, C); } 00222 00223 #if 0 00224 cu_bool_t cuex_compound_conj(cuex_intf_compound_t impl, cuex_t C, 00225 cu_clop(f, cu_bool_t, cuex_t)); 00226 00227 cuex_t cuex_compound_image(cuex_intf_compound_t impl, cuex_t C, 00228 cu_clop(f, cuex_t, cuex_t)); 00229 #endif 00230 00231 /*!Returns an ordered sequence over immediate subexpressions of \a e. For 00232 * operations, yields the opreands in order (as returned by \ref cuex_opn_at). 00233 * For compounds, returns the non-commutative source of the compound, or \c 00234 * NULL if the compound only has a commutative view. Returns the empty 00235 * interator for atomic expressions. */ 00236 cu_ptr_source_t cuex_ncomm_source(cuex_t e); 00237 00238 /*!Returns an unordered sequence over immediate subexpressions of \a e. For 00239 * operations, a sequence of cuex_o2_metapair are returned, where the first 00240 * operand is an cudyn_int of the position, and the second is the original 00241 * operand. For compounds, the (possibly synthesised) commutative view is 00242 * returned. Returns the empty iterator for atomic expressions. */ 00243 cu_ptr_source_t cuex_comm_source(cuex_t e); 00244 00245 /*!Returns a sequence over \a e, using the preferred iteration source. For 00246 * operations, the operands are returned in order, as with \ref 00247 * cuex_ncomm_source. For compounds, \ref cuex_compound_pref_iter_source is 00248 * used. Returns the empty iterator for atomic expressions. */ 00249 cu_ptr_source_t cuex_pref_source(cuex_t e); 00250 00251 /*!@}*/ 00252 CU_END_DECLARATIONS 00253 00254 #endif