ordered_set.tpp
Go to the documentation of this file.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