1// -*- C++ -*-
2
3// Copyright (C) 2005-2015 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
48namespace __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
225