1// { dg-do compile }
2// { dg-options "-O -fstrict-aliasing -ftree-pre -fno-tree-fre -fno-tree-sra" }
3
4typedef __SIZE_TYPE__ size_t;
5namespace std
6{
7  template < class _T1, class > struct pair
8  {
9    _T1 first;
10  };
11}
12namespace __gnu_cxx
13{
14  template < typename _Tp > class new_allocator
15  {
16  public:
17    typedef size_t size_type;
18    typedef _Tp * pointer;
19    typedef _Tp const_pointer;
20    typedef _Tp & reference;
21    typedef const _Tp & const_reference;
22    template < typename _Tp1 > struct rebind
23    {
24      typedef new_allocator < _Tp1 > other;
25    };
26  };
27}
28namespace std
29{
30template < typename _Tp > class allocator:
31  public __gnu_cxx::new_allocator < _Tp >
32  {};
33  template < typename, typename, typename > struct binary_function;
34  template < typename _Tp > struct less:binary_function < _Tp, _Tp, bool >
35  {};
36}
37namespace __gnu_cxx
38{
39  namespace typelist
40  {
41    struct null_type;
42    template < typename Root > struct node
43    {
44      typedef Root root;
45    };
46    template < typename, typename > struct chain;
47    namespace detail
48    {
49      template < typename, int >struct chain_at_index_;
50      template
51	<
52	typename
53	Hd, typename Tl > struct chain_at_index_ <chain < Hd, Tl >, 0 >
54      {
55	typedef Hd type;
56      };
57      template
58	<
59	typename
60	Hd, typename Tl, int i > struct chain_at_index_ <chain < Hd, Tl >, i >
61      {
62	typedef typename chain_at_index_ < Tl, i - 1 >::type type;
63      };
64    }
65    template < typename Typelist, int i > struct at_index
66    {
67      typedef typename Typelist::root root_type;
68      typedef detail::chain_at_index_ < root_type, i > index_type;
69      typedef typename index_type::type type;
70    };
71    template < typename T1, typename T2 > struct create2
72    {
73      typedef node < chain < T1, chain < T2, null_type > > >type;
74    };
75  }
76}
77namespace std
78{
79  namespace tr1
80  {
81    template < typename _Tp, _Tp __v > struct integral_constant
82    {
83      static const _Tp value = __v;
84    };
85    typedef integral_constant < bool, false > false_type;
86    template < typename, typename > struct is_same:false_type
87    {};
88  }
89}
90using std::tr1::is_same;
91namespace __gnu_pbds
92{
93  struct null_mapped_type;
94  struct rb_tree_tag;
95  namespace detail
96  {
97    template < typename, typename, typename > struct basic_tree_policy_base;
98    template
99      <
100      typename
101      Const_Node_Iterator,
102      typename
103      Allocator
104      >
105      struct
106      basic_tree_policy_base
107      <Const_Node_Iterator, Const_Node_Iterator, Allocator >
108    {};
109  }
110  template
111    < typename, typename, typename, typename > struct null_tree_node_update;
112template < typename Const_Node_Iterator, typename Node_Iterator, typename, typename Allocator > class tree_order_statistics_node_update:
113  detail::basic_tree_policy_base
114    < Const_Node_Iterator, Node_Iterator, Allocator >
115  {
116  public:
117    typedef Allocator allocator_type;
118    typedef typename allocator_type::size_type size_type;
119    typedef size_type metadata_type;
120    typedef Const_Node_Iterator const_node_iterator;
121    typedef Node_Iterator node_iterator;
122    typedef
123      typename
124      allocator_type::template
125      rebind < metadata_type >::other::reference metadata_reference;
126    void operator () (node_iterator, const_node_iterator) const;
127  };
128  template
129    <
130    typename
131    Const_Node_Iterator,
132    class
133    Node_Iterator,
134    class
135    Cmp_Fn,
136    class
137    Allocator
138    >
139    inline
140    void
141    tree_order_statistics_node_update
142    <
143    Const_Node_Iterator,
144    Node_Iterator,
145    Cmp_Fn,
146    Allocator
147    >::operator
148    () (node_iterator node_it, const_node_iterator end_nd_it) const
149  {
150    node_iterator l_child_it;
151    size_type
152      l_rank = (l_child_it == end_nd_it) ? : l_child_it.get_metadata ();
153    node_iterator r_child_it = node_it.get_r_child ();
154    size_type
155      r_rank = (r_child_it == end_nd_it) ? : r_child_it.get_metadata ();
156    const_cast
157      < metadata_reference > (node_it.get_metadata ()) = l_rank + r_rank;
158  }
159  namespace
160  {
161    template < typename, typename, typename, bool > struct value_type_base;
162    template
163      <
164      typename
165      Key,
166      typename
167      Allocator
168      > struct value_type_base <Key, null_mapped_type, Allocator, false >
169    {
170      typedef Key value_type;
171      typedef
172	typename
173	Allocator::template rebind < value_type >::other value_type_allocator;
174      typedef typename value_type_allocator::pointer pointer;
175      typedef typename value_type_allocator::const_pointer const_pointer;
176      typedef typename value_type_allocator::reference reference;
177      typedef typename value_type_allocator::const_reference const_reference;
178    };
179    template
180      <
181      typename
182      Key,
183      typename
184      Mapped, typename Alloc, bool Store_Extra > struct vt_base_selector
185    {
186      typedef value_type_base < Key, Mapped, Alloc, Store_Extra > type;
187    };
188    template
189      <
190      typename
191      Key,
192      typename
193      Mapped,
194      typename
195      Alloc,
196      bool
197      Store_Extra
198      >
199      struct
200      types_traits:vt_base_selector < Key, Mapped, Alloc, Store_Extra >::type
201    {};
202    template < typename, class, class > struct dumconst_node_iterator;
203    template
204      <
205      typename
206      Key,
207      typename
208      Mapped,
209      class,
210      class
211      Node_And_It_Traits, class Allocator > class bin_search_tree_no_data_
212    {
213    protected:
214      typedef
215	typename
216	Allocator::template
217	rebind
218	< typename Node_And_It_Traits::node >::other::pointer node_pointer;
219      typedef
220	typename
221	types_traits
222	< Key, Mapped, Allocator, false >::const_reference const_reference;
223      typedef typename Node_And_It_Traits::point_iterator point_iterator;
224      typedef typename Node_And_It_Traits::node_update node_update;
225      void rotate_right (node_pointer);
226      template
227	<
228	typename
229	Node_Update_ > void apply_update (node_pointer, Node_Update_ *);
230    };
231    template
232      <
233      typename
234      Key,
235      typename
236      Mapped,
237      class
238      Cmp_Fn,
239      class
240      Node_And_It_Traits,
241      class
242      Allocator
243      >
244      void
245      bin_search_tree_no_data_
246      <
247      Key,
248      Mapped,
249      Cmp_Fn, Node_And_It_Traits, Allocator >::rotate_right (node_pointer p_x)
250    {
251      node_pointer p_y = p_x->m_p_parent;
252      p_y->m_p_right = p_x;
253      apply_update (p_x, this);
254      apply_update (p_x->m_p_parent, (node_update *) this);
255    }
256    template
257      <
258      typename
259      Key,
260      typename
261      Mapped,
262      class
263      Cmp_Fn,
264      class
265      Node_And_It_Traits,
266      class
267      Allocator
268      >
269      template
270      <
271      typename
272      Node_Update_
273      >
274      void
275      bin_search_tree_no_data_
276      <
277      Key,
278      Mapped,
279      Cmp_Fn,
280      Node_And_It_Traits,
281      Allocator >::apply_update (node_pointer p_nd, Node_Update_ *)
282    {
283      node_update ()((p_nd), ((0)));
284    }
285  }
286  namespace detail
287  {
288  template < typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename Allocator > class rb_tree_no_data_:
289    bin_search_tree_no_data_
290      < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator >
291    {
292      typedef
293	bin_search_tree_no_data_
294	< Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator > base_type;
295      typedef typename base_type::node_pointer node_pointer;
296    public:
297      typedef typename base_type::const_reference const_reference;
298      typedef typename base_type::point_iterator point_iterator;
299      std::pair < point_iterator, bool > insert (const_reference);
300      void insert_fixup (node_pointer);
301    };
302    template
303      <
304      typename
305      Key,
306      typename
307      Mapped,
308      typename
309      Cmp_Fn,
310      typename
311      Node_And_It_Traits,
312      typename
313      Allocator
314      >
315      std::pair
316      <
317      typename
318      rb_tree_no_data_
319      <
320      Key,
321      Mapped,
322      Cmp_Fn,
323      Node_And_It_Traits,
324      Allocator
325      >::point_iterator,
326      bool
327      >
328      rb_tree_no_data_
329      <
330      Key,
331      Mapped,
332      Cmp_Fn, Node_And_It_Traits, Allocator >::insert (const_reference)
333    {
334      std::pair < point_iterator, bool > ins_pair;
335{
336	insert_fixup (ins_pair.first.m_p_nd);
337      }
338    }
339    template
340      <
341      typename
342      Key,
343      typename
344      Mapped,
345      typename
346      Cmp_Fn,
347      typename
348      Node_And_It_Traits,
349      typename
350      Allocator
351      >
352      void
353      rb_tree_no_data_
354      <
355      Key,
356      Mapped,
357      Cmp_Fn,
358      Node_And_It_Traits, Allocator >::insert_fixup (node_pointer p_nd)
359    {
360{
361{
362{
363	    this->rotate_right (p_nd);
364	  }
365	}
366      }
367    }
368    template
369      <
370      typename,
371      typename, typename, typename, typename > struct container_base_dispatch;
372    template
373      <
374      typename
375      Key,
376      typename
377      Policy_Tl,
378      typename
379      Alloc
380      >
381      struct
382      container_base_dispatch
383      <Key, null_mapped_type, rb_tree_tag, Policy_Tl, Alloc >
384    {
385      typedef __gnu_cxx::typelist::at_index < Policy_Tl, 0 > at0;
386      typedef typename at0::type at0t;
387      typedef __gnu_cxx::typelist::at_index < Policy_Tl, 1 > at1;
388      typedef typename at1::type at1t;
389      typedef
390	rb_tree_no_data_ < Key, null_mapped_type, at0t, at1t, Alloc > type;
391    };
392    template
393      <
394      typename
395      Node_Pointer,
396      typename,
397      typename,
398      typename,
399      typename, typename, bool, class > class bin_search_tree_const_it_
400    {
401    public:
402      Node_Pointer m_p_nd;
403    };
404    template
405      <
406      typename
407      Node,
408      class
409      Const_Iterator,
410      class Iterator, class Allocator > class bin_search_tree_const_node_it_
411    {
412      typedef
413	typename
414	Allocator::template rebind < Node >::other::pointer node_pointer;
415    public:
416      typedef typename Node::metadata_type metadata_type;
417      typedef
418	typename
419	Allocator::template
420	rebind
421	< metadata_type >::other::const_reference const_metadata_reference;
422    bin_search_tree_const_node_it_ (node_pointer p_nd):
423      m_p_nd ((p_nd))
424      {}
425      const_metadata_reference get_metadata ()
426      {
427	return (m_p_nd->get_metadata ());
428      }
429      bin_search_tree_const_node_it_ ()
430      {}
431      bin_search_tree_const_node_it_
432	< Node, Const_Iterator, Iterator, Allocator > get_r_child ()
433      {
434	return ((m_p_nd->m_p_right));
435      }
436      bool operator == (bin_search_tree_const_node_it_)
437      {}
438      node_pointer m_p_nd;
439    };
440    template
441      <
442      typename,
443      typename,
444      class,
445      template
446      <
447      typename,
448      class,
449      class, class > class, class, class > struct bin_search_tree_traits;
450    template
451      <
452      typename
453      Key,
454      class
455      Cmp_Fn,
456      template
457      <
458      typename,
459      class,
460      class,
461      class
462      >
463      class
464      Node_Update,
465      class
466      Node,
467      class
468      Allocator
469      >
470      struct
471      bin_search_tree_traits
472      <Key, null_mapped_type, Cmp_Fn, Node_Update, Node, Allocator >
473    {
474      typedef
475	types_traits < Key, null_mapped_type, Allocator, false > type_traits;
476      typedef Node node;
477      typedef
478	bin_search_tree_const_it_
479	<
480	typename
481	Allocator::template
482	rebind
483	<
484	node
485	>::other::pointer,
486	typename
487	type_traits::value_type,
488	typename
489	type_traits::pointer,
490	typename
491	type_traits::const_pointer,
492	typename
493	type_traits::reference,
494	typename
495	type_traits::const_reference, true, Allocator > const_point_iterator;
496      typedef const_point_iterator point_iterator;
497      typedef
498	bin_search_tree_const_node_it_
499	<
500	Node,
501	const_point_iterator, point_iterator, Allocator > const_node_iterator;
502      typedef const_node_iterator node_iterator;
503      typedef
504	Node_Update
505	< const_node_iterator, node_iterator, Cmp_Fn, Allocator > node_update;
506    };
507    template < typename Node_Update, bool > struct tree_metadata_helper
508    {
509      typedef typename Node_Update::metadata_type type;
510    };
511    template
512      <
513      typename
514      Key,
515      typename
516      Data,
517      class
518      Cmp_Fn,
519      template
520      <
521      typename,
522      class,
523      class,
524      class
525      >
526      class Node_Update, class Allocator > struct tree_node_metadata_selector
527    {
528      typedef
529	dumconst_node_iterator < Key, Data, Allocator > dumconst_node_it;
530      enum
531      {
532	null_update = is_same < Node_Update < dumconst_node_it,
533	dumconst_node_it,
534	Cmp_Fn,
535	Allocator >,
536	null_tree_node_update < dumconst_node_it,
537	dumconst_node_it,
538	Cmp_Fn,
539	Allocator > >::value
540      };
541      typedef
542	typename
543	tree_metadata_helper
544	<
545	Node_Update
546	<
547	dumconst_node_it,
548	dumconst_node_it, Cmp_Fn, Allocator >, null_update >::type type;
549    };
550    template
551      <
552      typename,
553      typename,
554      class,
555      template
556      <
557      typename,
558      class, class, class > class, class, class > struct tree_traits;
559    template < typename Value_Type, class Metadata, class Allocator > struct rb_tree_node_
560    {
561      typedef Metadata metadata_type;
562      typedef
563	typename
564	Allocator::template
565	rebind
566	<
567	rb_tree_node_
568	< Value_Type, Metadata, Allocator > >::other::pointer node_pointer;
569      typedef
570	typename
571	Allocator::template
572	rebind < metadata_type >::other::reference metadata_reference;
573        metadata_reference get_metadata ()
574      {
575	return m_metadata;
576      }
577      node_pointer m_p_right;
578      node_pointer m_p_parent;
579      metadata_type m_metadata;
580    };
581    template
582      <
583      typename
584      Key,
585      typename
586      Mapped,
587      typename
588      Cmp_Fn,
589      template
590      <
591      typename,
592      class,
593      class,
594      class
595      >
596      class
597      Node_Update,
598      typename
599      Allocator
600      >
601      struct
602      tree_traits
603      <Key,
604      Mapped,
605      Cmp_Fn,
606      Node_Update,
607      rb_tree_tag,
608      Allocator
609      >:bin_search_tree_traits
610      <
611      Key,
612      Mapped,
613      Cmp_Fn,
614      Node_Update,
615      rb_tree_node_
616      <
617      typename
618      types_traits
619      <
620      Key,
621      Mapped,
622      Allocator,
623      false
624      >::value_type,
625      typename
626      tree_node_metadata_selector
627      <
628      Key,
629      Mapped, Cmp_Fn, Node_Update, Allocator >::type, Allocator >, Allocator >
630    {};
631  }
632template < typename Key, typename Mapped, typename Tag, typename Policy_Tl, typename Allocator > class container_base:
633  public
634    detail::container_base_dispatch
635    < Key, Mapped, Tag, Policy_Tl, Allocator >::type
636  {};
637template < typename Key, typename Mapped, typename Tag, typename, typename Policy_Tl, typename Allocator > class basic_tree:
638  public
639    container_base < Key, Mapped, Tag, Policy_Tl, Allocator >
640  {};
641  template
642    <
643    typename
644    Key,
645    typename
646    Mapped,
647    typename
648    Cmp_Fn
649    =
650    std::less
651    <
652    Key
653    >,
654    typename
655    Tag
656    =
657    rb_tree_tag,
658    template
659    <
660    typename,
661    typename,
662    typename,
663    typename
664    >
665    class
666    Node_Update
667    =
668    null_tree_node_update,
669    typename
670    Allocator
671    =
672    std::allocator
673    <
674    char
675    > >class
676    tree:public
677    basic_tree
678    <
679    Key,
680    Mapped,
681    Tag,
682    detail::tree_traits
683    <
684    Key,
685    Mapped,
686    Cmp_Fn,
687    Node_Update,
688    Tag,
689    Allocator
690    >,
691    typename
692    __gnu_cxx::typelist::create2
693    <
694    Cmp_Fn,
695    detail::tree_traits
696    < Key, Mapped, Cmp_Fn, Node_Update, Tag, Allocator > >::type, Allocator >
697  {};
698}
699using namespace std;
700using namespace __gnu_pbds;
701typedef
702  tree
703  <
704  int,
705  null_mapped_type,
706  less < int >, rb_tree_tag, tree_order_statistics_node_update > set_t;
707main ()
708{
709  set_t s;
710  s.insert (12);
711}
712