13123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// -*- C++ -*- 23123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 33123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc. 43123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// 53123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// This file is part of the GNU ISO C++ Library. This library is free 63123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// software; you can redistribute it and/or modify it under the terms 73123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// of the GNU General Public License as published by the Free Software 83123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Foundation; either version 3, or (at your option) any later 93123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// version. 103123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 113123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// This library is distributed in the hope that it will be useful, but 123123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// WITHOUT ANY WARRANTY; without even the implied warranty of 133123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 143123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// General Public License for more details. 153123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 163123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Under Section 7 of GPL version 3, you are granted additional 173123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// permissions described in the GCC Runtime Library Exception, version 183123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// 3.1, as published by the Free Software Foundation. 193123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 203123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// You should have received a copy of the GNU General Public License and 213123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// a copy of the GCC Runtime Library Exception along with this program; 223123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 233123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// <http://www.gnu.org/licenses/>. 243123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 253123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 263123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 273123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Permission to use, copy, modify, sell, and distribute this software 283123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// is hereby granted without fee, provided that the above copyright 293123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// notice appears in all copies, and that both that copyright notice 303123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// and this permission notice appear in supporting documentation. None 313123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// of the above authors, nor IBM Haifa Research Laboratories, make any 323123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// representation about the suitability of this software for any 333123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// purpose. It is provided "as is" without express or implied 343123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// warranty. 353123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 363123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh/** 373123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh * @file container_base_dispatch.hpp 383123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh * Contains associative container dispatching. 393123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh */ 403123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 413123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#ifndef PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP 423123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP 433123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 443123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/typelist.h> 453123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 463123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_ASSERT_VALID(X) \ 473123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);) 483123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 493123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_DEBUG_VERIFY(_Cond) \ 503123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ 513123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh _M_message(#_Cond" assertion from %1;:%2;") \ 523123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh ._M_string(__FILE__)._M_integer(__LINE__) \ 533123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh ,__file,__line) 543123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 553123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_CHECK_KEY_EXISTS(_Key) \ 563123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(_Key, __FILE__, __LINE__);) 573123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 583123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_CHECK_KEY_DOES_NOT_EXIST(_Key) \ 593123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(_Key, \ 603123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh __FILE__, __LINE__);) 613123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 623123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_DATA_TRUE_INDICATOR 633123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_V2F(X) (X).first 643123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_V2S(X) (X).second 653123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_EP2VP(X)& ((X)->m_value) 663123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp> 673123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> 683123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp> 693123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp> 703123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp> 713123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp> 723123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp> 733123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp> 743123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_DATA_TRUE_INDICATOR 753123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_V2F 763123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_V2S 773123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_EP2VP 783123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 793123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_DATA_FALSE_INDICATOR 803123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_V2F(X) (X) 813123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_V2S(X) Mapped_Data() 823123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#define PB_DS_EP2VP(X)& ((X)->m_value.first) 833123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp> 843123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> 853123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp> 863123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp> 873123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp> 883123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp> 893123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp> 903123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp> 913123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_DATA_FALSE_INDICATOR 923123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_V2F 933123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_V2S 943123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_EP2VP 953123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 963123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_CHECK_KEY_DOES_NOT_EXIST 973123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_CHECK_KEY_EXISTS 983123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_DEBUG_VERIFY 993123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#undef PB_DS_ASSERT_VALID 1003123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1013123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsiehnamespace __gnu_pbds 1023123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh{ 1033123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsiehnamespace detail 1043123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh{ 1053123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization for list-update map. 1063123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 1073123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, 1083123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 1093123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 1103123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 1113123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 1123123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 1133123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 1143123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 1153123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1163123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 1173123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 1183123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef lu_map<Key, Mapped, at0t, _Alloc, at1t> type; 1193123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 1203123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1213123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization for list-update set. 1223123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename _Alloc, typename Policy_Tl> 1233123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, null_type, _Alloc, list_update_tag, 1243123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 1253123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 1263123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 1273123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 1283123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 1293123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 1303123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 1313123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1323123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 1333123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 1343123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef lu_set<Key, null_type, at0t, _Alloc, at1t> type; 1353123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 1363123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1373123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization for PATRICIA trie map. 1383123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 1393123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, Mapped, _Alloc, pat_trie_tag, Policy_Tl> 1403123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 1413123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 1423123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 1433123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 1443123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1453123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 1463123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef pat_trie_map<Key, Mapped, at1t, _Alloc> type; 1473123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 1483123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1493123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization for PATRICIA trie set. 1503123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename _Alloc, typename Policy_Tl> 1513123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, null_type, _Alloc, pat_trie_tag, 1523123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 1533123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 1543123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 1553123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 1563123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 1573123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1583123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 1593123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 1603123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef pat_trie_set<Key, null_type, at1t, _Alloc> type; 1613123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 1623123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1633123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization for R-B tree map. 1643123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 1653123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, Mapped, _Alloc, rb_tree_tag, Policy_Tl> 1663123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 1673123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 1683123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 1693123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 1703123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 1713123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 1723123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1733123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 1743123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 1753123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef rb_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 1763123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 1773123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1783123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization for R-B tree set. 1793123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename _Alloc, typename Policy_Tl> 1803123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, null_type, _Alloc, rb_tree_tag, 1813123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 1823123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 1833123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 1843123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 1853123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 1863123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 1873123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 1883123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1893123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 1903123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef rb_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 1913123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 1923123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1933123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization splay tree map. 1943123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 1953123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, Mapped, _Alloc, splay_tree_tag, 1963123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 1973123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 1983123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 1993123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 2003123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 2013123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 2023123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 2033123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2043123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 2053123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 2063123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef splay_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 2073123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 2083123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2093123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization splay tree set. 2103123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename _Alloc, typename Policy_Tl> 2113123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, null_type, _Alloc, splay_tree_tag, 2123123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 2133123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 2143123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 2153123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 2163123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 2173123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 2183123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 2193123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2203123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 2213123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 2223123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef splay_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 2233123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 2243123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2253123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization ordered-vector tree map. 2263123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 2273123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, Mapped, _Alloc, ov_tree_tag, Policy_Tl> 2283123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 2293123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 2303123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 2313123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 2323123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 2333123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 2343123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2353123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 2363123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 2373123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef ov_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 2383123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 2393123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2403123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization ordered-vector tree set. 2413123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename _Alloc, typename Policy_Tl> 2423123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, null_type, _Alloc, ov_tree_tag, 2433123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 2443123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 2453123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 2463123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 2473123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 2483123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 2493123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 2503123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2513123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 2523123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 2533123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef ov_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 2543123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 2553123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2563123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization colision-chaining hash map. 2573123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 2583123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, Mapped, _Alloc, cc_hash_tag, Policy_Tl> 2593123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 2603123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 2613123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 2623123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 2633123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 2643123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 2653123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 2663123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at2::type at2t; 2673123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 2683123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at3::type at3t; 2693123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 2703123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at4::type at4t; 2713123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2723123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 2733123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 2743123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef cc_ht_map<Key, Mapped, at0t, at1t, _Alloc, 2753123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh at3t::value, at4t, at2t> type; 2763123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 2773123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2783123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization colision-chaining hash set. 2793123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename _Alloc, typename Policy_Tl> 2803123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, null_type, _Alloc, cc_hash_tag, 2813123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 2823123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 2833123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 2843123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 2853123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 2863123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 2873123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 2883123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 2893123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at2::type at2t; 2903123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 2913123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at3::type at3t; 2923123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 2933123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at4::type at4t; 2943123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 2953123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 2963123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 2973123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef cc_ht_set<Key, null_type, at0t, at1t, _Alloc, 2983123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh at3t::value, at4t, at2t> type; 2993123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 3003123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 3013123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization general-probe hash map. 3023123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 3033123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, Mapped, _Alloc, gp_hash_tag, Policy_Tl> 3043123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 3053123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 3063123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 3073123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 3083123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 3093123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 3103123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 3113123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at2::type at2t; 3123123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 3133123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at3::type at3t; 3143123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 3153123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at4::type at4t; 3163123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5> at5; 3173123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at5::type at5t; 3183123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 3193123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 3203123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 3213123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef gp_ht_map<Key, Mapped, at0t, at1t, _Alloc, 3223123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh at3t::value, at4t, at5t, at2t> type; 3233123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 3243123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 3253123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Specialization general-probe hash set. 3263123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh template<typename Key, typename _Alloc, typename Policy_Tl> 3273123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh struct container_base_dispatch<Key, null_type, _Alloc, gp_hash_tag, 3283123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh Policy_Tl> 3293123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 3303123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh private: 3313123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 3323123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at0::type at0t; 3333123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 3343123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at1::type at1t; 3353123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 3363123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at2::type at2t; 3373123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 3383123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at3::type at3t; 3393123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 3403123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at4::type at4t; 3413123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5> at5; 3423123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef typename at5::type at5t; 3433123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 3443123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh public: 3453123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh /// Dispatched type. 3463123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typedef gp_ht_set<Key, null_type, at0t, at1t, _Alloc, 3473123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh at3t::value, at4t, at5t, at2t> type; 3483123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh }; 3493123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh} // namespace detail 3503123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh} // namespace __gnu_pbds 3513123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 3523123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#endif 353