libstdc++
rb_tree_map_/node.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2014 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 rb_tree_map_/node.hpp
38  * Contains an implementation for rb_tree_.
39  */
40 
41 #ifndef PB_DS_RB_TREE_NODE_HPP
42 #define PB_DS_RB_TREE_NODE_HPP
43 
45 
46 namespace __gnu_pbds
47 {
48  namespace detail
49  {
50  /// Node for Red-Black trees.
51  template<typename Value_Type, class Metadata, typename _Alloc>
53  {
54  public:
55  typedef Value_Type value_type;
56  typedef Metadata metadata_type;
57 
58  typedef
59  typename _Alloc::template rebind<
61  Value_Type,
62  Metadata,
63  _Alloc> >::other::pointer
64  node_pointer;
65 
66  typedef
67  typename _Alloc::template rebind<
68  metadata_type>::other::reference
69  metadata_reference;
70 
71  typedef
72  typename _Alloc::template rebind<
73  metadata_type>::other::const_reference
74  metadata_const_reference;
75 
76  bool
77  special() const
78  { return m_red; }
79 
80  metadata_const_reference
81  get_metadata() const
82  { return m_metadata; }
83 
84  metadata_reference
85  get_metadata()
86  { return m_metadata; }
87 
88 #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
89  void
90  trace() const
91  {
92  std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> ")
93  << "(" << m_metadata << ")";
94  }
95 #endif
96 
97  node_pointer m_p_left;
98  node_pointer m_p_right;
99  node_pointer m_p_parent;
100  value_type m_value;
101  bool m_red;
102  metadata_type m_metadata;
103  };
104 
105  template<typename Value_Type, typename _Alloc>
106  struct rb_tree_node_<Value_Type, null_type, _Alloc>
107  {
108  public:
109  typedef Value_Type value_type;
110  typedef null_type metadata_type;
111 
112  typedef
113  typename _Alloc::template rebind<
115  Value_Type,
116  null_type,
117  _Alloc> >::other::pointer
118  node_pointer;
119 
120  bool
121  special() const
122  { return m_red; }
123 
124 #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
125  void
126  trace() const
127  { std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> "); }
128 #endif
129 
130  node_pointer m_p_left;
131  node_pointer m_p_right;
132  node_pointer m_p_parent;
133  value_type m_value;
134  bool m_red;
135  };
136  } // namespace detail
137 } // namespace __gnu_pbds
138 
139 #endif
GNU extensions for policy-based data structures for public use.
Represents no type, or absence of type, for template tricks.
Node for Red-Black trees.