- メインページ
- モジュール
- ネームスペース
- データ構造
- ファイル

- ファイル一覧
- グローバル

set.h
説明を見る。
1 //
2 // Copyright (c) 2003-2011, MIST Project, Nagoya University
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without modification,
6 // are permitted provided that the following conditions are met:
7 //
8 // 1. Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 //
11 // 2. Redistributions in binary form must reproduce the above copyright notice,
12 // this list of conditions and the following disclaimer in the documentation
13 // and/or other materials provided with the distribution.
14 //
15 // 3. Neither the name of the Nagoya University nor the names of its contributors
16 // may be used to endorse or promote products derived from this software
17 // without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
21 // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
22 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25 // IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
26 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 //
28
33
34 #ifndef __INCLUDE_MIST_SET_H__
35 #define __INCLUDE_MIST_SET_H__
36
37
38 #ifndef __INCLUDE_MIST_CONF_H__
39 #include "mist_conf.h"
40 #endif
41
42 #include <iostream>
43 #include <set>
44 #include <algorithm>
45
46 // mist名前空間の始まり
47 _MIST_BEGIN
48
49
50
58
59
64 template< class SetType >
65 class set_base : public SetType
66 {
67 protected:
68 typedef SetType base;
69
70 public:
71 typedef typename base::key_type key_type;
72 typedef typename base::key_compare key_compare;
73 typedef typename base::value_compare value_compare;
74 typedef typename base::allocator_type allocator_type;
75 typedef typename base::size_type size_type;
76 typedef typename base::difference_type difference_type;
77
78 #if __MIST_MSVC__ != 6
79 typedef typename base::pointer pointer;
80 typedef typename base::const_pointer const_pointer;
81 #endif
82
83 typedef typename base::reference reference;
84 typedef typename base::const_reference const_reference;
85 typedef typename base::iterator iterator;
86 typedef typename base::const_iterator const_iterator;
87 typedef typename base::reverse_iterator reverse_iterator;
88 typedef typename base::const_reverse_iterator const_reverse_iterator;
89 typedef typename base::value_type value_type;
90
91
92 public:
94 set_base( ) : base( ){ }
95
97 explicit set_base( const key_compare &pred ) : base( pred ){ }
98
100 explicit set_base( const key_type &key ) : base( ){ base::insert( key ); }
101
103 set_base( const key_compare &pred, const allocator_type &alloc ) : base( pred, alloc ){ }
104
106 template< class Iterator >
107 set_base( Iterator first, Iterator last ) : base( first, last ){ }
108
109
111 template< class Iterator >
112 set_base( Iterator first, Iterator last, const key_compare &pred ) : base( first, last, pred ){ }
113
114
116 template< class Iterator >
117 set_base( Iterator first, Iterator last, const key_compare &pred, const allocator_type &alloc ) : base( first, last, pred, alloc ){ }
118
119 public:
124 set_base &operator +=( const set_base &s )
125 {
126 #if __MIST_MSVC__ != 6
127 base::insert( s.begin( ), s.end( ) );
128 #else
129 // MSVC6 付属のSTLのSETではイテレータの実装が異なる
130 const_iterator site = s.begin( );
131 const_iterator eite = s.end( );
132 for( ; site != eite ; ++site )
133 {
134 base::insert( *site );
135 }
136 #endif
137 return( *this );
138 }
139
141 set_base &operator +=( const key_type &s ){ base::insert( s ); return( *this ); }
142
143
148 set_base &operator -=( const set_base &s )
149 {
150 if( &s == this )
151 {
152 base::clear( );
153 }
154 else
155 {
156 set_base a = *this;
157 const_iterator site1 = a.begin( );
158 const_iterator eite1 = a.end( );
159 const_iterator site2 = s.begin( );
160 const_iterator eite2 = s.end( );
161
162 // 自分自身の内容を空っぽにする
163 base::clear( );
164
165 key_compare compare;
166 while( site1 != eite1 && site2 != eite2 )
167 {
168 if( compare( *site1, *site2 ) )
169 {
170 base::insert( *site1 );
171 ++site1;
172 }
173 else if( compare( *site2, *site1 ) )
174 {
175 ++site2;
176 }
177 else
178 {
179 ++site1;
180 ++site2;
181 }
182 }
183
184 if( site1 != eite1 )
185 {
186 #if __MIST_MSVC__ != 6
187 base::insert( site1, eite1 );
188 #else
189 // MSVC6 付属のSTLのSETではイテレータの実装が異なる
190 for( ; site1 != eite1 ; ++site1 )
191 {
192 base::insert( *site1 );
193 }
194 #endif
195 }
196 }
197 return( *this );
198 }
199
201 set_base &operator -=( const key_type &s ){ base::erase( s ); return( *this ); }
202
203
208 set_base &operator *=( const set_base &s )
209 {
210 if( &s != this )
211 {
212 set_base a = *this;
213 const_iterator site1 = a.begin( );
214 const_iterator eite1 = a.end( );
215 const_iterator site2 = s.begin( );
216 const_iterator eite2 = s.end( );
217
218 // 自分自身の内容を空っぽにする
219 base::clear( );
220
221 key_compare compare;
222 while( site1 != eite1 && site2 != eite2 )
223 {
224 if( compare( *site1, *site2 ) )
225 {
226 ++site1;
227 }
228 else if ( compare( *site2, *site1 ) )
229 {
230 ++site2;
231 }
232 else
233 {
234 base::insert( *site1 );
235 ++site1;
236 ++site2;
237 }
238 }
239 }
240 return( *this );
241 }
242
243
245 set_base &operator *=( const key_type &s )
246 {
247 set_base a = *this;
248 const_iterator site = a.begin( );
249 const_iterator eite = a.end( );
250
251 // 自分自身の内容を空っぽにする
252 base::clear( );
253
254 key_compare compare;
255 while( site != eite )
256 {
257 if( compare( *site, s ) )
258 {
259 ++site;
260 }
261 else if ( compare( s, *site ) )
262 {
263 break;
264 }
265 else
266 {
267 base::insert( *site );
268 ++site;
269 }
270 }
271 return( *this );
272 }
273
274
276 set_base &operator <<=( const set_base &s ){ return( operator +=( s ) ); }
277
279 set_base &operator <<=( const key_type &s ){ return( operator +=( s ) ); }
280
281
283 set_base &operator <<( const key_type &s ) const { return( set_base( *this )+=( s ) ); }
284
285
287 bool operator ==( const set_base &s ) const
288 {
289 if( base::size( ) != s.size( ) )
290 {
291 return( false );
292 }
293
294 key_compare compare;
295 const_iterator ite1 = base::begin( );
296 const_iterator eite1 = base::end( );
297 const_iterator ite2 = s.begin( );
298 for( ; ite1 != eite1 ; ++ite1, ++ite2 )
299 {
300 if( compare( *ite1, *ite2 ) || compare( *ite2, *ite1 ) )
301 {
302 return( false );
303 }
304 }
305 return( true );
306 }
307
308
310 bool operator ==( const key_type &s ) const
311 {
312 if( base::size( ) != 1 )
313 {
314 return( false );
315 }
316
317 key_compare compare;
318 const_iterator ite = base::begin( );
319 const_iterator eite = base::end( );
320 for( ; ite != eite ; ++ite )
321 {
322 if( compare( *ite, s ) || compare( s, *ite ) )
323 {
324 return( false );
325 }
326 }
327 return( true );
328 }
329
330
332 bool operator !=( const set_base &s ) const { return( !( *this == s ) ); }
333
335 bool operator !=( const key_type &s ) const { return( !( *this == s ) ); }
336
338 bool operator < ( const set_base &s ) const
339 {
340 if( base::size( ) >= s.size( ) )
341 {
342 return( false );
343 }
344
345 return( std::includes( s.begin( ), s.end( ), base::begin( ), base::end( ), key_compare( ) ) );
346 }
347
349 bool operator <=( const set_base &s ) const
350 {
351 if( base::size( ) > s.size( ) )
352 {
353 return( false );
354 }
355
356 return( std::includes( s.begin( ), s.end( ), base::begin( ), base::end( ), key_compare( ) ) );
357 }
358
360 bool operator > ( const set_base &s ) const { return( s < *this ); }
361
363 bool operator >=( const set_base &s ) const { return( s <= *this ); }
364 };
365
366
368 template< class SetType > inline const set_base< SetType > operator +( const set_base< SetType > &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) += s2 ); }
369
371 template< class SetType > inline const set_base< SetType > operator -( const set_base< SetType > &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) -= s2 ); }
372
374 template< class SetType > inline const set_base< SetType > operator *( const set_base< SetType > &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) *= s2 ); }
375
376
377 //inline const set_base operator /( const set_base &s1, const set_base &s2 ){ return( set_base( s1 ) /= s2 ); }
378 //inline const set_base operator %( const set_base &s1, const set_base &s2 ){ return( set_base( s1 ) %= s2 ); }
379 //inline const set_base operator |( const set_base &s1, const set_base &s2 ){ return( set_base( s1 ) |= s2 ); }
380 //inline const set_base operator &( const set_base &s1, const set_base &s2 ){ return( set_base( s1 ) &= s2 ); }
381 //inline const set_base operator ^( const set_base &s1, const set_base &s2 ){ return( set_base( s1 ) ^= s2 ); }
382
383
384
386 template< class SetType > inline const set_base< SetType > operator *( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( set_base< SetType >( s1 ) *= s2 ); }
387
389 template< class SetType > inline const set_base< SetType > operator *( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) *= s2 ); }
390
392 template< class SetType > inline const set_base< SetType > operator +( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( set_base< SetType >( s1 ) += s2 ); }
393
395 template< class SetType > inline const set_base< SetType > operator +( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s2 ) += s1 ); }
396
398 template< class SetType > inline const set_base< SetType > operator -( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( set_base< SetType >( s1 ) -= s2 ); }
399
401 template< class SetType > inline const set_base< SetType > operator -( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) -= s2 ); }
402
403
404
406 template< class SetType > bool operator ==( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( set_base< SetType >( s2 ) == s1 ); }
407
409 template< class SetType > bool operator !=( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( set_base< SetType >( s2 ) != s1 ); }
410
412 template< class SetType > bool operator < ( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( s1 < set_base< SetType >( s2 ) ); }
413
415 template< class SetType > bool operator <=( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( s1 <= set_base< SetType >( s2 ) ); }
416
418 template< class SetType > bool operator > ( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( s1 > set_base< SetType >( s2 ) ); }
419
421 template< class SetType > bool operator >=( const set_base< SetType > &s1, const typename set_base< SetType >::key_type &s2 ){ return( s1 >= set_base< SetType >( s2 ) ); }
422
423
424
426 template< class SetType > bool operator ==( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) == s2 ); }
427
429 template< class SetType > bool operator !=( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) != s2 ); }
430
432 template< class SetType > bool operator < ( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) < s2 ); }
433
435 template< class SetType > bool operator <=( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) <= s2 ); }
436
438 template< class SetType > bool operator > ( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) > s2 ); }
439
441 template< class SetType > bool operator >=( const typename set_base< SetType >::key_type &s1, const set_base< SetType > &s2 ){ return( set_base< SetType >( s1 ) >= s2 ); }
442
443
455 template< class SetType >
456 inline std::ostream &operator <<( std::ostream &out, const set_base< SetType > &s )
457 {
458 typename set_base< SetType >::const_iterator ite = s.begin( );
459 if( ite != s.end( ) )
460 {
461 out << *ite++;
462 }
463
464 for( ; ite != s.end( ) ; ++ite )
465 {
466 out << ", " << *ite;
467 }
468 return( out );
469 }
470
471
472
481 template< class Key, class Comp = std::less< Key >, class Allocator = std::allocator< Key > >
482 class set : public set_base< std::set< Key, Comp, Allocator > >
483 {
484 protected:
485 typedef set_base< std::set< Key, Comp, Allocator > > base;
486
487 public:
488 typedef typename base::key_type key_type;
489 typedef typename base::key_compare key_compare;
490 typedef typename base::value_compare value_compare;
491 typedef typename base::allocator_type allocator_type;
492 typedef typename base::size_type size_type;
493 typedef typename base::difference_type difference_type;
494
495 #if __MIST_MSVC__ != 6
496 typedef typename base::pointer pointer;
497 typedef typename base::const_pointer const_pointer;
498 #endif
499
500 typedef typename base::reference reference;
501 typedef typename base::const_reference const_reference;
502 typedef typename base::iterator iterator;
503 typedef typename base::const_iterator const_iterator;
504 typedef typename base::reverse_iterator reverse_iterator;
505 typedef typename base::const_reverse_iterator const_reverse_iterator;
506 typedef typename base::value_type value_type;
507
508 public:
510 set( ) : base( ){ }
511
513 explicit set( const key_compare &pred ) : base( pred ){ }
514
516 explicit set( const key_type &key ) : base( ){ base::insert( key ); }
517
519 set( const key_compare &pred, const allocator_type &alloc ) : base( pred, alloc ){ }
520
522 template< class Iterator >
523 set( Iterator first, Iterator last ) : base( first, last ){ }
524
526 template< class Iterator >
527 set( Iterator first, Iterator last, const key_compare &pred ) : base( first, last, pred ){ }
528
530 template< class Iterator >
531 set( Iterator first, Iterator last, const key_compare &pred, const allocator_type &alloc ) : base( first, last, pred, alloc ){ }
532 };
533
534
535
544 template< class Key, class Comp = std::less< Key >, class Allocator = std::allocator< Key > >
545 class multiset : public set_base< std::multiset< Key, Comp, Allocator > >
546 {
547 protected:
548 typedef set_base< std::multiset< Key, Comp, Allocator > > base;
549
550 public:
551 typedef typename base::key_type key_type;
552 typedef typename base::key_compare key_compare;
553 typedef typename base::value_compare value_compare;
554 typedef typename base::allocator_type allocator_type;
555 typedef typename base::size_type size_type;
556 typedef typename base::difference_type difference_type;
557
558 #if __MIST_MSVC__ != 6
559 typedef typename base::pointer pointer;
560 typedef typename base::const_pointer const_pointer;
561 #endif
562
563 typedef typename base::reference reference;
564 typedef typename base::const_reference const_reference;
565 typedef typename base::iterator iterator;
566 typedef typename base::const_iterator const_iterator;
567 typedef typename base::reverse_iterator reverse_iterator;
568 typedef typename base::const_reverse_iterator const_reverse_iterator;
569 typedef typename base::value_type value_type;
570
571 public:
573 multiset( ) : base( ){ }
574
576 explicit multiset( const key_compare &pred ) : base( pred ){ }
577
579 explicit multiset( const key_type &key ) : base( ){ base::insert( key ); }
580
582 multiset( const key_compare &pred, const allocator_type &alloc ) : base( pred, alloc ){ }
583
585 template< class Iterator >
586 multiset( Iterator first, Iterator last ) : base( first, last ){ }
587
589 template< class Iterator >
590 multiset( Iterator first, Iterator last, const key_compare &pred ) : base( first, last, pred ){ }
591
593 template< class Iterator >
594 multiset( Iterator first, Iterator last, const key_compare &pred, const allocator_type &alloc ) : base( first, last, pred, alloc ){ }
595 };
596
597
598
600 // 集合演算グループの終わり
601
602
603
604 // mist名前空間の終わり
605 _MIST_END
606
607
608 #endif // __INCLUDE_MIST_SET_H__
609