1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006, 2009 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 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
51    template<typename Key,
52	     typename Mapped,
53	     class Cmp_Fn,
54	     template<typename Const_Node_Iterator,
55		      class Node_Iterator,
56		      class Cmp_Fn_,
57		      class Allocator_>
58    class Node_Update,
59	     class Allocator>
60    struct tree_traits<
61      Key,
62      Mapped,
63      Cmp_Fn,
64      Node_Update,
65      ov_tree_tag,
66      Allocator>
67    {
68    private:
69      typedef
70      typename types_traits<
71      Key,
72      Mapped,
73      Allocator,
74      false>::value_type
75      value_type;
76
77    public:
78      typedef
79      typename tree_node_metadata_selector<
80      Key,
81      Mapped,
82      Cmp_Fn,
83      Node_Update,
84      Allocator>::type
85      metadata_type;
86
87      typedef
88      ov_tree_node_const_it_<
89	value_type,
90	metadata_type,
91	Allocator>
92      const_node_iterator;
93
94      typedef
95      ov_tree_node_it_<
96	value_type,
97	metadata_type,
98	Allocator>
99      node_iterator;
100
101      typedef
102      Node_Update<
103	const_node_iterator,
104	node_iterator,
105	Cmp_Fn,
106	Allocator>
107      node_update;
108
109      typedef
110      __gnu_pbds::null_tree_node_update<
111	const_node_iterator,
112	node_iterator,
113	Cmp_Fn,
114	Allocator>*
115      null_node_update_pointer;
116    };
117
118    template<typename Key,
119	     class Cmp_Fn,
120	     template<typename Const_Node_Iterator,
121		      class Node_Iterator,
122		      class Cmp_Fn_,
123		      class Allocator_>
124    class Node_Update,
125	     class Allocator>
126    struct tree_traits<
127      Key,
128      null_mapped_type,
129      Cmp_Fn,
130      Node_Update,
131      ov_tree_tag,
132      Allocator>
133    {
134    private:
135      typedef
136      typename types_traits<
137      Key,
138      null_mapped_type,
139      Allocator,
140      false>::value_type
141      value_type;
142
143    public:
144      typedef
145      typename tree_node_metadata_selector<
146      Key,
147      null_mapped_type,
148      Cmp_Fn,
149      Node_Update,
150      Allocator>::type
151      metadata_type;
152
153      typedef
154      ov_tree_node_const_it_<
155	value_type,
156	metadata_type,
157	Allocator>
158      const_node_iterator;
159
160      typedef const_node_iterator node_iterator;
161
162      typedef
163      Node_Update<
164	const_node_iterator,
165	const_node_iterator,
166	Cmp_Fn,
167	Allocator>
168      node_update;
169
170      typedef
171      __gnu_pbds::null_tree_node_update<
172	const_node_iterator,
173	node_iterator,
174	Cmp_Fn,
175	Allocator>*
176      null_node_update_pointer;
177    };
178
179  } // namespace detail
180} // namespace __gnu_pbds
181
182#endif // #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
183
184