STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
addressable_queues.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/common/addressable_queues.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2010-2011 Raoul Steffen <[email protected]>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER
14 #define STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER
15 
16 #include <set>
17 #include <list>
18 #include <map>
19 
20 #include <stxxl/bits/namespace.h>
21 
23 
24 //! An internal fifo queue that allows removing elements addressed with (a copy
25 //! of) themselves.
26 //! \tparam KeyType Type of contained elements.
27 template <typename KeyType>
29 {
30  typedef std::list<KeyType> container_type;
31  typedef typename container_type::iterator container_iterator;
32  typedef std::map<KeyType, container_iterator> meta_type;
33  typedef typename meta_type::iterator meta_iterator;
34 
37 
38 public:
39  //! Type of handle to an entry. For use with insert and remove.
41 
42  //! Create an empty queue.
45 
46  //! Check if queue is empty.
47  //! \return If queue is empty.
48  bool empty() const
49  { return vals.empty(); }
50 
51  //! Insert new element. If the element is already in, it is moved to the
52  //! back.
53  //! \param e Element to insert.
54  //! \return pair<handle, bool> Iterator to element; if element was newly
55  //! inserted.
56  std::pair<handle, bool> insert(const KeyType& e)
57  {
58  container_iterator ei = vals.insert(vals.end(), e);
59  std::pair<handle, bool> r = meta.insert(std::make_pair(e, ei));
60  if (! r.second)
61  {
62  // element was already in
63  vals.erase(r.first->second);
64  r.first->second = ei;
65  }
66  return r;
67  }
68 
69  //! Erase element from the queue.
70  //! \param e Element to remove.
71  //! \return If element was in.
72  bool erase(const KeyType& e)
73  {
74  handle mi = meta.find(e);
75  if (mi == meta.end())
76  return false;
77  vals.erase(mi->second);
78  meta.erase(mi);
79  return true;
80  }
81 
82  //! Erase element from the queue.
83  //! \param i Iterator to element to remove.
84  void erase(handle i)
85  {
86  vals.erase(i->second);
87  meta.erase(i);
88  }
89 
90  //! Access top element in the queue.
91  //! \return Const reference to top element.
92  const KeyType & top() const
93  { return vals.front(); }
94 
95  //! Remove top element from the queue.
96  //! \return Top element.
97  KeyType pop()
98  {
99  assert(! empty());
100  const KeyType e = top();
101  meta.erase(e);
102  vals.pop_front();
103  return e;
104  }
105 };
106 
107 //! An internal priority queue that allows removing elements addressed with (a
108 //! copy of) themselves.
109 //! \tparam KeyType Type of contained elements.
110 //! \tparam PriorityType Type of Priority.
111 template <typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType> >
113 {
114  struct cmp // like < for pair, but uses Cmp for < on first
115  {
116  bool operator () (const std::pair<PriorityType, KeyType>& left,
117  const std::pair<PriorityType, KeyType>& right) const
118  {
119  Cmp c;
120  return c(left.first, right.first) ||
121  ((! c(right.first, left.first)) && left.second < right.second);
122  }
123  };
124 
125  typedef std::set<std::pair<PriorityType, KeyType>, cmp> container_type;
126  typedef typename container_type::iterator container_iterator;
127  typedef std::map<KeyType, container_iterator> meta_type;
128  typedef typename meta_type::iterator meta_iterator;
129 
132 
133 public:
134  //! Type of handle to an entry. For use with insert and remove.
136 
137  //! Create an empty queue.
140 
141  //! Check if queue is empty.
142  //! \return If queue is empty.
143  bool empty() const
144  { return vals.empty(); }
145 
146  //! Insert new element. If the element is already in, it's priority is updated.
147  //! \param e Element to insert.
148  //! \param o Priority of element.
149  //! \return pair<handle, bool> Iterator to element; if element was newly inserted.
150  std::pair<handle, bool> insert(const KeyType& e, const PriorityType o)
151  {
152  std::pair<container_iterator, bool> s = vals.insert(std::make_pair(o, e));
153  std::pair<handle, bool> r = meta.insert(std::make_pair(e, s.first));
154  if (! r.second && s.second)
155  {
156  // was already in with different priority
157  vals.erase(r.first->second);
158  r.first->second = s.first;
159  }
160  return r;
161  }
162 
163  //! Erase element from the queue.
164  //! \param e Element to remove.
165  //! \return If element was in.
166  bool erase(const KeyType& e)
167  {
168  handle mi = meta.find(e);
169  if (mi == meta.end())
170  return false;
171  vals.erase(mi->second);
172  meta.erase(mi);
173  return true;
174  }
175 
176  //! Erase element from the queue.
177  //! \param i Iterator to element to remove.
178  void erase(handle i)
179  {
180  vals.erase(i->second);
181  meta.erase(i);
182  }
183 
184  //! Access top (= min) element in the queue.
185  //! \return Const reference to top element.
186  const KeyType & top() const
187  { return vals.begin()->second; }
188 
189  //! Remove top (= min) element from the queue.
190  //! \return Top element.
191  KeyType pop()
192  {
193  assert(! empty());
194  const KeyType e = top();
195  meta.erase(e);
196  vals.erase(vals.begin());
197  return e;
198  }
199 };
200 
202 
203 #endif // !STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER
container_type::iterator container_iterator
std::pair< handle, bool > insert(const KeyType &e)
Insert new element. If the element is already in, it is moved to the back.
An internal priority queue that allows removing elements addressed with (a copy of) themselves...
container_type::iterator container_iterator
std::pair< handle, bool > insert(const KeyType &e, const PriorityType o)
Insert new element. If the element is already in, it&#39;s priority is updated.
const KeyType & top() const
Access top (= min) element in the queue.
bool erase(const KeyType &e)
Erase element from the queue.
const KeyType & top() const
Access top element in the queue.
addressable_fifo_queue()
Create an empty queue.
std::map< KeyType, container_iterator > meta_type
std::list< KeyType > container_type
meta_iterator handle
Type of handle to an entry. For use with insert and remove.
bool empty() const
Check if queue is empty.
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
meta_iterator handle
Type of handle to an entry. For use with insert and remove.
meta_type::iterator meta_iterator
addressable_priority_queue()
Create an empty queue.
bool erase(const KeyType &e)
Erase element from the queue.
KeyType pop()
Remove top (= min) element from the queue.
void erase(handle i)
Erase element from the queue.
void erase(handle i)
Erase element from the queue.
An internal fifo queue that allows removing elements addressed with (a copy of) themselves.
bool empty() const
Check if queue is empty.
std::set< std::pair< PriorityType, KeyType >, cmp > container_type
KeyType pop()
Remove top element from the queue.
std::map< KeyType, container_iterator > meta_type
#define STXXL_END_NAMESPACE
Definition: namespace.h:17