aGrUM  0.13.2
multiPriorityQueue.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
27 #ifndef GUM_MULTI_PRIORITY_QUEUE_H
28 #define GUM_MULTI_PRIORITY_QUEUE_H
29 
30 #include <functional>
31 #include <initializer_list>
32 #include <sstream>
33 #include <string>
34 #include <utility>
35 #include <vector>
36 
37 #include <agrum/agrum.h>
38 #include <agrum/core/hashTable.h>
39 
40 namespace gum {
41 
42 #define GUM_MULTIPLE_PRIORITY_QUEUE_DEFAULT_CAPACITY 10
43 
44 #ifndef DOXYGEN_SHOULD_SKIP_THIS
45  // templates provided by this file
46  template < typename Val, typename Priority, typename Cmp, typename Alloc >
47  class MultiPriorityQueue;
48 
49  template < typename Val, typename Priority, typename Cmp, typename Alloc >
50  std::ostream& operator<<(std::ostream&,
51  const MultiPriorityQueue< Val, Priority, Cmp, Alloc >&);
52 
53 #endif // DOXYGEN_SHOULD_SKIP_THIS
54 
55  // ===========================================================================
56  // === PRIORITY QUEUES ===
57  // ===========================================================================
120  template < typename Val,
121  typename Priority = int,
122  typename Cmp = std::less< Priority >,
123  typename Alloc = std::allocator< Val > >
126  template < typename V, typename P, typename C, typename A >
127  friend class MultiPriorityQueue;
128 
129  public:
132  using value_type = Val;
133  using reference = Val&;
134  using const_reference = const Val&;
135  using pointer = Val*;
136  using const_pointer = const Val*;
137  using difference_type = std::ptrdiff_t;
138  using allocator_type = Alloc;
140 
142  using IndexAlloc = typename Alloc::template rebind<
143  std::pair< Val, std::vector< Size > > >::other;
144 
146  using HeapAlloc =
147  typename Alloc::template rebind< std::pair< Priority, const Val* > >::other;
148 
149  // ============================================================================
151  // ============================================================================
153 
163  explicit MultiPriorityQueue(
164  Cmp compare = Cmp(),
166 
175  explicit MultiPriorityQueue(
176  std::initializer_list< std::pair< Val, Priority > > list);
177 
184 
186 
191  template < typename OtherAlloc >
194 
200 
205 
207  // ============================================================================
209  // ============================================================================
211 
224 
236  template < typename OtherAlloc >
239 
246 
254  const Val& operator[](Size index_elt) const;
255 
257  // ============================================================================
259  // ============================================================================
261 
266  Size size() const noexcept;
267 
272  bool empty() const noexcept;
273 
279  bool contains(const Val& val) const;
280 
286  const Val& top() const;
287 
292  const Priority& topPriority() const;
293 
299  Val pop();
300 
312  Size insert(const Val& val, const Priority& priority);
313 
325  Size insert(Val&& val, Priority&& priority);
326 
337  template < typename... Args >
338  Size emplace(Args&&... args);
339 
346  void eraseTop();
347 
366  void eraseByPos(Size index);
367 
380  void erase(const Val& val);
381 
391  Size setPriorityByPos(Size index, const Priority& new_priority);
392 
402  Size setPriorityByPos(Size index, Priority&& new_priority);
403 
410  void setPriority(const Val& elt, const Priority& new_priority);
411 
424  const Priority& priority(const Val& elt) const;
425 
429  void clear();
430 
442  const HashTable< Val, std::vector< Size > >& allValues() const;
443 
448  std::string toString() const;
449 
451  // ============================================================================
453  // ============================================================================
455 
462  Size capacity() const noexcept;
463 
471  void resize(Size new_size);
472 
474 
475  private:
477  std::vector< std::pair< Priority, const Val* >, HeapAlloc > __heap;
478 
480  HashTable< Val, std::vector< Size >, IndexAlloc > __indices;
481 
483  Size __nb_elements{0};
484 
486  Cmp __cmp;
487  };
488 
489 } /* namespace gum */
490 
491 
492 extern template class gum::MultiPriorityQueue< std::string >;
493 extern template class gum::MultiPriorityQueue< int, int >;
494 
495 
496 // always include the implementation of the templates
498 
499 #endif /* GUM_MULTI_PRIORITY_QUEUE_H */
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
void setPriority(const Val &elt, const Priority &new_priority)
Modifies the priority of each instance of a given element.
Size setPriorityByPos(Size index, const Priority &new_priority)
Modifies the priority of the element at position "index" of the queue.
std::vector< std::pair< Priority, const Val * >, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size __nb_elements
The number of elements in the heap.
std::string toString() const
Displays the content of the queue.
Cmp __cmp
Comparison function.
void clear()
Removes all the elements from the queue.
const Priority & priority(const Val &elt) const
Returns the priority of an instance of the value passed in argument.
#define GUM_MULTIPLE_PRIORITY_QUEUE_DEFAULT_CAPACITY
typename std::allocator< gum::LeafPair * >::template rebind< std::pair< double, const gum::LeafPair ** > >::other HeapAlloc
The allocator for the heap.
void erase(const Val &val)
Removes a given element from the priority queue (but does not return it).
Size size() const noexcept
Returns the number of elements in the priority queue.
STL namespace.
typename std::allocator< gum::LeafPair * >::template rebind< std::pair< gum::LeafPair *, std::vector< Size > > >::other IndexAlloc
The allocator for the indices.
<agrum/FMDP/learning/datastructure/leaves/leafPair.h>
Definition: leafPair.h:48
Val pop()
Removes the top element from the priority queue and return it.
void eraseByPos(Size index)
Removes the element at position "index" from the priority queue.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
bool empty() const noexcept
Indicates whether the priority queue is empty.
The class for generic Hash Tables.
Definition: hashTable.h:676
Size capacity() const noexcept
Return the size of the internal structure storing the priority queue.
const HashTable< Val, std::vector< Size > > & allValues() const
Returns a gum::HashTable the keys of which are the values stored in the queue.
std::ostream & operator<<(std::ostream &output, const BayesNet< GUM_SCALAR > &bn)
Prints map&#39;s DAG in output using the Graphviz-dot format.
Definition: BayesNet_tpl.h:573
Size insert(const Val &val, const Priority &priority)
Inserts a new (a copy) element in the priority queue.
void resize(Size new_size)
Changes the size of the internal structure storing the priority queue.
Size emplace(Args &&...args)
Emplace a new element into the priority queue.
Template implementations of multi priority queues.
MultiPriorityQueue< Val, Priority, Cmp, Alloc > & operator=(const MultiPriorityQueue< Val, Priority, Cmp, Alloc > &from)
Copy operator.
const Priority & topPriority() const
Returns the priority of the top element.
~MultiPriorityQueue()
Class destructor.
const Val & operator[](Size index_elt) const
Returns the element at index "index_elt" from the priority queue.
const Val & top() const
Returns the element at the top of the priority queue.
void eraseTop()
Removes the top of the priority queue (but does not return it).
Class hash tables iterators.
A MultiPriorityQueue is a heap in which each element has a mutable priority and duplicates are allowe...
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.
bool contains(const Val &val) const
Indicates whether the priority queue contains a given value.