gomp-20050608-branch/libstdc++-v3/include/ext/pb_assoc/tree_policy.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /*
  41  * @file tree_policy.hpp
  42  * Contains tree-related policies.
  43  */
  44
  45 #ifndef TREE_POLICY_HPP
  46 #define TREE_POLICY_HPP
  47
  48 #include <functional>
  49 #include <ext/pb_assoc/ms_trait.hpp>
  50
  51 namespace pb_assoc
  52 {
  53   struct null_node_updator
  54   {
  55     inline void
  56     swap(null_node_updator& r_other);
  57   };
  58
  59 #include <ext/pb_assoc/detail/tree_policy/null_node_updator_imp.hpp>
  60
  61   template<typename Key, typename Allocator = std::allocator<char> >
  62     class order_statistics_key
  63     {
  64     public:
  65       typedef Allocator                         allocator;
  66       typedef Key                               key_type;
  67       typedef typename allocator::template rebind<Key>::other::const_reference
  68                                                 const_key_reference;
  69       typedef typename allocator::template rebind<Key>::other::reference
  70                                                 key_reference;
  71       typedef typename allocator::size_type     size_type;
  72
  73       inline explicit
  74       order_statistics_key(const_key_reference r_key = Key());
  75
  76       inline
  77       operator key_reference();
  78
  79       inline
  80       operator key_type() const;
  81
  82     private:
  83       // The logical key of the entry.
  84       key_type m_key;
  85
  86       // The number of entries in the subtree rooted at the node of
  87       // this element.
  88       mutable size_type m_rank;
  89
  90       template<typename Cntnr>
  91         friend class order_by_key;
  92
  93       template<typename Some_Cmp_Fn, typename Some_Allocator>
  94         friend class order_statistics_key_cmp;
  95
  96       template<typename Some_Key, typename Some_Allocator>
  97         friend class order_statistics_node_updator;
  98
  99       template<typename Cntnr>
 100         friend class find_by_order;
 101
 102       template<typename Cntnr, typename Some_Allocator>
 103         friend class order_statistics_key_verifier;
 104   };
 105
 106   template<typename Cmp_Fn, typename Allocator = std::allocator<char> >
 107     class order_statistics_key_cmp
 108     : public std::binary_function<
 109       order_statistics_key<typename Cmp_Fn::first_argument_type, Allocator>,
 110       order_statistics_key<typename Cmp_Fn::second_argument_type, Allocator>, bool>,
 111     private Cmp_Fn
 112     {
 113     public:
 114       typedef Allocator allocator;
 115       typedef Cmp_Fn cmp_fn;
 116
 117       typedef
 118       order_statistics_key<typename Cmp_Fn::first_argument_type, Allocator>
 119       key_type;
 120
 121       typedef
 122       typename allocator::template rebind<key_type>::other::const_reference
 123       const_key_reference;
 124
 125       inline
 126       order_statistics_key_cmp();
 127
 128       inline
 129       order_statistics_key_cmp(const Cmp_Fn& r_cmp_fn);
 130
 131       inline bool
 132       operator()(const_key_reference, const_key_reference) const;
 133
 134       inline cmp_fn&
 135       get_cmp_fn();
 136
 137       inline const cmp_fn&
 138       get_cmp_fn() const;
 139     };
 140
 141 #define PB_ASSOC_CLASS_C_DEC \
 142         order_statistics_node_updator<Key, Allocator>
 143
 144   template<typename Key, typename Allocator = std::allocator<char> >
 145     class order_statistics_node_updator
 146     {
 147     public:
 148       typedef Allocator allocator;
 149       typedef order_statistics_key< Key, Allocator> key_type;
 150
 151       typedef
 152       typename Allocator::template rebind<key_type>::other::const_pointer
 153       const_key_pointer;
 154
 155       inline void
 156       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 157
 158       inline void
 159       operator()(const_key_pointer, const_key_pointer, const_key_pointer);
 160
 161     private:
 162       typedef typename Allocator::size_type size_type;
 163     };
 164
 165 #undef PB_ASSOC_CLASS_C_DEC
 166
 167   template<class Cntnr>
 168     class find_by_order
 169     {
 170     public:
 171       typedef Cntnr                             cntnr;
 172       typedef typename cntnr::iterator          iterator;
 173       typedef typename cntnr::const_iterator    const_iterator;
 174       typedef typename cntnr::size_type         size_type;
 175
 176       inline iterator
 177       operator()(Cntnr& r_c, size_type order) const;
 178
 179       inline const_iterator
 180       operator()(const Cntnr& r_c, size_type order) const;
 181
 182     private:
 183       typedef typename Cntnr::node_iterator     node_iterator;
 184       typedef typename Cntnr::const_iterator    cntnr_const_it;
 185       typedef typename Cntnr::iterator          cntnr_it;
 186
 187       inline static iterator
 188       find(Cntnr& r_c, size_type order);
 189
 190       inline static const_iterator
 191       find(const Cntnr& r_c, size_type order);
 192     };
 193
 194   template<class Cntnr>
 195     class order_by_key
 196     {
 197     public:
 198       typedef Cntnr                             cntnr;
 199       typedef typename Cntnr::key_type          order_statistics_key_type;
 200       typedef typename order_statistics_key_type::key_type
 201                                                 underlying_key_type;
 202       typedef typename cntnr::size_type         size_type;
 203
 204       inline size_type
 205       operator()(const Cntnr& r_c, const underlying_key_type& r_key) const;
 206
 207     private:
 208       typedef typename cntnr::const_iterator cntnr_const_it;
 209       typedef typename cntnr::iterator cntnr_it;
 210     };
 211
 212 #include <ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp>
 213 } // namespace pb_assoc
 214
 215 #endif // #ifndef TREE_POLICY_HPP