gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc > Class Template Reference

A MultiPriorityQueue is a heap in which each element has a mutable priority and duplicates are allowedA priority queue is quite similar to a heap except that a priority (a score) is assigned to each element in the structure. More...

#include <agrum/tools/core/multiPriorityQueue.h>

Collaboration diagram for gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >:

Public Member Functions
template<typename... Args>
INLINE Size	emplace (Args &&... args)
Constructors / Destructors
	MultiPriorityQueue (Cmp compare=Cmp(), Size capacity=GUM_MULTIPLE_PRIORITY_QUEUE_DEFAULT_CAPACITY)
	Basic constructor. More...
	MultiPriorityQueue (std::initializer_list< std::pair< Val, Priority > > list)
	Initializer list constructor. More...
	MultiPriorityQueue (const MultiPriorityQueue< Val, Priority, Cmp, Alloc > &from)
	Copy constructor. More...
template<typename OtherAlloc >
	MultiPriorityQueue (const MultiPriorityQueue< Val, Priority, Cmp, OtherAlloc > &from)
	generalized copy constructor More...
	MultiPriorityQueue (MultiPriorityQueue< Val, Priority, Cmp, Alloc > &&from)
	Move constructor. More...
	~MultiPriorityQueue ()
	Class destructor. More...
Operators
MultiPriorityQueue< Val, Priority, Cmp, Alloc > &	operator= (const MultiPriorityQueue< Val, Priority, Cmp, Alloc > &from)
	Copy operator. More...
template<typename OtherAlloc >
MultiPriorityQueue< Val, Priority, Cmp, Alloc > &	operator= (const MultiPriorityQueue< Val, Priority, Cmp, OtherAlloc > &from)
	Generalized copy operator. More...
MultiPriorityQueue< Val, Priority, Cmp, Alloc > &	operator= (MultiPriorityQueue< Val, Priority, Cmp, Alloc > &&from)
	Move operator. More...
const Val &	operator[] (Size index_elt) const
	Returns the element at index "index_elt" from the priority queue. More...
Accessors / Modifiers
Size	size () const noexcept
	Returns the number of elements in the priority queue. More...
bool	empty () const noexcept
	Indicates whether the priority queue is empty. More...
bool	contains (const Val &val) const
	Indicates whether the priority queue contains a given value. More...
const Val &	top () const
	Returns the element at the top of the priority queue. More...
const Priority &	topPriority () const
	Returns the priority of the top element. More...
Val	pop ()
	Removes the top element from the priority queue and return it. More...
Size	insert (const Val &val, const Priority &priority)
	Inserts a new (a copy) element in the priority queue. More...
Size	insert (Val &&val, Priority &&priority)
	Inserts (by move) a new element in the priority queue. More...
template<typename... Args>
Size	emplace (Args &&... args)
	Emplace a new element into the priority queue. More...
void	eraseTop ()
	Removes the top of the priority queue (but does not return it). More...
void	eraseByPos (Size index)
	Removes the element at position "index" from the priority queue. More...
void	erase (const Val &val)
	Removes a given element from the priority queue (but does not return it). More...
Size	setPriorityByPos (Size index, const Priority &new_priority)
	Modifies the priority of the element at position "index" of the queue. More...
Size	setPriorityByPos (Size index, Priority &&new_priority)
	Modifies the priority of the element at position "index" of the queue. More...
void	setPriority (const Val &elt, const Priority &new_priority)
	Modifies the priority of each instance of a given element. More...
const Priority &	priority (const Val &elt) const
	Returns the priority of an instance of the value passed in argument. More...
void	clear ()
	Removes all the elements from the queue. More...
const HashTable< Val, std::vector< Size > > &	allValues () const
	Returns a gum::HashTable the keys of which are the values stored in the queue. More...
std::string	toString () const
	Displays the content of the queue. More...
Fine tuning
Size	capacity () const noexcept
	Return the size of the internal structure storing the priority queue. More...
void	resize (Size new_size)
	Changes the size of the internal structure storing the priority queue. More...

Public Types
using	IndexAlloc = typename Alloc::template rebind< std::pair< Val, std::vector< Size > > >::other
	The allocator for the indices. More...
using	HeapAlloc = typename Alloc::template rebind< std::pair< Priority, const Val *> >::other
	The allocator for the heap. More...
using	value_type = Val
	types for STL compliance More...
using	reference = Val &
	types for STL compliance More...
using	const_reference = const Val &
	types for STL compliance More...
using	pointer = Val *
	types for STL compliance More...
using	const_pointer = const Val *
	types for STL compliance More...
using	difference_type = std::ptrdiff_t
	types for STL compliance More...
using	allocator_type = Alloc
	types for STL compliance More...

Friends
template<typename V , typename P , typename C , typename A >
class	MultiPriorityQueue
	Making all MultiPriorityQueue friend with themselves. More...

Detailed Description

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
class gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >

A MultiPriorityQueue is a heap in which each element has a mutable priority and duplicates are allowed

A priority queue is quite similar to a heap except that a priority (a score) is assigned to each element in the structure.

The elements are sorted according to a weak order on the scores. The priority of any element can be changed at any moment by the user. The priority queue then restores a heap property accordingly.

Usage example:

// create a priority queue of strings, the priorities of which are
// integers the element at the top of the queue has the smallest priority
MultiPriorityQueue<std::string> queue1;

// insert elements into the queue
queue1.insert (8,  "AAA");
queue1.insert (10, "BBB");
queue1.insert (2,  "CCC");
queue1.insert (23, "DDD");
queue1.insert (24, "EEE");
queue1.insert (10, "AAA");

// copy the queue
MultiPriorityQueue<std::string> queue2 = queue1;

// initializer list constructor
MultiPriorityQueue<std::string,int>
queue3 { std::pair<std::string,int> ( "aa", 3 ),
         std::pair<std::string,int> ( "bb", 2 ) };

// create a priority queue of strings, the priorities of which are
// pairs of ints
MultiPriorityQueue< std::string, std::pair<int,int> > queue3;

// get the top element, then remove it
std::cerr << queue2.top() << std::endl;
queue2.eraseTop();

// get the top element, then remove it
std::cerr << queue2.pop() << std::endl;

// output the content of the queue
std::cerr << queue1 << std::endl;

// change the priority of the element at position 3
Size new_pos=queue1.setPriorityByPos (3,100);

// change the priority of all instances of element "AAA"
queue1.setPriority ("AAA",100);

Template Parameters

Val	The values type stored in the gum::MultiPriorityQueue.
Priority	The priorities type.
Cmp	The priorities comparator.
Alloc	The values allocator.

Definition at line 126 of file multiPriorityQueue.h.

Member Typedef Documentation

allocator_type

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::allocator_type = Alloc

types for STL compliance

Definition at line 140 of file multiPriorityQueue.h.

const_pointer

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::const_pointer = const Val*

types for STL compliance

Definition at line 138 of file multiPriorityQueue.h.

const_reference

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::const_reference = const Val&

types for STL compliance

Definition at line 136 of file multiPriorityQueue.h.

difference_type

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::difference_type = std::ptrdiff_t

types for STL compliance

Definition at line 139 of file multiPriorityQueue.h.

HeapAlloc

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::HeapAlloc = typename Alloc::template rebind< std::pair< Priority, const Val* > >::other

The allocator for the heap.

Definition at line 149 of file multiPriorityQueue.h.

IndexAlloc

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::IndexAlloc = typename Alloc::template rebind< std::pair< Val, std::vector< Size > > >::other

The allocator for the indices.

Definition at line 145 of file multiPriorityQueue.h.

pointer

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::pointer = Val*

types for STL compliance

Definition at line 137 of file multiPriorityQueue.h.

reference

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::reference = Val&

types for STL compliance

Definition at line 135 of file multiPriorityQueue.h.

value_type

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::value_type = Val

types for STL compliance

Definition at line 134 of file multiPriorityQueue.h.

Constructor & Destructor Documentation

MultiPriorityQueue() [1/5]

template<typename Val , typename Priority , typename Cmp, typename Alloc >

gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::MultiPriorityQueue ( Cmp  compare = Cmp(), Size  capacity = GUM_MULTIPLE_PRIORITY_QUEUE_DEFAULT_CAPACITY  )

explicit

Basic constructor.

Creates an empty priority queue.

Parameters

compare	a function taking two elements in argument, say e1 and e2, and returning a Boolean indicating wether e1 < e2, i.e., whether e1 should be nearer than e2 to the top of the heap.
capacity	the size of the internal data structures containing the elements (could be for instance vectors or hashtables).

Definition at line 36 of file multiPriorityQueue_tpl.h.

                    :
      indices__(capacity >> 1, true, false),
      cmp__(compare) {
    heap__.reserve(capacity);

    // for debugging purposes
    GUM_CONSTRUCTOR(MultiPriorityQueue);
  }

MultiPriorityQueue() [2/5]

template<typename Val, typename Priority, typename Cmp, typename Alloc >

gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::MultiPriorityQueue ( std::initializer_list< std::pair< Val, Priority > >  list )

explicit

Initializer list constructor.

The elements of the initializer list are pairs <Val,Priority>. The comparison function is the default one, i.e., std::less<Priority>.

Parameters

list	The initializer list.

Definition at line 49 of file multiPriorityQueue_tpl.h.

                                                           :
      indices__(Size(list.size()) / 2, true, false) {
    // fill the queue
    heap__.reserve(list.size());
    for (const auto& elt: list) {
      insert(elt.first, elt.second);
    }

    // for debugging purposes
    GUM_CONSTRUCTOR(MultiPriorityQueue);
  }

MultiPriorityQueue() [3/5]

template<typename Val, typename Priority, typename Cmp, typename Alloc>

gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::MultiPriorityQueue

(

const MultiPriorityQueue< Val, Priority, Cmp, Alloc > &

from

)

Copy constructor.

Parameters

from	The gum::MultiPriorityQueue to copy.

Definition at line 64 of file multiPriorityQueue_tpl.h.

                                                                  :
      heap__(from.heap__),
      indices__(from.indices__), nb_elements__(from.nb_elements__),
      cmp__(from.cmp__) {
    // for debugging purposes
    GUM_CONS_CPY(MultiPriorityQueue);

    // fill the heap structure
    for (const auto& val_and_index: indices__) {
      const Val*                 val  = &(val_and_index.first);
      const std::vector< Size >& vect = val_and_index.second;
      for (auto index: vect) {
        heap__[index].second = val;
      }
    }
  }

MultiPriorityQueue() [4/5]

template<typename Val, typename Priority, typename Cmp, typename Alloc >

template<typename OtherAlloc >

gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::MultiPriorityQueue

(

const MultiPriorityQueue< Val, Priority, Cmp, OtherAlloc > &

from

)

generalized copy constructor

Generalized Copy constructor.

Parameters

from	The gum::MultiPriorityQueue to copy.

Template Parameters

OtherAlloc

The other gum::MultiPriorityQueue allocator.

Definition at line 85 of file multiPriorityQueue_tpl.h.

                                                                       :
      indices__(from.indices__),
      nb_elements__(from.nb_elements__), cmp__(from.cmp__) {
    // for debugging purposes
    GUM_CONS_CPY(MultiPriorityQueue);

    // fill the heap structure
    if (nb_elements__) {
      heap__.reserve(from.heap__.size());
      for (const auto& elt: from.heap__) {
        heap__.push_back(elt);
      }
      for (const auto& val_and_index: indices__) {
        const Val*                 val  = &(val_and_index.first);
        const std::vector< Size >& vect = val_and_index.second;
        for (auto index: vect) {
          heap__[index].second = val;
        }
      }
    }
  }

MultiPriorityQueue() [5/5]

template<typename Val, typename Priority, typename Cmp, typename Alloc>

gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::MultiPriorityQueue

(

MultiPriorityQueue< Val, Priority, Cmp, Alloc > &&

from

)

Move constructor.

Parameters

from	The gum::MultiPriorityQueue to move.

Definition at line 110 of file multiPriorityQueue_tpl.h.

                                                             :
      heap__(std::move(from.heap__)),
      indices__(std::move(from.indices__)),
      nb_elements__(std::move(from.nb_elements__)), cmp__(std::move(from.cmp__)) {
    // for debugging purposes
    GUM_CONS_MOV(MultiPriorityQueue);
  }

~MultiPriorityQueue()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::~MultiPriorityQueue

(

)

Class destructor.

Definition at line 121 of file multiPriorityQueue_tpl.h.

                                                                       {
    // for debugging purposes
    GUM_DESTRUCTOR(MultiPriorityQueue);
  }

Member Function Documentation

allValues()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const HashTable< Val, std::vector< Size > > & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::allValues

(

)

const

Returns a gum::HashTable the keys of which are the values stored in the queue.

The keys of the gum::HashTable correspond to the values stored in the priority queue and, for each key, the corresponding value is the list of indices in the queue where we can find the key.

Returns

Returns a gum::HashTable the keys of which are the values stored in the queue.

Definition at line 360 of file multiPriorityQueue_tpl.h.

                                                                                {
    return reinterpret_cast< const HashTable< Val, std::vector< Size > >& >(
       indices__);
  }

capacity()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::capacity ( ) const

noexcept

Return the size of the internal structure storing the priority queue.

Returns

Return the size of the internal structure storing the priority queue.

Definition at line 249 of file multiPriorityQueue_tpl.h.

                                                                              {
    return Size(heap__.capacity());
  }

clear()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

void gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::clear

(

)

Removes all the elements from the queue.

Definition at line 265 of file multiPriorityQueue_tpl.h.

                                                              {
    nb_elements__ = 0;
    heap__.clear();
    indices__.clear();
  }

contains()

template<typename Val, typename Priority , typename Cmp , typename Alloc >

INLINE bool gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::contains

(

const Val &

val

)

const

Indicates whether the priority queue contains a given value.

Parameters

val	The value to check if it is in the priority queue.

Returns

Returns true if the priority queue cotains the given value.

Definition at line 501 of file multiPriorityQueue_tpl.h.

                           {
    return indices__.exists(val);
  }

emplace() [1/2]

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

template<typename... Args>

Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::emplace

(

Args &&...

args

)

Emplace a new element into the priority queue.

See method gum::MultiPriorityQueue::eraseByPos(Size) for more details about the index.

Template Parameters

Args	The emplace arguments types.

Parameters

args	The emplace arguments.

Returns

the index of the element inserted into the priority queue.

emplace() [2/2]

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

template<typename... Args>

INLINE Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::emplace

(

Args &&...

args

)

Definition at line 486 of file multiPriorityQueue_tpl.h.

                                                                            {
    std::pair< Val, Priority > new_elt
       = std::make_pair< Val, Priority >(std::forward< Args >(args)...);
    return insert(std::move(new_elt.first), std::move(new_elt.second));
  }

empty()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE bool gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::empty ( ) const

noexcept

Indicates whether the priority queue is empty.

Returns

Indicates whether the priority queue is empty.

Definition at line 495 of file multiPriorityQueue_tpl.h.

                                                                           {
    return (nb_elements__ == 0);
  }

erase()

template<typename Val, typename Priority , typename Cmp , typename Alloc >

INLINE void gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::erase

(

const Val &

val

)

Removes a given element from the priority queue (but does not return it).

If the element cannot be found, the function returns without throwing any exception.

If the queue contains several times this element, then the one with the smallest index is removed.

Parameters

val	the element we wish to remove.

Definition at line 334 of file multiPriorityQueue_tpl.h.

                                                                          {
    try {
      eraseByPos(indices__[val][0]);
    } catch (NotFound&) {}
  }

eraseByPos()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

void gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::eraseByPos

(

Size

index

)

Removes the element at position "index" from the priority queue.

If the element cannot be found, the function returns without throwing any exception.

The priority is computed as follows: suppose that the queue is a complete binary tree where all levels are completely filled except, eventually, the last one. In this case, the elements of the last level are all on the left of the tree.

We assign 0 to the root, then parsing the tree from top to bottom then from left to right we increment the index and assigned it to the current node. Doing so, we get a unique index for each element. This is precisely what the index passed in argument of the function represents.

Parameters

index

represents the position of the element to be removed.

Definition at line 273 of file multiPriorityQueue_tpl.h.

                                                                             {
    if (index >= nb_elements__) return;

    // remove the element from the hashtable
    const Val&           del_val    = *(heap__[index].second);
    std::vector< Size >& vect_index = indices__[del_val];
    if (vect_index.size() == 1)
      indices__.erase(del_val);
    else {
      for (auto& v_index: vect_index) {
        if (v_index == index) {
          v_index = vect_index.back();
          vect_index.pop_back();
          break;
        }
      }
    }

    // put the last element at the "index" location
    std::pair< Priority, const Val* > last = std::move(heap__.back());
    heap__.pop_back();
    --nb_elements__;

    if (!nb_elements__ || (index == nb_elements__)) return;

    // restore the heap property
    Size i = index;

    for (Size j = (index << 1) + 1; j < nb_elements__; i = j, j = (j << 1) + 1) {
      // let j be the max child
      if ((j + 1 < nb_elements__) && cmp__(heap__[j + 1].first, heap__[j].first))
        ++j;

      // if "last" is lower than heap[j], "last" must be stored at index i
      if (cmp__(last.first, heap__[j].first)) break;

      // else pull up the jth node
      heap__[i]                       = std::move(heap__[j]);
      std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
      for (auto& v_index: vect_index) {
        if (v_index == j) {
          v_index = i;
          break;
        }
      }
    }

    // put "last" back into the heap
    heap__[i]                         = std::move(last);
    std::vector< Size >& last_indices = indices__[*(heap__[i].second)];
    for (auto& v_index: last_indices) {
      if (v_index == nb_elements__) {
        v_index = i;
        break;
      }
    }
  }

eraseTop()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE void gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::eraseTop

(

)

Removes the top of the priority queue (but does not return it).

If the heap is empty, it does nothing (in particular, it does not throw any exception).

Definition at line 342 of file multiPriorityQueue_tpl.h.

                                                                        {
    eraseByPos(0);
  }

insert() [1/2]

template<typename Val, typename Priority, typename Cmp , typename Alloc >

Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::insert	(	const Val &	val,
		const Priority &	priority
	)

Inserts a new (a copy) element in the priority queue.

See method gum::MultiPriorityQueue::eraseByPos(Size) for more details about the index.

Parameters

val	The value to insert.
priority	The value priority.

Returns

Returns the index of the element inserted into the priority queue.

Definition at line 367 of file multiPriorityQueue_tpl.h.

                               {
    // create the entry in the indices hashtable
    const Val*           new_val;
    std::vector< Size >* new_vect;
    if (!indices__.exists(val)) {
      auto& new_elt = indices__.insert(val, std::vector< Size >());
      new_val       = &(new_elt.first);
      new_vect      = &(new_elt.second);
    } else {
      new_val  = &(indices__.key(val));
      new_vect = &(indices__[val]);
    }

    try {
      new_vect->push_back(0);
    } catch (...) {
      if (new_vect->empty()) { indices__.erase(val); }
      throw;
    }

    try {
      heap__.push_back(std::pair< Priority, const Val* >(priority, new_val));
    } catch (...) {
      if (new_vect->size() == 1) { indices__.erase(val); }
      throw;
    }

    std::pair< Priority, const Val* > new_heap_val
       = std::move(heap__[nb_elements__]);
    ++nb_elements__;

    // restore the heap property
    Size i = nb_elements__ - 1;

    for (Size j = (i - 1) >> 1; i && cmp__(new_heap_val.first, heap__[j].first);
         i = j, j = (j - 1) >> 1) {
      heap__[i]                       = std::move(heap__[j]);
      std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
      for (auto& index: vect_index) {
        if (index == j) {
          index = i;
          break;
        }
      }
    }

    // put the new bucket into the heap
    heap__[i].first  = std::move(new_heap_val.first);
    heap__[i].second = new_val;
    new_vect->back() = i;

    return i;
  }

insert() [2/2]

template<typename Val, typename Priority, typename Cmp , typename Alloc >

Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::insert	(	Val &&	val,
		Priority &&	priority
	)

Inserts (by move) a new element in the priority queue.

See method gum::MultiPriorityQueue::eraseByPos(Size) for more details about the index.

Parameters

val	The value to insert.
priority	The value priority.

Returns

Returns the index of the element inserted into the priority queue.

Definition at line 426 of file multiPriorityQueue_tpl.h.

                                                                                  {
    // create the entry in the indices hashtable
    const Val*           new_val;
    std::vector< Size >* new_vect;
    if (!indices__.exists(val)) {
      auto& new_elt = indices__.insert(std::move(val), std::vector< Size >());
      new_val       = &(new_elt.first);
      new_vect      = &(new_elt.second);
    } else {
      new_val  = &(indices__.key(val));
      new_vect = &(indices__[val]);
    }

    try {
      new_vect->push_back(0);
    } catch (...) {
      if (new_vect->empty()) { indices__.erase(*new_val); }
      throw;
    }

    try {
      heap__.push_back(
         std::pair< Priority, const Val* >(std::move(priority), new_val));
    } catch (...) {
      if (new_vect->size() == 1) { indices__.erase(*new_val); }
      throw;
    }

    std::pair< Priority, const Val* > new_heap_val
       = std::move(heap__[nb_elements__]);
    ++nb_elements__;

    // restore the heap property
    Size i = nb_elements__ - 1;

    for (Size j = (i - 1) >> 1; i && cmp__(new_heap_val.first, heap__[j].first);
         i = j, j = (j - 1) >> 1) {
      heap__[i]                       = std::move(heap__[j]);
      std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
      for (auto& index: vect_index) {
        if (index == j) {
          index = i;
          break;
        }
      }
    }

    // put the new bucket into the heap
    heap__[i].first  = std::move(new_heap_val.first);
    heap__[i].second = new_val;
    new_vect->back() = i;

    return i;
  }

operator=() [1/3]

template<typename Val, typename Priority, typename Cmp, typename Alloc>

MultiPriorityQueue< Val, Priority, Cmp, Alloc > & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::operator=

(

const MultiPriorityQueue< Val, Priority, Cmp, Alloc > &

from

)

Copy operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the priority queue becomes empty. An exception is then thrown.

Parameters

from	The gum::MultiPriorityQueue to copy.

Definition at line 129 of file multiPriorityQueue_tpl.h.

                                                                     {
    // for debugging purposes
    GUM_OP_CPY(MultiPriorityQueue);

    try {
      // set the comprison function
      cmp__ = from.cmp__;

      // copy the indices and the heap
      indices__     = from.indices__;
      heap__        = from.heap__;
      nb_elements__ = from.nb_elements__;

      // restore the link between indices__ and heap__
      for (const auto& val_and_index: indices__) {
        const Val*                 val  = &(val_and_index.first);
        const std::vector< Size >& vect = val_and_index.second;
        for (auto index: vect) {
          heap__[index].second = val;
        }
      }
    } catch (...) {
      heap__.clear();
      indices__.clear();
      nb_elements__ = 0;

      throw;
    }

    return *this;
  }

operator=() [2/3]

template<typename Val, typename Priority, typename Cmp, typename Alloc >

template<typename OtherAlloc >

MultiPriorityQueue< Val, Priority, Cmp, Alloc > & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::operator=

(

const MultiPriorityQueue< Val, Priority, Cmp, OtherAlloc > &

from

)

Generalized copy operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the priority queue becomes empty. An exception is then thrown.

Parameters

from	The gum::MultiPriorityQueue to copy.

Template Parameters

OtherAlloc

The other gum::MultiPriorityQueue allocator.

Definition at line 166 of file multiPriorityQueue_tpl.h.

                                                                          {
    // for debugging purposes
    GUM_OP_CPY(MultiPriorityQueue);

    try {
      // set the comprison function
      cmp__ = from.cmp__;

      // copy the indices and the heap
      indices__     = from.indices__;
      nb_elements__ = from.nb_elements__;

      // restore the link between indices__ and heap__
      heap__.clear();
      heap__.reserve(from.heap__.size());
      for (const auto& elt: from.heap__) {
        heap__.push_back(elt);
      }
      for (const auto& val_and_index: indices__) {
        const Val*                 val  = &(val_and_index.first);
        const std::vector< Size >& vect = val_and_index.second;
        for (auto index: vect) {
          heap__[index].second = val;
        }
      }
    } catch (...) {
      heap__.clear();
      indices__.clear();
      nb_elements__ = 0;

      throw;
    }

    return *this;
  }

operator=() [3/3]

template<typename Val, typename Priority, typename Cmp, typename Alloc>

MultiPriorityQueue< Val, Priority, Cmp, Alloc > & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::operator=

(

MultiPriorityQueue< Val, Priority, Cmp, Alloc > &&

from

)

Move operator.

Parameters

from	The gum::MultiPriorityQueue to copy.

Definition at line 206 of file multiPriorityQueue_tpl.h.

                                                                {
    // avoid self assignment
    if (this != &from) {
      // for debugging purposes
      GUM_OP_MOV(MultiPriorityQueue);

      cmp__         = std::move(from.cmp__);
      indices__     = std::move(from.indices__);
      heap__        = std::move(from.heap__);
      nb_elements__ = std::move(from.nb_elements__);
    }

    return *this;
  }

operator[]()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const Val & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::operator[]

(

Size

index_elt

)

const

Returns the element at index "index_elt" from the priority queue.

Parameters

index_elt

The index of the element to return.

Returns

Returns the element at index "index_elt" from the priority queue.

Exceptions

NotFound

Raised if the element does not exist.

Definition at line 508 of file multiPriorityQueue_tpl.h.

                       {
    if (index >= nb_elements__) {
      GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
    }

    return *(heap__[index].second);
  }

pop()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE Val gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::pop

(

)

Removes the top element from the priority queue and return it.

Returns

Returns the top element from the priority queue.

Exceptions

NotFound

Raised if the queue is empty.

Definition at line 348 of file multiPriorityQueue_tpl.h.

                                                                  {
    if (!nb_elements__) { GUM_ERROR(NotFound, "empty priority queue"); }

    Val v = *(heap__[0].second);
    eraseByPos(0);

    return v;
  }

priority()

template<typename Val, typename Priority , typename Cmp , typename Alloc >

INLINE const Priority & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::priority

(

const Val &

elt

)

const

Returns the priority of an instance of the value passed in argument.

Of course, this method is really meaningful only when there is only one instance of the given element within the PriorityQueue.

Parameters

elt	The element for which the priority is returned.

Returns

Returns the priority of an instance of the value passed in argument.

Exceptions

NotFound

Raised if the element cannot be found.

Definition at line 675 of file multiPriorityQueue_tpl.h.

                           {
    return heap__[indices__[elt][0]].first;
  }

resize()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE void gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::resize

(

Size

new_size

)

Changes the size of the internal structure storing the priority queue.

Parameters

new_size

The internal structure new size.

Returns

Changes the size of the internal structure storing the priority queue.

Definition at line 256 of file multiPriorityQueue_tpl.h.

                                                                          {
    if (new_size < nb_elements__) return;

    heap__.reserve(new_size);
    indices__.resize(new_size / 2);
  }

setPriority()

template<typename Val, typename Priority, typename Cmp , typename Alloc >

void gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::setPriority	(	const Val &	elt,
		const Priority &	new_priority
	)

Modifies the priority of each instance of a given element.

Parameters

elt	The value to update.
new_priority	The values new priority.

Exceptions

NotFound

Raised if the element cannot be found.

Definition at line 663 of file multiPriorityQueue_tpl.h.

                                   {
    std::vector< Size >& vect_index = indices__[elt];

    for (auto index: vect_index) {
      setPriorityByPos(index, new_priority);
    }
  }

setPriorityByPos() [1/2]

template<typename Val , typename Priority, typename Cmp , typename Alloc >

Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::setPriorityByPos	(	Size	index,
		const Priority &	new_priority
	)

Modifies the priority of the element at position "index" of the queue.

Parameters

index	The index of the element to update.
new_priority	The element's new priority.

Returns

Returns the elements new priority.

Exceptions

NotFound

Raised if the element cannot be found.

Definition at line 537 of file multiPriorityQueue_tpl.h.

                                   {
    // check whether the element the priority of which should be changed exists
    if (index >= nb_elements__) {
      GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
    }

    // get the element itself
    const Val* val = heap__[index].second;

    // restore the heap property
    Size i = index;

    // move val upward if needed
    for (Size j = (i - 1) >> 1; i && cmp__(new_priority, heap__[j].first);
         i = j, j = (j - 1) >> 1) {
      heap__[i]                       = std::move(heap__[j]);
      std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
      for (auto& idx: vect_index) {
        if (idx == j) {
          idx = i;
          break;
        }
      }
    }

    // move val downward if needed
    for (Size j = (i << 1) + 1; j < nb_elements__; i = j, j = (j << 1) + 1) {
      // let j be the max child
      if ((j + 1 < nb_elements__) && cmp__(heap__[j + 1].first, heap__[j].first))
        ++j;

      // if "val" is lower than heap[j], "val" must be stored at index i
      if (cmp__(new_priority, heap__[j].first)) break;

      // else pull up the jth node
      heap__[i]                       = std::move(heap__[j]);
      std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
      for (auto& idx: vect_index) {
        if (idx == j) {
          idx = i;
          break;
        }
      }
    }

    // update the index of val
    heap__[i].first                 = new_priority;
    heap__[i].second                = val;
    std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
    for (auto& idx: vect_index) {
      if (idx == index) {
        idx = i;
        break;
      }
    }

    return i;
  }

setPriorityByPos() [2/2]

template<typename Val , typename Priority, typename Cmp , typename Alloc >

Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::setPriorityByPos	(	Size	index,
		Priority &&	new_priority
	)

Modifies the priority of the element at position "index" of the queue.

Parameters

index	The index of the element to update.
new_priority	The element's new priority.

Returns

Returns the elements new priority.

Exceptions

NotFound

Raised if the element cannot be found.

Definition at line 600 of file multiPriorityQueue_tpl.h.

                              {
    // check whether the element the priority of which should be changed exists
    if (index >= nb_elements__) {
      GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
    }

    // get the element itself
    const Val* val = heap__[index].second;

    // restore the heap property
    Size i = index;

    // move val upward if needed
    for (Size j = (i - 1) >> 1; i && cmp__(new_priority, heap__[j].first);
         i = j, j = (j - 1) >> 1) {
      heap__[i]                       = std::move(heap__[j]);
      std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
      for (auto& idx: vect_index) {
        if (idx == j) {
          idx = i;
          break;
        }
      }
    }

    // move val downward if needed
    for (Size j = (i << 1) + 1; j < nb_elements__; i = j, j = (j << 1) + 1) {
      // let j be the max child
      if ((j + 1 < nb_elements__) && cmp__(heap__[j + 1].first, heap__[j].first))
        ++j;

      // if "val" is lower than heap[j], "val" must be stored at index i
      if (cmp__(new_priority, heap__[j].first)) break;

      // else pull up the jth node
      heap__[i]                       = std::move(heap__[j]);
      std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
      for (auto& idx: vect_index) {
        if (idx == j) {
          idx = i;
          break;
        }
      }
    }

    // update the index of val
    heap__[i].first                 = std::move(new_priority);
    heap__[i].second                = val;
    std::vector< Size >& vect_index = indices__[*(heap__[i].second)];
    for (auto& idx: vect_index) {
      if (idx == index) {
        idx = i;
        break;
      }
    }

    return i;
  }

size()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::size ( ) const

noexcept

Returns the number of elements in the priority queue.

Returns

Returns the number of elements in the priority queue.

Definition at line 242 of file multiPriorityQueue_tpl.h.

                                                                          {
    return nb_elements__;
  }

top()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const Val & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::top

(

)

const

Returns the element at the top of the priority queue.

Returns

Returns the element at the top of the priority queue.

Exceptions

NotFound

Raised if the queue is empty.

Definition at line 224 of file multiPriorityQueue_tpl.h.

                                                                               {
    if (!nb_elements__) { GUM_ERROR(NotFound, "empty priority queue"); }

    return *(heap__[0].second);
  }

topPriority()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const Priority & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::topPriority

(

)

const

Returns the priority of the top element.

Exceptions

NotFound

Raised if the queue is empty.

Definition at line 233 of file multiPriorityQueue_tpl.h.

                                                                        {
    if (!nb_elements__) { GUM_ERROR(NotFound, "empty priority queue"); }

    return heap__[0].first;
  }

toString()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

std::string gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::toString

(

)

const

Displays the content of the queue.

Returns

Returns the content of the queue.

Definition at line 519 of file multiPriorityQueue_tpl.h.

                                                                            {
    bool              deja = false;
    std::stringstream stream;
    stream << "[";

    for (Size i = 0; i != nb_elements__; ++i, deja = true) {
      if (deja) stream << " , ";

      stream << "(" << heap__[i].first << " , " << *(heap__[i].second) << ")";
    }

    stream << "]";

    return stream.str();
  }

Friends And Related Function Documentation

MultiPriorityQueue

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

template<typename V , typename P , typename C , typename A >

friend class MultiPriorityQueue

friend

Making all MultiPriorityQueue friend with themselves.

Definition at line 129 of file multiPriorityQueue.h.

Member Data Documentation

cmp__

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

Cmp gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::cmp__

private

Comparison function.

Definition at line 488 of file multiPriorityQueue.h.

heap__

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

std::vector< std::pair< Priority, const Val* >, HeapAlloc > gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::heap__

private

An array storing all the elements of the heap as well as their score.

Definition at line 479 of file multiPriorityQueue.h.

indices__

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

HashTable< Val, std::vector< Size >, IndexAlloc > gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::indices__

private

A hashtable for quickly finding the elements by their value.

Definition at line 482 of file multiPriorityQueue.h.

nb_elements__

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>

Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::nb_elements__ {0}

private

The number of elements in the heap.

Definition at line 485 of file multiPriorityQueue.h.

---

The documentation for this class was generated from the following files:

• agrum/tools/core/multiPriorityQueue.h
• agrum/tools/core/multiPriorityQueue_tpl.h