URL
https://opencores.org/ocsvn/openrisc_2011-10-31/openrisc_2011-10-31/trunk
Subversion Repositories openrisc_2011-10-31
[/] [openrisc/] [tags/] [gnu-src/] [gcc-4.5.1/] [gcc-4.5.1-or32-1.0rc3/] [libstdc++-v3/] [testsuite/] [util/] [native_type/] [native_priority_queue.hpp] - Rev 424
Go to most recent revision | Compare with Previous | Blame | View Log
// -*- C++ -*- // Copyright (C) 2005, 2006, 2009 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING3. 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 native_priority_queue.hpp * Contains an adapter to Dinkumware/SGI tree tables */ #ifndef PB_DS_NATIVE_PRIORITY_QUEUE_HPP #define PB_DS_NATIVE_PRIORITY_QUEUE_HPP #include <string> #include <vector> #include <queue> #include <deque> #include <ext/pb_ds/detail/standard_policies.hpp> #include <ext/pb_ds/detail/type_utils.hpp> #include <io/xml.hpp> namespace __gnu_pbds { namespace test { namespace detail { template<typename Value_Type, bool Vector, typename Allocator> struct base_seq { private: typedef typename Allocator::template rebind<Value_Type> value_rebind; public: typedef std::vector<Value_Type, typename value_rebind::other> type; }; template<typename Value_Type, typename Allocator> struct base_seq<Value_Type, false, Allocator> { private: typedef typename Allocator::template rebind<Value_Type> value_rebind; public: typedef std::deque<Value_Type, typename value_rebind::other> type; }; } // namespace detail struct native_pq_tag { }; #define PB_DS_CLASS_C_DEC \ native_priority_queue<Value_Type, Vector, Cmp_Fn, Allocator> #define PB_DS_BASE_C_DEC \ std::priority_queue<Value_Type, typename detail::base_seq<Value_Type, Vector, Allocator>::type, Cmp_Fn> template<typename Value_Type, bool Vector, typename Cmp_Fn = std::less<Value_Type>, typename Allocator = std::allocator<char> > class native_priority_queue : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; typedef typename Allocator::template rebind<Value_Type> value_rebind; public: typedef Value_Type value_type; typedef typename value_rebind::other::const_reference const_reference; typedef native_pq_tag container_category; typedef Cmp_Fn cmp_fn; native_priority_queue() : base_type() { } template<typename It> native_priority_queue(It f, It l) : base_type(f, l) { } static std::string name() { if (Vector) return ("n_pq_vector"); return ("n_pq_deque"); } static std::string desc() { if (Vector) return make_xml_tag("type", "value", "std::priority_queue_vector"); return make_xml_tag("type", "value", "std::priority_queue_deque"); } void clear() { *static_cast<base_type*>(this) = base_type(); } void erase(const_reference r_val) { base_type tmp; Cmp_Fn cmp; while (cmp(base_type::top(), r_val) || cmp(r_val, base_type::top())) { tmp.push(base_type::top()); base_type::pop(); } if (!base_type::empty()) { base_type::pop(); while (!base_type::empty()) { tmp.push(base_type::top()); base_type::pop(); } } *static_cast<base_type* >(this) = tmp; } template<typename Pred> size_t erase_if(Pred pred) { base_type tmp; std::size_t ersd = 0; while (!base_type::empty()) { if (!pred(base_type::top())) tmp.push(base_type::top()); else ++ersd; base_type::pop(); } *static_cast<base_type*>(this) = tmp; return ersd; } template<typename Pred> void split(Pred pred, PB_DS_CLASS_C_DEC& other) { base_type tmp; other.clear(); while (!base_type::empty()) { if (!pred(base_type::top())) tmp.push(base_type::top()); else other.push(base_type::top()); base_type::pop(); } *static_cast<base_type*>(this) = tmp; } void modify(const_reference r_old, const_reference r_new) { erase(r_old); push(r_new); } void join(PB_DS_CLASS_C_DEC& other) { std::vector<value_type> a_tmp; while (!base_type::empty()) { a_tmp.push_back(base_type::top()); base_type::pop(); } while (!other.empty()) { a_tmp.push_back(other.top()); other.pop(); } *static_cast<base_type*>(this) = base_type(a_tmp.begin(), a_tmp.end()); } Cmp_Fn get_cmp_fn() const { return Cmp_Fn(); } }; #undef PB_DS_BASE_C_DEC #undef PB_DS_CLASS_C_DEC } // namespace test } // namespace __gnu_pbds #endif
Go to most recent revision | Compare with Previous | Blame | View Log