Claw 1.7.3
ordered_set.tpp
1/*
2 CLAW - a C++ Library Absolutely Wonderful
3
4 CLAW is a free library without any particular aim but being useful to
5 anyone.
6
7 Copyright (C) 2005-2011 Julien Jorge
8
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.
13
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.
18
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
22
23 contact: julien.jorge@gamned.org
24*/
25/**
26 * \file ordered_set.tpp
27 * \brief Implementation of the claw::math::ordered_set
28 * \author Julien Jorge
29 */
30#include <list>
31
32/*----------------------------------------------------------------------------*/
33template<class K, class Comp>
34Comp claw::math::ordered_set<K,Comp>::s_key_comp;
35
36/*----------------------------------------------------------------------------*/
37/**
38 * \brief Intersection.
39 * \param that The instance to intersect from.
40 */
41template<class K, class Comp>
42claw::math::ordered_set<K, Comp>&
43claw::math::ordered_set<K, Comp>::operator*=( const ordered_set& that )
44{
45 return intersection( that );
46} // ordered_set::operator*=()
47
48/*----------------------------------------------------------------------------*/
49/**
50 * \brief Union.
51 * \param that The instance to join with.
52 */
53template<class K, class Comp>
54claw::math::ordered_set<K, Comp>&
55claw::math::ordered_set<K, Comp>::operator+=( const ordered_set& that )
56{
57 return join( that );
58} // ordered_set::operator+=()
59
60/*----------------------------------------------------------------------------*/
61/**
62 * \brief Difference.
63 * \param that The instance from which to remove items.
64 */
65template<class K, class Comp>
66claw::math::ordered_set<K, Comp>&
67claw::math::ordered_set<K, Comp>::operator-=( const ordered_set& that )
68{
69 return difference( that );
70} // ordered_set::operator-=()
71
72/*----------------------------------------------------------------------------*/
73/**
74 * \brief Symetric difference.
75 * \param that The instance to differ from.
76 */
77template<class K, class Comp>
78claw::math::ordered_set<K, Comp>&
79claw::math::ordered_set<K, Comp>::operator/=( const ordered_set& that )
80{
81 return symetric_difference( that );
82} // ordered_set::operator/=()
83
84/*----------------------------------------------------------------------------*/
85/**
86 * \brief Inclusion.
87 * \param that The instance that should be contained.
88 * \return true if that is strictly included in this.
89 */
90template<class K, class Comp>
91bool
92claw::math::ordered_set<K, Comp>::operator>( const ordered_set& that ) const
93{
94 return strictly_contains( that );
95} // ordered_set::operator>()
96
97/*----------------------------------------------------------------------------*/
98/**
99 * \brief Inclusion or equality.
100 * \param that The instance that should be contained.
101 * \return true if that is included in this.
102 */
103template<class K, class Comp>
104bool
105claw::math::ordered_set<K, Comp>::operator>=( const ordered_set& that ) const
106{
107 return contains( that );
108} // ordered_set::operator>=()
109
110/*----------------------------------------------------------------------------*/
111/**
112 * \brief Inclusion.
113 * \param that The instance that should contain.
114 * \return true if that is strictly included in this.
115 */
116template<class K, class Comp>
117bool
118claw::math::ordered_set<K, Comp>::operator<( const ordered_set& that ) const
119{
120 return that.strictly_contains( *this );
121} // ordered_set::operator<()
122
123/*----------------------------------------------------------------------------*/
124/**
125 * \brief Inclusion or equality.
126 * \param that The instance that should be contained.
127 * \return true if that is included in this.
128 */
129template<class K, class Comp>
130bool
131claw::math::ordered_set<K, Comp>::operator<=( const ordered_set& that ) const
132{
133 return that.contains( *this );
134} // ordered_set::operator<=()
135
136/*----------------------------------------------------------------------------*/
137/**
138 * \brief Intersection.
139 * \param that The instance to intersect from.
140 */
141template<class K, class Comp>
142claw::math::ordered_set<K, Comp>&
143claw::math::ordered_set<K, Comp>::intersection( const ordered_set& that )
144{
145 std::list<K> remove_us;
146 const_iterator it;
147
148 for (it=super::begin(); it!=super::end(); ++it)
149 if ( that.find( *it ) == that.end() )
150 remove_us.push_front( *it );
151
152 typename std::list<K>::const_iterator remove_it;
153
154 for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
155 super::erase( *remove_it );
156
157 return *this;
158} // ordered_set::intersection()
159
160/*----------------------------------------------------------------------------*/
161/**
162 * \brief Union.
163 * \param that The instance to join with.
164 */
165template<class K, class Comp>
166claw::math::ordered_set<K, Comp>&
167claw::math::ordered_set<K, Comp>::join( const ordered_set& that )
168{
169 const_iterator it;
170
171 for (it=that.begin(); it!=that.end(); ++it)
172 super::insert( *it );
173
174 return *this;
175} // ordered_set::join()
176
177/*----------------------------------------------------------------------------*/
178/**
179 * \brief Difference.
180 * \param that The instance from which to remove items.
181 */
182template<class K, class Comp>
183claw::math::ordered_set<K, Comp>&
184claw::math::ordered_set<K, Comp>::difference( const ordered_set& that )
185{
186 std::list<K> remove_us;
187 const_iterator it;
188
189 for (it=super::begin(); it!=super::end(); ++it)
190 if ( that.find( *it ) != that.end() )
191 remove_us.push_front( *it );
192
193 typename std::list<K>::const_iterator remove_it;
194
195 for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
196 super::erase( *remove_it );
197
198 return *this;
199} // ordered_set::difference()
200
201/*----------------------------------------------------------------------------*/
202/**
203 * \brief Symetric difference.
204 * \param that The instance to differ from.
205 */
206template<class K, class Comp>
207claw::math::ordered_set<K, Comp>&
208claw::math::ordered_set<K, Comp>::symetric_difference( const ordered_set& that )
209{
210 ordered_set<K, Comp> my_copy(*this), his_copy(that);
211
212 return difference( that ).join( his_copy.difference(my_copy) );
213} // ordered_set::symetric_difference()
214
215/*----------------------------------------------------------------------------*/
216/**
217 * \brief Inclusion or equality.
218 * \param that The instance that should be contained.
219 * \return true if that is included in this.
220 */
221template<class K, class Comp>
222bool
223claw::math::ordered_set<K, Comp>::contains( const ordered_set& that ) const
224{
225 bool ok = super::size() >= that.size();
226 const_iterator it_this( super::begin() );
227 const_iterator it_that( that.begin() );
228
229 while ( ok && (it_that != that.end()) && (it_this != super::end()) )
230 if ( s_key_comp( *it_this, *it_that ) )
231 ++it_this;
232 else if ( s_key_comp( *it_that, *it_this ) )
233 ok = false;
234 else
235 {
236 ++it_this;
237 ++it_that;
238 }
239
240 return it_that == that.end();
241} // ordered_set::contains()
242
243/*----------------------------------------------------------------------------*/
244/**
245 * \brief Inclusion.
246 * \param that The instance that should contain.
247 * \return true if that is strictly included in this.
248 */
249template<class K, class Comp>
250bool
251claw::math::ordered_set<K, Comp>::strictly_contains
252( const ordered_set& that ) const
253{
254 return contains(that) && ( super::size() > that.size() );
255} // ordered_set::strictly_contains()
256