Claw
1.7.3
|
00001 /* 00002 CLAW - a C++ Library Absolutely Wonderful 00003 00004 CLAW is a free library without any particular aim but being useful to 00005 anyone. 00006 00007 Copyright (C) 2005-2011 Julien Jorge 00008 00009 This library is free software; you can redistribute it and/or 00010 modify it under the terms of the GNU Lesser General Public 00011 License as published by the Free Software Foundation; either 00012 version 2.1 of the License, or (at your option) any later version. 00013 00014 This library is distributed in the hope that it will be useful, 00015 but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00017 Lesser General Public License for more details. 00018 00019 You should have received a copy of the GNU Lesser General Public 00020 License along with this library; if not, write to the Free Software 00021 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00022 00023 contact: julien.jorge@gamned.org 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 } // ordered_set::operator*=() 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 } // ordered_set::operator+=() 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 } // ordered_set::operator-=() 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 } // ordered_set::operator/=() 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 } // ordered_set::operator>() 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 } // ordered_set::operator>=() 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 } // ordered_set::operator<() 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 } // ordered_set::operator<=() 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 } // ordered_set::intersection() 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 } // ordered_set::join() 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 } // ordered_set::difference() 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 } // ordered_set::symetric_difference() 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 } // ordered_set::contains() 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 } // ordered_set::strictly_contains() 00256