1// -*- C++ -*-
2
3// Copyright (C) 2005-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26
27// Permission to use, copy, modify, sell, and distribute this software
28// is hereby granted without fee, provided that the above copyright
29// notice appears in all copies, and that both that copyright notice
30// and this permission notice appear in supporting documentation. None
31// of the above authors, nor IBM Haifa Research Laboratories, make any
32// representation about the suitability of this software for any
33// purpose. It is provided "as is" without express or implied
34// warranty.
35
36/**
37 * @file ov_tree_map_/traits.hpp
38 * Contains an implementation class for ov_tree_.
39 */
40
41#ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
42#define PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
43
44#include <ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp>
45
46namespace __gnu_pbds
47{
48  namespace detail
49  {
50    /// Tree traits.
51    /// @ingroup traits
52    template<typename Key,
53	     typename Mapped,
54	     class Cmp_Fn,
55	     template<typename Node_CItr,
56		      class Node_Itr,
57		      class Cmp_Fn_,
58		      typename _Alloc_>
59    class Node_Update,
60	     typename _Alloc>
61    struct tree_traits<
62      Key,
63      Mapped,
64      Cmp_Fn,
65      Node_Update,
66      ov_tree_tag,
67      _Alloc>
68    {
69    private:
70      typedef
71      typename types_traits<
72      Key,
73      Mapped,
74      _Alloc,
75      false>::value_type
76      value_type;
77
78    public:
79      typedef
80      typename tree_node_metadata_dispatch<
81      Key,
82      Mapped,
83      Cmp_Fn,
84      Node_Update,
85      _Alloc>::type
86      metadata_type;
87
88      /// This is an iterator to an iterator: it iterates over nodes,
89      /// and de-referencing it returns one of the tree's iterators.
90      typedef
91      ov_tree_node_const_it_<
92	value_type,
93	metadata_type,
94	_Alloc>
95      node_const_iterator;
96
97      typedef
98      ov_tree_node_it_<
99	value_type,
100	metadata_type,
101	_Alloc>
102      node_iterator;
103
104      typedef
105      Node_Update<
106	node_const_iterator,
107	node_iterator,
108	Cmp_Fn,
109	_Alloc>
110      node_update;
111
112      typedef
113      __gnu_pbds::null_node_update<
114	node_const_iterator,
115	node_iterator,
116	Cmp_Fn,
117	_Alloc>*
118      null_node_update_pointer;
119    };
120
121
122    /// Specialization.
123    /// @ingroup traits
124    template<typename Key,
125	     class Cmp_Fn,
126	     template<typename Node_CItr,
127		      class Node_Itr,
128		      class Cmp_Fn_,
129		      typename _Alloc_>
130    class Node_Update,
131	     typename _Alloc>
132    struct tree_traits<
133      Key,
134      null_type,
135      Cmp_Fn,
136      Node_Update,
137      ov_tree_tag,
138      _Alloc>
139    {
140    private:
141      typedef
142      typename types_traits<
143      Key,
144      null_type,
145      _Alloc,
146      false>::value_type
147      value_type;
148
149    public:
150      typedef
151      typename tree_node_metadata_dispatch<
152      Key,
153      null_type,
154      Cmp_Fn,
155      Node_Update,
156      _Alloc>::type
157      metadata_type;
158
159      /// This is an iterator to an iterator: it iterates over nodes,
160      /// and de-referencing it returns one of the tree's iterators.
161      typedef
162      ov_tree_node_const_it_<
163	value_type,
164	metadata_type,
165	_Alloc>
166      node_const_iterator;
167
168      typedef node_const_iterator node_iterator;
169
170      typedef
171      Node_Update<
172	node_const_iterator,
173	node_const_iterator,
174	Cmp_Fn,
175	_Alloc>
176      node_update;
177
178      typedef
179      __gnu_pbds::null_node_update<
180	node_const_iterator,
181	node_iterator,
182	Cmp_Fn,
183	_Alloc>*
184      null_node_update_pointer;
185    };
186  } // namespace detail
187} // namespace __gnu_pbds
188
189#endif // #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
190
191