2 CLAW - a C++ Library Absolutely Wonderful
4 CLAW is a free library without any particular aim but being useful to
7 Copyright (C) 2005-2011 Julien Jorge
9 This library is free software; you can redistribute it and/or
10 modify it under the terms of the GNU Lesser General Public
11 License as published by the Free Software Foundation; either
12 version 2.1 of the License, or (at your option) any later version.
14 This library is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Lesser General Public License for more details.
19 You should have received a copy of the GNU Lesser General Public
20 License along with this library; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 contact: julien.jorge@gamned.org
26 * \file ordered_set.tpp
27 * \brief Implementation of the claw::math::ordered_set
28 * \author Julien Jorge
32 /*----------------------------------------------------------------------------*/
33 template<class K, class Comp>
34 Comp claw::math::ordered_set<K,Comp>::s_key_comp;
36 /*----------------------------------------------------------------------------*/
38 * \brief Intersection.
39 * \param that The instance to intersect from.
41 template<class K, class Comp>
42 claw::math::ordered_set<K, Comp>&
43 claw::math::ordered_set<K, Comp>::operator*=( const ordered_set& that )
45 return intersection( that );
46 } // ordered_set::operator*=()
48 /*----------------------------------------------------------------------------*/
51 * \param that The instance to join with.
53 template<class K, class Comp>
54 claw::math::ordered_set<K, Comp>&
55 claw::math::ordered_set<K, Comp>::operator+=( const ordered_set& that )
58 } // ordered_set::operator+=()
60 /*----------------------------------------------------------------------------*/
63 * \param that The instance from which to remove items.
65 template<class K, class Comp>
66 claw::math::ordered_set<K, Comp>&
67 claw::math::ordered_set<K, Comp>::operator-=( const ordered_set& that )
69 return difference( that );
70 } // ordered_set::operator-=()
72 /*----------------------------------------------------------------------------*/
74 * \brief Symetric difference.
75 * \param that The instance to differ from.
77 template<class K, class Comp>
78 claw::math::ordered_set<K, Comp>&
79 claw::math::ordered_set<K, Comp>::operator/=( const ordered_set& that )
81 return symetric_difference( that );
82 } // ordered_set::operator/=()
84 /*----------------------------------------------------------------------------*/
87 * \param that The instance that should be contained.
88 * \return true if that is strictly included in this.
90 template<class K, class Comp>
92 claw::math::ordered_set<K, Comp>::operator>( const ordered_set& that ) const
94 return strictly_contains( that );
95 } // ordered_set::operator>()
97 /*----------------------------------------------------------------------------*/
99 * \brief Inclusion or equality.
100 * \param that The instance that should be contained.
101 * \return true if that is included in this.
103 template<class K, class Comp>
105 claw::math::ordered_set<K, Comp>::operator>=( const ordered_set& that ) const
107 return contains( that );
108 } // ordered_set::operator>=()
110 /*----------------------------------------------------------------------------*/
113 * \param that The instance that should contain.
114 * \return true if that is strictly included in this.
116 template<class K, class Comp>
118 claw::math::ordered_set<K, Comp>::operator<( const ordered_set& that ) const
120 return that.strictly_contains( *this );
121 } // ordered_set::operator<()
123 /*----------------------------------------------------------------------------*/
125 * \brief Inclusion or equality.
126 * \param that The instance that should be contained.
127 * \return true if that is included in this.
129 template<class K, class Comp>
131 claw::math::ordered_set<K, Comp>::operator<=( const ordered_set& that ) const
133 return that.contains( *this );
134 } // ordered_set::operator<=()
136 /*----------------------------------------------------------------------------*/
138 * \brief Intersection.
139 * \param that The instance to intersect from.
141 template<class K, class Comp>
142 claw::math::ordered_set<K, Comp>&
143 claw::math::ordered_set<K, Comp>::intersection( const ordered_set& that )
145 std::list<K> remove_us;
148 for (it=super::begin(); it!=super::end(); ++it)
149 if ( that.find( *it ) == that.end() )
150 remove_us.push_front( *it );
152 typename std::list<K>::const_iterator remove_it;
154 for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
155 super::erase( *remove_it );
158 } // ordered_set::intersection()
160 /*----------------------------------------------------------------------------*/
163 * \param that The instance to join with.
165 template<class K, class Comp>
166 claw::math::ordered_set<K, Comp>&
167 claw::math::ordered_set<K, Comp>::join( const ordered_set& that )
171 for (it=that.begin(); it!=that.end(); ++it)
172 super::insert( *it );
175 } // ordered_set::join()
177 /*----------------------------------------------------------------------------*/
180 * \param that The instance from which to remove items.
182 template<class K, class Comp>
183 claw::math::ordered_set<K, Comp>&
184 claw::math::ordered_set<K, Comp>::difference( const ordered_set& that )
186 std::list<K> remove_us;
189 for (it=super::begin(); it!=super::end(); ++it)
190 if ( that.find( *it ) != that.end() )
191 remove_us.push_front( *it );
193 typename std::list<K>::const_iterator remove_it;
195 for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
196 super::erase( *remove_it );
199 } // ordered_set::difference()
201 /*----------------------------------------------------------------------------*/
203 * \brief Symetric difference.
204 * \param that The instance to differ from.
206 template<class K, class Comp>
207 claw::math::ordered_set<K, Comp>&
208 claw::math::ordered_set<K, Comp>::symetric_difference( const ordered_set& that )
210 ordered_set<K, Comp> my_copy(*this), his_copy(that);
212 return difference( that ).join( his_copy.difference(my_copy) );
213 } // ordered_set::symetric_difference()
215 /*----------------------------------------------------------------------------*/
217 * \brief Inclusion or equality.
218 * \param that The instance that should be contained.
219 * \return true if that is included in this.
221 template<class K, class Comp>
223 claw::math::ordered_set<K, Comp>::contains( const ordered_set& that ) const
225 bool ok = super::size() >= that.size();
226 const_iterator it_this( super::begin() );
227 const_iterator it_that( that.begin() );
229 while ( ok && (it_that != that.end()) && (it_this != super::end()) )
230 if ( s_key_comp( *it_this, *it_that ) )
232 else if ( s_key_comp( *it_that, *it_this ) )
240 return it_that == that.end();
241 } // ordered_set::contains()
243 /*----------------------------------------------------------------------------*/
246 * \param that The instance that should contain.
247 * \return true if that is strictly included in this.
249 template<class K, class Comp>
251 claw::math::ordered_set<K, Comp>::strictly_contains
252 ( const ordered_set& that ) const
254 return contains(that) && ( super::size() > that.size() );
255 } // ordered_set::strictly_contains()