OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [testsuite/] [g++.dg/] [tm/] [pr46567.C] - Blame information for rev 693

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 693 jeremybenn
// { dg-do compile }
2
// { dg-options "-fgnu-tm -O2" }
3
 
4
typedef __PTRDIFF_TYPE__ ptrdiff_t;
5
typedef __SIZE_TYPE__ size_t;
6
namespace std __attribute__ ((__visibility__ ("default"))) {
7
  using ::ptrdiff_t;
8
  using ::size_t;
9
}
10
namespace std __attribute__ ((__visibility__ ("default"))) {
11
  void
12
  __throw_bad_exception(void) __attribute__((__noreturn__));
13
  void
14
  __throw_bad_alloc(void) __attribute__((__noreturn__));
15
  void
16
  __throw_bad_cast(void) __attribute__((__noreturn__));
17
  void
18
  __throw_bad_typeid(void) __attribute__((__noreturn__));
19
  void
20
  __throw_logic_error(const char*) __attribute__((__noreturn__));
21
  void
22
  __throw_domain_error(const char*) __attribute__((__noreturn__));
23
  void
24
  __throw_invalid_argument(const char*) __attribute__((__noreturn__));
25
  void
26
  __throw_length_error(const char*) __attribute__((__noreturn__));
27
  void
28
  __throw_out_of_range(const char*) __attribute__((__noreturn__));
29
  void
30
  __throw_runtime_error(const char*) __attribute__((__noreturn__));
31
  void
32
  __throw_range_error(const char*) __attribute__((__noreturn__));
33
  void
34
  __throw_overflow_error(const char*) __attribute__((__noreturn__));
35
  void
36
  __throw_underflow_error(const char*) __attribute__((__noreturn__));
37
  void
38
  __throw_ios_failure(const char*) __attribute__((__noreturn__));
39
  void
40
  __throw_system_error(int) __attribute__((__noreturn__));
41
}
42
 
43
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
44
  template
45
    class __normal_iterator;
46
}
47
namespace std __attribute__ ((__visibility__ ("default"))) {
48
  struct __true_type { };
49
  struct __false_type { };
50
  template
51
    struct __truth_type
52
    { typedef __false_type __type; };
53
  template<>
54
    struct __truth_type
55
    { typedef __true_type __type; };
56
  template
57
    struct __traitor
58
    {
59
      enum { __value = bool(_Sp::__value) || bool(_Tp::__value) };
60
      typedef typename __truth_type<__value>::__type __type;
61
    };
62
  template
63
    struct __are_same
64
    {
65
      enum { __value = 0 };
66
      typedef __false_type __type;
67
    };
68
  template
69
    struct __are_same<_Tp, _Tp>
70
    {
71
      enum { __value = 1 };
72
      typedef __true_type __type;
73
    };
74
  template
75
    struct __is_void
76
    {
77
      enum { __value = 0 };
78
      typedef __false_type __type;
79
    };
80
  template<>
81
    struct __is_void
82
    {
83
      enum { __value = 1 };
84
      typedef __true_type __type;
85
    };
86
  template
87
    struct __is_integer
88
    {
89
      enum { __value = 0 };
90
      typedef __false_type __type;
91
    };
92
  template<>
93
    struct __is_integer
94
    {
95
      enum { __value = 1 };
96
      typedef __true_type __type;
97
    };
98
  template<>
99
    struct __is_integer
100
    {
101
      enum { __value = 1 };
102
      typedef __true_type __type;
103
    };
104
  template<>
105
    struct __is_integer
106
    {
107
      enum { __value = 1 };
108
      typedef __true_type __type;
109
    };
110
  template<>
111
    struct __is_integer
112
    {
113
      enum { __value = 1 };
114
      typedef __true_type __type;
115
    };
116
  template<>
117
    struct __is_integer
118
    {
119
      enum { __value = 1 };
120
      typedef __true_type __type;
121
    };
122
  template<>
123
    struct __is_integer
124
    {
125
      enum { __value = 1 };
126
      typedef __true_type __type;
127
    };
128
  template<>
129
    struct __is_integer
130
    {
131
      enum { __value = 1 };
132
      typedef __true_type __type;
133
    };
134
  template<>
135
    struct __is_integer
136
    {
137
      enum { __value = 1 };
138
      typedef __true_type __type;
139
    };
140
  template<>
141
    struct __is_integer
142
    {
143
      enum { __value = 1 };
144
      typedef __true_type __type;
145
    };
146
  template<>
147
    struct __is_integer
148
    {
149
      enum { __value = 1 };
150
      typedef __true_type __type;
151
    };
152
  template<>
153
    struct __is_integer
154
    {
155
      enum { __value = 1 };
156
      typedef __true_type __type;
157
    };
158
  template<>
159
    struct __is_integer
160
    {
161
      enum { __value = 1 };
162
      typedef __true_type __type;
163
    };
164
  template<>
165
    struct __is_integer
166
    {
167
      enum { __value = 1 };
168
      typedef __true_type __type;
169
    };
170
  template
171
    struct __is_floating
172
    {
173
      enum { __value = 0 };
174
      typedef __false_type __type;
175
    };
176
  template<>
177
    struct __is_floating
178
    {
179
      enum { __value = 1 };
180
      typedef __true_type __type;
181
    };
182
  template<>
183
    struct __is_floating
184
    {
185
      enum { __value = 1 };
186
      typedef __true_type __type;
187
    };
188
  template<>
189
    struct __is_floating
190
    {
191
      enum { __value = 1 };
192
      typedef __true_type __type;
193
    };
194
  template
195
    struct __is_pointer
196
    {
197
      enum { __value = 0 };
198
      typedef __false_type __type;
199
    };
200
  template
201
    struct __is_pointer<_Tp*>
202
    {
203
      enum { __value = 1 };
204
      typedef __true_type __type;
205
    };
206
  template
207
    struct __is_normal_iterator
208
    {
209
      enum { __value = 0 };
210
      typedef __false_type __type;
211
    };
212
  template
213
    struct __is_normal_iterator< __gnu_cxx::__normal_iterator<_Iterator,
214
             _Container> >
215
    {
216
      enum { __value = 1 };
217
      typedef __true_type __type;
218
    };
219
  template
220
    struct __is_arithmetic
221
    : public __traitor<__is_integer<_Tp>, __is_floating<_Tp> >
222
    { };
223
  template
224
    struct __is_fundamental
225
    : public __traitor<__is_void<_Tp>, __is_arithmetic<_Tp> >
226
    { };
227
  template
228
    struct __is_scalar
229
    : public __traitor<__is_arithmetic<_Tp>, __is_pointer<_Tp> >
230
    { };
231
  template
232
    struct __is_char
233
    {
234
      enum { __value = 0 };
235
      typedef __false_type __type;
236
    };
237
  template<>
238
    struct __is_char
239
    {
240
      enum { __value = 1 };
241
      typedef __true_type __type;
242
    };
243
  template<>
244
    struct __is_char
245
    {
246
      enum { __value = 1 };
247
      typedef __true_type __type;
248
    };
249
  template
250
    struct __is_byte
251
    {
252
      enum { __value = 0 };
253
      typedef __false_type __type;
254
    };
255
  template<>
256
    struct __is_byte
257
    {
258
      enum { __value = 1 };
259
      typedef __true_type __type;
260
    };
261
  template<>
262
    struct __is_byte
263
    {
264
      enum { __value = 1 };
265
      typedef __true_type __type;
266
    };
267
  template<>
268
    struct __is_byte
269
    {
270
      enum { __value = 1 };
271
      typedef __true_type __type;
272
    };
273
  template
274
    struct __is_move_iterator
275
    {
276
      enum { __value = 0 };
277
      typedef __false_type __type;
278
    };
279
}
280
 
281
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
282
  template
283
    struct __enable_if
284
    { };
285
  template
286
    struct __enable_if
287
    { typedef _Tp __type; };
288
  template
289
    struct __conditional_type
290
    { typedef _Iftrue __type; };
291
  template
292
    struct __conditional_type
293
    { typedef _Iffalse __type; };
294
  template
295
    struct __add_unsigned
296
    {
297
    private:
298
      typedef __enable_if::__value, _Tp> __if_type;
299
    public:
300
      typedef typename __if_type::__type __type;
301
    };
302
  template<>
303
    struct __add_unsigned
304
    { typedef unsigned char __type; };
305
  template<>
306
    struct __add_unsigned
307
    { typedef unsigned char __type; };
308
  template<>
309
    struct __add_unsigned
310
    { typedef unsigned short __type; };
311
  template<>
312
    struct __add_unsigned
313
    { typedef unsigned int __type; };
314
  template<>
315
    struct __add_unsigned
316
    { typedef unsigned long __type; };
317
  template<>
318
    struct __add_unsigned
319
    { typedef unsigned long long __type; };
320
  template<>
321
    struct __add_unsigned;
322
  template<>
323
    struct __add_unsigned;
324
  template
325
    struct __remove_unsigned
326
    {
327
    private:
328
      typedef __enable_if::__value, _Tp> __if_type;
329
    public:
330
      typedef typename __if_type::__type __type;
331
    };
332
  template<>
333
    struct __remove_unsigned
334
    { typedef signed char __type; };
335
  template<>
336
    struct __remove_unsigned
337
    { typedef signed char __type; };
338
  template<>
339
    struct __remove_unsigned
340
    { typedef short __type; };
341
  template<>
342
    struct __remove_unsigned
343
    { typedef int __type; };
344
  template<>
345
    struct __remove_unsigned
346
    { typedef long __type; };
347
  template<>
348
    struct __remove_unsigned
349
    { typedef long long __type; };
350
  template<>
351
    struct __remove_unsigned;
352
  template<>
353
    struct __remove_unsigned;
354
  template
355
    inline bool
356
    __is_null_pointer(_Type* __ptr)
357
    { return __ptr == 0; }
358
  template
359
    inline bool
360
    __is_null_pointer(_Type)
361
    { return false; }
362
  template::__value>
363
    struct __promote
364
    { typedef double __type; };
365
  template
366
    struct __promote<_Tp, false>
367
    { typedef _Tp __type; };
368
  template
369
    struct __promote_2
370
    {
371
    private:
372
      typedef typename __promote<_Tp>::__type __type1;
373
      typedef typename __promote<_Up>::__type __type2;
374
    public:
375
      typedef __typeof__(__type1() + __type2()) __type;
376
    };
377
  template
378
    struct __promote_3
379
    {
380
    private:
381
      typedef typename __promote<_Tp>::__type __type1;
382
      typedef typename __promote<_Up>::__type __type2;
383
      typedef typename __promote<_Vp>::__type __type3;
384
    public:
385
      typedef __typeof__(__type1() + __type2() + __type3()) __type;
386
    };
387
  template
388
    struct __promote_4
389
    {
390
    private:
391
      typedef typename __promote<_Tp>::__type __type1;
392
      typedef typename __promote<_Up>::__type __type2;
393
      typedef typename __promote<_Vp>::__type __type3;
394
      typedef typename __promote<_Wp>::__type __type4;
395
    public:
396
      typedef __typeof__(__type1() + __type2() + __type3() + __type4()) __type;
397
    };
398
}
399
 
400
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
401
  template
402
    struct __numeric_traits_integer
403
    {
404
      static const _Value __min = (((_Value)(-1) < 0) ? (_Value)1 << (sizeof(_Value) * 8 - ((_Value)(-1) < 0)) : (_Value)0);
405
      static const _Value __max = (((_Value)(-1) < 0) ? (((((_Value)1 << ((sizeof(_Value) * 8 - ((_Value)(-1) < 0)) - 1)) - 1) << 1) + 1) : ~(_Value)0);
406
      static const bool __is_signed = ((_Value)(-1) < 0);
407
      static const int __digits = (sizeof(_Value) * 8 - ((_Value)(-1) < 0));
408
    };
409
  template
410
    const _Value __numeric_traits_integer<_Value>::__min;
411
  template
412
    const _Value __numeric_traits_integer<_Value>::__max;
413
  template
414
    const bool __numeric_traits_integer<_Value>::__is_signed;
415
  template
416
    const int __numeric_traits_integer<_Value>::__digits;
417
  template
418
    struct __numeric_traits_floating
419
    {
420
      static const int __max_digits10 = (2 + (std::__are_same<_Value, float>::__value ? 24 : std::__are_same<_Value, double>::__value ? 53 : 64) * 3010 / 10000);
421
      static const bool __is_signed = true;
422
      static const int __digits10 = (std::__are_same<_Value, float>::__value ? 6 : std::__are_same<_Value, double>::__value ? 15 : 18);
423
      static const int __max_exponent10 = (std::__are_same<_Value, float>::__value ? 38 : std::__are_same<_Value, double>::__value ? 308 : 4932);
424
    };
425
  template
426
    const int __numeric_traits_floating<_Value>::__max_digits10;
427
  template
428
    const bool __numeric_traits_floating<_Value>::__is_signed;
429
  template
430
    const int __numeric_traits_floating<_Value>::__digits10;
431
  template
432
    const int __numeric_traits_floating<_Value>::__max_exponent10;
433
  template
434
    struct __numeric_traits
435
    : public __conditional_type::__value,
436
    __numeric_traits_integer<_Value>,
437
    __numeric_traits_floating<_Value> >::__type
438
    { };
439
}
440
 
441
 
442
namespace std __attribute__ ((__visibility__ ("default"))) {
443
  template
444
    inline void
445
    swap(_Tp& __a, _Tp& __b)
446
    {
447
 
448
      _Tp __tmp = (__a);
449
      __a = (__b);
450
      __b = (__tmp);
451
    }
452
  template
453
    inline void
454
    swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
455
    {
456
      for (size_t __n = 0; __n < _Nm; ++__n)
457
 swap(__a[__n], __b[__n]);
458
    }
459
}
460
namespace std __attribute__ ((__visibility__ ("default"))) {
461
  template
462
    struct pair
463
    {
464
      typedef _T1 first_type;
465
      typedef _T2 second_type;
466
      _T1 first;
467
      _T2 second;
468
      pair()
469
      : first(), second() { }
470
      pair(const _T1& __a, const _T2& __b)
471
      : first(__a), second(__b) { }
472
      template
473
        pair(const pair<_U1, _U2>& __p)
474
 : first(__p.first),
475
   second(__p.second) { }
476
    };
477
  template
478
    inline bool
479
    operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
480
    { return __x.first == __y.first && __x.second == __y.second; }
481
  template
482
    inline bool
483
    operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
484
    { return __x.first < __y.first
485
      || (!(__y.first < __x.first) && __x.second < __y.second); }
486
  template
487
    inline bool
488
    operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
489
    { return !(__x == __y); }
490
  template
491
    inline bool
492
    operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
493
    { return __y < __x; }
494
  template
495
    inline bool
496
    operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
497
    { return !(__y < __x); }
498
  template
499
    inline bool
500
    operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
501
    { return !(__x < __y); }
502
  template
503
    inline pair<_T1, _T2>
504
    make_pair(_T1 __x, _T2 __y)
505
    { return pair<_T1, _T2>(__x, __y); }
506
}
507
 
508
 
509
namespace std __attribute__ ((__visibility__ ("default"))) {
510
  struct input_iterator_tag { };
511
  struct output_iterator_tag { };
512
  struct forward_iterator_tag : public input_iterator_tag { };
513
  struct bidirectional_iterator_tag : public forward_iterator_tag { };
514
  struct random_access_iterator_tag : public bidirectional_iterator_tag { };
515
  template
516
           typename _Pointer = _Tp*, typename _Reference = _Tp&>
517
    struct iterator
518
    {
519
      typedef _Category iterator_category;
520
      typedef _Tp value_type;
521
      typedef _Distance difference_type;
522
      typedef _Pointer pointer;
523
      typedef _Reference reference;
524
    };
525
  template
526
    struct iterator_traits
527
    {
528
      typedef typename _Iterator::iterator_category iterator_category;
529
      typedef typename _Iterator::value_type value_type;
530
      typedef typename _Iterator::difference_type difference_type;
531
      typedef typename _Iterator::pointer pointer;
532
      typedef typename _Iterator::reference reference;
533
    };
534
  template
535
    struct iterator_traits<_Tp*>
536
    {
537
      typedef random_access_iterator_tag iterator_category;
538
      typedef _Tp value_type;
539
      typedef ptrdiff_t difference_type;
540
      typedef _Tp* pointer;
541
      typedef _Tp& reference;
542
    };
543
  template
544
    struct iterator_traits
545
    {
546
      typedef random_access_iterator_tag iterator_category;
547
      typedef _Tp value_type;
548
      typedef ptrdiff_t difference_type;
549
      typedef const _Tp* pointer;
550
      typedef const _Tp& reference;
551
    };
552
  template
553
    inline typename iterator_traits<_Iter>::iterator_category
554
    __iterator_category(const _Iter&)
555
    { return typename iterator_traits<_Iter>::iterator_category(); }
556
}
557
 
558
namespace std __attribute__ ((__visibility__ ("default"))) {
559
  template
560
    inline typename iterator_traits<_InputIterator>::difference_type
561
    __distance(_InputIterator __first, _InputIterator __last,
562
               input_iterator_tag)
563
    {
564
 
565
      typename iterator_traits<_InputIterator>::difference_type __n = 0;
566
      while (__first != __last)
567
 {
568
   ++__first;
569
   ++__n;
570
 }
571
      return __n;
572
    }
573
  template
574
    inline typename iterator_traits<_RandomAccessIterator>::difference_type
575
    __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
576
               random_access_iterator_tag)
577
    {
578
 
579
      return __last - __first;
580
    }
581
  template
582
    inline typename iterator_traits<_InputIterator>::difference_type
583
    distance(_InputIterator __first, _InputIterator __last)
584
    {
585
      return std::__distance(__first, __last,
586
        std::__iterator_category(__first));
587
    }
588
  template
589
    inline void
590
    __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
591
    {
592
 
593
      while (__n--)
594
 ++__i;
595
    }
596
  template
597
    inline void
598
    __advance(_BidirectionalIterator& __i, _Distance __n,
599
       bidirectional_iterator_tag)
600
    {
601
 
602
      if (__n > 0)
603
        while (__n--)
604
   ++__i;
605
      else
606
        while (__n++)
607
   --__i;
608
    }
609
  template
610
    inline void
611
    __advance(_RandomAccessIterator& __i, _Distance __n,
612
              random_access_iterator_tag)
613
    {
614
 
615
      __i += __n;
616
    }
617
  template
618
    inline void
619
    advance(_InputIterator& __i, _Distance __n)
620
    {
621
      typename iterator_traits<_InputIterator>::difference_type __d = __n;
622
      std::__advance(__i, __d, std::__iterator_category(__i));
623
    }
624
}
625
namespace std __attribute__ ((__visibility__ ("default"))) {
626
  template
627
    class reverse_iterator
628
    : public iterator::iterator_category,
629
        typename iterator_traits<_Iterator>::value_type,
630
        typename iterator_traits<_Iterator>::difference_type,
631
        typename iterator_traits<_Iterator>::pointer,
632
                      typename iterator_traits<_Iterator>::reference>
633
    {
634
    protected:
635
      _Iterator current;
636
    public:
637
      typedef _Iterator iterator_type;
638
      typedef typename iterator_traits<_Iterator>::difference_type
639
              difference_type;
640
      typedef typename iterator_traits<_Iterator>::reference reference;
641
      typedef typename iterator_traits<_Iterator>::pointer pointer;
642
    public:
643
      reverse_iterator() : current() { }
644
      explicit
645
      reverse_iterator(iterator_type __x) : current(__x) { }
646
      reverse_iterator(const reverse_iterator& __x)
647
      : current(__x.current) { }
648
      template
649
        reverse_iterator(const reverse_iterator<_Iter>& __x)
650
 : current(__x.base()) { }
651
      iterator_type
652
      base() const
653
      { return current; }
654
      reference
655
      operator*() const
656
      {
657
 _Iterator __tmp = current;
658
 return *--__tmp;
659
      }
660
      pointer
661
      operator->() const
662
      { return &(operator*()); }
663
      reverse_iterator&
664
      operator++()
665
      {
666
 --current;
667
 return *this;
668
      }
669
      reverse_iterator
670
      operator++(int)
671
      {
672
 reverse_iterator __tmp = *this;
673
 --current;
674
 return __tmp;
675
      }
676
      reverse_iterator&
677
      operator--()
678
      {
679
 ++current;
680
 return *this;
681
      }
682
      reverse_iterator
683
      operator--(int)
684
      {
685
 reverse_iterator __tmp = *this;
686
 ++current;
687
 return __tmp;
688
      }
689
      reverse_iterator
690
      operator+(difference_type __n) const
691
      { return reverse_iterator(current - __n); }
692
      reverse_iterator&
693
      operator+=(difference_type __n)
694
      {
695
 current -= __n;
696
 return *this;
697
      }
698
      reverse_iterator
699
      operator-(difference_type __n) const
700
      { return reverse_iterator(current + __n); }
701
      reverse_iterator&
702
      operator-=(difference_type __n)
703
      {
704
 current += __n;
705
 return *this;
706
      }
707
      reference
708
      operator[](difference_type __n) const
709
      { return *(*this + __n); }
710
    };
711
  template
712
    inline bool
713
    operator==(const reverse_iterator<_Iterator>& __x,
714
        const reverse_iterator<_Iterator>& __y)
715
    { return __x.base() == __y.base(); }
716
  template
717
    inline bool
718
    operator<(const reverse_iterator<_Iterator>& __x,
719
       const reverse_iterator<_Iterator>& __y)
720
    { return __y.base() < __x.base(); }
721
  template
722
    inline bool
723
    operator!=(const reverse_iterator<_Iterator>& __x,
724
        const reverse_iterator<_Iterator>& __y)
725
    { return !(__x == __y); }
726
  template
727
    inline bool
728
    operator>(const reverse_iterator<_Iterator>& __x,
729
       const reverse_iterator<_Iterator>& __y)
730
    { return __y < __x; }
731
  template
732
    inline bool
733
    operator<=(const reverse_iterator<_Iterator>& __x,
734
        const reverse_iterator<_Iterator>& __y)
735
    { return !(__y < __x); }
736
  template
737
    inline bool
738
    operator>=(const reverse_iterator<_Iterator>& __x,
739
        const reverse_iterator<_Iterator>& __y)
740
    { return !(__x < __y); }
741
  template
742
    inline typename reverse_iterator<_Iterator>::difference_type
743
    operator-(const reverse_iterator<_Iterator>& __x,
744
       const reverse_iterator<_Iterator>& __y)
745
    { return __y.base() - __x.base(); }
746
  template
747
    inline reverse_iterator<_Iterator>
748
    operator+(typename reverse_iterator<_Iterator>::difference_type __n,
749
       const reverse_iterator<_Iterator>& __x)
750
    { return reverse_iterator<_Iterator>(__x.base() - __n); }
751
  template
752
    inline bool
753
    operator==(const reverse_iterator<_IteratorL>& __x,
754
        const reverse_iterator<_IteratorR>& __y)
755
    { return __x.base() == __y.base(); }
756
  template
757
    inline bool
758
    operator<(const reverse_iterator<_IteratorL>& __x,
759
       const reverse_iterator<_IteratorR>& __y)
760
    { return __y.base() < __x.base(); }
761
  template
762
    inline bool
763
    operator!=(const reverse_iterator<_IteratorL>& __x,
764
        const reverse_iterator<_IteratorR>& __y)
765
    { return !(__x == __y); }
766
  template
767
    inline bool
768
    operator>(const reverse_iterator<_IteratorL>& __x,
769
       const reverse_iterator<_IteratorR>& __y)
770
    { return __y < __x; }
771
  template
772
    inline bool
773
    operator<=(const reverse_iterator<_IteratorL>& __x,
774
        const reverse_iterator<_IteratorR>& __y)
775
    { return !(__y < __x); }
776
  template
777
    inline bool
778
    operator>=(const reverse_iterator<_IteratorL>& __x,
779
        const reverse_iterator<_IteratorR>& __y)
780
    { return !(__x < __y); }
781
  template
782
    inline typename reverse_iterator<_IteratorL>::difference_type
783
    operator-(const reverse_iterator<_IteratorL>& __x,
784
       const reverse_iterator<_IteratorR>& __y)
785
    { return __y.base() - __x.base(); }
786
  template
787
    class back_insert_iterator
788
    : public iterator
789
    {
790
    protected:
791
      _Container* container;
792
    public:
793
      typedef _Container container_type;
794
      explicit
795
      back_insert_iterator(_Container& __x) : container(&__x) { }
796
      back_insert_iterator&
797
      operator=(typename _Container::const_reference __value)
798
      {
799
 container->push_back(__value);
800
 return *this;
801
      }
802
      back_insert_iterator&
803
      operator*()
804
      { return *this; }
805
      back_insert_iterator&
806
      operator++()
807
      { return *this; }
808
      back_insert_iterator
809
      operator++(int)
810
      { return *this; }
811
    };
812
  template
813
    inline back_insert_iterator<_Container>
814
    back_inserter(_Container& __x)
815
    { return back_insert_iterator<_Container>(__x); }
816
  template
817
    class front_insert_iterator
818
    : public iterator
819
    {
820
    protected:
821
      _Container* container;
822
    public:
823
      typedef _Container container_type;
824
      explicit front_insert_iterator(_Container& __x) : container(&__x) { }
825
      front_insert_iterator&
826
      operator=(typename _Container::const_reference __value)
827
      {
828
 container->push_front(__value);
829
 return *this;
830
      }
831
      front_insert_iterator&
832
      operator*()
833
      { return *this; }
834
      front_insert_iterator&
835
      operator++()
836
      { return *this; }
837
      front_insert_iterator
838
      operator++(int)
839
      { return *this; }
840
    };
841
  template
842
    inline front_insert_iterator<_Container>
843
    front_inserter(_Container& __x)
844
    { return front_insert_iterator<_Container>(__x); }
845
  template
846
    class insert_iterator
847
    : public iterator
848
    {
849
    protected:
850
      _Container* container;
851
      typename _Container::iterator iter;
852
    public:
853
      typedef _Container container_type;
854
      insert_iterator(_Container& __x, typename _Container::iterator __i)
855
      : container(&__x), iter(__i) {}
856
      insert_iterator&
857
      operator=(typename _Container::const_reference __value)
858
      {
859
 iter = container->insert(iter, __value);
860
 ++iter;
861
 return *this;
862
      }
863
      insert_iterator&
864
      operator*()
865
      { return *this; }
866
      insert_iterator&
867
      operator++()
868
      { return *this; }
869
      insert_iterator&
870
      operator++(int)
871
      { return *this; }
872
    };
873
  template
874
    inline insert_iterator<_Container>
875
    inserter(_Container& __x, _Iterator __i)
876
    {
877
      return insert_iterator<_Container>(__x,
878
      typename _Container::iterator(__i));
879
    }
880
}
881
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
882
  using std::iterator_traits;
883
  using std::iterator;
884
  template
885
    class __normal_iterator
886
    {
887
    protected:
888
      _Iterator _M_current;
889
    public:
890
      typedef _Iterator iterator_type;
891
      typedef typename iterator_traits<_Iterator>::iterator_category
892
                                                             iterator_category;
893
      typedef typename iterator_traits<_Iterator>::value_type value_type;
894
      typedef typename iterator_traits<_Iterator>::difference_type
895
                                                             difference_type;
896
      typedef typename iterator_traits<_Iterator>::reference reference;
897
      typedef typename iterator_traits<_Iterator>::pointer pointer;
898
      __normal_iterator() : _M_current(_Iterator()) { }
899
      explicit
900
      __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
901
      template
902
        __normal_iterator(const __normal_iterator<_Iter,
903
     typename __enable_if<
904
              (std::__are_same<_Iter, typename _Container::pointer>::__value),
905
        _Container>::__type>& __i)
906
        : _M_current(__i.base()) { }
907
      reference
908
      operator*() const
909
      { return *_M_current; }
910
      pointer
911
      operator->() const
912
      { return _M_current; }
913
      __normal_iterator&
914
      operator++()
915
      {
916
 ++_M_current;
917
 return *this;
918
      }
919
      __normal_iterator
920
      operator++(int)
921
      { return __normal_iterator(_M_current++); }
922
      __normal_iterator&
923
      operator--()
924
      {
925
 --_M_current;
926
 return *this;
927
      }
928
      __normal_iterator
929
      operator--(int)
930
      { return __normal_iterator(_M_current--); }
931
      reference
932
      operator[](const difference_type& __n) const
933
      { return _M_current[__n]; }
934
      __normal_iterator&
935
      operator+=(const difference_type& __n)
936
      { _M_current += __n; return *this; }
937
      __normal_iterator
938
      operator+(const difference_type& __n) const
939
      { return __normal_iterator(_M_current + __n); }
940
      __normal_iterator&
941
      operator-=(const difference_type& __n)
942
      { _M_current -= __n; return *this; }
943
      __normal_iterator
944
      operator-(const difference_type& __n) const
945
      { return __normal_iterator(_M_current - __n); }
946
      const _Iterator&
947
      base() const
948
      { return _M_current; }
949
    };
950
  template
951
    inline bool
952
    operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
953
        const __normal_iterator<_IteratorR, _Container>& __rhs)
954
    { return __lhs.base() == __rhs.base(); }
955
  template
956
    inline bool
957
    operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
958
        const __normal_iterator<_Iterator, _Container>& __rhs)
959
    { return __lhs.base() == __rhs.base(); }
960
  template
961
    inline bool
962
    operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
963
        const __normal_iterator<_IteratorR, _Container>& __rhs)
964
    { return __lhs.base() != __rhs.base(); }
965
  template
966
    inline bool
967
    operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
968
        const __normal_iterator<_Iterator, _Container>& __rhs)
969
    { return __lhs.base() != __rhs.base(); }
970
  template
971
    inline bool
972
    operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
973
       const __normal_iterator<_IteratorR, _Container>& __rhs)
974
    { return __lhs.base() < __rhs.base(); }
975
  template
976
    inline bool
977
    operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
978
       const __normal_iterator<_Iterator, _Container>& __rhs)
979
    { return __lhs.base() < __rhs.base(); }
980
  template
981
    inline bool
982
    operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
983
       const __normal_iterator<_IteratorR, _Container>& __rhs)
984
    { return __lhs.base() > __rhs.base(); }
985
  template
986
    inline bool
987
    operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
988
       const __normal_iterator<_Iterator, _Container>& __rhs)
989
    { return __lhs.base() > __rhs.base(); }
990
  template
991
    inline bool
992
    operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
993
        const __normal_iterator<_IteratorR, _Container>& __rhs)
994
    { return __lhs.base() <= __rhs.base(); }
995
  template
996
    inline bool
997
    operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
998
        const __normal_iterator<_Iterator, _Container>& __rhs)
999
    { return __lhs.base() <= __rhs.base(); }
1000
  template
1001
    inline bool
1002
    operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1003
        const __normal_iterator<_IteratorR, _Container>& __rhs)
1004
    { return __lhs.base() >= __rhs.base(); }
1005
  template
1006
    inline bool
1007
    operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
1008
        const __normal_iterator<_Iterator, _Container>& __rhs)
1009
    { return __lhs.base() >= __rhs.base(); }
1010
  template
1011
    inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1012
    operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1013
       const __normal_iterator<_IteratorR, _Container>& __rhs)
1014
    { return __lhs.base() - __rhs.base(); }
1015
  template
1016
    inline typename __normal_iterator<_Iterator, _Container>::difference_type
1017
    operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
1018
       const __normal_iterator<_Iterator, _Container>& __rhs)
1019
    { return __lhs.base() - __rhs.base(); }
1020
  template
1021
    inline __normal_iterator<_Iterator, _Container>
1022
    operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
1023
       __n, const __normal_iterator<_Iterator, _Container>& __i)
1024
    { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1025
}
1026
namespace std
1027
{
1028
  namespace __debug { }
1029
}
1030
namespace __gnu_debug
1031
{
1032
  using namespace std::__debug;
1033
}
1034
namespace std __attribute__ ((__visibility__ ("default"))) {
1035
  template
1036
    struct __iter_swap
1037
    {
1038
      template
1039
        static void
1040
        iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
1041
        {
1042
          typedef typename iterator_traits<_ForwardIterator1>::value_type
1043
            _ValueType1;
1044
          _ValueType1 __tmp = (*__a);
1045
          *__a = (*__b);
1046
          *__b = (__tmp);
1047
 }
1048
    };
1049
  template<>
1050
    struct __iter_swap
1051
    {
1052
      template
1053
        static void
1054
        iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
1055
        {
1056
          swap(*__a, *__b);
1057
        }
1058
    };
1059
  template
1060
    inline void
1061
    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
1062
    {
1063
      typedef typename iterator_traits<_ForwardIterator1>::value_type
1064
 _ValueType1;
1065
      typedef typename iterator_traits<_ForwardIterator2>::value_type
1066
 _ValueType2;
1067
 
1068
 
1069
 
1070
 
1071
      typedef typename iterator_traits<_ForwardIterator1>::reference
1072
 _ReferenceType1;
1073
      typedef typename iterator_traits<_ForwardIterator2>::reference
1074
 _ReferenceType2;
1075
      std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
1076
 && __are_same<_ValueType1&, _ReferenceType1>::__value
1077
 && __are_same<_ValueType2&, _ReferenceType2>::__value>::
1078
 iter_swap(__a, __b);
1079
    }
1080
  template
1081
    _ForwardIterator2
1082
    swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
1083
  _ForwardIterator2 __first2)
1084
    {
1085
 
1086
 
1087
      ;
1088
      for (; __first1 != __last1; ++__first1, ++__first2)
1089
 std::iter_swap(__first1, __first2);
1090
      return __first2;
1091
    }
1092
  template
1093
    inline const _Tp&
1094
    min(const _Tp& __a, const _Tp& __b)
1095
    {
1096
 
1097
      if (__b < __a)
1098
 return __b;
1099
      return __a;
1100
    }
1101
  template
1102
    inline const _Tp&
1103
    max(const _Tp& __a, const _Tp& __b)
1104
    {
1105
 
1106
      if (__a < __b)
1107
 return __b;
1108
      return __a;
1109
    }
1110
  template
1111
    inline const _Tp&
1112
    min(const _Tp& __a, const _Tp& __b, _Compare __comp)
1113
    {
1114
      if (__comp(__b, __a))
1115
 return __b;
1116
      return __a;
1117
    }
1118
  template
1119
    inline const _Tp&
1120
    max(const _Tp& __a, const _Tp& __b, _Compare __comp)
1121
    {
1122
      if (__comp(__a, __b))
1123
 return __b;
1124
      return __a;
1125
    }
1126
  template
1127
    bool _IsNormal = __is_normal_iterator<_Iterator>::__value>
1128
    struct __niter_base
1129
    {
1130
      static _Iterator
1131
      __b(_Iterator __it)
1132
      { return __it; }
1133
    };
1134
  template
1135
    struct __niter_base<_Iterator, true>
1136
    {
1137
      static typename _Iterator::iterator_type
1138
      __b(_Iterator __it)
1139
      { return __it.base(); }
1140
    };
1141
  template
1142
    bool _IsMove = __is_move_iterator<_Iterator>::__value>
1143
    struct __miter_base
1144
    {
1145
      static _Iterator
1146
      __b(_Iterator __it)
1147
      { return __it; }
1148
    };
1149
  template
1150
    struct __miter_base<_Iterator, true>
1151
    {
1152
      static typename _Iterator::iterator_type
1153
      __b(_Iterator __it)
1154
      { return __it.base(); }
1155
    };
1156
  template
1157
    struct __copy_move
1158
    {
1159
      template
1160
        static _OI
1161
        __copy_m(_II __first, _II __last, _OI __result)
1162
        {
1163
   for (; __first != __last; ++__result, ++__first)
1164
     *__result = *__first;
1165
   return __result;
1166
 }
1167
    };
1168
  template<>
1169
    struct __copy_move
1170
    {
1171
      template
1172
        static _OI
1173
        __copy_m(_II __first, _II __last, _OI __result)
1174
        {
1175
   typedef typename iterator_traits<_II>::difference_type _Distance;
1176
   for(_Distance __n = __last - __first; __n > 0; --__n)
1177
     {
1178
       *__result = *__first;
1179
       ++__first;
1180
       ++__result;
1181
     }
1182
   return __result;
1183
 }
1184
    };
1185
  template
1186
    struct __copy_move<_IsMove, true, random_access_iterator_tag>
1187
    {
1188
      template
1189
        static _Tp*
1190
        __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
1191
        {
1192
   __builtin_memmove(__result, __first,
1193
       sizeof(_Tp) * (__last - __first));
1194
   return __result + (__last - __first);
1195
 }
1196
    };
1197
  template
1198
    inline _OI
1199
    __copy_move_a(_II __first, _II __last, _OI __result)
1200
    {
1201
      typedef typename iterator_traits<_II>::value_type _ValueTypeI;
1202
      typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
1203
      typedef typename iterator_traits<_II>::iterator_category _Category;
1204
      const bool __simple = (__is_pod(_ValueTypeI)
1205
                      && __is_pointer<_II>::__value
1206
                      && __is_pointer<_OI>::__value
1207
        && __are_same<_ValueTypeI, _ValueTypeO>::__value);
1208
      return std::__copy_move<_IsMove, __simple,
1209
                       _Category>::__copy_m(__first, __last, __result);
1210
    }
1211
  template
1212
    struct char_traits;
1213
  template
1214
    class istreambuf_iterator;
1215
  template
1216
    class ostreambuf_iterator;
1217
  template
1218
    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
1219
      ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
1220
    __copy_move_a2(_CharT*, _CharT*,
1221
     ostreambuf_iterator<_CharT, char_traits<_CharT> >);
1222
  template
1223
    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
1224
      ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
1225
    __copy_move_a2(const _CharT*, const _CharT*,
1226
     ostreambuf_iterator<_CharT, char_traits<_CharT> >);
1227
  template
1228
    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
1229
        _CharT*>::__type
1230
    __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
1231
     istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
1232
  template
1233
    inline _OI
1234
    __copy_move_a2(_II __first, _II __last, _OI __result)
1235
    {
1236
      return _OI(std::__copy_move_a<_IsMove>
1237
   (std::__niter_base<_II>::__b(__first),
1238
    std::__niter_base<_II>::__b(__last),
1239
    std::__niter_base<_OI>::__b(__result)));
1240
    }
1241
  template
1242
    inline _OI
1243
    copy(_II __first, _II __last, _OI __result)
1244
    {
1245
 
1246
 
1247
      ;
1248
      return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
1249
       (std::__miter_base<_II>::__b(__first),
1250
        std::__miter_base<_II>::__b(__last), __result));
1251
    }
1252
  template
1253
    struct __copy_move_backward
1254
    {
1255
      template
1256
        static _BI2
1257
        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
1258
        {
1259
   while (__first != __last)
1260
     *--__result = *--__last;
1261
   return __result;
1262
 }
1263
    };
1264
  template<>
1265
    struct __copy_move_backward
1266
    {
1267
      template
1268
        static _BI2
1269
        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
1270
        {
1271
   typename iterator_traits<_BI1>::difference_type __n;
1272
   for (__n = __last - __first; __n > 0; --__n)
1273
     *--__result = *--__last;
1274
   return __result;
1275
 }
1276
    };
1277
  template
1278
    struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
1279
    {
1280
      template
1281
        static _Tp*
1282
        __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
1283
        {
1284
   const ptrdiff_t _Num = __last - __first;
1285
   __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
1286
   return __result - _Num;
1287
 }
1288
    };
1289
  template
1290
    inline _BI2
1291
    __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
1292
    {
1293
      typedef typename iterator_traits<_BI1>::value_type _ValueType1;
1294
      typedef typename iterator_traits<_BI2>::value_type _ValueType2;
1295
      typedef typename iterator_traits<_BI1>::iterator_category _Category;
1296
      const bool __simple = (__is_pod(_ValueType1)
1297
                      && __is_pointer<_BI1>::__value
1298
                      && __is_pointer<_BI2>::__value
1299
        && __are_same<_ValueType1, _ValueType2>::__value);
1300
      return std::__copy_move_backward<_IsMove, __simple,
1301
                                _Category>::__copy_move_b(__first,
1302
         __last,
1303
         __result);
1304
    }
1305
  template
1306
    inline _BI2
1307
    __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
1308
    {
1309
      return _BI2(std::__copy_move_backward_a<_IsMove>
1310
    (std::__niter_base<_BI1>::__b(__first),
1311
     std::__niter_base<_BI1>::__b(__last),
1312
     std::__niter_base<_BI2>::__b(__result)));
1313
    }
1314
  template
1315
    inline _BI2
1316
    copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
1317
    {
1318
 
1319
 
1320
 
1321
      ;
1322
      return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
1323
       (std::__miter_base<_BI1>::__b(__first),
1324
        std::__miter_base<_BI1>::__b(__last), __result));
1325
    }
1326
  template
1327
    inline typename
1328
    __gnu_cxx::__enable_if::__value, void>::__type
1329
    __fill_a(_ForwardIterator __first, _ForwardIterator __last,
1330
       const _Tp& __value)
1331
    {
1332
      for (; __first != __last; ++__first)
1333
 *__first = __value;
1334
    }
1335
  template
1336
    inline typename
1337
    __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
1338
    __fill_a(_ForwardIterator __first, _ForwardIterator __last,
1339
      const _Tp& __value)
1340
    {
1341
      const _Tp __tmp = __value;
1342
      for (; __first != __last; ++__first)
1343
 *__first = __tmp;
1344
    }
1345
  template
1346
    inline typename
1347
    __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
1348
    __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
1349
    {
1350
      const _Tp __tmp = __c;
1351
      __builtin_memset(__first, static_cast(__tmp),
1352
         __last - __first);
1353
    }
1354
  template
1355
    inline void
1356
    fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
1357
    {
1358
 
1359
      ;
1360
      std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first),
1361
      std::__niter_base<_ForwardIterator>::__b(__last), __value);
1362
    }
1363
  template
1364
    inline typename
1365
    __gnu_cxx::__enable_if::__value, _OutputIterator>::__type
1366
    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
1367
    {
1368
      for (; __n > 0; --__n, ++__first)
1369
 *__first = __value;
1370
      return __first;
1371
    }
1372
  template
1373
    inline typename
1374
    __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
1375
    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
1376
    {
1377
      const _Tp __tmp = __value;
1378
      for (; __n > 0; --__n, ++__first)
1379
 *__first = __tmp;
1380
      return __first;
1381
    }
1382
  template
1383
    inline typename
1384
    __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
1385
    __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
1386
    {
1387
      std::__fill_a(__first, __first + __n, __c);
1388
      return __first + __n;
1389
    }
1390
  template
1391
    inline _OI
1392
    fill_n(_OI __first, _Size __n, const _Tp& __value)
1393
    {
1394
 
1395
      return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first),
1396
     __n, __value));
1397
    }
1398
  template
1399
    struct __equal
1400
    {
1401
      template
1402
        static bool
1403
        equal(_II1 __first1, _II1 __last1, _II2 __first2)
1404
        {
1405
   for (; __first1 != __last1; ++__first1, ++__first2)
1406
     if (!(*__first1 == *__first2))
1407
       return false;
1408
   return true;
1409
 }
1410
    };
1411
  template<>
1412
    struct __equal
1413
    {
1414
      template
1415
        static bool
1416
        equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
1417
        {
1418
   return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
1419
       * (__last1 - __first1));
1420
 }
1421
    };
1422
  template
1423
    inline bool
1424
    __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1425
    {
1426
      typedef typename iterator_traits<_II1>::value_type _ValueType1;
1427
      typedef typename iterator_traits<_II2>::value_type _ValueType2;
1428
      const bool __simple = (__is_integer<_ValueType1>::__value
1429
                      && __is_pointer<_II1>::__value
1430
                      && __is_pointer<_II2>::__value
1431
        && __are_same<_ValueType1, _ValueType2>::__value);
1432
      return std::__equal<__simple>::equal(__first1, __last1, __first2);
1433
    }
1434
  template
1435
    struct __lc_rai
1436
    {
1437
      template
1438
        static _II1
1439
        __newlast1(_II1, _II1 __last1, _II2, _II2)
1440
        { return __last1; }
1441
      template
1442
        static bool
1443
        __cnd2(_II __first, _II __last)
1444
        { return __first != __last; }
1445
    };
1446
  template<>
1447
    struct __lc_rai
1448
    {
1449
      template
1450
        static _RAI1
1451
        __newlast1(_RAI1 __first1, _RAI1 __last1,
1452
     _RAI2 __first2, _RAI2 __last2)
1453
        {
1454
   const typename iterator_traits<_RAI1>::difference_type
1455
     __diff1 = __last1 - __first1;
1456
   const typename iterator_traits<_RAI2>::difference_type
1457
     __diff2 = __last2 - __first2;
1458
   return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1459
 }
1460
      template
1461
        static bool
1462
        __cnd2(_RAI, _RAI)
1463
        { return true; }
1464
    };
1465
  template
1466
    struct __lexicographical_compare
1467
    {
1468
      template
1469
        static bool __lc(_II1, _II1, _II2, _II2);
1470
    };
1471
  template
1472
    template
1473
      bool
1474
      __lexicographical_compare<_BoolType>::
1475
      __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1476
      {
1477
 typedef typename iterator_traits<_II1>::iterator_category _Category1;
1478
 typedef typename iterator_traits<_II2>::iterator_category _Category2;
1479
 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1480
 __last1 = __rai_type::__newlast1(__first1, __last1,
1481
      __first2, __last2);
1482
 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1483
      ++__first1, ++__first2)
1484
   {
1485
     if (*__first1 < *__first2)
1486
       return true;
1487
     if (*__first2 < *__first1)
1488
       return false;
1489
   }
1490
 return __first1 == __last1 && __first2 != __last2;
1491
      }
1492
  template<>
1493
    struct __lexicographical_compare
1494
    {
1495
      template
1496
        static bool
1497
        __lc(const _Tp* __first1, const _Tp* __last1,
1498
      const _Up* __first2, const _Up* __last2)
1499
 {
1500
   const size_t __len1 = __last1 - __first1;
1501
   const size_t __len2 = __last2 - __first2;
1502
   const int __result = __builtin_memcmp(__first1, __first2,
1503
      std::min(__len1, __len2));
1504
   return __result != 0 ? __result < 0 : __len1 < __len2;
1505
 }
1506
    };
1507
  template
1508
    inline bool
1509
    __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1510
      _II2 __first2, _II2 __last2)
1511
    {
1512
      typedef typename iterator_traits<_II1>::value_type _ValueType1;
1513
      typedef typename iterator_traits<_II2>::value_type _ValueType2;
1514
      const bool __simple =
1515
 (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
1516
  && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
1517
  && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
1518
  && __is_pointer<_II1>::__value
1519
  && __is_pointer<_II2>::__value);
1520
      return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1521
           __first2, __last2);
1522
    }
1523
}
1524
namespace std __attribute__ ((__visibility__ ("default"))) {
1525
  template
1526
    inline bool
1527
    equal(_II1 __first1, _II1 __last1, _II2 __first2)
1528
    {
1529
 
1530
 
1531
 
1532
      ;
1533
      return std::__equal_aux(std::__niter_base<_II1>::__b(__first1),
1534
         std::__niter_base<_II1>::__b(__last1),
1535
         std::__niter_base<_II2>::__b(__first2));
1536
    }
1537
  template
1538
    inline bool
1539
    equal(_IIter1 __first1, _IIter1 __last1,
1540
   _IIter2 __first2, _BinaryPredicate __binary_pred)
1541
    {
1542
 
1543
 
1544
      ;
1545
      for (; __first1 != __last1; ++__first1, ++__first2)
1546
 if (!bool(__binary_pred(*__first1, *__first2)))
1547
   return false;
1548
      return true;
1549
    }
1550
  template
1551
    inline bool
1552
    lexicographical_compare(_II1 __first1, _II1 __last1,
1553
       _II2 __first2, _II2 __last2)
1554
    {
1555
      typedef typename iterator_traits<_II1>::value_type _ValueType1;
1556
      typedef typename iterator_traits<_II2>::value_type _ValueType2;
1557
 
1558
 
1559
 
1560
 
1561
      ;
1562
      ;
1563
      return std::__lexicographical_compare_aux
1564
 (std::__niter_base<_II1>::__b(__first1),
1565
  std::__niter_base<_II1>::__b(__last1),
1566
  std::__niter_base<_II2>::__b(__first2),
1567
  std::__niter_base<_II2>::__b(__last2));
1568
    }
1569
  template
1570
    bool
1571
    lexicographical_compare(_II1 __first1, _II1 __last1,
1572
       _II2 __first2, _II2 __last2, _Compare __comp)
1573
    {
1574
      typedef typename iterator_traits<_II1>::iterator_category _Category1;
1575
      typedef typename iterator_traits<_II2>::iterator_category _Category2;
1576
      typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1577
 
1578
 
1579
      ;
1580
      ;
1581
      __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1582
      for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1583
    ++__first1, ++__first2)
1584
 {
1585
   if (__comp(*__first1, *__first2))
1586
     return true;
1587
   if (__comp(*__first2, *__first1))
1588
     return false;
1589
 }
1590
      return __first1 == __last1 && __first2 != __last2;
1591
    }
1592
  template
1593
    pair<_InputIterator1, _InputIterator2>
1594
    mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1595
      _InputIterator2 __first2)
1596
    {
1597
 
1598
 
1599
 
1600
      ;
1601
      while (__first1 != __last1 && *__first1 == *__first2)
1602
        {
1603
   ++__first1;
1604
   ++__first2;
1605
        }
1606
      return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1607
    }
1608
  template
1609
    typename _BinaryPredicate>
1610
    pair<_InputIterator1, _InputIterator2>
1611
    mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1612
      _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1613
    {
1614
 
1615
 
1616
      ;
1617
      while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
1618
        {
1619
   ++__first1;
1620
   ++__first2;
1621
        }
1622
      return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1623
    }
1624
}
1625
 
1626
extern "C++" {
1627
namespace std
1628
{
1629
  class exception
1630
  {
1631
  public:
1632
    exception() throw() { }
1633
    virtual ~exception() throw();
1634
    virtual const char* what() const throw();
1635
  };
1636
  class bad_exception : public exception
1637
  {
1638
  public:
1639
    bad_exception() throw() { }
1640
    virtual ~bad_exception() throw();
1641
    virtual const char* what() const throw();
1642
  };
1643
  typedef void (*terminate_handler) ();
1644
  typedef void (*unexpected_handler) ();
1645
  terminate_handler set_terminate(terminate_handler) throw();
1646
  void terminate() __attribute__ ((__noreturn__));
1647
  unexpected_handler set_unexpected(unexpected_handler) throw();
1648
  void unexpected() __attribute__ ((__noreturn__));
1649
  bool uncaught_exception() throw();
1650
}
1651
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
1652
  void __verbose_terminate_handler();
1653
}
1654
}
1655
extern "C++" {
1656
namespace std
1657
{
1658
  class bad_alloc : public exception
1659
  {
1660
  public:
1661
    bad_alloc() throw() { }
1662
    virtual ~bad_alloc() throw();
1663
    virtual const char* what() const throw();
1664
  };
1665
  struct nothrow_t { };
1666
  extern const nothrow_t nothrow;
1667
  typedef void (*new_handler)();
1668
  new_handler set_new_handler(new_handler) throw();
1669
}
1670
void* operator new(std::size_t) throw (std::bad_alloc);
1671
void* operator new[](std::size_t) throw (std::bad_alloc);
1672
void operator delete(void*) throw();
1673
void operator delete[](void*) throw();
1674
void* operator new(std::size_t, const std::nothrow_t&) throw();
1675
void* operator new[](std::size_t, const std::nothrow_t&) throw();
1676
void operator delete(void*, const std::nothrow_t&) throw();
1677
void operator delete[](void*, const std::nothrow_t&) throw();
1678
inline void* operator new(std::size_t, void* __p) throw() { return __p; }
1679
inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
1680
inline void operator delete (void*, void*) throw() { }
1681
inline void operator delete[](void*, void*) throw() { }
1682
}
1683
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
1684
  using std::size_t;
1685
  using std::ptrdiff_t;
1686
  template
1687
    class new_allocator
1688
    {
1689
    public:
1690
      typedef size_t size_type;
1691
      typedef ptrdiff_t difference_type;
1692
      typedef _Tp* pointer;
1693
      typedef const _Tp* const_pointer;
1694
      typedef _Tp& reference;
1695
      typedef const _Tp& const_reference;
1696
      typedef _Tp value_type;
1697
      template
1698
        struct rebind
1699
        { typedef new_allocator<_Tp1> other; };
1700
      new_allocator() throw() { }
1701
      new_allocator(const new_allocator&) throw() { }
1702
      template
1703
        new_allocator(const new_allocator<_Tp1>&) throw() { }
1704
      ~new_allocator() throw() { }
1705
      pointer
1706
      address(reference __x) const { return &__x; }
1707
      const_pointer
1708
      address(const_reference __x) const { return &__x; }
1709
      pointer
1710
      allocate(size_type __n, const void* = 0)
1711
      {
1712
 if (__builtin_expect(__n > this->max_size(), false))
1713
   std::__throw_bad_alloc();
1714
 return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
1715
      }
1716
      void
1717
      deallocate(pointer __p, size_type)
1718
      { ::operator delete(__p); }
1719
      size_type
1720
      max_size() const throw()
1721
      { return size_t(-1) / sizeof(_Tp); }
1722
      void
1723
      construct(pointer __p, const _Tp& __val)
1724
      { ::new((void *)__p) _Tp(__val); }
1725
      void
1726
      destroy(pointer __p) { __p->~_Tp(); }
1727
    };
1728
  template
1729
    inline bool
1730
    operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
1731
    { return true; }
1732
  template
1733
    inline bool
1734
    operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
1735
    { return false; }
1736
}
1737
namespace std __attribute__ ((__visibility__ ("default"))) {
1738
  template
1739
    class allocator;
1740
  template<>
1741
    class allocator
1742
    {
1743
    public:
1744
      typedef size_t size_type;
1745
      typedef ptrdiff_t difference_type;
1746
      typedef void* pointer;
1747
      typedef const void* const_pointer;
1748
      typedef void value_type;
1749
      template
1750
        struct rebind
1751
        { typedef allocator<_Tp1> other; };
1752
    };
1753
  template
1754
    class allocator: public __gnu_cxx::new_allocator<_Tp>
1755
    {
1756
   public:
1757
      typedef size_t size_type;
1758
      typedef ptrdiff_t difference_type;
1759
      typedef _Tp* pointer;
1760
      typedef const _Tp* const_pointer;
1761
      typedef _Tp& reference;
1762
      typedef const _Tp& const_reference;
1763
      typedef _Tp value_type;
1764
      template
1765
        struct rebind
1766
        { typedef allocator<_Tp1> other; };
1767
      allocator() throw() { }
1768
      allocator(const allocator& __a) throw()
1769
      : __gnu_cxx::new_allocator<_Tp>(__a) { }
1770
      template
1771
        allocator(const allocator<_Tp1>&) throw() { }
1772
      ~allocator() throw() { }
1773
    };
1774
  template
1775
    inline bool
1776
    operator==(const allocator<_T1>&, const allocator<_T2>&)
1777
    { return true; }
1778
  template
1779
    inline bool
1780
    operator==(const allocator<_Tp>&, const allocator<_Tp>&)
1781
    { return true; }
1782
  template
1783
    inline bool
1784
    operator!=(const allocator<_T1>&, const allocator<_T2>&)
1785
    { return false; }
1786
  template
1787
    inline bool
1788
    operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
1789
    { return false; }
1790
  extern template class allocator;
1791
  extern template class allocator;
1792
  template
1793
    struct __alloc_swap
1794
    { static void _S_do_it(_Alloc&, _Alloc&) { } };
1795
  template
1796
    struct __alloc_swap<_Alloc, false>
1797
    {
1798
      static void
1799
      _S_do_it(_Alloc& __one, _Alloc& __two)
1800
      {
1801
 if (__one != __two)
1802
   swap(__one, __two);
1803
      }
1804
    };
1805
  template
1806
    struct __alloc_neq
1807
    {
1808
      static bool
1809
      _S_do_it(const _Alloc&, const _Alloc&)
1810
      { return false; }
1811
    };
1812
  template
1813
    struct __alloc_neq<_Alloc, false>
1814
    {
1815
      static bool
1816
      _S_do_it(const _Alloc& __one, const _Alloc& __two)
1817
      { return __one != __two; }
1818
    };
1819
}
1820
namespace std __attribute__ ((__visibility__ ("default"))) {
1821
  struct _List_node_base
1822
  {
1823
    _List_node_base* _M_next;
1824
    _List_node_base* _M_prev;
1825
    static void
1826
    swap(_List_node_base& __x, _List_node_base& __y);
1827
    void
1828
    transfer(_List_node_base * const __first,
1829
      _List_node_base * const __last);
1830
    void
1831
    reverse();
1832
    void
1833
    hook(_List_node_base * const __position);
1834
    void
1835
    unhook();
1836
  };
1837
  template
1838
    struct _List_node : public _List_node_base
1839
    {
1840
      _Tp _M_data;
1841
    };
1842
  template
1843
    struct _List_iterator
1844
    {
1845
      typedef _List_iterator<_Tp> _Self;
1846
      typedef _List_node<_Tp> _Node;
1847
      typedef ptrdiff_t difference_type;
1848
      typedef std::bidirectional_iterator_tag iterator_category;
1849
      typedef _Tp value_type;
1850
      typedef _Tp* pointer;
1851
      typedef _Tp& reference;
1852
      _List_iterator()
1853
      : _M_node() { }
1854
      explicit
1855
      _List_iterator(_List_node_base* __x)
1856
      : _M_node(__x) { }
1857
      reference
1858
      operator*() const
1859
      { return static_cast<_Node*>(_M_node)->_M_data; }
1860
      pointer
1861
      operator->() const
1862
      { return &static_cast<_Node*>(_M_node)->_M_data; }
1863
      _Self&
1864
      operator++()
1865
      {
1866
 _M_node = _M_node->_M_next;
1867
 return *this;
1868
      }
1869
      _Self
1870
      operator++(int)
1871
      {
1872
 _Self __tmp = *this;
1873
 _M_node = _M_node->_M_next;
1874
 return __tmp;
1875
      }
1876
      _Self&
1877
      operator--()
1878
      {
1879
 _M_node = _M_node->_M_prev;
1880
 return *this;
1881
      }
1882
      _Self
1883
      operator--(int)
1884
      {
1885
 _Self __tmp = *this;
1886
 _M_node = _M_node->_M_prev;
1887
 return __tmp;
1888
      }
1889
      bool
1890
      operator==(const _Self& __x) const
1891
      { return _M_node == __x._M_node; }
1892
      bool
1893
      operator!=(const _Self& __x) const
1894
      { return _M_node != __x._M_node; }
1895
      _List_node_base* _M_node;
1896
    };
1897
  template
1898
    struct _List_const_iterator
1899
    {
1900
      typedef _List_const_iterator<_Tp> _Self;
1901
      typedef const _List_node<_Tp> _Node;
1902
      typedef _List_iterator<_Tp> iterator;
1903
      typedef ptrdiff_t difference_type;
1904
      typedef std::bidirectional_iterator_tag iterator_category;
1905
      typedef _Tp value_type;
1906
      typedef const _Tp* pointer;
1907
      typedef const _Tp& reference;
1908
      _List_const_iterator()
1909
      : _M_node() { }
1910
      explicit
1911
      _List_const_iterator(const _List_node_base* __x)
1912
      : _M_node(__x) { }
1913
      _List_const_iterator(const iterator& __x)
1914
      : _M_node(__x._M_node) { }
1915
      reference
1916
      operator*() const
1917
      { return static_cast<_Node*>(_M_node)->_M_data; }
1918
      pointer
1919
      operator->() const
1920
      { return &static_cast<_Node*>(_M_node)->_M_data; }
1921
      _Self&
1922
      operator++()
1923
      {
1924
 _M_node = _M_node->_M_next;
1925
 return *this;
1926
      }
1927
      _Self
1928
      operator++(int)
1929
      {
1930
 _Self __tmp = *this;
1931
 _M_node = _M_node->_M_next;
1932
 return __tmp;
1933
      }
1934
      _Self&
1935
      operator--()
1936
      {
1937
 _M_node = _M_node->_M_prev;
1938
 return *this;
1939
      }
1940
      _Self
1941
      operator--(int)
1942
      {
1943
 _Self __tmp = *this;
1944
 _M_node = _M_node->_M_prev;
1945
 return __tmp;
1946
      }
1947
      bool
1948
      operator==(const _Self& __x) const
1949
      { return _M_node == __x._M_node; }
1950
      bool
1951
      operator!=(const _Self& __x) const
1952
      { return _M_node != __x._M_node; }
1953
      const _List_node_base* _M_node;
1954
    };
1955
  template
1956
    inline bool
1957
    operator==(const _List_iterator<_Val>& __x,
1958
        const _List_const_iterator<_Val>& __y)
1959
    { return __x._M_node == __y._M_node; }
1960
  template
1961
    inline bool
1962
    operator!=(const _List_iterator<_Val>& __x,
1963
               const _List_const_iterator<_Val>& __y)
1964
    { return __x._M_node != __y._M_node; }
1965
  template
1966
    class _List_base
1967
    {
1968
    protected:
1969
      typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
1970
        _Node_alloc_type;
1971
      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
1972
      struct _List_impl
1973
      : public _Node_alloc_type
1974
      {
1975
 _List_node_base _M_node;
1976
 _List_impl()
1977
 : _Node_alloc_type(), _M_node()
1978
 { }
1979
 _List_impl(const _Node_alloc_type& __a)
1980
 : _Node_alloc_type(__a), _M_node()
1981
 { }
1982
      };
1983
      _List_impl _M_impl;
1984
      _List_node<_Tp>*
1985
      _M_get_node()
1986
      { return _M_impl._Node_alloc_type::allocate(1); }
1987
      void
1988
      _M_put_node(_List_node<_Tp>* __p)
1989
      { _M_impl._Node_alloc_type::deallocate(__p, 1); }
1990
  public:
1991
      typedef _Alloc allocator_type;
1992
      _Node_alloc_type&
1993
      _M_get_Node_allocator()
1994
      { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
1995
      const _Node_alloc_type&
1996
      _M_get_Node_allocator() const
1997
      { return *static_cast(&this->_M_impl); }
1998
      _Tp_alloc_type
1999
      _M_get_Tp_allocator() const
2000
      { return _Tp_alloc_type(_M_get_Node_allocator()); }
2001
      allocator_type
2002
      get_allocator() const
2003
      { return allocator_type(_M_get_Node_allocator()); }
2004
      _List_base()
2005
      : _M_impl()
2006
      { _M_init(); }
2007
      _List_base(const allocator_type& __a)
2008
      : _M_impl(__a)
2009
      { _M_init(); }
2010
      ~_List_base()
2011
      { _M_clear(); }
2012
      void
2013
      _M_clear();
2014
      void
2015
      _M_init()
2016
      {
2017
        this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
2018
        this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
2019
      }
2020
    };
2021
  template >
2022
    class list : protected _List_base<_Tp, _Alloc>
2023
    {
2024
      typedef typename _Alloc::value_type _Alloc_value_type;
2025
 
2026
 
2027
      typedef _List_base<_Tp, _Alloc> _Base;
2028
      typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
2029
    public:
2030
      typedef _Tp value_type;
2031
      typedef typename _Tp_alloc_type::pointer pointer;
2032
      typedef typename _Tp_alloc_type::const_pointer const_pointer;
2033
      typedef typename _Tp_alloc_type::reference reference;
2034
      typedef typename _Tp_alloc_type::const_reference const_reference;
2035
      typedef _List_iterator<_Tp> iterator;
2036
      typedef _List_const_iterator<_Tp> const_iterator;
2037
      typedef std::reverse_iterator const_reverse_iterator;
2038
      typedef std::reverse_iterator reverse_iterator;
2039
      typedef size_t size_type;
2040
      typedef ptrdiff_t difference_type;
2041
      typedef _Alloc allocator_type;
2042
    protected:
2043
      typedef _List_node<_Tp> _Node;
2044
      using _Base::_M_impl;
2045
      using _Base::_M_put_node;
2046
      using _Base::_M_get_node;
2047
      using _Base::_M_get_Tp_allocator;
2048
      using _Base::_M_get_Node_allocator;
2049
      _Node*
2050
      _M_create_node(const value_type& __x)
2051
      {
2052
 _Node* __p = this->_M_get_node();
2053
 try
2054
   {
2055
     _M_get_Tp_allocator().construct(&__p->_M_data, __x);
2056
   }
2057
 catch(...)
2058
   {
2059
     _M_put_node(__p);
2060
     throw;
2061
   }
2062
 return __p;
2063
      }
2064
    public:
2065
      list()
2066
      : _Base() { }
2067
      explicit
2068
      list(const allocator_type& __a)
2069
      : _Base(__a) { }
2070
      explicit
2071
      list(size_type __n, const value_type& __value = value_type(),
2072
    const allocator_type& __a = allocator_type())
2073
      : _Base(__a)
2074
      { _M_fill_initialize(__n, __value); }
2075
      list(const list& __x)
2076
      : _Base(__x._M_get_Node_allocator())
2077
      { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
2078
      template
2079
        list(_InputIterator __first, _InputIterator __last,
2080
      const allocator_type& __a = allocator_type())
2081
        : _Base(__a)
2082
        {
2083
   typedef typename std::__is_integer<_InputIterator>::__type _Integral;
2084
   _M_initialize_dispatch(__first, __last, _Integral());
2085
 }
2086
      list&
2087
      operator=(const list& __x);
2088
      void
2089
      assign(size_type __n, const value_type& __val)
2090
      { _M_fill_assign(__n, __val); }
2091
      template
2092
        void
2093
        assign(_InputIterator __first, _InputIterator __last)
2094
        {
2095
   typedef typename std::__is_integer<_InputIterator>::__type _Integral;
2096
   _M_assign_dispatch(__first, __last, _Integral());
2097
 }
2098
      allocator_type
2099
      get_allocator() const
2100
      { return _Base::get_allocator(); }
2101
      iterator
2102
      begin()
2103
      { return iterator(this->_M_impl._M_node._M_next); }
2104
      const_iterator
2105
      begin() const
2106
      { return const_iterator(this->_M_impl._M_node._M_next); }
2107
      iterator
2108
      end()
2109
      { return iterator(&this->_M_impl._M_node); }
2110
      const_iterator
2111
      end() const
2112
      { return const_iterator(&this->_M_impl._M_node); }
2113
      reverse_iterator
2114
      rbegin()
2115
      { return reverse_iterator(end()); }
2116
      const_reverse_iterator
2117
      rbegin() const
2118
      { return const_reverse_iterator(end()); }
2119
      reverse_iterator
2120
      rend()
2121
      { return reverse_iterator(begin()); }
2122
      const_reverse_iterator
2123
      rend() const
2124
      { return const_reverse_iterator(begin()); }
2125
      bool
2126
      empty() const
2127
      { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
2128
      size_type
2129
      size() const
2130
      { return std::distance(begin(), end()); }
2131
      size_type
2132
      max_size() const
2133
      { return _M_get_Node_allocator().max_size(); }
2134
      void
2135
      resize(size_type __new_size, value_type __x = value_type());
2136
      reference
2137
      front()
2138
      { return *begin(); }
2139
      const_reference
2140
      front() const
2141
      { return *begin(); }
2142
      reference
2143
      back()
2144
      {
2145
 iterator __tmp = end();
2146
 --__tmp;
2147
 return *__tmp;
2148
      }
2149
      const_reference
2150
      back() const
2151
      {
2152
 const_iterator __tmp = end();
2153
 --__tmp;
2154
 return *__tmp;
2155
      }
2156
      void
2157
      push_front(const value_type& __x)
2158
      { this->_M_insert(begin(), __x); }
2159
      void
2160
      pop_front()
2161
      { this->_M_erase(begin()); }
2162
      void
2163
      push_back(const value_type& __x)
2164
      { this->_M_insert(end(), __x); }
2165
      void
2166
      pop_back()
2167
      { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
2168
      iterator
2169
      insert(iterator __position, const value_type& __x);
2170
      void
2171
      insert(iterator __position, size_type __n, const value_type& __x)
2172
      {
2173
 list __tmp(__n, __x, _M_get_Node_allocator());
2174
 splice(__position, __tmp);
2175
      }
2176
      template
2177
        void
2178
        insert(iterator __position, _InputIterator __first,
2179
        _InputIterator __last)
2180
        {
2181
   list __tmp(__first, __last, _M_get_Node_allocator());
2182
   splice(__position, __tmp);
2183
 }
2184
      iterator
2185
      erase(iterator __position);
2186
      iterator
2187
      erase(iterator __first, iterator __last)
2188
      {
2189
 while (__first != __last)
2190
   __first = erase(__first);
2191
 return __last;
2192
      }
2193
      void
2194
      swap(list& __x)
2195
      {
2196
 _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node);
2197
 std::__alloc_swap::
2198
   _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator());
2199
      }
2200
      void
2201
      clear()
2202
      {
2203
        _Base::_M_clear();
2204
        _Base::_M_init();
2205
      }
2206
      void
2207
      splice(iterator __position, list& __x)
2208
      {
2209
 if (!__x.empty())
2210
   {
2211
     _M_check_equal_allocators(__x);
2212
     this->_M_transfer(__position, __x.begin(), __x.end());
2213
   }
2214
      }
2215
      void
2216
      splice(iterator __position, list& __x, iterator __i)
2217
      {
2218
 iterator __j = __i;
2219
 ++__j;
2220
 if (__position == __i || __position == __j)
2221
   return;
2222
 if (this != &__x)
2223
   _M_check_equal_allocators(__x);
2224
 this->_M_transfer(__position, __i, __j);
2225
      }
2226
      void
2227
      splice(iterator __position, list& __x, iterator __first,
2228
      iterator __last)
2229
      {
2230
 if (__first != __last)
2231
   {
2232
     if (this != &__x)
2233
       _M_check_equal_allocators(__x);
2234
     this->_M_transfer(__position, __first, __last);
2235
   }
2236
      }
2237
      void
2238
      remove(const _Tp& __value);
2239
      template
2240
        void
2241
        remove_if(_Predicate);
2242
      void
2243
      unique();
2244
      template
2245
        void
2246
        unique(_BinaryPredicate);
2247
      void
2248
      merge(list& __x);
2249
      template
2250
        void
2251
        merge(list&, _StrictWeakOrdering);
2252
      void
2253
      reverse()
2254
      { this->_M_impl._M_node.reverse(); }
2255
      void
2256
      sort();
2257
      template
2258
        void
2259
        sort(_StrictWeakOrdering);
2260
    protected:
2261
      template
2262
        void
2263
        _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
2264
        { _M_fill_initialize(static_cast(__n), __x); }
2265
      template
2266
        void
2267
        _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
2268
          __false_type)
2269
        {
2270
   for (; __first != __last; ++__first)
2271
     push_back(*__first);
2272
 }
2273
      void
2274
      _M_fill_initialize(size_type __n, const value_type& __x)
2275
      {
2276
 for (; __n > 0; --__n)
2277
   push_back(__x);
2278
      }
2279
      template
2280
        void
2281
        _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
2282
        { _M_fill_assign(__n, __val); }
2283
      template
2284
        void
2285
        _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
2286
      __false_type);
2287
      void
2288
      _M_fill_assign(size_type __n, const value_type& __val);
2289
      void
2290
      _M_transfer(iterator __position, iterator __first, iterator __last)
2291
      { __position._M_node->transfer(__first._M_node, __last._M_node); }
2292
      void
2293
      _M_insert(iterator __position, const value_type& __x)
2294
      {
2295
        _Node* __tmp = _M_create_node(__x);
2296
        __tmp->hook(__position._M_node);
2297
      }
2298
      void
2299
      _M_erase(iterator __position)
2300
      {
2301
        __position._M_node->unhook();
2302
        _Node* __n = static_cast<_Node*>(__position._M_node);
2303
 _M_get_Tp_allocator().destroy(&__n->_M_data);
2304
        _M_put_node(__n);
2305
      }
2306
      void
2307
      _M_check_equal_allocators(list& __x)
2308
      {
2309
 if (std::__alloc_neq::
2310
     _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
2311
   __throw_runtime_error(("list::_M_check_equal_allocators"));
2312
      }
2313
    };
2314
  template
2315
    inline bool
2316
    operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2317
    {
2318
      typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
2319
      const_iterator __end1 = __x.end();
2320
      const_iterator __end2 = __y.end();
2321
      const_iterator __i1 = __x.begin();
2322
      const_iterator __i2 = __y.begin();
2323
      while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
2324
 {
2325
   ++__i1;
2326
   ++__i2;
2327
 }
2328
      return __i1 == __end1 && __i2 == __end2;
2329
    }
2330
  template
2331
    inline bool
2332
    operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2333
    { return std::lexicographical_compare(__x.begin(), __x.end(),
2334
       __y.begin(), __y.end()); }
2335
  template
2336
    inline bool
2337
    operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2338
    { return !(__x == __y); }
2339
  template
2340
    inline bool
2341
    operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2342
    { return __y < __x; }
2343
  template
2344
    inline bool
2345
    operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2346
    { return !(__y < __x); }
2347
  template
2348
    inline bool
2349
    operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2350
    { return !(__x < __y); }
2351
  template
2352
    inline void
2353
    swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2354
    { __x.swap(__y); }
2355
}
2356
namespace std __attribute__ ((__visibility__ ("default"))) {
2357
  template
2358
    void
2359
    _List_base<_Tp, _Alloc>::
2360
    _M_clear()
2361
    {
2362
      typedef _List_node<_Tp> _Node;
2363
      _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
2364
      while (__cur != &this->_M_impl._M_node)
2365
 {
2366
   _Node* __tmp = __cur;
2367
   __cur = static_cast<_Node*>(__cur->_M_next);
2368
   _M_get_Tp_allocator().destroy(&__tmp->_M_data);
2369
   _M_put_node(__tmp);
2370
 }
2371
    }
2372
  template
2373
    typename list<_Tp, _Alloc>::iterator
2374
    list<_Tp, _Alloc>::
2375
    insert(iterator __position, const value_type& __x)
2376
    {
2377
      _Node* __tmp = _M_create_node(__x);
2378
      __tmp->hook(__position._M_node);
2379
      return iterator(__tmp);
2380
    }
2381
  template
2382
    typename list<_Tp, _Alloc>::iterator
2383
    list<_Tp, _Alloc>::
2384
    erase(iterator __position)
2385
    {
2386
      iterator __ret = iterator(__position._M_node->_M_next);
2387
      _M_erase(__position);
2388
      return __ret;
2389
    }
2390
  template
2391
    void
2392
    list<_Tp, _Alloc>::
2393
    resize(size_type __new_size, value_type __x)
2394
    {
2395
      iterator __i = begin();
2396
      size_type __len = 0;
2397
      for (; __i != end() && __len < __new_size; ++__i, ++__len)
2398
        ;
2399
      if (__len == __new_size)
2400
        erase(__i, end());
2401
      else
2402
        insert(end(), __new_size - __len, __x);
2403
    }
2404
  template
2405
    list<_Tp, _Alloc>&
2406
    list<_Tp, _Alloc>::
2407
    operator=(const list& __x)
2408
    {
2409
      if (this != &__x)
2410
 {
2411
   iterator __first1 = begin();
2412
   iterator __last1 = end();
2413
   const_iterator __first2 = __x.begin();
2414
   const_iterator __last2 = __x.end();
2415
   for (; __first1 != __last1 && __first2 != __last2;
2416
        ++__first1, ++__first2)
2417
     *__first1 = *__first2;
2418
   if (__first2 == __last2)
2419
     erase(__first1, __last1);
2420
   else
2421
     insert(__last1, __first2, __last2);
2422
 }
2423
      return *this;
2424
    }
2425
  template
2426
    void
2427
    list<_Tp, _Alloc>::
2428
    _M_fill_assign(size_type __n, const value_type& __val)
2429
    {
2430
      iterator __i = begin();
2431
      for (; __i != end() && __n > 0; ++__i, --__n)
2432
        *__i = __val;
2433
      if (__n > 0)
2434
        insert(end(), __n, __val);
2435
      else
2436
        erase(__i, end());
2437
    }
2438
  template
2439
    template 
2440
      void
2441
      list<_Tp, _Alloc>::
2442
      _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
2443
    __false_type)
2444
      {
2445
        iterator __first1 = begin();
2446
        iterator __last1 = end();
2447
        for (; __first1 != __last1 && __first2 != __last2;
2448
      ++__first1, ++__first2)
2449
          *__first1 = *__first2;
2450
        if (__first2 == __last2)
2451
          erase(__first1, __last1);
2452
        else
2453
          insert(__last1, __first2, __last2);
2454
      }
2455
  template
2456
    void
2457
    list<_Tp, _Alloc>::
2458
    remove(const value_type& __value)
2459
    {
2460
      iterator __first = begin();
2461
      iterator __last = end();
2462
      iterator __extra = __last;
2463
      while (__first != __last)
2464
 {
2465
   iterator __next = __first;
2466
   ++__next;
2467
   if (*__first == __value)
2468
     {
2469
       if (&*__first != &__value)
2470
  _M_erase(__first);
2471
       else
2472
  __extra = __first;
2473
     }
2474
   __first = __next;
2475
 }
2476
      if (__extra != __last)
2477
 _M_erase(__extra);
2478
    }
2479
  template
2480
    void
2481
    list<_Tp, _Alloc>::
2482
    unique()
2483
    {
2484
      iterator __first = begin();
2485
      iterator __last = end();
2486
      if (__first == __last)
2487
 return;
2488
      iterator __next = __first;
2489
      while (++__next != __last)
2490
 {
2491
   if (*__first == *__next)
2492
     _M_erase(__next);
2493
   else
2494
     __first = __next;
2495
   __next = __first;
2496
 }
2497
    }
2498
  template
2499
    void
2500
    list<_Tp, _Alloc>::
2501
    merge(list& __x)
2502
    {
2503
      if (this != &__x)
2504
 {
2505
   _M_check_equal_allocators(__x);
2506
   iterator __first1 = begin();
2507
   iterator __last1 = end();
2508
   iterator __first2 = __x.begin();
2509
   iterator __last2 = __x.end();
2510
   while (__first1 != __last1 && __first2 != __last2)
2511
     if (*__first2 < *__first1)
2512
       {
2513
  iterator __next = __first2;
2514
  _M_transfer(__first1, __first2, ++__next);
2515
  __first2 = __next;
2516
       }
2517
     else
2518
       ++__first1;
2519
   if (__first2 != __last2)
2520
     _M_transfer(__last1, __first2, __last2);
2521
 }
2522
    }
2523
  template
2524
    template 
2525
      void
2526
      list<_Tp, _Alloc>::
2527
      merge(list& __x, _StrictWeakOrdering __comp)
2528
      {
2529
 if (this != &__x)
2530
   {
2531
     _M_check_equal_allocators(__x);
2532
     iterator __first1 = begin();
2533
     iterator __last1 = end();
2534
     iterator __first2 = __x.begin();
2535
     iterator __last2 = __x.end();
2536
     while (__first1 != __last1 && __first2 != __last2)
2537
       if (__comp(*__first2, *__first1))
2538
  {
2539
    iterator __next = __first2;
2540
    _M_transfer(__first1, __first2, ++__next);
2541
    __first2 = __next;
2542
  }
2543
       else
2544
  ++__first1;
2545
     if (__first2 != __last2)
2546
       _M_transfer(__last1, __first2, __last2);
2547
   }
2548
      }
2549
  template
2550
    void
2551
    list<_Tp, _Alloc>::
2552
    sort()
2553
    {
2554
      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
2555
   && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
2556
      {
2557
        list __carry;
2558
        list __tmp[64];
2559
        list * __fill = &__tmp[0];
2560
        list * __counter;
2561
        do
2562
   {
2563
     __carry.splice(__carry.begin(), *this, begin());
2564
     for(__counter = &__tmp[0];
2565
  __counter != __fill && !__counter->empty();
2566
  ++__counter)
2567
       {
2568
  __counter->merge(__carry);
2569
  __carry.swap(*__counter);
2570
       }
2571
     __carry.swap(*__counter);
2572
     if (__counter == __fill)
2573
       ++__fill;
2574
   }
2575
 while ( !empty() );
2576
        for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
2577
          __counter->merge(*(__counter - 1));
2578
        swap( *(__fill - 1) );
2579
      }
2580
    }
2581
  template
2582
    template 
2583
      void
2584
      list<_Tp, _Alloc>::
2585
      remove_if(_Predicate __pred)
2586
      {
2587
        iterator __first = begin();
2588
        iterator __last = end();
2589
        while (__first != __last)
2590
   {
2591
     iterator __next = __first;
2592
     ++__next;
2593
     if (__pred(*__first))
2594
       _M_erase(__first);
2595
     __first = __next;
2596
   }
2597
      }
2598
  template
2599
    template 
2600
      void
2601
      list<_Tp, _Alloc>::
2602
      unique(_BinaryPredicate __binary_pred)
2603
      {
2604
        iterator __first = begin();
2605
        iterator __last = end();
2606
        if (__first == __last)
2607
   return;
2608
        iterator __next = __first;
2609
        while (++__next != __last)
2610
   {
2611
     if (__binary_pred(*__first, *__next))
2612
       _M_erase(__next);
2613
     else
2614
       __first = __next;
2615
     __next = __first;
2616
   }
2617
      }
2618
  template
2619
    template 
2620
      void
2621
      list<_Tp, _Alloc>::
2622
      sort(_StrictWeakOrdering __comp)
2623
      {
2624
 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
2625
     && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
2626
   {
2627
     list __carry;
2628
     list __tmp[64];
2629
     list * __fill = &__tmp[0];
2630
     list * __counter;
2631
     do
2632
       {
2633
  __carry.splice(__carry.begin(), *this, begin());
2634
  for(__counter = &__tmp[0];
2635
      __counter != __fill && !__counter->empty();
2636
      ++__counter)
2637
    {
2638
      __counter->merge(__carry, __comp);
2639
      __carry.swap(*__counter);
2640
    }
2641
  __carry.swap(*__counter);
2642
  if (__counter == __fill)
2643
    ++__fill;
2644
       }
2645
     while ( !empty() );
2646
     for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
2647
       __counter->merge(*(__counter - 1), __comp);
2648
     swap(*(__fill - 1));
2649
   }
2650
      }
2651
}
2652
extern void foobarit(void);
2653
class Game
2654
{
2655
public:
2656
        struct BuildProject
2657
        {
2658
                int posX;
2659
        };
2660
        std::list buildProjects;
2661
};
2662
static Game game;
2663
static std::list::iterator>
2664
erasableBuildProjects;
2665
void *buildProjectSyncStepConcurrently(int id, int localTeam)
2666
{
2667
        __transaction_relaxed {
2668
                std::list::iterator>::iterator it
2669
= erasableBuildProjects.begin();
2670
                foobarit();
2671
                game.buildProjects.erase( (std::list
2672
::iterator) *it);
2673
        }
2674
        return 0;
2675
}
2676
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.