00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #include <list>
00031
00032
00037 template<class K, class Comp>
00038 claw::math::ordered_set<K, Comp>&
00039 claw::math::ordered_set<K, Comp>::operator*=( const ordered_set& that )
00040 {
00041 return intersection( that );
00042 }
00043
00044
00049 template<class K, class Comp>
00050 claw::math::ordered_set<K, Comp>&
00051 claw::math::ordered_set<K, Comp>::operator+=( const ordered_set& that )
00052 {
00053 return join( that );
00054 }
00055
00056
00061 template<class K, class Comp>
00062 claw::math::ordered_set<K, Comp>&
00063 claw::math::ordered_set<K, Comp>::operator-=( const ordered_set& that )
00064 {
00065 return difference( that );
00066 }
00067
00068
00073 template<class K, class Comp>
00074 claw::math::ordered_set<K, Comp>&
00075 claw::math::ordered_set<K, Comp>::operator/=( const ordered_set& that )
00076 {
00077 return symetric_difference( that );
00078 }
00079
00080
00086 template<class K, class Comp>
00087 bool
00088 claw::math::ordered_set<K, Comp>::operator>( const ordered_set& that ) const
00089 {
00090 return strictly_contains( that );
00091 }
00092
00093
00099 template<class K, class Comp>
00100 bool
00101 claw::math::ordered_set<K, Comp>::operator>=( const ordered_set& that ) const
00102 {
00103 return contains( that );
00104 }
00105
00106
00112 template<class K, class Comp>
00113 bool
00114 claw::math::ordered_set<K, Comp>::operator<( const ordered_set& that ) const
00115 {
00116 return that.strictly_contains( *this );
00117 }
00118
00119
00125 template<class K, class Comp>
00126 bool
00127 claw::math::ordered_set<K, Comp>::operator<=( const ordered_set& that ) const
00128 {
00129 return that.contains( *this );
00130 }
00131
00132
00137 template<class K, class Comp>
00138 claw::math::ordered_set<K, Comp>&
00139 claw::math::ordered_set<K, Comp>::intersection( const ordered_set& that )
00140 {
00141 std::list<K> remove_us;
00142 const_iterator it;
00143
00144 for (it=super::begin(); it!=super::end(); ++it)
00145 if ( that.find( *it ) == that.end() )
00146 remove_us.push_front( *it );
00147
00148 typename std::list<K>::const_iterator remove_it;
00149
00150 for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
00151 super::erase( *remove_it );
00152
00153 return *this;
00154 }
00155
00156
00161 template<class K, class Comp>
00162 claw::math::ordered_set<K, Comp>&
00163 claw::math::ordered_set<K, Comp>::join( const ordered_set& that )
00164 {
00165 const_iterator it;
00166
00167 for (it=that.begin(); it!=that.end(); ++it)
00168 super::insert( *it );
00169
00170 return *this;
00171 }
00172
00173
00178 template<class K, class Comp>
00179 claw::math::ordered_set<K, Comp>&
00180 claw::math::ordered_set<K, Comp>::difference( const ordered_set& that )
00181 {
00182 std::list<K> remove_us;
00183 const_iterator it;
00184
00185 for (it=super::begin(); it!=super::end(); ++it)
00186 if ( that.find( *it ) != that.end() )
00187 remove_us.push_front( *it );
00188
00189 typename std::list<K>::const_iterator remove_it;
00190
00191 for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
00192 super::erase( *remove_it );
00193
00194 return *this;
00195 }
00196
00197
00202 template<class K, class Comp>
00203 claw::math::ordered_set<K, Comp>&
00204 claw::math::ordered_set<K, Comp>::symetric_difference( const ordered_set& that )
00205 {
00206 ordered_set<K, Comp> my_copy(*this), his_copy(that);
00207
00208 return difference( that ).join( his_copy.difference(my_copy) );
00209 }
00210
00211
00217 template<class K, class Comp>
00218 bool
00219 claw::math::ordered_set<K, Comp>::contains( const ordered_set& that ) const
00220 {
00221 bool ok = super::size() >= that.size();
00222 const_iterator it_this( super::begin() );
00223 const_iterator it_that( that.begin() );
00224
00225 while ( ok && (it_that != that.end()) && (it_this != super::end()) )
00226 if ( s_key_less( *it_this, *it_that ) )
00227 ++it_this;
00228 else if ( s_key_less( *it_that, *it_this ) )
00229 ok = false;
00230 else
00231 {
00232 ++it_this;
00233 ++it_that;
00234 }
00235
00236 return it_that == that.end();
00237 }
00238
00239
00245 template<class K, class Comp>
00246 bool
00247 claw::math::ordered_set<K, Comp>::strictly_contains
00248 ( const ordered_set& that ) const
00249 {
00250 return contains(that) && ( super::size() > that.size() );
00251 }
00252