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_LABELLING_H 00019 #define CUEX_LABELLING_H 00020 00021 #include <cuex/fwd.h> 00022 #include <cuoo/meta.h> 00023 #include <cuoo/type.h> 00024 00025 CU_BEGIN_DECLARATIONS 00026 /** \defgroup cuex_labelling_h cuex/labelling.h: Association from Constants to Expressions 00027 ** @{ \ingroup cuex_mod */ 00028 00029 extern cuoo_type_t cuexP_labelling_type; 00030 #define cuex_labelling_meta() cuoo_type_to_meta(cuexP_labelling_type) 00031 #define cuex_labelling_type() cuexP_labelling_type 00032 00033 /** True iff \a e is a labelling. */ 00034 CU_SINLINE cu_bool_t 00035 cuex_is_labelling(cuex_t e) 00036 { return cuex_meta(e) == cuex_labelling_meta(); } 00037 00038 extern cuex_t cuexP_labelling_empty; 00039 00040 /** The empty labelling. */ 00041 CU_SINLINE cuex_t cuex_labelling_empty(void) { return cuexP_labelling_empty; } 00042 00043 /** True iff \a e is the empty labelling. */ 00044 CU_SINLINE cu_bool_t cuex_is_labelling_empty(cuex_t e) 00045 { return e == cuexP_labelling_empty; } 00046 00047 /** A labelling with a single mapping from \a l to \a e. */ 00048 cuex_t cuex_labelling_singleton(cuex_t l, cuex_t e); 00049 00050 /** Given an altering sequence of labels and values terminated by \c NULL, 00051 ** returns the labelling of the corresponding mapping. */ 00052 cuex_t cuex_labelling_by_arglist(cuex_t l, cuex_t e, ...); 00053 00054 /** The labelling \a L with the additional mapping from \a l to \a e. If \a L 00055 ** already contains the key \a l, then \a L is returned. */ 00056 cuex_t cuex_labelling_insert(cuex_t L, cuex_t l, cuex_t e); 00057 00058 /** Assuming \a va refers to an argument list which contains a altering 00059 ** sequence of pairs of labels and values terminated by \c NULL, returns the 00060 ** result of inserting a mapping for each pair into \a L. */ 00061 cuex_t cuex_labelling_insert_valist(cuex_t L, va_list va); 00062 00063 /** The variable arguments shall be an altering sequence of labels and values 00064 ** terminated by \c NULL, and this function returns the result of inserting a 00065 ** mapping for each (label, value) pair into \a L. */ 00066 cuex_t cuex_labelling_insert_arglist(cuex_t L, ...); 00067 00068 /** Returns \a L with an extra mapping from \a l to \a e. If \a l is already 00069 ** present in \a L, the existing value \e v is replaced with <code>merge(\e v, 00070 ** \a e)</code>. */ 00071 cuex_t cuex_labelling_deep_insert(cu_clop(merge, cuex_t, cuex_t, cuex_t), 00072 cuex_t L, cuex_t l, cuex_t e); 00073 00074 /** Returns the mapping of \a l in \a L, or \c NULL if none. */ 00075 cuex_t cuex_labelling_find(cuex_t L, cuex_t l); 00076 00077 /** Returns the index of \a l in \a L, or \c (size_t)-1 if not found. Note 00078 ** that the complexity of this call is linear in the cardinality of \a L. */ 00079 size_t cuex_labelling_find_index(cuex_t L, cuex_t l); 00080 00081 /** Returns the result of erasing the mapping from \a l in \a L if present, 00082 ** otherwise returns \a L. */ 00083 cuex_t cuex_labelling_erase(cuex_t L, cuex_t l); 00084 00085 /** If \a l has a mapping if \c *\a L, updates <code>*\a L</code> by erasing 00086 ** it, and returns the value of the mapping, otherwise returns \c NULL. */ 00087 cuex_t cuex_labelling_find_erase(cuex_t *L, cuex_t l); 00088 00089 /** Returns the cardinality of \a L. Note that the complexity is linear. */ 00090 size_t cuex_labelling_card(cuex_t L); 00091 00092 /** Forms the union of \a L0 and \a L1 considering elements equal if they have 00093 ** the same label. For elements present in both labellings, those from \a L0 00094 ** are used in the result. */ 00095 cuex_t cuex_labelling_left_union(cuex_t L0, cuex_t L1); 00096 00097 /** Forms the union of \a L0 and \a L1, merging the value part of common 00098 ** elements with \a merge. */ 00099 cuex_t cuex_labelling_deep_union(cu_clop(merge, cuex_t, cuex_t e0, cuex_t e1), 00100 cuex_t L0, cuex_t L1); 00101 00102 /** Returns the union of \a L0 and \a L1 if the labellings are disjoint, \c 00103 ** NULL otherwise. */ 00104 cuex_t cuex_labelling_disjoint_union(cuex_t L0, cuex_t L1); 00105 00106 /** Forms the intersection of \a L0 and \a L1 considering elements equal if 00107 ** they have the same label. The elements of \a L0 are used in the result. */ 00108 cuex_t cuex_labelling_left_isecn(cuex_t L0, cuex_t L1); 00109 00110 /** Forms the intersection of \a L0 and \a L1, merging the value part of the 00111 ** elements with \a merge. */ 00112 cuex_t cuex_labelling_deep_isecn(cu_clop(merge, cuex_t, cuex_t e0, cuex_t e1), 00113 cuex_t L0, cuex_t L1); 00114 00115 /** Call \a f with each label and value of \a L as long as it returns true, and 00116 ** return false iff an invocation of \a f returned false. */ 00117 cu_bool_t 00118 cuex_labelling_conj_kv(cuex_t L, cu_clop(f, cu_bool_t, cuex_t l, cuex_t e)); 00119 00120 /** Return the labelling where each value of \a L is transformed by \a f, which 00121 ** receives the old value and should return the new value. If the label is 00122 ** needed for the transform, see \ref cuex_labelling_image_kv. */ 00123 cuex_t 00124 cuex_labelling_image(cuex_t L, cu_clop(f, cuex_t, cuex_t e)); 00125 00126 /** Return the labelling where each value of \a L is transformed by \a f, which 00127 ** receives the label and the old value and should return the new value. */ 00128 cuex_t 00129 cuex_labelling_image_kv(cuex_t L, cu_clop(f, cuex_t, cuex_t l, cuex_t e)); 00130 00131 cuex_t cuex_labelling_expand_all(cuex_t L); 00132 cuex_t cuex_labelling_contract_all(cuex_t L); 00133 00134 /** Returns an iteration source for the unordered sequence. The implied 00135 ** sequence are \c CUEX_O2_METAPAIR nodes. 00136 ** \pre L is a labelling; check with \ref cuex_is_labelling */ 00137 cu_ptr_source_t cuex_labelling_comm_iter_source(cuex_t L); 00138 00139 /** Returns an iteration source for an ordered sequence of all values mapped by 00140 ** \a L. The ordering is given by arbitrary fixing the ordering of the 00141 ** labels. The labels are not exposed. 00142 ** \pre L is a labelling; check with \ref cuex_is_labelling 00143 ** \see cuex_labelling_comm_iter_source */ 00144 cu_ptr_source_t cuex_labelling_ncomm_iter_source(cuex_t L); 00145 00146 /** A junctor for constructing the image of \a L, using the ordered view 00147 ** corresponding to \a cuex_labelling_comm_iter_source. For each element 00148 ** popped from the junctor, at most one must be put back. The labels of the 00149 ** resulting labelling is taken from the original. */ 00150 cu_ptr_junctor_t cuex_labelling_ncomm_image_junctor(cuex_t L); 00151 00152 /** A \ref cu_ptr_seq_h "sinktor" for construction a new labelling by unordered 00153 ** insertion of \c CUEX_O2_METAPAIR nodes and labellings. */ 00154 cu_ptr_sinktor_t cuex_labelling_comm_build_sinktor(void); 00155 00156 /** A \ref cu_ptr_seq_h "sinktor" for extending a labelling by unordered 00157 ** insertion of \c CUEX_O2_METAPAIR nodes and labellings. */ 00158 cu_ptr_sinktor_t cuex_labelling_comm_union_sinktor(cuex_t L); 00159 00160 /** @} */ 00161 CU_END_DECLARATIONS 00162 00163 #endif