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 CUCON_UCSET_H 00019 #define CUCON_UCSET_H 00020 00021 /* This tuning option has a significant constant performance hit on insertions, 00022 * but reduced memory usage and provides O(1) equality. */ 00023 #define CUCON_UCSET_ENABLE_HCONS 1 00024 00025 #include <cucon/fwd.h> 00026 #include <stdio.h> 00027 #include <cu/clos.h> 00028 00029 CU_BEGIN_DECLARATIONS 00030 /** \defgroup cucon_ucset_h cucon/ucset.h: Constructive Integer Sets 00031 ** @{ \ingroup cucon_maps_and_sets_mod 00032 ** 00033 ** This provides constructive tests of integers, implemented as a trie of 00034 ** bitsets. 00035 ** It is thus suitable to represent both sparse and dense sets. 00036 ** The main features are 00037 ** 00038 ** - O(1) copy since modifications are non-destructive 00039 ** - Search and insert complexity ranges from <i>O</i>(log <i>n</i>) 00040 ** on avarage for containers of <i>n</i> random numbers, 00041 ** to <i>O</i>(<i>n</i>) for some patological cases like of containers with 00042 ** <i>n</i> powers of two. The patological cases are limited by 00043 ** the range of integers. For instance, on a 32 bit platform, 00044 ** <i>n</i> ≤ 32 - log<sub>2</sub> 64 = 26. 00045 ** (log<sub>2</sub> 64 comes from the 64-element bitsets at the 00046 ** leaves.) 00047 ** 00048 ** \sa 00049 ** \ref cucon_ucmap_h "cucon/ucmap.h": Maps with a similar implementation. 00050 ** \sa 00051 ** \ref cucon_pmap_h "cucon/pmap.h": This hash map can also be used as a set. 00052 */ 00053 00054 /** True iff \a set0 and \a set1 contains exactly the same elements. */ 00055 #if CUCON_UCSET_ENABLE_HCONS 00056 CU_SINLINE cu_bool_t 00057 cucon_ucset_eq(cucon_ucset_t set0, cucon_ucset_t set1) 00058 { return set0 == set1; } 00059 #else 00060 cu_bool_t cucon_ucset_eq(cucon_ucset_t set0, cucon_ucset_t set1); 00061 #endif 00062 00063 /** True iff \a set0 ⊆ \a set1. */ 00064 cu_bool_t cucon_ucset_subeq(cucon_ucset_t set0, cucon_ucset_t set1); 00065 00066 /** True iff \a set0 ∩ \a set1 = ∅. */ 00067 cu_bool_t cucon_ucset_disjoint(cucon_ucset_t set0, cucon_ucset_t set1); 00068 00069 /** Returs the empty set (\c NULL). */ 00070 CU_SINLINE cucon_ucset_t cucon_ucset_empty(void) { return NULL; } 00071 00072 /** True iff \a set is the empty set. */ 00073 CU_SINLINE cu_bool_t cucon_ucset_is_empty(cucon_ucset_t set) 00074 { return set == NULL; } 00075 00076 /** Returns the singleton set {\a key}. */ 00077 cucon_ucset_t cucon_ucset_singleton(uintptr_t key); 00078 00079 /** True iff \a set is a singleton set. */ 00080 cu_bool_t cucon_ucset_is_singleton(cucon_ucset_t set); 00081 00082 /** Return \a set with \a key inserted. */ 00083 cucon_ucset_t cucon_ucset_insert(cucon_ucset_t set, uintptr_t key); 00084 00085 /** Returns \a set ∖ {\a key}. */ 00086 cucon_ucset_t cucon_ucset_erase(cucon_ucset_t set, uintptr_t key); 00087 00088 /** Returns \a set0 ∪ \a set1. */ 00089 cucon_ucset_t cucon_ucset_union(cucon_ucset_t set0, cucon_ucset_t set1); 00090 00091 /** Returns \a set0 ∩ \a set1. */ 00092 cucon_ucset_t cucon_ucset_isecn(cucon_ucset_t set0, cucon_ucset_t set1); 00093 00094 /** Returns \a set0 ∖ \a set1. */ 00095 cucon_ucset_t cucon_ucset_compl(cucon_ucset_t set0, cucon_ucset_t set1); 00096 00097 /** True iff \a key ∈ \a set. */ 00098 cu_bool_t cucon_ucset_find(cucon_ucset_t set, uintptr_t key); 00099 00100 /** Sequential conjunction over elements in increasing order. */ 00101 cu_bool_t cucon_ucset_conj(cucon_ucset_t set, 00102 cu_clop(cb, cu_bool_t, uintptr_t key)); 00103 00104 /** Calls \a f for each element of \a set. */ 00105 void cucon_ucset_iter(cucon_ucset_t set, cu_clop(f, void, uintptr_t)); 00106 00107 /** Returns the cardinality of \a set. */ 00108 size_t cucon_ucset_card(cucon_ucset_t set); 00109 00110 /** Returns the minimum element of \a set, using unsigned comparison. */ 00111 uintptr_t cucon_ucset_umin(cucon_ucset_t set); 00112 00113 /** Returns the maximum element of \a set, using unsigned comparison. */ 00114 uintptr_t cucon_ucset_umax(cucon_ucset_t set); 00115 00116 /** Returns the minimum element of \a set, using signed comparison. */ 00117 intptr_t cucon_ucset_smin(cucon_ucset_t set); 00118 00119 /** Returns the maximum element of \a set, using signed comparison. */ 00120 intptr_t cucon_ucset_smax(cucon_ucset_t set); 00121 00122 /** Returns {\e x | \e x ∈ \a set ∧ \a f(\e x)}. */ 00123 cucon_ucset_t cucon_ucset_filter(cucon_ucset_t set, 00124 cu_clop(f, cu_bool_t, uintptr_t)); 00125 00126 /** Returns {\a f(\e x) | \e x ∈ \a set}. */ 00127 cucon_ucset_t cucon_ucset_image(cucon_ucset_t set, 00128 cu_clop(f, uintptr_t, uintptr_t)); 00129 00130 /** Combines \ref cucon_ucset_filter and cucon_ucset_image in one operation. 00131 ** \a f is passed a pointer to each key in \a set. If it returns false, the 00132 ** element is skipped, otherwise the key at the pointer passed to \a f, which 00133 ** may be modified by \a f, is included in the result. */ 00134 cucon_ucset_t cucon_ucset_filter_image(cucon_ucset_t set, 00135 cu_clop(f, cu_bool_t, uintptr_t *)); 00136 00137 /** Returns \a set ∩ [clip_min, clip_max], using unsigned comparison. */ 00138 cucon_ucset_t cucon_ucset_uclip(cucon_ucset_t set, 00139 uintptr_t clip_min, uintptr_t clip_max); 00140 00141 /** Returns \a set ∩ [clip_min, clip_max], using signed comparison. */ 00142 cucon_ucset_t cucon_ucset_sclip(cucon_ucset_t set, 00143 intptr_t clip_min, intptr_t clip_max); 00144 00145 /** Returns the set {\e x + \a diff | \e x ∈ \a set ∧ \a clip_min ≤ \e x ≤ \a 00146 ** clip_max}. */ 00147 cucon_ucset_t cucon_ucset_translate_uclip(cucon_ucset_t set, intptr_t diff, 00148 uintptr_t clip_min, 00149 uintptr_t clip_max); 00150 00151 /** \copydoc cucon_ucset_translate_uclip*/ 00152 cucon_ucset_t cucon_ucset_translate_sclip(cucon_ucset_t set, intptr_t diff, 00153 intptr_t clip_min, 00154 intptr_t clip_max); 00155 00156 /** Returns the set {\e x + \a diff | \e x ∈ \a set}. */ 00157 cucon_ucset_t cucon_ucset_translate(cucon_ucset_t set, intptr_t diff); 00158 00159 /** Print \a set to \a out as a set of unsigend integers using normal set 00160 ** notation. */ 00161 void cucon_ucset_fprint_uintptr(cucon_ucset_t set, FILE *out); 00162 00163 /** Print \a set to \a out as a set of signed integers using normal set 00164 ** notation. */ 00165 void cucon_ucset_fprint_intptr(cucon_ucset_t set, FILE *out); 00166 00167 /** Debug dump of \a set. */ 00168 void cucon_ucset_dump(cucon_ucset_t set, FILE *out); 00169 00170 struct cucon_ucset_itr 00171 { 00172 int sp, pos; 00173 cucon_ucset_t node_stack[1]; 00174 }; 00175 00176 /** Returns the size needed and interator over the elements of \a set. */ 00177 size_t cucon_ucset_itr_size(cucon_ucset_t set); 00178 00179 /** Initialises \a itr for iteration over \a set. The memory at \a itr must be 00180 ** at least the size reported by \ref cucon_ucset_itr_size(\a set). */ 00181 void cucon_ucset_itr_init(cucon_ucset_itr_t itr, cucon_ucset_t set); 00182 00183 /** Returns an iterator over the elements of \a set. */ 00184 cucon_ucset_itr_t cucon_ucset_itr_new(cucon_ucset_t set); 00185 00186 /** True iff \a itr is past the last element. */ 00187 CU_SINLINE cu_bool_t cucon_ucset_itr_at_end(cucon_ucset_itr_t itr) 00188 { return itr->sp < 0; } 00189 00190 /** Returns and advances over the next element of \a itr. */ 00191 uintptr_t cucon_ucset_itr_get(cucon_ucset_itr_t itr); 00192 00193 /** @} */ 00194 CU_END_DECLARATIONS 00195 00196 #endif