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
00033 template<class K, class Comp>
00034 Comp claw::math::ordered_set<K,Comp>::s_key_comp;
00035
00036
00041 template<class K, class Comp>
00042 claw::math::ordered_set<K, Comp>&
00043 claw::math::ordered_set<K, Comp>::operator*=( const ordered_set& that )
00044 {
00045 return intersection( that );
00046 }
00047
00048
00053 template<class K, class Comp>
00054 claw::math::ordered_set<K, Comp>&
00055 claw::math::ordered_set<K, Comp>::operator+=( const ordered_set& that )
00056 {
00057 return join( that );
00058 }
00059
00060
00065 template<class K, class Comp>
00066 claw::math::ordered_set<K, Comp>&
00067 claw::math::ordered_set<K, Comp>::operator-=( const ordered_set& that )
00068 {
00069 return difference( that );
00070 }
00071
00072
00077 template<class K, class Comp>
00078 claw::math::ordered_set<K, Comp>&
00079 claw::math::ordered_set<K, Comp>::operator/=( const ordered_set& that )
00080 {
00081 return symetric_difference( that );
00082 }
00083
00084
00090 template<class K, class Comp>
00091 bool
00092 claw::math::ordered_set<K, Comp>::operator>( const ordered_set& that ) const
00093 {
00094 return strictly_contains( that );
00095 }
00096
00097
00103 template<class K, class Comp>
00104 bool
00105 claw::math::ordered_set<K, Comp>::operator>=( const ordered_set& that ) const
00106 {
00107 return contains( that );
00108 }
00109
00110
00116 template<class K, class Comp>
00117 bool
00118 claw::math::ordered_set<K, Comp>::operator<( const ordered_set& that ) const
00119 {
00120 return that.strictly_contains( *this );
00121 }
00122
00123
00129 template<class K, class Comp>
00130 bool
00131 claw::math::ordered_set<K, Comp>::operator<=( const ordered_set& that ) const
00132 {
00133 return that.contains( *this );
00134 }
00135
00136
00141 template<class K, class Comp>
00142 claw::math::ordered_set<K, Comp>&
00143 claw::math::ordered_set<K, Comp>::intersection( const ordered_set& that )
00144 {
00145 std::list<K> remove_us;
00146 const_iterator it;
00147
00148 for (it=super::begin(); it!=super::end(); ++it)
00149 if ( that.find( *it ) == that.end() )
00150 remove_us.push_front( *it );
00151
00152 typename std::list<K>::const_iterator remove_it;
00153
00154 for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
00155 super::erase( *remove_it );
00156
00157 return *this;
00158 }
00159
00160
00165 template<class K, class Comp>
00166 claw::math::ordered_set<K, Comp>&
00167 claw::math::ordered_set<K, Comp>::join( const ordered_set& that )
00168 {
00169 const_iterator it;
00170
00171 for (it=that.begin(); it!=that.end(); ++it)
00172 super::insert( *it );
00173
00174 return *this;
00175 }
00176
00177
00182 template<class K, class Comp>
00183 claw::math::ordered_set<K, Comp>&
00184 claw::math::ordered_set<K, Comp>::difference( const ordered_set& that )
00185 {
00186 std::list<K> remove_us;
00187 const_iterator it;
00188
00189 for (it=super::begin(); it!=super::end(); ++it)
00190 if ( that.find( *it ) != that.end() )
00191 remove_us.push_front( *it );
00192
00193 typename std::list<K>::const_iterator remove_it;
00194
00195 for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
00196 super::erase( *remove_it );
00197
00198 return *this;
00199 }
00200
00201
00206 template<class K, class Comp>
00207 claw::math::ordered_set<K, Comp>&
00208 claw::math::ordered_set<K, Comp>::symetric_difference( const ordered_set& that )
00209 {
00210 ordered_set<K, Comp> my_copy(*this), his_copy(that);
00211
00212 return difference( that ).join( his_copy.difference(my_copy) );
00213 }
00214
00215
00221 template<class K, class Comp>
00222 bool
00223 claw::math::ordered_set<K, Comp>::contains( const ordered_set& that ) const
00224 {
00225 bool ok = super::size() >= that.size();
00226 const_iterator it_this( super::begin() );
00227 const_iterator it_that( that.begin() );
00228
00229 while ( ok && (it_that != that.end()) && (it_this != super::end()) )
00230 if ( s_key_comp( *it_this, *it_that ) )
00231 ++it_this;
00232 else if ( s_key_comp( *it_that, *it_this ) )
00233 ok = false;
00234 else
00235 {
00236 ++it_this;
00237 ++it_that;
00238 }
00239
00240 return it_that == that.end();
00241 }
00242
00243
00249 template<class K, class Comp>
00250 bool
00251 claw::math::ordered_set<K, Comp>::strictly_contains
00252 ( const ordered_set& that ) const
00253 {
00254 return contains(that) && ( super::size() > that.size() );
00255 }
00256