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 /*----------------------------------------------------------------------------*/
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 

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1