ordered_set.tpp

Go to the documentation of this file.
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-2008 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@yahoo.fr
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 } // ordered_set::operator*=()
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 } // ordered_set::operator+=()
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 } // ordered_set::operator-=()
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 } // ordered_set::operator/=()
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 } // ordered_set::operator>()
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 } // ordered_set::operator>=()
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 } // ordered_set::operator<()
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 } // ordered_set::operator<=()
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 } // ordered_set::intersection()
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 } // ordered_set::join()
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 } // ordered_set::difference()
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 } // ordered_set::symetric_difference()
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 } // ordered_set::contains()
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 } // ordered_set::strictly_contains()
00252 

Generated on Thu May 22 21:07:35 2008 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.5.5