17b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// -*- C++ -*- 27b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 37b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Copyright (C) 2005-2014 Free Software Foundation, Inc. 47b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// 57b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// This file is part of the GNU ISO C++ Library. This library is free 67b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// software; you can redistribute it and/or modify it under the terms 77b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// of the GNU General Public License as published by the Free Software 87b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Foundation; either version 3, or (at your option) any later 97b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// version. 107b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 117b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// This library is distributed in the hope that it will be useful, but 127b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// WITHOUT ANY WARRANTY; without even the implied warranty of 137b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 147b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// General Public License for more details. 157b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 167b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Under Section 7 of GPL version 3, you are granted additional 177b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// permissions described in the GCC Runtime Library Exception, version 187b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// 3.1, as published by the Free Software Foundation. 197b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 207b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// You should have received a copy of the GNU General Public License and 217b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// a copy of the GCC Runtime Library Exception along with this program; 227b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 237b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// <http://www.gnu.org/licenses/>. 247b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 257b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 267b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 277b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Permission to use, copy, modify, sell, and distribute this software 287b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// is hereby granted without fee, provided that the above copyright 297b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// notice appears in all copies, and that both that copyright notice 307b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// and this permission notice appear in supporting documentation. None 317b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// of the above authors, nor IBM Haifa Research Laboratories, make any 327b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// representation about the suitability of this software for any 337b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// purpose. It is provided "as is" without express or implied 347b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// warranty. 357b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 367b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh/** 377b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * @file tree_policy/node_metadata_selector.hpp 387b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * Contains an implementation class for trees. 397b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh */ 407b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 417b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#ifndef PB_DS_TREE_NODE_METADATA_DISPATCH_HPP 427b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#define PB_DS_TREE_NODE_METADATA_DISPATCH_HPP 437b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 447b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp> 457b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/types_traits.hpp> 467b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 477b9b0e19b31944fce201a273083eaca38e477580Andrew Hsiehnamespace __gnu_pbds 487b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh{ 497b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh namespace detail 507b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh { 517b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh /** 527b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * @addtogroup traits Traits 537b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * @{ 547b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh */ 557b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 567b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh /// Tree metadata helper. 577b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Node_Update, bool _BTp> 587b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh struct tree_metadata_helper; 597b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 607b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh /// Specialization, false. 617b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Node_Update> 627b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh struct tree_metadata_helper<Node_Update, false> 637b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh { 647b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename Node_Update::metadata_type type; 657b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh }; 667b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 677b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh /// Specialization, true. 687b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Node_Update> 697b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh struct tree_metadata_helper<Node_Update, true> 707b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh { 717b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef null_type type; 727b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh }; 737b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 747b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh /// Tree node metadata dispatch. 757b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Key, 767b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typename Data, 777b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typename Cmp_Fn, 787b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Node_CItr, 797b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typename Const_Iterator, 807b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typename Cmp_Fn_, 817b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typename _Alloc_> 827b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh class Node_Update, 837b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typename _Alloc> 847b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh struct tree_node_metadata_dispatch 857b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh { 867b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh private: 877b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef dumnode_const_iterator<Key, Data, _Alloc> __it_type; 887b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef Node_Update<__it_type, __it_type, Cmp_Fn, _Alloc> __node_u; 897b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef null_node_update<__it_type, __it_type, Cmp_Fn, _Alloc> __nnode_u; 907b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 917b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh enum 927b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh { 937b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh null_update = is_same<__node_u, __nnode_u>::value 947b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh }; 957b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 967b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh public: 977b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename tree_metadata_helper<__node_u, null_update>::type type; 987b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh }; 997b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh //@} 1007b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh } // namespace detail 1017b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh} // namespace __gnu_pbds 1027b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1037b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#endif // #ifndef PB_DS_TREE_NODE_METADATA_DISPATCH_HPP 104