00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2009 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_ITERATION_H 00019 #define CUEX_ITERATION_H 00020 00021 #include <cuex/fwd.h> 00022 #include <cu/clos.h> 00023 00024 CU_BEGIN_DECLARATIONS 00025 /** \defgroup cuex_iteration_h cuex/iteration.h: Iteration over Subterms 00026 ** @{ \ingroup cuex_mod 00027 ** 00028 ** The following implements various basic forms of iteration and imaging of 00029 ** expressions, taking into account both plain operations and compounds. Some 00030 ** hints to remember the function names: 00031 ** - \c A — Like the ∀ operator, the predicate holds for all subexpressions. 00032 ** - \c E — Like the ∃ operator, the predicate holds for at least one 00033 ** subexpression. 00034 ** - \c img — The image under the given function 00035 ** - <tt>iter</tt>\e X — An iterative (sequential) variant of the algorithm \e X 00036 ** - <tt>bare</tt>\e X — A variant of \e X which takes a bare (context-free) 00037 ** function. 00038 ** - <em>X</em>\c k — A variant of \e X which pass the operand number as the 00039 ** first argument. 00040 ** 00041 ** Functions ending with \c _view take a first argument \ref cuex_opview_t, 00042 ** which specifies how the operands are passed to the callback. In 00043 ** particular, operations and non-commutative containers can be given a 00044 ** commutative view. Each operand will then be replaced on the fly by 00045 ** <tt>cuex_o2_metapair(\e ei, \e eo)</tt> where \e ei is a \ref cudyn_int of 00046 ** the operand number and \e eo is the original operand. Callbacks to image 00047 ** functions are expected to return the result in the same format. 00048 **/ 00049 00050 /** The compound view specifies how to iterate over or reconstruct operations 00051 ** and compounds. */ 00052 typedef enum { 00053 /** Non-commutative view for plain operations, preferred view according to 00054 ** their implementation for compounds. */ 00055 CUEX_PREF_VIEW, 00056 00057 /** Semi-commutative view, meaning non-commutative for plain operations and 00058 ** commutative for all kinds of compounds. */ 00059 CUEX_SCOMM_VIEW, 00060 00061 /** Fully commutative view, meaning commutative for operations as well as 00062 ** compounds. */ 00063 CUEX_FCOMM_VIEW 00064 } cuex_opview_t; 00065 00066 #if defined(CUCONF_PARALLELIZE) || defined(CU_IN_DOXYGEN) 00067 00068 /** True iff \a f takes every immediate subexpression of \a e to true. This is 00069 ** the same as \ref cuex_iterA_operands, but with unordered invocation, and 00070 ** the additional requirement that \a f is safe for parallel invocation. */ 00071 cu_bool_t cuex_A_operands(cu_clop(f, cu_bool_t, cuex_t), cuex_t e); 00072 00073 /** Like \ref cuex_A_operands but with a specified view of operands. */ 00074 cu_bool_t cuex_A_operands_view(cuex_opview_t view, 00075 cu_clop(f, cu_bool_t, cuex_t), cuex_t e); 00076 00077 /** Like \ref cuex_A_operands but also pass the operand number to \a f. */ 00078 cu_bool_t cuex_Ak_operands(cu_clop(f, cu_bool_t, int, cuex_t), cuex_t e); 00079 00080 /** Like \ref cuex_A_operands but also pass the operand number to \a f and use 00081 ** the specified view of the operands. */ 00082 cu_bool_t cuex_Ak_operands_view(cuex_opview_t view, 00083 cu_clop(f, cu_bool_t, int, cuex_t), cuex_t e); 00084 00085 /** True iff \a f takes some immediate subexpression of \a e to true. This is 00086 ** the same as \ref cuex_iterE_operand, but with unordered invocation, and the 00087 ** additional requirement that \a f is safe for parallel invocation. */ 00088 cu_bool_t cuex_E_operand(cu_clop(f, cu_bool_t, cuex_t), cuex_t e); 00089 00090 #else 00091 # define cuex_A_operands cuex_iterA_operands 00092 # define cuex_A_operands_view cuex_iterA_operands_view 00093 # define cuex_Ak_operands cuex_iterAk_operands 00094 # define cuex_Ak_operands_view cuex_iterAk_operands_view 00095 # define cuex_E_operand cuex_iterE_operand 00096 #endif 00097 00098 /** A variant of \ref cuex_A_operands specialised for context-free callbacks. */ 00099 cu_bool_t cuex_bareA_operands(cu_bool_t (*f)(cuex_t), cuex_t e); 00100 00101 /** A variant of \ref cuex_E_operand specialised for context-free callbacks. */ 00102 cu_bool_t cuex_bareE_operand(cu_bool_t (*f)(cuex_t), cuex_t e); 00103 00104 /** Calls \a f on each immediate subexpression of \a e in operand order. */ 00105 void cuex_iter_operands(cu_clop(f, void, cuex_t), cuex_t e); 00106 00107 /** Calls \a f on each subexpression of \a e in operand order and builds the 00108 ** conjunction of the results, exiting as soon as \a f returns false. */ 00109 cu_bool_t cuex_iterA_operands(cu_clop(f, cu_bool_t, cuex_t), cuex_t e); 00110 00111 /** Like \ref cuex_iterA_operands but using specified view of operands. */ 00112 cu_bool_t cuex_iterA_operands_view(cuex_opview_t view, 00113 cu_clop(f, cu_bool_t, cuex_t), cuex_t e); 00114 00115 /** Like \a ref cuex_iterA_operands but also pass the operand number to 00116 ** \a f. */ 00117 cu_bool_t cuex_iterAk_operands(cu_clop(f, cu_bool_t, int, cuex_t), cuex_t e); 00118 00119 /** Like \ref cuex_iterA_operands but also pass the operand number to \a f and 00120 ** use the specified view. */ 00121 cu_bool_t cuex_iterAk_operands_view(cuex_opview_t view, 00122 cu_clop(f, cu_bool_t, int, cuex_t), 00123 cuex_t e); 00124 00125 /** Calls \a f on each subexpression of \a e in operand order and builds the 00126 ** disjunction of the results, exiting as soon as \a f returns true. */ 00127 cu_bool_t cuex_iterE_operand(cu_clop(f, cu_bool_t, cuex_t), cuex_t e); 00128 00129 #if defined(CUCONF_PARALLELIZE) || defined(CU_IN_DOXYGEN) 00130 00131 /** Returns the result of replacing each immediate subexpression of \a e with 00132 ** its mapping under \a f. This is the same as \ref cuex_iterimg_operands, 00133 ** but with unordered invocation, and the additional requirement that \a f is 00134 ** safe for parallel invocation. */ 00135 cuex_t cuex_img_operands(cu_clop(f, cuex_t, cuex_t), cuex_t e); 00136 00137 /** A variant of \ref cuex_img_operands with a specified view of operands. */ 00138 cuex_t cuex_img_operands_view(cuex_opview_t view, 00139 cu_clop(f, cuex_t, cuex_t), cuex_t e); 00140 00141 /** As \ref cuex_img_operands but also pass the operand number as the first 00142 ** argument to \a f. */ 00143 cuex_t cuex_imgk_operands(cu_clop(f, cuex_t, int, cuex_t), cuex_t e); 00144 00145 /** A variant of \ref cuex_imgk_operands with a specified view of operands. */ 00146 cuex_t cuex_imgk_operands_view(cuex_opview_t view, 00147 cu_clop(f, cuex_t, int, cuex_t), cuex_t e); 00148 00149 #else 00150 # define cuex_img_operands cuex_iterimg_operands 00151 # define cuex_img_operands_view cuex_iterimg_operands_view 00152 # define cuex_imgk_operands cuex_iterimgk_operands 00153 # define cuex_imgk_operands_view cuex_iterimgk_operands_view 00154 #endif 00155 00156 /** A variant of \ref cuex_img_operands specialised for context-free callbacks. */ 00157 cuex_t cuex_bareimg_operands(cuex_t (*f)(cuex_t), cuex_t e); 00158 00159 /** Returns the result of replacing each immediate subexpression of \a e with 00160 ** its mapping under \a f, where \a f is called in operand order. If \a f 00161 ** returns \c NULL, this function immediately returns \c NULL, as well. */ 00162 cuex_t cuex_iterimg_operands(cu_clop(f, cuex_t, cuex_t), cuex_t e); 00163 00164 /** As \ref cuex_iterimg_operands but using a specified of operands. */ 00165 cuex_t cuex_iterimg_operands_view(cuex_opview_t view, 00166 cu_clop(f, cuex_t, cuex_t), cuex_t e); 00167 00168 /** Like \ref cuex_iterimg_operands but also pass the operand number as the 00169 ** first argument to \a f. */ 00170 cuex_t cuex_iterimgk_operands(cu_clop(f, cuex_t, int, cuex_t), cuex_t e); 00171 00172 /** As \ref cuex_iterimgk_operands but using a specified of operands. */ 00173 cuex_t cuex_iterimgk_operands_view(cuex_opview_t view, 00174 cu_clop(f, cuex_t, int, cuex_t), cuex_t e); 00175 00176 /** @} */ 00177 CU_END_DECLARATIONS 00178 00179 #endif