wibble
0.1.28
|
00001 // -*- C++ -*- 00002 00003 #include <set> 00004 #include <wibble/empty.h> 00005 #include <wibble/singleton.h> 00006 #include <algorithm> 00007 00008 #ifndef WIBBLE_OPERATORS_H 00009 #define WIBBLE_OPERATORS_H 00010 00011 namespace wibble { 00012 namespace operators { 00013 00014 /* 00015 template< typename S, typename VT > struct IsContainer { 00016 typedef S T; 00017 }; 00018 00019 template< typename S > 00020 typename IsContainer< S, typename S::value_type >::T operator &&( const S &a, const S &b ) { 00021 S ret; 00022 std::set_intersection( a.begin(), a.end(), b.begin(), b.end(), 00023 std::inserter( ret, ret.begin() ) ); 00024 return ret; 00025 } 00026 */ 00027 00028 template< typename T > 00029 T operator+( const T &i, typename T::difference_type o ) { 00030 T r = i; 00031 std::advance( r, o ); 00032 return r; 00033 } 00034 00035 template< typename T > 00036 std::set< T > operator &( const std::set< T > &a, const std::set< T > &b ) { 00037 std::set< T > ret; 00038 std::set_intersection( a.begin(), a.end(), b.begin(), b.end(), 00039 std::inserter( ret, ret.begin() ) ); 00040 return ret; 00041 } 00042 00043 template< typename T > 00044 std::set< T > operator &( const std::set< T > &a, const T &b ) { 00045 std::set< T > ret; 00046 if ( a.find( b ) != a.end() ) { 00047 std::set< T > r; 00048 r.insert( b ); 00049 return r; 00050 } 00051 return std::set< T >(); 00052 } 00053 00054 template< typename T > 00055 std::set< T > operator |( const std::set< T > &a, const T& item ) { 00056 std::set< T > ret = a; 00057 ret.insert(item); 00058 return ret; 00059 } 00060 00061 template< typename T > 00062 std::set< T > operator |( const std::set< T > &a, const wibble::Empty<T>& ) { 00063 return a; 00064 } 00065 00066 template< typename T > 00067 std::set< T > operator |( const std::set< T > &a, const wibble::Singleton<T>& item ) { 00068 std::set< T > ret = a; 00069 ret.insert(*item.begin()); 00070 return ret; 00071 } 00072 00073 template< typename T > 00074 std::set< T > operator |( const std::set< T > &a, const std::set< T > &b ) { 00075 std::set< T > ret; 00076 std::set_union( a.begin(), a.end(), b.begin(), b.end(), 00077 std::inserter( ret, ret.begin() ) ); 00078 return ret; 00079 } 00080 00081 template< typename T > 00082 std::set< T > operator -( const std::set< T > &a, const std::set< T > &b ) { 00083 std::set< T > ret; 00084 std::set_difference( a.begin(), a.end(), b.begin(), b.end(), 00085 std::inserter(ret, ret.begin() ) ); 00086 return ret; 00087 } 00088 00089 template< typename T > 00090 std::set< T > operator -( const std::set< T > &a, const T& item ) { 00091 std::set< T > ret = a; 00092 ret.erase(item); 00093 return ret; 00094 } 00095 00096 template< typename T > 00097 std::set< T > operator -( const std::set< T > &a, const wibble::Singleton<T>& item ) { 00098 std::set< T > ret = a; 00099 ret.erase(*item.begin()); 00100 return ret; 00101 } 00102 00103 template< typename T > 00104 std::set< T > operator -( const std::set< T > &a, const wibble::Empty<T>& ) { 00105 return a; 00106 } 00107 00108 template< typename T > 00109 std::set< T > &operator|=( std::set< T > &a, const wibble::Empty<T>& ) 00110 { 00111 return a; 00112 } 00113 00114 template< typename T > 00115 std::set< T > &operator|=( std::set< T > &a, const T& item ) 00116 { 00117 a.insert(item); 00118 return a; 00119 } 00120 00121 // General case 00122 template< typename T, typename SEQ > 00123 std::set< T > &operator|=( std::set< T > &a, const SEQ& items ) 00124 { 00125 for (typename SEQ::const_iterator i = items.begin(); 00126 i != items.end(); ++i) 00127 a.insert(*i); 00128 return a; 00129 } 00130 00131 // Little optimization in case a is empty 00132 template< typename T > 00133 std::set< T > &operator |=( std::set< T > &a, const std::set< T > &b ) { 00134 if (a.empty()) 00135 return a = b; 00136 00137 for (typename std::set<T>::const_iterator i = b.begin(); 00138 i != b.end(); ++i) 00139 a.insert(*i); 00140 return a; 00141 } 00142 00143 // General case, but assumes that b is sorted 00144 template< typename T, typename SEQ > 00145 std::set< T > &operator &=( std::set< T > &a, const SEQ& b ) { 00146 // Little optimization: if b is empty, we avoid a run through a 00147 if (b.empty()) 00148 { 00149 a.clear(); 00150 return a; 00151 } 00152 00153 typename std::set<T>::iterator ia = a.begin(); 00154 typename SEQ::const_iterator ib = b.begin(); 00155 while (ia != a.end()) 00156 { 00157 if (ib != b.end() && *ib < *ia) 00158 { 00159 ++ib; 00160 } 00161 else if (ib == b.end() || *ia != *ib) 00162 { 00163 typename std::set<T>::iterator tmp = ia; 00164 ++ia; 00165 a.erase(tmp); 00166 } 00167 else 00168 { 00169 ++ia; 00170 ++ib; 00171 } 00172 } 00173 return a; 00174 } 00175 00176 template< typename T > 00177 std::set< T > &operator-=( std::set< T > &a, const wibble::Empty<T>& ) 00178 { 00179 return a; 00180 } 00181 00182 template< typename T > 00183 std::set< T > &operator-=( std::set< T > &a, const T& item ) 00184 { 00185 a.erase(item); 00186 return a; 00187 } 00188 00189 template< typename T > 00190 std::set< T > &operator-=( std::set< T > &a, const wibble::Singleton<T>& item ) 00191 { 00192 a.erase(*item.begin()); 00193 return a; 00194 } 00195 00196 // General case, but works only if b is sorted 00197 template< typename T, typename SEQ > 00198 std::set< T > &operator -=( std::set< T > &a, const SEQ& b ) 00199 { 00200 typename std::set<T>::iterator ia = a.begin(); 00201 typename SEQ::const_iterator ib = b.begin(); 00202 while (ia != a.end() && ib != b.end()) 00203 { 00204 if (*ia == *ib) 00205 { 00206 typename std::set<T>::iterator tmp = ia; 00207 ++ia; 00208 ++ib; 00209 a.erase(tmp); 00210 } 00211 else if (*ia < *ib) 00212 ++ia; 00213 else 00214 ++ib; 00215 } 00216 return a; 00217 } 00218 00219 template< typename T > 00220 bool operator<=( const T &a, const std::set< T > &b ) { 00221 return b.find( a ) != b.end(); 00222 } 00223 00224 template< typename T > 00225 bool operator<=( const std::set< T > &a, const std::set< T > &b ) { 00226 typename std::set<T>::const_iterator x = a.begin(); 00227 00228 for ( typename std::set<T>::const_iterator y = b.begin(); y != b.end(); ++y ) 00229 if ( x == a.end() ) 00230 return true; 00231 else if (*x == *y) 00232 ++x; 00233 else if (*x < *y) 00234 return false; 00235 00236 return x == a.end(); 00237 } 00238 00239 } 00240 } 00241 00242 #endif