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 
Generated on Wed Nov 12 2014 19:44:24 for MIST by doxygen 1.8.1.2