// -*- 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
// .
// 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
#include
#include
#include
#include
#include
#include
namespace __gnu_pbds
{
namespace test
{
namespace detail
{
template
struct base_seq
{
private:
typedef typename Allocator::template rebind value_rebind;
public:
typedef std::vector type;
};
template
struct base_seq
{
private:
typedef typename Allocator::template rebind value_rebind;
public:
typedef std::deque type;
};
} // namespace detail
struct native_pq_tag
{ };
#define PB_DS_CLASS_C_DEC \
native_priority_queue
#define PB_DS_BASE_C_DEC \
std::priority_queue::type, Cmp_Fn>
template,
typename Allocator = std::allocator >
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_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
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(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(this) = tmp;
}
template
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(this) = tmp;
return ersd;
}
template
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(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 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(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