types_traits.hpp

Go to the documentation of this file.

// -*- C++ -*-
 
// Copyright (C) 2005-2020 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
 * @file detail/types_traits.hpp
 * Contains a traits class of types used by containers.
 */
 
#ifndef PB_DS_TYPES_TRAITS_HPP
#define PB_DS_TYPES_TRAITS_HPP
 
#include <algorithm>
#include <utility>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <memory>
 
namespace __gnu_pbds
{
  namespace detail
  {
    /**
     *  @addtogroup traits Traits
     *  @{
     */
 
    /// Primary template.
    template<typename Key, typename Mapped>
      struct no_throw_copies
      {
        static const bool __simple = is_simple<Key>::value
                                 && is_simple<Mapped>::value;
        typedef integral_constant<int, __simple>                indicator;
      };
 
    /// Specialization.
    template<typename Key>
      struct no_throw_copies<Key, null_type>
      {
        typedef integral_constant<int, is_simple<Key>::value>   indicator;
      };
 
 
    /// Stored value.
    template<typename _Tv>
      struct stored_value
      {
        typedef _Tv     value_type;
        value_type      m_value;
      };
 
    /// Stored hash.
    template<typename _Th>
      struct stored_hash
      {
        typedef _Th     hash_type;
        hash_type       m_hash;
      };
 
    /// Primary template for representation of stored data.
    /// Two types of data can be stored: value and hash.
    template<typename _Tv, typename _Th, bool Store_Hash>
      struct stored_data
      : public stored_value<_Tv>, public stored_hash<_Th>
      { };
 
    /// Specialization for representation of stored data of just value type.
    template<typename _Tv, typename _Th>
      struct stored_data<_Tv, _Th, false>
      : public stored_value<_Tv>
      { };
 
    /// Choose value_type to be a key/value pair or just a key.
    template<typename Key, typename Mapped>
      struct select_value_type
      {
        typedef std::pair<const Key, Mapped> type;
      };
 
    /// Specialization for sets where the key is the value_type.
    template<typename Key>
      struct select_value_type<Key, null_type>
      {
        typedef Key type;
      };
 
    /// Base class for conditionally defining a static data member.
    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
      struct maybe_null_type
      { };
 
    /// Specialization that defines a static data member of type null_type.
    template<typename Key,typename _Alloc, bool Store_Hash>
      struct maybe_null_type<Key, null_type, _Alloc, Store_Hash>
      {
        static null_type s_null_type;
      };
 
    template<typename Key,typename _Alloc, bool Store_Hash>
      null_type
      maybe_null_type<Key, null_type, _Alloc, Store_Hash>::s_null_type;
 
    /// Consistent API for accessing allocator-related types.
    template<typename _Alloc, typename T>
      struct rebind_traits
#if __cplusplus >= 201103L
      : std::allocator_traits<_Alloc>::template rebind_traits<T>
      {
        using reference = T&;
        using const_reference = const T&;
      };
#else
      : _Alloc::template rebind<T>::other
      {
        typedef typename _Alloc::template rebind<T>::other allocator_type;
      };
#endif
 
 
    /// Traits for abstract types.
    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
      struct types_traits
      : public maybe_null_type<Key, Mapped, _Alloc, Store_Hash>
      {
      public:
        typedef typename _Alloc::size_type                      size_type;
        typedef typename select_value_type<Key, Mapped>::type   value_type;
        typedef Key                                             key_type;
        typedef Mapped                                          mapped_type;
 
      private:
        typedef rebind_traits<_Alloc, value_type>       __rebind_va;
        typedef rebind_traits<_Alloc, key_type>         __rebind_ka;
        typedef rebind_traits<_Alloc, mapped_type>      __rebind_ma;
 
        typedef no_throw_copies<Key, Mapped>            __nothrowcopy;
 
      public:
        typedef typename __rebind_ma::pointer           mapped_pointer;
        typedef typename __rebind_ma::const_pointer     mapped_const_pointer;
        typedef typename __rebind_ma::reference         mapped_reference;
        typedef typename __rebind_ma::const_reference   mapped_const_reference;
 
        typedef typename __rebind_va::pointer           pointer;
        typedef typename __rebind_va::const_pointer     const_pointer;
        typedef typename __rebind_va::reference         reference;
        typedef typename __rebind_va::const_reference   const_reference;
 
        typedef stored_data<value_type, size_type, Store_Hash> stored_data_type;
 
        typedef typename __rebind_ka::pointer           key_pointer;
        typedef typename __rebind_ka::const_pointer     key_const_pointer;
        typedef typename __rebind_ka::reference         key_reference;
        typedef typename __rebind_ka::const_reference   key_const_reference;
        typedef std::pair<size_type, size_type>         comp_hash;
        typedef integral_constant<int, Store_Hash>      store_extra;
        typedef typename __nothrowcopy::indicator       no_throw_indicator;
 
        store_extra                             m_store_extra_indicator;
        no_throw_indicator                      m_no_throw_copies_indicator;
    };
    ///@}
  } // namespace detail
} // namespace __gnu_pbds
 
#endif