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 /*----------------------------------------------------------------------------*/
33 template<class K, class Comp>
34 Comp claw::math::ordered_set<K,Comp>::s_key_comp;
35 
36 /*----------------------------------------------------------------------------*/
37 /**
38  * \brief Intersection.
39  * \param that The instance to intersect from.
40  */
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 )
44 {
45  return intersection( that );
46 } // ordered_set::operator*=()
47 
48 /*----------------------------------------------------------------------------*/
49 /**
50  * \brief Union.
51  * \param that The instance to join with.
52  */
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 )
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  */
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 )
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  */
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 )
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  */
90 template<class K, class Comp>
91 bool
92 claw::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  */
103 template<class K, class Comp>
104 bool
105 claw::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  */
116 template<class K, class Comp>
117 bool
118 claw::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  */
129 template<class K, class Comp>
130 bool
131 claw::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  */
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 )
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  */
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 )
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  */
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 )
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  */
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 )
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  */
221 template<class K, class Comp>
222 bool
223 claw::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  */
249 template<class K, class Comp>
250 bool
251 claw::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