libstdc++-v3/testsuite/util/native_type/native_priority_queue.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2013 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 terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20
  21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  22
  23 // Permission to use, copy, modify, sell, and distribute this software
  24 // is hereby granted without fee, provided that the above copyright
  25 // notice appears in all copies, and that both that copyright notice
  26 // and this permission notice appear in supporting documentation. None
  27 // of the above authors, nor IBM Haifa Research Laboratories, make any
  28 // representation about the suitability of this software for any
  29 // purpose. It is provided "as is" without express or implied
  30 // warranty.
  31
  32 /**
  33  * @file native_priority_queue.hpp
  34  * Contains an adapter to Dinkumware/SGI tree tables
  35  */
  36
  37 #ifndef PB_DS_NATIVE_PRIORITY_QUEUE_HPP
  38 #define PB_DS_NATIVE_PRIORITY_QUEUE_HPP
  39
  40 #include <string>
  41 #include <vector>
  42 #include <queue>
  43 #include <deque>
  44 #include <ext/pb_ds/detail/standard_policies.hpp>
  45 #include <ext/pb_ds/detail/type_utils.hpp>
  46 #include <io/xml.hpp>
  47
  48 namespace __gnu_pbds
  49 {
  50   namespace test
  51   {
  52     namespace detail
  53     {
  54       template<typename Value_Type, bool Vector, typename _Alloc>
  55       struct base_seq
  56       {
  57       private:
  58         typedef typename _Alloc::template rebind<Value_Type> value_rebind;
  59
  60       public:
  61         typedef std::vector<Value_Type, typename value_rebind::other> type;
  62       };
  63
  64       template<typename Value_Type, typename _Alloc>
  65       struct base_seq<Value_Type, false, _Alloc>
  66       {
  67       private:
  68         typedef typename _Alloc::template rebind<Value_Type> value_rebind;
  69
  70       public:
  71         typedef std::deque<Value_Type, typename value_rebind::other> type;
  72       };
  73     } // namespace detail
  74
  75     struct native_pq_tag
  76     { };
  77
  78 #define PB_DS_CLASS_C_DEC \
  79     native_priority_queue<Value_Type, Vector, Cmp_Fn, _Alloc>
  80
  81 #define PB_DS_BASE_C_DEC \
  82     std::priority_queue<Value_Type, typename detail::base_seq<Value_Type, Vector, _Alloc>::type, Cmp_Fn>
  83
  84     template<typename Value_Type,
  85              bool Vector,
  86              typename Cmp_Fn = std::less<Value_Type>,
  87              typename _Alloc = std::allocator<char> >
  88     class native_priority_queue : public PB_DS_BASE_C_DEC
  89     {
  90     private:
  91       typedef PB_DS_BASE_C_DEC base_type;
  92       typedef typename _Alloc::template rebind<Value_Type> value_rebind;
  93
  94     public:
  95       typedef Value_Type value_type;
  96       typedef typename value_rebind::other::const_reference const_reference;
  97       typedef native_pq_tag container_category;
  98       typedef Cmp_Fn cmp_fn;
  99
 100       native_priority_queue() : base_type()
 101       { }
 102
 103       template<typename It>
 104       native_priority_queue(It f, It l) : base_type(f, l)
 105       { }
 106
 107       static std::string
 108       name()
 109       {
 110         if (Vector)
 111           return ("n_pq_vector");
 112         return ("n_pq_deque");
 113       }
 114
 115       static std::string
 116       desc()
 117       {
 118         if (Vector)
 119           return make_xml_tag("type", "value", "std::priority_queue_vector");
 120         return make_xml_tag("type", "value", "std::priority_queue_deque");
 121       }
 122
 123       void
 124       clear()
 125       { *static_cast<base_type*>(this) = base_type(); }
 126
 127       void
 128       erase(const_reference r_val)
 129       {
 130         base_type tmp;
 131         Cmp_Fn cmp;
 132
 133         while (cmp(base_type::top(), r_val) || cmp(r_val, base_type::top()))
 134           {
 135             tmp.push(base_type::top());
 136             base_type::pop();
 137           }
 138
 139         if (!base_type::empty())
 140           {
 141             base_type::pop();
 142             while (!base_type::empty())
 143               {
 144                 tmp.push(base_type::top());
 145                 base_type::pop();
 146               }
 147           }
 148         *static_cast<base_type* >(this) = tmp;
 149       }
 150
 151       template<typename Pred>
 152       size_t
 153       erase_if(Pred pred)
 154       {
 155         base_type tmp;
 156         std::size_t ersd = 0;
 157         while (!base_type::empty())
 158           {
 159             if (!pred(base_type::top()))
 160               tmp.push(base_type::top());
 161             else
 162               ++ersd;
 163             base_type::pop();
 164           }
 165
 166         *static_cast<base_type*>(this) = tmp;
 167         return ersd;
 168       }
 169
 170       template<typename Pred>
 171       void
 172       split(Pred pred, PB_DS_CLASS_C_DEC& other)
 173       {
 174         base_type tmp;
 175         other.clear();
 176         while (!base_type::empty())
 177           {
 178             if (!pred(base_type::top()))
 179               tmp.push(base_type::top());
 180             else
 181               other.push(base_type::top());
 182             base_type::pop();
 183           }
 184         *static_cast<base_type*>(this) = tmp;
 185       }
 186
 187       void
 188       modify(const_reference r_old, const_reference r_new)
 189       {
 190         erase(r_old);
 191         this->push(r_new);
 192       }
 193
 194       void
 195       join(PB_DS_CLASS_C_DEC& other)
 196       {
 197         std::vector<value_type> a_tmp;
 198         while (!base_type::empty())
 199           {
 200             a_tmp.push_back(base_type::top());
 201             base_type::pop();
 202           }
 203
 204         while (!other.empty())
 205           {
 206             a_tmp.push_back(other.top());
 207             other.pop();
 208           }
 209
 210         *static_cast<base_type*>(this) = base_type(a_tmp.begin(), a_tmp.end());
 211       }
 212
 213       Cmp_Fn
 214       get_cmp_fn() const
 215       { return Cmp_Fn(); }
 216     };
 217
 218 #undef PB_DS_BASE_C_DEC
 219 #undef PB_DS_CLASS_C_DEC
 220
 221   } // namespace test
 222 } // namespace __gnu_pbds
 223
 224 #endif