types_traits.hpp

Go to the documentation of this file.

// -*- C++ -*-

// Copyright (C) 2005, 2006, 2009, 2011 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 <utility>

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>
      struct stored_data
      : public stored_value<_Tv>, public stored_hash<_Th>
      { };

    /// Specialization for representation of stored data of just value type.
    template<typename _Tv>
      struct stored_data<_Tv, null_type>
      : public stored_value<_Tv>
      { };

    /// Primary template.
    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
      struct type_base;

    /**
     * Specialization of type_base for the case where the hash value
     * is not stored alongside each value.
     */
    template<typename Key, typename Mapped, typename _Alloc>
      struct type_base<Key, Mapped, _Alloc, false>
      {
      public:
    typedef typename _Alloc::size_type      size_type;

      private:
    typedef typename _Alloc::template rebind<Mapped>    __rebind_m;
    typedef typename __rebind_m::other          __rebind_ma;
    typedef std::pair<const Key, Mapped>            __value_type;
    typedef typename _Alloc::template rebind<__value_type>  __rebind_v;
        typedef typename __rebind_v::other          __rebind_va;

      public:
    typedef typename __rebind_ma::value_type        mapped_type;
    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::value_type    value_type;
    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, null_type>  stored_data_type;
      };

    /**
     * Specialization of type_base for the case where the hash value
     * is stored alongside each value.
     */
    template<typename Key, typename Mapped, typename _Alloc>
      struct type_base<Key, Mapped, _Alloc, true>
      {
      public:
    typedef typename _Alloc::size_type      size_type;

      private:
    typedef typename _Alloc::template rebind<Mapped>    __rebind_m;
    typedef typename __rebind_m::other          __rebind_ma;
    typedef std::pair<const Key, Mapped>            __value_type;
    typedef typename _Alloc::template rebind<__value_type>  __rebind_v;
        typedef typename __rebind_v::other          __rebind_va;

      public:
    typedef typename __rebind_ma::value_type        mapped_type;
    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::value_type    value_type;
    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>  stored_data_type;
      };


    /**
     * Specialization of type_base for the case where the hash value
     * is not stored alongside each value.
     */
    template<typename Key, typename _Alloc>
      struct type_base<Key, null_type, _Alloc, false>
      {
      public:
    typedef typename _Alloc::size_type      size_type;
    typedef Key                     value_type;

      private:
    typedef typename _Alloc::template rebind<null_type>     __rebind_m;
    typedef typename __rebind_m::other          __rebind_ma;
    typedef typename _Alloc::template rebind<value_type>    __rebind_v;
        typedef typename __rebind_v::other          __rebind_va;

      public:
    typedef typename __rebind_ma::value_type        mapped_type;
    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, null_type>  stored_data_type;

    static null_type            s_null_type;
      };

    template<typename Key, typename _Alloc>
      null_type
      type_base<Key, null_type, _Alloc, false>::s_null_type;


    /**
     * Specialization of type_base for the case where the hash value
     * is stored alongside each value.
     */
    template<typename Key, typename _Alloc>
      struct type_base<Key, null_type, _Alloc, true>
      {
      public:
    typedef typename _Alloc::size_type      size_type;
    typedef Key                     value_type;

      private:
    typedef typename _Alloc::template rebind<null_type>     __rebind_m;
    typedef typename __rebind_m::other          __rebind_ma;
    typedef typename _Alloc::template rebind<value_type>    __rebind_v;
        typedef typename __rebind_v::other          __rebind_va;

      public:
    typedef typename __rebind_ma::value_type        mapped_type;
    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>  stored_data_type;

    static null_type                s_null_type;
      };

    template<typename Key, typename _Alloc>
      null_type
      type_base<Key, null_type, _Alloc, true>::s_null_type;


    /// Type base dispatch.
    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
      struct type_dispatch
      {
    typedef type_base<Key, Mapped, _Alloc, Store_Hash> type;
      };

    /// Traits for abstract types.
    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
      struct types_traits
      : public type_dispatch<Key, Mapped, _Alloc, Store_Hash>::type
      {
      private:
    typedef no_throw_copies<Key, Mapped>        __nothrowcopy;
    typedef typename _Alloc::template rebind<Key>::other __rebind_a;

      public:
    typedef typename _Alloc::size_type      size_type;
    typedef typename __rebind_a::value_type     key_type;
    typedef typename __rebind_a::pointer        key_pointer;
    typedef typename __rebind_a::const_pointer  key_const_pointer;
    typedef typename __rebind_a::reference      key_reference;
    typedef typename __rebind_a::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