libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file splay_tree_/node.hpp 00038 * Contains an implementation struct for splay_tree_'s node. 00039 */ 00040 00041 #ifndef PB_DS_SPLAY_TREE_NODE_HPP 00042 #define PB_DS_SPLAY_TREE_NODE_HPP 00043 00044 namespace __gnu_pbds 00045 { 00046 namespace detail 00047 { 00048 /// Node for splay tree. 00049 template<typename Value_Type, class Metadata, typename _Alloc> 00050 struct splay_tree_node_ 00051 { 00052 public: 00053 typedef Value_Type value_type; 00054 typedef Metadata metadata_type; 00055 00056 typedef 00057 typename _Alloc::template rebind< 00058 splay_tree_node_<Value_Type, Metadata, _Alloc> >::other::pointer 00059 node_pointer; 00060 00061 typedef 00062 typename _Alloc::template rebind<metadata_type>::other::reference 00063 metadata_reference; 00064 00065 typedef 00066 typename _Alloc::template rebind<metadata_type>::other::const_reference 00067 metadata_const_reference; 00068 00069 #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ 00070 void 00071 trace() const 00072 { std::cout << PB_DS_V2F(m_value) << "(" << m_metadata << ")"; } 00073 #endif 00074 00075 inline bool 00076 special() const 00077 { return m_special; } 00078 00079 inline metadata_const_reference 00080 get_metadata() const 00081 { return m_metadata; } 00082 00083 inline metadata_reference 00084 get_metadata() 00085 { return m_metadata; } 00086 00087 value_type m_value; 00088 bool m_special; 00089 node_pointer m_p_left; 00090 node_pointer m_p_right; 00091 node_pointer m_p_parent; 00092 metadata_type m_metadata; 00093 }; 00094 00095 template<typename Value_Type, typename _Alloc> 00096 struct splay_tree_node_<Value_Type, null_type, _Alloc> 00097 { 00098 public: 00099 typedef Value_Type value_type; 00100 typedef null_type metadata_type; 00101 00102 typedef 00103 typename _Alloc::template rebind< 00104 splay_tree_node_<Value_Type, null_type, _Alloc> >::other::pointer 00105 node_pointer; 00106 00107 inline bool 00108 special() const 00109 { return m_special; } 00110 00111 #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ 00112 void 00113 trace() const 00114 { std::cout << PB_DS_V2F(m_value); } 00115 #endif 00116 00117 node_pointer m_p_left; 00118 node_pointer m_p_right; 00119 node_pointer m_p_parent; 00120 value_type m_value; 00121 bool m_special; 00122 }; 00123 } // namespace detail 00124 } // namespace __gnu_pbds 00125 00126 #endif