111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2005-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Permission to use, copy, modify, sell, and distribute this software 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// is hereby granted without fee, provided that the above copyright 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// notice appears in all copies, and that both that copyright notice 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// and this permission notice appear in supporting documentation. None 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the above authors, nor IBM Haifa Research Laboratories, make any 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// representation about the suitability of this software for any 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// purpose. It is provided "as is" without express or implied 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// warranty. 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @file pat_trie_/synth_access_traits.hpp 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Contains an implementation class for a patricia tree. 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef PB_DS_SYNTH_E_ACCESS_TRAITS_HPP 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_SYNTH_E_ACCESS_TRAITS_HPP 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/type_utils.hpp> 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_pbds 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert namespace detail 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC \ 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Type_Traits, bool Set, typename _ATraits> 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC \ 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert synth_access_traits<Type_Traits, Set, _ATraits> 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Synthetic element access traits. 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Type_Traits, bool Set, typename _ATraits> 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct synth_access_traits : public _ATraits 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _ATraits base_type; 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::const_iterator const_iterator; 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef Type_Traits type_traits; 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename type_traits::const_reference const_reference; 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename type_traits::key_const_reference key_const_reference; 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert synth_access_traits(); 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert synth_access_traits(const base_type&); 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert equal_prefixes(const_iterator, const_iterator, const_iterator, 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator, bool compare_after = true) const; 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert equal_keys(key_const_reference, key_const_reference) const; 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cmp_prefixes(const_iterator, const_iterator, const_iterator, 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator, bool compare_after = false) const; 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cmp_keys(key_const_reference, key_const_reference) const; 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline static key_const_reference 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert extract_key(const_reference); 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(key_const_reference, key_const_reference); 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline static key_const_reference 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert extract_key(const_reference, true_type); 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline static key_const_reference 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert extract_key(const_reference, false_type); 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static integral_constant<int, Set> s_set_ind; 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert integral_constant<int,Set> 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::s_set_ind; 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert synth_access_traits() 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { } 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert synth_access_traits(const _ATraits& r_traits) 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _ATraits(r_traits) 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { } 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert equal_prefixes(const_iterator b_l, const_iterator e_l, const_iterator b_r, 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator e_r, bool compare_after /*= false */) const 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (b_l != e_l) 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (b_r == e_r) 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (base_type::e_pos(*b_l) != base_type::e_pos(*b_r)) 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++b_l; 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++b_r; 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return (!compare_after || b_r == e_r); 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert equal_keys(key_const_reference r_lhs_key, 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert key_const_reference r_rhs_key) const 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return equal_prefixes(base_type::begin(r_lhs_key), 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert base_type::end(r_lhs_key), 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert base_type::begin(r_rhs_key), 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert base_type::end(r_rhs_key), 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert true); 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cmp_prefixes(const_iterator b_l, const_iterator e_l, const_iterator b_r, 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator e_r, bool compare_after /* = false*/) const 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (b_l != e_l) 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (b_r == e_r) 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const typename base_type::size_type l_pos = base_type::e_pos(*b_l); 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const typename base_type::size_type r_pos = base_type::e_pos(*b_r); 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (l_pos != r_pos) 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return l_pos < r_pos; 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++b_l; 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++b_r; 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!compare_after) 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return b_r != e_r; 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cmp_keys(key_const_reference r_lhs_key, 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert key_const_reference r_rhs_key) const 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return cmp_prefixes(base_type::begin(r_lhs_key), 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert base_type::end(r_lhs_key), 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert base_type::begin(r_rhs_key), 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert base_type::end(r_rhs_key), 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert true); 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::key_const_reference 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert extract_key(const_reference r_val) 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return extract_key(r_val, s_set_ind); } 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::key_const_reference 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert extract_key(const_reference r_val, true_type) 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return r_val; } 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::key_const_reference 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert extract_key(const_reference r_val, false_type) 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return r_val.first; } 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(key_const_reference r_lhs, key_const_reference r_rhs) 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return cmp_keys(r_lhs, r_rhs); } 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } // namespace detail 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace __gnu_pbds 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 219