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